面试经典问题（持续更新）
leetcode 上有关面试问题
0. 写在前面
之前为了准备一系列的技术面试，准备了一段时间，在leetcode上也刷了相关的题目，最近没有刷，后面也会有手撕代码的面试，因此后续也会跟进这部分的题解。
注：本人比较菜，主要是结合大神的题解进行讲解，要是灵光咋现一种方法也会写上去。
1. 总结
a88. 合并两个有序数组 - 力扣（LeetCode）
自己想到的一种方法就是使用逆向双指针，就是从数组的后面向前进行遍历，然后逐一对两个数组进行比较，谁大谁就放在nums1数组后面。想到这个方法是因为前向遍历的话容易将nums1中的原来的值覆盖掉。
但是我还是没有注意到的是边界条件
我的代码如下：
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int t = m + n - 1, i = m - 1, j = n - 1;
while (t >= 0) {
if (j >= 0 && nums1[i] < nums2[j]) {
nums1[t] = nums2[j];
t--;
j--;
} else if (i >= 0 && nums1[i] >= nums2[j]) {
nums1[t] = nums1[i];
t--;
i--;
}
}
}
};
上述代码是错误的，原因是没有进行边界处理，要是nums1和nums2已经遍历完毕，则需要将另一个数组剩余的部分复制到nums1的前面。因此上面while中写t>=0就不妥，可能t没有到达0i和j中有一个已经小于0了，这样就会报错的。因此就这个限制对代码修改如下：
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int t = m + n - 1, i = m - 1, j = n - 1;
while (i >= 0 && j >= 0) { // 修改了循环条件，确保同时检查 i 和 j
if (nums1[i] > nums2[j]) {
nums1[t--] = nums1[i--];
} else {
nums1[t--] = nums2[j--];
}
}
// 如果 nums2 还有剩余的元素，则将其复制到 nums1 的开头,要是nums1有剩余的话，nums1无需复制的，直接就是在其中
while (j >= 0) {
nums1[t--] = nums2[j--];
}
}
};
当然，上述代码是官方给的第三种解法，还有两种解法进行参考：
第二种方法就是用到了双指针从前向后进行遍历，将两个数组看成队列，每次从两个数组头部取出比较小的数字放入结果中。要是直接对nums1进行操作，可能会出现数据被覆盖的情况，因此这里需要开辟一个新的数组进行数据的存储。然后在后面将对应位置的数值赋值给nums1即可。
第一种方法不做参考，就是将nums2中的数据直接拼接在数组num1后面然后使用的sort函数进行排序。
27. 移除元素 - 力扣（LeetCode）
本题一开始我没有看懂，不知道为啥给测试用例解释这么多的话，后面细细分析了一下，发现确实需要这样，题目不仅仅只需要求出一个数组中和给定数值不同的数的个数（记为k），还需要将该数组进行排序，使得测评机在测试的时候前k个位置的元素都不是给定的数字，因此我自然而然想到的是开辟一个新数组，将不等于给定值的数字放入该数组，同时统计数字的个数，然后在赋值回去即可，因此代码如下：
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int len = nums.size();
vector<int> nums1(len, 0);
int k = 0;
for (int i = 0; i < len; i++)
if (nums[i] != val) {
nums1[k] = nums[i];
k++;
}
for (int i = 0; i < len; i++)
nums[i] = nums1[i];
return k;
}
};
额，不用说，这题要是面试题的话，肯定是需要不在开辟一个新的数组的情况下进行代码的实现。要是在删除特定数字之后还需要保持数字在原数组中相对位置不变的话，那还是比较的难的，但是这道题目不需要保证相对顺序，只需要保证前k个数字不等于特定的数字即可。因此我可以使用双指针，要是找到一个等于特定值的，直接和最后的不等于该特定值的数字进行交换即可。
具体而言，就是删除后的数组的长度肯定是不大于原来数组长度的，因此可以直接使用两个指针从前向后进行遍历
class Solution
{
public:
int removeElement(vector<int> &nums, int val)
{
int len = nums.size();
int left = 0;
for (int right = 0; right < len; right++)
if (nums[right] != val)
{
nums[left] = nums[right];
left++;
}
return left;
}
};
// 下面是优化代码
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int left = 0, right = nums.size();
while (left < right) {
if (nums[left] == val) {
nums[left] = nums[right - 1];
right--;
} else {
left++;
}
}
return left;
}
};
// 下面的代码有很大的错误
class Solution
{
public:
int removeElement(vector<int> &nums, int val)
{
int len = nums.size();
int right = len - 1;
for (int left = 0; left <= right; left++) // 看似和上面的代码比较的类似，实际上是不能使用for循环进行判断的，需要使用while循环进行判断，因为要是输入是 [1] 1的形式，这样的话，循环完成后left的数值会变成1，这样是不对的，应该是0才是对的。因为left++只能在nums[left]!=val的时候才能够进行的
{
while (nums[right] == val)
right--;
if (nums[left] == val)
{
nums[left] = nums[right];
right--;
}
}
return ++right;
}
};
26. 删除有序数组中的重复项 - 力扣（LeetCode）
要是这个数组没有排序的话，还真是不好处理，可能就需要额外的数组对每个位置出现的数字进行统计，但是这里已经知道了该数组是一个非严格递增的数组，因此这样就比较的好处理了，由于由于处理完成后的数组的元素肯定是小于等于原来的数组的元素个数的，因此这里直接使用双指针进行求解。
class Solution
{
public:
int removeDuplicates(vector<int> &nums)
{
int len = nums.size();
int i = 0, j = 0; // i,j都从数组的最开始的元素进行遍历，j遍历的快一点
while (j < len)
{
if (nums[i] == nums[j]) // 要是这两个位置的元素相等的话，直接跳过j位置的元素即可
j++;
else // 要是不相等的话，就需要将j位置的值传给j++位置了，然后再向后进行遍历
{
i++;
nums[i] = nums[j];
j++;
}
}
return ++i; // 由于数组的下标是从0开始的，因此返回的结果需要再i的基础上加上1才是最终的结果
}
};
class Solution // 和上面的代码是一样的结果
{
public:
int removeDuplicates(vector<int> &nums)
{
int len = nums.size();
int i = 0;
for (int j = 1; j < len; j++)
if (nums[i] != nums[j])
{
i++;
nums[i] = nums[j];
}
return ++i;
}
};
80. 删除有序数组中的重复项 II - 力扣（LeetCode）
这题是上面的题目的一个变体，就是加一个条件：使得出现次数超过两次的元素只出现两次，其余的都是一样的，因此首先想到的就是引入一个新的记号flag，初始化为1，要是有重复元素，对flag进行++即可，要是元素不相同的话，又将flag的值置成1即可。
class Solution
{
public:
int removeDuplicates(vector<int> &nums)
{
int len = nums.size();
int flag = 1; // 判断超过两次的元素是否出现的两次
int i = 0;
for (int j = 1; j < len; j++)
{
if (nums[i] != nums[j]) // 不相等的话，处理的过程就是和前一道题目是一样的，只是需要将flag置成1
{
i++;
nums[i] = nums[j];
flag = 1;
}
else if (nums[i] == nums[j] && flag == 1) // 要是相等的话，并且flag==1的话，也是类似的赋值处理，只是需要将flag的值置成2
{
i++;
nums[i] = nums[j];
flag++;
}
}
return ++i;
}
};
当然，官方还有一种解题方法：
代码如下：
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n = nums.size();
if (n <= 2) // 对于长度不超过2的数组，无需进行任何处理
return n;
int slow = 2, fast = 2;
while (fast < n) {
if (nums[slow - 2] != nums[fast]) {
nums[slow] = nums[fast]; // 由于nums[slow-1]为上一个应该被保留的元素所移动到的指定位置，因此赋值是对nums[slow]开始后面进行的了
++slow;
}
++fast;
}
return slow;
}
};
169. 多数元素 - 力扣（LeetCode） (官方的题解还是写的比较的详细的，有时间可以看看)
首先，看到这道题目的第一个想法就是将该数组进行排序，然后由多数元素的定义可知，排序后的数组的中间元素一定是该多数元素，因此代码如下：
class Solution
{
public:
int majorityElement(vector<int> &nums)
{
sort(nums.begin(), nums.end());
return nums[nums.size() / 2];
}
};
然后还有一种思路：
使用 Boyer-Moore 投票算法，也就是把众数记为+1，把其他数记为-1，然后将其全部加起来，由于总数超过一半，因此和显然是大于0的。
class Solution {
public:
int majorityElement(vector<int>& nums) {
int x = 0, votes = 0; // 这里的x代表的是众数，初始时候任意数字都可以是众数，vote表示的是票数
for (int num : nums){
if (votes == 0) x = num; // 要是票数为0的话，表示原来的众数是不对的，需要重新开始确定众数。 要是votes等于0的话，则原来是众数的数现在在剩下的数里面还是众数。
votes += num == x ? 1 : -1;
}
return x;
}
};
上述代码的原理可以如此进行理解，假设a是众数，因此不管前面x被赋值为多少，到后面的某个为止，总是会被赋值为a的，这样就可以将众数求出来了。
189. 轮转数组 - 力扣（LeetCode）
说实话，看到这道题目的时候，其实我不知道如何做的，最初的想法就是开辟一个是原来数组两倍长的新的数组，然后将原来的数组复制两次放入新的数组中去。但是有许多的细节需要就能行处理，具体看代码：
class Solution
{
public:
void duplicateAndCopy(vector<int> &original, vector<int> &result)
// 将原来的数组复制两次存入新的数组
{
// 创建一个两倍长的新向量
result.resize(original.size() * 2);
// 复制原数组两次
for (int i = 0; i < original.size(); ++i)
{
result[i] = original[i]; // 第一次复制
result[i + original.size()] = original[i]; // 第二次复制
}
}
void rotate(vector<int> &nums, int k)
{
vector<int> result; // 开辟出来是原来两倍长的新的数组，长度在这里还没有确定下来
int len = nums.size();
if (len != 1) // 要是原来数组只有一个元素的话，就无需进行处理了，直接返回原来的数组即可
{
duplicateAndCopy(nums, result); // 调用函数复制数组
k %= len; // 由于k可能大于原来数组的长度，因此这里需要保证k是落在[0,len)之间的
for (int i = len - k; i < 2 * len - k; i++) // i的边界和初始值是根据图形画出来的
nums[i - len + k] = result[i];
}
}
};
// 当然，也可以只开辟一个长度和原来的数组一模一样的数组，然后再将新数组拷贝至原数组即可
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
vector<int> newArr(n); // 开辟一个和原数组一样大小的新数组
for (int i = 0; i < n; ++i)
newArr[(i + k) % n] = nums[i];
// 将原数组下标为 i 的元素放至新数组下标为 (i+k)%n 的位置
nums.assign(newArr.begin(), newArr.end()); // 最后拷贝回去即可
}
};
上面的两种方法都是开辟了一个新的数组进行求解的，能否考虑在原地对数组进行翻转呢？下面有两种方法进行原地翻转：
数组翻转：当我们将数组的元素向右移动 k 次后，尾部 kmodn 个元素会移动至数组头部，其余元素向后移动 kmodn 个位置。因此，我们可以先将所有元素翻转，这样尾部的 k%n 个元素就被移至数组头部，然后我们再翻转 [0,k%n−1] 区间的元素和 [k%n,n−1] 区间的元素即能得到最后的答案。
class Solution {
public:
void reverse(vector<int>& nums, int start, int end) {
while (start < end) {
swap(nums[start], nums[end]);
start += 1;
end -= 1;
}
}
void rotate(vector<int>& nums, int k) {
k %= nums.size();
reverse(nums, 0, nums.size() - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.size() - 1);
}
};
class Solution {
public:
void rotate(std::vector<int>& nums, int k) {
int n = nums.size();
k %= n; // 确保 k 不超过数组长度
// 反转整个数组
std::reverse(nums.begin(), nums.end());
// 反转前 k 个元素
std::reverse(nums.begin(), nums.begin() + k);
// 反转剩余部分
std::reverse(nums.begin() + k, nums.end());
}
};
上述解答还有一种环状替换，当时就是大概看了一下，没有仔细看，有时间的话还是可以看看的。
55. 跳跃游戏 - 力扣（LeetCode）
看到这道题目的初步想法就是从后向前进行遍历，然后将每个位置的可达性表示出来，最后直接返回初始位置的可达性即可，然后就超时了…
// 超时代码
class Solution
{
public:
bool canJump(vector<int> &nums)
{
int len = nums.size();
vector<bool> dp(len, false);
dp[len - 1] = true;
for (int i = len - 2; i >= 0; i--)
for (int j = 0; j <= nums[i]; j++)
if (i + j < len && dp[i + j] == true)
dp[i] = true;
return dp[0];
}
};
// 修改一下 但是时间复杂度和空间复杂度都是比较的高的
class Solution
{
public:
bool canJump(vector<int> &nums)
{
int len = nums.size();
vector<bool> dp(len, false);
dp[len - 1] = true;
int step = 1;
for (int i = len - 2; i >= 0; i--)
{
if (nums[i] >= step)
{
step = 0;
dp[i] = true;
}
step++;
}
return dp[0];
}
};
// 一种比较简单的做法
class Solution {
public:
bool canJump(vector<int>& nums) {
int step = 1; // 走到目标需要的步数
for (int i = nums.size() - 2; i >= 0; i--) {
if (nums[i] >= step)
// 如果>=，代表从此元素可以达到，这样步数就可以设置成0了
step = 0;
step++; // 向前移动一个元素的话，步数也需要相应的增加1
}
return step == 1; // 看看第一个元素是不是可达的
}
};
// 当然，也是可以使用贪心的方法进行求解的，
// 从初始点开始，用rightmost记录其向右的最大值，然后在这个范围的所有的数，再找是否有更向右的位置，要是有的话，直接更新rightmost即可，知道找完位置，要是rightmost >= n - 1，说明可以跳到最后的位置去，直接返回true即可。注意，更新的时候必须不能超过rightmost的大小
class Solution {
public:
bool canJump(vector<int>& nums) {
int n = nums.size();
int rightmost = 0;
for (int i = 0; i < n; ++i)
if (i <= rightmost) {
rightmost = max(rightmost, i + nums[i]);
if (rightmost >= n - 1)
return true;
}
return false;
}
};
45. 跳跃游戏 II - 力扣（LeetCode）
这道题目和上面的题目比较的类似，不同点就是在于题目保证了能够到达最后的位置，然后需要找出来跳跃的最小次数。因此我的第一想法就是从后向前进行动态规划，寻找最小跳跃次数，知道找到第一个元素即可。同时使用一个dp数组进行维护。
class Solution
{
public:
int jump(vector<int> &nums)
{
int len = nums.size();
vector<int> dp(len, INT_MAX - 1); // 每个值设置为INT_MAX的原因就是防止后面越界
dp[len - 1] = 0; // 最后一个元素无需跳跃
for (int i = len - 2; i >= 0; i--)
for (int j = 0; j <= nums[i]; j++)
if (i + j < len)
dp[i] = min(dp[i], dp[i + j] + 1); // 状态转移方程
return dp[0];
}
};
但是上面的代码时间复杂度比较的高，因此能否降低时间复杂度呢。
可以使用贪心的思想，维护当前能够到达的最大下标位置，记为边界。然后从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加1.在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。
class Solution
{
public:
int jump(vector<int> &nums)
{
int maxPos = 0, n = nums.size(), end = 0, step = 0;
// maxPos 表示当前能够到达的最远位置。
// 遍历数组中的每个位置 i
for (int i = 0; i < n - 1; i++) // 注意：遍历到 n-2 即可，因为最后一个位置无需跳跃
// 如果当前位置 i 在之前的跳跃范围内，则考虑更新最远可达位置 maxPos
if (maxPos >= i)
{
// 更新最远可达位置
maxPos = max(maxPos, i + nums[i]);
// 如果当前 i 已经达到了上一步的终点
if (i == end)
{
// 更新终点为新的最远可达位置
end = maxPos;
// 增加跳跃次数
step++;
}
}
// 返回最终所需的最小跳跃次数
return step;
}
};
274. H 指数 - 力扣（LeetCode）
先看题，发现给的数据不是很大，因此可以多上几个循环进行求解。我的初步想法就是先将数组进行排序，然后引入max_num记录返回值，count_num记录引用次数。
具体代码如下：
class Solution
{
public:
int hIndex(vector<int> &citations)
{
int len = citations.size();
sort(citations.begin(), citations.end());
int max_num = 0, count_num = 0;
for (int i = 0; i <= citations[len - 1]; i++) // 枚举引用次数
{
count_num = 0; // 每次开始新的循环的时候需要重新赋值为0
for (int j = 0; j < len; j++)
if (citations[j] >= i) // 当前的论文的引用次数大于枚举的次数的话，总数就++
count_num++;
if (count_num >= i) // 要是论文枚举的次数大于枚举次数，表示可以成为一个H指数
max_num = i;
}
return max_num;
}
};
// 下面的这段代码也是可以的，原理就是：
// 先将H指数设为0，然后将数组进行排序，要是当前H指数为h并且在遍历过程中找到当前值citations[i]>h，则说明找到了一篇被引用了至少h+1次的论文，因此将h的值+1，继续遍历直到h无法继续增大，则返回h就是最终答案
class Solution {
public:
int hIndex(vector<int>& citations) {
// 对引用次数进行排序，从低到高
sort(citations.begin(), citations.end());
int h = 0; // 初始化 H 指数
int i = citations.size() - 1; // 从数组的最后一个元素开始检查
// 循环遍历引用次数数组，从后向前
while (i >= 0 && citations[i] > h) {
h++; // 增加 H 指数
i--; // 移动到前一个元素
}
// 返回计算出的 H 指数
return h;
}
};
// 也可以使用计数排序算法，新建并维护一个数组counter用来记录当前引用次数的论文有几篇
class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size(); // 获取引用次数数组的长度
int tot = 0; // 初始化累加的论文数量为 0
vector<int> counter(n + 1, 0); // 初始化计数器数组，大小为 n+1，所有元素初始化为 0
// 统计引用次数
for (int i = 0; i < n; i++) {
if (citations[i] >= n)
counter[n]++; // 如果引用次数大于等于 n，增加计数器数组最后一个元素的值，这里只给最大的那个位置进行++，这样便于后面用tot进行处理
else
counter[citations[i]]++; // 否则，增加对应引用次数的位置的值
}
// 计算 H 指数
for (int i = n; i >= 0; i--) {
tot += counter[i]; // 累加当前及之后的所有论文数量
if (tot >= i)
return i; // 如果累加的论文数量大于等于当前的引用次数 i，则返回 i 作为 H 指数
}
return 0; // 如果没有找到符合条件的 H 指数，返回 0
}
};
380. O(1) 时间插入、删除和获取随机元素 - 力扣（LeetCode）
没有啥思路，看题解后，好像是用可变数组+哈希表进行求解的
class RandomizedSet
{
private:
vector<int> nums; // 存储元素的有序列表
unordered_map<int, int> indices; // 用于快速查找元素在有序列表中的索引，一个哈希表
public:
RandomizedSet()
{
srand((unsigned)time(NULL)); // 初始化随机数生成器
}
// 插入一个值到集合中
bool insert(int val)
{
// 如果值已存在，则无法插入
if (indices.count(val))
return false;
// 获取新的索引位置
int index = nums.size();
// 将值添加到有序列表末尾
nums.emplace_back(val);
// 在哈希表中记录该值的索引
indices[val] = index;
// 返回成功标志
return true;
}
// 从集合中移除一个值，就是将需要删除的元素和最后一个元素进行交换，然后删除最后一个元素即可
bool remove(int val)
{
// 如果值不存在，则无法移除
if (!indices.count(val))
return false;
// 获取要移除值的索引
int index = indices[val];
// 获取有序列表最后一个元素
int last = nums.back();
// 将最后一个元素移动到要移除的元素位置
nums[index] = last;
// 更新最后一个元素的新索引
indices[last] = index;
// 从有序列表中移除最后一个元素
nums.pop_back();
// 从哈希表中移除已删除的元素
indices.erase(val);
// 返回成功标志
return true;
}
// 随机返回集合中的一个元素
int getRandom()
{
// 计算随机索引
int randomIndex = rand() % nums.size();
// 返回对应索引处的元素
return nums[randomIndex];
}
};
// 创建 RandomizedSet 对象实例
// RandomizedSet* obj = new RandomizedSet();
// 调用 insert 方法插入一个值
// bool param_1 = obj->insert(val);
// 调用 remove 方法移除一个值
// bool param_2 = obj->remove(val);
// 调用 getRandom 方法随机返回一个值
// int param_3 = obj->getRandom();
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet* obj = new RandomizedSet();
* bool param_1 = obj->insert(val);
* bool param_2 = obj->remove(val);
* int param_3 = obj->getRandom();
*/
238. 除自身以外数组的乘积 - 力扣（LeetCode）
这道题目之前好像是做过的，我好像就是使用的除法进行解决的，代码如下：
class Solution
{
public:
vector<int> productExceptSelf(vector<int> &nums)
{
int zero_num = 0; // 用来记录0的个数
int n = nums.size();
int sum = 1; // 用来统计所有非0元素的个数
int index = 0; // 记录当nums中只有一个0元素时，此时的0元素的下标
vector<int> dp(n, 0); // 引入新的数组，并初始化为0
for (int i = 0; i < n; i++)
if (nums[i] == 0)
zero_num++;
if (zero_num > 1) // 要是nums数组中0元素的个数大于0的话，则dp直接返回即可
return dp;
else if (zero_num == 1)
{
for (int i = 0; i < n; i++) // 将不等于0的元素都乘起来，同时找到0元素的下标
if (nums[i] != 0)
sum *= nums[i];
else
index = i;
dp[index] = sum;
return dp;
}
else
{
for (int i = 0; i < n; i++)
if (nums[i] != 0)
sum *= nums[i];
for (int i = 0; i < n; i++)
dp[i] = sum / nums[i];
return dp;
}
}
};
上述代码虽然可以通过，但是使用到了除法，不符合题意，因此解答不正确。
class Solution { // 参考官方解答，加上自己的理解，写的下面的代码
public:
vector<int> productExceptSelf(vector<int>& nums) {
int len = nums.size();
vector<int> answer(len), L(len, 1), R(len, 1);
for (int i = 1; i < len; i++)
L[i] = L[i - 1] * nums[i - 1];
for (int i = len - 2; i >= 0; i--)
R[i] = R[i + 1] * nums[i + 1];
for (int i = 0; i < len; i++)
answer[i] = L[i] * R[i];
return answer;
}
};
class Solution
{
public:
vector<int> productExceptSelf(vector<int> &nums)
{
int length = nums.size();
vector<int> answer(length, 1);
// answer[i] 表示索引 i 左侧所有元素的乘积
// 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
for (int i = 1; i < length; i++)
answer[i] = nums[i - 1] * answer[i - 1];
// R 为右侧所有元素的乘积
// 刚开始右边没有元素，所以 R = 1
int R = 1;
for (int i = length - 1; i >= 0; i--)
{
// 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
answer[i] = answer[i] * R;
// R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
R *= nums[i];
}
return answer;
}
};
134. 加油站 - 力扣（LeetCode）
由于题目保证了答案是唯一的，因此可以知道gas中的所有元素和是小于等于cost中的所有元素和的，要是小于，直接返回-1即可，要是等于，找到开始的位置即可。因此这里主要是要确定等于的情况下开始的位置是啥，这里使用到了贪心的算法，一次便利整个数组，使用startStation记录加油站的初始位置，用total 表示需要返回的结果，currentTank 表示遍历到此处当前的油箱的容量，要是当前容量是一个负数的话，表示之前的位置都不能作为起始点，需要重新从下一个点开始进行，也就是将startStation赋值为下一个加油站的位置，同时油箱的油数清零，然后再向后遍历，直到找到符合题意的位置。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int len = gas.size(); // 获取加油站的数量
int total = 0, currentTank = 0; // 初始化总盈余和当前油箱中的剩余汽油量
int startStation = 0; // 初始化起始加油站的索引
// 遍历每个加油站
for (int i = 0; i < len; i++) {
// 更新总的汽油盈余
total += gas[i] - cost[i];
// 更新当前油箱中的剩余汽油量
currentTank += gas[i] - cost[i];
// 如果当前油箱中的剩余汽油量小于0，表示从当前站之前的任何站出发都无法完成一圈
if (currentTank < 0) {
// 更新起始站为当前站的下一站
startStation = i + 1;
// 重置当前油箱中的剩余汽油量为0
currentTank = 0;
}
}
// 如果总的汽油盈余是非负数，说明至少存在一个起始站可以从那里出发完成一圈
return (total < 0) ? -1 : startStation;
}
};
135. 分发糖果 - 力扣（LeetCode）
这道题目一看就是需要使用贪心算法进行实现，可以形象的理解为，资本家发工资算法，想尽一切办法发出尽量少的工资。这题被列为困难提，主要是因为不知道如何使用贪心策略进行上述代码的求解。肯定一开始就是想两边一起进行考虑，但是这样的话会导致顾此失彼。因此，不妨先确定一边之后，再在此基础上确定另外一边。因此可以按照下面的方式进行贪心：
$$
从左往右遍历: 如果"右边"比"左边"分高，右边的糖果 = 左边 + 1, 否则 = 1\
从右往左遍历: 如果"左边"比"右边"分高，左边的糖果 = max(左边本身的糖果数, 右边糖果数 + 1 )
$$
如此，便可写出来对应的代码：
class Solution
{
public:
int candy(vector<int> &ratings)
{
int n = ratings.size();
vector<int> dp(n, 1);
for (int i = 1; i < n; i++)
if (ratings[i] > ratings[i - 1])
dp[i] = dp[i - 1] + 1;
for (int i = n - 1; i > 0; i--)
if (ratings[i - 1] > ratings[i])
dp[i - 1] = max(dp[i - 1], dp[i] + 1);
int sum = 0;
for (int i = 0; i < n; i++)
sum += dp[i];
return sum;
}
};
// 下面的代码与上面的类似
class Solution
{
public:
int candy(vector<int> &ratings)
{
int n = ratings.size();
vector<int> dp(n, 1);
for (int i = 1; i < n; i++)
if (ratings[i] > ratings[i - 1])
dp[i] = dp[i - 1] + 1;
int sum = dp[n - 1];
for (int i = n - 1; i > 0; i--)
{
if (ratings[i - 1] > ratings[i])
dp[i - 1] = max(dp[i - 1], dp[i] + 1);
sum += dp[i - 1];
}
return sum;
}
};
42. 接雨水 - 力扣（LeetCode）
说实话，第一次看到这道题目的时候是没有一点思路的。还是看题解才会做的。
总结来说，思路一就是对每一个点求解可以装入的雨水量。而该点的值由左右两侧较小的高度减去当前位置的高度决定的
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
vector<int> leftMax(n);
leftMax[0] = height[0];
for (int i = 1; i < n; ++i)
leftMax[i] = max(leftMax[i - 1], height[i]);
vector<int> rightMax(n);
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; --i)
rightMax[i] = max(rightMax[i + 1], height[i]);
int ans = 0;
for (int i = 0; i < n; ++i)
ans += min(leftMax[i], rightMax[i]) - height[i];
return ans;
}
};
class Solution {
public:
int trap(vector<int>& height) {
int ans = 0;
stack<int> stk; // 维护一个单调栈
int n = height.size();
for (int i = 0; i < n; ++i) {
while (!stk.empty() && height[i] > height[stk.top()]) {
// 要是单调栈不为空，并且当前位置的高度高于栈顶的高度
int top = stk.top();
stk.pop(); // 弹出栈顶元素
if (stk.empty()) // 要是取出元素后栈里面没有元素了，表示该位置无法接住雨水，直接跳过本次循环
break;
int left = stk.top();// 要是不为空的话，再次记录当前栈顶元素，进行top位置的雨水容量求解操作
int currWidth = i - left - 1;
int currHeight = min(height[left], height[i]) - height[top];
ans += currWidth * currHeight;
}
stk.push(i);// 计算完i处的雨水量之后，将i入栈，继续下一次循环
}
return ans;
}
};
13. 罗马数字转整数 - 力扣（LeetCode）
就是使用一个哈希表，将键值对存储进去，然后再遍历字符串，要是小的数字在大的数字的右边，则使用加法进行操作，反之则使用减法进行操作。
class Solution
{
private:
unordered_map<char, int> symbolValues = {
{'I', 1},
{'V', 5},
{'X', 10},
{'L', 50},
{'C', 100},
{'D', 500},
{'M', 1000},
};
public:
int romanToInt(string s)
{
int sum = 0;
int len = s.length();
for (int i = 0; i < len; i++)
{
int value = symbolValues[s[i]];
if (i < len - 1 && symbolValues[s[i + 1]] > value)
sum -= value;
else
sum += value;
}
return sum;
}
};
12. 整数转罗马数字 - 力扣（LeetCode）
由于罗马数字有唯一的表示法，因此对于给定的整数num，找寻不超过num的最大符号值，然后减去该符号值，接着继续寻找，直至num=0。因此，可以建立一个数值-符号对的列表alueSymbols，按数值从大到小排列。遍历 valueSymbols 中的每个数值-符号对，若当前数值 value 不超过 num，则从 num 中不断减去 value，直至 num 小于 value，然后遍历下一个数值-符号对。若遍历中 num 为 0 则跳出循环。
// 这里按照数值从大到小进行排列，因此使用unordered_map 就不太适合了
const pair<int, string> valueSymbols[] = {
{1000, "M"}, {900, "CM"}, {500, "D"}, {400, "CD"}, {100, "C"},
{90, "XC"}, {50, "L"}, {40, "XL"}, {10, "X"}, {9, "IX"},
{5, "V"}, {4, "IV"}, {1, "I"},
};
class Solution {
public:
string intToRoman(int num) {
string roman;
for (const auto& [value, symbol] : valueSymbols) {
while (num >= value) {
num -= value;
roman += symbol;
}
if (num == 0)
break;
}
return roman;
}
};
/*pair和unordered_map区别
pair 主要用来组合两个相关的值 ，其总是包含两个元素，不支持查找操作。
unordered_map 用于存储键值对，每个键都是唯一的，键值对是以无序的方式存储的，可以通过键快速查找对应的值。
*/
58. 最后一个单词的长度 - 力扣（LeetCode）
这题还是很简单的，第一次做的思路是：直接从后向前进行遍历，使用num记录最后一个单词的长度，要是遇到第一个不是空字符的位置，num进行启动，并继续向前遍历，直到遇到空字符位置，然后返回即可。
class Solution {
public:
int lengthOfLastWord(string s) {
int len = s.length();
int sum = 0;
for (int i = len - 1; i >= 0; i--) {
if (s[i] == ' ' && sum == 0) // 表示还没有到达最后一个单词的位置
continue;
if (s[i] != ' ')
sum++;
else // 再次遇到空字符的话，直接返回即可
break;
}
return sum;
}
};
class Solution {
public:
int lengthOfLastWord(string s) {
s.erase(s.find_last_not_of(' ') + 1);
// find_last_not_of会从后向前查找最有一个不在指定字符集中的字符的位置，返回最后一个非空格字符的位置
// erase会删除从最后一个非空格字符后面的第一个位置到字符串末尾的所有字符。换句话说，它会删除字符串末尾的所有空格。
return s.length() - 1 - s.rfind(' ');
// rfind方法是从右向左搜索指定字符的最后一次出现的位置
}
};
class Solution {
public:
int lengthOfLastWord(string s) {
int i = s.find_last_not_of(' ');
int j = s.find_last_of(' ', i);
// 查找从位置i开始往左方向最后一个出现的空格的位置
return i - j;
}
};
14. 最长公共前缀 - 力扣（LeetCode）
官方解答还给出了四种解答：
横向扫描（相比较前两个，然后用公共部分和后面进行比较），
纵向扫描（同时比较每一个字符串的同一个位置，相同就是公共的，不相同直接返回）
分治（将问题分解成较小的问题，然后综合起来求解公共前缀）
二分查找（取中点mid，判断前mid的前缀是不是相同的，要是相同，则长度大于等于mid，反之则小于等于mid）
class Solution {
// 思路就是将该数组进行排序，然后直接比较第一个字符串和最后一个字符串的字母，
// 要是相等的话，该字母直接加入返回的字符串中，要是不相等的话，就直接返回即可
public:
string longestCommonPrefix(vector<string>& strs) {
int len = strs.size();
sort(strs.begin(), strs.end());
string ss = "";
for (int i = 0; i < strs[0].length() && i < strs[len - 1].length(); i++)
if (strs[0][i] == strs[len - 1][i])
ss += strs[0][i];
else
break;
return ss;
}
};
151. 反转字符串中的单词 - 力扣（LeetCode）
初步的想法就是先将前导空格和尾随空格进行删除，然后新引入一个字符串，再对原来的字符串中的每个单词进行反转之后向前插入到新的字符串中去，然后返回原来的字符串即可。
class Solution
{
public:
string reverseWords(string s)
{
// 去除前导和尾随空格
s.erase(0, s.find_first_not_of(' '));
s.erase(s.find_last_not_of(' ') + 1);
string result = "";
int start = 0; // 单词的开始位置
for (int i = 0; i <= s.length(); ++i)
{
if (s[i] == ' ' || i == s.length()) // 找到单词的结束位置
{
// 反转单词的顺序，这里就是将每个单词从前向后截取出来，然后向前拼接在result字符串中去
string word = s.substr(start, i - start);
if (!result.empty())
result = word + " " + result;
else
result = word; // 第一个单词拼接进去的时候是不需要插入空格的
while (i < s.length() && s[i] == ' ') // 删除单词间多余的空格
i++;
start = i;
}
}
return result;
}
};
// 下面解法的思想就是 整体反转，处理单词，去除多余空格
class Solution
{
public:
string reverseWords(string s)
{
// 反转整个字符串
reverse(s.begin(), s.end());
int n = s.size();
int idx = 0; // 新字符串的写入位置
for (int start = 0; start < n; ++start)
{
// 要是当前字符不是空格，则表示找到了一个单词的开始位置
if (s[start] != ' ')
{
// 填一个空白字符然后将idx移动到下一个单词的开头位置
if (idx != 0)
s[idx++] = ' '; // 要是idx不为0，说明这不是第一个单词，需要插入一个空格
// 循环遍历至单词的末尾
int end = start;
while (end < n && s[end] != ' ')
s[idx++] = s[end++];
// 反转整个单词，这个规律需要自己总结出来
reverse(s.begin() + idx - (end - start), s.begin() + idx);
// 更新start，去找下一个单词
start = end;
}
}
// 去除末尾多余的空格
s.erase(s.begin() + idx, s.end());
return s;
}
};
6. Z 字形变换 - 力扣（LeetCode）
看到这道题目的第一眼，就知道肯定是一道找规律的题目，初步的想法就是将字符串按照题中所描述的规律进行排序，然后再使用一个数组，将每一行的字符存储到一个数组中去。但是现在的问题主要是如何按照顺序进行存储。也就是在从上向下移动之后如何在从下至上进行移动。在看完相关题解之后，我知道可以设置一个flag，当达到最上面或者最下面之后就对flag=-flag，这样就实现了翻转。
class Solution
{
public:
string convert(string s, int numRows)
{
if (numRows < 2) // 要是划分的行数就是1行的话，直接就是原字符串
return s;
vector<string> nums(numRows);
int flag = -1, i = 0;
for (char c : s)
{
nums[i].push_back(c); // 第一个字符压入第一行
if (i == 0 || i == numRows - 1)
flag *= -1; // 到达最上面或者最下面就取相反数
i += flag;
}
string res;
for (const string &num : nums) //从上至下逐步拼接起来
res += num;
return res;
}
};
// 下面使用的是二维矩阵进行求解，直接按照题目的顺序将字符存储起来，但是有大量的空间没有被利用到
class Solution
{
public:
string convert(string s, int numRows)
{
int n = s.length(), r = numRows;
if (r == 1 || r >= n)
return s;
int t = 2 * r - 2; // 变换周期
int c = (n + t - 1) / t * (r - 1);
// 列数应该是周期数×每个周期的列数，即(n/t)向上取整，然后乘以r-1列
// 为便于求解，(n/t)向上取整也是可以表示为(n+t-1)/t的
vector<string> mat(r, string(c, 0));
for (int i = 0, x = 0, y = 0; i < n; i++)
{
mat[x][y] = s[i];
if (i % t < r - 1) // 要是满足条件，则向下移动
++x;
else // 否则向右上移动
{
--x;
++y;
}
}
string ans;
for (auto &row : mat)
for (char ch : row)
if (ch)
ans += ch;
return ans;
}
};
// 上面的代码浪费了大量的空间，这是没有必要的，因此可以进行优化处理:每次向矩阵的某一行添加字符的时候，都会添加到该行上一个字符的右侧，因此可以优化上面的代码
class Solution
{
public:
string convert(string s, int numRows)
{
int n = s.length(), r = numRows;
if (r == 1 || r >= n)
return s;
vector<string> mat(r);
for (int i = 0, x = 0, t = 2 * r - 2; i < n; i++)
{
mat[x] += s[i]; // 每一行的元素直接拼接在原来该行元素的右侧即可
i % t < r - 1 ? ++x : --x;
}
string ans;
for (auto &row : mat)
ans += row;
return ans;
}
};
28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）
这道题目是一个典型的字符串匹配问题，因此可以想到用kmp算法进行求解，但是这个算法我还是不太会，于是无奈，只能通过暴力方法进行求解了。
class Solution
{
public:
int strStr(string haystack, string needle)
{
int m = haystack.length();
int n = needle.length();
char c = needle[0];
for (int i = 0; i < m; i++)
{
if (haystack[i] == c) //要是第一个字符是相等的，则开始进行字符串的截取与比较
{
string s = haystack.substr(i, n);
// substr 接受的参数应该是起始位置和长度，因此传参数需要注意
if (s == needle) // 要是比较后字符串相等的话，那就直接返回起始位置即可
return i;
}
}
return -1;
}
};
// 下面使用kmp算法进行求解，
// next数组的本质就是寻找子串中“相同前后缀的长度”，并且一定是最长的前后缀
// 主串的指针只能向前移动，不能向后移动，这样时间复杂度才是O(n)
【最浅显易懂的 KMP 算法讲解】https://www.bilibili.com/video/BV1AY4y157yL?vd_source=787265274e83402df2af8ddda989e677
class Solution {
public:
int strStr(string haystack, string needle) {
// 初始化两个字符串的长度，并处理特殊的情况
int n = haystack.size(), m = needle.size();
if (m == 0)
return 0;
vector<int> pi(m);
// i表示当前正在处理的needle中字符的位置，j表示当前已知的最长公共前后缀的长度
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && needle[i] != needle[j])
j = pi[j - 1];
// 要是不匹配，j退回到pi[j-1]，即前一个状态的最长公共前后缀长度
if (needle[i] == needle[j])
j++; // 要是匹配，j++
pi[i] = j; // 更新pi[i]为当前已知的最长公共前后缀长度
}
for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && haystack[i] != needle[j])
j = pi[j - 1];
// 当haystack[i]与needle[j]不匹配时，根据pi数组更新j；
// 也就是看不匹配前一个元素的pi数组对应的位置的数值，表示可以跳过的比较的元素
if (haystack[i] == needle[j])
j++;
if (j == m)
return i - m + 1;
// 如果j达到模式串的长度m，说明找到了一个匹配，返回匹配开始的位置i-m+1
}
return -1;
}
};
68. 文本左右对齐 - 力扣（LeetCode）
这道题目没有看懂如何做，只是大致看懂了相关的一些小的知识点，有时间的话再进行研究一下：
class Solution
{
// blank 返回长度为 n 的由空格组成的字符串
string blank(int n)
{
return string(n, ' ');
}
// join 返回用 sep 拼接 [left, right) 范围内的 words 组成的字符串
string join(vector<string> &words, int left, int right, string sep)
{
string s = words[left];
for (int i = left + 1; i < right; ++i)
s += sep + words[i];
return s;
}
public:
vector<string> fullJustify(vector<string> &words, int maxWidth)
{
vector<string> ans;
int right = 0, n = words.size();
while (true)
{
int left = right; // 当前行的第一个单词在 words 的位置
int sumLen = 0; // 统计这一行单词长度之和
// 循环确定当前行可以放多少单词，注意单词之间应至少有一个空格,这里使用的是right-left表示的是空格的数量
while (right < n && sumLen + words[right].length() + right - left <= maxWidth)
sumLen += words[right++].length();
// 当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格
if (right == n)
{
string s = join(words, left, n, " ");
ans.emplace_back(s + blank(maxWidth - s.length())); // 剩余的填充空格就行
return ans;
}
int numWords = right - left;
int numSpaces = maxWidth - sumLen;
// 当前行只有一个单词：该单词左对齐，在行末填充剩余空格
if (numWords == 1)
{
ans.emplace_back(words[left] + blank(numSpaces));
continue;
}
// 当前行不只一个单词
int avgSpaces = numSpaces / (numWords - 1);
int extraSpaces = numSpaces % (numWords - 1);
string s1 = join(words, left, left + extraSpaces + 1, blank(avgSpaces + 1)); // 拼接额外加一个空格的单词
string s2 = join(words, left + extraSpaces + 1, right, blank(avgSpaces)); // 拼接其余单词
ans.emplace_back(s1 + blank(avgSpaces) + s2);
}
}
};
125. 验证回文串 - 力扣（LeetCode）
这道题目我的解题方式如下：直接暴力破解，然后上if
class Solution {
public:
bool isPalindrome(string s) {
string ss;
int len = s.length();
for (int i = 0; i < len; i++)
if (s[i] >= 'a' && s[i] <= 'z')
ss += s[i];
else if (s[i] >= 'A' && s[i] <= 'Z')
ss += s[i] - 'A' + 'a';
else if (s[i] >= '0' && s[i] <= '9')
ss += s[i];
string sss = ss;
reverse(ss.begin(), ss.end());
if (sss == ss)
return true;
else
return false;
}
};
// 但是题解给了一种更为便捷的方式，就是使用相关的库函数
class Solution{
public:
bool isPalindrome(string s){
string sgood;
for(char ch:s){
if(isalnum(ch)){
// isalnum() 函数来检查字符是否是字母或数字
sgood+=tolower(ch); // 要是处理到数字字符的话，是不会产生影响的
}
}
string sgood_rev(sgood.rbegin(),sgood.rend());
return sgood==sgood_rev;
}
};
392. 判断子序列 - 力扣（LeetCode）
很容易想到的解法就是使用双指针进行求解，从前向后分别遍历这两个字符串即可
class Solution {
public:
bool isSubsequence(string s, string t) {
int s_len = s.length();
if (s_len == 0) // 较小的字符串长度为0肯定是可以的
return true;
int t_len = t.length();
int j = 0; // 用来从后向前遍历s字符串
for (int i = 0; i < t_len; i++) {
if (t[i] == s[j])
j++;
if (j == s_len)
return true;
}
return false;
}
};
// 下面是官方的类似解答
class Solution {
public:
bool isSubsequence(string s, string t) {
int m = s.length();
int n = t.length();
int i = 0, j = 0;
while (i < m && j < n) {
if (s[i] == t[j]) // 只有子串和主串匹配之后，子串才向前进行移动
i++;
j++; // 不管匹不匹配，主串是一直需要向前走的
}
return i == m;
}
};
167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）
看到这道题目，第一想法就是使用双指针进行解题，然后这也是比较好的一种解题思路，由于题目已经明确告知给定的数组是有序地，并且有且仅有唯一的一个有效答案，因此一个指针从下标0开始进行遍历，另一个指针从下标len-1(len表示给定数组的长度)开始进行遍历。然后逐渐缩短两个指针之间的距离，直到找到唯一确定的解即可。
class Solution
{
public:
vector<int> twoSum(vector<int> &numbers, int target)
{
int len = numbers.size();
int i = 0, j = len - 1;
while (i < j)
{
if (numbers[i] + numbers[j] < target)
i++;
else if (numbers[i] + numbers[j] > target)
j--;
else
return {i + 1, j + 1};
}
return {-1, -1}; // 由于是有唯一确定的结果的，因此这条语句是不会执行到的，但是不写的话好像是会报错的
}
};
当然，也是可以使用二分法进行求解的，也就是先固定第一个数，然后寻找第二个数。
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
for (int i = 0; i < numbers.size(); ++i) {
int low = i + 1, high = numbers.size() - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
// int mid = (low+high) / 2; 这种写法也是可以的
if (numbers[mid] == target - numbers[i]) {
return {i + 1, mid + 1};
} else if (numbers[mid] > target - numbers[i]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
return {-1, -1};
}
};
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int len = numbers.size();
for (int i = 0; i < len; i++) {
int low = i + 1, high = len - 1;
while (low <= high) {
int mid = (low + high) / 2;
int sum = numbers[i] + numbers[mid];
if (sum == target)
return {i + 1, mid + 1};
else if (sum < target)
low = mid + 1;
else
high = mid - 1;
}
}
return {-1, -1};
}
};
11. 盛最多水的容器 - 力扣（LeetCode）
看到这道题的第一个想法就是使用两层循环进行遍历，直到找到最大的值即可，于是代码如下：
class Solution
{
public:
int maxArea(vector<int> &height)
{
int maxA = 0;
for (int i = 0; i < height.size() - 1; i++)
{
for (int j = 1; j < height.size(); j++)
{
int Area = (j - i) * (min(height[i], height[j]));
maxA = max(maxA, Area);
}
}
return maxA;
}
};
然后发现结果超出了时间限制，仔细一看，确实会超出，于是没有办法，只能优化上述代码。观察上述代码可以发现，其实有很多重复的计算与比较是没有意义的，也就是如上代码：要是j小于i的话，这样比较就重复了，因此不如一个指针指向数组初始位置，一个指针指向数组末尾位置。然后两个指针分别移动。这样时间复杂度就大大减少了。
class Solution
{
public:
int maxArea(vector<int> &height)
{
int l = 0, r = height.size() - 1; // 一个指针指向数组初始位置，一个指针指向数组的末尾位置
int ans = 0;
while (l < r)
{
int area = min(height[l], height[r]) * (r - l);
ans = max(ans, area);
if (height[l] <= height[r]) // 贪心：谁短移动谁
l++;
else
r--;
}
return ans;
}
};
15. 三数之和 - 力扣（LeetCode）
前面有一道两数之和给我相关的做题提示，只是将前面的target换成了数组中的一个数值，其实实际上还是一样的，先对数组进行排序，然后再找这三个数：然后我就写出来了下面的代码：
class Solution
{
public:
vector<vector<int>> threeSum(vector<int> &nums)
{
int len = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
for (int i = 0; i < len; i++)
{
int target = nums[i];
int j = i + 1, k = len - 1;
while (j < k)
{
if (target + nums[j] + nums[k] == 0)
ans.push_back({nums[i], nums[j], nums[k]});
else if (target + nums[j] + nums[k] > 0)
k--;
else
j++;
}
}
return ans;
}
};
结果显示超出内存限制，仔细分析发现，我没有去除掉重复的结果，因为三个数字相同但是顺序不同也是同一个三元组，因此基于此对上述代码优化如下：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int len = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
for (int i = 0; i < len; i++) {
// 去除最外层循环中的重复元素
if (i > 0 && nums[i] == nums[i-1]) continue;
int target = nums[i];
int j = i + 1, k = len - 1;
while (j < k) {
if (target + nums[j] + nums[k] == 0) {
ans.push_back({nums[i], nums[j], nums[k]});
// 去除内部循环中的重复元素
while (j < k && nums[j] == nums[j+1]) j++;
while (j < k && nums[k] == nums[k-1]) k--;
j++;
k--;
} else if (target + nums[j] + nums[k] > 0) {
k--;
} else {
j++;
}
}
}
return ans;
}
};
下面的四道题目都是使用滑动窗口的相关思想进行求解。fucking-algorithm/算法思维系列/滑动窗口技巧进阶.md at master · labuladong/fucking-algorithm · GitHub
这种算法是有一个模板的，以后解题可以看这个解题模板进行编码
//外层循环扩展右边界，内层循环扩展左边界
for (int l = 0, r = 0 ; r < n ; r++) {
//当前考虑的元素
while (l <= r && check()) {//区间[left,right]不符合题意
//扩展左边界
}
//区间[left,right]符合题意，统计相关信息
}
209. 长度最小的子数组 - 力扣（LeetCode）
看到这道题目的第一眼，想当然的就是排序，然后从后往前找，直到大于给定的数字就是答案，于是我想的代码如下：
class Solution // 这段代码是不对的
{
public:
int minSubArrayLen(int target, vector<int> &nums)
{
int len = nums.size();
sort(nums.begin(), nums.end());
int sum = 0;
for (int i = len - 1; i >= 0; i--)
{
sum += nums[i];
if (sum >= target)
return len - i;
}
return 0;
}
};
结果一顿操作猛如虎，一看结果，错啦！！！仔细一看，原来是需要找到连续的子数组而不是连续的子序列啊，也就是数组中元素的顺序是不能够改变的。因此代码就不能这样写了。思来想去，有一种方式（官方给出了三种解题方法），也就是使用滑动窗口的知识进行求解：定义两个指针，左右指针中间窗口的sum为两指针的“共同财产”，就是右指针一直在努力工作挣钱，好不容易共同财产大过target，记录一下两指针之间的距离，结果左指针就开始得瑟挥霍，不停花钱（往右移动），结果花钱一直花到sum又小过target，此时右指针不得不再次出来工作，不停向右移动，周而复始，最后取左右指针离得最近的时候。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int left = 0, current_sum = 0;
int min_length = INT_MAX; // 先将最小长度初始化为最大值
for (int right = 0; right < nums.size(); ++right) {
current_sum += nums[right]; // 有指针增加财富
while (current_sum >= target) {
min_length = min(min_length, right - left + 1); // 找两距离间的最小值
current_sum -= nums[left++]; // 财富达到标准后，左指针挥霍财富
}
}
return min_length == INT_MAX ? 0 : min_length;
}
};
3. 无重复字符的最长子串 - 力扣（LeetCode）
其实本题和上面的题目很类似，就是使用双指针进行循环，要是满足条件，右侧指针就向后移动，要是不满足条件的话，左侧指针就向前移动，这样就类似一个窗口在进行移动，因此称为滑动窗口。
本题主要需要解决的问题就是当引入一个新的字符（也就是right指针i向前移动一个位置之后），需要判断是否有重复字符的字符。这时候，我们可以利用哈希集合进行求解。常用的数据结构为哈希集合（即 C++ 中的 std::unordered_set，Java 中的 HashSet，Python 中的 set, JavaScript 中的 Set）
class Solution
{
public:
int lengthOfLongestSubstring(std::string s)
{
std::unordered_set<char> chars;
int left = 0, right = 0, max_len = 0, n = s.length();
while (right < n)
{
// 如果右侧字符不在当前窗口中，if中的句子表示要是find找到了最后一个位置，则该窗口中是没有该元素的，可以直接插入，并更新最大值
if (chars.find(s[right]) == chars.end())
{
// 将其加入窗口并扩展窗口大小
chars.insert(s[right]);
max_len = std::max(max_len, right - left + 1);
++right;
}
else
{
// 移除左侧字符来缩小窗口直到重复字符不再出现
chars.erase(s[left]);
++left;
}
}
return max_len;
}
};
30. 串联所有单词的子串 - 力扣（LeetCode）
这道题目没咋看懂，有时间的话再看看，还是一样，使用滑动窗口的知识进行求解。
class Solution {
public:
vector<int> findSubstring(string &s, vector<string> &words) {
vector<int> res; // 存储结果的数组
int m = words.size(), n = words[0].size(), ls = s.size(); // 单词数量、单词长度、字符串 s 的长度
for (int i = 0; i < n && i + m * n <= ls; ++i) { // 外层循环，从每个可能的起始位置 i 开始
unordered_map<string, int> differ; // 用于统计当前窗口内单词的出现次数
// 统计从当前起始位置 i 开始的 m 个单词
for (int j = 0; j < m; ++j)
++differ[s.substr(i + j * n, n)]; // 将子串加入到 differ 中并计数
// 遍历 words 中的每个单词，检查其在 differ 中的出现次数
for (string &word: words)
if (--differ[word] == 0) // 如果单词的计数减为 0，则从 differ 中删除
differ.erase(word);
// 内层循环，从起始位置 i 开始滑动窗口
for (int start = i; start < ls - m * n + 1; start += n) {
if (start != i) {
// 添加新进入窗口的单词到 differ 中
string word = s.substr(start + (m - 1) * n, n);//窗口右边加的单词
if (++differ[word] == 0)
differ.erase(word);
// 移除窗口左侧移出的单词
word = s.substr(start - n, n);
if (--differ[word] == 0)
differ.erase(word);
}
// 如果 differ 为空，表示当前窗口符合要求，将起始位置加入结果数组 res
if (differ.empty())
res.emplace_back(start);
}
}
return res; // 返回所有符合要求的起始位置数组
}
};
// 下面的代码用到了相应的模板，我觉得好理解一点
class Solution
{
public:
vector<int> findSubstring(string s, vector<string> &words)
{
vector<int> res; // 存储结果的数组
int n = words[0].size(), ls = s.size(); // 单词长度、字符串 s 的长度
unordered_map<string, int> need, window;
// 初始化 need 映射，记录每个单词在 words 中出现的次数
for (const string &ss : words)
need[ss]++;
// 处理不同的起始位置
for (int start = 0; start < n; ++start) // 这里不能写start+=n，因为s中的单词不一定是以n的长度进行变化的
{
int left = start, right = start;
window.clear(); // 每次从不同的下标进行寻找，都需要将window进行清零操作
int valid = 0; // 用来判断是否将初始下标加入到res中去
while (right + n <= ls) // 这里写right<=ls不对，因为这样s.substr(ringht,n)可能会超出ls的长度
{
string ss = s.substr(right, n); // 取出s中的一个单词
right += n;
if (need.count(ss)) // 要是ss是need中的一个单词
{
window[ss]++;
if (window[ss] == need[ss]) // 哈希表中的size记录的是独立元素的数量，而不是元素内部的计数字段
valid++;
// 当 window[ss] 大于 need[ss] 时，需要收缩窗口，此时移动left指针
while (window[ss] > need[ss])
{
string dd = s.substr(left, n);
left += n;
if (need.count(dd))
{
window[dd]--;
if (window[dd] == need[dd] - 1)
valid--;
}
}
}
else // 要是不是words中的一个单词，则重新开始进行查找，由于left到right范围内的都不满足了，因此直接将left指针移动到right的位置开始进行寻找。
{
left = right;
window.clear();
valid = 0;
}
// 当 valid 等于 need.size() 时，记录结果，并开始去除窗口中的元素
if (valid == need.size())
{
res.emplace_back(left);
string ddd = s.substr(left, n);
left += n;
if (need.count(ddd)) // 其实也可以不使用if语句判断，因为该元素必定在need中
{
window[ddd]--;
if (window[ddd] == need[ddd] - 1)
valid--;
}
}
}
}
return res;
}
};
76. 最小覆盖子串 - 力扣（LeetCode）
从一个网站上看到的这道题目的一个模板，现摘抄下来：
/* 滑动窗口算法框架 */
void slidingWindow(string s) {
// 用合适的数据结构记录窗口中的数据，根据具体场景变通
// 比如说，我想记录窗口中元素出现的次数，就用 map
// 我想记录窗口中的元素和，就用 int
unordered_map<char, int> window;
int left = 0, right = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
window.add(c)
// 增大窗口
right++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
// 注意在最终的解法代码中不要 print
// 因为 IO 操作很耗时，可能导致超时
printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (left < right && window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
window.remove(d)
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
// 有了上述模板，于是可以编写下面的代码
class Solution
{
public:
string minWindow(string s, string t)
{
unordered_map<char, int> need, window;
// need记录t中字符出现的次数，window记录窗口中出现的t中字符的次数
for (char c : t)
need[c]++;
int left = 0, right = 0;
int valid = 0; // 用来判断窗口是否需要收缩
int start = 0, len = INT_MAX;
while (right < s.size())
{
char c = s[right];// 右指针不断向前推进
right++;
if (need.count(c)) // 要是该字符在need中，也就是t中的一个字符
{
window[c]++;
if (window[c] == need[c]) // 表示c代表的字符是匹配的
valid++;
}
// 判断左侧窗口是否要收缩
while (valid == need.size())
{
// 在这里更新最小覆盖子串
if (right - left < len)
{
start = left;
len = right - left;
}
// d 是将要移出窗口的字符
char d = s[left];
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
if (need.count(d))
{
if (window[d] == need[d])
valid--;
window[d]--;
}
}
}
// 返回最小覆盖子串
return len == INT_MAX ? "" : s.substr(start, len);
}
};
36. 有效的数独 - 力扣（LeetCode）
题目对于我的主要难点，就是不知道用啥进行存储以便于实现，其实思路还是挺简单的，就是看行，看列，是否有行重复或者列重复或者子矩阵中有重复的元素。
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
int rows[9][9];
int columns[9][9];
int subboxes[3][3][9]; // 判断小矩阵中的元素是否超标，3*3*9=81，刚好符合
memset(rows,0,sizeof(rows));
memset(columns,0,sizeof(columns));
memset(subboxes,0,sizeof(subboxes));
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) {
char c = board[i][j];
if (c != '.') {
int index = c - '0' - 1;
rows[i][index]++;
columns[j][index]++;
subboxes[i / 3][j / 3][index]++; // 要是i与j均小于3的话，则就是在第一个小矩阵的进行运算，只有9个不同的元素，因此可以判断，
if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1)
return false;
}
}
return true;
}
};
// 或者也是可以有如下的解法
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
const int BOARD_SIZE = 9;
const int SUB_BOX_SIZE = 3;
vector<int> row(BOARD_SIZE, 0);
vector<int> col(BOARD_SIZE, 0);
vector<int> box(BOARD_SIZE, 0);
for (int i = 0; i < BOARD_SIZE; ++i) {
for (int j = 0; j < BOARD_SIZE; ++j) {
char c = board[i][j];
if (c != '.') {
int num = c - '0' - 1;
int boxIndex = (i / SUB_BOX_SIZE) * SUB_BOX_SIZE + j / SUB_BOX_SIZE;
if ((row[i] & (1 << num)) > 0 ||
(col[j] & (1 << num)) > 0 ||
(box[boxIndex] & (1 << num)) > 0) {
return false;
}
// Mark the number as used.
row[i] |= (1 << num);
col[j] |= (1 << num);
box[boxIndex] |= (1 << num);
}
}
}
return true;
}
};
54. 螺旋矩阵 - 力扣（LeetCode）
还是做题目做的太少了，这道题目唯一的想法如下：还是错的。。。
class Solution
{
public:
vector<int> spiralOrder(vector<vector<int>> &matrix)
{
int m = matrix.size();
int n = matrix[0].size();
vector<int> ans;
int i = 0, j = 0, sum = 0, temp = 1;
while (sum != m * n)
{
if (temp == 1)
{
if (i != n - 1)
{
ans.push_back(matrix[i][j]);
i += temp;
sum++;
}
if (i == n - 1)
{
ans.push_back(matrix[i][j]);
j += temp;
sum++;
if (j == m - 1)
temp *= -1;
}
}
if (temp == -1)
{
if (i != 0)
{
ans.push_back(matrix[i][j]);
i += temp;
sum++;
}
if (i == 0)
{
ans.push_back(matrix[i][j]);
j += temp;
sum++;
if (j == 0)
temp *= -1;
}
}
}
return ans;
}
};
上述错误的原因实在是太多了，我都不想再检查了，哎。看完题解，才知道这道题目如何进行解答。
题目中遍历矩阵的解法有上下左右四种走法，每种都有一个边界，因此不妨定义上(upper)下(down)左(left)右(right)四个指针。要是移动到某一个边界的话，该边界值+1或者-1表示向内部移动一个单位，并且判断遍历是否完成。基于上面的思想，代码如下：
class Solution
{
public:
vector<int> spiralOrder(vector<vector<int>> &matrix)
{
vector<int> ans;
if (matrix.empty())
return ans; // 若数组为空，直接返回答案
int upper = 0; // 赋值上下左右边界
int down = matrix.size() - 1; // 记录的是行数
int left = 0;
int right = matrix[0].size() - 1; // 记录的是列数
while (true)
{
for (int i = left; i <= right; ++i)
ans.push_back(matrix[upper][i]); // 向右移动直到最右
if (++upper > down)
break; // 重新设定上边界，若上边界大于下边界，则遍历遍历完成，下同
for (int i = upper; i <= down; ++i)
ans.push_back(matrix[i][right]); // 向下移动直到最下
if (--right < left)
break; // 重新设定右边界
for (int i = right; i >= left; --i)
ans.push_back(matrix[down][i]); // 向左
if (--down < upper)
break; // 重新设定下边界
for (int i = down; i >= upper; --i)
ans.push_back(matrix[i][left]); // 向上
if (++left > right)
break; // 重新设定左边界
}
return ans;
}
};
48. 旋转图像 - 力扣（LeetCode）
看到这道题目的第一眼，其实我也不知道这道题目究竟是考了啥，感觉又像是转置，又不像是转置，哎，不过仔细分析发现好像需要进行数学上面的分析，就前面所说，转置之后发现好像还是不是很像，但是仔细一看，好像将每一行再进行对应元素位置的交换好像就可以了，于是我的思路就出来了：将矩阵进行转置，然后再按照每一行进行对应元素的交换即可。
官方的答案给的过于复杂，不建议参考，主要是培养思维即可。
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int len = matrix.size();
for (int i = 0; i < len; i++)
for (int j = i + 1; j < len; j++)
swap(matrix[i][j], matrix[j][i]);
for (int i = 0; i < len; i++)
for (int j = 0; j < len/2; j++)
swap(matrix[i][j], matrix[i][len - j - 1]);
}
};
// 与上面的代码在数学上是等价的，也就是先将每一列对应位置的元素进行交换，然后在进行转置
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int len = matrix.size();
for (int i = 0; i < len; i++)
for (int j = 0; j < len / 2; j++)
swap(matrix[j][i], matrix[len - j - 1][i]);
for (int i = 0; i < len; i++)
for (int j = i + 1; j < len; j++)
swap(matrix[i][j], matrix[j][i]);
}
};
73. 矩阵置零 - 力扣（LeetCode）
主要就是需要区分哪些0是原来矩阵中就存在的元素，哪些0是后面改变得到的，因此有以下两种解法：
// 这是官方给的一个解答，主要的思想就是使用一个行数组，一个列数组，分别记录某一行或者某一列是否出现过0，要是出现过，则置成1，然后在循环遍历矩阵，要是找到某一个元素所对应的行数组或者列数组是1的话，直接将这个位置的元素置成0即可。
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<int> col(n), row(m); // 分别记录某一行是否出现过0元素
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (matrix[i][j] == 0) {
row[i] = 1;
col[j] = 1;
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (col[j] == 1 || row[i] == 1)
matrix[i][j] = 0;
}
};
// 方法二就是减少了空间复杂度，没有额外引入两个数组，而是使用第一行和第一列进行代替，同时只需要引入两个元素分别记录第一行和第一列的元素中是否有0即可。
class Solution
{
public:
void setZeroes(vector<vector<int>> &matrix)
{
int m = matrix.size(); // 记录行数
int n = matrix[0].size(); // 记录列数
int first_row_has_zero = 0; // 记录第一行是否有元素为0
int first_col_has_zero = 0; // 记录第一列是否有元素为0
for (int i = 0; i < m; i++)
if (matrix[i][0] == 0)
first_row_has_zero = 1;
for (int j = 0; j < n; j++)
if (matrix[0][j] == 0)
first_col_has_zero = 1;
for (int i = 0; i < m; i++) // 要是某一列有0出现，将该列的第一个元素置成0
for (int j = 0; j < n; j++)
if (matrix[i][j] == 0)
matrix[i][0] = 0;
for (int j = 1; j < n; j++) // 要是某一行有0出现，将该行的第一个元素置成0
for (int i = 1; i < m; i++)
if (matrix[i][j] == 0)
matrix[0][j] = 0;
for (int i = 1; i < m; i++)
if (matrix[i][0] == 0)
for (int j = 1; j < n; j++)
matrix[i][j] = 0;
for (int j = 1; j < n; j++)
if (matrix[0][j] == 0)
for (int i = 1; i < m; i++)
matrix[i][j] = 0;
if (first_row_has_zero == 1)
for (int i = 0; i < m; i++)
matrix[i][0] = 0;
if (first_col_has_zero == 1)
for (int j = 0; j < n; j++)
matrix[0][j] = 0;
}
};
// 下面的代码和上面的代码表达的意思是一样的，只是写的更加简洁一点
class Solution {
public:
void setZeroes(std::vector<std::vector<int>>& matrix) {
int m = matrix.size(); // 行数
int n = m ? matrix[0].size() : 0; // 列数
bool firstRowZero = false;
bool firstColZero = false;
// 检查第一行是否有0
for (int j = 0; j < n; ++j)
if (matrix[0][j] == 0) {
firstRowZero = true;
break;
}
// 检查第一列是否有0
for (int i = 0; i < m; ++i)
if (matrix[i][0] == 0) {
firstColZero = true;
break;
}
// 使用第一行和第一列作为标志位
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// 设置除第一行和第一列外的其他位置为0
for (int i = 1; i < m; ++i) {
if (matrix[i][0] == 0) {
for (int j = 1; j < n; ++j)
matrix[i][j] = 0;
}
}
for (int j = 1; j < n; ++j) {
if (matrix[0][j] == 0) {
for (int i = 1; i < m; ++i)
matrix[i][j] = 0;
}
}
// 设置第一行和第一列为0
if (firstRowZero) {
for (int j = 0; j < n; ++j)
matrix[0][j] = 0;
}
if (firstColZero) {
for (int i = 0; i < m; ++i)
matrix[i][0] = 0;
}
}
};
289. 生命游戏 - 力扣（LeetCode）
其实刚开始看到这道题目的时候，我想的是使用卷积的思想进行求解，但是突然发现我还是不太会写相关的代码，因此只能交给通义写出相类似的代码出来：
class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
int rows = board.size();
int cols = board[0].size();
vector<vector<int>> temp(rows, vector<int>(cols, 0));
// 卷积核
int kernel[3][3] = {{1, 1, 1},
{1, 0, 1},
{1, 1, 1}};
// 卷积操作
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
int liveNeighbors = 0;
for (int i = -1; i <= 1; ++i) {
for (int j = -1; j <= 1; ++j) {
if (kernel[i + 1][j + 1] == 0) continue; // 忽略中心点
int r = row + i;
int c = col + j;
if (r >= 0 && r < rows && c >= 0 && c < cols && board[r][c] == 1) {
liveNeighbors++;
}
}
}
// 根据生命游戏规则更新细胞状态
if (board[row][col] == 1 && (liveNeighbors == 3 || liveNeighbors == 2)) {
temp[row][col] = 1;
} else if (board[row][col] == 0 && liveNeighbors == 3) {
temp[row][col] = 1;
} else {
temp[row][col] = 0;
}
}
}
// 更新原数组
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
board[row][col] = temp[row][col];
}
}
}
};
但是我发现上述代码写的不是很好理解，于是我还有一种理解方式，就是复制一个一模一样的数组，对该数组进行处理，逐步更新原来数组中的细胞状态即可。但是我尽管想到了这种方式，我的代码想的比较的冗长，就是先将边界处理掉，然后在处理一般的情况，实际上，这是可以合并在一起进行处理的，也就是不需要分开处理，具体的实现方式如下：
// 复制的那一份永远不修改，只作为更新规则的引用。这样原始数组的细胞值就不会被污染了
class Solution
{
public:
void gameOfLife(vector<vector<int>> &board)
{
int neighbors[3] = {0, 1, -1}; // 用三个值计算当前细胞的八个邻居的位置
int rows = board.size();
int cols = board[0].size();
// 创建复制数组 copyBoard
vector<vector<int>> copyBoard(rows, vector<int>(cols, 0));
// 从原数组复制一份到 copyBoard 中
for (int row = 0; row < rows; row++)
for (int col = 0; col < cols; col++)
copyBoard[row][col] = board[row][col];
// 遍历面板每一个格子里的细胞
for (int row = 0; row < rows; row++)
{
for (int col = 0; col < cols; col++)
{
// 对于每一个细胞统计其八个相邻位置里的活细胞数量
int liveNeighbors = 0;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (!(neighbors[i] == 0 && neighbors[j] == 0)) // 要是当前考虑的细胞不是本身的细胞的话
{
int r = (row + neighbors[i]); // 计算当前细胞的邻居的坐标
int c = (col + neighbors[j]);
// 查看相邻的细胞是否是活细胞，同时细胞不能超出矩阵边界
if ((r < rows && r >= 0) && (c < cols && c >= 0) && (copyBoard[r][c] == 1))
liveNeighbors += 1;
}
// 规则 1 或规则 3
if ((copyBoard[row][col] == 1) && (liveNeighbors < 2 || liveNeighbors > 3))
board[row][col] = 0;
// 规则 4
if (copyBoard[row][col] == 0 && liveNeighbors == 3)
board[row][col] = 1;
}
}
}
};
// 上述代码复制了一个一模一样的数组进行处理，这样对于较大的数组来说空间复杂度就比较的高了，因此下面的代码不使用额外的数组进行求解，而是使用额外的状态进行标记
class Solution
{
public:
void gameOfLife(vector<vector<int>> &board)
{
int neighbors[3] = {0, 1, -1};
int rows = board.size();
int cols = board[0].size();
// 遍历面板每一个格子里的细胞
for (int row = 0; row < rows; row++)
{
for (int col = 0; col < cols; col++)
{
// 对于每一个细胞统计其八个相邻位置里的活细胞数量
int liveNeighbors = 0;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (!(neighbors[i] == 0 && neighbors[j] == 0))
{
// 相邻位置的坐标
int r = (row + neighbors[i]);
int c = (col + neighbors[j]);
// 查看相邻的细胞是否是活细胞，这里使用abs的原因是-1这个细胞状态其实之前是活的，需要在更新其周边的细胞的时候将其看成活的细胞进行处理。
if ((r < rows && r >= 0) && (c < cols && c >= 0) && (abs(board[r][c]) == 1))
liveNeighbors += 1;
}
// 规则 1 或规则 3
if ((board[row][col] == 1) && (liveNeighbors < 2 || liveNeighbors > 3))
// -1 代表这个细胞过去是活的现在死了
board[row][col] = -1;
// 规则 4
if (board[row][col] == 0 && liveNeighbors == 3)
// 2 代表这个细胞过去是死的现在活了
board[row][col] = 2;
}
}
// 遍历 board 得到一次更新后的状态
for (int row = 0; row < rows; row++)
for (int col = 0; col < cols; col++)
if (board[row][col] > 0)
board[row][col] = 1;
else
board[row][col] = 0;
}
};
383. 赎金信 - 力扣（LeetCode）
要是我不知道C++有unordered_map的话，这道题目我还真的不会做，但是我知道有这个东西的话，那就还是很简单的。当然，也是可以使用vector模拟哈希表的实现的。
class Solution
{
public:
bool canConstruct(string ransomNote, string magazine)
{
unordered_map<char, int> charCount;
for (char c : magazine)
charCount[c]++;
for (char c : ransomNote)
{
charCount[c]--;
if (charCount[c] < 0)
return false;
}
return true;
}
};
// 使用vector数组进行模拟哈希表的实现
class Solution
{
public:
bool canConstruct(string ransomNote, string magazine)
{
if (ransomNote.size() > magazine.size())
return false;
vector<int> cnt(26); // 用于计数 magazine 中字符的频率
// 计算 magazine 中字符的频率
for (auto &c : magazine)
cnt[c - 'a']++;
// 检查 ransomNote 中的字符是否都能被 magazine 中的字符覆盖
for (auto &c : ransomNote)
{
if (--cnt[c - 'a'] < 0)
return false; // 如果 magazine 中的字符不足，则返回 false
}
return true; // 如果所有字符都足够，则返回 true
}
};
205. 同构字符串 - 力扣（LeetCode）
上述的主要难点就是需要建立一个双向映射，也就是双射。因此，需要选择使用两个哈希表，分别建立映射关系。
class Solution
{
public:
bool isIsomorphic(string s, string t)
{
// 如果两个字符串长度不相等，直接返回 false
if (s.length() != t.length())
return false;
unordered_map<char, char> mapSToT; // 用于存储从 s 到 t 的映射关系
unordered_map<char, char> mapTToS; // 用于存储从 t 到 s 的映射关系
for (size_t i = 0; i < s.length(); ++i)
{
char sChar = s[i]; // 获取 s 中的当前字符
char tChar = t[i]; // 获取 t 中的当前字符
// 检查是否有从 s 到 t 的映射关系
if (mapSToT.find(sChar) == mapSToT.end()) // 如果 s 中的字符还没有映射
{
// 检查 t 中的当前字符是否已经映射到另一个 s 中的字符
if (mapTToS.find(tChar) != mapTToS.end())
return false; // 如果 t 中的当前字符已经映射到另一个 s 中的字符，返回 false
// 建立映射关系
mapSToT[sChar] = tChar; // 在 mapSToT 中建立映射
mapTToS[tChar] = sChar; // 在 mapTToS 中建立映射
}
else
{
// 如果已经有映射关系，检查当前映射是否一致
if (mapSToT[sChar] != tChar)
return false; // 如果映射不一致，返回 false
}
}
// 如果所有字符都符合映射规则，则返回 true
return true;
}
};
class Solution
{
public:
bool isIsomorphic(string s, string t)
{
// 如果两个字符串长度不相等，直接返回 false
if (s.length() != t.length())
return false;
unordered_map<char, char> mapSToT; // 用于存储从 s 到 t 的映射关系
unordered_map<char, char> mapTToS; // 用于存储从 t 到 s 的映射关系
for (size_t i = 0; i < s.length(); ++i)
{
char sChar = s[i]; // 获取 s 中的当前字符
char tChar = t[i]; // 获取 t 中的当前字符
if ((mapSToT.count(sChar) && mapSToT[sChar] != tChar) ||
(mapTToS.count(tChar) && mapTToS[tChar] != sChar))
// 如果 sChar 已经有映射，并且当前的映射不符合，或者如果 tChar 已经有映射，并且当前的映射不符合 则返回 false
return false;
// 建立映射关系
mapSToT[sChar] = tChar; // 在 mapSToT 中建立映射
mapTToS[tChar] = sChar; // 在 mapTToS 中建立映射
}
// 如果所有字符都符合映射规则，则返回 true
return true;
}
};
290. 单词规律 - 力扣（LeetCode）
要是做过上面的题目，其实这道题目和上面的题目很类似的，只是需要将char换成String，同时也需要将s中的单词按照空格一个一个的提取出来。其实也是可以使用双指针一个一个的取的，但是这样比较的麻烦，还是使用C++中提供的istringstream进行处理比较的简单。
class Solution
{
public:
bool wordPattern(string pattern, string s)
{
istringstream iss(s); // 通过 iss，我们可以像处理输入流一样逐个单词地读取 s 中的数据
vector<string> tokens;
for (string token; iss >> token;) // >> 操作符用于提取数据
tokens.push_back(token); // 循环条件 iss >> token; 只要还能读取到单词就继续执行
// 如果两个字符串长度不相等，直接返回 false
// 下面注释起来的代码也是可以进行
// vector<string> tokens;
// int i = 0, j = 0;
// while (j <= s.length()) // 修改为 <= ，以便处理最后一个单词
// {
// if (j == s.length() || s[j] == ' ') // 处理最后一个单词或遇到空格
// {
// tokens.push_back(s.substr(i, j - i));
// i = j + 1;
// }
// j++;
// }
if (tokens.size() != pattern.length())
return false;
unordered_map<char, string> map_pTos; // 用于存储从 s 到 t 的映射关系
unordered_map<string, char> map_sTop; // 用于存储从 t 到 s 的映射关系
for (size_t i = 0; i < pattern.length(); ++i)
{
char pChar = pattern[i]; // 获取pattern中的当前字符
string s_string = tokens[i]; // 获取 s 中的当前字符串
if ((map_pTos.count(pChar) && map_pTos[pChar] != s_string) ||
(map_sTop.count(s_string) && map_sTop[s_string] != pChar))
return false;
map_pTos[pChar] = s_string;
map_sTop[s_string] = pChar;
}
// 如果所有字符都符合映射规则，则返回 true
return true;
}
};
242. 有效的字母异位词 - 力扣（LeetCode）
要是你会使用哈希表的话，就是一个unordered_map的使用，就可以解决掉这道题目了，但是需要注意的是，啥叫字母异位词。字母异位词就是字符是相同的，只是顺序有些许改变，因此也是可以使用排序进行解题的。
class Solution
{
public:
bool isAnagram(string s, string t)
{
if (s.length() != t.length())
// 这个条件判断要是不加的话，实际上就不对了，比如 s="ab" , t="a"，这样的话，后面的代码就是不对的。
return false;
unordered_map<char, int> Char_count;
for (auto &c : s)
Char_count[c]++;
for (auto &c : t)
if (--Char_count[c] < 0)
return false;
return true;
}
};
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.length() != t.length())
return false;
sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;
}
};
202. 快乐数 - 力扣（LeetCode）
这道题我是看了解析才会做的，答案就是使用了一个快慢指针进行运算，就像是跑步一样，跑的快的在某一个时刻一定会追上跑得慢的，这里也是一样，快指针在某一时刻一定会和慢指针指向同一个数字，这样的话，要是指向的数字是1的话，表示是一个快乐数，要是不是1的话，表示进入了一个循环，这样就不是一个快乐数。
class Solution
{
public:
int bitSquareSum(int n) // 用来取出来每一个位置的数字进行平方运算
{
int sum = 0;
while (n > 0)
{
int bit = n % 10;
sum += bit * bit;
n = n / 10;
}
return sum;
}
bool isHappy(int n)
{
int slow = n, fast = n; // 使用两个指针，一个快指针，一个慢指针，快指针走两步，慢指针走一步
do
{
slow = bitSquareSum(slow);
fast = bitSquareSum(fast);
fast = bitSquareSum(fast);
} while (slow != fast);
return slow == 1;
}
};
// 当然，还是可以使用哈希表进行运算的，还是需要编写一个函数将每一个位置的数进行平方求和，然后创建一个哈希表，将每一个n插入，要是n进行运算后得到的数字不等于1或者该数字不在哈希表中的话，进行循环，直到不满足循环的条件即可
class Solution {
public:
// 获取下一个数
int getNext(int n) {
int sum = 0;
while (n > 0) {
int bit = n % 10;
sum += bit * bit;
n = n / 10;
}
return sum;
}
// 判断是否为快乐数
bool isHappy(int n) {
unordered_set<int> seen;
while (n != 1 && seen.find(n) == seen.end()) {
// 使用 end() 方法来检查元素是否存在，要是存在的话，说明和之前的数字形成了一个循环，要是这个循环中没有1的话，就直接返回false，要是有1的话，返回true即可
seen.insert(n);
n = getNext(n);
}
return n == 1;
}
};
219. 存在重复元素 II - 力扣（LeetCode）
// 第一个代码是我能够想到的，就是使用一个哈希表，先将前k个元素存储进哈希表中，要是有重复的元素直接就返回true即可，然后再使用两个指针，初始时一个指向0位置，一个指向k+1的位置，然后都同时向后移动，两个指针的距离保持k+1，要是移出这个范围内的元素直接减掉即可，要是进入这个范围内的元素直接相加即可。然后再看有没有相同的元素。
class Solution
{
public:
bool containsNearbyDuplicate(vector<int> &nums, int k)
{
unordered_map<int, int> num_count;
for (int i = 0; i <= k && i < nums.size(); i++)
{
num_count[nums[i]]++;
if (num_count[nums[i]] > 1)
return true;
}
for (int i = 0, j = k + 1; j < nums.size(); j++, i++)
{
num_count[nums[i]]--;
num_count[nums[j]]++;
if (num_count[nums[j]] > 1)
return true;
}
return false;
}
};
// 下面的代码是不对的，我其实是想使用vector代替哈希表的，但是这样的话，vector不能直接表示负数，需要使用偏移来进行表示，因此不行，除非找出最大值和最小值，然后用其进行偏移才行。
// nums 向量的长度最大可达 100,000，每个元素的值可以在 -1,000,000,000 到 1,000,000,000 之间，而 k 的最大值也可以达到 100,000。在这种情况下，直接使用 vector<int> 来存储计数是不可行的，因为可能的整数值范围太大，无法合理地用一个足够大的 vector 来表示所有的整数。
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
int n = nums.size();
vector<int> num_count(n, 0);
for (int i = 0; i <= k && i < nums.size(); i++)
if (++num_count[nums[i]] > 1)
return true;
for (int i = 0, j = k + 1; j < nums.size(); i++, j++) {
num_count[nums[i]]--;
if (++num_count[nums[j]] > 1)
return true;
}
return false;
}
};
// 当然，也可以只使用一个指针进行操作
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int, int> index_map; // 存储元素及其最后出现的位置
for (int i = 0; i < nums.size(); ++i) {
if (index_map.find(nums[i]) != index_map.end()) {
// 如果元素已经出现过，检查是否在 k 的范围内
if (i - index_map[nums[i]] <= k)
return true;
}
index_map[nums[i]] = i; // 更新元素的最新位置
}
return false;
}
};
// 当然，也是可以使用哈希集合进行求解的
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_set<int> s; // 创建一个无序集合用来存储最近 k 个元素
int length = nums.size();
for (int i = 0; i < length; i++) { // 必须要先移除，然后再添加进行判断，不然就不对了
if (i > k) { // 当 i > k 时，移除最早添加到集合中的元素
s.erase(nums[i - k - 1]);
}
if (s.count(nums[i])) { // 检查当前元素是否已经在集合中
return true;
}
s.emplace(nums[i]); // 将当前元素添加到集合中
}
return false; // 如果循环结束都没有找到重复元素，返回 false
}
};
228. 汇总区间 - 力扣（LeetCode）
下面写法的好处是，无需特判 nums 是否为空，也无需在循环结束后，再补上处理最后一段区间的逻辑。以我的经验，这种写法是所有写法中最不容易出 bug 的，推荐大家记住。
适用场景：按照题目要求，数组会被分割成若干段，且每一段的判断/处理逻辑是一样的。
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
vector<string> ret;
int i = 0;
int n = nums.size();
while (i < n) {
int low = i;
i++;
while (i < n && nums[i] == nums[i - 1] + 1)
i++;
int high = i - 1;
string temp = to_string(nums[low]);
if (low < high) {
temp.append("->");
temp.append(to_string(nums[high]));
}
ret.push_back(move(temp)); // 其实这里加不加move都是可以的
// 使用 std::move 将 temp 移动到 ret 向量中。由于 temp 在此之后不再使用，使用 std::move 是合适的。
}
return ret;
}
};
56. 合并区间 - 力扣（LeetCode）
我感觉我在某些地方看见过这道题目，但是就是没有印象了，包括如何解题都忘记了。没办法，再学习一下吧：题目给出的二维数组是没有排序的，因此我们可以对每个区间的起始位置进行排序，这样处理的话会比较的简单一点。
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) // 要是数组为空的话，直接返回一个空的数组即可
return {};
// 按照区间起始位置排序
sort(intervals.begin(), intervals.end());
vector<vector<int>> result;
result.push_back(intervals[0]); // 先将排序后的第一个元素的start存储进入数组中去
for (const auto& interval : intervals) {
int current_start = interval[0];
int current_end = interval[1];
int last_end = result.back()[1];
// 如果当前区间的开始位置小于等于上一个区间的结束位置，则存在重叠
if (current_start <= last_end)
// 更新上一个区间的结束位置为当前区间的结束位置和上一个区间的结束位置中的较大者
result.back()[1] = max(current_end, last_end);
else
// 如果没有重叠，将当前区间添加到结果集中
result.push_back(interval);
}
return result;
}
};
// 下面是官方给出来的答案
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.size() == 0)
return {};
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
for (int i = 0; i < intervals.size(); ++i) {
int L = intervals[i][0], R = intervals[i][1]; // 先取出来当前区间的起始位置和终止位置
if (!merged.size() || merged.back()[1] < L)
// 要是数组中没有元素或者下一个区间的起始位置大于上一个区间的终止位置的话，直接将当前区间放入数组即可
merged.push_back({L, R});
else
merged.back()[1] = max(merged.back()[1], R); // 要是重叠的话，看是谁的终止位置的大一点
}
return merged;
}
};
57. 插入区间 - 力扣（LeetCode）
由于做过上面的题目，因此我的第一个想法就是将新给的区间放在原来的区间中，然后对所有的区间进行排序，然后再使用上面的算法思想就可以进行解决了。
class Solution
{
public:
vector<vector<int>> insert(vector<vector<int>> &intervals, vector<int> &newInterval)
{
vector<vector<int>> ans;
intervals.push_back(newInterval); // 将新的区间插入到区间列表中的最后
sort(intervals.begin(), intervals.end()); // 对区间列表重新按照区间起始位置进行排序
ans.push_back(intervals[0]);
for (auto &interval : intervals)
{
int current_begin = interval[0];
int current_end = interval[1];
int last_end = ans.back()[1];
if (current_begin <= last_end)
ans.back()[1] = max(last_end, current_end);
else
ans.push_back(interval);
}
return ans;
}
};
听说这道题目是2024.8.15腾讯一面的算法题，因此肯定不能像上面这样如此简单的处理，官方给出了一种思想，可以学习一下：
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
int left = newInterval[0]; // 记录新插入的区间的左端点
int right = newInterval[1]; // 记录新插入的区间的右端点
bool placed = false; // false表示还没有合并到区间列表中去
vector<vector<int>> ans;
for (const auto& interval : intervals) {
if (interval[0] > right) {
// 在插入区间的右侧且无交集
if (!placed) {
ans.push_back({left, right}); // 这里需要使用区间的形式进行插入，不能直接使用newInterval的形式，因为后面的代码可能会将其区间的左右边界进行改变的。
placed = true; // 插入进去之后，就需要将placed置成true了，防止后面的代码出错
}
ans.push_back(interval); // 直接将新的区间插入进去即可，因为没有重叠的部分
} else if (interval[1] < left) {
// 在插入区间的左侧且无交集 ，在左边嘛，肯定是要先插入这个区间的，而不是插入新给的区间
ans.push_back(interval);
} else {
// 与插入区间有交集，计算它们的并集
left = min(left, interval[0]);
right = max(right, interval[1]);
}
}
if (!placed) // 如果新区间没有被放置，那么就放置在最后
ans.push_back({left, right}); // 这里也是一样，需要使用区间的形式进行插入，除非将newInterval的左右边界进行改变才行。
return ans;
}
};
452. 用最少数量的箭引爆气球 - 力扣（LeetCode）
看到这道题目的第一眼，我就知道需要将区间进行排序，然后再不断的合并重复的区间，直到区间最终无法合并，最后区间的数量就是需要返回箭的数量。但是这道题目需要注意的是，和之前的合并区间问题不一样，合并区间后去最大的区间值，而这里合并后是取最小的区间值进行求解的。
class Solution
{
public:
int findMinArrowShots(vector<vector<int>> &points)
{
vector<vector<int>> ans;
sort(points.begin(), points.end()); // 这里选择按照区间的左端点进行排序。
ans.push_back(points[0]);
for (const auto &point : points)
{
int current_start = point[0];
int current_end = point[1];
int last_end = ans.back()[1];
if (current_start <= last_end)
ans.back()[1] = min(last_end, current_end); // 合并区间是求出来最大值，这里是求出来最小值 。
else
ans.push_back(point);
}
return ans.size();
}
};
// 不使用二维数组的实现方式
class Solution
{
public:
int findMinArrowShots(vector<vector<int>> &points)
{
sort(points.begin(), points.end()); // 这里选择按照区间的左端点进行排序。
int ans = 1;
int pos = points[0][1];
for (const auto &point : points)
{
if (pos < point[0])
{
ans++;
pos = point[1];
}
else
pos = min(pos, point[1]);
}
return ans;
}
};
// 当然，还可以按照区间的右端点进行排序，这样处理的话就更加的简单了
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
// 按照结束位置排序
sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) {
return a[1] < b[1];
});
// 初始化第一个区间
vector<int> currentRange = points[0];
int arrows = 1; // 至少需要一支箭
for (const auto& point : points) {
// 如果当前区间不能覆盖新点，则需要新增一个区间
if (point[0] > currentRange[1]) {
arrows++;
currentRange = point;
} else
// 否则更新当前区间的结束位置
currentRange[1] = min(currentRange[1], point[1]);
}
return arrows;
}
};
// 下面是官方给出来的解答
class Solution
{
public:
int findMinArrowShots(vector<vector<int>> &points)
{
sort(points.begin(), points.end(), [](const vector<int> &u, const vector<int> &v)
// 按照每个区间的右边界进行升序排序
{ return u[1] < v[1]; });
int pos = points[0][1];
int ans = 1; // 第一个气球肯定是要一个箭的
for (const vector<int> &balloon : points)
if (balloon[0] > pos)
// 要是某一个位置的气球的起始区间超过了当前气球位置的终止区间，说明箭的数量需要增加一个，然后将pos移到新的区间终止位置上
{
pos = balloon[1]; // 当前位置移动到新区间的终止位置上
++ans; // 箭的数量加一
}
return ans;
}
};
20. 有效的括号 - 力扣（LeetCode）
这是一道有关于栈的简单题目，但是我的栈还是不太熟悉，因此这道题目可以很好的帮助我进行栈的学习。
首先就是需要明白题目的意思，这里有效的括号指的是，必须是配对的形式出现的括号，不能是错开的形式，比如：需要满足下面的条件{}()[],而不能是({[}]),虽然这也是有效的括号吧，但是题目不是这样要求的，并且要是这样的话，题目的难度就会变得不一样了，因此题目是要求我们实现前面的一种情况。
理解完题目意思后，就会变得比较的简单了，也就是先将s中的每一个元素压入栈中，要是是形如’(‘,’[‘,’{‘这样的字符，直接压入栈中，要是是形如’)‘’]‘’}',就需要判断其与栈顶元素是不是配对的，要是配对的话，直接弹出栈顶元素，开启下一次的判断，要是没有配对成功的话，直接返回false即可。因此很容易想到代码如下：
class Solution {
public:
bool isValid(string s) {
stack<int> st;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(' || s[i] == '{' || s[i] == '[')
st.push(i);
else {
if (st.empty())
// 这一句表示的是，既不是三种左括号，同时栈中也是没有元素的，这样的话，是肯定不会匹配的，直接返回false即可。
return false;
if (s[i] == ')' && s[st.top()] != '(')
return false;
if (s[i] == '}' && s[st.top()] != '{')
return false;
if (s[i] == ']' && s[st.top()] != '[')
return false;
st.pop(); // 要是配对成功的话，直接弹出当前栈顶元素
}
}
return st.empty(); // 最后，要是栈中元素为空的话，表示全部配对成功，要是还有元素的话，表示配对失败
}
};
当然，上述代码是很好理解的，也是很直观的，但是往往好理解的代码扩展性不是很好，比如我要是再引入一个新的括号对<>，这样的话，需要修改的地方就会很多，也就是修改会很麻烦，也很容易出错。
因此，我们代码有一个设计原则OCP原则：即对扩展开放，对修改关闭。
因此官方给出来的代码具有很好的健壮性与可扩展性：
class Solution {
public:
// 定义一个公共成员函数来检查一个字符串中的括号是否有效
bool isValid(string s) {
// 获取字符串的长度
int n = s.size();
// 如果字符串长度为奇数，则直接返回false，因为配对的括号必然是偶数个
if (n % 2 == 1)
return false;
// 使用unordered_map来存储括号对及其关系
unordered_map<char, char> pairs = {
{')', '('}, // 将右括号映射到对应的左括号
{']', '['},
{'}', '{'}
// {'>', '<'} 要是有新的种类的括号对需要进行扩展的话，直接加上这一句代码即可，即可扩展性很好
};
// 使用栈来帮助检查括号的有效性
stack<char> stk;
// 遍历字符串中的每一个字符
for (char ch: s) {
// 如果当前字符是右括号
if (pairs.count(ch)) {
// 如果栈为空或者栈顶元素不是当前右括号对应的左括号，表示无法进行配对，则返回false
if (stk.empty() || stk.top() != pairs[ch])
return false;
// 否则弹出栈顶元素（即匹配了当前右括号的左括号）
stk.pop();
}
else
// 如果当前字符是左括号，将其压入栈中
stk.push(ch);
}
// 如果遍历完字符串后栈为空，说明所有括号都被正确地配对了，返回true
return stk.empty();
}
};
71. 简化路径 - 力扣（LeetCode）
这道题目主要还是需要看懂题目的意思，也就是需要理解题目中说的Unix的风格。首先就是需要编写一个函数，表示将输入的原来的字符串通过"/“进行分割，然后再依次对分割后的元素进行处理即可，即：遇到”…“且栈不为空的话，弹出栈顶元素，遇到”.“，不进行任何处理，其余的直接压入栈中即可。然后在对处理好的字符串使用”/"进行拼接即可
class Solution
{
public:
// 函数声明：简化输入的Unix风格的绝对路径字符串
string simplifyPath(string path)
{
// 定义一个lambda表达式用于分割字符串，当然，也是可以写一个lambda函数的，而不用该表达式
auto split = [](const string &s, char delim) -> vector<string>
{
vector<string> ans; // 创建一个字符串向量来存储结果
string cur; // 当前正在构建的子字符串
// 遍历输入字符串中的每一个字符
for (char ch : s)
{
// 如果当前字符等于指定的分隔符
if (ch == delim)
{
ans.push_back(move(cur)); // 将当前子字符串加入到结果向量中，并清空当前子字符串
cur.clear();
}
else
cur += ch; // 否则将当前字符添加到当前子字符串中
}
ans.push_back(move(cur)); // 最后将剩余的子字符串加入到结果向量中
return ans; // 返回结果向量
};
// 使用定义的lambda表达式来分割输入的路径字符串
vector<string> names = split(path, '/');
// 创建一个栈用来存储有效的路径片段
vector<string> stack;
// 遍历每个路径片段
for (string &name : names)
{
if (name == "..")
{ // 如果片段为'..'并且栈非空，则弹出栈顶元素（即回退一层目录）
if (!stack.empty())
stack.pop_back();
// 如果片段非空且不是'.'
}
else if (!name.empty() && name != ".")
stack.push_back(move(name)); // 将有效片段压入栈中
}
// 构建最终简化后的路径
string ans;
if (stack.empty()) // 如果栈为空，说明在根目录
ans = "/";
else
// 否则遍历栈中的所有有效片段并拼接成路径
for (string &name : stack)
ans += "/" + name; // 注意这里使用了`+`而非`+=`是因为`name`并未用move语义传递
return ans; // 返回构建好的路径
}
};
155. 最小栈 - 力扣（LeetCode）
我看后面的评论说的是，这道题目面试的时候也是考过的，因此还是需要大概的套路的，本题需要常数时间将栈中的最小元素找出来，下面是一种可以想到的方法：
因此可以编写代码如下：
class MinStack
{
stack<int> stk; // 定义的一个元素栈
stack<int> min_stk; // 定义的一个辅助栈，与上述定义的元素栈同步插入与删除
public:
MinStack() {}
void push(int val)
{
stk.push(val);
if (min_stk.empty())
min_stk.push(val);
else
{
min_stk.push(min(val, min_stk.top()));
}
}
// MinStack() { min_stk.push(INT_MAX); } 这些代码是可以和上面的代码进行互换的
// void push(int val) {
// stk.push(val);
// min_stk.push(min(val, min_stk.top()));
// }
void pop()
{
stk.pop();
min_stk.pop();
}
int top() { return stk.top(); }
int getMin() { return min_stk.top(); }
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
当然，上述代码使用了两个栈，一个元素栈，一个辅助栈，其实也可以只使用一个栈进行求解的，这个栈同时保存的是每个数字 x 进栈的时候的值 与 插入该值后的栈内最小值。即每次新元素 x 入栈的时候保存一个元组：（当前值 x，栈内最小值）。这个元组需要看成一个整体，同时进栈和出栈，即保证栈顶同时有值和栈内最小值。其实和上述思路本质上还是一样的，只是少创建了一个辅助栈。
class MinStack {
private:
stack<pair<int, int>> stk;
public:
MinStack() {}
void push(int val) {
if (stk.size() == 0)
stk.push({val, val});
else
stk.push({val, min(val, stk.top().second)});
}
void pop() { stk.pop(); }
int top() { return stk.top().first; }
int getMin() { return stk.top().second; }
};
150. 逆波兰表达式求值 - 力扣（LeetCode）
主要还是需要看懂题目需要表达的意思，这里的逆波兰表达式是一种后缀表达式，同时表达式中去掉括号后也是没有影响的。因此可以使用栈和数组进行实现：
class Solution {
public:
bool isNumber(string& token) {
return !(token == "+" || token == "-" || token == "*" || token == "/");
}
int evalRPN(vector<string>& tokens) {
stack<int> stk;
for (string& token : tokens) {
if (isNumber(token)) // 要是这个字符串是一个数字的话，直接压入栈中即可
stk.push(stoi(token));
else {
int num2 = stk.top();
stk.pop();
int num1 = stk.top();
stk.pop();
if (token == "+")
stk.push(num2 + num1);
if (token == "-")
stk.push(num1 - num2);
if (token == "*")
stk.push(num1 * num2);
if (token == "/")
stk.push(num1 / num2);
}
}
return stk.top();
}
};
// 下面是使用数组模拟栈进行实现:
class Solution {
public:
int evalRPN(vector<string>& tokens) {
int n = tokens.size();
vector<int> stk((n + 1) / 2); // 一个长为n的表达式最多有(n+1)/2个数字
int index = -1;
for (string& token : tokens) {
if (isdigit(token[0]) || token.length() > 1) {
index++;
stk[index] = stoi(token);
} else {
if (token == "+") {
index--;
stk[index] += stk[index + 1];
}
if (token == "-") {
index--;
stk[index] -= stk[index + 1];
}
if (token == "*") {
index--;
stk[index] *= stk[index + 1];
}
if (token == "/") {
index--;
stk[index] /= stk[index + 1];
}
}
}
return stk[index];
}
};
224. 基本计算器 - 力扣（LeetCode）
这道题好像也是某些大厂一面的一道原题，因此还是有必要将其搞明白的。我肯定还是一样，不会写的，因此参考了官方的题目解析，我得出了如下的解题方法：由于字符串除了数字和括号外，只有加号和减号两种运算符，因此可以考虑将括号进行展开，则这样的话，数字本身是不会发生变化的，只是数字前面的符号会发生变化。这题主要还是结合了题目的具体语境了的，要是还有乘除法，阶乘啥的话，这样处理就肯定不是很对了，这样就需要重新选择比较好的方式进行处理了。
class Solution {
public:
// 计算给定字符串表达式的值
int calculate(string s) {
// 使用栈来保存操作数的符号
stack<int> ops;
// 默认初始符号为正
ops.push(1);
// 当前计算结果
int sign = 1;
// 最终返回的结果
int ret = 0;
// 字符串长度
int n = s.length();
// 遍历字符串中的每个字符
for (int i = 0; i < n;) {
// 如果遇到空格，则忽略它
if (s[i] == ' ')
i++;
// 如果是加号，则当前符号为栈顶的符号
else if (s[i] == '+') {
sign = ops.top();
i++;
}
// 如果是减号，则当前符号为栈顶符号的相反数
else if (s[i] == '-') {
sign = -ops.top();
i++;
}
// 如果是左括号，则将当前符号压入栈中
else if (s[i] == '(') {
ops.push(sign);
i++;
}
// 如果是右括号，则弹出栈顶的符号
else if (s[i] == ')') {
ops.pop();
i++;
}
// 如果是数字，则开始读取数字
else {
long num = 0;
// 就是可能存在数字有多位的情况，因此这里需要处理多位数的情况
while (i < n && s[i] >= '0' && s[i] <= '9') {
// 构造数字
num = num * 10 + s[i] - '0';
i++;
}
// 更新最终结果
ret += sign * num;
}
}
// 返回计算结果
return ret;
}
};
141. 环形链表 - 力扣（LeetCode）
这道题目还是很简单的，就是拿来练练手的，我首先想到的就是使用哈希表进行实现，也就是循环遍历链表，要是遇到一个节点，就去判断该节点之前是否被访问过。要是访问过，这相当于存在一个环形链表，要是遍历完链表都没有找到的话，表示不存在这样的环形链表。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
// 其实这里只需要跟踪某些项的存在与否，因此实际上 unordered_set 就足够了
bool hasCycle(ListNode* head) {
unordered_set<ListNode*> seen;
while (head != nullptr) {
if (seen.count(head))
return true;
seen.insert(head);
head = head->next;
}
return false;
}
};
// 当然，这里使用unordered_set也是可以的，实际上这样是没有必要的，因为unordered_map存储的是与这些项相关的信息
class Solution {
public:
bool hasCycle(ListNode* head) {
unordered_map<ListNode*, int> seen;
while (head != nullptr) {
if (seen.count(head))
return true;
seen[head]++;
head = head->next;
}
return false;
}
};
// 除了使用哈希表之外，还可以使用快慢指针进行查找，关于快慢指针的思想，前面有所提及，这里就不在赘述。
class Solution {
public:
bool hasCycle(ListNode* head) {
if (head == nullptr || head->next == nullptr)
return false;
ListNode* slow = head;
ListNode* fast = head->next;
while (slow != fast) {
if (fast == nullptr || fast->next == nullptr)
return false;
slow = slow->next;
fast = fast->next->next;
}
return true;
}
};
2. 两数相加 - 力扣（LeetCode）
我的想法就是创建一个新的链表，然后对链表每个位置上的值进行相加。要是有进位就使用一个标志位进行表示，然后如此计算即可
class Solution {
public:
// 主要方法，用于计算两个链表表示的数字之和，并以链表形式返回结果
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
// 创建一个哑节点作为新链表的头节点，方便操作
ListNode dummyHead(0);
// 使用一个指针指向这个哑节点
ListNode* result = &dummyHead;
// 初始化进位值为0
int carry = 0;
// 当两个输入链表至少有一个不为空时，进入循环
while (l1 != nullptr || l2 != nullptr) {
// 如果当前l1不为空，则获取其值；否则默认值为0
int val1 = (l1 != nullptr) ? l1->val : 0;
// 如果当前l2不为空，则获取其值；否则默认值为0
int val2 = (l2 != nullptr) ? l2->val : 0;
// 计算当前位的值和进位值
int sumVal = val1 + val2 + carry;
// 更新进位值
carry = sumVal / 10;
// 取模得到当前位的值
sumVal %= 10;
// 创建一个新的节点，值为当前位的结果，并连接到结果链表的末尾
result->next = new ListNode(sumVal);
// 移动result指针到刚刚添加的新节点
result = result->next;
// 如果l1不为空，则移动到下一个节点
if (l1 != nullptr) l1 = l1->next;
// 如果l2不为空，则移动到下一个节点
if (l2 != nullptr) l2 = l2->next;
}
// 如果最后还有进位值，则创建一个新的节点，值为进位值，并添加到结果链表的末尾
if (carry > 0)
result->next = new ListNode(carry);
// 返回新链表的第一个有效节点（跳过哑节点）
return dummyHead.next;
}
};
21. 合并两个有序链表 - 力扣（LeetCode）
上述的题目我觉得还是很简单的，但是我由于不熟悉链表的相关操作，导致我还是不太会做这样的题目，还是需要看题目的解析的。
我看题目的解析给了两种方式进行实现，一种就是我想到的：新建立一个链表，然后逐个比较原来的链表值，谁小谁就放进新链表中区，第二种方式就是使用递归的方法进行实现，这个实在是巧妙，我难以描述，直接上代码吧，我也还是很震撼的。
// 首先展示的是使用递归的方式进行实现的代码，递归的主要思想就是：两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并
class Solution
{
public:
ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
{
if (list1 == nullptr)
return list2;
else if (list2 == nullptr)
return list1;
else if (list1->val < list2->val)
{
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}
else
{
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
};
// 上面的代码比较的优美，实在是难以想到，下面的代码才是我能够想到的
class Solution
{
public:
ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
{
if (list1 == nullptr)
return list2;
if (list2 == nullptr)
return list1;
ListNode *head = new ListNode(0); // 新建一个节点，到时候直接返回该节点即可
ListNode *curr = head; // 不断移动的指针，用于向新节点中添加元素
while (list1 != nullptr && list2 != nullptr)
{
int val = 0;
if (list1->val <= list2->val)
{
val = list1->val;
list1 = list1->next;
}
else
{
val = list2->val;
list2 = list2->next;
}
curr->next = new ListNode(val);
curr = curr->next;
}
if (list1 == nullptr)
curr->next = list2;
else if (list2 == nullptr)
curr->next = list1;
return head->next;
}
};
138. 随机链表的复制 - 力扣（LeetCode）
这道题要是每个节点只有一个next指针而没有随机指针的话，这道题目还是很好做的，但是这有一个随机指针了，导致就不能按照顺序进行链表的复制了。
// 第一种方法是官方给出的回溯+哈希表进行求解
class Solution {
public:
// 使用一个哈希表来缓存原始节点与新复制节点之间的映射关系
unordered_map<Node*, Node*> cachedNode;
// 定义深拷贝函数，参数为原链表的头结点
Node* copyRandomList(Node* head) {
// 如果原链表为空，则返回空指针
if (head == nullptr)
return nullptr;
// 检查当前节点是否已经复制过
if (!cachedNode.count(head)) {
// 创建一个新的节点，并将原节点的值赋给新节点
Node* headNew = new Node(head->val);
// 在缓存中记录新旧节点的映射关系
cachedNode[head] = headNew;
// 递归地复制当前节点的下一个节点，并连接到新节点的next指针上
headNew->next = copyRandomList(head->next);
// 递归地复制当前节点的随机指向节点，并连接到新节点的random指针上
headNew->random = copyRandomList(head->random);
}
// 返回当前节点的副本
return cachedNode[head];
}
};
// 还有一种方法我觉得也是很好的，就是先使用哈希表克隆所有的节点，然后再遍历克隆next和random指针
class Solution {
public:
// 声明一个哈希表用于存储原节点和其克隆节点的对应关系
unordered_map<Node*, Node*> hmap;
// 定义一个函数用来复制带随机指针的链表
Node* copyRandomList(Node* head) {
Node *p = head; // p指向原链表的头节点
// 第一步：遍历原链表并创建所有克隆节点
// 将原节点及其对应的克隆节点添加到哈希表中
while (p) {
hmap.insert({p, new Node(p->val)}); // 创建新节点并插入到哈希表
p = p->next; // 移动到下一个节点
}
// 重置指针p回到原链表头部
p = head;
// 第二步：再次遍历原链表以设置克隆节点的next和random指针
while (p) {
// 设置克隆节点的next指针
// 如果原节点的next指针不为空，则从哈希表中找到对应的克隆节点并设置
hmap[p]->next = (p->next != nullptr) ? hmap[p->next] : nullptr;
// 设置克隆节点的random指针
// 同样地，如果原节点的random指针不为空，则从哈希表中找到对应的克隆节点并设置
hmap[p]->random = (p->random != nullptr) ? hmap[p->random] : nullptr;
// 继续移动到下一个节点
p = p->next;
}
// 返回原链表头节点对应的克隆节点
return hmap[head];
}
};