用C++实现下面网址的题目

https://leetcode.cn/problems/merge-sorted-array/?envType=study-plan-v2&envId=top-interview-150

1、数组\字符串

88合并两个有序数组

以下是使用 C++ 实现合并两个有序数组的代码及测试用例

C++代码实现

#include <iostream>
#include <vector>using namespace std;class Solution {
public:// 合并两个有序数组的函数void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {// 初始化三个指针，i指向nums1有效元素的末尾，j指向nums2的末尾，k指向合并后nums1的末尾int i = m - 1; int j = n - 1;int k = m + n - 1;// 当nums1和nums2都还有未处理的元素时while (i >= 0 && j >= 0) {if (nums1[i] > nums2[j]) {// 如果nums1中当前元素大于nums2中当前元素，将nums1中的元素移到合并后的位置nums1[k] = nums1[i];i--;} else {// 如果nums2中当前元素大于等于nums1中当前元素，将nums2中的元素移到合并后的位置nums1[k] = nums2[j];j--;}k--;}// 如果nums2还有剩余元素，将它们全部复制到nums1的前面部分while (j >= 0) {nums1[k] = nums2[j];j--;k--;}}
};// 测试用例函数
void testMerge() {Solution solution;// 测试示例1vector<int> nums1_1 = {1, 2, 3, 0, 0, 0};int m1 = 3;vector<int> nums2_1 = {2, 5, 6};int n1 = 3;solution.merge(nums1_1, m1, nums2_1, n1);for (int num : nums1_1) {cout << num << " ";}cout << endl;// 测试示例2vector<int> nums1_2 = {4, 5, 6, 0, 0, 0};int m2 = 3;vector<int> nums2_2 = {1, 2, 3};int n2 = 3;solution.merge(nums1_2, m2, nums2_2, n2);for (int num : nums1_2) {cout << num << " ";}cout << endl;// 测试示例3（nums1为空数组，用0填充）vector<int> nums1_3 = {0, 0, 0};int m3 = 0;vector<int> nums2_3 = {1, 2, 3};int n3 = 3;solution.merge(nums1_3, m3, nums2_3, n3);for (int num : nums1_3) {cout << num << " ";}cout << endl;
}int main() {testMerge();return 0;
}

以下是对代码的详细注释：

merge函数注释

1. 函数参数和初始化指针：

   • vector<int>& nums1：这是第一个有序数组，它有足够的空间来容纳合并后的结果。我们通过引用传递它，以避免复制大型数组。
   • int m：表示nums1中实际有效元素的个数。
   • vector<int>& nums2：第二个有序数组。
   • int n：表示nums2中元素的个数。
   • 初始化i、j、k三个指针：
     • int i = m - 1：i指向nums1中有效元素部分的末尾，用于从后往前遍历nums1的有效元素。
     • int j = n - 1：j指向nums2的末尾，用于从后往前遍历nums2。
     • int k = m + n - 1：k指向nums1用于填充合并结果的末尾位置，因为合并后的数组长度是m + n。

2. 合并过程的主循环：

   • while (i >= 0 && j >= 0)：只要nums1和nums2都还有未处理的元素，就继续循环。
   • 在循环内：
     • if (nums1[i] > nums2[j])：比较nums1和nums2当前指向的元素大小。如果nums1[i]更大，就将nums1[i]移到nums1的合并后位置nums1[k]，然后i减 1（因为这个元素已经处理了），k也减 1（移动到下一个合并后的位置）。
     • 否则（nums2[j] >= nums1[i]），将nums2[j]移到nums1[k]，然后j减 1，k减 1。

3. 处理nums2剩余元素：

   • while (j >= 0)：当nums2还有剩余元素（nums1已经处理完或者处理过程中nums2还有剩余）时，将nums2的剩余元素依次复制到nums1的前面部分（因为nums1有足够的空间），每次复制后j减 1，k减 1。

testMerge函数注释

1. 创建Solution对象和测试示例数据：

   • Solution solution：创建Solution类的一个实例，用于调用merge函数。
   • 对于每个测试示例：
     • 定义nums1、m、nums2、n。例如在第一个测试示例中：
       • vector<int> nums1_1 = {1, 2, 3, 0, 0, 0}：nums1_1是第一个有序数组，后面的0是用于填充合并结果的额外空间。
       • int m1 = 3：表示nums1_1中实际有效元素的个数是 3 个。
       • vector<int> nums2_1 = {2, 5, 6}：第二个有序数组。
       • int n1 = 3：nums2_1中元素的个数是 3 个。

2. 调用merge函数并输出结果：

   • 调用solution.merge(nums1_1, m1, nums2_1, n1)来合并两个数组。
   • 然后使用for循环for (int num : nums1_1)遍历合并后的nums1_1数组，并输出每个元素，用于查看合并结果是否正确。每个测试示例都重复这个过程。

main函数注释

在main函数中，只调用了testMerge函数来执行所有的测试用例，最后返回 0，表示程序正常结束。

代码提交测试结果如下：

27移除元素

以下是使用 C++ 实现移除数组中指定元素的代码，并包含了测试用例：

C++代码实现

#include <iostream>
#include <vector>using namespace std;class Solution {
public:// 函数用于移除向量nums中的指定元素valint removeElement(vector<int>& nums, int val) {int i = 0;  // 慢指针，用于标记新数组的索引位置// 遍历整个nums数组，j为快指针for (int j = 0; j < nums.size(); j++) {// 如果当前元素不等于要移除的值valif (nums[j]!= val) {nums[i] = nums[j];  // 将当前元素复制到新数组的位置（由慢指针i指定）i++;  // 慢指针后移一位，准备接收下一个新元素}}return i;  // 返回新数组的长度（即移除指定元素后的数组长度）}
};// 测试用例函数
void testRemoveElement() {Solution solution;// 测试示例1vector<int> nums1 = {3, 2, 2, 3};int val1 = 3;int newSize1 = solution.removeElement(nums1, val1);for (int k = 0; k < newSize1; k++) {cout << nums1[k] << " ";}cout << endl;// 测试示例2vector<int> nums2 = {0, 1, 2, 2, 3, 0, 4, 2};int val2 = 2;int newSize2 = solution.removeElement(nums2, val2);for (int k = 0; k < newSize2; k++) {cout << nums2[k] << " ";}cout << endl;// 测试示例3（数组中没有要移除的元素）vector<int> nums3 = {1, 3, 5, 7};int val3 = 2;int newSize3 = solution.removeElement(nums3, val3);for (int k = 0; k < newSize3; k++) {cout << nums3[k] << " ";}cout << endl;
}int main() {testRemoveElement();return 0;
}

以下是对代码的详细注释：

removeElement函数注释

• 参数和慢指针初始化：

  • vector<int>& nums：这是一个引用传递的整数向量，我们要在这个向量中移除指定元素。引用传递可以避免在函数调用时复制整个向量，提高效率。
  • int val：要从nums向量中移除的目标元素值。
  • int i = 0：定义一个慢指针i，它用于标记新数组的索引位置。新数组是指移除指定元素val后的数组。

• 遍历数组和移除元素的过程：

  • 使用for循环for (int j = 0; j < nums.size(); j++)来遍历整个nums向量，这里j是快指针。
  • 在循环内部，通过if (nums[j]!= val)判断当前元素nums[j]是否不等于要移除的值val。
  • 如果nums[j]不等于val，就执行nums[i] = nums[j];，这意味着将当前元素（不需要移除的元素）复制到新数组的位置（由慢指针i指定）。
  • 然后执行i++;，将慢指针i向后移动一位，准备接收下一个不需要移除的元素。

• 返回新数组长度：

  • 当遍历完整个nums向量后，i的值就是新数组的长度，也就是移除指定元素val后的数组长度，最后将i返回。

testRemoveElement函数注释

• 创建Solution对象和测试数据：

  • Solution solution：创建Solution类的一个实例，用于调用removeElement函数。
  • 对于每个测试示例：
    • 定义nums向量和val值。例如在第一个测试示例中：
      • vector<int> nums1 = {3, 2, 2, 3}：定义了一个整数向量nums1，其中包含要操作的数组元素。
      • int val1 = 3：指定要从nums1中移除的元素值为3。

• 调用removeElement函数并输出结果：

  • 调用solution.removeElement(nums1, val1)来移除nums1中的val1元素，并将返回的新数组长度存储在newSize1中。
  • 使用for循环for (int k = 0; k < newSize1; k++)遍历新数组（即移除指定元素后的nums1部分），并输出每个元素，以便查看移除结果是否正确。每个测试示例都重复这个过程。

main函数注释

• 在main函数中，只调用了testRemoveElement函数来执行所有的测试用例，最后返回0，表示程序正常结束。

代码提交测试结果如下： 

26. 删除有序数组中的重复项 

以下是使用 C++ 实现删除有序数组中的重复项的代码，并包含测试用例：

C++代码实现 

#include <iostream>
#include <vector>using namespace std;class Solution {
public:// 函数用于删除有序数组nums中的重复项int removeDuplicates(vector<int>& nums) {if (nums.size() == 0) {return 0;}int i = 0; // 慢指针，指向不重复元素的位置for (int j = 1; j < nums.size(); j++) { // 快指针，用于遍历数组if (nums[j]!= nums[i]) { i++;nums[i] = nums[j];}}return i + 1; // 返回不重复元素的个数，因为索引从0开始，所以个数为i + 1}
};// 测试用例函数
void testRemoveDuplicates() {Solution solution;// 测试示例1vector<int> nums1 = {1, 1, 2};int newLength1 = solution.removeDuplicates(nums1);for (int k = 0; k < newLength1; k++) {cout << nums1[k] << " ";}cout << endl;// 测试示例2vector<int> nums2 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};int newLength2 = solution.removeDuplicates(nums2);for (int k = 0; k < newLength2; k++) {cout << nums2[k] << " ";}cout << endl;// 测试示例3（没有重复元素的数组）vector<int> nums3 = {5, 6, 7, 8};int newLength3 = solution.removeDuplicates(nums3);for (int k = 0; k < newLength3; k++) {cout << nums3[k] << " ";}cout << endl;
}int main() {testRemoveDuplicates();return 0;
}

以下是对代码的详细注释：

removeDuplicates函数注释

• 边界情况处理：

  • 首先判断数组是否为空，如果nums.size() == 0，则直接返回0，因为空数组没有元素，也就没有重复项需要处理。

• 初始化指针和遍历数组：

  • int i = 0：定义一个慢指针i，它用于标记不重复元素的位置。初始时，数组的第一个元素必然是不重复的，所以i初始化为0。
  • 使用for循环for (int j = 1; j < nums.size(); j++)来遍历数组，这里j是快指针，从索引1开始，因为我们已经将i初始化为0，即第一个元素已经考虑过了。

• 处理重复元素：

  • 在循环内部，通过if (nums[j]!= nums[i])判断当前元素nums[j]是否与慢指针i所指向的元素不同。
  • 如果不同，说明找到了一个新的不重复元素。首先将慢指针i向后移动一位（i++），然后将新的不重复元素nums[j]赋值给nums[i]，这样就将不重复元素依次向前移动。

• 返回不重复元素个数：

  • 当遍历完整个数组后，由于索引从0开始，不重复元素的个数就是i + 1，所以返回i + 1。

testRemoveDuplicates函数注释

• 创建Solution对象和测试数据：

  • Solution solution：创建Solution类的一个实例，用于调用removeDuplicates函数。
  • 对于每个测试示例：
    • 定义nums向量。例如在第一个测试示例中：
      • vector<int> nums1 = {1, 1, 2}：定义了一个有序整数向量nums1，其中包含重复元素。

• 调用removeDuplicates函数并输出结果：

  • 调用solution.removeDuplicates(nums1)来删除nums1中的重复元素，并将返回的不重复元素个数存储在newLength1中。
  • 使用for循环for (int k = 0; k < newLength1; k++)遍历处理后的数组（即不重复元素部分），并输出每个元素，以便查看删除重复项的结果是否正确。每个测试示例都重复这个过程。

main函数注释

• 在main函数中，只调用了testRemoveDuplicates函数来执行所有的测试用例，最后返回0，表示程序正常结束。

代码提交测试结果如下：  

80. 删除有序数组中的重复项 II

以下是使用 C++ 实现删除有序数组中的重复项 II 的代码，允许每个元素最多出现两次：

C++代码实现 

#include <iostream>
#include <vector>using namespace std;class Solution {
public:int removeDuplicates(vector<int>& nums) {if (nums.size() <= 2) {return nums.size();}int i = 2; // 慢指针，从索引2开始，因为前两个元素不管是否重复都保留for (int j = 2; j < nums.size(); j++) {// 如果当前元素与慢指针前两个位置的元素不相等，说明当前元素不是重复超过2次的元素if (nums[j]!= nums[i - 2]) { nums[i] = nums[j];i++;}}return i;}
};// 测试用例函数
void testRemoveDuplicatesII() {Solution solution;// 测试示例1vector<int> nums1 = {1, 1, 1, 2, 2, 3};int newLength1 = solution.removeDuplicates(nums1);for (int k = 0; k < newLength1; k++) {cout << nums1[k] << " ";}cout << endl;// 测试示例2vector<int> nums2 = {0, 0, 1, 1, 1, 1, 2, 3, 3};int newLength2 = solution.removeDuplicates(nums2);for (int k = 0; k < newLength2; k++) {cout << nums2[k] << " ";}cout << endl;// 测试示例3（没有重复元素的数组）vector<int> nums3 = {2, 3, 5, 7};int newLength3 = solution.removeDuplicates(nums3);for (int k = 0; k < newLength3; k++) {cout << nums3[k] << " ";}cout << endl;
}int main() {testRemoveDuplicatesII();return 0;
}

以下是详细注释：

removeDuplicates函数注释

• 边界情况处理：

  • 首先判断数组大小，如果nums.size() <= 2，那么数组中的元素最多重复两次或者没有重复，直接返回数组的大小。

• 初始化指针和遍历数组：

  • int i = 2：慢指针i从索引2开始，因为我们允许每个元素最多出现两次，所以前两个元素不管是否重复都先保留。
  • 使用for循环for (int j = 2; j < nums.size(); j++)，其中j是快指针，从索引2开始遍历整个数组。

• 处理重复元素：

  • 在循环中，通过if (nums[j]!= nums[i - 2])判断当前元素nums[j]是否与慢指针i往前数两个位置的元素不相等。如果不相等，说明当前元素不是重复超过两次的元素。
  • 当满足条件时，将nums[j]赋值给nums[i]，然后将慢指针i向后移动一位（i++），这样就将不重复或者重复次数未超过两次的元素依次向前移动。

• 返回处理后的数组长度：

  • 当遍历完整个数组后，慢指针i的值就是处理后的数组长度，返回i。

testRemoveDuplicatesII函数注释

• 创建Solution对象和测试数据：

  • Solution solution：创建Solution类的一个实例，用于调用removeDuplicates函数。
  • 对于每个测试示例：
    • 定义nums向量。例如在第一个测试示例中，vector<int> nums1 = {1, 1, 1, 2, 2, 3}定义了一个有序整数向量nums1，其中有重复元素。

• 调用removeDuplicates函数并输出结果：

  • 调用solution.removeDuplicates(nums1)来处理nums1中的重复元素，并将返回的新数组长度存储在newLength1中。
  • 使用for循环for (int k = 0; k < newLength1; k++)遍历处理后的数组，并输出每个元素，以此来查看处理结果是否正确。每个测试示例都重复这个过程。

main函数注释

• 在main函数中，调用testRemoveDuplicatesII函数来执行所有的测试用例，最后返回0，表示程序正常结束。

代码提交测试结果如下：   

169. 多数元素

利用哈希表统计出现次数的方法

C++代码实现

#include <iostream>
#include <vector>
#include <unordered_map>using namespace std;class Solution {
public:int majorityElement(vector<int>& nums) {// 创建一个无序映射（哈希表）来存储元素及其出现的次数unordered_map<int, int> countMap;int n = nums.size();// 遍历数组，统计每个元素出现的次数for (int num : nums) {if (countMap.find(num)!= countMap.end()) {countMap[num]++;} else {countMap[num] = 1;}// 如果某个元素的出现次数超过数组长度的一半，返回该元素if (countMap[num] > n / 2) {return num;}}return -1; // 如果没有找到多数元素，返回 -1（实际情况中多数元素一定存在）}
};// 测试用例函数
void testMajorityElement() {Solution solution;// 测试示例1vector<int> nums1 = {3, 2, 3};cout << solution.majorityElement(nums1) << endl;// 测试示例2vector<int> nums2 = {2, 2, 1, 1, 1, 2, 2};cout << solution.majorityElement(nums2) << endl;
}int main() {testMajorityElement();return 0;
}

• majorityElement函数注释：

  • 首先创建一个unordered_map<int, int>类型的countMap，用于存储数组中每个元素及其出现的次数。
  • 通过int n = nums.size();获取数组的长度。
  • 使用for (int num : nums)遍历数组nums，对于每个元素num：
    • 如果countMap.find(num)!= countMap.end()，说明num已经在countMap中，将其对应的值（出现次数）加1，即countMap[num]++;。
    • 如果num不在countMap中，将其插入countMap，并将出现次数初始化为1，即countMap[num] = 1;。
    • 在每次更新countMap后，检查当前元素num的出现次数是否大于n / 2，如果是，则直接返回num。
  • 如果遍历完整个数组都没有找到多数元素（实际上本题保证多数元素一定存在），则返回-1。

• testMajorityElement函数注释：

  • 创建Solution类的实例solution。
  • 对于每个测试示例，定义nums向量，然后调用solution.majorityElement(nums)来获取多数元素并输出结果。

• main函数注释：

  • 在main函数中，调用testMajorityElement函数来执行测试用例，最后返回0表示程序正常结束。

代码提交测试结果如下：    

189. 轮转数组

原地旋转的方法（三次反转法）

C++代码实现 

#include <iostream>
#include <vector>using namespace std;class Solution {
public:void rotate(vector<int>& nums, int k) {int n = nums.size();k %= n;// 反转整个数组reverse(nums.begin(), nums.end());// 反转前k个元素reverse(nums.begin(), nums.begin() + k);// 反转后n - k个元素reverse(nums.begin() + k, nums.end());}
};// 测试用例函数（与上面使用额外数组方法中的testRotate函数相同，此处省略）int main() {testRotate();return 0;
}

代码注释：

• rotate函数注释：
  • 同样先获取数组长度n，并对k取模以处理k大于n的情况。
  • 第一次调用reverse(nums.begin(), nums.end())将整个数组反转。这样原数组中最后k个元素就到了数组的前面，但顺序是相反的。
  • 第二次调用reverse(nums.begin(), nums.begin() + k)，将数组的前k个元素再次反转，使得这 `k$ 个元素恢复正确的顺序。
  • 第三次调用reverse(nums.begin() + k, nums.end())，将数组剩余的 `n - k$ 个元素反转，使其恢复正确的顺序，从而完成数组的旋转。

这种原地旋转的方法不需要额外的数组空间，相比使用额外数组的方法更节省空间。

代码提交测试结果如下：   

121. 买卖股票的最佳时机

 以下是使用 C++ 实现 “买卖股票的最佳时机” 问题的代码，该问题要求找到一次买卖股票所能获得的最大利润。

C++代码实现

#include <iostream>
#include <vector>using namespace std;class Solution {
public:int maxProfit(vector<int>& prices) {if (prices.size() == 0) {return 0;}int minPrice = prices[0]; // 初始化最小价格为第一天的价格int maxProfit = 0; // 初始化最大利润为0for (int i = 1; i < prices.size(); i++) {// 更新最小价格if (prices[i] < minPrice) {minPrice = prices[i];} else {// 计算当前价格与最小价格的差值，尝试更新最大利润int profit = prices[i] - minPrice;if (profit > maxProfit) {maxProfit = profit;}}}return maxProfit;}
};// 测试用例函数
void testMaxProfit() {Solution solution;// 测试示例1vector<int> prices1 = {7, 1, 5, 3, 6, 4};cout << solution.maxProfit(prices1) << endl;// 测试示例2vector<int> prices2 = {7, 6, 4, 3, 1};cout << solution.maxProfit(prices2) << endl;// 测试示例3（只有一个价格）vector<int> prices3 = {5};cout << solution.maxProfit(prices3) << endl;
}int main() {testMaxProfit();return 0;
}

以下是对代码的详细注释：

maxProfit函数注释

• 边界情况处理：

  • 首先判断输入的价格数组prices是否为空，如果prices.size() == 0，则直接返回0，因为没有交易就没有利润。

• 初始化变量：

  • int minPrice = prices[0];：初始化最小价格为数组中的第一个价格，因为我们需要从第一天开始寻找最低价格。
  • int maxProfit = 0;：初始化最大利润为0，后续会在遍历过程中更新这个值。

• 遍历价格数组：

  • 使用for (int i = 1; i < prices.size(); i++)从数组的第二个元素开始遍历。
  • 在循环中：
    • if (prices[i] < minPrice)：如果当前价格比之前记录的最小价格还小，那么更新最小价格，因为我们希望找到最低的买入价格。
    • 否则，计算当前价格与最小价格的差值int profit = prices[i] - minPrice;，这个差值就是如果在最小价格买入并在当前价格卖出所能获得的利润。
    • 接着，if (profit > maxProfit)：如果这个利润大于之前记录的最大利润，就更新最大利润。

• 返回最大利润：

  • 遍历完整个价格数组后，maxProfit中存储的就是一次买卖股票所能获得的最大利润，最后返回这个值。

testMaxProfit函数注释

• 创建Solution对象和测试数据：

  • Solution solution;：创建Solution类的一个实例，用于调用maxProfit函数。
  • 对于每个测试示例，定义prices向量，例如vector<int> prices1 = {7, 1, 5, 3, 6, 4};，这里定义了不同的价格序列。

• 调用maxProfit函数并输出结果：

  • 调用solution.maxProfit(prices1)计算并获取最大利润，然后使用cout输出结果。每个测试示例都重复这个过程。

main函数注释

• 在main函数中，调用testMaxProfit函数来执行所有的测试用例，最后返回0表示程序正常结束。

代码提交测试结果如下：    

 

122. 买卖股票的最佳时机 II

以下是使用 C++ 实现 “买卖股票的最佳时机 II” 问题的代码。本题中可以多次买卖股票，只要在每次买卖时有利润即可。 

C++代码实现

#include <iostream>
#include <vector>using namespace std;class Solution {
public:int maxProfit(vector<int>& prices) {int profit = 0;for (int i = 0; i < prices.size() - 1; i++) {// 如果后一天的价格比当前价格高，就进行一次买卖操作（模拟买入和卖出）if (prices[i + 1] > prices[i]) {profit += prices[i + 1] - prices[i];}}return profit;}
};// 测试用例函数
void testMaxProfitII() {Solution solution;// 测试示例1vector<int> prices1 = {7, 1, 5, 3, 6, 4};cout << solution.maxProfit(prices1) << endl;// 测试示例2vector<int> prices2 = {1, 2, 3, 4, 5};cout << solution.maxProfit(prices2) << endl;// 测试示例3vector<int> prices3 = {7, 6, 4, 3, 1};cout << solution.maxProfit(prices3) << endl;
}int main() {testMaxProfitII();return 0;
}

以下是对代码的详细注释：

maxProfit函数注释

• 初始化利润变量：

  • int profit = 0;：初始化利润为 0，这个变量将用于累计每次买卖股票所获得的利润。

• 遍历价格数组（除最后一个元素）：

  • 使用for (int i = 0; i < prices.size() - 1; i++)遍历价格数组，这里不需要遍历最后一个元素，因为我们是通过比较当前元素和下一个元素来判断是否有利润可赚。
  • 在循环中：
    • if (prices[i + 1] > prices[i])：如果后一天的价格比当前价格高，说明可以进行一次买卖操作来获取利润。
    • 计算利润并累加到profit变量中，profit += prices[i + 1] - prices[i];，这里模拟了买入当前价格的股票并在下一天卖出的操作。

• 返回总利润：

  • 遍历完整个价格数组后，profit变量中存储的就是多次买卖股票所能获得的最大利润，最后返回这个值。

testMaxProfitII函数注释

• 创建Solution对象和测试数据：

  • Solution solution;：创建Solution类的一个实例，用于调用maxProfit函数。
  • 对于每个测试示例，定义prices向量，例如vector<int> prices1 = {7, 1, 5, 3, 6, 4};，这里定义了不同的价格序列。

• 调用maxProfit函数并输出结果：

  • 调用solution.maxProfit(prices1)计算并获取最大利润，然后使用cout输出结果。每个测试示例都重复这个过程。

main函数注释

• 在main函数中，调用testMaxProfitII函数来执行所有的测试用例，最后返回 0 表示程序正常结束。

代码提交测试结果如下： 

55. 跳跃游戏 

以下是使用 C++ 实现跳跃游戏的代码及测试用例

C++ 代码实现

#include <iostream>
#include <vector>using namespace std;class Solution {
public:bool canJump(vector<int>& nums) {int n = nums.size();int farthest = 0; // 记录当前能跳到的最远位置for (int i = 0; i < n; i++) {if (i > farthest) {// 如果当前位置超过了能跳到的最远位置，说明无法继续前进，返回 falsereturn false; }farthest = max(farthest, i + nums[i]); // 更新能跳到的最远位置}return true; // 如果能顺利遍历完数组，说明可以跳到最后一个位置，返回 true}
};// 测试用例函数
void testCanJump() {Solution solution;// 测试示例1：可以跳到最后vector<int> nums1 = {2, 3, 1, 1, 4};cout << (solution.canJump(nums1)? "True" : "False") << endl;// 测试示例2：无法跳到最后vector<int> nums2 = {3, 2, 1, 0, 4};cout << (solution.canJump(nums2)? "True" : "False") << endl;
}int main() {testCanJump();return 0;
}

以下是对代码的详细注释：

canJump函数注释

• 初始化和获取数组长度：

  • 首先获取输入数组nums的长度n。
  • 初始化变量farthest为0，它用于记录当前能够跳到的最远位置。

• 遍历数组：

  • 使用for循环for (int i = 0; i < n; i++)遍历数组nums的每个元素。
  • 在循环中，首先判断if (i > farthest)：如果当前位置i已经超过了之前记录的能跳到的最远位置farthest，这意味着无法从之前的位置跳到当前位置，也就无法继续前进到达数组末尾，所以直接返回false。
  • 然后更新能跳到的最远位置，通过farthest = max(farthest, i + nums[i]);。这里i + nums[i]表示从当前位置i能够跳到的最远距离，取它和之前记录的farthest的最大值作为新的farthest。

• 返回结果：

  • 如果能够顺利遍历完整个数组，说明可以通过合理的跳跃到达最后一个位置，返回true。

testCanJump函数注释

• 创建Solution对象和测试数据：

  • 创建Solution类的实例solution。
  • 对于每个测试示例，定义nums向量，例如vector<int> nums1 = {2, 3, 1, 1, 4};，这里定义了不同的跳跃能力数组。

• 调用canJump函数并输出结果：

  • 调用solution.canJump(nums1)来判断是否能够跳到最后，并根据返回结果输出"True"或"False"。每个测试示例都重复这个过程。

main函数注释

• 在main函数中，调用testCanJump函数来执行测试用例，最后返回0表示程序正常结束。

代码提交测试结果如下：  

45. 跳跃游戏 II

以下是使用 C++ 实现的跳跃游戏 II 的代码：

#include <vector>
#include <iostream>// 这个函数用于计算在给定的数组中，从起始位置到达最后一个位置所需的最小跳跃次数
int jump(std::vector<int>& nums) {int n = nums.size();// 如果数组为空或者只有一个元素，不需要跳跃，直接返回0if (n <= 1) return 0;// 当前能够到达的最远位置int curMax = nums[0];// 下一步能够到达的最远位置int nextMax = nums[0];int jumps = 1;for (int i = 0; i < n; i++) {// 如果当前位置超过了当前能够到达的最远位置，说明需要进行一次跳跃if (i > curMax) {curMax = nextMax;jumps++;}// 更新下一步能够到达的最远位置nextMax = std::max(nextMax, i + nums[i]);}return jumps;
}// 以下是测试用例
int main() {std::vector<int> nums1 = {2,3,1,1,4};std::cout << "For nums1 = {2,3,1,1,4}, the minimum number of jumps is: " << jump(nums1) << std::endl;std::vector<int> nums2 = {2,3,0,1,4};std::cout << "For nums2 = {2,3,0,1,4}, the minimum number of jumps is: " << jump(nums2) << std::endl;return 0;
}

在上述代码中：

• 在jump函数中：
  • 首先处理了边界情况，如果数组长度小于等于 1，直接返回 0，表示不需要跳跃。
  • 然后初始化curMax为数组的第一个元素，表示当前能够到达的最远位置，nextMax也初始化为第一个元素，它用于记录遍历过程中发现的更远的可达位置。jumps初始化为 1，因为至少需要跳一次。
  • 在for循环中，当i超过了curMax，意味着需要进行一次新的跳跃，此时更新curMax为nextMax，并增加jumps的值。同时，不断更新nextMax，取当前的nextMax和i + nums[i]中的较大值。
• 在main函数中，提供了两个不同的测试用例，调用jump函数并输出结果。

代码提交测试结果如下： 

274. H 指数

以下是使用 C++ 实现计算 H 指数的代码：

#include <vector>
#include <algorithm>
#include <iostream>// 计算H指数的函数
int hIndex(std::vector<int>& citations) {// 对引用次数数组进行排序std::sort(citations.begin(), citations.end());int n = citations.size();for (int i = 0; i < n; i++) {// h指数的定义：有h篇论文的引用次数至少为hint h = n - i;if (citations[i] >= h) {return h;}}return 0;
}// 测试用例函数
int main() {// 测试用例1std::vector<int> citations1 = {3, 0, 6, 1, 7};std::cout << "For citations1 = {3, 0, 6, 1, 7}, the H - index is: " << hIndex(citations1) << std::endl;// 测试用例2std::vector<int> citations2 = {1, 3, 1};std::cout << "For citations2 = {1, 3, 1}, the H - index is: " << hIndex(citations2) << std::endl;return 0;
}

代码注释如下：

在hIndex函数中：

1. std::sort(citations.begin(), citations.end());：
   • 首先对输入的引用次数数组citations进行排序。这是为了方便后续按照从小到大的顺序遍历数组来确定 H 指数。排序操作利用了algorithm头文件中的sort函数。
2. int n = citations.size();：
   • 获取数组的大小，用于后续的遍历和计算。
3. for (int i = 0; i < n; i++)：
   • 开始遍历排序后的数组。
   • 在每次循环中，计算当前可能的h值，根据h指数的定义，h等于数组中剩余元素的数量（即n - i）。
   • if (citations[i] >= h)：
     • 如果当前引用次数citations[i]大于或等于当前计算出的h值，那么这个h就是满足条件的 H 指数，直接返回h。

在main函数中：

1. 对于citations1：
   • 定义了std::vector<int> citations1 = {3, 0, 6, 1, 7};作为一个测试用例。
   • 调用hIndex(citations1)并输出结果，展示了在这种引用次数分布下的 H 指数计算。
2. 对于citations2：
   • 类似地，定义std::vector<int> citations2 = {1, 3, 1};作为另一个测试用例。
   • 调用hIndex(citations2)并输出结果，用于验证不同引用情况的 H 指数计算。

 380. O(1) 时间插入、删除和获取随机元素

以下是使用 C++ 实现一个支持O(1)时间插入、删除和获取随机元素的数据结构的代码。这里我们使用一个vector和一个unordered_map来实现。

#include <vector>
#include <unordered_map>
#include <iostream>
#include <cstdlib>class RandomizedSet {
private:std::vector<int> nums;  // 用于存储元素的向量std::unordered_map<int, int> valToIndex;  // 用于快速查找元素在向量中的索引public:// 构造函数RandomizedSet() {}// 插入元素，如果元素不存在则插入成功并返回 true，否则返回 falsebool insert(int val) {if (valToIndex.find(val)!= valToIndex.end()) {return false;}nums.push_back(val);valToIndex[val] = nums.size() - 1;return true;}// 删除元素，如果元素存在则删除成功并返回 true，否则返回 falsebool remove(int val) {if (valToIndex.find(val) == valToIndex.end()) {return false;}int index = valToIndex[val];int lastVal = nums.back();nums[index] = lastVal;valToIndex[lastVal] = index;nums.pop_back();valToIndex.erase(val);return true;}// 获取一个随机元素int getRandom() {int randomIndex = rand() % nums.size();return nums[randomIndex];}
};// 测试用例
int main() {RandomizedSet randomizedSet;std::cout << "Insert 1: " << (randomizedSet.insert(1)? "Success" : "Failed") << std::endl;std::cout << "Insert 2: " << (randomizedSet.insert(2)? "Success" : "Failed") << std::endl;std::cout << "Insert 3: " << (randomizedSet.insert(3)? "Success" : "Failed") << std::endl;std::cout << "Remove 2: " << (randomizedSet.remove(2)? "Success" : "Failed") << std::endl;std::cout << "Random element: " << randomizedSet.getRandom() << std::endl;return 0;
}

以下是代码注释：

在RandomizedSet类中：

1. 成员变量：

   • std::vector<int> nums;：这个向量用于存储所有的元素。插入新元素时会将元素添加到这个向量的末尾，删除元素时可能会涉及到向量中元素的交换。
   • std::unordered_map<int, int> valToIndex;：这个无序映射用于快速查找元素在nums向量中的索引。键是元素的值，值是该元素在nums向量中的索引。

2. insert函数：

   • if (valToIndex.find(val)!= valToIndex.end())：首先检查元素val是否已经存在于valToIndex中，如果存在（即find函数返回的迭代器不等于end），说明元素已经存在，直接返回false。
   • nums.push_back(val);：如果元素不存在，将元素添加到nums向量的末尾。
   • valToIndex[val] = nums.size() - 1;：在valToIndex中记录新插入元素val的索引，索引值为nums向量当前的大小减 1（因为push_back操作后新元素在末尾），然后返回true表示插入成功。

3. remove函数：

   • if (valToIndex.find(val) == valToIndex.end())：首先检查要删除的元素val是否存在于valToIndex中，如果不存在（即find函数返回的迭代器等于end），则返回false。
   • int index = valToIndex[val];：获取要删除元素在nums向量中的索引。
   • int lastVal = nums.back();：获取nums向量中的最后一个元素的值。
   • nums[index] = lastVal;：将nums向量中要删除元素的位置替换为最后一个元素。
   • valToIndex[lastVal] = index;：更新lastVal在valToIndex中的索引。
   • nums.pop_back();：删除nums向量的最后一个元素（即原来要删除元素的副本）。
   • valToIndex.erase(val);：从valToIndex中删除要删除元素的记录，最后返回true表示删除成功。

4. getRandom函数：

   • int randomIndex = rand() % nums.size();：使用rand函数生成一个在0到nums.size() - 1范围内的随机索引。这里假设已经包含了<cstdlib>头文件来使用rand函数。
   • return nums[randomIndex];：返回nums向量中随机索引位置的元素。

在main函数中：

• 首先创建了RandomizedSet类的实例randomizedSet。
• 然后依次进行插入操作，并输出插入结果。插入操作调用randomizedSet.insert函数，并根据返回值输出Success或Failed。
• 接着进行删除操作，调用randomizedSet.remove函数并输出结果。
• 最后调用randomizedSet.getRandom函数获取一个随机元素并输出。每次运行程序，获取的随机元素可能不同。

238. 除自身以外数组的乘积

以下是使用 C++ 实现的除自身以外数组的乘积的代码

#include <vector>
#include <iostream>using namespace std;class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();// 用于存储结果的向量vector<int> result(n, 1);// 计算当前元素左侧所有元素的乘积int leftProduct = 1;for (int i = 0; i < n; i++) {result[i] *= leftProduct;leftProduct *= nums[i];}// 计算当前元素右侧所有元素的乘积，并与之前的结果相乘int rightProduct = 1;for (int i = n - 1; i >= 0; i--) {result[i] *= rightProduct;rightProduct *= nums[i];}return result;}
};// 测试用例
int main() {vector<int> nums = {1, 2, 3, 4};Solution solution;vector<int> output = solution.productExceptSelf(nums);for (int i = 0; i < output.size(); i++) {cout << output[i] << " ";}cout << endl;return 0;
}

代码注释如下：

在productExceptSelf函数中：

1. int n = nums.size();：
   • 首先获取输入数组nums的大小，以便后续遍历。
2. vector<int> result(n, 1);：
   • 创建一个大小为n的vector，并将所有元素初始化为1。这个vector将用于存储最终的结果，即每个元素为除自身以外数组元素的乘积。
3. 计算左侧元素乘积：
   • int leftProduct = 1;：初始化一个变量leftProduct为1，用于累乘当前元素左侧的所有元素。
   • for (int i = 0; i < n; i++)：从左到右遍历数组nums。
     • result[i] *= leftProduct;：将当前result中的元素乘以leftProduct，这样就将左侧元素的乘积累乘到了result中。
     • leftProduct *= nums[i];：更新leftProduct，将当前元素nums[i]乘到leftProduct中，为下一次循环做准备。
4. 计算右侧元素乘积并更新结果：
   • int rightProduct = 1;：初始化一个变量rightProduct为1，用于累乘当前元素右侧的所有元素。
   • for (int i = n - 1; i >= 0; i--)：从右到左遍历数组nums。
     • result[i] *= rightProduct;：将当前result中的元素乘以rightProduct，这样就将右侧元素的乘积与之前计算的左侧元素乘积相乘，得到了除自身以外数组元素的乘积。
     • rightProduct *= nums[i];：更新rightProduct，将当前元素nums[i]乘到rightProduct中，为下一次循环做准备。

在main函数中：

1. vector<int> nums = {1, 2, 3, 4};：
   • 定义一个测试用例数组nums。
2. Solution solution;：
   • 创建Solution类的实例，用于调用productExceptSelf函数。
3. vector<int> output = solution.productExceptSelf(nums);：
   • 调用productExceptSelf函数，传入nums数组，并将结果存储在output向量中。
4. for (int i = 0; i < output.size(); i++) { cout << output[i] << " "; }：
   • 遍历output向量，并输出其中的每个元素，展示计算得到的除自身以外数组元素的乘积的结果。
5. cout << endl;：
   • 输出换行符，使输出结果更美观。

 134. 加油站

以下是使用 C++ 实现的 “加油站” 问题的解决方案。“加油站” 问题是在一个环形路线上有一系列加油站，每个加油站有一定量的汽油，从某个加油站出发，汽车油箱容量无限，问是否能绕一圈回到出发点，如果能，返回出发的加油站编号，否则返回 -1。

#include <vector>
#include <iostream>using namespace std;class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int n = gas.size();int totalGas = 0;  // 记录总剩余汽油量int currentGas = 0;  // 当前剩余汽油量int startIndex = 0;  // 可能的起始加油站索引for (int i = 0; i < n; i++) {int diff = gas[i] - cost[i];  // 计算在当前加油站加油后与到达下一个加油站消耗后的剩余油量totalGas += diff;currentGas += diff;if (currentGas < 0) {  // 如果当前剩余油量小于0，说明从上次记录的起始点无法到达当前点currentGas = 0;  // 重置当前剩余油量startIndex = i + 1;  // 更新起始点为下一个加油站}}return (totalGas >= 0)? startIndex : -1;  // 如果总剩余油量大于等于0，则存在这样的起始点，否则不存在}
};// 测试用例
int main() {vector<int> gas = {1, 2, 3, 4, 5};vector<int> cost = {3, 4, 5, 1, 2};Solution solution;int result = solution.canCompleteCircuit(gas, cost);if (result!= -1) {cout << "可以从加油站 " << result << " 出发绕一圈。" << endl;} else {cout << "无法绕一圈。" << endl;}return 0;
}

以下是代码的详细注释：

在canCompleteCircuit函数中：

1. int n = gas.size();：
   • 获取加油站的数量，这里假设gas和cost两个向量的大小相同。
2. int totalGas = 0;和int currentGas = 0;以及int startIndex = 0;：
   • totalGas用于记录整个行程中汽油的总剩余量，它是所有加油站加油量与消耗量差值的总和。
   • currentGas用于记录当前从某个起始点开始到当前加油站的剩余汽油量。
   • startIndex用于记录可能的起始加油站索引，初始化为 0。
3. for (int i = 0; i < n; i++)：
   • 遍历所有加油站。
4. int diff = gas[i] - cost[i];：
   • 计算在当前加油站i加油后与到达下一个加油站消耗后的剩余油量。
5. totalGas += diff;和currentGas += diff;：
   • 将当前加油站的剩余油量累加到totalGas和currentGas中。
6. if (currentGas < 0)：
   • 如果当前剩余油量小于 0，说明从上次记录的起始点startIndex无法到达当前加油站i。
7. currentGas = 0;：
   • 重置当前剩余油量，因为要从下一个加油站重新开始计算剩余油量。
8. startIndex = i + 1;：
   • 更新起始点为下一个加油站，即i + 1。
9. return (totalGas >= 0)? startIndex : -1;：
   • 在遍历完所有加油站后，如果totalGas大于等于 0，说明存在一个起始点可以绕一圈，返回这个起始点startIndex；否则返回 -1，表示无法绕一圈。

在main函数中：

1. 定义了vector<int> gas = {1, 2, 3, 4, 5};和vector<int> cost = {3, 4, 5, 1, 2};：
   • 这是一个测试用例，gas向量表示每个加油站的汽油量，cost向量表示从当前加油站到下一个加油站的耗油量。
2. 创建Solution类的实例solution，并调用canCompleteCircuit函数：
   • 将gas和cost向量作为参数传入canCompleteCircuit函数，得到结果result。
3. 根据result的值输出相应的信息：
   • 如果result不等于 -1，说明找到了起始加油站，输出可以从哪个加油站出发绕一圈；否则输出无法绕一圈的信息。

135. 分发糖果

以下是使用 C++ 实现分发糖果问题的代码

#include <vector>
#include <iostream>using namespace std;class Solution {
public:int candy(vector<int>& ratings) {int n = ratings.size();// 初始化每个孩子至少有一个糖果vector<int> candies(n, 1);// 从左到右遍历，如果当前孩子的评分比左边孩子高，// 则当前孩子的糖果数为左边孩子糖果数 + 1for (int i = 1; i < n; i++) {if (ratings[i] > ratings[i - 1]) {candies[i] = candies[i - 1] + 1;}}// 从右到左遍历，修正糖果数，如果当前孩子的评分比右边孩子高，// 且当前孩子的糖果数不大于右边孩子的糖果数，则当前孩子的糖果数为右边孩子糖果数 + 1for (int i = n - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {candies[i] = candies[i + 1] + 1;}}// 计算总共需要的糖果数int totalCandies = 0;for (int i = 0; i < n; i++) {totalCandies += candies[i];}return totalCandies;}
};// 测试用例
int main() {vector<int> ratings = {1, 0, 2};Solution solution;int result = solution.candy(ratings);cout << "总共需要的糖果数: " << result << endl;return 0;
}

以下是对代码的详细注释：

在candy函数中：

1. int n = ratings.size();：
   • 获取孩子的数量，即评分数组ratings的大小。
2. vector<int> candies(n, 1);：
   • 创建一个与ratings大小相同的vector，并初始化为 1，表示每个孩子至少有一个糖果。
3. 从左到右遍历：
   • for (int i = 1; i < n; i++)：从第二个孩子开始遍历（索引为 1）。
   • if (ratings[i] > ratings[i - 1])：如果当前孩子的评分比左边孩子高。
   • candies[i] = candies[i - 1] + 1;：那么当前孩子的糖果数应该比左边孩子多一个，所以设置为左边孩子糖果数加 1。这样保证了从左到右满足评分高的孩子糖果数更多的条件（局部最优）。
4. 从右到左遍历：
   • for (int i = n - 2; i >= 0; i--)：从倒数第二个孩子开始向左遍历。
   • if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1])：如果当前孩子的评分比右边孩子高，并且当前孩子的糖果数不大于右边孩子的糖果数。
   • candies[i] = candies[i + 1] + 1;：则将当前孩子的糖果数设置为右边孩子糖果数加 1，以满足从右到左评分高的孩子糖果数更多的条件（局部最优）。经过这两次遍历，综合考虑了左右两边的情况，保证了每个孩子的糖果数满足条件（全局最优）。
5. 计算糖果总数：
   • int totalCandies = 0;：初始化一个变量用于存储总共需要的糖果数。
   • for (int i = 0; i < n; i++)：遍历candies数组。
   • totalCandies += candies[i];：将每个孩子的糖果数累加到totalCandies中。

在main函数中：

1. vector<int> ratings = {1, 0, 2};：
   • 定义一个测试用例的评分数组，这里有 3 个孩子，中间孩子评分最低，右边孩子评分最高。
2. 创建Solution类的实例solution，并调用candy函数：
   • 调用candy函数传入ratings数组，得到结果result，即总共需要的糖果数。
3. 输出结果：
   • 使用cout输出总共需要的糖果数。

这个算法通过两次遍历数组，分别从左到右和从右到左，来确定每个孩子的糖果数，最后计算出总的糖果数。时间复杂度为O(n)，其中是孩子的数量。

42. 接雨水 

 以下是使用 C++ 实现的 “接雨水” 问题的代码

#include <vector>
#include <iostream>using namespace std;class Solution {
public:int trap(vector<int>& height) {if (height.empty()) {return 0;}int n = height.size();// leftMax[i]表示height[0]到height[i]中的最大值vector<int> leftMax(n);// rightMax[i]表示height[i]到height[n - 1]中的最大值vector<int> rightMax(n);// 计算leftMax数组leftMax[0] = height[0];for (int i = 1; i < n; i++) {leftMax[i] = max(leftMax[i - 1], height[i]);}// 计算rightMax数组rightMax[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; i--) {rightMax[i] = max(rightMax[i + 1], height[i]);}int trappedWater = 0;// 计算每个位置能接住的雨水量并累加for (int i = 0; i < n; i++) {// 每个位置能接住的雨水量是min(leftMax[i], rightMax[i]) - height[i]trappedWater += min(leftMax[i], rightMax[i]) - height[i];}return trappedWater;}
};// 测试用例
int main() {vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};Solution solution;int result = solution.trap(height);cout << "接雨水的总量: " << result << endl;return 0;
}

以下是代码注释：

在trap函数中：

1. if (height.empty()) { return 0; }：
   • 首先判断输入的高度数组height是否为空，如果为空则没有雨水可接，直接返回 0。
2. int n = height.size();：
   • 获取数组height的长度，用于后续的遍历。
3. vector<int> leftMax(n);和vector<int> rightMax(n);：
   • 创建两个长度为n的向量leftMax和rightMax。leftMax[i]用于存储从数组开头到height[i]位置的最大高度值，rightMax[i]用于存储从height[i]到数组末尾的最大高度值。
4. 计算leftMax数组：
   • leftMax[0] = height[0];：初始化leftMax的第一个元素为height[0]，因为从开头到第一个位置的最大高度就是第一个位置的高度。
   • for (int i = 1; i < n; i++)：从第二个位置（索引为 1）开始遍历数组。
   • leftMax[i] = max(leftMax[i - 1], height[i]);：对于每个位置i，取前一个位置的最大高度值leftMax[i - 1]和当前位置的高度height[i]中的较大值作为当前位置的最大高度值leftMax[i]。这样就逐步计算出了从左到右的最大高度序列。
5. 计算rightMax数组：
   • rightMax[n - 1] = height[n - 1];：初始化rightMax的最后一个元素为height[n - 1]，因为从最后一个位置到末尾的最大高度就是最后一个位置的高度。
   • for (int i = n - 2; i >= 0; i--)：从倒数第二个位置（索引为n - 2）开始逆序遍历数组。
   • rightMax[i] = max(rightMax[i + 1], height[i]);：对于每个位置i，取后一个位置的最大高度值rightMax[i + 1]和当前位置的高度height[i]中的较大值作为当前位置的最大高度值rightMax[i]。这样就逐步计算出了从右到左的最大高度序列。
6. int trappedWater = 0;：
   • 初始化一个变量trappedWater，用于累加每个位置能接住的雨水量。
7. 计算接雨水总量：
   • for (int i = 0; i < n; i++)：遍历整个数组。
   • trappedWater += min(leftMax[i], rightMax[i]) - height[i];：对于每个位置i，该位置能接住的雨水量等于leftMax[i]和rightMax[i]中的较小值减去当前位置的高度height[i]。这是因为能接住雨水的高度取决于左右两边的最大高度中的较小值，减去当前位置高度就是该位置能接住的雨水量。将每个位置的雨水量累加到trappedWater中。

在main函数中：

1. vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};：
   • 定义一个测试用例的高度数组height。
2. 创建Solution类的实例solution，并调用trap函数：
   • 调用trap函数传入height数组，得到结果result，即接雨水的总量。
3. 输出结果：
   • 使用cout输出接雨水的总量。

这个算法通过分别计算每个位置左右两边的最大高度，然后根据较小的最大高度来计算该位置能接住的雨水量，最后累加得到总的接雨水量。时间复杂度为O(n)，空间复杂度也为O(n)，其中n是数组height的长度。

 13. 罗马数字转整数

 以下是使用 C++ 实现罗马数字转整数的代码：

#include <iostream>
#include <string>
#include <unordered_map>using namespace std;class Solution {
public:int romanToInt(string s) {// 使用无序映射存储罗马数字字符与其对应的整数值unordered_map<char, int> romanMap = {{'I', 1},{'V', 5},{'X', 10},{'L', 50},{'C', 100},{'D', 500},{'M', 1000}};int result = 0;for (int i = 0; i < s.length(); i++) {// 获取当前罗马数字字符对应的整数值int currentValue = romanMap[s[i]];// 如果当前字符不是最后一个字符，获取下一个字符对应的整数值if (i < s.length() - 1) {int nextValue = romanMap[s[i + 1]];// 如果当前值小于下一个值，说明是特殊情况（如 IV = 4），需要减去当前值if (currentValue < nextValue) {result -= currentValue;} else {// 否则正常相加result += currentValue;}} else {// 如果当前字符是最后一个字符，直接相加result += currentValue;}}return result;}
};// 测试用例
int main() {Solution solution;string roman1 = "III";cout << "罗马数字 " << roman1 << " 转换为整数是: " << solution.romanToInt(roman1) << endl;string roman2 = "IV";cout << "罗马数字 " << roman2 << " 转换为整数是: " << solution.romanToInt(roman2) << endl;string roman3 = "IX";cout << "罗马数字 " << roman3 << " 转换为整数是: " << solution.romanToInt(roman3) << endl;string roman4 = "LVIII";cout << "罗马数字 " << roman4 << " 转换为整数是: " << solution.romanToInt(roman4) << endl;string roman5 = "MCMXCIV";cout << "罗马数字 " << roman5 << " 转换为整数是: " << solution.romanToInt(roman5) << endl;return 0;
}

以下是对代码的详细注释：

在romanToInt函数中：

1. unordered_map<char, int> romanMap = {... };：
   • 创建一个无序映射romanMap，用于存储罗马数字的每个字符（I、V、X、L、C、D、M）与其对应的整数值（1、5、10、50、100、500、1000）。这样可以方便地通过罗马数字字符获取其对应的数值。
2. int result = 0;：
   • 初始化一个变量result，用于存储最终转换得到的整数结果。
3. for (int i = 0; i < s.length(); i++)：
   • 开始遍历输入的罗马数字字符串s。
4. int currentValue = romanMap[s[i]];：
   • 通过romanMap获取当前罗马数字字符s[i]对应的整数值，并存储在currentValue中。
5. if (i < s.length() - 1)：
   • 判断当前字符是否不是字符串的最后一个字符。如果不是，需要考虑特殊情况（如IV、IX等）。
6. int nextValue = romanMap[s[i + 1]];：
   • 获取下一个罗马数字字符对应的整数值。
7. if (currentValue < nextValue)：
   • 如果当前字符的值小于下一个字符的值，说明遇到了特殊情况，需要减去当前值。例如在IV中，I（1）在V（5）之前，应该是5 - 1 = 4，所以这里减去currentValue。
8. else：
   • 如果当前值不小于下一个值，则正常将当前值加到result中。
9. if (i == s.length() - 1)：
   • 如果当前字符是最后一个字符，直接将其值加到result中。

在main函数中：

1. 创建Solution类的实例solution。
2. 定义了多个罗马数字字符串作为测试用例（roman1、roman2、roman3、roman4、roman5）。
3. 对于每个测试用例，调用solution.romanToInt函数将罗马数字转换为整数，并使用cout输出罗马数字和对应的转换结果。

这个算法通过遍历罗马数字字符串，根据罗马数字的规则（特殊情况和一般情况）来计算对应的整数值。时间复杂度为O(n)，其中n是罗马数字字符串的长度，因为需要遍历一次字符串。空间复杂度主要取决于romanMap的大小，是一个常数。

12. 整数转罗马数字

以下是使用 C++ 实现整数转罗马数字的代码

#include <iostream>
#include <string>
#include <vector>using namespace std;class Solution {
public:string intToRoman(int num) {// 定义数值和对应的罗马数字符号向量vector<int> values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};vector<string> symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};string result;for (int i = 0; i < values.size(); i++) {// 计算当前数值在num中出现的次数while (num >= values[i]) {num -= values[i];result += symbols[i];}}return result;}
};// 测试用例
int main() {Solution solution;int number1 = 3;cout << "整数 " << number1 << " 转换为罗马数字是: " << solution.intToRoman(number1) << endl;int number2 = 4;cout << "整数 " << number2 << " 转换为罗马数字是: " << solution.intToRoman(number2) << endl;int number3 = 9;cout << "整数 " << number3 << " 转换为罗马数字是: " << solution.intToRoman(number3) << endl;int number4 = 58;cout << "整数 " << number4 << " 转换为罗马数字是: " << solution.intToRoman(number4) << endl;int number5 = 1994;cout << "整数 " << number5 << " 转换为罗马数字是: " << solution.intToRoman(number5) << endl;return 0;
}

以下是代码的详细注释：

在intToRoman函数中：

1. vector<int> values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};和vector<string> symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};：
   • 定义了两个向量。values向量存储了从大到小的特定整数数值，这些数值是构成罗马数字的关键值。symbols向量存储了与values中每个数值对应的罗马数字符号。例如，1000对应M，900对应CM等。这种对应关系是根据罗马数字的表示规则确定的。
2. string result;：
   • 初始化一个空字符串result，用于存储最终转换得到的罗马数字。
3. for (int i = 0; i < values.size(); i++)：
   • 开始遍历values和symbols向量。这里通过一个循环同时处理数值和符号的对应关系。
4. while (num >= values[i])：
   • 只要输入的整数num大于等于当前values中的数值，就执行以下操作。这意味着尽可能多地使用当前的罗马数字符号来表示num。
5. num -= values[i];：
   • 从num中减去当前处理的数值，以更新num的值。
6. result += symbols[i];：
   • 将当前的罗马数字符号添加到result字符串中。

在main函数中：

1. 创建Solution类的实例solution。
2. 定义了多个整数作为测试用例（number1、number2、number3、number4、number5）。
3. 对于每个测试用例，调用solution.intToRoman函数将整数转换为罗马数字，并使用cout输出整数和对应的罗马数字。

这个算法通过从大到小遍历预先定义的数值和符号向量，尽可能多地使用大数值对应的符号来构建罗马数字，直到将整数完全转换。时间复杂度为O(n)，其中n是values向量的长度，因为在最坏情况下，需要遍历整个values向量来构建罗马数字。空间复杂度主要取决于values和symbols向量的大小以及result字符串的长度，在最坏情况下，result字符串的长度与输入整数成正比。

58. 最后一个单词的长度

以下是使用 C++ 实现计算最后一个单词长度的代码：

#include <iostream>
#include <string>using namespace std;class Solution {
public:int lengthOfLastWord(string s) {int n = s.length();int count = 0;// 从后往前遍历字符串for (int i = n - 1; i >= 0; i--) {// 如果当前字符不是空格，增加计数if (s[i]!= ' ') {count++;} else {// 如果当前字符是空格且已经有单词被计数，说明已经找到最后一个单词的末尾，返回计数if (count > 0) {return count;}}}return count;}
};// 测试用例
int main() {Solution solution;string str1 = "Hello World";cout << "字符串 \"" << str1 << "\" 最后一个单词的长度是: " << solution.lengthOfLastWord(str1) << endl;string str2 = "   fly me   to   the moon  ";cout << "字符串 \"" << str2 << "\" 最后一个单词的长度是: " << solution.lengthOfLastWord(str2) << endl;string str3 = "luffy is still joyboy";cout << "字符串 \"" << str3 << "\" 最后一个单词的长度是: " << solution.lengthOfLastWord(str3) << endl;return 0;
}

 

14. 最长公共前缀 

以下是使用 C++ 实现的最长公共前缀函数，该函数用于找出一组字符串中的最长公共前缀

#include <iostream>
#include <vector>
#include <string>using namespace std;class Solution {
public:string longestCommonPrefix(vector<string>& strs) {if (strs.empty()) {return "";}// 以第一个字符串为基准来比较string prefix = strs[0];for (int i = 1; i < strs.size(); i++) {string current = strs[i];int j = 0;// 比较当前字符串和基准字符串的每个字符while (j < prefix.length() && j < current.length() && prefix[j] == current[j]) {j++;}// 更新公共前缀if (j == 0) {return "";}prefix = prefix.substr(0, j);}return prefix;}
};// 测试用例
int main() {Solution solution;// 测试用例1：正常情况vector<string> strs1 = {"flower", "flow", "flight"};cout << "最长公共前缀（测试用例1）: " << solution.longestCommonPrefix(strs1) << endl;// 测试用例2：没有公共前缀vector<string> strs2 = {"dog", "racecar", "car"};cout << "最长公共前缀（测试用例2）: " << solution.longestCommonPrefix(strs2) << endl;// 测试用例3：只有一个字符串vector<string> strs3 = {"apple"};cout << "最长公共前缀（测试用例3）: " << solution.longestCommonPrefix(strs3) << endl;// 测试用例4：空字符串数组vector<string> strs4;cout << "最长公共前缀（测试用例4）: " << solution.longestCommonPrefix(strs4) << endl;return 0;
}

 

 151. 反转字符串中的单词

以下是使用 C++ 实现的反转字符串中的单词的代码：

#include <iostream>
#include <string>
#include <algorithm>class Solution {
public:// 函数用于反转字符串中的单词std::string reverseWords(std::string s) {// 去除字符串开头和结尾的空格s.erase(0, s.find_first_not_of(' '));s.erase(s.find_last_not_of(' ') + 1);// 反转整个字符串std::reverse(s.begin(), s.end());int start = 0;for (int i = 0; i <= s.length(); i++) {if (s[i] == ' ' || i == s.length()) {// 反转每个单词std::reverse(s.begin() + start, s.begin() + i);start = i + 1;}}// 处理多余空格std::string result;for (int i = 0; i < s.length(); i++) {if (s[i]!= ' ') {result += s[i];} else if (s[i] == ' ' && (i == 0 || s[i - 1]!= ' ')) {result += ' ';}}return result;}
};// 测试用例
int main() {Solution solution;std::string str1 = "the sky is blue";std::cout << "原始字符串: " << str1 << std::endl;std::cout << "反转单词后的字符串: " << solution.reverseWords(str1) << std::endl;std::string str2 = "  hello world!  ";std::cout << "原始字符串: " << str2 << std::endl;std::cout << "反转单词后的字符串: " << solution.reverseWords(str2) << std::endl;std::string str3 = "a good   example";std::cout << "原始字符串: " << str3 << std::endl;std::cout << "反转单词后的字符串: " << solution.reverseWords(str3) << std::endl;return 0;
}

 

 6. Z 字形变换

以下是使用 C++ 实现的6. Z 字形变换的代码：

#include <iostream>
#include <string>
#include <vector>using namespace std;class Solution {
public:string convert(string s, int numRows) {if (numRows == 1) {return s;}// 创建一个二维向量，用于存储Z字形排列的字符vector<vector<char>> matrix(numRows, vector<char>());int row = 0;bool goingDown = false;for (char c : s) {matrix[row].push_back(c);if (row == 0 || row == numRows - 1) {goingDown =!goingDown;}row += goingDown? 1 : -1;}string result;for (int i = 0; i < numRows; i++) {for (char c : matrix[i]) {result += c;}}return result;}
};// 测试用例
int main() {Solution solution;string s1 = "PAYPALISHIRING";int numRows1 = 3;cout << "原始字符串: " << s1 << ", numRows: " << numRows1 << endl;cout << "Z 字形变换后的字符串: " << solution.convert(s1, numRows1) << endl;string s2 = "PAYPALISHIRING";int numRows2 = 4;cout << "原始字符串: " << s2 << ", numRows: " << numRows2 << endl;cout << "Z 字形变换后的字符串: " << solution.convert(s2, numRows2) << endl;string s3 = "A";int numRows3 = 1;cout << "原始字符串: " << s3 << ", numRows: " << numRows3 << endl;cout << "Z 字形变换后的字符串: " << solution.convert(s3, numRows3) << endl;return 0;
}

28. 找出字符串中第一个匹配项的下标

以下是使用 C++ 实现28. 找出字符串中第一个匹配项的下标的代码，这里使用 KMP（Knuth - Morris - Pratt）算法。

#include <iostream>
#include <string>
#include <vector>class Solution {
public:int strStr(std::string haystack, std::string needle) {int m = haystack.size();int n = needle.size();// 处理特殊情况：当needle为空字符串时，返回0if (n == 0) {return 0;}// 构建next数组std::vector<int> next(n);next[0] = 0;int i = 0, j = 1;while (j < n) {// 如果当前字符和前缀字符相等，更新next数组if (needle[i] == needle[j]) {i++;next[j] = i;j++;} else {// 如果不相等，回溯iif (i!= 0) {i = next[i - 1];} else {// 如果i已经为0，next[j]为0next[j] = 0;j++;}}}i = 0;j = 0;while (i < m && j < n) {// 如果字符相等，继续匹配下一个字符if (haystack[i] == needle[j]) {i++;j++;} else {// 如果不相等，利用next数组回溯jif (j!= 0) {j = next[j - 1];} else {i++;}}}// 如果j等于needle的长度，说明找到了匹配项，返回其起始下标return (j == n)? (i - n) : -1;}
};// 测试用例
int main() {Solution solution;std::string haystack1 = "sadbutsad";std::string needle1 = "sad";std::cout << "在字符串 \"" << haystack1 << "\" 中查找 \"" << needle1 << "\" 的第一个匹配项下标: " << solution.strStr(haystack1, needle1) << std::endl;std::string haystack2 = "leetcode";std::string needle2 = "leeto";std::cout << "在字符串 \"" << haystack2 << "\" 中查找 \"" << needle2 << "\" 的第一个匹配项下标: " << solution.strStr(haystack2, needle2) << std::endl;std::string haystack3 = "a";std::string needle3 = "a";std::cout << "在字符串 \"" << haystack3 << "\" 中查找 \"" << needle3 << "\" 的第一个匹配项下标: " << solution.strStr(haystack3, needle3) << std::endl;return 0;
}

 双指针

125.验证回文串

以下是一种优化后的 C++ 代码实现125. 验证回文串，重点考虑了执行速度：

#include <iostream>
#include <string>using namespace std;class Solution {
public:bool isPalindrome(string s) {int n = s.length();int left = 0;int right = n - 1;// 定义两个字符数组，用于存储处理后的字符串（只包含字母和数字）char forward[n];char backward[n];int forwardIndex = 0;int backwardIndex = 0;// 从左到右遍历字符串，将字母和数字存储到forward数组for (int i = 0; i < n; i++) {if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z') || (s[i] >= '0' && s[i] <= '9')) {if (s[i] >= 'A' && s[i] <= 'Z') {forward[forwardIndex++] = s[i] + 32;  // 将大写字母转换为小写字母} else {forward[forwardIndex++] = s[i];}}}// 从右到左遍历字符串，将字母和数字存储到backward数组for (int i = n - 1; i >= 0; i--) {if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z') || (s[i] >= '0' && s[i] <= '9')) {if (s[i] >= 'A' && s[i] <= 'Z') {backward[backwardIndex++] = s[i] + 32;  // 将大写字母转换为小写字母} else {backward[backwardIndex++] = s[i];}}}// 比较两个数组中的字符是否相等for (int i = 0; i < forwardIndex; i++) {if (forward[i]!= backward[i]) {return false;}}return true;}
};// 测试用例
int main() {Solution solution;string str1 = "A man, a plan, a canal: Panama";cout << "字符串 \"" << str1 << "\" 是否是回文串: " << (solution.isPalindrome(str1)? "是" : "否") << endl;string str2 = "race a car";cout << "字符串 \"" << str2 << "\" 是否是回文串: " << (solution.isPalindrome(str2)? "是" : "否") << endl;string str3 = " ";cout << "字符串 \"" << str3 << "\" 是否是回文串: " << (solution.isPalindrome(str3)? "是" : "否") << endl;return 0;
}

392. 判断子序列 

 以下是使用 C++ 实现LeetCode 392. 判断子序列的代码示例，包括详细注释和测试用例。

#include <iostream>
// 判断子序列函数
bool isSubsequence(string s, string t) {// 指针i用于遍历子序列s，指针j用于遍历序列tint i = 0, j = 0;// 只要i还没遍历完s且j还没遍历完t，就继续循环while (i < s.length() && j < t.length()) {// 如果s[i]和t[j]相等，说明找到了一个匹配的字符，移动子序列指针iif (s[i] == t[j]) {i++;}// 无论是否匹配，都要移动序列t的指针jj++;}// 如果i成功遍历完s，说明s是t的子序列，返回true；否则返回falsereturn i == s.length();
}int main() {string s1 = "abc";string t1 = "ahbgdc";std::cout << "Is 'abc' a subsequence of 'ahbgdc'? " << (isSubsequence(s1, t1)? "Yes" : "No") << std::endl;string s2 = "axc";string t2 = "ahbgdc";std::cout << "Is 'axc' a subsequence of 'ahbgdc'? " << (isSubsequence(s2, t2)? "Yes" : "No") << std::endl;return 0;
}

167. 两数之和 II - 输入有序数组 

 

双指针法实现代码

#include <iostream>
#include <vector>using namespace std;// 函数用于在有序数组中找到两个数，使它们的和等于目标值
vector<int> twoSum(vector<int>& numbers, int target) {int left = 0;  // 左指针，初始指向数组的第一个元素int right = numbers.size() - 1;  // 右指针，初始指向数组的最后一个元素while (left < right) {  // 只要左指针小于右指针，就继续循环int sum = numbers[left] + numbers[right];  // 计算当前两个指针所指元素的和if (sum == target) {  // 如果和等于目标值// 返回两个数的下标（注意下标从1开始，所以要加1）return {left + 1, right + 1}; } else if (sum < target) {  // 如果和小于目标值left++;  // 左指针右移，尝试增大和} else {  // 如果和大于目标值right--;  // 右指针左移，尝试减小和}}return {-1, -1};  // 如果没有找到符合条件的两个数，返回{-1, -1}（这里实际上不会执行到，因为题目保证有解）
}int main() {// 测试用例1vector<int> numbers1 = {2, 7, 11, 15};int target1 = 9;vector<int> result1 = twoSum(numbers1, target1);std::cout << "For numbers [2,7,11,15] and target 9, the indices are: " << result1[0] << " and " << result1[1] << std::endl;// 测试用例2vector<int> numbers2 = {2, 3, 4};int target2 = 6;vector<int> result2 = twoSum(numbers2, target2);std::cout << "For numbers [2,3,4] and target 6, the indices are: " << result2[0] << " and " << result2[1] << std::endl;return 0;
}

 11. 盛最多水的容器

#include <iostream>
#include <vector>// 计算能盛最多水的容器的容量的函数
int maxArea(std::vector<int>& height) {int left = 0;  // 初始化左指针为数组起始位置int right = height.size() - 1;  // 初始化右指针为数组末尾位置int maxWater = 0;  // 用于存储最大水量，初始化为0// 只要左指针和右指针没有相遇，就继续循环while (left < right) { // 计算当前两个指针所构成容器的水量int currentWater = (right - left) * (height[left] < height[right]? height[left] : height[right]);// 更新最大水量maxWater = (maxWater > currentWater)? maxWater : currentWater;// 如果左边木板高度小于右边木板高度，将左指针向右移动一位if (height[left] < height[right]) { left++; } // 否则将右指针向左移动一位else { right--; }}return maxWater;  // 返回最大水量
}int main() {// 测试用例1std::vector<int> height1 = {1, 8, 6, 2, 5, 4, 8, 3, 7};int result1 = maxArea(height1);std::cout << "For height vector [1,8,6,2,5,4,8,3,7], the maximum area is: " << result1 << std::endl;// 测试用例2std::vector<int> height2 = {4, 3, 2, 1, 4};int result2 = maxArea(height2);std::cout << "For height vector [4,3,2,1,4], the maximum area is: " << result2 << std::endl;// 测试用例3std::vector<int> height3 = {1, 2, 1};int result3 = maxArea(height3);std::cout << "For height vector [1,2,1], the maximum area is: " << result3 << std::endl;return 0;
}

 15. 三数之和

 

#include <vector>
#include <algorithm>
#include <iostream>using namespace std;vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> result;  // 用于存储结果三元组sort(nums.begin(), nums.end());  // 对数组进行排序for (int i = 0; i < nums.size(); i++) {// 跳过重复的元素if (i > 0 && nums[i] == nums[i - 1]) {continue;}int left = i + 1;  // 左指针int right = nums.size() - 1;  // 右指针int target = -nums[i];  // 目标值，因为要使得三数之和为0while (left < right) {int sum = nums[left] + nums[right];  // 当前两数之和if (sum == target) {  // 如果和等于目标值result.push_back({nums[i], nums[left], nums[right]});// 跳过重复的元素while (left < right && nums[left] == nums[left + 1]) {left++;}while (left < right && nums[right] == nums[right - 1]) {right--;}left++;right--;} else if (sum < target) {  // 如果和小于目标值，增大和left++;} else {  // 如果和大于目标值，减小和right--;}}}return result;
}

5、测试用例 

int main() {vector<int> nums1 = {-1, 0, 1, 2, -1, -4};vector<vector<int>> result1 = threeSum(nums1);for (const auto& triplet : result1) {cout << "[";for (int num : triplet) {cout << num << " ";}cout << "]" << endl;}vector<int> nums2 = {0, 0, 0};vector<vector<int>> result2 = threeSum(nums2);for (const auto& triplet : result2) {cout << "[";for (int num : triplet) {cout << num << " ";}cout << "]" << endl;}return 0;
}

 滑动窗口

209. 长度最小的子数组

209. 长度最小的子数组

 

#include <vector>
#include <iostream>using namespace std;// 函数用于找到满足和大于等于给定值s的最小子数组长度
int minSubArrayLen(int s, vector<int>& nums) {int left = 0;  // 滑动窗口左边界int right = 0;  // 滑动窗口右边界int sum = 0;  // 当前窗口内元素的和int minLength = INT_MAX;  // 初始化为最大整数，用于记录最小子数组长度while (right < nums.size()) {sum += nums[right];  // 将右指针指向的元素加入窗口和while (sum >= s) {  // 当窗口内元素和大于等于s时int currentLength = right - left + 1;  // 计算当前窗口长度minLength = min(minLength, currentLength);  // 更新最小长度sum -= nums[left];  // 尝试缩小窗口，将左指针指向的元素从窗口和中减去left++;  // 移动左指针}right++;  // 移动右指针，扩大窗口}return (minLength == INT_MAX)? 0 : minLength;  // 如果最小长度仍为最大整数，则不存在符合条件的子数组，返回0；否则返回最小长度
}

int main() {// 测试用例1vector<int> nums1 = {2, 3, 1, 2, 4, 3};int s1 = 7;int result1 = minSubArrayLen(s1, nums1);cout << "For nums = [2,3,1,2,4,3] and s = 7, the minimum subarray length is: " << result1 << endl;// 测试用例2vector<int> nums2 = {1, 4, 4};int s2 = 4;int result2 = minSubArrayLen(s2, nums2);cout << "For nums = [1,4,4] and s = 4, the minimum subarray length is: " << result2 << endl;// 测试用例3vector<int> nums3 = {1, 1, 1, 1, 1, 1, 1, 1};int s3 = 11;int result3 = minSubArrayLen(s3, nums3);cout << "For nums = [1,1,1,1,1,1,1,1] and s = 11, the minimum subarray length is: " << result3 << endl;return 0;
}

3. 无重复字符的最长子串 

#include <iostream>
#include <string>
#include <unordered_map>// 函数用于计算给定字符串中无重复字符的最长子串的长度
int lengthOfLongestSubstring(std::string s) {std::unordered_map<char, int> charMap;  // 哈希表，用于记录字符及其在窗口中的位置int left = 0;  // 滑动窗口左边界int maxLength = 0;  // 用于记录最长子串长度for (int right = 0; right < s.length(); right++) {  // 移动右指针遍历字符串char currentChar = s[right];// 如果当前字符在哈希表中且其位置在当前窗口内（大于等于left）if (charMap.find(currentChar)!= charMap.end() && charMap[currentChar] >= left) {left = charMap[currentChar] + 1;  // 更新左指针，将窗口左移}charMap[currentChar] = right;  // 更新当前字符在哈希表中的位置maxLength = std::max(maxLength, right - left + 1);  // 更新最长子串长度}return maxLength;
}

int main() {std::string str1 = "abcabcbb";int result1 = lengthOfLongestSubstring(str1);std::cout << "For string \"abcabcbb\", the length of the longest substring without repeating characters is: " << result1 << std::endl;std::string str2 = "bbbbb";int result2 = lengthOfLongestSubstring(str2);std::cout << "For string \"bbbbb\", the length of the longest substring without repeating characters is: " << result2 << std::endl;std::string str3 = "pwwkew";int result3 = lengthOfLongestSubstring(str3);std::cout << "For string \"pwwkew\", the length of the longest substring without repeating characters is: " << result3 << std::endl;return 0;
}

30. 串联所有单词的子串 

 

76. 最小覆盖子串

#include <iostream>
#include <string>
#include <vector>
#include <climits>using namespace std;string minWindow(string s, string t) {// 使用vector模拟哈希表，大小为128（ASCII码范围）vector<int> need(128, 0);vector<int> window(128, 0);int tLen = t.size();int sLen = s.size();int count = 0;  // 记录当前窗口中已经匹配的t中字符的数量int minLen = INT_MAX;  // 最小窗口长度，初始化为最大整数int minLeft = 0;  // 最小窗口的左边界// 统计目标字符串t中每个字符的出现次数for (int i = 0; i < tLen; i++) {need[t[i]]++;}int left = 0;  // 滑动窗口左边界for (int right = 0; right < sLen; right++) {char c = s[right];window[c]++;// 如果当前窗口中字符c的出现次数不超过目标字符串中c的出现次数，匹配字符数加1if (window[c] <= need[c]) {count++;}// 当窗口中已经匹配了目标字符串t的所有字符while (count == tLen && left <= right) {// 更新最小窗口长度和左边界if (right - left + 1 < minLen) {minLen = right - left + 1;minLeft = left;}char d = s[left];window[d]--;// 如果移除窗口左边界字符后，该字符的出现次数小于目标字符串中该字符的出现次数，匹配字符数减1if (window[d] < need[d]) {count--;}left++;}}return minLen == INT_MAX? "" : s.substr(minLeft, minLen);
}

 

int main() {string s1 = "ADOBECODEBANC";string t1 = "ABC";cout << "For s = \"ADOBECODEBANC\" and t = \"ABC\", the minimum window is: " << minWindow(s1, t1) << endl;string s2 = "a";string t2 = "a";cout << "For s = \"a\" and t = \"a\", the minimum window is: " << minWindow(s2, t2) << endl;string s3 = "ab";string t3 = "a";cout << "For s = \"ab\" and t = \"a\", the minimum window is: " << minWindow(s3, t3) << endl;string s4 = "aaflslfldkalskaaa";string t4 = "aaa";cout << "For s = \"aaflslfldkalskaaa\" and t = \"aaa\", the minimum window is: " << minWindow(s4, t4) << endl;return 0;
}

 

矩阵 

36. 有效的数独

 

#include <vector>using namespace std;class Solution {
public:bool isValidSudoku(vector<vector<char>>& board) {// 用于记录每行数字出现的情况，初始化为falsevector<vector<bool>> row(9, vector<bool>(9, false)); // 用于记录每列数字出现的情况，初始化为falsevector<vector<bool>> col(9, vector<bool>(9, false)); // 用于记录每个3x3子数独数字出现的情况，初始化为falsevector<vector<bool>> box(9, vector<bool>(9, false)); for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {if (board[i][j]!= '.') {int num = board[i][j] - '1';  // 将字符数字转换为0 - 8的整数int boxIndex = (i / 3) * 3 + (j / 3);  // 计算3x3子数独的索引// 检查行if (row[i][num]) return false;row[i][num] = true;// 检查列if (col[j][num]) return false;col[j][num] = true;// 检查3x3子数独if (box[boxIndex][num]) return false;box[boxIndex][num] = true;}}}return true;}
};

#include <iostream>
#include <vector>using namespace std;int main() {// 有效数独示例vector<vector<char>> validBoard = {{'5', '3', '.', '.', '7', '.', '.', '.', '.'},{'6', '.', '.', '1', '9', '5', '.', '.', '.'},{'.', '9', '8', '.', '.', '.', '.', '6', '.'},{'8', '.', '.', '.', '6', '.', '.', '.', '3'},{'4', '.', '.', '8', '.', '3', '.', '.', '1'},{'7', '.', '.', '.', '2', '.', '.', '.', '6'},{'.', '6', '.', '.', '.', '.', '2', '8', '.'},{'.', '.', '.', '4', '1', '9', '.', '.', '5'},{'.', '.', '.', '.', '8', '.', '.', '7', '9'}};Solution solution;cout << "Is the valid board valid? " << (solution.isValidSudoku(validBoard)? "Yes" : "No") << endl;// 无效数独示例（第一行有重复数字5）vector<vector<char>> invalidBoard = {{'5', '3', '5', '.', '7', '.', '.', '.', '.'},{'6', '.', '.', '1', '9', '5', '.', '.', '.'},{'.', '9', '8', '.', '.', '.', '.', '6', '.'},{'8', '.', '.', '.', '6', '.', '.', '.', '3'},{'4', '.', '.', '8', '.', '3', '.', '.', '1'},{'7', '.', '.', '.', '2', '.', '.', '.', '6'},{'.', '6', '.', '.', '.', '.', '2', '8', '.'},{'.', '.', '.', '4', '1', '9', '.', '.', '5'},{'.', '.', '.', '.', '8', '.', '.', '7', '9'}};cout << "Is the invalid board valid? " << (solution.isValidSudoku(invalidBoard)? "Yes" : "No") << endl;return 0;
}

54. 螺旋矩阵 

#include <vector>using namespace std;vector<int> spiralOrder(vector<vector<int>>& matrix) {if (matrix.empty()) {return {};}int m = matrix.size();  // 矩阵的行数int n = matrix[0].size();  // 矩阵的列数vector<int> result;int left = 0, right = n - 1, top = 0, bottom = m - 1;while (left <= right && top <= bottom) {// 从左到右遍历上边界for (int j = left; j <= right; j++) {result.push_back(matrix[top][j]);}top++;// 当上边界和下边界重合时，说明已经遍历完所有行，跳出循环if (top > bottom) {break;}// 从上到下遍历右边界for (int i = top; i <= bottom; i++) {result.push_back(matrix[i][right]);}right--;// 当右边界和左边界重合时，说明已经遍历完所有列，跳出循环if (left > right) {break;}// 从右到左遍历下边界for (int j = right; j >= left; j--) {result.push_back(matrix[bottom][j]);}bottom--;// 从下到上遍历左边界for (int i = bottom; i >= top; i--) {result.push_back(matrix[i][left]);}left++;}return result;
}

#include <iostream>
#include <vector>using namespace std;int main() {// 测试用例1vector<vector<int>> matrix1 = {{1, 2, 3},{4, 5, 6},{7, 8, 9}};vector<int> result1 = spiralOrder(matrix1);for (int num : result1) {cout << num << " ";}cout << endl;// 测试用例2vector<vector<int>> matrix2 = {{1, 2, 3, 4},{5, 6, 7, 8},{9, 10, 11, 12}};vector<int> result2 = spiralOrder(matrix2);for (int num : result2) {cout << num << " ";}cout << endl;return 0;
}

48. 旋转图像，向右旋转90° 

#include <vector>using namespace std;class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size();// 转置矩阵for (int i = 0; i < n; ++i) {for (int j = i; j < n; ++j) {swap(matrix[i][j], matrix[j][i]);}}// 水平翻转for (int i = 0; i < n; ++i) {for (int j = 0; j < n / 2; ++j) {swap(matrix[i][j], matrix[i][n - j - 1]);}}}
};

#include <iostream>
#include <vector>using namespace std;// 打印矩阵函数
void printMatrix(vector<vector<int>>& matrix) {for (int i = 0; i < matrix.size(); i++) {for (int j = 0; j < matrix[i].size(); j++) {cout << matrix[i][j] << " ";}cout << endl;}
}int main() {// 测试用例1：3x3矩阵vector<vector<int>> matrix1 = {{1, 2, 3},{4, 5, 6},{7, 8, 9}};Solution solution;solution.rotate(matrix1);printMatrix(matrix1);// 测试用例2：4x4矩阵vector<vector<int>> matrix2 = {{1, 2, 3, 4},{5, 6, 7, 8},{9, 10, 11, 12},{13, 14, 15, 16}};solution.rotate(matrix2);printMatrix(matrix2);return 0;
}

73. 矩阵置零 

#include <vector>using namespace std;class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {int m = matrix.size();int n = matrix[0].size();bool firstRowZero = false;bool firstColZero = false;// 检查第一行是否有0for (int j = 0; j < n; j++) {if (matrix[0][j] == 0) {firstRowZero = true;break;}}// 检查第一列是否有0for (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;}}}// 根据标记置零除第一行和第一列外的元素for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (matrix[i][0] == 0 || matrix[0][j] == 0) {matrix[i][j] = 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;}}}
};

#include <iostream>
#include <vector>using namespace std;// 打印矩阵函数
void printMatrix(vector<vector<int>>& matrix) {int m = matrix.size();int n = matrix[0].size();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {cout << matrix[i][j] << " ";}cout << endl;}
}int main() {// 测试用例1vector<vector<int>> matrix1 = {{1, 1, 1},{1, 0, 1},{1, 1, 1}};Solution solution;solution.setZeroes(matrix1);printMatrix(matrix1);// 测试用例2vector<vector<int>> matrix2 = {{0, 1, 2, 0},{3, 4, 5, 2},{1, 3, 1, 5}};solution.setZeroes(matrix2);printMatrix(matrix2);return 0;
}

 289. 生命游戏

 

#include <vector>using namespace std;class Solution {
public:void gameOfLife(vector<vector<int>>& board) {int m = board.size();int n = board[0].size();// 用于记录下一轮的细胞状态，初始化为0vector<vector<int>> nextBoard(m, vector<int>(n, 0));// 八个方向的偏移量，用于遍历周围细胞int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {int liveNeighbors = 0;// 遍历当前细胞周围的8个细胞for (int k = 0; k < 8; k++) {int newX = i + dx[k];int newY = j + dy[k];// 判断新坐标是否在棋盘内，并且统计活细胞数量if (newX >= 0 && newX < m && newY >= 0 && newY < n && (board[newX][newY] == 1 || board[newX][newY] == -1)) {liveNeighbors++;}}// 根据规则确定下一轮当前细胞的状态if (board[i][j] == 1 && (liveNeighbors == 2 || liveNeighbors == 3)) {nextBoard[i][j] = 1;} else if (board[i][j] == 0 && liveNeighbors == 3) {nextBoard[i][j] = 1;} else if (board[i][j] == 1) {nextBoard[i][j] = -1; // 标记当前活细胞下一轮将死亡}}}// 将下一轮的状态复制回原棋盘for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (nextBoard[i][j] == 1) {board[i][j] = 1;} else {board[i][j] = 0;}}}}
};

 5、测试用例

#include <iostream>
#include <vector>using namespace std;// 打印棋盘函数
void printBoard(vector<vector<int>>& board) {int m = board.size();int n = board[0].size();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {cout << board[i][j] << " ";}cout << endl;}
}int main() {// 测试用例1vector<vector<int>> board1 = {{0, 1, 0},{0, 0, 1},{1, 1, 1},{0, 0, 0}};Solution solution;solution.gameOfLife(board1);printBoard(board1);// 测试用例2vector<vector<int>> board2 = {{1, 1},{1, 0}};solution.gameOfLife(board2);printBoard(board2);return 0;
}

哈希表 

383. 赎金信

 

#include <string>using namespace std;class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int char_count[26] = {0};  // 用于模拟哈希表，统计字符出现次数，初始化为0// 遍历杂志字符串，统计每个字符出现的次数for (char c : magazine) {char_count[c - 'a']++;  // 通过字符与 'a' 的差值作为索引来统计}// 遍历赎金信字符串，减少相应字符的计数for (char c : ransomNote) {char_count[c - 'a']--;if (char_count[c - 'a'] < 0) {  // 如果计数小于0，说明杂志中的字符不够组成赎金信return false;}}return true;}
};

#include <iostream>int main() {Solution solution;// 测试用例1：可以组成赎金信std::string ransomNote1 = "aa";std::string magazine1 = "aaa";std::cout << "For ransomNote = \"aa\" and magazine = \"aaa\", can construct? " << (solution.canConstruct(ransomNote1, magazine1)? "Yes" : "No") << std::endl;// 测试用例2：不可以组成赎金信std::string ransomNote2 = "abc";std::string magazine2 = "abd";std::cout << "For ransomNote = \"abc\" and magazine = \"abd\", can construct? " << (solution.canConstruct(ransomNote2, magazine2)? "Yes" : "No") << std::endl;// 测试用例3：可以组成赎金信std::string ransomNote3 = "a";std::string magazine3 = "b a";std::cout << "For ransomNote = \"a\" and magazine = \"b a\", can construct? " << (solution.canConstruct(ransomNote3, magazine3)? "Yes" : "No") << std::endl;return 0;
}

 205. 同构字符串

#include <string>
#include <unordered_map>using namespace std;class Solution {
public:bool isIsomorphic(string s, string t) {unordered_map<char, char> s_to_t;unordered_map<char, char> t_to_s;for (int i = 0; i < s.length(); i++) {char s_char = s[i];char t_char = t[i];// 检查s到t的映射if (s_to_t.find(s_char)!= s_to_t.end()) {if (s_to_t[s_char]!= t_char) {return false;}} else {s_to_t[s_char] = t_char;}// 检查t到s的映射if (t_to_s.find(t_char)!= t_to_s.end()) {if (t_to_s[t_char]!= s_char) {return false;}} else {t_to_s[t_char] = s_char;}}return true;}
};

#include <iostream>int main() {Solution solution;// 测试用例1：同构字符串string s1 = "egg";string t1 = "add";std::cout << "For s = \"egg\" and t = \"add\", are they isomorphic? " << (solution.isIsomorphic(s1, t1)? "Yes" : "No") << std::endl;// 测试用例2：不同构字符串string s2 = "foo";string t2 = "bar";std::cout << "For s = \"foo\" and t = \"bar\", are they isomorphic? " << (solution.isIsomorphic(s2, t2)? "Yes" : "No") << std::endl;// 测试用例3：同构字符串string s3 = "paper";string t3 = "title";std::cout << "For s = \"paper\" and t = \"title\", are they isomorphic? " << (solution.isIsomorphic(s3, t3)? "Yes" : "No") << std::endl;return 0;
}

#include <string>using namespace std;class Solution {
public:bool isIsomorphic(string s, string t) {int s_map[256] = {0};  // 假设ASCII码字符，用于记录s到t的映射，初始化为0int t_map[256] = {0};  // 用于记录t到s的映射，初始化为0for (int i = 0; i < s.length(); i++) {char s_char = s[i];char t_char = t[i];// 检查s到t的映射if (s_map[s_char]!= 0 && s_map[s_char]!= t_char) {return false;}s_map[s_char] = t_char;// 检查t到s的映射if (t_map[t_char]!= 0 && t_map[t_char]!= s_char) {return false;}t_map[t_char] = s_char;}return true;}
};

290. 单词规律 

class Solution {
public:bool wordPattern(string pattern, string str) {// 创建两个无序映射（哈希表），str2ch用于存储字符串到字符的映射，ch2str用于存储字符到字符串的映射unordered_map<string, char> str2ch;unordered_map<char, string> ch2str;int m = str.length();  // 获取输入字符串str的长度int i = 0;  // 用于在str中标记当前位置// 遍历模式字符串patternfor (auto ch : pattern) {// 如果已经遍历完str字符串（索引超出范围），则不符合规律，返回falseif (i >= m) {return false;}int j = i;// 从当前位置i开始，找到下一个空格的位置，以此来提取一个单词while (j < m && str[j]!= ' ') {j++;}// 提取从i到j（不包含j）的子字符串，这里使用引用是为了避免不必要的拷贝const string &tmp = str.substr(i, j - i);// 如果tmp已经在str2ch中，检查其映射的字符是否与当前模式字符ch一致，不一致则返回falseif (str2ch.count(tmp) && str2ch[tmp]!= ch) {return false;}// 如果ch已经在ch2str中，检查其映射的字符串是否与当前单词tmp一致，不一致则返回falseif (ch2str.count(ch) && ch2str[ch]!= tmp) {return false;}// 在str2ch中建立tmp到ch的映射str2ch[tmp] = ch;// 在ch2str中建立ch到tmp的映射ch2str[ch] = tmp;// 更新i的位置，跳过当前提取的单词和空格i = j + 1;}// 最后检查是否已经完整遍历完str字符串，如果是，则说明符合规律，返回true；否则返回falsereturn i >= m;}
};

这段代码的功能是判断给定的模式字符串pattern和单词字符串str是否遵循相同的规律。它通过同时遍历两个字符串，使用两个哈希表来记录字符串与字符之间的映射关系，在遍历过程中检查映射的一致性。如果在任何时候发现不一致或者没有完整遍历完str字符串（即单词数量和模式字符数量不匹配），则返回false；只有当完整遍历完str且映射关系始终一致时，才返回true。

242. 有效的字母异位词

class Solution {
public:bool isAnagram(string s, string t) {// 如果两个字符串的长度不相等，它们不可能是字母异位词，直接返回falseif (s.length()!= t.length()) {return false;}// 创建一个大小为26的整数向量，用于记录每个字母（假设只考虑小写字母）出现的次数，初始化为0vector<int> table(26, 0);// 遍历字符串s，对于其中的每个字符chfor (auto& ch: s) {// 将字符ch转换为0 - 25的索引（通过减去'a'的ASCII值），并在table中对应的位置加1，表示该字母出现了一次table[ch - 'a']++;}// 遍历字符串t，对于其中的每个字符chfor (auto& ch: t) {// 将字符ch转换为0 - 25的索引，并在table中对应的位置减1，表示使用了一次该字母table[ch - 'a']--;// 如果在减1之后，该位置的值小于0，说明在t中出现了s中没有的字母，或者某个字母在t中出现的次数多于在s中出现的次数，所以不是字母异位词，返回falseif (table[ch - 'a'] < 0) {return false;}}// 如果两个字符串长度相等，并且在遍历t的过程中没有发现不匹配的情况，那么它们是字母异位词，返回truereturn true;}
};