LeetCode训练记录

太久没用C++了，记录一下大概用法

因为蓝桥杯准备的是Python，C++现在已经很久没用了

难绷的是，蓝桥杯Python组还打水漂了，太幽默了

不过问题不大，接着搞C++的就行

LeetCode代码运行框架

力扣是写函数的，不用写输入输出，一定程度上比较方便

但之前没写过力扣，写过的全是牛客、洛谷这种从0开始写完整代码的，没有只写函数的

再加上我很久没有练习C++了，因此在此总结力扣代码的运行框架


力扣代码提交

以“两数之和”题目（力扣题库第一题）为例，你需要提交的是一个Solution类中的twoSum函数，参数和返回值类型已经确定：

1
2
3
4
5
6
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
    }
};

因此，用集成环境需要写一个Solution类，完成需要实现的twoSum函数，再写一个Run函数，最后在main函数中调用即可

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
//万能头文件，如果MinGW版本低可能找不到这个文件
//可以去 https://winlibs.com 下载新的MinGW
#include <bits/stdc++.h>

using namespace std;

//Solution类
class Solution
{
public:
    //需要实现的函数，此处用暴力做法
    vector<int> twoSum(vector<int> &nums, int target)
    {
        vector<int> result;
        for (int i = 0; i < nums.size(); i++)
        {
            for (int j = i + 1; j < nums.size(); j++)
            {
                if (nums[i] + nums[j] == target)
                {
                    result.push_back(i);
                    result.push_back(j);
                    return result;
                }
            }
        }
        return result;
    }
    
	//Run函数
    void Run(vector<int> &nums, int target)
    {
        vector<int> tmp = this->twoSum(nums, target);
        cout << "[" << tmp[0] << "," << tmp[1] << "]" << endl;
    }
};

int main()
{
    //main函数里初始化一个对象
    Solution ans;
    //初始化需要的参数，省略了输入函数
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    //调用Run函数得到结果
    ans.Run(nums, target);
}

大概的框架就是这样

异或运算寻找只出现一次的数

只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

1 <= nums.length <= 3 * 104

-3 * 104 <= nums[i] <= 3 * 104

除了某个元素只出现一次以外，其余每个元素均出现两次。


这个题刚看到就想着用桶排序的思路，即一个萝卜一个坑，可以找到那个唯一的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 桶排序思想
    int singleNumber(vector<int> &nums)
    {
        const int defaultSize = 1e5;
        int lst[defaultSize] = {0};
        int delta = 3e4;
        for (int i = 0; i < nums.size(); i++)
        {
            lst[nums[i] + delta]++;
        }
        for (int i = 0; i < defaultSize; i++)
        {
            if (lst[i] == 1)
            {
                return i - delta;
            }
        }
        return 0;
    }

很快就能写完，但是用时太长了

于是就准备借鉴一下高手做法：

高手做法用的是异或操作^

1
2
3
4
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

故0与A异或，结果为A

A与A异或，结果为0

故如果有重复的数，异或结果就为0

比如一个数组为[4,1,2,1,2]，写成二进制就是[1000,0001,0010,0001,0010]

因为异或有交换律，所以最后异或的结果就是(1^1)^(2^2)^4=0^0^4=4

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 高手做法：异或
    int singleNumber(vector<int> &nums)
    {
        int result = 0;
        // // C++11以后的版本可以像Python一样写
        // // Python里是 for num in nums:
        // // C++里是 for(int num : nums)
        // for (int num : nums)
        // {
        //     result = result ^ num;
        // }
        for (int i = 0; i < nums.size(); i++)
        {
            result = result ^ nums[i];
        }
        return result;
    }

此外，此题还能用排序的方法，然后遍历，就能找到唯一的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 排序
    int singleNumber(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());
        // 注意考虑数组大小问题
        if (nums.size() == 1 || (nums.size() > 1 && nums[0] != nums[1]))
        {
            return nums[0];
        }
        else if (nums.size() > 1 && nums[nums.size() - 1] != nums[nums.size() - 2])
        {
            return nums[nums.size() - 1];
        }
        for (int i = 1; i < nums.size() - 1; i++)
        {
            if (nums[i] != nums[i - 1] && nums[i] != nums[i + 1])
            {
                return nums[i];
            }
        }
        return 0;
    }

只不过这个做法需要考虑下标的正确用法，要讨论“数组长度只有1”、“不同的数在开头”、“不同的数在最后”、“不同的数在中间”这几种情况

因为涉及到nums.size() - 1，nums.size() - 2这样的运算，所以需要考虑nums.size() > 1

因为涉及到nums[0] != nums[1]，所以也需要考虑nums.size() > 1

就这两点错误，导致一开始没完全做对

bing给我改的新代码如下：

下面是一个更简洁的版本：

1
2
3
4
5
6
7
8
9
>int singleNumber(vector<int> &nums) {
   sort(nums.begin(), nums.end());
   for (int i = 0; i < nums.size(); i += 2) {
       if (i + 1 == nums.size() || nums[i] != nums[i + 1]) {
           return nums[i];
       }
   }
   return 0;
>}

在这个版本中，我们首先对数组进行排序。然后，我们每次跳过两个元素进行遍历。因为如果一个数字有两个副本，那么它们现在应该是相邻的。如果我们发现nums[i]不等于nums[i + 1]，那么nums[i]就是只出现一次的数字。如果我们遍历完整个数组都没有找到只出现一次的数字，那么我们返回0。

这样好看多了，也不需要讨论那么多

Sad for programmers

原地修改vector时size()返回值会变

很弱智的问题，但就是出错了，因此记录

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

确实很容易的问题，直接用vector的erase就能解决

遍历数组，如果是0就直接erase，最后push_back对应个数的0就行

但是这里我出错了，错误代码如下：

1
2
3
4
5
//出错部分
for (int i = 0; i < OriginSize - nums.size(); i++)
{
    nums.push_back(0);
}

很明显的错误，但是做得少，因为原地操作数组经验太少

数组变动，就会导致nums.size()变动，循环次数就变动了，因此错误


还有一个容易错误的地方：

1
2
3
4
5
6
7
8
for (int i = 0; i < nums.size(); i++)
{
    if (nums[i] == 0)
    {
        nums.erase(nums.begin() + i);
        i--;	//i--如果漏了，就会导致连续两个0的情况出错
    }
}

i--如果漏了，就会导致连续两个0的情况出错

完整函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// STL原地修改，容易错
void moveZeroes(vector<int> &nums)
{
    int OriginSize = nums.size();
    for (int i = 0; i < nums.size(); i++)
    {
        if (nums[i] == 0)
        {
            nums.erase(nums.begin() + i);
            i--;	//原地删完i再变回去
        }
    }
    int Sizenow = nums.size();	//提前记下所需个数，保证循环次数不变
    for (int i = 0; i < OriginSize - Sizenow; i++)
    {
        nums.push_back(0);
    }
}


还是看看远方的双指针做法吧

思路简单，i一定指向0的位置，j一定指向非0位置，而且一定是后面的非0数换前面的0（即i<j）

容易出错的点就是[1,0,0,2]这样的情况

i和j都指向对应位置，但是i比j大，不能交换，此时需要更新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
// 双指针
void moveZeroes(vector<int> &nums)
{
    for (int i = 0, j = 0; i < nums.size() && j < nums.size();)
    {
        // 保证i指向0
        if (nums[i] != 0)
        {
            i++;
            continue;
        }
        // 保证j指向非0
        if (nums[j] == 0)
        {
            j++;
            continue;
        }
        // 保证后面的非0数换前面的0
        if (i < j)
        {
            nums[i] = nums[j];
            nums[j] = 0;
            i++;
            j++;
        }
        // 如果此时i和j都指向对应的数，但是i比j大，就更新j
        // 比如[1,0,0,2]这样的情况
        else
        {
            j++;
        }
    }
}

哈希表解决两数之和

两数之和是力扣题库第一题，我现阶段也只能想到暴力解法，因此在此记录高手做法

而且这个高手做法提供了一个很好的思路，利用遍历过的已知信息

暴力解法还是很容易的，遍历就完了，就是太蠢了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 暴力做法
vector<int> twoSum(vector<int> &nums, int target)
{
    vector<int> result;
    for (int i = 0; i < nums.size(); i++)
    {
        for (int j = i + 1; j < nums.size(); j++)
        {
            if (nums[i] + nums[j] == target)
            {
                result.push_back(i);
                result.push_back(j);
                return result;
            }
        }
    }
    return result;
}

来看看高手方法：哈希表

大致思路是利用键值对map，遍历数组

每次查找target - nums[i]这个键有没有存入map，如果有，那答案就是他了

如果没有，就把nums[i]这个键和下标存入这个map

因为题目保证一定有解，所以这个方法能求出正确结果

这个方法的好处是利用了已知信息（没有成功配对的数的下标是已知的），可以通过O(1)的复杂度求出target - nums[i]的坐标

而暴力做法的双重循环，是通过O(n)的时间复杂度寻找是否存在target - nums[i]这个数，因此效率低下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 哈希表高手做法
vector<int> twoSum(vector<int> &nums, int target)
{
    vector<int> result;
    map<int, int> Mymap;
    for (int i = 0; i < nums.size(); i++)
    {
        if (Mymap.find(target - nums[i]) == Mymap.end())
        {
            Mymap[nums[i]] = i;
        }
        else
        {
            result.push_back(i);
            result.push_back(Mymap[target - nums[i]]);
            return result;
        }
    }
    return result;
}


这个题还有一个高手做法：先排序，再用双指针两边缩进，直到找到解

可以参考相向双指针解决两数之和

但有一点需要注意：排序以后数组下标会改变，需要存下原来对应坐标的位置

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
// 双指针
vector<int> twoSum(vector<int> &nums, int target)
{
    vector<int> result;
    // 存下原数组的拷贝
    vector<int> tmp = nums;
	// 排序
    sort(nums.begin(), nums.end());
    for (int i = 0, j = nums.size() - 1; i < nums.size(), j >= 0;)
    {
        if (nums[i] + nums[j] > target)
        {
            j--;
            continue;
        }
        if (nums[i] + nums[j] < target)
        {
            i++;
            continue;
        }
        if (nums[i] + nums[j] == target && i != j)
        {
            for (int k = 0; k < tmp.size(); k++)
            {
                if (nums[i] == tmp[k])
                {
                    result.push_back(k);
                    continue;
                }
                if (nums[j] == tmp[k])
                {
                    result.push_back(k);
                    continue;
                }
            }
            return result;
        }
    }
    return result;
}

各种数据类型上下限

弱质题：整数反转

需要考虑int会溢出，上下限为负21亿多到正21亿多

有两个宏可以用：INT_MAX（0x7fffffff即2147483647）和INT_MIN（-0x7fffffff - 1即-2147483648）

同理，long long的上限是INT64_MAX，下限是INT64_MIN

太久没写这样的代码了，写起来跟弱质一样

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
// 低手算法，不要这样写
int reverse(int x)
{
    bool ifnegative = false;
    if (x < 0)
    {
        ifnegative = true;
    }
    x = abs(x);
    //这里一开始还写错了
    //用的 vector<int> 导致result_Array里的值直接超出范围
    //但是最后求和result的时候看不出来，因为result_Array的值自动转换到范围之内了
    //挺低能的错误
    vector<long long> result_Array;
    while (x != 0)
    {
        result_Array.push_back(x % 10);
        x /= 10;
    }
    long long result = 0;
    for (int i = 0; i < result_Array.size(); i++)
    {
        for (int j = i; j < result_Array.size() - 1; j++)
        {
            result_Array[i] *= 10;
        }
        result += result_Array[i];
        if (result > INT_MAX || result < INT_MIN)
        {
            return 0;
        }
    }
    if (ifnegative)
    {
        result *= -1;
    }
    return result;
}

难绷，真的手生了，怎么会想新开一个数组写啊

看看正常人是怎么写代码的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 正常人写法
int reverse(int x)
{
    long long result = 0; // 使用 long long 类型来防止溢出
    while (x != 0)
    {
        int digit = x % 10;
        result = result * 10 + digit;
        if (result > INT_MAX || result < INT_MIN)
        {             // 检查是否溢出
            return 0; // 如果溢出，返回 0
        }
        x /= 10;
    }
    return result;
}

刚好总结一下C++中各种数据类型的范围，参考数据类型范围 | Microsoft Learn

类型名称 字节 其他名称 值的范围
int 4 signed -2,147,483,648 到 2,147,483,647
unsigned int 4 unsigned 0 到 4,294,967,295
bool 1 无 false 或 true
char 1 无 -128 到 127
signed char 1 无 -128 到 127
unsigned char 1 无 0 到 255
short 2 short int，signed short int -32,768 到 32,767
unsigned short 2 unsigned short int 0 到 65,535
long 4 long int，signed long int -2,147,483,648 到 2,147,483,647
unsigned long 4 unsigned long int 0 到 4,294,967,295
long long 8 无 -9,223,372,036,854,775,808 到 9,223,372,036,854,775,807
unsigned long long 8 无 0 到 18,446,744,073,709,551,615
float 4 无 3.4E +/- 38（7 位数）
double 8 无 1.7E +/- 308（15 位数）
long double 与 double 相同 无 与 double 相同


有时也需要注意long long的上下限（19位数），上限是INT64_MAX，下限是INT64_MIN

比如20000000000000000000这个数就超过了long long的上界（有20位）

string::earse()函数

太久没用忘了，具体用法如下：

在 C++ 中，string 类的 erase 函数用于删除字符串中的一部分。以下是 erase 函数的一些常见用法：

s.erase(pos, n)：删除从 pos 开始的 n 个字符。例如，s.erase(0, 1) 就是删除第一个字符。

1
2
3
>string s = "hello";
>s.erase(0, 1);  // 删除第一个字符
>cout << s << endl;  // 输出："ello"

s.erase(pos)：删除 pos 处的一个字符。pos 是一个 string 类型的迭代器。

1
2
3
>string s = "hello";
>s.erase(s.begin());  // 删除第一个字符
>cout << s << endl;  // 输出："ello"

s.erase(first, last)：删除从 first 到 last 之间的字符

1
2
3
>string s = "hello";
>s.erase(s.begin(), s.begin() + 3);  // 删除前三个字符
>cout << s << endl;  // 输出："lo"

也就是说，erase函数里的参数有两种类型：迭代器类型和下标(int)类型

如果参数是迭代器那么就只会删除一个字符，如果是下标，如果不指定删除字符个数，默认删除下标后的全部

总结如下，注意s.erase(s.end()) 会导致未定义行为，在我的机子上体现的就是清空字符串

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
string s = "0123456789";
// 迭代器情况，只删一个字符
// 删除0
s.erase(s.begin());
cout << s << endl;

s = "0123456789";
// 删除1
s.erase(s.begin() + 1);
cout << s << endl;

s = "0123456789";
// s.end() 返回的是一个指向字符串末尾的迭代器
// s.erase(s.end()) 会导致未定义行为
// 删除最后一个元素正确写法
s.erase(s.end() - 1);
cout << s << endl;

// 下标情况
s = "0123456789";
// 删除1以及之后的全部
s.erase(1);
cout << s << endl;

s = "0123456789";
// 指定删除字符个数
s.erase(1, 1); // 删除下标为1的1个字符
cout << s << endl;

s = "0123456789";
// 指定删除字符个数
s.erase(0, 2); // 删除下标为0的连续两个字符
cout << s << endl;

数值类型转换为string

这也是很久没用忘记的内容了，使用std::to_string()函数

比如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int num = 123;
std::string str = std::to_string(num);
// 现在，str 是 "123"

double d = 3.14;
std::string str1 = std::to_string(d);
// 现在，str1 是 "3.140000"

float f = 2.71f;
std::string str2 = std::to_string(f);
// 现在，str2 是 "2.710000"

long l = 1000000;
std::string str3 = std::to_string(l);
// 现在，str3 是 "1000000"

注意，对于浮点数，默认是小数点后六位，即使超过了6位也会截断6位存入字符串

STL中stack的基本用法

以前都是自己写栈类的，这次看看stack的基本语法，不用手写了

在C++中，标准模板库（STL）提供了一个名为 std::stack 的栈容器适配器。栈是一种后进先出（LIFO）的数据结构，只允许在栈顶添加或删除元素。

以下是一些基本的 std::stack 操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
>#include <stack> // 引入栈的头文件

>int main() {
   std::stack<int> s; // 创建一个空的 int 类型的栈

   s.push(1); // 将元素 1 压入栈顶
   s.push(2); // 将元素 2 压入栈顶
   s.push(3); // 将元素 3 压入栈顶

   // 现在，栈的内容是：3, 2, 1

   int top = s.top(); // 获取栈顶元素，此时 top 的值是 3

   s.pop(); // 弹出栈顶元素

   // 现在，栈的内容是：2, 1

   bool isEmpty = s.empty(); // 检查栈是否为空，此时 isEmpty 的值是 false

   int size = s.size(); // 获取栈的大小，此时 size 的值是 2

   return 0;
>}

set解决环形链表

环形链表是一个比较简单的题，可以利用map或者unordered_map里键的唯一性来解决

但既然涉及到“唯一性”，我想不得不提到另一个只用到“唯一性”的工具：集合set

之前也没用过set，故在此记录用法

在C++中，标准模板库（STL）提供了一个名为 std::set 的容器。std::set 是一种关联容器，它包含的元素都是唯一的。std::set 内部通常实现为红黑树，元素会按照特定的排序准则插入，所以你可以很快地通过键值进行检索。

以下是一些基本的 std::set 操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
>#include <set> // 引入 set 的头文件

>int main() {
   std::set<int> s; // 创建一个空的 int 类型的 set

   s.insert(1); // 将元素 1 插入 set
   s.insert(2); // 将元素 2 插入 set
   s.insert(3); // 将元素 3 插入 set

   // 现在，set 的内容是：1, 2, 3

   s.erase(2); // 删除元素 2

   // 现在，set 的内容是：1, 3

   bool exists = s.count(3); // 检查元素 3 是否存在，此时 exists 的值是 true

   int size = s.size(); // 获取 set 的大小，此时 size 的值是 2

   return 0;
>}

不过感觉map比起set更灵活一些？毕竟是键值对，比如map里可以直接通过键来访问或修改值，比如：

1
2
3
4
5
6
7
8
9
10
map<string, int> Mymap;
//插入元素
Mymap["WHITE ALBUM 2"] = 1;
Mymap["サクラノ詩"] = 1;
Mymap["STEINS;GATE"] = 2;
Mymap["Ever17"] = 3;
//查找指定键对应的值
cout << Mymap["WHITE ALBUM 2"] << endl;
//更新元素
Mymap["WHITE ALBUM 2"] = 0;

std::set 只包含键，而不包含值，所以不能像 std::map 那样通过键来访问或修改值。

在 std::set 中，你只能使用 insert 方法来添加元素。例如：

1
2
>std::set<std::string> mySet;
>mySet.insert("test");

总结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
// 可以直接给set赋初值
set<int> s = {1, 2, 3};
// 插入元素
s.insert(4);
// 查找元素，有两种方法
// count函数，返回一个布尔值，用于检查存在与否
bool ifexist = s.count(1);
// find函数，返回一个迭代器（指针），指向 set 中等于给定值的元素
// 如果找到了，就返回对应元素的指针
// 如果没找到，返回 end()
auto it = s.find(1);
if (it != s.end())
{
    cout << "找到元素 " << *it << endl;
}
else
{
    cout << "未找到元素" << endl;
}
// 删除元素，返回值就是是否删除成功
cout << s.erase(2) << endl;
cout << s.erase(2) << endl;
// 获取大小
cout << s.size() << endl;

回到这个很简单的题：

就可以用ListNode *的唯一性来确定是否到达重复位置，判断是否环路

我最开始用的map解决，其实是一个道理，也是利用键的唯一性，看到题解用的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
39
40
41
42
43
// map解决
bool hasCycle(ListNode *head)
{
    // map<ListNode *, int> Mymap;
    unordered_map<ListNode *, int> Mymap;
    ListNode *it = head;
    while (it != NULL)
    {
        // 这里利用的是map的特性：试图访问map中不存在的键时，这个键会被自动插入到映射中
        // 并且其值会被初始化为该类型的默认值，对于整数类型默认值是0
        if (Mymap[it] == 0)
        {
            Mymap[it]++;
        }
        else
        {
            return true;
        }
        it = it->next;
    }
    return false;
}

// set解决，逻辑跟map解决一模一样
// 唯一的区别就在于判断是否已经存入，set用 count 函数可以做到
bool hasCycle(ListNode *head)
{
    set<ListNode *> Myset;
    ListNode *it = head;
    while (it != NULL)
    {
        if (Myset.count(it) == 0)
        {
            Myset.insert(it);
        }
        else
        {
            return true;
        }
        it = it->next;
    }
    return false;
}

这个题也可以用快慢指针解决，快指针走2步，慢指针走1步

因为有个步数差，如果指针追上（相遇）说明一定有环路




参考资料

相向双指针解决两数之和

数据类型范围 | Microsoft Learn