YifanChen's Blog

一个专注技术的新手程序员

0%

链接

28. 实现 strStr()
459.重复的子字符串
字符串:总结篇
双指针总结篇

知识

KMP算法理论

KMP与解决的问题

KMP:发明本算法的三位学者的英文名首字母

应用:字符串匹配问题

经典例子:

  • 给出文本串: aabaabaaf

  • 给出模式串: aabaaf
    求在文本串中是否出现过模式串

暴力方法与KMP

暴力解法:两重for循环,先遍历文本串,再遍历模式串,挨个匹配。从文本串的首位开始,若模式串不匹配文本串,则将模式串后移一位,直到匹配上。时间复杂度O(m * n),m和n分别是文本串和模式串的长度。

KMP算法:跳到之前已匹配的地方,继续匹配。

前缀表的由来

KMP算法如何知道我们之前已匹配过哪些,且跳到已匹配的内容后面继续匹配?

前缀表有什么特性,可以让我们找到之前已匹配过的内容?

在f处不匹配,找到f前面子串的后缀是aa,找到与该后缀相等的前缀的后面开始匹配。故我们要求一个字符串中的最长相等前后缀,重新匹配时跳到最长前缀之后开始匹配。

前缀与后缀

前缀:包含首字母,不包含尾字母的所有子串。

后缀:包含尾字母,不包含首字母的所有子串。

最长相等前后缀

最长相等的前缀和后缀的长度。以模式串aabaaf为例。

子串 前缀 后缀 最长相等的前缀和后缀的长度
a 0
aa a a 1
aab a, aa b, ab 0
aaba a, aa, aab a, ba, aba 1
aabaa a, aa, aab, aaba a, aa, baa, abaa 2
aabaaf a, aa, aab, aaba, aabaa f, af, aaf, baaf, abaaf 0

得到模式串的前缀表:010120。

使用前缀表的匹配过程

模式串 aabaaf
前缀表 010120
发现f不匹配,要找f前的最长相等前后缀,由前缀表得到最长相等前后缀为2。2意味着有一个后缀aa,前面也有一个与之相等的前缀aa。在后缀aa的后面不匹配了,就要从与后缀相等的前缀的后面继续开始匹配。最长相等前后缀为2,故从s[2] = 'b'处开始重新匹配。

next数组

next/prefix都可以用来表示前缀表。在遇到不匹配的地方,next数组告诉我们要回退到哪里。前缀表为010120,对其的处理包括:右移/统一减一。不处理前缀表,就将其作为next数组,依然可以完成KMP算法。

总结

KMP算法->能解决哪些问题->为什么KMP算法匹配失败后可以跳到某个位置->前缀表->前缀表的特性及如何求取前缀表->用前缀表完成一次匹配的操作->实现KMP算法时,有时对前缀表统一减一,有时右移,这不设计KMP算法原理性的东西,只是实现上方法不同而已。

KMP算法的代码实现

next数组不同的实现方式

模式串:aabaaf

文本串:aabaabaaf

前缀表:010120,用next数组表示。

如何求next数组?

  • 有人会把前缀表右移,第一位放上-1,得到-101012,作为next数组。
  • 有人会把前缀表整体-1,得到-10-101-1,作为next数组。
  • 有人会直接拿前缀表做Next数组。
    上述实现方式都可以,但具体处理逻辑会略有差别。

模式串与文本串在模式串的最后一位f处发生了冲突,看f的前一位的前缀表的值是多少,发现是2,于是跳转到下标为2的位置,即b。如果next数组是前缀表右移得到,就直接比较f对应的next数组的值,发现是2,于是也跳转到b的位置。若next数组是前缀表-1得到,那么就把f的前一位的next数组的值+1,依然跳转到b的位置。

next数组的核心:遇到冲突向前回退。本节我们就拿前缀表作为next数组

求Next数组的具体代码

共4步:

  1. 初始化
  2. 处理前后缀不相同的情况
  3. 处理前后缀相同的情况
  4. 更新next数组的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 传入的参数:next数组,我们需要对其进行赋值,模式串s
void getNext(vector<int> next, string s)
{
// 初始化
// 指针i:指向后缀末尾位置
// 指针j:指向前缀末尾位置,还代表着i之前(包括i)的子串的最长相等前后缀的长度
int j = 0; // 前缀从0开始
int next[N];
next[0] = 0; // next数组初始位置为0

// 比较前后缀所对应的字符是否相等,故i从1开始,这样i和j才能进行比较
for (int i = 1; i < s.size(); i ++ )
{
// 处理前后缀末尾不相同的情况
// 因为在一次循环中,i相当于是固定不动的,所以此时j回退
// j回退到next[j - 1]指向的位置,即遇见冲突,就看next数组(即前缀表)的前一位
// 不止回退一步,而要连续回退,不能写if,而要写while
while ( j > 0 && s[i] != s[j]) j = next[j - 1]; // 因为要求j - 1 >= 0,因此要求j > 0

// 处理前后缀相同的情况
// j代表着i之前(包括i)的子串的最长相等前后缀的长度
if (s[i] == s[j]) j ++ ;

// 更新next数组,在其中存储i之前(包括i)的子串的最长相等前后缀的长度
next[i] = j;
}
}

模拟运行过程

当j指向s[1],i指向s[2]时,前后缀不匹配,此时next[j - 1] = next[0] = 0,j回退到s[0],再次比较前后缀是否匹配,发现仍不相同,此时j无法继续回退,我们就更新next数组的值,next[2] = 0,这就代表i = 2之前包括i的子串的最长相等前后缀为0,这与表格中的结果相同。此时i后移一位,指向s[3],有s[3] == s[0],j ++,j = 1,next[3] = 1,说明aaba的最长相等前后缀长度是1,这与表格中的结果相同。进入下一轮循环,i = 4,同理。最终用getNext函数完成了对next数组的求值。

总结

用上述函数,求得了next数组,即前缀表。

28. 实现 strStr()

求next数组的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 传入的参数:next数组,我们需要对其进行赋值,模式串s
void getNext(vector<int> next, string s)
{
int j = 0; // 前缀从0开始
int next[N];
next[0] = 0; // next数组初始位置为0

// 比较前后缀所对应的字符是否相等,故i从1开始,这样i和j才能进行比较
for (int i = 1; i < s.size(); i ++ )
{
while ( j > 0 && s[i] != s[j]) j = next[j - 1]; // 因为要求j - 1 >= 0,因此要求j > 0

if (s[i] == s[j]) j ++ ;

// 更新next数组,在其中存储i之前(包括i)的子串的最长相等前后缀的长度
next[i] = j;
}
}

用next数组做匹配的代码(文本串s,模式串t):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int j = 0; // 因为next数组里记录的起始位置为0
for (int i = 0; i < s.size(); i++) { // i从0开始,遍历文本串
while(j > 0 && s[i] != t[j]) { // 不匹配, j - 1 >= 0 => j > 0
j = next[j - 1]; // j 寻找之前匹配的位置
}
if (s[i] == t[j]) { // 匹配,j和i同时向后移动
j++; // i的增加在for循环里
}
// j指向了模式串t的末尾,那么就说明模式串t完全匹配文本串s里的某个子串了
if (j == t.size()) { // 文本串s里出现了模式串t
// 返回当前在文本串匹配模式串的位置i-模式串的长度 + 1,就是文本串字符串中出现模式串的第一个位置(位置从0开始)
return (i - t.size() + 1);
}
}

完整代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
void getNext(int* next, const string& s) {
int j = 0;
next[0] = 0;
for(int i = 1; i < s.size(); i++) {
while (j > 0 && s[i] != s[j]) {
j = next[j - 1];
}
if (s[i] == s[j]) {
j++;
}
next[i] = j;
}
}
int strStr(string haystack, string needle) {
// 特殊情况,模式串长度为0,则返回0,本处是一个易错点
if (needle.size() == 0) {
return 0;
}
// 定义next数组
int next[needle.size()];
// 填充next数组
getNext(next, needle);
// 用next数组做匹配
// j指向模式串,i指向文本串
int j = 0;
for (int i = 0; i < haystack.size(); i++) {
while(j > 0 && haystack[i] != needle[j]) {
j = next[j - 1];
}
if (haystack[i] == needle[j]) {
j++;
}
if (j == needle.size() ) {
return (i - needle.size() + 1);
}
}
// 模式串匹配不上文本串,则返回-1
return -1;
}
};

n为文本串长度,m为模式串长度

  • 时间复杂度: 生成next数组,时间复杂度是O(m);根据前缀表不断调整匹配的位置,可以看出匹配的过程是O(n)。所以总共的时间复杂度为O(n + m)
  • 空间复杂度: 开辟空间用于存储next数组,即模式串的前缀表,因此是O(m)

459.重复的子字符串

暴力解法

枚举所有的子串,看能否构成字符串。

1
2
for 子串结束位置
for 子串与主串比较

时间复杂度O(n^2)。目标子串的开始位置必然是主串最前面的元素,因此只需要枚举子串的结束位置即可。

移动匹配

设一个可由重复的子串构成的字符串为s,那么两个s拼接起来,前一个s的后半部分和后一个s的前半部分又可以构成一个新的字符串s。s由重复子串构成的判据:两个s相加起来,若其中出现了s,那么s就是由重复子串构成的。

注意:在(s + s)中去搜索s时,一定要把(s + s)的首元素和尾元素删去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
bool repeatedSubstringPattern(string s) {
string ss = s + s;
ss.erase(ss.begin());
ss.erase(ss.end() - 1);

// string::npos 是 std::string 类型的一个静态成员常量,表示字符串中不存在匹配的位置。在 find() 函数中,如果没有找到匹配的子串,则返回 string::npos。这个值通常是一个很大的无符号整数,表示找不到匹配的位置。
if (ss.find(s) != string::npos)
return true;
else
return false;
}
};

find函数的实现其实就是28. 实现strStr()。若用KMP实现find函数,那么时间复杂度是O(m + n),find函数的其他实现方法时间复杂度大抵也是O(m + n)。

KMP解法

KMP算法的应用场景:模式串是否在文本串中出现过,即上面的find函数的一种实现方式。

前缀:不包含尾字母,一定包含首字母的所有子串。
后缀:包含尾字母,不包含首字母的所有子串。

结论:若s由重复子串组成,那么它的最小重复单位就是它的最长相等前后缀不包含的那个子串。后缀不包含和前缀不包含的部分是相同的,都是最小重复子串。

举例:abababab,最长相等前缀是ababab,最长相等后缀是ababab,剩余的部分ab即为最小重复子串。
图三

推导:设原字符串是s,标出其下标;设最长相等前缀是t,最长相等后缀是f,也分别标出下标。利用最长相等前缀和最长相等后缀的下标之间的对应关系和最长相等前后缀和原字符串下标之间的对应关系推导即可。

实现:设s存在最小重复单位,len为s的长度,则next[len - 1]为s的最长相等前后缀的长度,最小重复单位的长度为:len - next[len - 1],若该长度能被原字符串的长度整除:len % (len - next[len - 1]) == 0,那么return true。有如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
// 求next数组
void getNext (int* next, const string& s){
// 初始化
next[0] = 0;
int j = 0;
for(int i = 1;i < s.size(); i++){
// 处理前后缀不相同的情况
while(j > 0 && s[i] != s[j]) {
j = next[j - 1];
}
// 处理前后缀相同的情况
if(s[i] == s[j]) {
j++;
}
// 更新next数组
next[i] = j;
}
}
bool repeatedSubstringPattern (string s) {
if (s.size() == 0) {
return false;
}
int next[s.size()];
getNext(next, s);
int len = s.size();
// 核心代码
if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
return true;
}
return false;
}
};

初次尝试

28. 实现 strStr()

直接听卡尔讲,尝试去理解,不要求独立写出代码。

459.重复的子字符串

直接听卡尔讲,尝试去理解,不要求独立写出代码。

实现

28. 实现 strStr()

因为KMP算法很难,大家别奢求一次就把kmp全理解了,大家刚学KMP一定会有各种各样的疑问,先留着,别期望立刻啃明白,第一遍了解大概思路,二刷的时候,再看KMP会懂很多。或者说大家可以放弃一刷可以不看KMP,今天来回顾一下之前的算法题目就可以。

因为大家算法能力还没到,细扣很难的算法,会把自己绕进去,就算别人给解释,只会激发出更多的问题和疑惑。所以大家先了解大体过程,知道这么回事, 等自己有算法基础和思维了,在看多看几遍视频,慢慢就理解了。

459.重复的子字符串

本题算是KMP算法的一个应用,不过对KMP了解不够熟练的话,理解本题就难很多。

建议是 KMP和本题,一刷的时候 ,可以适当放过,了解怎么回事就行,二刷的时候再来硬啃

心得与备忘录

28. 实现 strStr()

  1. 我觉得KMP算法很想一种特殊的双指针算法。一个指针i用于遍历文本串,另一个指针j用于根据next数组的指引在模式串中移动。这种双指针算法可以把时间复杂度从暴力算法的O(n * m)优化为O(n + m)。
  2. 代码分为独立的两部分,第一部分是求next数组(即前缀表),第二部分是同时在两个字符串中移动指针并使用next数组。
  3. 当模式串为空时,应当返回0。因为空字符串被认为是任何字符串的子串,所以文本串中最开始与模式串匹配的字符的索引就是0。如果文本串中不存在与之匹配的模式串,则返回 -1。

459.重复的子字符串

  1. 本题有两种解法:移动匹配和KMP解法。如果忘记了KMP算法的next数组怎么写,可以使用移动匹配方法(最难写的KMP部分可以用find函数来代劳)。
  2. 注意string中find函数的用法:在 find() 函数中,如果没有找到匹配的子串,则返回 string::npos。
  3. 本题的KMP解法的关键在于结论:若s由重复子串组成,那么它的最小重复单位就是它的最长相等前后缀不包含的那个子串。

总结

字符串总结

常见题型和常用方法:

  1. 花式反转字符串(整体&局部反转,有时还要搭配双指针算法删除空格)
  2. 后续处理字符串
  3. KMP算法(匹配模式串和文本串)
  4. 移动匹配(核心也是KMP算法,只不过核心由库函数find实现)

小知识:

  1. substr,split,reverse, erase这四个库函数的时间复杂度都是O(n),在循环中使用会使得程序的时间复杂度达到O(n^2)。此时需要双指针算法等进行优化。
  2. 字符串本质为字符数组,数据结构基本等用于普通数组,因此普通数组中常用的双指针算法也常用于字符串中。

双指针总结

双指针应用于:

  1. 数组:移除元素
  2. 字符串:反转字符串、替换数字、翻转字符串里的单词
  3. 链表:反转链表、环形链表II
  4. 哈希表章节:三数之和、四数之和,两数之和若要求返回两数的值而非索引,也可以用双指针做,代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    vector<int> twoSum(vector<int> nums, int target)
    {
    vector<int> res; // 存储结果
    sort(nums.begin(), nums.end()); // 先排序

    int left = 0, right = nums.size() - 1;

    while (left < right)
    {
    if (nums[left] + nums[right] > target) right -- ;
    else if (nums[left] + nums[right] < target) left ++ ;
    else
    {
    res.push_back({nums[left], nums[right]}); // 收获答案
    // 去重
    while (left < right && nums[left] == nums[left + 1]) left ++ ;
    while (left < right && nums[right] == nums[right - 1]) right -- ;
    // 寻找新的答案
    left ++ ;
    right -- ;
    }
    }
    return res;
    }

    上述代码本质上就是三数之和、四数之和的一部分(for循环中的while循环)。相比于两数之和的哈希写法,新增了值去重的功能。

    双指针的题目中,以三数、四数之和以及反转链表最容易写错,一定要多复习。三数、四数之和的易错点在于剪枝、去重和求四数之和时的int类型变量的溢出。反转链表的易错点在于搞错了tmp, cur->next, prev和cur更新的先后顺序。

链接

344.反转字符串
541. 反转字符串II
卡码网:54.替换数字
151.翻转字符串里的单词
卡码网:55.右旋转字符串

知识

541. 反转字符串II

一般来说,编程语言自己实现的库函数都是左闭右开的,因此reverse(s, i, i + k)表示的是反转字符串s的第i位到第i + k位,不包含第i + k位。

卡码网:54.替换数字

  1. 注意,cpp中比较大小不能写作48 <= s[i] <= 57,而是要写作s[i] >= 48 && s[i] <= 57。表达式48 <= s[i] <= 57实际上会先计算48 <= s[i],这个表达式的结果是一个布尔值truefalse,在C++中,这个布尔值会被隐式转换为整数,true转换为1false转换为0。然后,该整数(01)会与57进行比较,所以条件几乎总是为真(除非s[i]是字符'0')。
  2. 扩容字符串的函数为resize函数。
  3. cpp中是可以不遍历字符串中的每个字符,就直接cout输出整个字符串的。
  4. 字符串和数组的区别(摘自代码随想录):
    字符串是若干字符组成的有限序列,也可以理解为是一个字符数组,但是很多语言对字符串做了特殊的规定,接下来我来说一说C/C++中的字符串。
    在C语言中,把一个字符串存入一个数组时,也把结束符 ‘\0’存入数组,并以此作为该字符串是否结束的标志。
    在C++中,提供一个string类,string类会提供 size接口,可以用来判断string类字符串是否结束,就不用’\0’来判断是否结束
    那么vector< char > 和 string 又有什么区别呢?
    其实在基本操作上没有区别,但是string提供更多的字符串处理的相关接口,例如string 重载了+,而vector却没有。所以想处理字符串,我们还是会定义一个string类型。
  5. 若要求某个字符在0-9之间,既可以写s[i] >= 48 && s[i] <= 57(’0’的ascii码是48,’1’的ascii码是57),也可以写s[i] >= '0' && s[i] <= '9'

151.翻转字符串里的单词

  1. erase函数的时间复杂度是O(n)
  2. 本题可以用split函数来从字符串中分割出单词,但那样就失去了意义
  3. 若给一个函数传入的参数加上引用&,那么在函数中对这个参数进行了修改,调用该函数后该参数也会被修改。

卡码网:55.右旋转字符串

  1. 注意:若在ACM模式中调用reverse函数,必须#include <algorithm>,否则会报错。但若调用swap函数,不需要引用任何头文件,直接使用即可。

初次尝试

344.反转字符串

先尝试用reverse函数秒杀,顺便复习reverse函数的用法:

1
2
3
4
5
6
class Solution {
public:
void reverseString(vector<char>& s) {
reverse(s.begin(), s.end());
}
};

reverse函数相当于把字符串反转以后,将新的字符串存入了旧的字符串中。

我曾经做过反转链表的题,猜测用双指针可以解决这道题。写下了以下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
void reverseString(vector<char>& s) {
for (int l = 0, r = s.size() - 1; l < r; l ++ , r -- )
{
// swap(s[l], s[r]);
int tmp = s[l];
s[l] = s[r];
s[r] = tmp;
}
}
};

直接用swap函数或者手写swap函数都是可以的。l < r或者l <= r都可以。因为字符串中字符的个数为奇数时,中间那个字符交换不交换都一样;字符个数为偶数时,交换最后两个成对的字符即可。

541. 反转字符串II

拿到这道题,我的第一想法是分类讨论。设字符串的长度是len。若len < k,则全部反转;若k <= len < 2k,则反转前k个字母;若len >= 2k,则按照题意反转。本题在反转的逻辑上没有困难,但问题在于如何分割出需要反转的子字符串。我没想出来什么好办法,写的逻辑太复杂又容易出错。

卡码网:54.替换数字

我先输入字符串s,然后定义每个元素由char类型变量组成的vector。遍历字符串s,若其中的某个字符的ascii码在48-57之间,说明该字符是数字0-9,那么向vector中依次插入number这6个字符。其他情况下,向vector中插入原始字符即可。据此思路写下以下的代码,可以通过评测。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# include <iostream>
# include <vector>

using namespace std;

int main()
{
string s;
cin >> s;

vector<char> out;

for (int i = 0; i < s.size(); i ++ )
{
if (s[i] >= 48 && s[i] <= 57)
{
out.push_back('n');
out.push_back('u');
out.push_back('m');
out.push_back('b');
out.push_back('e');
out.push_back('r');
}
else
out.push_back(s[i]);
}

for (int i = 0; i < out.size(); i ++ )
cout << out[i];
cout << endl;
return 0;
}

151.翻转字符串里的单词

这道题yxc应该讲过,要么通过流的方式读入为一个个单词,样例代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <string>
#include <sstream> // 引入 stringstream

using namespace std;

int main()
{
string line;
getline(cin, line); // 使用 getline 读取一整行

stringstream ss(line); // 使用 stringstream 来分割字符串
string word;
while (ss >> word) { // 从 stringstream 中读取单词,直到结束
cout << word << endl; // 输出单个单词
}

return 0;
}

要么通过双指针算法找出一个个单词并存储之。然后再将一个个单词逆序拼接为字符串并输出。我先尝试后一种方法。但没有做出来。

卡码网:55.右旋转字符串

本题我下意识地使用substr来写,得到如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <string>

using namespace std;

int main()
{
int k;
string s;
cin >> k >> s;

string s1 = s.substr(s.size() - k, s.size()); // 后面k个字符
string s2 = s.substr(0, s.size() - k); // 字符串在后面k个字符前的字符
cout << s1 + s2 << endl;
}

向substr中传入的区间是左闭右开的。

若不借助库函数,我还有一个想法。先拿一个字符串保存输入字符串的后面k个字符。然后在输入字符串的基础上,从尾部倒着插入前面的那些字符,最后再将另一个字符串保存的原字符串的后面k个字符插到新字符串的前面去。其实倒着插入和顺着插入也没什么区别。

我还想到一种做法。受到151. 翻转字符串里的单词启发,首先反转整个字符串,然后反转字符串的前k位,最后反转字符串的后(n - k)位。由此写出了两个版本的代码,第一版是直接调用reverse函数,第二版是手动实现reverse函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main()
{
int k;
string s;
cin >> k >> s;

reverse(s.begin(), s.end());
reverse(s.begin(), s.begin() + k);
reverse(s.begin() + k, s.end());
cout << s << endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <string>

using namespace std;

// 手动实现reverse函数
void reverseString(string &s, int i, int j)
{
for (int a = i, b = j; a < b; a ++ , b -- )
{
int tmp = s[a];
s[a] = s[b];
s[b] = tmp;
}
}

int main()
{
int k;
string s;
cin >> k >> s;

reverseString(s, 0, s.size() - 1);
reverseString(s, 0, k - 1);
reverseString(s, k, s.size() - 1);
cout << s << endl;
}

实现

344.反转字符串

在算法的思路上,字符串和数组非常类似。本题应用双指针法即可:首尾交换,再次一级交换,以此类推。因此首尾各有一个指针,两指针交换,然后两指针同时向中间移动。若库函数直接把题目解决了,就不要用库函数。若库函数是题目的一部分,且我们知道库函数的大体实现逻辑和时间复杂度,那就可以用。代码如下所示:

1
2
3
4
5
6
7
class Solution {
public:
void reverseString(vector<char>& s) {
for (int i = 0, j = s.size() - 1; i < s.size() / 2; i ++ , j -- )
swap(s[i], s[j]);
}
};

swap函数有两种方法,一种是常见的交换数值,另一种是位运算,可参见代码随想录。

541. 反转字符串II

模拟题,模拟复杂的规则下,如何反转字符串。题意:每2k段的前k个字符进行反转,尾部如果剩下的字符超过长度超过k,则反转k个字符,剩下的不动。尾部如果剩下的字符长度小于k,则全部反转。本题的代码可以很简洁。

本题每次取2k段,因此按照2k来遍历:for (int i = 0; i < s.size(); i += 2k)。然后在for循环中操作前k个字符即可。边界条件想不明白可以带一个具体的例子来试。代码和注释如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
string reverseStr(string s, int k) {
// 每隔2k个字符跳转一次,即每次取出2k个字符
for (int i = 0; i < s.size(); i += 2 * k)
{
// 对2k个字符的前k个字符进行反转
// 由于每次取2k,取若干次后。字符串的尾部剩下的字符长度l可能l < k 或 k <= l < 2k
// 对前一种情况,需要将尾部全部反转,对后一种情况,需要反转尾部剩下字符的前k个字符
// 先处理后一种情况,注意加上条件i + k <= s.size(),这可以避免对索引超出范围的元素进行反转
// 至于i + k是否能取到s.size(),可以举例子:k = 3, s = {a, b, c},由此可见可以取等于
// 也可以从理论上分析,由于reverse的区间是左闭右开的,因此s.begin() + i + k实际上取不到,因此可以让i + k = s.size()
// 处理完后continue即可,除去反转2k个字符中的前k个字符的一般情况,尾部剩下的字符的长度的第一种情况和第二种情况只可能有一种发生
if (i + k <= s.size())
{
reverse(s.begin() + i, s.begin() + i + k); // 左闭右开
continue;
}
// 再处理前一种情况,当剩余的字符长度l < k时,反转剩余的全部字符
reverse(s.begin() + i, s.end());
}
return s;
}
};

也可以不用continue,直接采用if-else写法,参见代码随想录的写法(代码随线录的注释也更加简洁明了):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
string reverseStr(string s, int k) {
for (int i = 0; i < s.size(); i += (2 * k)) {
// 1. 每隔 2k 个字符的前 k 个字符进行反转
// 2. 剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符
if (i + k <= s.size()) {
reverse(s.begin() + i, s.begin() + i + k );
} else {
// 3. 剩余字符少于 k 个,则将剩余字符全部反转
reverse(s.begin() + i, s.end());
}
}
return s;
}
};

卡码网:54.替换数字

本题的最佳解法不需要额外的辅助空间。首先扩充原字符串到每个数字字符替换成 “number” 之后的大小。然后用双指针算法,指针i指向旧字符串的末尾,指针j指向新字符串的末尾。用指针i遍历旧字符串,若遇到字母,则原样填入指针j指向的位置;若遇到数字,则从后往前将number填入到指针j指向的位置。直到i和j都指向新旧字符串的开头为止。这里的新旧字符串其实是扩容之后和扩容之前的同一字符串,只是为了方便区分称它们为新旧字符串。根据这个思路,我写出了如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# include <iostream>

using namespace std;

int main()
{
string s;
cin >> s;

// count为字符串中数字的数量
int count = 0;
for (int i = 0; i < s.size(); i ++ )
if (s[i] >= 48 && s[i] <= 57)
count ++ ;

int oldSize = s.size();
s.resize(oldSize + count * 5); // 字符串扩容

// 双指针算法,i指向旧字符串,j指向新字符串
for (int i = oldSize - 1, j = s.size() - 1; i >= 0; )
{
if (s[i] < 48 || s[i] > 57)
{
s[j] = s[i];
i -- ;
j -- ;
}
else
{
s[j] = 'r';
s[j - 1] = 'e';
s[j - 2] = 'b';
s[j - 3] = 'm';
s[j - 4] = 'u';
s[j - 5] = 'n';
i -- ;
j -= 6;
}
}

// 可以直接写作cout << s << endl;
for (int i = 0; i < s.size(); i ++ )
cout << s[i];
return 0;
}

代码随想录的代码本质上和我写的是一样的,但他写的更见简洁一些,我写的更易于理解一些。

我的写法中,必须让i >= 0,不能写成i > 0,否则答案错误。例子,输入1,输出本来应该为number,若for循环的条件为i > 0,则不会进入for循环,直接输出1,这显然是不对的。但对于代码随想录的写法:for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--),则j < i是正确的,若首字符为字母,则j = i时两指针均以指向首字符,首字符保留即可,不需要处理;若首字符为数字,则逻辑也可以正确执行。若j <= i,则反而会出现越界的问题,因为当j和i都指向首字符后,for循环的条件依然满足,此时完成当前循环后,i和j继续-1,再次判断时,i依然等于j,再次进入循环,此时s[i]和s[j]就不存在了(s[-1]不存在)。

151.翻转字符串里的单词

是字符串中操作比较复杂的题目,给的字符串中在开头、中间、结尾都可能有空格。反转字符串里的单词后,要将多余的空格都删掉。

整体思路:先让单词的顺序和目标相同,即将整个字符串都反转。再对每个单词做反转,就得到了目标字符串。将原字符串整体反转,再将每一个单词反转

难点:如何删去多余的空格。要求空间复杂度O(1),即不能申请新的字符串来放置删去多余空格后的字符串。且不能使用库函数。使用快慢双指针算法,删除多余空格的时间复杂度为O(n)。快指针用于遍历旧字符串,慢指针用于依次指向新字符串中的各个元素。(新字符串在旧字符串的基础上修改,并不需要另外创建字符串来存储新字符串)。双指针的用法同数组章节的移除元素。

根据上述思路,我写出了如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution
{
public:
void removeExtraSpace(string &s)
{
int slow = 0;
for (int fast = 0; fast < s.size(); fast ++ )
{
if (s[fast] != ' ') // 去除字符串开头的空格
{
// 每复制完一个单词后,加一个空格
// 这句话不可以放在while循环后,否则会在最后一个单词后面增加一个多余的空格
if (slow != 0) s[slow ++ ] = ' ';

// 将旧字符串的非空部分复制到新字符串中
while (fast < s.size() && s[fast] != ' ') s[slow ++ ] = s[fast ++ ];
}
}
s.resize(slow);
}

string reverseWords(string s)
{
removeExtraSpace(s); // 删去所有多余的空格

reverse(s.begin(), s.end()); // 反转整个字符串,注意reverse函数是左开右闭的

// 反转每个单词
int start = 0, i = 0;
while (i < s.size())
{
while (i < s.size() && s[i] != ' ') i ++ ; // 找到空格
reverse(s.begin() + start, s.begin() + i); // 反转start到空格之间的单词
start = i + 1; // 更新start
i = start; // 更新i
}
return s;
}
};

代码随想录中的反转每个单词的写法和我的略有不同,他用的是for循环,但本质是一样的。

卡码网:55.右旋转字符串

我在初次尝试中已经给出了空间复杂度为O(1)的最优解法,下面两幅图(对应两种等效的方法)可以帮助理解:

  1. 先反转整个字符串,再反转两个子串

    img

  2. 先反转子串,再反转整个字符串

    img

心得与备忘录

344.反转字符串

两种for循环的写法:for (int i = 0, j = s.size() - 1; i < s.size() / 2; i ++ , j -- )for (int l = 0, r = s.size() - 1; l < r; l ++ , r -- )都可以。

541. 反转字符串II

  1. for循环每次以2k为长度去跳转
  2. 本题反转字符的三种情况

    • 每隔 2k 个字符的前 k 个字符进行反转
    • 剩余字符小于 2k 但大于或等于 k 个,则反转前 k 个字符
    • 剩余字符少于 k 个,则将剩余字符全部反转

    三种情况每次只可能出现一种,即出现了一种情况,另外两种情况就不会出现了。据此,我写出了结构分明的三段式代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    class Solution {
    public:
    string reverseStr(string s, int k) {
    for (int i = 0; i < s.size(); i += 2 * k)
    {
    // 情况1
    if (i + 2 * k <= s.size())
    {
    reverse(s.begin() + i, s.begin() + i + k);
    continue; // 可以省略
    }
    // 情况2
    else if (i + k <= s.size())
    {
    reverse(s.begin() + i, s.begin() + i + k);
    continue; // 可以省略
    }
    // 情况3
    else
    reverse(s.begin() + i, s.end());
    }
    return s;
    }
    };

    情况1和情况2可以合并(即剩余字符的长度l满足l >= k时,都是反转剩下字符的前k个;只有当l满足l < k时,才要反转剩下的所有字符),因此产生了实现部分中的第二版代码。每次思考时应该先想到三种情况,再写出结构分明的三段式代码,然后对其进行简化。能够写出三段式代码即可,虽然不简洁但思路清晰简单、不容易出错

  3. 如果要求一段段地操作字符串或数组,那么for循环中的i变量是可以一段段增加的,而没必要每次+1

卡码网:54.替换数字

  1. 本题注意使用双指针做法。代码推荐参考我在实现中的写法,虽然和代码随想录的代码略有差别,但本质是完全一样的。
  2. 本题注意考虑边界条件,在我的写法中,是i >= 0而非i > 0;在代码随想录的写法中,是j < i而非j <= i。如果边界条件写得不对会导致发生指针异常或者部分样例无法通过。考虑边界条件时,可以举特例,也可以让代码先运行,若发生错误则修改相应的边界条件。
  3. 很多数组填充类的问题,其做法都是先预先给数组扩容带填充后的大小,然后在从后向前进行操作。对于线性数据结构,填充或者删除,后序处理会高效的多。

    这么做有两个好处:

    1. 不用申请新数组。算法的空间复杂度从O(N)降到了O(1)。
    2. 从后向前填充元素,避免了从前向后填充元素时,每次添加元素都要将添加元素之后的所有元素向后移动的问题。算法的时间复杂度从O(n^2)降到了O(n)。

151.翻转字符串里的单词

  1. 本题的总体思路:移除多余的空格->反转整个字符串->反转字符串中的每个单词
  2. 利用快慢双指针移除多余的空格有两种写法,一种较为复杂,需要分别移除字符串前面的空格和字符串中间和最后的连续的不止一个的空格,最后再移除字符串最后可能存在的一个空格。另一种较为简单,思路和27.移除元素是相同的快指针用于遍历旧字符串,慢指针用于依次指向新字符串中的各个元素。时间复杂度O(n)
  3. 推荐使用较为简单的双指针写法。除去从旧字符串中复制每个单词到新字符串中的代码,还需要加上用于在新字符串中添加每个单词尾部的空格的代码。注意这两行代码的顺序不能写反,必须是先有添加空格的代码,再有复制单词的代码,否则会导致在新字符串的末尾多添加一个空格
  4. 上面提到的新旧字符串只是有时间上的先后,没有空间上的拷贝。新字符串就是在旧字符串的基础上利用双指针算法通过删除和改动部分元素得到的。因此空间复杂度为O(1)。

卡码网:55.右旋转字符串

  1. 本题加上限制条件:不能申请额外空间,只能在本串上操作(对cpp)。
  2. 可以先反转总串,再反转子串;也可以先反转子串,再反转总串。
  3. 右旋转字符串和左旋转字符串方法完全相同,就是反转的区间不同。

链接

454.四数相加II
383. 赎金信
15. 三数之和
18. 四数之和
哈希表总结篇

知识

454.四数相加II

cpp中的map中的value是支持++操作的,且value可以通过key直接索引到,就像普通的数组那样。

383. 赎金信

  1. 不仅对vector可以用范围遍历,对string类型的变量和普通的数组也可以用范围遍历的写法来简化代码。似乎范围遍历的速度要稍快于普通的for循环遍历。

  2. cpp中,可以用erase函数来删除string类型变量的第j个字符,有两种写法:
    string.erase(j, 1);
    string.erase(s.begin() + j);

  3. cpp中,如果想使用变量类型来给变量命名,需要使用std,有如下例子:

    1
    2
    3
    4
    5
    6
    7
    8
    #include <set>

    int main() {
    std::set<int> set; // 使用 "set" 作为变量名
    set.insert(1);
    set.insert(2);
    return 0;
    }

    在这个例子中,set是作为std::set<int>类型的变量名使用的。由于std::set是在std命名空间中定义的,而变量set是在局部作用域中定义的,所以编译器能够区分这两者。

18. 四数之和

  1. 将四数之和由int类型转换为long类型:(long) nums[i] + nums[j] + nums[l] + nums[r] > target

初次尝试

454.四数相加II

这道题肯定是要用map做哈希的,且map的key用来存储元素的值,map的value用来存储元素的索引。此题和两数之和为target有较多的相同点,但也有些不同。若四个数相加为0,则其中的数两两互为相反数。但这种想法是不对的,可以存在2, 4, -3, -3的情况。对这题的算法我暂时想不出来什么好主意。

383. 赎金信

看着就是242.有效的字母异位词的变式,若前面那个字符串可以由后面那个字符串中的字母构成,则返回true,否则返回false。本质就是看后面的字符串是否包含前面的字符串。因为两个字符串都只是由小写字母构成,因此用数组做哈希足矣。根据这个思路,我写出了如下代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
// 本题的本质是判断后面的字符串是否包含前面的字符串,即后面的字符串中出现的所有字符是否在前面的字符串中出现过
int N[26] = {0};

for (int i = 0; i < ransomNote.size(); i ++ )
N[ransomNote[i] - 'a'] ++ ;

for (int i = 0; i < magazine.size(); i ++ )
N[magazine[i] - 'a'] -- ;

// 数组N中有元素大于0,说明ransomNote中出现了magazine中未出现的字母
// 说明前者不能完全由后者组成,返回false
for (int i = 0; i < 26; i ++ )
if (N[i] > 0)
return false;
return true;
}
};

采用范围遍历的方法,可以把上述代码写得更简洁:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
// ransomNote < magazine return true
// else return false
int N[26] = {0};

for (char r: ransomNote)
N[r - 'a'] ++ ;
for (char m: magazine)
N[m - 'a'] -- ;

for (int i: N)
if (i > 0)
return false;
return true;
}
};

15. 三数之和

这道题的题目我都不太理解,什么叫答案中不可以包含重复的三元组。直到我看到了示例1,明白了这个意思是可能存在情况:两个三元组,它们的索引组成的三元组可能不同,但这两个三元组本身的数值是完全相同的(忽略顺序),此时这两个三元组只能算作一个。这道题应该可以用哈希法,但需要去重。本题我认为有三个难点:

  • 枚举完一个数,怎么去寻找另外两个数
  • 用什么数据结构维护另外两个数
  • 如何去重

18. 四数之和

本题应该依然是双指针算法。但需要注意去重的操作。我的思路是先对数组进行排序,然后让a = i, b = i + 1, c = i + 2, d = nums.size() - 1。然后一边向后移动a, b和c,一边对a,b和c去重,一边向前移动d,一边对d去重。根据以上思路,我写下了以下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());

for (int i = 0; i < nums.size(); i ++ )
{
if (nums[i] > target) return res;
// 对i去重
if (i > 0 && nums[i] == nums[i - 1]) continue;

for (int j = i + 1; j < nums.size(); j ++ )
{
// 对j去重
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1, right = nums.size() - 1;
while (left < right)
{
if (nums[i] + nums[j] + nums[left] + nums[right] > target) right -- ;
else if (nums[i] + nums[j] + nums[left] + nums[right] < target) left ++ ;
else
{
res.push_back({nums[i], nums[j], nums[left], nums[right]});
// 对left和right进行去重
while (left < right && nums[left] == nums[left + 1]) left ++ ;
while (left < right && nums[right] == nums[right - 1]) right -- ;
left ++ ;
right -- ;
}
}
}
}
return res;
}
};

以上代码测试样例通过了229 / 294,可见思路是对的,但细节仍不完美。我将在实现部分进一步优化细节。

实现

454.四数相加II

四数相加和四数之和题目看起来相似,但前者是哈希表中的经典题目,后者用哈希表的方法不太合适。其实只需要知道有多少对四数之和为0,不需要知道每一对的具体数值。

本题不需要去重,因此相对简单,四数之和则需要考虑去重。举例:四个数组,每个数组中都有n个0,则返回的结果是n。

思路:遍历数组A和B,将从这两个数组取出的元素a + b放入map中;再遍历数组C和D,求得c + d,再判断map中有无我们想要的元素-(c + d),有则count += -(c+d)出现过的次数(即map中key为-(c+d)的元素的value)。

本题的数据范围很大,因此用数组来做哈希不可取,只能考虑set/map。因为不仅需要将a + b放入哈希结构中,还需要统计a + b出现过多少次,因此用map。用map的key存a + b的值,用map的value存a + b出现的次数。

时间复杂度:O(n^2) + O(n^2),还是O(n^2)。如果先遍历一个数组,再遍历三个数组,则时间复杂度是O(n^3)。

我知道上述思路后,尝试写代码,出现一个问题:不知道如何统计数组A和数组B中各取一个元素求和后的值出现的次数。我把简单的问题想复杂了,map中的value是支持++操作的,且value可以通过key索引到,因此直接:map[num1 + num2] ++ ;即可,这个代码的意思是:若num1 + num2的值出现过,则其value += 1;若没出现过,则相当于:map.insert({num1 + num2, 1})。写出了以下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
// 遍历nums1和nums2数组,将两个数组各取一个值的和作为key,和出现的次数作为value存入map中
unordered_map<int, int> sum;

for (int num1: nums1)
for (int num2: nums2)
sum[num1 + num2] ++ ; // 和为num1 + num2的值的出现次数 + 1

// 遍历nums3和nums4数组,设两个数组各取一个值的和是c + d
// 若map中出现了-(c + d),则count += value
int count = 0;
for (int num3: nums3)
{
for (int num4: nums4)
{
int s = num3 + num4;
auto it = sum.find(-s);
if (it != sum.end())
count += it->second; // it->second也可以写作sum[-s]
}
}
return count;
}
};

更简洁的写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> map;

for (int num1: nums1)
for (int num2: nums2)
map[num1 + num2] ++ ;

int count = 0;

for (int num3: nums3)
for (int num4: nums4)
{
int target = -(num3 + num4);
if (map.find(target) != map.end())
count += map[target];
}

return count;
}
};

383. 赎金信

注意,本题的题干中虽然强调了Each letter in magazine can only be used once in ransomNote,但这个条件在写代码时实际上并不需要考虑。这应该只是生成测试样例时需要遵守的规则。

本题用暴力做法也可以过,但暴力做法的代码写起来似乎还更麻烦一点。暴力做法就是两重for循环,若ransomNote中出现了magazine中出现过的字符,则从ransomNote中移除该字符,最后判断ransomNote的长度是否为0即可。暴力做法的代码可以参见代码随想录。

至于时间复杂度为O(n)的哈希解法,我在初次尝试中写的就已经很完美了。若想进一步优化,可以加上判断:若ransomNote的长度大于magazine的长度,则可以直接return false。若在遍历字符串时就对数组中元素的正负进行判断,那需要注意:只能在ransomNote中对数组中元素的正负进行判断,为负则说明赎金信中有magazine中没有的字符。若在magazine中对数组中元素的正负进行判断,可能存在问题:数组中的元素为正不一定代表赎金信中有magazine中没有的字符,可能仅仅是因为尚未遍历完成,数组中的元素还没被减到负数。因此,下面的代码是错误的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int N[26];

if (ransomNote.size() > magazine.size()) return false;

for (char r: ransomNote)
N[r - 'a'] ++ ;
for (char m: magazine)
{
N[m - 'a'] -- ;
if (N[m - 'a'] > 0) return false;
}

return true;
}
};

可以通过测试样例轻而易举地看出上述解法的漏洞,比如
ransomNote =”aa”
magazine =”aab”
Output false
Expected true
而代码随想录上的哈希解法的代码是正确的。

若想避免上述问题,最直接的办法就是等到N数组中的元素全部计算完成后,另开一个循环来判断其中是否有为正的元素。

15. 三数之和

本题可以用哈希法做,但比较复杂。本题需要返回的三元组,其中的元素是数组中元素的值,而非下标。注意:三元组是去重的。本题相较于两数之和的难点就在于去重

哈希法的大致思路:用两重for循环,第一重确定a,第二重确定b,然后看-(a + b)是否在map中出现过。但这里的难点在于:需要同时对a, b和c(-a - b)去重。去重的细节太多了,基本上都会遇到小问题,难以一次想周全。因此推荐使用更易于理解的双指针法

双指针法的思路:使用双指针法之前需要对数组进行排序。for循环遍历数组,得到a;left指针从数组的第2个位置开始向后移动,得到b;right指针从数组的最后一个位置开始向前移动,得到c。若num[i] + num[left] + num[right] > 0,说明三数之和大了,i是固定的(for循环从头开始遍历),因此应当让right --。若num[i] + num[left] + num[right] < 0,说明三数之和小了,应该让其变大,则应当让left ++。若三数之和为0,则将三者放入二维数组res中。注意细节:去重。num[i], num[left], num[right]三个数都需要去重,因为res中不能有重复的三元组。

伪代码:(注:a = num[i], b = num[left], c = num[right]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
vector<vector<int>> res; // 存储结果
sort(nums.begin(), nums.end()); // 排序

for (int i = 0; i < nums.size(); i ++ )
{
// 排序后,若最小值仍大于0,说明不存在三数之和等于0的情况,返回现有的res即可
if (nums[i] > 0) return res;

// nums[i]即a,需要对a去重
// 三元组之间不可重复,但三元组内部可以有重复的数字,比如000
// 去重是nums[i] == nums[i + 1] continue还是nums[i] == nums[i - 1] continue
// 应该是后者。若是前者,由于left指针指向nums[i + 1],因此若b和a相同,则会跳过这个结果集,这显然是错误的
// 因为三元组内部是可以有重复的数字的
if (i > 0 && nums[i] == nums[i - 1]) continue; // 当前三元组的a和上一个三元组的a重复,则进入下一个循环

int left = i + 1, right = nums.size() - 1;
// 求三个数,因此是left > right。若left = right,则三个数变为了两个数
while (right > left)
{
if (nums[i] + nums[left] + nums[right] > 0) right -- ;
else if (nums[i] + nums[left] + nums[right] < 0) left ++ ;
else
{
res.push_back({nums[i], nums[left], nums[right]}); // 三者之和等于0.则放入结果数组中,收获结果
// 去重
while (right > left && right[i] == right[i - 1]) right -- ; // 对c去重
while (right > left && left[i] == left[i + 1]) left ++ ; // 对b去重
// 收获一个结果后,left和right都向着数组的中间位置移动
left ++ ;
right -- ;
}
}
}
return res;

细节:

  • 如何对a去重:if (i > 0 && nums[i] == nums[i - 1]) continue;

  • 如何对b和c去重:

    1
    2
    while (right > left && right[i] == right[i - 1]) right -- ; // 对c去重
    while (right > left && left[i] == left[i + 1]) left ++ ; // 对b去重
  • 对b和c去重的代码放在哪里
    必须先收获结果,再去重。否则若出现数组中全是0的情况,就会一直运行去重的逻辑,而不收获结果。

根据上述伪代码,我独立写出了本题的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 用双指针算法前需要先排序

vector<vector<int>> res; // 二维数组,存放结果

// 三元组{a, b, c},i指向a, left指向b, right指向c
// a = nums[i], b = nums[left], c = nums[right]
for (int i = 0; i < nums.size(); i ++ )
{
// 若最小的a都大于0,则三数之和不可能等于0,不需要继续循环,返回现有的res即可
if (nums[i] > 0) return res;

// 对a去重
if (i > 0 && nums[i] == nums[i - 1]) continue;

int left = i + 1, right = nums.size() - 1;

while (left < right)
{
if (nums[i] + nums[left] + nums[right] > 0) right -- ;
else if (nums[i] + nums[left] + nums[right] < 0) left ++ ;
else
{
res.push_back({nums[i], nums[left], nums[right]}); // 收获结果

// 对b和c去重
while (left < right && nums[left] == nums[left + 1]) left ++ ;
while (left < right && nums[right] == nums[right - 1]) right -- ;

// 移动left和right指针
left ++ ;
right -- ;
}
}
}
return res;
}
};

18. 四数之和

和三数之和思路相同,但多一重for循环。共有i, j, left, right四个指针,前三者初始时分别指向数组的前三个元素,right指向数组最后一个元素。left和right向中心靠拢,使得nums[i] + nums[j] + nums[left] + nums[right] = target

细节:剪枝和去重。

  • 一级剪枝:不能延续三数之和的剪枝操作:if(nums[i] > target) return res;。这没有考虑到数组中可能有负数的情况,若数组中有负数,几个元素相加是越加越小的,因此即使最小的数大于target,通过加上一些负数,四数之和依然可能为target。正确的剪枝操作应该为:if (nums[i] > target && nums[i] > 0 && target > 0) break;。其实这里写break(即最后返回)和写return res都是可以的,并不会影响运行结果。
  • 二级剪枝:if (nums[i] + nums[j] > target && nums[i] + nums[j] > 0 && target > 0) break;二级剪枝完成后只能写break,写return res会有几个测试样例无法通过。原因:一级剪枝条件时直接return res,相当于结束所有循环,返回结果,不会漏掉部分四元组;二级剪枝时直接return res,同样相当于结束所有循环,返回结果,此时就会漏掉部分四元组。正确的做法应该是结束第二重循环,继续进行第一重循环

其实还有一个细节需要注意,在求四数之和nums[i] + nums[j] + nums[left] + nums[right]时,若四个数都是10亿,加起来就会超过int的限制(大约21亿),因此需要把四数之和转化为long类型:(long) nums[i] + nums[j] + nums[l] + nums[r] > target。如果不将int转换为long,会报错:整数溢出,同时有几个测试样例无法通过。代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());

// a = i, b = j(i + 1), c = l(i + 2), d = r(nums.size() - 1)
for (int i = 0; i < nums.size(); i ++ )
{
if (nums[i] > target && target > 0 && nums[i] > 0) return res; // 一级剪枝
if (i > 0 && nums[i] == nums[i - 1]) continue; // 一级去重

for (int j = i + 1; j < nums.size(); j ++ )
{
if (nums[i] + nums[j] > target && target > 0 && nums[i] + nums[j] > 0) return res; // 二级剪枝
if (j > i + 1 && nums[j] == nums[j - 1]) continue; // 二级去重

int l = j + 1, r = nums.size() - 1;
while (l < r)
{
if ((long) nums[i] + nums[j] + nums[l] + nums[r] > target) r -- ;
else if ((long) nums[i] + nums[j] + nums[l] + nums[r] < target) l ++ ;
else
{
res.push_back({nums[i], nums[j], nums[l], nums[r]});
// 对l和r去重
while (l < r && nums[l] == nums[l + 1]) l ++ ;
while (l < r && nums[r] == nums[r - 1]) r -- ;
l ++ ;
r -- ;
}
}
}
}
return res;
}
};

心得与备忘录

454.四数相加II

  1. 本题的大体思路?
    遍历前两个数组A和B,将a + b的值存入map
    再遍历后两个数组C和D,在map中查找-(c + d)的值

  2. 为什么选择map做哈希?
    因为不仅需要存储a + b的值,还需要存储这个值出现的次数(map[a + b] ++),用于在4中统计元组的个数

  3. map中的key放什么?value放什么?
    map中的key放a + b的值,map中的value放这个值出现的次数

  4. 如何统计元组的个数?
    count += map[-(c + d)]

  5. 如何统计a和b的和出现的次数?
    map[a + b] ++

383. 赎金信

代码随想录上的哈希解法不如我在初次尝试部分写的哈希解法简洁,而且代码随想录的哈希解法在颠倒遍历两个字符串的顺序时容易出错。本题的最佳解法是我在初次尝试部分写的第二个版本的代码

15. 三数之和

  1. 采用双指针法,不要用哈希法,哈希法写起来复杂,去重麻烦、难以做剪枝操作,故效率显著低于双指针法
  2. 双指针法思路简单,但要注意去重的细节
  3. 排序的目的是方便剪枝,且一个三元组只会有唯一的顺序
  4. 双指针法只适用于返回的结果是数而不是索引的题目,因为双指针法使用前必须对数组进行排序,排序后索引会被打乱,因此返回的结果不能是索引。若两数之和要求返回的结果是数,那么也可以用双指针算法。这不禁让我思考,若本题要求返回的结果是索引,那么也只能用哈希法。但如果要求返回的结果是索引,那么就不需要有复杂的去重操作,因此实际上是简化了本题。
  5. 对于nums[i](即a)去重的代码,可以用if判断写:if (i > 0 && nums[i] == nums[i - 1]) continue;,也可以用while循环写:while (i < nums.size() && i > 0 && nums[i] == nums[i - 1]) i ++ ;。一般在写while循环时,都需要加上对数组索引不可越界的限制i < nums.size()。如果出现报错:Runtime Error: AddressSanitizer,大概率是因为数组索引越界了,此时需要检查是否加上了限制条件i < nums.size()i > 0

18. 四数之和

  1. 本题思路和三数之和相同,但需要注意剪枝的细节
  2. 还需要注意在求四数之和时将int类型转换为long类型,避免整数溢出。
  3. 若采用双指针算法,三数之和的时间复杂度是O(n^2),四数之和的时间复杂度是O(n^3)。用暴力做法的时间复杂度则分别为O(n^3)O(n^4)
  4. 本题相比于四数相加,由于要考虑去重问题,所以更加复杂,因此无法(不推荐)使用哈希法,推荐使用双指针算法。
  5. 剪枝方面可以做进一步的优化,但属实没有必要。
  6. 本题写剪枝统一用break,不要用return res,以免方式意外的错误
  7. 本题如果有几个测试样例总是过不了,可以直接删去剪枝的代码,一般就可以通过了。剪枝是优化,即使不加,依然可以轻松通过。剪枝部分是易错点。

哈希表总结

  1. 哈希表的使用场景:快速判断一个元素是否在集合中出现过。
  2. 哈希的三重境界:普通数组->set->map。
  3. 目前哈希中用到的set和map实际上是unordered_set和unordered_map,相对于set和map中的另外两种数据结构(set, multiset, map, multimap),unordered_set和unordered_map的查询效率和增删效率都是最高的。选择set类型的三种数据结构时,若我们不需要数据有序,且需要去重,且希望效率高,则用unordered_set。选择map类型的三种数据结构时,若我们不需要key有序,且希望效率高,则用unordered_map。
  4. 遇到哈希问题时,首先想想能不能用数组做哈希(比如题目中提到字符串中全是小写英文字母,就果断用数组做哈希)。用数组做哈希最直接,运行速度也最快,用set做哈希速度更慢,但遇到大规模的索引,数组放不下时,只能用set。
  5. 什么时候用map做哈希?当对一个元素需要同时存储两个值时,就必须用map做哈希。这两个值一个作为key,一个作为value存入map中。key中一般存储的是元素的值(便于查询),value中可以存放元素的索引(如1. 两数之和),也可以存放元素出现的次数(如454.四数相加II)。
  6. map可以当作普通数组一样使用,忘了STL的用法可以复习知识部分。
  7. 哈希表部分的八道算法题,前六道都使用的是正统的哈希法,最后两道(三树之和&四数之和)并非不可以使用哈希法,但使用哈希法需要进行复杂的去重操作,代码容易写错,且运行效率低下,因此推荐使用双指针算法。
  8. 三数之和&四数之和的易错点在于剪枝和去重。每重for循环都需要剪枝和去重,while循环进行去重即可,但其实剪枝是一种优化,并不是必须的。但去重是必须的!

快速了解项目

Snipaste_2024-01-30_11-45-52.png

从0带读Java小说项目。项目:小说精品屋

首先看代码的简介(README),然后看代码的更新频率(几年没更新的就不用看了)。

接着看项目的介绍,看项目的技术栈和我们自己的技术栈是否匹配。

接着看包结构(项目结构)。

看技术选型。高级的技术:ShardingSphere-JDBC(数据库分库分表支持)、分布式缓存支持、搜索引擎服务、开源消息中间件、文件存储、对象存储。

接着看核心:项目如何安装,如何启动

了解项目依赖

通过github1s(在线查看项目的工具)看项目。

==看项目从整体到局部,先看项目的架构及关键配置文件==

比如assets放静态文件,sql放SQL语句。根目录下的pom.xml定义了父工程的配置。在父工程的配置中又定义了子模块,可以达到多包同时编译的效果。

dockerfile:可以用其来生成一个docker镜像

Java的项目主要分为两部分:resources放一些资源文件和配置,另一部分是java的核心代码。

看resources/application.yml:跑起这个项目需要启动哪些服务。

resources/mybatis:放一些SQL语句

resources/static:放前端的文件,比如javascript, css等等。

resources/templates:用的是thymeleaf,拓展标签可以动态地把一些后台数据渲染到页面。

resources/application-dev.yml:是项目的开发环境的配置。

resources/application-prod.yml:是项目生成环境的配置。

resources/logback.yml:日志

了解项目结构

现在java项目的目录结构比较清晰和规范。都是mvc结构:model view controller。

controller:控制层,接收用户的请求,给予一些响应,业务逻辑一般不写在其中

core:项目核心的类

mapper:mybatis的映射文件,在这个文件中定义操作数据库的方法

page:控制页面的返回。用户请求一个地址,请求发送到controller,会响应并返回某个页面给用户,和前端的模板有关联。

service:编写业务的逻辑

vo:返回给页面的数据

springboot的启动类,会自动帮助我启动一个tomcat服务器

追踪请求(了解分层)

参考

带你读懂一个开源项目,学习通用套路!程序员阅读项目源码技巧、Java 编程项目分享

编程导航

小说精品屋

链接

哈希表理论基础
242.有效的字母异位词
349. 两个数组的交集
202. 快乐数
1. 两数之和

知识

哈希表理论基础

哈希表->哈希函数->哈希碰撞->拉链法/线性探测法->常见的三种哈希结构->set & map及如何选取->总结

哈希表

哈希表是根据关键码的值而直接进行访问的数据结构。举例:其实数组就是一张哈希表。哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素。

哈希表能解决什么问题呢,一般哈希表都是用来快速判断一个元素是否出现集合里。

哈希函数

哈希函数:哈希函数,把学生的姓名直接映射为哈希表上的索引,然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。通过hashCode把名字转化为数值,一般hashcode是通过特定编码方式,可以将其他数据格式转化为不同的数值,这样就把学生名字映射为哈希表上的索引数字了。如果hashCode得到的数值大于哈希表的大小了,也就是大于tableSize了,此时为了保证映射出来的索引数值都落在哈希表上,我们会在再次对数值做一个取模的操作,这样我们就保证了学生姓名一定可以映射到哈希表上了。

如果学生的数量大于哈希表的大小怎么办,此时就算哈希函数计算的再均匀,也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下标的位置。接下来哈希碰撞登场。

哈希碰撞

小李和小王都映射到了索引下标 1 的位置,这一现象叫做哈希碰撞。一般哈希碰撞有两种解决方法, 拉链法和线性探测法。

拉链法/线性探测法

其实拉链法就是要选择适当的哈希表的大小,这样既不会因为数组空值而浪费大量内存,也不会因为链表太长而在查找上浪费太多时间。使用线性探测法,一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。例如冲突的位置,放了小李,那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ,要不然哈希表上就没有空置的位置来存放冲突的数据了。

常见的三种哈希结构

当我们想使用哈希法来解决问题的时候,我们一般会选择如下三种数据结构。

  • 数组
  • set (集合)
  • map(映射)

set & map及如何选取

Snipaste_2024-01-29_09-29-58.png

std::unordered_set底层实现为哈希表,std::set 和std::multiset 的底层实现是红黑树,红黑树是一种平衡二叉搜索树,所以key值是有序的,但key不可以修改,改动key值会导致整棵树的错乱,所以只能删除和增加。

img

std::unordered_map 底层实现为哈希表,std::map 和std::multimap 的底层实现是红黑树。同理,std::map 和std::multimap 的key也是有序的(这个问题也经常作为面试题,考察对语言容器底层的理解)。

两个unordered都是哈希表实现的,其他四个都是红黑树实现的。三类set和三类map性质上是类似的。

当我们要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。

那么再来看一下map ,在map 是一个key-value 的数据结构,map中,对key是有限制,因为key的存储方式使用红黑树实现的,对value没有限制。

虽然std::set、std::multiset 的底层实现是红黑树,不是哈希表,std::set、std::multiset 使用红黑树来索引和存储,不过给我们的使用方式,还是哈希法的使用方式,即key和value。所以使用这些数据结构来解决映射问题的方法,我们依然称之为哈希法。 map也是一样的道理。

总结

总结一下,==当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法==。哈希法的查询速度很快:O(1)。

但是哈希法也是牺牲了空间换取了时间,因为我们要使用额外的数组,set或者是map来存放数据,才能实现快速的查找。

如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景也应该第一时间想到哈希法!

题目

242.有效的字母异位词

  1. 将一个数组中的元素全部置为0:int hash[26] = {0};。实际上,直接写int hash[26]也可以,不给数组中的值赋值,数组中的值默认为0。
  2. 求字符串string s的长度,可以用s.size(),也可以用s.length()
  3. s[i] - 'a':编译器会自动用ascii码进行计算,不需要手动将变量类型转换为整数。
  4. 一个有返回值的函数,如果执行了return语句,函数直接结束,不需要再break。
  5. 定义一个常量大小的数组,空间复杂度是O(1)。

349. 两个数组的交集

  1. set, multiset, unordered_set。前两者底层实现是红黑树,最后一个的底层实现是哈希值直接映射。unordered_set就是一个可以无限存装的数组。本题用unordered_set,因为其做映射和取值时效率最高,前两者的底层实现是树,因此取值是还要有查找的过程。unordered_set中的元素不可重复,相当于自动帮我们做去重;而multiset中的元素可以重复。
  2. 可以直接将set类型的数据转换为vector类型:return vector<int>(set.begin(), set.end())
  3. cpp中的vector中既有insert方法,又有push_back方法,前者需要指定插入元素的具体位置,后者直接将元素插入到vector的末尾。cpp的set(包括set, multiset, unordered_set)中只有insert方法,传入的参数为要插入的值,不需要指定插入元素的具体位置。
  4. 将vector转换为unordered_set: unordered_set<int> nums1_set(nums1.begin(), nums1.end())
  5. 在unordered_set中查找元素:nums1_set.find(nums2[i]),返回的结果是一个迭代器(指针)。如果找到该值,find返回一个指向该元素的迭代器;如果未找到,则返回一个指向unordered_set末尾的迭代器,即end()迭代器。

1. 两数之和

  1. 返回一个vector可以直接将vector的内容写入大括号中,然后返回,比如return {a[i], b[i]},返回一个空数组可以直接写成return {},而不用定义一个vector再利用push_back方法向其中插入数,然后再返回这个vector。
  2. 定义的vector<int> a,若不给其赋值,则该vector长度为0。可见vector是动态地被分配内存,如果不给其赋值,则其长度为0,不占用内存,这与普通数组需要在定义时声明长度有所不同。
  3. 定义unordered_map的方式:unordered_map<int, int> map;unordered_map中有insert函数和find函数,用法同unordered_set;遍历这些STL容器都要用迭代器,相当于是一种加强版的指针;访问unordered_map的key和value:map->firstmap->second

初次尝试

242.有效的字母异位词

想到一个办法,用两个数组分别统计两个字符串中出现的字母和字母出现的频次,然后判断两个数组是否完全相同。代码如下所示,可以成功运行:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
bool isAnagram(string s, string t) {
int hash1[26] = {0};
int hash2[26] = {0};

for (int i = 0; i < s.size(); i ++ )
hash1[s[i] - 'a'] ++ ;

for (int i = 0; i < t.size(); i ++ )
hash2[t[i] - 'a'] ++ ;

for (int i = 0; i < 26; i ++ )
if (hash1[i] != hash2[i])
return false;
return true;
}
};

稍微麻烦了点,实际上用一个数组就够了。

349. 两个数组的交集

暂时还不会用set做哈希,因此先尝试用数组做哈希。我写下了如下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
int hash1[1000] = {0};
int hash2[1000] = {0};

// 统计两个数组nums1和nums2中每个数值出现的频次
for (int i = 0; i < nums1.size(); i ++ )
hash1[nums1[i]] ++ ;
for (int i = 0; i < nums2.size(); i ++ )
hash2[nums2[i]] ++ ;

vector<int> res;

// 若一个数同时在nums1和nums2数组中出现的频次>=1,则该数是两数组的重叠,放入结果数组res中
for (int i = 0; i < 1000; i ++ )
{
if (hash1[i] && hash2[i])
res.push_back(i);
}
return res;
}
};

本题其实是使用set的好题,但是后来力扣改了题目描述和测试用例,添加了 0 <= nums1[i], nums2[i] <= 1000 条件,所以使用数组也可以了,不过建议大家忽略这个条件。 尝试去使用set。

202. 快乐数

尽管说这道题和上一道题原理上差不多,只是套了快乐数的壳子,但我看不出这题怎么用set来进行哈希。直接看讲解吧。

1. 两数之和

看到的第一想法是类似滑动窗口,但滑动窗口(209.长度最小的子数组)返回的是长度最小的子数组的长度,这道题却要返回两个整数的下标,因此还是有很大不同的。如果要快速在集合中查找一个元素是否出现过,那么应该采用哈希表的方法。我产生了一个想法,将nums数组中的所有数一对一对不重不漏地取出,将每一对数的和作为索引(key),将它们的下标作为(value)存入map中,然后通过查询map的索引来找到目标对,进而返回目标对的下标。实现起来有两个难点:

  • 如何不重不漏地枚举所有的数对?
  • 如何将两个下标存入一个value里?

实现

242.有效的字母异位词

判断两个字符串是否由相同的字母组成,但字母的位置可以不同。两个完全一样的字符串也是有效异位词。由于字符串中都是小写字母,因此a可以对应数组中索引为0的位置,z可以对应数组中索引为25的位置。用数组hash[26]统计第一个数组中每个字母出现的频率,然后第二个字符串中每个字母出现的频率再在hash数组中做对应的减法,若最后数组中所有元素均为0,则说明两个字符串互为有效的字母异位词。

什么时候用数组/set/map:当哈希值较小,且范围也较小且可控;若哈希值很大,则用set;若是key-value对,则用map

根据上述思路,我独立写出了代码,如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
bool isAnagram(string s, string t) {
int hash[26] = {0}; // 数组中的元素全部初始化为0

for (int i = 0; i < s.size(); i ++ )
hash[s[i] - 'a'] ++ ;

for (int j = 0; j < t.size(); j ++ )
hash[t[j] - 'a'] -- ;

for (int i = 0; i < 26; i ++ )
if (hash[i])
return false;
return true;
}
};

349. 两个数组的交集

返回两个数组的交集。注意要去重。虽然可以用数组哈希,但还是建议用set。若保持之前的题目描述,让两个数组中的数值可能非常大,比如上亿,此时就必须要用set了,因为数组下标放不下那么大的数,同时会浪费很多存储空间。

哈希表善于解决判断一个元素是否在一个集合中出现过的题目。集合中的数值很大时,或者集合中的元素数量很少但数值很分散时,用数组不合适,要用set。先将数组nums1中的所有数值放到哈希表中,再遍历num2,查看其中的元素的数值是否在哈希表中出现过,出现过则放入res集合中。

因为要去重,所以定义unordered_set来存储result。哈希表也用unordered_set。直接将nums1转化为unordered_set的存储结构。接着遍历nums2,看哈希表中是否出现了nums2中的元素,出现了则将其放入result中。

set哈希法

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
// 存储答案的unordered_set,因为是unordered_set所以自动去重
unordered_set<int> res;

// 将nums1从vector转换为unordered_set
unordered_set<int> nums1_set(nums1.begin(), nums1.end());

// 在nums1_set中查找nums2中的数据,如果出现过,则将其插入res中
// 也可以用范围遍历for (int num: nums2)
for (int i = 0; i < nums2.size(); i ++ )
{
if (nums1_set.find(nums2[i]) != nums1_set.end())
res.insert(nums2[i]);
}

// 将res从unordered_set类型转换回vector类型
return vector<int>(res.begin(), res.end());
}
};

时间复杂度:
构建nums_set:O(n)
遍历nums2并检查元素是否在nums_set中:O(m)
构建结果向量:O(k),其中k是结果集中元素的数量
综上所述,总的时间复杂度是O(n + m + k)。但是由于k(结果集的大小)是由n和m决定的,并且在大多数情况下k会小于n和m,所以可以近似地认为时间复杂度主要由n和m决定,即O(n + m)。

如果用数组做哈希的话,除了我在初次尝试中写的那种方式,其实还有另一种方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> res; // 存储结果,去重

int hash[1000] = {0};

// nums1中出现过的数,则将其在哈希数组中的值标记为1
for (int num: nums1)
hash[num] = 1;

// 若nums2中的数在nums1中出现过,则将其插入res中
for (int num: nums2)
if (hash[num] == 1)
res.insert(num);

// unordered_set->vector
return vector<int>(res.begin(), res.end());
}
};

202. 快乐数

题目中说:Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.本题本来是一个数学问题,可以得到严格的数学证明,但我们不需要懂数学,可以用编程的思维去解决它。

因此,一个数进行如题的操作后,要么会陷入死循环,要么会在某个时刻等于1并保持。因此,可以写一个循环来持续对输入的数进行如题的操作,如果某次操作的结果在之前出现过,那么该数就不是快乐数;如果操作的结果为1,那么该数就是快乐数。要快速判断一个元素是否在集合中出现过,就应该用一个set将集合中的所有元素维护起来。代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
// 用于求一个数每一位的平方之和的函数
int getSumofDigits(int n)
{
int s = 0;

while (n)
{
s += (n % 10) * (n % 10); // 求每一位的平方
n /= 10;
}
return s;
}

bool isHappy(int n) {
unordered_set<int> loop;

// 持续循环
while (1)
{
int s = getSumofDigits(n);

if (s == 1) return true; // 结束循环,是快乐数
else
{
// 若发现出现死循环,则立即返回不是快乐数
if (loop.find(s) != loop.end()) return false;
// 尚未出现死循环,则继续
else
{
loop.insert(s);
n = s;
}
}
}
}
};

可以将上述代码写得更见简练,更好理解:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
int getSum(int n)
{
int s = 0;

while (n)
{
s += (n % 10) * (n % 10);
n /= 10;
}
return s;
}

bool isHappy(int n) {
unordered_set<int> set;

while (1)
{
int s = getSum(n);

if (s == 1) return true; // 退出条件1,是快乐数
if (set.find(s) != set.end()) return false; // 退出条件2,不是快乐数

// 不满足两个退出条件,则继续循环
n = s;
set.insert(s);
}
}
};

这里主要处理的是数字 n 的每一位,一个数字n它的位数可以认为是logn(一个d位的数大约是10的d次方,n = 10^d => d = logn)。每次进行快乐数的判断会执行一次该计算操作,但是因为快乐数的范围有限,总体来看不会超过 logn 的常数倍,因此时间复杂度是O(log n)。

所以随着n的增加,存储在unordered_set中的不同可能结果的数量实际上是有限的。事实上,随着n的增长,这个数量的增长速度接近于对数增长。换句话说,即使n非常大,经过getSum处理后的结果仍然是一个相对较小的数字集合。因此空间复杂度为O(logn)。至于为什么是logn,我认为原因是其增长速度最慢,这比sqrt(n)等其他形式更符合n较大时set中存储的元素的数量接近一个常数的事实。

1. 两数之和

本题需要用map解决。判断一个元素是否在一个集合中出现过:用哈希法。假设target = 9,当遍历到元素3时,我们需要去寻找元素6是否被遍历过。把遍历过的元素加到一个集合(哈希表结构)中,每次遍历新元素a时,判断(target - a)是否在集合中出现过。若出现过,我们需要知道其下标,因此集合中既要存储元素的值,又要存储元素的下标。此时想到用map,存储元素的值用map的key,存储元素的下标用map的value(因为要查找元素是否出现过,因此以元素的值作为key,map能以最快的速度找到这个key是否在这个map中出现过)。

看完上述思路后,我独立写出了以下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> store;
vector<int> res;

// 将所有元素的值作为key,索引作为value存入map中
for (int i = 0; i < nums.size(); i ++ )
store.insert({nums[i], i});

// 每遍历到一个元素nums[i],查找target - nums[i]是否在map中
// 是则返回结果
for (int i = 0; i < nums.size(); i ++ )
{
int t = target - nums[i];
auto it = store.find(t);

// 注意除去第一个条件外,还需要保证查找到的元素并非当前元素本身
// 否则会出现target = 两倍当前元素而导致的误判
if (it != store.end() && it->second != i)
{
res.push_back(i);
res.push_back(it->second);
return res;
}
}
return res;
}
};

继续听讲解,map用于存放遍历过的元素的值和索引。本题使用unordered_map,其存和读的效率是最高的。因此写出了以下的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> store;
vector<int> res;

// 每遍历到一个元素nums[i],查找target - nums[i]是否在map中
// 是则返回结果
for (int i = 0; i < nums.size(); i ++ )
{
int t = target - nums[i];
auto it = store.find(t);

// 若找到了target - nums[i],则将其索引和当前遍历的元素的索引返回
if (it != store.end())
{
res.push_back(i);
res.push_back(it->second);
return res;
}
// 将已经遍历过的元素的值作为key,索引作为value存入map中
store.insert({nums[i], i});
}
return res;
}
};

我的第一版代码在store中存储了数组中所有元素的值和索引,因此需要保证查找到的元素并非当前元素本身。第二版代码在store中存储的是已经遍历过的元素,故天然满足查找到的元素并非当前元素本身的条件。两版代码都是对的,但后者更为简洁。最简洁版本的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map; // 用于存储已遍历过的元素的值和索引

for (int i = 0; i < nums.size(); i ++ )
{
// 用于查找map中是否有目标元素
auto it = map.find(target - nums[i]);
// 有,则返回两个索引构成的vector
if (it != map.end()) return {i, it->second};
// 无,则将当前元素的值和索引插入map中,然后开始循环的下一轮
map.insert({nums[i], i});
}
// 完成循环后还没找到两个索引,则返回空vector
return {};
}
};

心得与备忘录

242.有效的字母异位词

  1. 本题的本质是判断两个字符串是否由相同的字母组成。
  2. 本题用数组实现哈希。
  3. 遇到哈希问题时,首先想想能不能用数组做哈希。用数组做哈希最直接,运行速度也最快,用set做哈希速度更慢,但遇到大规模的索引,数组放不下时,只能用set。

349. 两个数组的交集

  1. 本题本来不改测试数据,数组中的数值可能很大时,只能用set做哈希。现在对数组中的数值做了限制,最大不超过1000,则可以用数组做哈希。
  2. 用数组做哈希比用set做哈希效率更高,因为用set的话每次往里Insert一个值,都需要对这个值做一次哈希运算,同时还要开辟一个新的空间。用数组的下标做哈希映射永远是最快的。
  3. 本题适合用来衔接用数组做哈希和用set做哈希。
  4. 本题用set做哈希时,要记住set的各种用法:vector和unordered_set互相转化,在unordered_set中查找元素。这些用法归纳在知识中。
  5. 本题有三种解法:一种是用set哈希,另外两种是用数组做哈希。用数组做哈希建议采用我在初次尝试中的做法,只需要用到数组,不需要用到unordered_set去重。
  6. 采用范围遍历的写法可以简化代码。

202. 快乐数

这道题的逻辑其实非常简单。若各个位上的平方和为1,则退出循环,返回是快乐数;若平方和之前出现过,则说明进入了死循环,也退出循环,返回不是快乐数;其他情况下,继续循环。由于本题的1 <= n <= 2^31 - 1,各个位的平方和的数据范围非常大,因此必须用set做哈希,不能再用数组做哈希。注意本题时间复杂度和空间复杂度的分析。时间复杂度和空间复杂度不存在sqrt(n)等表达式,要么是1, 要么是logn,要么是n,要么nlogn或者更大。

1. 两数之和

四个重要问题:

  1. 为什么用哈希法:快速查找一个元素(目标元素)是否在集合(unordered_map存放已遍历过的元素)中出现过。
  2. 为什么要用map(unordered_map):因为既需要存储元素的值,也需要存储元素的索引。这道题目中并不需要key有序,选择unordered_map 效率更高。
  3. map的作用:存储已遍历过的元素的值和索引。
  4. map中的key存了元素的值(便于查询),value存了元素的索引(作为结果返回)。

链接

24. 两两交换链表中的节点
19.删除链表的倒数第N个节点
面试题 02.07. 链表相交
142.环形链表II
链表总结篇

知识

面试题 02.07. 链表相交

  1. 两个链表的交点不是数值相等,而是指针相等。
  2. 本题在构造测试样例时,会输入两个单链表和两个单链表的交叉点,以及交叉点到两个链表头节点的距离。因此,只有指定的交叉点才是真正的交叉点,仅仅是值相等的节点并不一定是真正的交叉点。指定的交叉点被构造出来时在内存中的地址相同,而仅仅是值相等的两个节点在内存中的地址不一定相同。

初次尝试

24. 两两交换链表中的节点

应该和交换数组中的两个元素相同。需要创建一个额外的节点tmp,然后若要交换a节点和b节点,则进行:tmp = b, a = b, b = tmp即可。

19.删除链表的倒数第N个节点

我能想到的办法:先遍历一遍列表,返回列表有几个节点。然后再遍历一遍列表,当cur指向倒数第N个节点的前一个节点时,停止遍历链表,删除cur->next,然后返回链表的头节点即可。应该也要用到虚拟头节点,避免删除链表的第一个节点时需要特判。我按照上述思路写了代码,可以成功通过测评!!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
// 创建虚拟头节点
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;

// 统计链表中的节点数量
int size = 0;
ListNode* cur = dummyHead;
while (cur->next != NULL)
{
cur = cur->next;
size ++ ;
}

// 将cur指向倒数第n个节点的前一个节点
ListNode* cur1 = dummyHead;
int size1 = 0;
while (size1 < size - n)
{
cur1 = cur1->next;
size1 ++ ;
}

// 删除倒数第n个节点,并释放其占用的内存
ListNode* tmp = cur1->next;
cur1->next= cur1->next->next;
delete tmp;

// 返回结果
return dummyHead->next;
}
};

更好的办法是采用双指针算法,见实现部分。

面试题 02.07. 链表相交

我的第一想法是采用暴力解法。一个指针指向链表A的头节点,一个指针指向链表B的头节点,移动两个指针,当两个指针指向同一个节点时,说明该节点是两个链表相交的节点。据此,我写出了暴力解法的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* dummyHead1 = new ListNode(0);
ListNode* dummyHead2 = new ListNode(0);
dummyHead1->next = headA;
dummyHead2->next = headB;

ListNode* cur1 = dummyHead1;
ListNode* cur2 = dummyHead2;

for (cur1 = dummyHead1; cur1 != NULL; cur1 = cur1->next)
{
for (cur2 = dummyHead2; cur2 != NULL; cur2 = cur2->next)
{
if (cur1 == cur2)
return cur1;
}
}
return NULL;
}
};

暴力解法的时间复杂度是O(n^2),应该有时间复杂度为O(n)的解法。时间复杂度更低的代码参见代码随想录。

142.环形链表II

从没有见过这类题目,拿到题目毫无思路,直接看视频讲解和文字题解。

实现

24. 两两交换链表中的节点

注意:是交换链表中的节点,而不仅仅交换节点的数值。偶数个节点则正好两两交换,奇数个节点则最后一个点不参与交换。一定需要dummyHead,因为要交换节点1、2,就一定要用到它们之前的那个节点,即dummyHead(dummyHead->2->1->3->…)。同理,要交换节点3、4,就一定要用到它们之前的那个节点,即节点2。因此当前指针一定要指向要反转的两个节点中的前一个节点,且当前指针每次移动两位

若链表中的节点个数为奇数,则cur->next->next == NULL时循环结束,若链表中的节点个数为偶数,则cur -> next == NULL时循环结束。如下图所示。故遍历结束的条件为 while (cur->next != NULL && cur->next->next != NULL)。两个条件不可以反过来写,否则当出现空链表时,cur->next->next没有被定义,会出现空指针异常。
绘图1.png

接下来是两两交换节点的逻辑。改变后的链表为dummyHead->2->1->3,由于dummyHead->1改变为dummyHead->2后,原本的节点1已经不能被访问到了,因此需要先用tmp存下节点1。同理,由于要将2->3改为2->1,因此需要先用tmp1存下节点3。交换完节点的链表为:dummyHead->2->1->4->3…..。对于两两交换节点的逻辑,可以参考代码随想录教程中的三幅图片。

24.两两交换链表中的节点3

交换3和4节点的步骤时:cur目前为1,我们让1指向4,4再指向3,3再指向5(如果有5的话)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
// 交换两个节点需要用到这两个节点前的那个节点
// 因此定义虚拟头节点,用于交换节点1和节点2
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;

ListNode* cur = dummyHead;
// 搞清楚遍历的终止条件,参见笔记的图示
// 以下两个终止条件分别针对节点数目为偶数和奇数的情况
while (cur->next != NULL && cur->next->next != NULL)
{
// dummyHead->2时,dummyHead->1不再存在,无法访问到1,因此需要事先存储节点1
ListNode* tmp = cur->next;
// 同理,2->1时,2->3不再存在,无法访问到3,因此需要事先存储节点3
ListNode* tmp1 = cur->next->next->next;

// dummyHead->2->1->3
cur->next = cur->next->next; // dummyHead->1变为dummyHead->2
cur->next->next = tmp; // dummyHead->2->3变成dummyHead->2->1
tmp->next = tmp1; //dummyHead->2->1再在末尾接上3

cur = cur->next->next; // cur指针后移两位
}
return dummyHead->next;
}
};

19.删除链表的倒数第N个节点

看了代码随想录的思路之后,我独立写出了快慢指针解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;

// 快慢指针
ListNode* fast = dummyHead;
ListNode* slow = dummyHead;

// fast先向后移动n位
while (n -- ) fast = fast->next;

// fast移动到链表的最后一个节点(非空节点),此时slow移动到链表的倒数第n个节点前面的那个节点
while (fast->next != NULL)
{
slow = slow->next;
fast = fast->next;
}

// 删除倒数第n个节点
ListNode* tmp = slow->next;
slow->next = slow->next->next;
delete tmp;

return dummyHead->next;
}
};

也可以让fast先向后移动(n + 1)位,然后让fast和slow同时移动,直到fast移动到NULL为止,此时slow指向的也是倒数第n个节点的前一个节点。对这种办法,可以在移动fast指针前先让n ++ , 也可以在第一个while循环后让fast指针多向后移动一位。最稳妥的写法如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;

ListNode* fast = dummyHead;
ListNode* slow = dummyHead;

// 首先将快指针移动n + 1步
n ++ ;
while (n -- && fast != NULL) fast = fast->next;

// 快慢指针同时移动,直到快指针指向NULL。此时慢指针指向要删除的节点前面那个节点
while (fast != NULL)
{
fast = fast->next;
slow = slow->next;
}

// 释放内存并删除倒数第n个节点
ListNode* tmp = slow->next;
slow->next = slow->next->next;
delete tmp;

return dummyHead->next;
}
};

由于题目有如下限制:

1
2
3
4
The number of nodes in the list is sz.
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

因此即使不加上fast != NULL,也可以通过,但如果题目没有n <= sz的限制,那么必须加上fast != NULL,且不能使用以下写法:

1
2
while (n -- && fast != NULL) fast = fast->next;
fast = fast->next;

因为若采用以上写法,当n > sz时,当while循环结束后,fast已经指向了NULL,此时再做fast = fast->next操作,会导致空指针异常。

面试题 02.07. 链表相交

代码随想录的思路:求出两个链表的长度,并求出两个链表长度的差值,然后让curA移动到,和curB末尾对齐的位置。此时我们就可以比较curA和curB是否相同,如果不相同,同时向后移动curA和curB,如果遇到curA == curB,则找到交点。否则循环退出返回空指针。

看了代码随想录的思路后,我独立写出了代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int sizea = 0, sizeb = 0;
ListNode* cura = headA;
ListNode* curb = headB;

// 计算a链表的长度
while (cura != NULL)
{
cura = cura->next;
sizea ++ ;
}

// 计算b链表的长度
while (curb != NULL)
{
curb = curb->next;
sizeb ++ ;
}

cura = headA, curb = headB;

int delta = abs(sizea - sizeb); // 两链表长度的差值

if (sizea >= sizeb)
{
while (delta -- ) cura = cura->next;

while (sizeb -- )
{
if (cura == curb) return cura;
else
{
cura = cura->next;
curb = curb->next;
}
}
}
else
{
while (delta -- ) curb = curb->next;

while (sizea -- )
{
if (cura == curb) return cura;
else
{
cura = cura->next;
curb = curb->next;
}
}
}
return NULL;
}
};

这里特别需要注意的是,在计算完a链表和b链表的长度后,需要让 cura = headA, curb = headB

代码随想录的写法更见简洁:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* cura = headA, * curb = headB;
int sizea = 0, sizeb = 0;

// 计算a链表和b链表的长度
while (cura != NULL)
{
cura = cura->next;
sizea ++ ;
}
while (curb != NULL)
{
curb = curb->next;
sizeb ++ ;
}

// 始终保证链表a的长度大于等于链表b的长度
if (sizea < sizeb)
{
swap(sizea, sizeb);
swap(headA, headB);
}

// 交换cura和curb后,再恢复cura和curb的指向
// 也可以在上面直接swap(cura, curb),那这句话就可以写到if判断的前面去
cura = headA, curb = headB;

// 计算两链表的长度之差
int delta = sizea - sizeb;

// 移动指向链表a的指针,让链表a和b的尾部对齐
while (delta -- ) cura = cura->next;

while (cura != NULL) // 写作while (sizeb -- )也可
{
if (cura == curb) return cura;
cura = cura->next;
curb = curb->next;
}
return NULL;
}
};

142.环形链表II

有两问:

  1. 判断链表中是否有环

    用快慢指针来判断是否有环。若链表是一条直线,则快慢指针永远不会相遇。只有当链表中有环存在时,快指针先进入了环且在环中浪费了时间,快慢指针才会相遇。快指针从头节点开始,每次移动两位,慢指针也从头节点开始,每次移动一位,二者若相遇则一定在环里相遇,相遇则说明有环。快指针是一个节点一个节点的靠近慢指针,因此二者一定会在环中相遇。

  2. 找到环的入口

    img

    列方程即可解出x:x = n (y + z) - y, (n >= 1),由于看不出x和负数-y之间的关系,我们让出一圈,看x和z的关系:x = (n - 1) (y + z) + z, (n >= 1)。这就意味着:从头结点出发一个指针,从相遇节点 也出发一个指针,这两个指针每次只走一个节点, 那么当这两个指针相遇的时候就是环形入口的节点

    为什么第一次在环中相遇,slow的步数是x+y而不是 x + 若干环的长度 + y 呢?”这个问题,可以这样解释,设快指针每秒移动2格,慢指针每秒移动1格,圆的周长是k。则慢指针走一圈需要的时间是k,设两指针之间的距离为m(m < k),则快指针追上慢指针的时间是m(快指针相对于满指针每秒移动1格),此时慢指针走过的距离是m,由于m < k,因此慢指针在遇到快指针之前走过的距离小于圆的周长。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head, * slow = head;

// 下面两个循环条件保证了fast指针可以指向NULL,但不能指向NULL的next,这样就不会导致空指针异常
while (fast != NULL && fast->next != NULL)
{
fast = fast->next->next; // 快指针每次移动两位
slow = slow->next; // 慢指针每次移动一位

// 快慢指针相遇,说明链表中有环
if (fast == slow)
{
// 一指针从相遇处开始移动,一指针从head处开始移动,二者相遇的位置就是环的入口,数学推导见笔记
ListNode* index1 = fast, * index2 = head;
while (index1 != index2)
{
index1 = index1->next;
index2 = index2->next;
}
return index1;
}
}
return NULL; // 若没有返回环的入口节点,则说明没有环,返回空指针
}
};

我自研的另一种写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head, * slow = head;

bool flag = false;
// 判断链表中是否有环
while (fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
{
flag = true;
break;
}
}

// 有环,则返回环的起点,无环,则返回空指针
if (flag && fast == slow)
{
ListNode* index1 = head, * index2 = slow;

while(index1 != index2)
{
index1 = index1->next;
index2 = index2->next;
}
return index1;
}
else
return NULL;
}
};

注意,一定要通过flag判断,只有当fast和slow相等且二者都在第一个while循环中转过时,才能确保链表中有环,若fast和slow相等,则可能是链表中只有一个节点的情况,此时fast和slow都没有在第一个循环中转过,因此二者相等且都等于head。

心得与备忘录

24. 两两交换链表中的节点

  1. 注意cur应该指向哪里。
  2. 注意遍历的终止条件(奇数/偶数个节点)
  3. 若原先的两节点之间的连接被断开,则需要在断开前保存两节点中后面那个节点,否则后面的那个节点无法被访问到

面试题 02.07. 链表相交

  1. 本题的关键思路在于:对齐两个链表的尾部。本题的算法实际上也是(快慢)双指针算法。
  2. 比较链表中的两个节点是否相同,直接用 cura == curb即可,不能用 cura->val == curb->val && cura->next == curb->next,因为比较两个节点除去比较val和next这两个参数外,还需要比较其本身的内存地址。
  3. 本题的时间复杂度分析:
    计算两个链表的长度:O(n) + O(m)
    调整指针以对齐两个链表:O(n - m)或O(m - n)
    同时遍历两个链表寻找交点:O(min(n, m))
    第一步和第三步的时间复杂度加在一起是 O(n) + O(m) + O(min(n, m))。但是,因为 O(min(n, m))O(n) + O(m)中已经被包含(总是小于或等于 nm),所以总的时间复杂度简化为 O(n) + O(m)。第二步(调整指针以对齐两个链表)的时间复杂度实际上也包含在 O(n) + O(m)中,因为无论是 n - m还是 m - n,它的值总是小于或等于 nm。因此,整个函数的总时间复杂度为 O(n + m),这里 nm分别是两个链表的长度。这个时间复杂度已经涵盖了所有的主要操作,包括计算长度、对齐链表和寻找交点。时间复杂度的计算应当关注主要操作,省略次要操作
  4. 在leetcode中调用swap,abs等函数时,不需要自行引用头文件,基本的函数和数据结构(STL)已经默认被引用了,因此直接写出来即可。

142.环形链表II

  1. 记住使用快慢双指针算法,有环的情况下快慢指针必然会相遇。
  2. 画图理解如何求环的起点的index。
  3. 记得复习时着重看这道题

总结:链表

  1. 插入虚拟头节点dummyHead,可以避免空链表并避免对头节点操作的特判
  2. 创建一个当前节点cur,对整个链表进行遍历(cur = cur->next),而不用链表中原本存在的节点对链表进行遍历
  3. NULL节点表示不存在的节点;虚拟节点实际上是存在的,其值为0,是人为创建的节点
  4. 递归时,需要先检查递归的终止条件,然后执行递归步骤
  5. 想要删除哪个节点,就用cur指针指向其前面的那个节点
  6. 链表中最常用的算法是双指针算法,在206.反转链表,19.删除链表的倒数第N个节点,面试题 02.07. 链表相交,142.环形链表II中都用到了,其他题目基本不需要算法,利用链表的一些基本性质进行增删改查即可。
  7. 记得复习142.环形链表II和24.两两交换链表中的节点,前者是链表中最独特也最难的一道题,难在数学推导和想清楚细节;后者在退出循环的条件和用tmp保存节点方面需要特别注意。

img

链接

链表理论基础
203.移除链表元素
707.设计链表
206.反转链表

知识

链表理论基础

链表是一种通过指针串联在一起的线性结构。每个节点等于数据域+指针域(存放指向下一个节点的指针)。最后一个节点的指针域指向null。头节点head。

img

单链表、双链表:既可以向前查询也可以向后查询。
循环链表:链表首尾相连(解决约瑟夫环问题)

链表在内存中不是连续分布的。其通过指针域的指针链接在内存中的各个节点。

链表的定义:
手写链表:

1
2
3
4
5
6
// 单链表
struct ListNode {
int val; // 节点上存储的元素
ListNode *next; // 指向下一个节点的指针
ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数
};

通过上述构造函数初始化节点:ListNode* head = new ListNode(5);
使用默认构造函数初始化节点:

1
2
ListNode* head = new ListNode();
head->val = 5;

不定义构造函数使用默认构造函数的话,在初始化的时候就不能直接给变量赋值!

添加节点:见图

数组和链表有不同的适用场景。数组适合数据量固定,频繁查找,较少增删的场景;链表适合数据量不固定,频繁增删,较少查询的场景。

203.移除链表元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {

}
};

结构体中定义了两个变量和三个构造函数。class Solution中的removeElements函数返回的变量类型是ListNode*,即这个函数返回一个指向ListNode对象的指针。

如果使用C,C++编程语言的话,不要忘了还要从内存中删除这两个移除的节点。如果移除一个节点之后,没有手动在内存中删除这个节点,leetcode依然也是可以通过的,只不过,内存使用的空间大一些而已,但建议依然要养成手动清理内存的习惯。

删除头节点:

  • 直接使用原来的链表来进行删除操作:头节点后移一位
  • 设置一个虚拟头结点在进行删除操作:原链表的所有节点就都可以按照统一的方式进行移除了,最后return dummyNode->next;

707.设计链表

  • void函数可以直接return,表示退出
  • 统一使用虚拟头节点的方式,便于进行增删改的操作
  • 变量名前加_表示是这个类的变量,而非局部变量,这是cpp中的一种约定俗成

206.反转链表

初次尝试

203.移除链表元素

对链表题我一直有点懵,不太熟悉链表题的格式,但是对用数组模拟链表倒是挺熟悉的。我知道算法的思路大致是:先定义一个虚的头节点,然后遍历链表,删去值等于val的节点,然后返回头节点指针指向的节点,就是新的头节点,但我不知道这种代码怎么写。

707.设计链表

这题yxc也教过,但是在他那里似乎是用数组模拟链表,实现链表的各种功能,而这里是调用链表完成函数中的功能,我认为这题不难,只是多个功能需要分别实现,单个功能的代码较为简单。这道题我基本会做,但处理边界条件时要倍加注意!!

206.反转链表

yxc也讲过这个题,但我也给完全忘了

实现

203.移除链表元素

方法1: 特判头节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// 删除头节点
while (head != NULL && head -> val == val)
{
ListNode* tmp = head;
head = head -> next;
delete tmp;
}

// 删除非头节点
ListNode* cur = head; // cur存储要删去的节点的前一个节点
// 要删的节点cur->next不可为空, cur != NULL是考虑空链表的情况
while (cur != NULL && cur -> next != NULL)
{
if (cur -> next -> val == val)
{
ListNode* tmp = cur -> next;
cur -> next = cur -> next -> next;
delete tmp;
}
else cur = cur -> next; // 后移一位
}
return head;
}
};

方法2: 加入虚拟头节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// 创建虚拟头节点
ListNode* dummyHead = new ListNode(0);
dummyHead -> next = head;
// 上面的两行代码:创建虚拟头节点可以简写为:
// ListNode* dummyHead = new ListNode(0, head);
// 或者ListNode* dummyHead = new ListNode();
// dummyHead -> next = head;

// 统一方法删去值为val的节点
// 从虚拟头节点开始遍历, cur为目标节点的前一个节点
// 此时因为加入了虚拟头节点,因此链表不可能为空,因此不再需要考虑链表为空的判断条件:cur != NULL
ListNode* cur = dummyHead;
while (cur -> next != NULL)
{
if (cur -> next -> val == val)
{
ListNode* tmp = cur -> next;
cur -> next = cur -> next -> next;
delete tmp;
}
else cur = cur -> next;
}

head = dummyHead -> next;
delete dummyHead;
return head;
}
};

以方法2为主。

707.设计链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class MyLinkedList {
public:
// 记住struct的写法
struct LinkedList {
int val;
LinkedList* next;
LinkedList(int x): val(x), next(NULL) {};
};

// 初始化, 带下划线的变量表示类中的变量,而非局部变量
MyLinkedList() {
_dummyHead = new LinkedList(0); // 虚拟头节点
_size = 0;
}

int get(int index) {
if (index < 0 || index > ( _size - 1)) return -1;

LinkedList* cur = _dummyHead -> next;

while (index -- ) cur = cur -> next;

return cur -> val;
}

void addAtHead(int val) {
LinkedList* head = new LinkedList(val);
head -> next = _dummyHead -> next;
_dummyHead -> next = head;
_size ++ ;
}

void addAtTail(int val) {
LinkedList* tail = new LinkedList(val);

LinkedList* cur = _dummyHead;
// while循环中的条件不能是_size -- ,不然会破坏链表长度的准确性
while(cur -> next != NULL) cur = cur -> next;
cur -> next = tail;
_size ++ ;
}

void addAtIndex(int index, int val) {
if (index > _size || index < 0) return;

LinkedList* cur = _dummyHead;
LinkedList* node = new LinkedList(val);

while(index -- ) cur = cur -> next;

node -> next = cur -> next;
cur -> next = node;
_size ++ ;
}

void deleteAtIndex(int index) {
if (index < 0 || index >= _size) return;
LinkedList* cur = _dummyHead;
while (index -- ) cur = cur -> next;
LinkedList* tmp = cur -> next;
cur -> next = cur -> next -> next;
delete tmp;
_size -- ;
}

private:
LinkedList* _dummyHead;
int _size;
};

206.反转链表(常考)

是考察对基础数据结构操作非常好的一道题目。先掌握双指针解法,再掌握递归的解法。根据双指针代码写出递归代码。

双指针解法

leetcode206.png

具体解法:由于不需要让翻转以后的链表的头节点为空,因此当cur指向NULL时,遍历结束。因此循环为:while(cur),cur == NULL为遍历的终止条件。

更新cur和pre的方式:用临时节点将cur的下一个节点保存下来。否则一旦反转后cur的写一个节点就会丢失(反转后的链表的下一个节点是pre)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* cur = head;
ListNode* pre = NULL;

while (cur)
{
ListNode* tmp = cur -> next;
cur -> next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
};

递归解法1

按照双指针的思路写递归的代码。递归的代码更简短但更难懂。

具体解法:定义一个reverse函数,其中有两个参数,即reverse(cur, pre)

在主函数中调用reverse函数,需要传入两个参数cur和pre,前者对应于双指针解法中的head,后者对应于双指针解法中的null。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
// 仿照双指针解法,递归函数中需要传入两个参数:cur和pre
ListNode* reverse(ListNode* cur, ListNode* pre)
{
// 先检查递归的终止条件,同双指针解法
if (cur == NULL) return pre;

// 再执行递归的步骤
// 同双指针解法中tmp = cur -> next, cur -> next = pre, pre = cur, cur = tmp
ListNode* tmp = cur -> next;
cur -> next = pre;
return reverse(tmp, cur);
}

ListNode* reverseList(ListNode* head) {
// 双指针解法中初始时cur = head, pre = NULL
return reverse(head, NULL);
}
};

递归解法2

另一种递归解法,思路和递归解法1完全不同,我认为相比于递归解法1更好理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// 先判断终止条件是否成立
if (head == NULL) return NULL; // 空链表,返回空
if (head->next == NULL) return head; // 递归结束,返回反转后链表的head

// 执行递归流程
ListNode* last = reverseList(head->next); // 从第二个节点开始反转链表
// 将原来的头节点接到反转后链表的尾节点之后,反转后链表的尾节点是head->next
head->next->next = head;
head->next = NULL; // 尾节点指向空
return last; // 返回反转后链表的头节点
}
};

心得与备忘录

通用方法

  1. 插入虚拟头节点dummyHead,可以避免空链表并避免对头节点操作的特判
  2. 创建一个当前节点cur,对整个链表进行遍历(cur = cur->next),而不用链表中原本存在的节点对链表进行遍历
  3. NULL节点表示不存在的节点;虚拟节点实际上是存在的,其值为0,是人为创建的节点
  4. 递归时,需要先检查递归的终止条件,然后执行递归步骤

203.移除链表元素

  1. 想要删除一个节点,需要先用tmp存下它,然后再delete删去之。
  2. 以后写,尽量采用方法2,即加入虚拟头节点。
  3. cur -> next表示的是cur节点的next变量(即指针域),而cur -> val表示的是cur节点的val变量(即节点的值)。通过构造函数也可以给这两个变量直接赋值。
  4. 在方法1中,一定要加上判断条件cur != NULL,因为当链表为空时,while (cur -> next != NULL) 这个条件将尝试访问 NULL 指针的 next 成员,这将触发未定义行为,从而导致程序报错。在方法2中,则不需要加上判断条件cur != NULL,因为有虚拟头节点的存在,链表不可能为空,至少有一个节点(即虚拟头节点)。当然,在方法2中加上这个判断条件也不会影响程序的正常运行。

707.设计链表

  1. 想清楚一个极端情况:返回第0个节点的值,是否会出现空指针异常等错误。
  2. cur节点都赋值为_dummyHead
  3. 注意删除第n个节点时的内存释放问题
  4. 在第n个节点前增加或者删除一个节点,应该让cur指向第n-1个节点,cur->next指向第n个节点。
  5. 注意插入节点时先更新后面的边,再更新前面的边
  6. 只要传入参数index,就要记得对index进行判断,排除掉不需处理的情况。对get函数和deleteAtIndex函数,判断条件都是index < 0 || index > _size - 1,但对addAtIndex函数,判断条件是index < 0 || index > _size,因为index = _size表示将节点插入到链表的末尾。
  7. 别忘记_size ++ / _size —

206.反转链表

双指针解法

代码量少,思维量大!需要明确:cur和pre初始的取值;循环终止的条件;如何更新pre和cur。画图理解即可。

递归解法

递归解法1参照双指针解法写。这题推荐就用双指针解法,比较清楚明白,且空间复杂度为O(1),优于递归解法的空间复杂度O(n)。递归解法2相比于递归解法1更好理解。

链接

视频

https://www.bilibili.com/video/BV1QB4y1D7ep

https://www.bilibili.com/video/BV1tZ4y1q7XE

https://www.bilibili.com/video/BV1SL4y1N7mV/

文章

https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html

https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html

https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html

https://programmercarl.com/%E6%95%B0%E7%BB%84%E6%80%BB%E7%BB%93%E7%AF%87.html#%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80

题目

https://leetcode.com/problems/squares-of-a-sorted-array/

https://leetcode.com/problems/minimum-size-subarray-sum/

https://leetcode.com/problems/spiral-matrix-ii/

知识

  1. cpp中sort函数的用法:sort(a.begin(), a.end()),排序后的结果就存储在a中。
  2. vector<int> result(A.size(), 0);的意思是创建一个长度为A.size(),数值全部为0的vector。
  3. cpp中的问号表达式——条件运算符

    len = sub < len ? sub: len;表示若sub < len,则len = sub;否则len等于len,保持不变。

    len == INT32_MAX ? 0: len;表示若len等于INT32_MAX,则l表达式值为0,否则表达式值为len。

  4. INT32_MAX:这是一个在 C++ 中定义的常量,代表 32 位整数类型(即 int 类型)可以表示的最大值。
  5. 初始化一个二维vector,让其中的元素全部为0:vector<vector<int>> res(n, vector<int>(n, 0));,即初始化一个全部元素为0的一维数组,然后将其复制n遍。

初次尝试

977.有序数组的平方

暴力做法,先平方,再排序。双指针做法有点思路,但由于不知道如何创建一个值为0且长度与nums相同的vector,因此不能完全正确地写出代码。

209.长度最小的子数组

滑动窗口我听yxc讲过,但是已经完全忘了,直接看视频讲解,然后看文字版讲解。

暴力解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int len = INT32_MAX;
int sub = 0;
for (int i = 0; i < nums.size(); i ++ )
{
int s = 0;
for (int j = i; j < nums.size(); j ++ )
{
s += nums[j];
if (s >= target)
{
sub = j - i + 1;
len = len < sub ? len: sub;
break;
}
}
}

return len == INT32_MAX ? 0: len;
}
};

暴力做法超时了。还是需要滑动窗口。

59.螺旋矩阵II

yxc讲过这题,我印象中涉及到一个向量,撞墙了就拐弯,遇到自己之前走过的地方也拐弯,挺生动形象的,但我已经忘记怎么写了。

实现

977.有序数组的平方

取平方后,最大的元素一定在原数组的两边。故用左右指针,从数组的两边向中间推进。需要一个新的数组来存储结果,新的数组的下标由大到小来更新。

for+if写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
// 创建ans数组来存储答案
vector<int> ans(nums.size(), 0);

int n = nums.size() - 1;

// 由于每次循环都要比较两个数的平方的大小关系,因此将最后一个数放入ans时
// i和j都会等于该数的索引,因此要求i可以等于j
for (int i = 0, j = nums.size() - 1; i <= j; )
{
if (nums[i] * nums[i] <= nums[j] * nums[j])
{
ans[n -- ] = nums[j] * nums[j];
j -- ;
}
else
{
ans[n -- ] = nums[i] * nums[i];
i ++ ;
}
}
return ans;
}
};

for + while写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> res(nums.size(), 0);

int k = nums.size() - 1;

for (int l = 0, r = nums.size() - 1; l <= r; )
{
// 一定要记得加上l <= r的条件
while (l <= r && nums[l] * nums[l] >= nums[r] * nums[r])
{
res[k -- ] = nums[l] * nums[l];
l ++ ;
}
while (l <= r && nums[l] * nums[l] < nums[r] * nums[r])
{
res[k -- ] = nums[r] * nums[r];
r -- ;
}
}
return res;
}
};

while+while写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> ans(nums.size(), 0);

int k = nums.size() - 1;

int i = 0, j = nums.size() - 1;
while (i <= j)
{
while (i <= j && nums[i] * nums[i] <= nums[j] * nums[j])
{
ans[k -- ] = nums[j] * nums[j];
j -- ;
}

while (i <= j && nums[i] * nums[i] > nums[j] * nums[j])
{
ans[k -- ] = nums[i] * nums[i];
i ++ ;
}
}
return ans;
}
};

while + if写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> res(nums.size(), 0);

int k = nums.size() - 1;

int l = 0, r = k;

while (l <= r)
{
if (nums[l] * nums[l] <= nums[r] * nums[r])
{
res[k -- ] = nums[r] * nums[r];
r -- ;
}
else
{
res[k -- ] = nums[l] * nums[l];
l ++ ;
}
}
return res;
}
};

209.长度最小的子数组

其实核心思想也是双指针,只不过取两指针中间的集合像是一个正在滑动的窗口,因此也叫滑动窗口。用一个for循环替代暴力做法里的两个for循环。一个for循环中的循环变量j若表示滑动窗口的起始位置,则j在遍历的过程中,终止位置也需要去遍历,这与暴力做法无异。因此for循环中的循环变量j表示滑动窗口的终止位置,起始位置需要动态移动地去获得滑动窗口的精髓在于如何移动起始位置

若滑动窗口的起始位置和终止位置间的数的和>=target,那么起止位置可以向后移动,即窗口可以缩小,看缩小后的窗口是否还可以符合条件。若满足条件,则可更新滑动窗口。更新滑动窗口时,需要同时更新滑动窗口的起始位置和滑动窗口中元素和的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int len = INT32_MAX; // result
int i = 0; // i是滑动窗口的起始位置
int sub = 0; // 窗口长度
int sum = 0; // 窗口之和

// j是滑动窗口的终止位置
for (int j = 0; j < nums.size(); j ++ )
{
sum += nums[j]; // 将新的终止位置放到窗口的和中去

// 更新滑动窗口
while(sum >= target)
{
sub = j - i + 1;
len = len < sub ? len: sub;
sum -= nums[i];
i ++ ;
}
}
return len == INT32_MAX ? 0: len;
}
};

59.螺旋矩阵II

不涉及算法,是道模拟题。不易写对的原因是转圈的过程中需要处理的边界条件很多。

边界条件:正方形的4个边界点

循环不变量:
循环——不断转圈
不变量——对每条边的处理规则
对每条边的处理规则应该不变。按照左闭右开的规则处理正方形的每一条边,每条边只处理头节点,不处理尾节点

n * n的矩阵,需要转n / 2圈,若n为奇数,则中心那个值最后单独赋即可。每一圈的终止位置在上一圈的基础上-1。

示意图如下所示:
Snipaste_2024-01-26_06-26-17.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> ans(n, vector<int>(n, 0));

int startx = 0, starty = 0;
int offset = 1, count = 1;

int i, j;
int loop = n / 2;

while (loop -- )
{
for (j = starty; j < n - offset; j ++ )
ans[startx][j] = count ++ ;
for (i = startx; i < n - offset; i ++ )
ans[i][j] = count ++ ;
for (; j > starty; j -- )
ans[i][j] = count ++ ;
for (; i > startx; i -- )
ans[i][j] = count ++ ;

startx ++ ;
starty ++ ;
offset ++ ;
}

if (n % 2) ans[n / 2][n / 2] = count;
return ans;
}
};

心得与备忘录

977易错点

  1. 一定要新建一个数组ans,不能在原数组的基础上修改,否则会混乱。
  2. 一定要注意左指针和右指针可以相等,因为最后总要处理两个元素,两个指针最终总会移到一起去。否则当两个指针指向同一个数时,该数会被落下,不会被添加到答案数组中。
  3. 这道题在for/while循环内用if或者while都可以,但用while的时候需要记得加上判断条件:while(l <= r && ....),不加l <= r的条件会报错:run time error。

209心得

滑动窗口方法其实脱胎于暴力做法。要特别注意遍历的是窗口的终止位置。

更新窗口的起始位置时,同时需要更新窗口中元素之和。

不要以为for里放一个while就以为是O(n^2)啊, 主要是看每一个元素被操作的次数,每个元素在滑动窗后进来操作一次,出去操作一次,每个元素都是被操作两次,所以时间复杂度至多是 2 × n 也就是O(n)。

209易错点

一定要记得把滑动窗口的初始位置定义在循环之外。

一定要记得在移动窗口初始位置的同时改变窗口中元素的sum。

59易错点

  1. 注意每一条边都是左开右闭
  2. 注意画图理解
  3. 注意为n为奇数时单独给中心点赋值
  4. 注意如何定义一个二维所有元素为0的矩阵
  5. offsetx/y和startx/y不会出现在同一个式子中

备忘

看代码随想录的数组总结

数组总结

数组题目中:整数二分一道(704)。双指针三道(27, 977, 包括滑动窗口209),双指针题目的难度是递增的,27最简单,977稍难,209最难。模拟题一道:59。

从方法上来说,704和59都应该采用循环不变量的原则,27、977、209则都是双指针算法的应用。

引用总结文章:https://programmercarl.com/%E6%95%B0%E7%BB%84%E6%80%BB%E7%BB%93%E7%AF%87.html#%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80
中的一幅图片:

img

链接

文章

https://programmercarl.com/%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

https://programmercarl.com/%E5%89%8D%E5%BA%8F/%E5%85%B3%E4%BA%8E%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%EF%BC%8C%E4%BD%A0%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84%E9%83%BD%E5%9C%A8%E8%BF%99%E9%87%8C%EF%BC%81.html#%E7%A9%B6%E7%AB%9F%E4%BB%80%E4%B9%88%E6%98%AF%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6

https://programmercarl.com/%E5%89%8D%E5%BA%8F/%E5%85%B3%E4%BA%8E%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%EF%BC%8C%E5%8F%AF%E8%83%BD%E6%9C%89%E5%87%A0%E4%B8%AA%E7%96%91%E9%97%AE%EF%BC%9F.html

题目

https://leetcode.com/problems/binary-search/

https://leetcode.com/problems/remove-element/

知识

数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合。

注意:

  • 数组下标都是从0开始的

  • 数组内存空间的地址是连续的

  • 正是因为数组的在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,就难免要移动其他元素的地址

  • C++中,要注意vector和array的区别,vector的底层实现是array,严格来讲vector是容器,不是数组

  • 数组的元素是不能删的,只能覆盖

  • C++中二维数组在地址空间上是连续的(在现代系统上,二维数组中的每个int占用4个字节)

  • Java是没有指针的,同时也不对程序员暴露其元素的地址,寻址操作完全交给虚拟机。输出的值不是真正的地址,而是经过处理的数值

时间复杂度

时间复杂度是一个函数,它定性描述该算法的运行时间。

大O用来表示上界的,当用它作为算法的最坏情况运行时间的上界,就是对任意数据输入的运行时间的上界。有时业界也默认O代表的就是一般情况,而不是严格的上界。面试中说道算法的时间复杂度是多少指的都是一般情况。

数据用例的不一样,时间复杂度也是不同的。

我们说的时间复杂度都是省略常数项系数的,是因为一般情况下都是默认数据规模足够的大。

我们统一说 logn,也就是忽略底数的描述。

空间复杂度

是对一个算法在运行过程中占用内存空间大小的量度。

来看一下例子,什么时候的空间复杂度是$O(1)$呢,C++代码如下:

1
2
3
4
int j = 0;
for (int i = 0; i < n; i++) {
j++;
}

第一段代码可以看出,随着n的变化,所需开辟的内存空间并不会随着n的变化而变化。即此算法空间复杂度为一个常量,所以表示为大O(1)。

当消耗空间和输入参数n保持线性增长,这样的空间复杂度为O(n),来看一下这段C++代码

1
2
3
4
int* a = new int(n);
for (int i = 0; i < n; i++) {
a[i] = i;
}

随着n的增大,开辟的内存大小呈线性增长,即 O(n)。

递归的时候,会出现空间复杂度为logn的情况。

思路

第一想法

Leetcode 704 二分查找

这题应该是整数二分,虽然我在yxc的算法基础课里学过这题,但时隔几个月我已经彻底忘了(不管是原理还是实现),从头开始吧。

Leetcode 27 移除元素

试试暴力做法吧,双指针做法想不出来。根据yxc的经验,暴力做法成功后再想办法去优化。

看完代码随想录后的想法

Leetcode 704 二分查找

二分法的使用前提:数组为有序数组,且数组中无重复元素。满足这两个性质的题目可尝试二分法。

二分法中区间的定义有两种:左闭右闭和左闭右开。每一次边界的处理都要坚持根据区间的定义来操作

Leetcode 27 移除元素

暴力做法:遍历数组->找到需要移除的元素->将该元素后面的所有元素都前移一位->索引前移一位,数组长度减1

双指针法(快慢指针法): 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

实现

Leetcode 704 二分查找

cpp中的vector中求数组的长度没有len函数,应该用size函数。

cpp中两个整数的做除法如果得到的结果变量类型为整数,则是向下取整的。

cpp中的vector是动态数组,要先向用push_back向其中添加元素,然后才能通过索引来访问元素。

左闭右闭和左闭右开的写法中,需要注意right初始值的选取的不同(由于一种写法的右边界可以取到,另一种写法的右边界取不到)。还需要注意分成三类讨论,即target > nums[mid], target < nums[mid]和target == nums[mid]。这样就可以避免处理大于等于和小于等于的情况。

返回总是返回mid,不要尝试返回l或者r,可能会遇到边界问题。

用(l + r) >> 1比(l + r) / 2要更快一点。

建议采用l + (r - l) / 2代替(r + l) / 2,前者可以防止(r + l)溢出整数的范围。

时间复杂度:O(log n)
空间复杂度:O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 左闭右闭写法
class Solution {
public:
int search(vector<int>& nums, int target) {
// 左闭右闭,因此要求左右边界均可取到,因此r的值要与右边界的索引相同
int l = 0, r = nums.size() - 1;

// 当left==right,区间[left, right]依然有效,所以用 <=
while (l <= r)
{
int mid = (l + r) / 2; // (l + r) >> 1速度更快
// 分三类情况讨论
// 因为区间是右闭的,所以r不可能取为mid,最大为mid - 1
if (target < nums[mid]) r = mid - 1;
// 因为区间是左闭的,所以l不可能取为mid,最小为mid + 1
else if (target > nums[mid]) l = mid + 1;
// return l/r都是错误的,可以通过模拟一个输入知道错误原因
else return mid;
}
return -1;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 左闭右开写法
class Solution {
public:
int search(vector<int>& nums, int target) {
// 左闭右开,因此target不能取为右边界的值,要保证区间完全覆盖住target,因此r的值要比右边界的索引大1
int l = 0, r = nums.size();

// 右边界取不到,因此是l < r
while (l < r)
{
int mid = (l + r) / 2;
// 因为区间是左闭的,所以l不可能取为mid,最小为mid + 1
if (target > nums[mid]) l = mid + 1;
// 因为区间是右开的,所以r可以取为mid
else if (target < nums[mid]) r = mid;
// return l是错误的,可以通过模拟一个输入知道错误原因
else return mid;
}
return -1;
}
};

Leetcode 27 移除元素

暴力做法

若不前移i,则若数组中出现连续的两个val时,结果会发生错误,不能完全移除数组中所有的val。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size = nums.size();

for (int i = 0; i < size; i ++ )
{
// 遍历数组,找到需要移除的元素
if (nums[i] == val)
{
// 将该元素后面的所有元素都前移一位,覆盖掉需要移除的元素
for (int j = i + 1; j < size; j ++ )
nums[j - 1] = nums[j];
// 索引前移一位,数组长度减1
i -- ;
size -- ;
}
}
return size;
}
};

时间复杂度:O(n^2)
空间复杂度:O(1)

快慢双指针做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
// 快指针用于遍历所有元素、慢指针用于记录更新后数组的下标
int slow = 0;

for (int fast = 0; fast < nums.size(); fast ++ )
{
if (nums[fast] != val)
nums[slow ++ ] = nums[fast];
}
return slow;
}
};

时间复杂度:O(n)
空间复杂度:O(1)

相向双指针做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 相向双指针方法
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int l = 0, r = nums.size() - 1;

while (l <= r)
{
// 跳过所有不需要移除的元素,剩下需要移除的元素
while (l <= r && nums[l] != val) l ++ ;
// 跳过所有需要移除的元素,剩下不需要移除的元素
while (l <= r && nums[r] == val) r -- ;

// 将右边不需要移除的元素覆盖掉左边需要移除的元素(交换左右两边的元素)
if (l < r) nums[l ++ ] = nums[r -- ];
}
// 返回左边的最后一个值的索引
return l;
}
};

时间复杂度:O(n)
空间复杂度:O(1)

注意:while (l <= r && nums[l] != val)和while (l <= r && nums[r] == val)中的两个判断条件不可以写反,否则会出现Runtime Error。这是因为短路原则,最好先进行边界检查,再访问数组。

逻辑:数组的左边放等于val的元素,因此需要跳过所有不等于val的元素;数组的右边放不等于val的元素,因此需要跳过所有等于val的元素。交换数组的左右两边,让数组的左边放不等于val的元素,数组的右边放等于val的元素,然后输出数组左边的最后一个值的索引。

相向双指针方法的基本过程我大致理解了,但还不理解其的细节和应用。

心得与备忘录

Leetcode 704 二分查找

我认为代码随想录的做法比yxc的讲解更加清晰。清楚地归纳总结出了左闭右闭和左闭右开的写法,并根据选择区间的开闭性质清晰地写出了代码。同时,分成三类讨论,避免了处理大于等于和小于等于的情况。

还没有做35和34,等到二刷来做。

Leetcode 27 移除元素

相向双指针方法的理解有待加深。

Django项目总结

项目介绍

Game based on Django framework, developed by yifanChen

Website

https://app5894.acapp.acwing.com.cn/

Repository

https://github.com/yfchenkeepgoing/Django_app

Gameplay

  1. Right-click to move
  2. Left-click plus ‘Q’ for the skill: Fireball, with a cooldown of 3 seconds
  3. Left-click plus ‘F’ for the skill: Flash, with a cooldown of 5 seconds
  4. In multiplayer mode, the winning player gains 10 points, and the losing player loses 5 points

Technology Stack

  1. Frontend: JQuery
  2. Backend: Django
  3. Database: SQLite, Redis
  4. Network Protocols: HTTPS, WSS
  5. RPC: Thrift
  6. Authorization Protocol: OAuth
  7. Authentication: JWT

Features

  1. Complete menu interface and game interface
  2. Frontend and backend separation, with AcApp and Web versions on the frontend
  3. Deployed with Nginx to interface with the AcApp
  4. Comprehensive account system, username and password login, and one-click login with AcWing & GitHub OAuth
  5. Online multiplayer and chat system implemented via WSS protocol
  6. Matchmaking system implemented through Thrift service
  7. Cross-origin issues resolved through Rest Framework and JWT authentication, achieving complete frontend-backend separation
  8. The ranking board displays the top ten players ranked by score

Django项目的框架

一个Django项目,大致由以下六部分组成:

  1. templates目录:管理html文件
  2. urls目录:管理路由,即链接与函数的对应关系,即每个链接交给哪个函数处理的信息,存储在urls文件夹中。
  3. views目录:视图,管理http函数(函数实现在views目录中)
  4. models目录:管理数据库数据。
  5. consumers目录:管理websocket函数(views管理http函数,即负责单向连接的函数;consumers管理双向连接的函数,比如联机对战和聊天的逻辑)
  6. static目录:管理静态文件,比如:
  • css文件:对象的格式(网页每部分的格式),比如位置、长宽、颜色、背景、字体大小等
  • js:对象的逻辑(项目的核心),比如对象的创建与销毁、事件函数、移动、变色等,渲染html也会在js部分(前端)
  • image:图片
  • audio:声音

urls文件夹、views文件夹、models文件夹和consumers文件夹都由python文件组成,如果想通过import将文件导入,则需要在文件夹下创建 __init__.py文件(即索引文件,内容为空即可)。在所有python文件夹中都需要创建这样的函数,否则在import时就无法进去,会报错。

项目核心逻辑

本项目由于是一个小游戏,因此前端的js代码占比较大。游戏单人模式的实现纯粹由前端完成,我用js代码实现了一个简易的游戏引擎。游戏的单人模式不需要前后端交互。

需要前后端交互的部分有:

  1. 注册与登录:涉及到写入、读取、查询数据库
  2. acwing和GitHub一键登录:即OAuth授权登录
  3. 实现联机对战和聊天系统:涉及到在多名玩家之间同步五个事件(函数):create_player, move_to, shoot_fireball, attack, message。前四个用于实现联机对战,最后一个用于实现聊天系统。
  4. Rest Framework与JWT身份验证:是对第一点和第二点的补充。
  • JWT(json web token)相比于django自带的登录验证方式(通过session_id)安全性更高。
  • 方便实现真正意义上的前后端分离,即后端只需要提供实现好的api给前端调用,而Rest Framework为这些api的调试提供了可视化界面。
  • JWT可以解决跨域产生的问题。
  • 可以使用http的四大类请求方法:get, post, delete, put,而不像之前仅仅使用get方法,这又提高了令牌的安全性。

纯后端的部分只有匹配系统的实现。匹配系统的实现涉及到两个后端(即django web server和match system)之间的通信,匹配系统本身涉及到多线程和锁等方面的知识。

我认为本项目的重点主要在于前后端交互的部分,前后端交互其实有一套统一的范式:先在views中实现后端的函数;然后在urls中为后端的函数定义url链接;再在前端代码中利用ajax技术通过url获得后端传来的数据(前后端一般以json的格式传递数据);最后通过前端使用或展示数据。如果给用户设计了一套通过点击鼠标或者使用键盘向后端请求数据的模式,那么还需要在前端进行按键索引和绑定监听函数等操作。

改进项目

  1. 使用功能更强大的前端框架,比如Vue或者React,取代简单的JQuey。
  2. 使用更多种类型的数据库,比如关系型数据库MySQL,文档数据库MongoDB,对象存储服务等等。
  3. 使用另外几种实现前后端通信的技术取代ajax,比如Fetch API,Server-Sent Events (SSE),GraphQL和WebRTC,以提高系统的性能。
  4. 学习并尝试使用Springboot框架和Go语言的后端框架。
  5. 使用k8s来自动化部署、扩展和管理容器化应用程序。

漫谈

后端的主要分类

算法与推荐系统、开发各种服务、数据库

对于实现客户端与服务器之间的通信功能的技术的选择

除了AJAX,现代Web开发中还有几种其他技术可以实现类似的客户端与服务器之间的通信功能。一些技术在特定场景下比AJAX更高效。以下是一些常用的技术:

  1. Fetch API: Fetch API提供了一种更简洁和强大的方式来发起网络请求。它基于Promise,使得写异步代码更加简洁和直观。Fetch API是AJAX的现代替代方案,被广泛支持和使用。
  2. WebSocket: WebSocket提供了全双工通信渠道,使得客户端和服务器可以实时、双向地通信。它非常适用于需要频繁和即时数据更新的应用,如在线游戏、聊天应用和实时数据流。
  3. Server-Sent Events (SSE): SSE允许服务器主动向客户端发送新数据。它是单向的,只有服务器可以发送消息给客户端。SSE适合实现如股票行情、新闻订阅等场景,其中服务器定期推送更新。
  4. GraphQL: GraphQL是一种数据查询和操作语言,它允许客户端以更灵活的方式请求数据。与REST相比,GraphQL可以减少数据传输量,因为它允许客户端精确指定所需的数据。
  5. WebRTC: WebRTC(Web Real-Time Communication)允许在不需要安装插件的情况下在Web应用中实现实时通信功能,常用于视频聊天和点对点数据共享。

每种技术都有其特定的应用场景和优势。选择哪一种技术取决于应用的具体需求:

  • 对于简单的异步数据请求,AJAX和Fetch API都是不错的选择。
  • 对于需要高实时性的应用,WebSocket或WebRTC可能更合适。
  • 对于服务器主动推送数据的场景,SSE是一个好的选择。
  • 对于需要更灵活数据交互的场景,GraphQL提供了更好的解决方案。

在性能方面,WebSocket和WebRTC通常在需要频繁和快速通信的场景下比AJAX更高效,因为它们建立了持久的连接,而不是像AJAX那样为每个请求创建新的连接。

如何使用MySQL,MongoDB,对象存储服务等外置的数据库(它们不像sqlite,不集成于后端框架内)

  • 租一台数据库服务器
  • 在框架中负责数据库的部分配置数据库服务器的连接/登录
  • 下载该框架下使用该种数据库的包
  • 在框架中负责数据库的部分调用包中的api完成对数据库的各种操作,比如读、写、删除等。

在 Django 中,通常不需要直接使用 SQL 语句来操作 MySQL 数据库,因为 Django 提供了一个强大的 ORM(对象关系映射)系统,允许你通过 Python 代码来操作数据库。这意味着你可以使用 Django 的模型和查询 API 来查询和操作数据,而无需直接编写 SQL 语句。

Django 本身不直接支持 MongoDB,因为它是一个 NoSQL 数据库,与 Django 的 ORM 系统设计理念不同。如果你想在 Django 项目中使用 MongoDB,可以采取以下方法:

  • 使用 Djongo: Djongo 是一个将 Django ORM 映射到 MongoDB 的工具。通过 Djongo,你可以在一定程度上使用 Django ORM 的风格来操作 MongoDB。
  • 使用 PyMongo: PyMongo 是 MongoDB 的官方 Python 驱动程序。使用 PyMongo,你可以直接以 Python 代码与 MongoDB 交互,但这意味着你需要手动编写数据库操作逻辑,而不是使用 Django ORM。

对于对象存储服务(如 Amazon S3),通常使用的是 RESTful API 而非传统的数据库查询语言。在 Django 项目中使用对象存储通常涉及以下步骤:

  • 选择合适的库: 例如,对于 Amazon S3,你可以使用 boto3,这是 AWS 的官方 Python SDK。
  • 进行配置和认证: 通常需要设置认证凭据和相关配置。
  • 使用 SDK 提供的 API: 使用 SDK 提供的方法来上传、下载、列出文件等。

JWT可以存放在内存、local storage和cookie中,这三个存放地各自有优缺点

Cookie:
优点:自动由浏览器管理,并且可以设置为HttpOnly(无法通过JavaScript访问,增加安全性),支持跨域访问控制(SameSite属性)。
缺点:容易受到CSRF(跨站请求伪造)攻击,尽管可以通过适当的防范措施(如使用CSRF Token)来缓解。

LocalStorage:
优点:易于使用,可以在浏览器会话间持久存储。
缺点:容易受到XSS(跨站脚本攻击)攻击,因为恶意脚本可以访问LocalStorage并窃取令牌。

内存(JavaScript变量):
优点:在浏览器关闭时自动清除,不容易受到XSS攻击(只要不将令牌暴露给恶意脚本)。
缺点:不持久,用户刷新页面或关闭浏览器时会丢失,可能需要重新认证。

最佳实践:
安全性考虑:通常推荐将JWT存储在HttpOnly的Cookie中,因为这样可以防止JavaScript访问令牌,从而减少XSS攻击的风险。

CSRF防范:如果使用Cookie,应结合CSRF保护机制。

易用性:如果需要在会话间持久保存用户的登录状态,LocalStorage可能更为方便。但是,务必注意XSS攻击的风险,并采取适当的安全措施。

短期使用:对于需要高安全性且可接受在会话结束后用户需要重新登录的场景,可以考虑仅将JWT存储在内存中。

在实践中,选择哪种方式取决于应用的安全需求、用户体验需求以及开发者对相关安全风险的管理能力。在处理任何形式的认证信息时,安全总是首要考虑的因素。在本项目中,出于安全性和短期使用的考量,我将JWT存储在了内存,即js变量中。如果没有明确地将JWT存储在Local Storage或Cookie中,那么它们就是存储在内存中。这意味着令牌只在当前页面会话中有效,一旦页面被关闭或刷新,令牌就会丢失。