C#常见算法面试题小结

常见算法

本文主要讲解C#常见算法，在面试或实际工作中应用较为广泛。以下是本文讨论的常见算法：

• 排序算法
• 查找算法
• 贪心算法
• 动态规划算法
• 字符串算法

排序算法

冒泡排序

冒泡排序是一种效率低下的排序，但是学习它有助于了解其他的排序算法。

冒泡排序的核心思想是重复地走访过要排序的序列，每次比较相邻的两个元素，如果他们的顺序错误就把他们交换过来。重复比较相邻元素并交换，直到最后一对元素，此时完成了一次冒泡。

下面是一个C#实现冒泡排序的示例代码：

public static void BubbleSort(int[] arr)
{
    for (int i = 0; i < arr.Length - 1; i++)
    {
        for (int j = 0; j < arr.Length - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

快速排序

快速排序是一种使用最普遍的排序算法之一。其基本思想是以分治的思想为基础，将一个大问题拆分成多个子问题，最后求解得到正确答案。在递归过程中，将问题拆分成小问题，并用一个基准值将数据划分成两半，以此达到排序的目的。

下面是一个C#实现快速排序的示例代码：

public static void QuickSort(int[] arr, int low, int high)
{
    if (low < high)
    {
        int pivot = Partition(arr, low, high);

        QuickSort(arr, low, pivot - 1);
        QuickSort(arr, pivot + 1, high);
    }
}

private static int Partition(int[] arr, int low, int high)
{
    int pivot = arr[low];
    while (low < high)
    {
        while (low < high && arr[high] >= pivot)
        {
            high--;
        }
        arr[low] = arr[high];

        while (low < high && arr[low] <= pivot)
        {
            low++;
        }
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}

查找算法

二分查找

二分查找是一种可以在有序数组中查找某个元素的高效算法。

二分查找的基本思想是将有序数组分成两半，然后看中间的元素是否是要查找的元素，如果是就返回该元素的下标；如果不是，如果中间元素小于要查找的元素，则在中点到右边继续查找；如果中间元素大于要查找的元素，则在左边继续查找。

下面是一个C#实现二分查找的示例代码：

public static int BinarySearch(int[] arr, int target)
{
    int low = 0;
    int high = arr.Length - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (arr[mid] == target)
        {
            return mid;
        }
        else if (arr[mid] < target)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }
    return -1;
}

贪心算法

贪心算法是一种优化问题的思想，它是将一个问题分解为多个局部决策问题，并将每一步的最优决策合并成全局最优解。

以下是一个问题思考:

给定一个由n个硬币组成的集合{c1,c2,c3……cn}，其中每个硬币的面值都是正整数，找出所需要的最少硬币个数，使它们的面值总和为V。

下面是一个C#实现贪心算法解决硬币问题的示例代码：

public static int CoinChange(int[] coins, int amount)
{
    Array.Sort(coins);
    int count = 0;
    for (int i = coins.Length - 1; i >= 0; i--)
    {
        while (amount >= coins[i])
        {
            count++;
            amount -= coins[i];
        }
    }
    return amount == 0 ? count : -1;
}

动态规划算法

动态规划算法是一种算法思想，通过解决子问题的方式，将问题转化为更小的、更简单的子问题，最终汇总得到结果。

动态规划算法通常可以解决最优化问题，比如最长公共子序列、最长上升子序列等。

以下是一个C#实现最长公共子序列(LCS)的示例代码：

public static string LongestCommonSubsequence(string text1, string text2)
{
    int m = text1.Length;
    int n = text2.Length;
    int[,] dp = new int[m + 1, n + 1];
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (text1[i - 1] == text2[j - 1])
            {
                dp[i, j] = dp[i - 1, j - 1] + 1;
            }
            else
            {
                dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
            }
        }
    }

    int index = dp[m, n];
    char[] res = new char[index];
    while (index > 0)
    {
        if (dp[m, n] == dp[m - 1, n])
        {
            m--;
        }
        else if (dp[m, n] == dp[m, n - 1])
        {
            n--;
        }
        else
        {
            res[--index] = text1[m - 1];
            m--;
            n--;
        }
    }
    return new string(res);
}

字符串算法

字符串算法主要涉及字符串的匹配和转换等问题。

其中，字符串中最长的回文子序列是一种经典的问题。其解题思路是利用动态规划算法，将一个字符串分成多个子问题进行求解。

以下是一个C#实现字符串中最长的回文子序列的示例代码：

public static int LongestPalindromeSubseq(string s)
{
    int n = s.Length;
    int[,] dp = new int[n, n];

    for (int i = n - 1; i >= 0; i--)
    {
        dp[i,i] = 1;
        for (int j = i + 1; j < n; j++)
        {
            if (s[i] == s[j])
            {
                dp[i,j] = dp[i + 1,j - 1] + 2;
            }
            else
            {
                dp[i,j] = Math.Max(dp[i + 1,j], dp[i,j - 1]);
            }
        }
    }
    return dp[0,n - 1];
}