leetcode|小细节

本文最后更新于:2 个月前

本文记录平时做 leetcode 题过程中,一些值得注意的细节之处。我将按照 基础语句数据结构算法 这三个方面进行整理。

一、基础语句

1.少用sqrt或者pow。

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

// 判断条件为: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]);
}
// 判断条件为:j <= sqrt(i)
for (int j = 1; j <= sqrt(i); j++) {
		min_num[i] = min(min_num[i - num[j]] + 1, min_num[i]);
}

2.整型转化为字符串

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

#include <iostream>
#include <string>
#include <stringstream>
int x = 100;
string s; 
stringstream ss;
ss << x;
ss >> s;

3.while判断

以下二者等同

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

while 适用于 i(循环条件)在循环体中发生改变,比如:

int i = 0;
while (a[i] != 0) {
  if (a[i] == 1) {
    i++;
  }
}

4.涉及最小值问题少用 0x3f3f3f3f

最好用 INT_MAX,以防真的出现边界值(例如 2147483647)

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

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

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

后果:

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

6.不知名的错误,考虑下标写错

for (int i = 0; i < x; i++) {
		a[x][0] = 0;  // 下标写错。
}

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

7.快慢指针交换,条件是 q < p

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

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

while (q < p) {
		swap(s[q], s[p]);
  	q--;
    p++;
}

二、数据结构

1.哈希表的键为字母时,用数组更高效

#13. 罗马数字转整数

利用字符的 ascii 码。

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

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

3.有stack程序报错,考虑空栈取top()

#20. 有效的括号

#84. 柱状图中最大的矩形(学习笔记 |算法)

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

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

4.vector匿名对象

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

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

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

#226. 翻转二叉树

// 如果为空,则执行。
if (!root->left) {
  return nullptr;
}

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

#226. 翻转二叉树

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

if (!root) {
  
}

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

三、算法

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

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

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

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

2.选取连续一段问题(不确定个数)考虑左右边界

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

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

(1)以 #84. 柱状图中最大的矩形 为例,考虑左右边界进行暴力(非最优):

// 枚举所有组合的可能。

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

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

// 以选中的高度为中心,左右遍历,找出比当前高度高的左右边界。

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

3.哨兵 Sentinel

#84. 柱状图中最大的矩形(学习笔记 |算法)

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

优势:

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

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

应用:

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

4.单调栈、单调队列存索引方便

#84. 柱状图中最大的矩形(学习笔记 |算法)

#239. 滑动窗口最大值(学习笔记 |算法)

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

5.深搜防止成环,死循环互找

733. 图像渲染

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

// 因为 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] 成环,无法退出循环,陷入了互找的死循环。


 目录

致敬李文亮及各路英雄好汉!