leetcode｜细枝末节

本文最后更新于：4 years ago

本文记录平时做 leetcode 题过程中，一些值得注意的细节之处。我将按照 基础语句 、数据结构、算法 这三个方面进行整理。写得很个性，可能只有我自己看的懂 :)

1.基础语句

1.1 少用 sqrt 或者 pow。

尤其是在循环判断中，少用 sqrt 或者 pow，用加减乘除代替

1
2
3
4
// 判断条件为：j*j <= i
for (int j = 1; i- j*j >= 0; j++) {
    min_num[i] = min(min_num[i - num[j]] + 1, min_num[i]);
}
1
2
3
4
// 判断条件为：j <= sqrt(i)
for (int j = 1; j <= sqrt(i); j++) {
    min_num[i] = min(min_num[i - num[j]] + 1, min_num[i]);
}

1.2 整型转化为字符串

用 stringstream，需要头文件 #include <stringstream>

1
2
3
4
5
6
7
8
#include <iostream>
#include <string>
#include <stringstream>
int x = 100;
string s; 
stringstream ss;
ss << x;
ss >> s;

1.3 while 判断

以下二者等同

1
2
while(n--)
for (int i = 0; i < n; i++)   // 从 0 开始
1
2
while(--n)
for (int i = 1; i < n; i++)   // 从 1 开始

while 适用于 i（循环条件）在循环体中发生改变，比如：

1
2
3
4
5
6
int i = 0;
while (a[i] != 0) {
    if (a[i] == 1) {
        i++;
    }
}

1.4 涉及最小值问题少用 0x3f3f3f3f

最好用 INT_MAX，以防真的出现边界值（例如 2147483647）

1.5 循环过程中不改变容器大小

#1558. 得到目标数组的最少函数调用次数

在 for(i -> n) 中，不可以删除元素。

后果：

  • 改变 q.size() 的值，但是未改变 n 的值，循环会发生数组越界的情况（段错误）。
  • 删除头部元素，所有的元素下标被均 -1，i++ 无遍历意义，会跳过一些元素。
1
2
3
4
5
6
7
8
9
// deque<int> q;
for (int i = 0; i < n; i++) {
    if (q[i] % 2 != 0) {
        q[i]--;
    }
    if (!q[i]) {
        q.pop_front();         // 严重错误！
    }
}

1.6 不知名的错误，考虑下标写错

1
2
3
4
5
6
7
for (int i = 0; i < x; i++) {
    a[x][0] = 0;  // 下标写错。
}

for (int i = 0; i < x; x++) {  // 遍历条件写错。
    a[i][0] = 0;  
}

1.7 快慢指针交换，条件是 q < p

#557.反转字符串中的单词 III 的 C 语言解法。

不应该是 q != p，偶数个元素时不会等于同一个点，例如当 q = 5， p = 6，

1
2
3
4
5
while (q < p) {
    swap(s[q], s[p]);
    q--;
    p++;
}

1.8 双指针交换完，记得更新双指针位置

否则进入死循环，超时。

1
2
3
4
5
while (q < p) {
    swap(s[q], s[p]);
    q--;          // 记得更新
    p++;          // 记得更新
}

2.数据结构

2.1 哈希表的键为字母时，用数组更高效

#13. 罗马数字转整数

利用字符的 ascii 码。

1
2
3
unordered_map<char, int> m;
m['I'] = 1;
m['V'] = 5;
1
2
3
int m[100] = {0};
m['I'] = 1;
m['V'] = 5;

2.2 空栈访问栈顶元素 top() 会报错

2.3 有stack程序报错，考虑空栈取 top()

#20. 有效的括号

#84. 柱状图中最大的矩形（学习笔记 ｜算法）

使用 stack.top() 访问栈顶元素时，应该先判断是否为空。

1
2
3
if (s[i] == ')' && !tmp.empty() && tmp.top() == '(') {
    tmp.pop();
}

2.4 vector 匿名对象

vector<int>{1, 2, 3} 构造匿名对象，leetcode 可以完美运行，但是 vs code 运行报错。

1
2
vector< vector<int> > m;
m.push_back(vector<int>{1, 2, 3});

2.5 二叉树判断节点是否为空的方法

#226. 翻转二叉树

1
2
3
4
// 如果为空，则执行。
if (!root->left) {
    return nullptr;
}

2.6 二叉树使用节点前先判断是否为空

#226. 翻转二叉树

二叉树，在使用 root 的子节点前，一定先判断 root 是否为空。

1
2
3
4
5
6
7
8
if (!root) {
  
}

// 使用 root 的子节点前，先判断 root 是否为空节点。
if (!root->left) {
  
}

3.算法

3.1 动态规划设置大空间以防越界

动态规划总是要先初始化 memo[0]、memo[1] 等等元素，但传入 n 为 0 时，就会越界，可设置空间为 n + 3。

即使传进来的是，n = 0，也不用担心 memo[0]、memo[1]、memo[2] 等越界。

1
2
3
4
vector<int> memo(n+3, 0);
memo[0] = 1;
memo[1] = 1;
memo[2] = 1;

3.2 选取连续一段问题（不确定个数）考虑左右边界

#84. 柱状图中最大的矩形

比如字符串的子序列，连续线段中的一段，而且未规定这一段的个数，可以考虑左右边界。

（1）以 #84. 柱状图中最大的矩形 为例，考虑左右边界进行暴力（非最优）：

1
2
3
4
5
6
// 枚举所有组合的可能。

for i -> 0, n-2
    for j -> i+1, n-1
        (i, j) -> 最小高度, 计算面积;
        updata max_area;

（2） #84. 柱状图中最大的矩形 还有第二种暴力方式，思路奇妙，值得一提。

1
2
3
4
5
6
7
8
// 以选中的高度为中心，左右遍历，找出比当前高度高的左右边界。

for i -> 0, n+2 {
    for j -> 0, i-1 { 找出比 当前高度 高的做左边界 left }
    for j -> i+1, n { 找出比 当前高度 高的做右边界 right }
    left, right  -> 计算面积;
    updata max_area;
}

3.3 哨兵 Sentinel

#84. 柱状图中最大的矩形（学习笔记 ｜算法）

哨兵是一个哑对象。哨兵不存放数据（可能为 0），但其结构体与其他有用的元素一致。主要用来简化边界条件的处理。

优势：

  • 防止索引越界，比如空栈取 top()。

  • 减少对边界条件的特殊处理。

应用：

  • 单链表的头节点
  • 插入排序
  • 栈底元素（防止空栈取 top()）

3.4 单调栈、单调队列存索引方便

#84. 柱状图中最大的矩形（学习笔记 ｜算法）

#239. 滑动窗口最大值（学习笔记 ｜算法）

单调栈、单调队列 存索引 比 存元素 更加方便。

3.5 深搜防止成环，死循环互找

733. 图像渲染

对于上下左右深搜，进入递归循环体之后，如果不符合退出条件，数据一定要发生变化（以便下次进入符合退出条件），否则会成环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 因为 source_color、aim_color 相等，进入循环体后，image[x][y] 没有发生变化。
void Dfs(vector<vector<int> >& image, int x, int y) {
    // 退出条件
    if (x < 0 || y < 0 || x >= n || y >= m || image[x][y] != source_color) {
      return;
    }
    image[x][y] = aim_color;
    // 深搜路径，上下左右
    Dfs(image, x + 1, y);
    Dfs(image, x - 1, y);
    Dfs(image, x, y + 1);
    Dfs(image, x, y - 1);
    return;
}

对于 image：

0，0，0

0，1，1

image[1][1]，image[1][2] 成环，无法退出循环，陷入了互找的死循环。

3.6 背包问题无法更新 res 值

1
2
3
4
5
6
int res = best_value(w, v, index - 1, c);
if (w[index] <= c) {
    // 不小心 res 被定义成了 **局部变量**
    int res = max(res, best_value(w, v, index - 1, c - w[index]) + v[index] );
}
return res;

上面代码问题在于：

if 中 res 是重新定义的一个局部变量，离开 if 大括号，值失效。

3.7 判断二进制数的 1 的个数

  1. __builtin_popcount()
  2. 连续 & 运算。
1
2
3
4
5
6
int tmp = 5;  // 十进制 5 = 二进制 101
int num = 0;  // 1 的个数
while (tmp) {
  tmp &= tmp - 1;
  num++;
}
Mark
#C/C++ #LeetCode
leetcode｜细枝末节
https://www.aimtao.net/note-of-leetcode/
Posted on
2020-07-07
Licensed under