只列举我实际面试中遇到过的算法题

用栈实现队列

LeetCode 232

用队列实现栈

LeetCode 225

洗牌算法

Fisher-Yates 洗牌算法，时间复杂度是 (O(n))，且能确保每个元素都被均匀随机分布。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
using System;

public class Shuffler
{
    private static Random random = new Random();

    public static void Shuffle<T>(T[] array)
    {
        for (int i = array.Length - 1; i > 0; i--)
        {
            int j = random.Next(0, i + 1);  // 生成一个 0 到 i 之间的随机数
            // 交换 array[i] 和 array[j]
            T temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
}

二分查找

LeetCode 704

加一

LeetCode 66

斐波那契数列

LeetCode 509

数组中的第 K 个最大元素

LeetCode 215

最大子数组和

LeetCode 53

最长递增子序列

LeetCode 300

删除链表倒数第 n 个节点

LeetCode 19

相交链表

LeetCode 160

数字序列分组

需要把数组里的数（每个数的取值都是 1-9）分成多个小组，分小组的规则是：3 个相同的数或者 3 个连续的数，当所有的数都可以被分组，则为完全分组。

设计一个算法，判断数组是否能完全分组。

例如[1, 1, 2, 2, 2, 3, 3, 3, 4]，可分为 123 123 234（完全分组），

注意：若先把 222 333 分为一组，则会导致出现 bug，判断为不可完全分组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
using System;
using System.Collections.Generic;
using System.Linq;

public class GroupChecker
{
    public static bool CanGroup(List<int> nums)
    {
        int n = nums.Count;
        int i = 0, j = 1, k = 2;
        bool sign = true;

        // 若数组长度不是3的倍数，则无法分组
        if (n % 3 != 0)
            return false;

        nums.Sort();
        List<int> newNums = new List<int>(nums);

        // 查找相同的3个数，并标记为已分组（使用-1表示已分组）
        while (i < n - 2)
        {
            if (nums[i] == nums[i + 1] && nums[i + 1] == nums[i + 2])
            {
                newNums[i] = newNums[i + 1] = newNums[i + 2] = -1;
                i += 3;
            }
            else
            {
                i++;
            }
        }

        i = 0;
        // 查找连续3个数，并标记为已分组（使用-1表示已分组）
        while (k < n)
        {
            while (i < j && newNums[i] == -1)
                i++;
            while (j < k && newNums[j] == -1)
                j++;
            while (k < n && newNums[k] == -1)
                k++;

            if (k < n && newNums[i] + 1 == newNums[j] && newNums[j] + 1 == newNums[k])
            {
                newNums[i] = newNums[j] = newNums[k] = -1;
            }
            else if (k < n && newNums[i] + 2 != newNums[k])
            {
                k++;
            }
            else if (j < k && newNums[i] + 1 != newNums[j])
            {
                j++;
            }
        }

        foreach (var num in newNums)
        {
            if (num != -1)
                sign = false;
        }

        if (!sign)
        {
            i = 0;
            j = 1;
            k = 2;
            newNums = new List<int>(nums);

            // 查找连续3个数，并标记为已分组（使用-1表示已分组）
            while (k < n)
            {
                while (i < j && newNums[i] == -1)
                    i++;
                while (j < k && newNums[j] == -1)
                    j++;
                while (k < n && newNums[k] == -1)
                    k++;

                if (k < n && newNums[i] + 1 == newNums[j] && newNums[j] + 1 == newNums[k])
                {
                    newNums[i] = newNums[j] = newNums[k] = -1;
                }
                else
                {
                    if (k < n && newNums[i] + 2 != newNums[k])
                        k++;
                    if (j < k && newNums[i] + 1 != newNums[j])
                        j++;
                }
            }

            i = 0;
            // 查找相同3个数，并标记为已分组（使用-1表示已分组）
            while (i < n - 2)
            {
                while (i < n - 2 && (newNums[i] == -1 || newNums[i + 1] == -1 || newNums[i + 2] == -1))
                    i++;
                if (i < n - 2 && newNums[i] == newNums[i + 1] && newNums[i + 1] == newNums[i + 2])
                {
                    newNums[i] = newNums[i + 1] = newNums[i + 2] = -1;
                    i += 3;
                }
                else
                {
                    i++;
                }
            }

            for (int m = 0; m < n; m++)
            {
                if (newNums[m] != -1)
                    return false;
            }
        }

        return true;
    }
}

class Program
{
    static void Main()
    {
        List<int> nums = new List<int> { 1, 1, 2, 2, 2, 3, 3, 3, 4 };
        Console.WriteLine(GroupChecker.CanGroup(nums)); // 输出 True
    }
}