Leetcode Trick题目总结

发表于 | 更新于
本文字数： 1.5k | 阅读时长 ≈ 1 分钟
LC41 缺失的第一个正整数

下标置换
让n出现在nums[n-1]的位置上，0和负数忽略，注意while循环的判断一定要思考循环是否能有效终止，第二种情况如果交换的两个数相同，则while循环会变为死循环

1
2
3
4
5
6
while (nums[i] > 0 && mums[i] <= n && nums[i] != nums[nums[i] - 1]) {
  swap(nums[i], nums[nums[i] - 1]);
}
// or
 while (nums[i] >= 0 && nums[i] < n && nums[i] != i && nums[i] != nums[nums[i]])
  swap(nums[i], nums[nums[i]]);

或者如果不想考虑下标和正整数元素的差1，可以先将所有元素值减1，负数不处理，但此时要注意INT_MIN不能减。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int firstMissingPositive(vector<int>& nums) {
     int n = nums.size();
     if (!n) return 1;
     for (auto &x : nums) {
         if (x != INT_MIN) x--;
     }
     for (int i = 0; i < n; i++) {
         while (nums[i] >= 0 && nums[i] < n && nums[i] != i && nums[i] != nums[nums[i]]) {
             int tmp = nums[nums[i]];
             nums[nums[i]] = nums[i];
             nums[i] = tmp;
         }
     }
     for (int i = 0; i < n; i++) {
         if (nums[i] != i) return i + 1;
     }
     return n + 1;
 }
LC23 合并k个有序链表
  1. 分治法
  2. 暴力k个指向k个链表头的指针找最小值O(KN) -> 维护k个元素的最小堆 O(nlgk)
    最小堆自定义比较函数
    1
    2
    3
    4
    5
    6
    struct Cmp {
      bool operator() (ListNode* a, ListNode* b) {
        return a->val > b->val;
      }
    }
    注意判读p->next不为空再加入优先队列
  • L2 链表两数相加

记得处理最后进位>0

  • L7 整数反转
  • L9 回文数

注意INT溢出情况的处理

  • 字符串的最大公因子

长度满足最大公约数，暴力检查a和b串或者判断a+b == b+a

  • 多数元素

分治

随机化

  • 最长上升子序列优化

最长上升子序列的个数

  • 最长上升连续子序列
  • 最长连续序列

排序

暴力枚举+哈希

并查集

  • 划分和相等的k个子集
  • 分发糖果

左-右&右-左两次贪心

  • 矩阵中的增长路径

动态规划和拓扑排序的关系

  • 不同的子序列