Leetcode Notes

Posted on 2024-12-30 Edited on 2025-01-01 In Notes

算法实用小知识

对于一个数组中出现次数最多的一个数，设数组长度为n，假如这个数出现次数大于$\frac{n}{2}$，那么，num[n/2]一定就是这个数，这个性质也是众数的性质。

LeetCode做题笔记

滑动窗口的思想：即可以使用一个队列，模拟一个滑动的窗口，不停地在一个字符串或者数组中滑动。滑动窗口最后的位置，可以不是最优的一个序列或者是其他的东西，滑动窗口最后的位置并没有多大关系，滑动窗口可以只起到一个遍历的作用，并不需要最后缩小到一个最优的序列。

在使用滑动窗口找最大或最小的时候，只需要记录目前最大或最小即可，滑动窗口最后并不需要指向最大或最小的那个序列
在使用滑动窗口找最好的那个序列的时候，如果最后需要输出这个序列，那么滑动窗口最后是要指向那个最好的序列的
题型：无重复字符串的最小子串，最小覆盖子串，最多包含k个字符的最长子串，反正是跟区间有关的题目

可以参考题713，209, 1297，也是滑动窗口的题目。基本思路就是遍历右端点right，right会和左端点left配合形成一个窗口区间，对这个区间执行某些判断条件，使用while循环移动left左端点。保证区间的某些特性。在这种情况下，left一般情况下都永远不会比right大，还可以少写一些判断条件

题单：713，209, 1297，1151
右端点右移，导致窗口扩大，是不满足条件的罪魁祸首；
左端点右移目的是为了缩小窗口，重新满足条件

维护一个有条件的滑动窗口；

// question 209
int ans = nums.size() + 1;
int left = 0;
int sum = 0;
for(int right = 0; right < nums.size(); ++right){
  sum += nums[right];
  while(sum >= target){
      ans = min(ans, right - left + 1);
      sum -= nums[left];
      left++;
  }
}

return ans == nums.size() + 1?0:ans;

双指针：即一个fast指针和一个slow指针，fast指针主要用处是进行遍历，找到符合条件的元素或者其他。slow指针可以指向可以进行修改的地方，或者是指向要进行操作的位置。
- 题型：删除一个数组中的重复元素，移除数组元素, 盛水最多的容器

回溯，动态规划好题：22.括号生成, 17.电话号码组成

stack = [("", 0)]
while stack:
    current, current_index = stack.pop()

    if(len(current) == length):
        ans.append(current)
        continue

    index = digits[current_index]
    letter_list = num_list[int(index)]
    for i in range(len(letter_list)):
        stack.append((current + letter_list[i], current_index + 1))

ans = []
stack = [("", 0, 0)]  # 初始化栈，存储初始状态：当前字符串，左括号计数，右括号计数
while stack:
    current, left, right = stack.pop()
    
    if len(current) == n * 2:
        ans.append(current)
        continue

    if left < n:
        stack.append((current + "(", left + 1, right))
    
    if right < left:
        stack.append((current + ")", left, right + 1))

ans = []
def bracket_search(answer, left, right):
    if(len(answer) == n * 2):
        ans.append("".join(answer))
        return
    if(left < n):
        answer.append("(")
        bracket_search(answer, left + 1, right)
        answer.pop()
    if(right < left):
        answer.append(")")
        bracket_search(answer, left, right + 1)
        answer.pop()

bracket_search([], 0, 0)

排列问题，组合问题的去重。注意传入的数组一定是已经排序过后的

排序算法：Python：sorted(nums), CPP: sort(nums.begin(), nums.end())

# 核心代码
for i in range(len(nums)):
  if i > 0 and nums[i] == nums[i - 1]:
      continue
  # 其他版本
  if i > 0 and nums[i] == nums[i - 1] and used[i - 1] == 0 # 全排列II问题, Q47

# 有Startindex版本
for i in range(startindex, len(nums)): # 组合总和II，Q40
  if i > 0 and nums[i] == nums[i - 1]:
      continue

# 因为nums数组是已经排序的，比如在0位置的1已经使用过了
# 第二次循环开始，startindex=0，当遍历到第二个1的时候，就会触发下面的if语句
# 从而跳过第二个1，第三个或者第四个同理，这样子就避免了重复的组合
# 主要原因还是因为nums数组是已经进行排序过后的
# i > startindex 或 i > 0的原因是保证遍历到的是重复的
# 而nums[i]==nums[i-1]保证可以遍历到重复的元素
# 这两个进行结合，保证不会重读进行遍历

图论：
- 一般使用DFS或者BFS进行搜索
- 对于在一个无向图中搜索一条最短路径，可以使用BFS算法进行搜索，因为当BFS搜索到终点的时候，一定是一条最短路径

LeetCode问题

45.跳跃游戏，没搞懂为什么要遍历整个数组，思考后个人觉得应该只要遍历有限的点的个数应该就可以，已解决（2024.6.5）https://leetcode.cn/problems/jump-game-ii/

jump_num = 0 # 跳跃次数
max_pos = 0 # 最大到达范围
next_pos = 0 # 跳跃到的下一个位置
index = 0 # 起跳位置

if len(nums) == 1: # 如果数组长度为1，不需要跳跃，返回跳跃次数0
    return 0

while(index < len(nums) - 1): # 当起跳位置不是最终的位置的时候，进行循环
    if index + nums[index] >= len(nums) - 1: # 若当前起跳的位置，可到达的范围大于终点，直接返回跳跃次数 + 1，这一步是为了防止下面的for循环中i的越界
        return jump_num + 1
    max_pos = 0 # 每次循环进行刷新
    # 对于当前起跳位置，贪心的寻找跳跃位置的最大覆盖范围，即最理想的可以调到最远的下一个点。在当前起跳位置，可以跳到的点范围是index + 1, index + 1 + nums[index]，对这些进行遍历，同时计算nums[i] + i，即最大的到达范围，不断更新，并记录下标next_pos, 注意if语句是>=的
    for i  in range(index + 1, index + nums[index] + 1):
        if nums[i] + i >= max_pos:
            next_pos = i
            max_pos = nums[i] + i

    jump_num += 1 # 进行完上面的步骤后，将跳跃次数 + 1
    index = next_pos # 更新下一次的跳跃位置
    print("jump_num", jump_num)
    print("jump_start", index)
    print("max_pos_end", max_pos)
  
return jump_num

判断出栈序列合法性
1. 将需要入栈时的1至n个数依次进入栈中。
2. 当模拟栈中的栈顶数字不等于题目所给的数字序列的开头时，继续进行下一个数字的进入。
3. 当模拟栈中的栈顶数字等于题目所给的数字序列的开头时，栈和数字序列的首数字同时出栈，之后，再进行下一个首数字的比较，反复2、3过程。
4. 当n个数字均已进行了入栈操作后，判断栈中的元素是否为空，若为空，说明数字序列合法，若不为空，说明数字序列不合法。
代码随想录-贪心算法-14到19题，都是区间的相关的题，都是比较巧妙地贪心算法，可以多看看
- 大致做法为先对区间的第一个元素或者第二个元素进行排序，当完成排序后，遍历一遍，可以做一些相关的操作
- 具体的操作有：合并区间，找最大区间范围，删除重叠区间
卡特兰数
$$ h(0)=1, h(1) = 1, h(2)=2$$
$$ h(n) = h(0)*h(n-1)+h(1)*h(n-2)+…+h(n-1)*h(0), n > 2$$
便于进行计算的定义如下
$$ C_0 = 1, C_{n+1}=\frac{2(2n+1)}{n+2}C_n$$
$$C_n=\frac{1}{n+1}\binom{2n}{n},\ 渐近表达为\frac{4^n}{\sqrt{t}}$$

01背包问题及完全背包问题模板代码(一维二维数组)
假设有3件物品，物品1价值15，重量1，物品2价值20，重量3，物品3价值30，重量4。背包最大重量为4
物品为两个数组，weight:{1, 3, 4}, value{15, 20, 30}

def package01(): # 01背包问题
  # 二维数组
  m = 3 # 物品数量为3
  n = 4 # 背包最大重量为4
  dp = [[0] * (n + 1) for _ in range(m + 1)] # 4 * 5的一个二维数组
  for j in range(n, weight[0] - 1, -1):
    dp[0][j] = value[0]
  
  for i in range(1, m + 1): # 从物品2开始，因为物品1在初始化里面已经处理过
    for j in range(n + 1): # 正常的从0开始
      dp[i][j] = dp[i - 1][j]
      if j >= weight[i]:
        dp[i][j] = dp[i - 1][j - weight[i]] + value[i]
  
  # 一维数组
  dp = [0] * (n + 1)

  for i in range(m):
    for j in range(n, weight[i] - 1, -1): # 从后序开始遍历, 因为如果从前序开始遍历，可能会访问到已经被修改过的数据，而不是上一个物品的数据了
      dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

def packagecomplete(): # 完全背包问题
  # 参数相同，同有weight，value数组，只不过每个物品的数量是无限的
  dp = [0] * (n + 1)
  for i in range(m):
    for j in range(weight[i], n + 1): # 从前序开始遍历，从当前物品的重量遍历到背包最大重量，在遍历顺序上与01背包问题不同
      dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
  # 对于完全背包问题，for循环的顺序是可以颠倒的

def multipackage(): # 多重背包问题
  # 多重背包问题，代表背包中的每个物品的数量可能不是1，但是也不是无限
  # 可以将多重背包问题转换为01背包问题，即将重复的物品放入weight和value数组即可

  # 假设有weight, value, num(物品数量）三个数据
  for i in range(N): # 遍历物品数量
    for j in range(M, weight[i] - 1, -1): # 遍历背包，倒序遍历，避免覆盖
      for k in range(1, num[i] + 1) # 遍历物品个数，从1遍历到物品最大个数
        dp[j] = max(dp[j], dp[j - (k * weight[i])] + (k * value[i]))
        # 当k为1的时候，就是正常的01背包，当k继续递增，就是多重背包问题
  return dp[M]

注意，可以使用完全背包的方法来求排列数或者是组合数

当求组合数（顺序无关）的时候外层for遍历物品，内层for遍历背包容量
当求排列数（顺序有关）的时候外层for遍历背包容量，内层for遍历物品
当顺序无关的时候，先遍历背包容量或物品，都是可以的，可以进行颠倒

注意，子数组和子序列不相同。子数组必须是连续的，子序列可以不是连续的。参考leetcode718题和1143题

位运算

可以用二进制来表示一个集合，比如二进制从低到高第 i 位为 1，表示 i 在集合中，为 0，表示 i 不在集合中。以下例子使用集合{0, 2, 3} = 1101和 {0, 1, 2} = 0111
- https://leetcode.cn/circle/discuss/CaOJ45/ 灵神的笔记
- 直接打开进行复习比较方便

异或运算，可以针对一些特殊问题，如leetcode136题，使用异或就可以运算

// 异或运算
int a = 1, b = 5;
int c = a ^ b; // ^ 就是异或运算
int d = (a ^ b) & 1; // 如果d为1，那么a和b的奇偶性不同，为0奇偶性相同
// 奇偶数二进制的表达主要在于最后一位，最后一位为1则为奇数，最后一位为0则为偶数
// 若一个奇数和一个偶数异或，最后一位变为1，再与1进行和运算&，就得到1，表示奇偶性不同

计算一个数二进制形式下的 1 的个数

// n & (n - 1) 的效果是每次使得n的二进制形式中最低位的1变成0
// 直到n的二进制形式的所有1都变成0，n变为0就结束循环，count就会统计变了几次，即有多少个1
static int count(int n){
  int count = 0;
  while(n){
      n = n & (n - 1);
      count++;
  }
  return count;
}
// n为正整数，且n的二进制表示中只有一个1的话，那么n一定是2的幂（2^i）
N > 0 && n & (n - 1) == 0 // n就是2的幂
n > 0 && (n & -n) == n; // n就是2的幂
int lb = n & -n; // 取出n的二进制表达式最后一个1，比如是1100的话，就会取出100，即值为4
n = n ^ lb; // 这步操作就会把最后一个1的位置变为0（异或），比如1100 ^ 100 = 1000

单调栈类型问题(monotonic stack)
- 当通常是一维数组，需要找到上一个更大（小）的元素，或者找到下一个更大（小）的元素，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。
- 如果求右边更大的数，从栈顶到栈底是递增序列，同时从后往前遍历
- 如果求右边更小的数，从栈顶到栈底是递减序列，同时从前往后遍历
- 经典题目：42接雨水，84柱状图中最大的矩形，739每日温度
- 可以看成是一座山，更高的山会遮住矮的山，那些矮的山就没有必要继续看了，就可以出栈丢掉
- 单调栈可以理解为一个遮挡的问题，比如一座山，可以从前往后遍历，找到第一个比它大的数。也可以从后往前遍历，找到第一个比它小的数。因为高的山会遮挡矮的山，矮的山被遮挡了就相当于没用的数据了。
- 所以单调栈的细节就是及时把没用的数据出栈并进行对应处理
单调队列(monotonic queue)
- 例题：239滑动窗口最大值
- 思路和单调栈类似，都是及时去除无用的元素，然后压入新的元素。及时把无用数据出队并作相应处理
- 可以看成是一座山，遮挡类型的问题
- 数据结构可以使用双端队列（std::list）涉及操作详见cpp_note
同余定理
- 对于两个数a和b，如果(a - b) mod k = 0, 则有 a mod k 等于 b mod k
前缀和（prefix sum）
- 可以参考leetcode930,560，1524,974，数组前缀和的经典例题
- 前缀和+哈希表的使用方法比较经典
并查集
- 参考leetcode684,685冗余连接系列问题

二分查找的进阶应用（非常难！常看常新）

参考leetcode34：在排序数组中寻找元素的第一个和最后一个位置
熟练使用ranges::lower_bound, ranges::upper_bound()
二分查找：lc2856
找最小：lc1011货运最小重量

找最大

// 二分查找相关函数ranges::lower_bound(), ranges::upper_bound();
#include<ranges>
vector<int> nums;
int target;
ranges::lower_bound(nums, target); // 返回指向第一个不小于（大于等于）target的元素的迭代器
ranges::upper_bound(nums, target); // 返回指向第一个大于target的元素的迭代器

// 若是对于一个整数数组，则有以下转换, upper_bound可以通过lower_bound来实现
// upper_bound(nums, target) = lower_bound(nums, target + 1)

// 左闭右闭区间，这个函数相当于lower_bound
int binary_search(vector<int>& nums, int target){ 
  int left = 0;
  int right = nums.size() - 1;
  while(left <= right){ // 闭区间[left, right]
      int mid = left + (right - left)/2;
      if(nums[mid] < target){ // 注意，这里如果是小于的情况，就写left变化
          left = mid + 1;
      }
      else{ // nums[mid] >= target
          right = mid - 1; // right的情况就是>=target
      }
  }
  return left; // 最后返回left
  // return right + 1; 也是正确的
  // 最后查找的结果，left = right + 1
  // right的结果是left的前一个结果，如果查找到target，那么left指示的就是target的位置，right是第一个比target小的位置
  // 如果为查找到target，那么left指示的是第一个比target大的数的位置，而right是第一个比target小的位置
}

// 上面的代码是找到数组中第一个大于等于target的元素位置，下面的代码是找到数组中第一个小于等于target的元素位置（同样可以通过转化，变成找到数组中第一个小于target元素的位置）
int binary_search(vector<int>& nums, int target){
  int left = 0, right = nums.size() - 1;
  int result = 0;
  while(left <= right){
    int mid = left + (right - left) / 2;
    if(nums[mid] <= target){
      result = mid;
      left = mid + 1;
    }
    else{
      right = mid - 1;
    }
  }

  return result;
}
// 同时，只要通过binary_search(nums, target - 1) 就能找到数组中第一个小于target元素的位置

差分数组difference array
- 思路比较巧妙，类似前缀和
- 经典题目可以参考leetcode1094拼车
- 题解可以参考https://leetcode.cn/problems/car-pooling/?source=vscode

字典树（Trie树，单词查找树）

树形结构，每一个节点存储一个next数组，长度为26，代表26个字母
可以用来存储大量的字符串
利用字符串的公共前缀来减少查找时间
可以顺序的插入字符串，利用字符串前缀存储，也可以逆序插入字符串，利用字符串的后缀进行存储

例题：lc208,820

class Trie {
  private:
    bool IsEnd; // 代表这个节点是不是一个字符串的结尾。若是，从此节点到根节点构成一个字符串
    vector<Trie*> next; // 每一个节点存储的next数组
  public:
    Trie(): next(26), IsEnd(false) {}

    void insert(string word){ // 向字典树中插入一个单词word
      Trie* node = this;
      for(char c : word){ // 按照单词正顺序插入的，也可以逆顺序插入
          if(node->next[c - 'a'] == NULL){
              node->next[c - 'a'] = new Trie();
          }
          node = node->next[c - 'a'];
      }
      node->IsEnd = true; // 代表是一个结尾
    }
    bool search(string word) { // 查找树中有没有word这个完整的单词
      Trie* node = this;
      for(char c : word){
          node = node->next[c - 'a'];
          if(node == nullptr){
              return false;
          }
      }
      return node->isEnd; // 如果遍历word完，此时node不是结尾的话，返回就是false了，否则会返回true
    }
    bool startsWith(string prefix) { // 查找一个单词是不是某个单词的前缀
      Trie* node = this;
      for(char c : prefix){
          node = node->next[c - 'a'];
          if(node == nullptr){
              return false;
          }
      }
      return true;
    }
};

哈希表小技巧
- 对于一些字符串，如果这些字符串里面的所有元素就是26个字母，那么可以只创建一个长度为26的字符串，用来当做哈希数组，节省空间
优先队列
1
2
priority_queue<int> pq; // 最大堆
priority_queue<int, vector<int>, std::greater<>> pq; // 最小堆
- 如果要找第k小的元素，则可以使用一个最大堆，保证堆中的元素数量是k个，那么堆中第一个数(pq.top())就正好是第k小的元素。同时及时把多余的大数弹出
- 找第k大的元素元素同理，用最小堆。如第2个最大的，pq = 3, 5, 则pq.top()正好就是第二个最大的元素
图判断是否有环
- 无向图：
  - 并查集：对每条边进行find操作，如果发现两个节点已经在一个集合中，那就说明有环
  - DFS：记录每个访问的节点，如果发现访问到了已经访问过的节点，说明有环
- 有向图：
  - 拓扑排序：如果排序后的顺序数组长度不等于节点个数，则有环
  - DFS + 递归栈
并查集偏移分组（适用于二分图）
- 对于一个边(u, v)，使用join(u + n, v) 和 join(u, v + n)，可以把u和v分别添加到不同的两个组
- 在循环的同时检查isSame(u, v)，如果为true则不能构成二分图
- 偏移分组就是添加一个足够大的偏移量，保证把所有的u和v分到两个不同的组里面
波兰表达式
- 前缀表达式，比如a+b就表示为+ab
- 从右到左解析，遇到操作数就入栈，遇到操作符就弹出两个操作数计算，结果入栈
逆波兰表达式
- 后缀表达式，a+b就表示为ab+
- 从左到右解析：解析时从左到右扫描表达式，遇到操作数就入栈，遇到操作符就弹出两个操作数进行计算，结果再入栈