codetop
2024-11-29 10:25:56 #算法

依照CodeTop后端算法题考查频度（并非全部）。

3.无重复字符的最长子串

滑动窗口：维护一个unordered_map类型的window变量以统计当前窗口中各字符出现的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 个人喜欢的滑动窗口框架
int l = 0, r = 0;
while (r < s.size()) {
    // 右窗口滑动
    char c = s[r++];
    window[c]++;

    // 判断左窗口是否要收缩
    while (window[c] > 1) { // 题目条件：此题是窗口内不含重复字符
        char d = s[l++];
        window[d]--;
    }

    // 更新结果
}

25.K个一组翻转链表

[1,2,3,4,5](k=2) → [2,1,4,3,5]

模拟翻转： 利用reverseK翻转两个head和tail之间的k个节点，并返回重置后的头尾，然后先统计链表节点的总数，k个一组翻转即可。

1
2
3
4
5
6
7
8
9
10
11
12
// 翻转head至tail之间的节点，并返回重置后的头尾
pair<ListNode*, ListNode*> reverseK(ListNode* head, ListNode* tail) {
    ListNode* pre = tail->next;
    ListNode* cur = head;
    while (pre != tail) {
        ListNode* next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return {tail, head};
}

215.数组中的第k个最大元素

快速选择： 快速排序的核心是“哨兵划分”和“递归”。

快速选择的思路是：数组长度为N，如果某次哨兵划分后，基准数的索引正好是N - k，则它就是第k大的数字。然而，对于包含大量重复元素的数组，每轮的哨兵划分都可能将数组划分为1和n - 1两个部分，此时快排的时间复杂度会退化至O(N^2)。

  • 三路划分：每轮划分数组为三个部分，当发现第k大数字处在“等于基准数”的子数组中时，便可直接返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int quickSelect(vector<int>& nums, int k) {
    // 随机选择基准数
    int pivot = nums[rand() % nums.size()];
    // 将大于、小于、等于pivot的元素划分至big、small、equal中
    vector<int> big, equal, small;
    for (auto& num : nums) {
        if (num > pivot)
            big.emplace_back(num);
        else if (num < pivot)
            small.emplace_back(num);
        else
            equal.emplace_back(num);
    }
    // 第k大的元素在big中
    if (k <= big.size())
        return quickSelect(big, k);
        // 第k大的元素在small中
    if (k - big.size() > equal.size()) // 注意这里是和equal.size()对比，等于pivot的元素可能不止一个！
        return quickSelect(small, k - big.size() - equal.size());
        
    return pivot;
}

103.二叉树的锯齿形层序遍历

奇数层翻转： 利用result.size() % 2 == 1来判断该层是否为奇数层，若是奇数层，则用reverse翻转。

1
2
3
4
// 核心
if (res.size() % 2 == 1)
    reverse(tmp.begin(), tmp.end());
res.emplace_back(tmp);

5.最长回文子串

中心扩展法： 子串不断向两边扩展，如果两边的字母相同就继续扩展。

1
2
3
4
5
6
7
8
9
// 核心 -> 中心扩展！
// 寻找以left 和 right为中心的最长回文子串
string isPalding(string s, int left, int right) {
    while (left >= 0 && right < s.size() && s[left] == s[right]) {
        left--;
        right++;
    }
    return s.substr(left + 1, right - left - 1);
}

236.二叉树的最近公共祖先

1
2
3
4
5
6
7
8
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == p || root == q || root == nullptr) return root;
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
    if (left != nullptr && right != nullptr) return root;
    if (left == nullptr) return right;
    return left;
}

143.重排链表

若用vector会带来O(N)的空间复杂度。
寻找链表中点 + 链表逆序 + 合并链表：快慢指针先找到链表中点mid，然后反转链表后半部分，最后合并即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void reorderList(ListNode* head) {
    if (head == nullptr)
        return;
    
    // middleNode自定义函数：寻找链表中点
    ListNode* mid = middleNode(head);
    ListNode* l1 = head;
    ListNode* l2 = mid->next;
    mid->next = nullptr;
    // reverseList自定义函数：反转链表
    l2 = reverseList(l2);
    // mergeList自定义函数：合并链表
    mergeList(l1, l2);
}

42.接雨水

双指针优化： 先用两个容器统计柱子左右两边最高的柱子，依次计算能接的雨水量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int trap(vector<int>& height) {
    int sum = 0;
    // 第1个和最后1个柱子无法接雨水
    vector<int> maxLeft(height.size(), 0);
    vector<int> maxRight(height.size(), 0);

    maxLeft[0] = height[0];
    maxRight[height.size() - 1] = height[height.size() - 1];

    for (int i = 1; i < height.size(); ++i)
        maxLeft[i] = max(maxLeft[i - 1], height[i]);
    for (int i = height.size() - 2; i >= 0; --i)
        maxRight[i] = max(maxRight[i + 1], height[i]);

    for (int i = 1; i < height.size() - 1; ++i) {
        int temp = min(maxLeft[i], maxRight[i]) - height[i];
        if (temp > 0)
        {
            sum += temp;
        }
    }

    return sum;
}

54.螺旋矩阵

模拟遍历：

  1. 若matrix为空，则直接返回空列表
  2. 初始化左、右、上、下四个边界l r t b
  3. 按照题目要求的顺序循环遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<int> result;
// 初始化4个边界
int l = 0, r = matrix[0].size() - 1;
int t = 0, b = matrix.size() - 1;

// 核心：模拟遍历
while (true) {
    for (int i = l; i <= r; ++i)
        result.emplace_back(matrix[t][i]);
    if (++t > b) break;
    for (int i = t; i <= b; ++i)
        result.emplace_back(matrix[i][r]);
    if (--r < l) break;
    for (int i = r; i >= l; --i)
        result.emplace_back(matrix[b][i]);
    if (--b < t) break;
    for (int i = b; i >= t; --i)
        result.emplace_back(matrix[i][l]);
    if (++l > r) break;
}

82.删除排序链表中的重复元素II

核心： 利用辅助前序节点原地删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* cur = dummy;

while (cur->next && cur->next->next) {
    int val = cur->next->val; // 当前位置下一节点的元素
    if (cur->next->next->val == val) {
        // 有重复 -> 将重复的所有元素删除
        while (cur->next && cur->next->val == val)
            cur->next = cur->next->next;
    } else {
        // 无重复 -> 辅助前序节点后移
        cur = cur->next;
    }
}

124.二叉树的最大路径和

核心：利用一个简化的函数maxGain(node)计算二叉树中某一个节点的最大贡献值（以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大）。

ex: [20, 15, 7]中，15和7的最大贡献值分别为15和7，而20的最大贡献值为35。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxGain(TreeNode* node) {
    if (node == nullptr)
        return 0;
        
    int leftGain = max(maxGain(node->left), 0);
    int rightGain = max(maxGain(node->right), 0);

    // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
    int priceNewpath = node->val + leftGain + rightGain;

    maxSum = max(maxSum, priceNewpath);

    return node->val + max(leftGain, rightGain);
}

31.下一个排列

思路： 将一个左边的[较小数]与右边的[较大数]交换，以能够让排列变大，从而得到下一个排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void nextPermutation(vector<int>& nums) {
    int i = nums.size() - 2;

    while (i >= 0 && nums[i] >= nums[i + 1])
        i--;
        
    if (i >= 0) {
        int j = nums.size() - 1;
        while (j >= 0 && nums[i] >= nums[j])
            j--;
            
        // 交换左边的[较小数]与右边的[较大数]
        swap(nums[i], nums[j]);
    }

    reverse(nums.begin() + i + 1, nums.end());
}
上一页
2024-11-29 10:25:56 #算法
下一页