leetcode|细枝末节

本文最后更新于:3 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++;
}

leetcode|细枝末节
https://www.aimtao.net/note-of-leetcode/
Posted on
2020-07-07
Licensed under