.net面试常见算法题

以下是一些常见的 .NET 面试算法题，这些问题涵盖了不同难度级别，可以帮助你准备面试时的算法部分：

反转字符串

题目：编写一个函数，将输入的字符串反转过来。

public string ReverseString(string s) {
    char[] charArray = s.ToCharArray();
    Array.Reverse(charArray);
    return new string(charArray);
}

判断回文字符串

题目：编写一个函数，判断一个给定的字符串是否是回文字符串（正着读和反着读都一样）。

public bool IsPalindrome(string s) {
    s = Regex.Replace(s, "[^a-zA-Z0-9]", "").ToLower();
    return s == new string(s.Reverse().ToArray());
}

找出两个数组的交集

题目：给定两个整数数组，编写一个函数来计算它们的交集。

public static int[] FindIntersection(int[] nums1, int[] nums2)
    {
        HashSet<int> set = new HashSet<int>();
        List<int> intersection = new List<int>();

        foreach (int num in nums1)
        {
            set.Add(num);
        }

        foreach (int num in nums2)
        {
            if (set.Contains(num))
            {
                intersection.Add(num);
                set.Remove(num); // To avoid duplicates in the result
            }
        }

        return intersection.ToArray();
    }

判断是否是有效的括号序列

题目：给定一个只包括 '('、')'、'{'、'}'、'[' 和 ']' 的字符串，编写一个函数来判断字符串是否有效。

public static bool IsValid(string s)
    {
        Stack<char> stack = new Stack<char>();

        foreach (char c in s)
        {
            if (c == '(' || c == '[' || c == '{')
            {
                stack.Push(c);
            }
            else if (c == ')' && (stack.Count == 0 || stack.Pop() != '('))
            {
                return false;
            }
            else if (c == ']' && (stack.Count == 0 || stack.Pop() != '['))
            {
                return false;
            }
            else if (c == '}' && (stack.Count == 0 || stack.Pop() != '{'))
            {
                return false;
            }
        }

        return stack.Count == 0;
    }

两数之和

题目：给定一个整数数组 nums 和一个目标值 target，在数组中找出和为目标值的两个数的索引。

public int[] TwoSum(int[] nums, int target) {
    Dictionary<int, int> map = new Dictionary<int, int>();
    for (int i = 0; i < nums.Length; i++) {
        int complement = target - nums[i];
        if (map.ContainsKey(complement)) {
            return new int[] { map[complement], i };
        }
        map[nums[i]] = i;
    }
    throw new ArgumentException("No two sum solution");
}

最大子序和

题目：给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素）。

public static int MaxSubArray(int[] nums)
    {
        if (nums.Length == 0) return 0;

        int maxSum = nums[0];
        int currentSum = nums[0];

        for (int i = 1; i < nums.Length; i++)
        {
            currentSum = Math.Max(nums[i], currentSum + nums[i]);
            maxSum = Math.Max(maxSum, currentSum);
        }

        return maxSum;
    }

判断链表是否有环

题目：给定一个链表，判断链表中是否有环。

public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int val = 0)
    {
        this.val = val;
        this.next = null;
    }
}

public class LinkedListCycleChecker
{
    public static bool HasCycle(ListNode head)
    {
        if (head == null || head.next == null)
            return false;

        ListNode slow = head;
        ListNode fast = head.next;

        while (slow != fast)
        {
            if (fast == null || fast.next == null)
                return false;

            slow = slow.next;
            fast = fast.next.next;
        }

        return true;
    }
}

class Program
{
    static void Main(string[] args)
    {
        ListNode head1 = new ListNode(3);
        head1.next = new ListNode(2);
        head1.next.next = new ListNode(0);
        head1.next.next.next = new ListNode(-4);
        head1.next.next.next.next = head1.next; // Create a cycle

        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(2);
        head2.next.next = head2; // Create a cycle

        Console.WriteLine(LinkedListCycleChecker.HasCycle(head1)); // true
        Console.WriteLine(LinkedListCycleChecker.HasCycle(head2)); // true
    }
}

合并两个有序链表

题目：将两个有序链表合并为一个新的有序链表。

public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int val = 0)
    {
        this.val = val;
        this.next = null;
    }
}

public class MergeSortedLists
{
    public static ListNode Merge(ListNode l1, ListNode l2)
    {
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;

        while (l1 != null && l2 != null)
        {
            if (l1.val < l2.val)
            {
                current.next = l1;
                l1 = l1.next;
            }
            else
            {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        if (l1 != null)
            current.next = l1;
        if (l2 != null)
            current.next = l2;

        return dummy.next;
    }
}

搜索旋转排序数组

题目：假设按照升序排序的数组在预先未知的某个点上进行了旋转。编写一个函数来搜索 target。

public static int Search(int[] nums, int target)
    {
        int left = 0;
        int right = nums.Length - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target)
                return mid;

            if (nums[left] <= nums[mid])
            {
                if (nums[left] <= target && target < nums[mid])
                    right = mid - 1;
                else
                    left = mid + 1;
            }
            else
            {
                if (nums[mid] < target && target <= nums[right])
                    left = mid + 1;
                else
                    right = mid - 1;
            }
        }

        return -1;
    }

二叉树的最大深度

题目：给定一个二叉树，找出其最大深度。

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class MaxDepthFinder
{
    public static int MaxDepth(TreeNode root)
    {
        if (root == null)
            return 0;

        int leftDepth = MaxDepth(root.left);
        int rightDepth = MaxDepth(root.right);

        return Math.Max(leftDepth, rightDepth) + 1;
    }
}

class Program
{
    static void Main(string[] args)
    {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        Console.WriteLine(MaxDepthFinder.MaxDepth(root)); // 3
    }
}

有效的括号组合数

题目：给定一个只包含字符 '(' 和 ')' 的字符串，编写一个函数来生成所有可能的有效括号组合。

using System;
using System.Collections.Generic;

public class ParenthesesGenerator
{
    public static IList<string> GenerateParentheses(int n)
    {
        List<string> result = new List<string>();
        GenerateParenthesesHelper(result, "", n, n);
        return result;
    }

    private static void GenerateParenthesesHelper(List<string> result, string current, int leftRemaining, int rightRemaining)
    {
        if (leftRemaining == 0 && rightRemaining == 0)
        {
            result.Add(current);
            return;
        }

        if (leftRemaining > 0)
            GenerateParenthesesHelper(result, current + "(", leftRemaining - 1, rightRemaining);

        if (rightRemaining > leftRemaining)
            GenerateParenthesesHelper(result, current + ")", leftRemaining, rightRemaining - 1);
    }
}

class Program
{
    static void Main(string[] args)
    {
        int n = 3;
        IList<string> combinations = ParenthesesGenerator.GenerateParentheses(n);

        foreach (string combination in combinations)
        {
            Console.WriteLine(combination);
        }
    }
}

全排列

题目：给定一个没有重复数字的序列，返回其所有可能的全排列。

using System;
using System.Collections.Generic;

public class PermutationsGenerator
{
    public static IList<IList<int>> Permute(int[] nums)
    {
        List<IList<int>> result = new List<IList<int>>();
        PermuteHelper(result, new List<int>(), nums);
        return result;
    }

    private static void PermuteHelper(List<IList<int>> result, List<int> current, int[] nums)
    {
        if (current.Count == nums.Length)
        {
            result.Add(new List<int>(current));
            return;
        }

        for (int i = 0; i < nums.Length; i++)
        {
            if (current.Contains(nums[i]))
                continue;

            current.Add(nums[i]);
            PermuteHelper(result, current, nums);
            current.RemoveAt(current.Count - 1);
        }
    }
}

class Program
{
    static void Main(string[] args)
    {
        int[] nums = { 1, 2, 3 };
        IList<IList<int>> permutations = PermutationsGenerator.Permute(nums);

        foreach (var permutation in permutations)
        {
            Console.WriteLine(string.Join(", ", permutation));
        }
    }
}

二叉树的最近公共祖先

题目：给定一个二叉树，找到该树中两个指定节点的最近公共祖先。

using System;

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class LowestCommonAncestorFinder
{
    public static TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {
        if (root == null || root == p || root == q)
            return root;

        TreeNode left = LowestCommonAncestor(root.left, p, q);
        TreeNode right = LowestCommonAncestor(root.right, p, q);

        if (left != null && right != null)
            return root;

        return left != null ? left : right;
    }
}

class Program
{
    static void Main(string[] args)
    {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);

        TreeNode p = root.left;
        TreeNode q = root.right;

        TreeNode ancestor = LowestCommonAncestorFinder.LowestCommonAncestor(root, p, q);

        Console.WriteLine("Lowest Common Ancestor: " + ancestor.val); // 3
    }
}

零钱兑换

题目：给定不同面额的硬币 coins 和一个总金额 amount，编写一个函数来计算可以凑成总金额所需的最少的硬币个数。

using System;

public class CoinChangeCalculator
{
    public static int CoinChange(int[] coins, int amount)
    {
        int[] dp = new int[amount + 1];

        for (int i = 1; i <= amount; i++)
        {
            dp[i] = amount + 1; // Initialize to a value larger than amount
            foreach (int coin in coins)
            {
                if (i >= coin)
                    dp[i] = Math.Min(dp[i], dp[i - coin] + 1);
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }
}

class Program
{
    static void Main(string[] args)
    {
        int[] coins = { 1, 2, 5 };
        int amount1 = 11;
        int amount2 = 3;

        Console.WriteLine(CoinChangeCalculator.CoinChange(coins, amount1)); // 3
        Console.WriteLine(CoinChangeCalculator.CoinChange(coins, amount2)); // -1
    }
}

字符串转整数

题目：实现 atoi 函数，将字符串转为整数。

using System;

public class StringToIntegerConverter
{
    public static int Atoi(string str)
    {
        if (string.IsNullOrWhiteSpace(str))
            return 0;

        int index = 0;
        int sign = 1;
        int result = 0;

        // Skip leading spaces
        while (index < str.Length && str[index] == ' ')
            index++;

        // Check for sign
        if (index < str.Length && (str[index] == '+' || str[index] == '-'))
        {
            sign = (str[index] == '-') ? -1 : 1;
            index++;
        }

        // Convert digits
        while (index < str.Length && char.IsDigit(str[index]))
        {
            int digit = str[index] - '0';

            if (result > int.MaxValue / 10 || (result == int.MaxValue / 10 && digit > 7))
                return (sign == 1) ? int.MaxValue : int.MinValue;

            result = result * 10 + digit;
            index++;
        }

        return result * sign;
    }
}

class Program
{
    static void Main(string[] args)
    {
        string str1 = "42";
        string str2 = "   -42";
        string str3 = "4193 with words";
        string str4 = "words and 987";
        string str5 = "-91283472332";

        Console.WriteLine(StringToIntegerConverter.Atoi(str1)); // 42
        Console.WriteLine(StringToIntegerConverter.Atoi(str2)); // -42
        Console.WriteLine(StringToIntegerConverter.Atoi(str3)); // 4193
        Console.WriteLine(StringToIntegerConverter.Atoi(str4)); // 0
        Console.WriteLine(StringToIntegerConverter.Atoi(str5)); // -2147483648
    }
}

这些题目旨在帮助你练习不同类型的算法问题，从而在面试中展示你的问题解决能力和编程技巧。请在准备面试时深入理解每个问题，并尝试用 .NET 编写出解决方案。