LeetCode新手村

博友们，如果觉得看文字不好理解，可以看我的讲解视频：讲解视频

2022/6/6

1480.一维数组的动态和

给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。
请返回 nums 的动态和。

示例 1：

输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。

示例 2：

输入：nums = [1,1,1,1,1]
输出：[1,2,3,4,5]
解释：动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。

示例 3：

输入：nums = [3,1,2,10,1]
输出：[3,4,6,16,17]

解题思路为：

初始化一个新的数组为sum,数组的长度即为输入数组的长度，
由题可知
sums[0]=nums[0];
sums[i]=nums[i]+sums[i-1];
使用for循环遍历进行计算，计算次数为nums的长度，注意从i=1进行循环。

class Solution {
public:vector<int> runningSum(vector<int>& nums) {vector<int> sum(nums.size());sum[0]=nums[0];for(int i=1;i<nums.size();i++){sum[i]=sum[i-1]+nums[i];}return sum;
}};

2.c++的for auto用法
for(auto item:list)进行遍历数组中的全部元素，不改变数组元素大小，
for(auto &item:list)改变item的值就改变了数组元素的值。
3.js的for of用法
for(let item of list)进行遍历数组list的每一个元素值。
4.charCodeAt()
用于返回一个字符的unicode值

383. 赎金信

题目：
给你两个字符串：ransomNote 和 magazine ，判断ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入：ransomNote = “a”, magazine = “b”
输出：false

示例 2：

输入：ransomNote = “aa”, magazine = “ab”
输出：false

示例 3：

输入：ransomNote = “aa”, magazine = “aab”
输出：true

解题思路为：

1.首先如果magazine的字符的个数小于ransomNote的个数，则返回为false。

2.统计magazine中每个字母出现的个数，统计ransomNote中每个字母的个数，比较两个集合中相同字母出现个数的比较，例如，若magazine中a的个数小于ransomNote中a的个数，则返回false。

c代码

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {
vector<int> num(26);
if(ransomNote.size()>magazine.size())
return false;//对magazine出现的26个字母的个数进行统计，分别统计每个字母出现的个数
for(auto item:magazine){   num[item-'a']++;
} 
//对ransomeNote出现的的字母得个数进行统计，对magazine中每个字母进行相减，
//若值小于为0，则说明ransomNote中字母个数多于magazine中字母个数，则返回false.
for(auto item:ransomNote){     num[item-'a']--;if(num[item-'a']<0)return false;
}
return true;}
};

javascript

/*** @param {string} ransomNote* @param {string} magazine* @return {boolean}*/
var canConstruct = function(ransomNote, magazine) {
let num=new Array(26).fill(0);
if(ransomNote.length>magazine.length)
return false;
for(let item of magazine)
{num[item.charCodeAt()-'a'.charCodeAt()]++;
}
for(let item of ransomNote){num[item.charCodeAt()-'a'.charCodeAt()]--;if(num[item.charCodeAt()-'a'.charCodeAt()]<0){return false;}}
return true;
};

2022/6/8

c++
push_back和emplace_back都是在容器末尾添加一个新元素进去。
to_string()将整数i转换为字符串表现形式i

412. Fizz Buzz

给你一个整数 n ，找出从 1 到 n 各个整数的 Fizz Buzz 表示，并用字符串数组 answer（下标从 1 开始）返回结果，其中：

answer[i] == “FizzBuzz” 如果 i 同时是 3 和 5 的倍数。
answer[i] == “Fizz” 如果 i 是 3 的倍数。
answer[i] == “Buzz” 如果 i 是 5 的倍数。
answer[i] == i （以字符串形式）如果上述条件全不满足。

示例 1：

输入：n = 3
输出：[“1”,“2”,“Fizz”]

示例 2：

输入：n = 5
输出：[“1”,“2”,“Fizz”,“4”,“Buzz”]

示例 3：

输入：n = 15
输出：[“1”,“2”,“Fizz”,“4”,“Buzz”,“Fizz”,“7”,“8”,“Fizz”,“Buzz”,“11”,“Fizz”,“13”,“14”,“FizzBuzz”]

解题思路：

1.就是先创建一个字符数组vector answer,给定整数n进行for循环，创建一个字符串string ctn,if(n%3==0)ctn+="Fizz";if(n%5==0) ctn+="Buzz";

如果ctn的大小为0，则说明应该添加整数i，将整数变为字符格式，使用to_string()进行转换。

class Solution {
public:vector<string> fizzBuzz(int n) {vector<string> answer;for(int i=1;i<=n;i++){string curr;if(i%3==0)curr+="Fizz";if(i%5==0)curr+="Buzz";if(curr.size()==0)curr+=to_string(i);answer.emplace_back(curr);}return answer;}
};

876. 链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

解题思路：数组法

首先创建一个数组指向头节点，将链表中的每一个元素放入到数组中，得到数组的中部元素，也就是数组长度/2,就得到了链表中的中间元素.

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* middleNode(ListNode* head) {vector<ListNode *> cur={head};while(cur.back()->next!=NULL){cur.push_back(cur.back()->next);}return cur[cur.size()/2];}
};

2022/6/10

1342.将数字变成 0 的操作次数

将数字变成 0 的操作次数给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。

示例 1：

输入：num = 14
输出：6
解释：
步骤 1) 14 是偶数，除以 2 得到 7 。
步骤 2） 7 是奇数，减 1 得到 6 。
步骤 3） 6 是偶数，除以 2 得到 3 。
步骤 4） 3 是奇数，减 1 得到 2 。
步骤 5） 2 是偶数，除以 2 得到 1 。
步骤 6） 1 是奇数，减 1 得到 0 。

示例 2：

输入：num = 8
输出：4
解释：
步骤 1） 8 是偶数，除以 2 得到 4 。
步骤 2） 4 是偶数，除以 2 得到 2 。
步骤 3） 2 是偶数，除以 2 得到 1 。
步骤 4） 1 是奇数，减 1 得到 0 。

示例 3：

输入：num = 123
输出：12

解题思路：

使用for循环，当num的值小于0时跳出循环，当num%2==0时，num=num/2,当num%2==1时，num-=num。

class Solution {
public:int numberOfSteps(int num) {
int ctn=0;
while(num>0){
if(num%2==0)
num=num/2;
else
num-=1;
ctn++;}
return ctn;}
};

1672. 最富有客户的资产总量

给你一个 m x n 的整数网格 accounts ，其中 accounts[i][j] 是第 i​​​​​​​​​​​​ 位客户在第 j 家银行托管的资产数量。返回最富有客户所拥有的 资产总量 。

客户的 资产总量 就是他们在各家银行托管的资产数量之和。最富有客户就是 资产总量 最大的客户。

示例 1：

输入：accounts = [[1,2,3],[3,2,1]]
输出：6
解释：
第 1 位客户的资产总量 = 1 + 2 + 3 = 6
第 2 位客户的资产总量 = 3 + 2 + 1 = 6
两位客户都是最富有的，资产总量都是 6 ，所以返回 6 。

示例 2：

输入：accounts = [[1,5],[7,3],[3,5]]
输出：10
解释：
第 1 位客户的资产总量 = 6
第 2 位客户的资产总量 = 10
第 3 位客户的资产总量 = 8
第 2 位客户是最富有的，资产总量是 10

示例 3：

输入：accounts = [[2,8,7],[7,1,3],[1,9,5]]
输出：17

解题思路：

首先使用for循环遍历每行的元素，将每行的元素累加起来后，通过比较大小来确定最大值。

1.累加求和

int sum = accumulate(vec.begin() , vec.end() , 42);
accumulate带有三个形参：头两个形参指定要累加的元素范围，第三个形参则是累加的初值。

accumulate函数将它的一个内部变量设置为指定的初始值，然后在此初值上累加输入范围内所有元素的值。accumulate算法返回累加的结果，其返回类型就是其第三个实参的类型。

class Solution {
public:int maximumWealth(vector<vector<int>>& accounts) {int maxWealth=0;for(auto item:accounts){maxWealth=max(maxWealth,accumulate(item.begin(),item.end(),0));}return maxWealth;}
};

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

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = […]; // 输入数组
int[] expectedNums = […]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; }
如果所有断言都通过，那么您的题解将被 通过。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

解题思路：

题目要求为传入一个数组，传出符合条件后的数组的长度，设置两个指针，分别为快指针和慢指针，快指针与慢指针的初始化均为1，因为0号元素一定是不需要变动位置的，排序从从小到大的顺序进行排序，块指针遍历整个数组元素，若nums[fast]!=nums[fast-1],则将nums[slow]=nums[fast],slow值加1.

class Solution {
public:int removeDuplicates(vector<int>& nums) {if(nums.size()==0)return 0;int fast=1,slow=1;int n=nums.size();while(fast<n){if(nums[fast]!=nums[fast-1]){nums[slow]=nums[fast];slow++;}fast++;}return slow;}
};

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

解题思路：

将两个有序链表进行连接，将两个链表进行连接起来，不占用新的空间，常见一个新的头结点prevhead，定义一个新的指针prev指向prevhead，当两个链表均不为空时，对节点进行遍历，当list1->val<list2->val时,让prev指向list1，list1右移，当list2->val<list1->val时,让prev指向list2，list2右移，让prev=prev->next让prev向右移动，最后prev->next=list1==nullptr?list2:list1;list1是否为空，若是，则prev->next=list2,若不是空，则prev->next=list1.

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode * prevhead=new ListNode(-1);ListNode * prev=prevhead;while(list1!=nullptr&&list2!=nullptr){if(list1->val<list2->val){prev->next=list1;list1=list1->next;}else{prev->next=list2;list2=list2->next;}
prev=prev->next;}prev->next=list1==nullptr?list2:list1;return prevhead->next;}
};

2022/6/22

283.移动零

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

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

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

解题思路：双指针

1、定义两个指针i和k，初始化i = 0，k = 0。

2、i指针向后移动，遍整个nums数组，如果 nums[i] != 0，也就是说遇到了非0元素，此时我们就将nums[i]元素放置到nums[k]位置，同时k++后一位。

3、最后将k位置之后的元素都赋值为0。

实现细节：

遍历数组可以使用for(int x : nums)，这样就少定义一个指针，代码也显得更加简洁。

时间复杂度分析： O(n)O(n) ，nn是数组的长度，每个位置只被遍历一次。

时间复杂度分析： O(1)O(1) ，只需要常数的空间存放指针变量。

class Solution {
public:void moveZeroes(vector<int>& nums) {int k = 0;for(int x : nums)if(x != 0) nums[k++] = x;while(k < nums.size())  nums[k++] = 0;        }
};

2022/6/23

27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

解题思路：

设置双指针法，将left、right同时指向数组的第一个元素即a[0],首先遍历数组的所有元素，当元素不等于val值时,将右指针所指的值赋值给左指针所指向元素的值，同时左指针右移1个单位。当右指针访问遍历完整个数组后，返回左指针的值即可。

class Solution {
public:int removeElement(vector<int>& nums, int val) {int i=0;for(int x:nums){if(x!=val){nums[i]=x;i++;}}return i;}
};

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

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。

更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = […]; // 输入数组
int[] expectedNums = […]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过，那么您的题解将被 通过。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

解题思路：

为首先设置双指针fast,slow指向nums[1],判断nums[fast]是否等nums[fast-1],若等于则fast++，即fast指针右移。若不等于，将fast指针指向的值赋值给slow指针指向的数字，即a[slow]=a[fast]然后将slow++,fast++,最后当fast遍历完整个数组后，返回slow即可。

class Solution {
public:int removeDuplicates(vector<int>& nums) {int fast=1;int slow=1;while(fast<nums.size()){if(nums[fast-1]!=nums[fast]){nums[slow]=nums[fast];slow++;}   fast++;}return slow;}
};

2022/6/24

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

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

说明：

为什么返回数值是整数，但输出的答案是数组呢？

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}

示例 1：

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。

解题思路：

首先设置双指针分别为fast和slow，让fast依次遍历访问每一个数组元素，因为由题意可知连续的2个元素相同时不改变，所以用nums[fast]与nums[slow-2]进行比较，若不相等，则将nums[fast]的值赋值给nums[slow],slow++,即向右移动一个单位。

class Solution {
public:int removeDuplicates(vector<int>& nums) {int fast=2;int slow=2;if(nums.size()<=2)return nums.size();while(fast<nums.size()){if(nums[fast]!=nums[slow-2]){nums[slow]=nums[fast];slow++;}fast++;}return slow;}
};

2022/6/25

75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

解题思路为：

首先设置一个指针ptr指向nums[0]，让0先排序到数组的前部分，然后让1排序到0元素的后面，最后剩余2。具体过程为首先遍历整个数组，让如果nums[i]==0时，让nums[i]与nums[ptr]进行交换，ptr++。当把0元素排序到数组的前面时，从ptr开始遍历剩下的元素，如果nums[i]==1时，并把nums[ptr]=nums[i],并让ptr++。
具体代码为：

class Solution {
public:void sortColors(vector<int>& nums) {int ptr=0;for(int i=0;i<nums.size();i++){if(nums[i]==0){swap(nums[i],nums[ptr]);ptr++; }} for(int i=ptr;i<nums.size();i++){if(nums[i]==1){swap(nums[i],nums[ptr]);ptr++;}}}
};

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

解题思路为：

方法一：直接合并后排序

将nums2放进nums1的尾部，对整个数组进行排序。

时间复杂度为：O((m+n)log(m+n))。

空间复杂度为：O(log(m+n))。

排序序列长度为 m+n，套用快速排序的空间复杂度即可，平均情况为 O(log(m+n))。

代码为：

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {for (int i = 0; i != n; ++i) {nums1[m + i] = nums2[i];}sort(nums1.begin(), nums1.end());}
};

方法二：

对2个数组nums1和nums2的元素进行比较，将小的元素放入到新生成的数组nums3当中。因为2个数组都是按从小到大的顺序进行的排序，当将一个数组当中的元素全部放入到nums3当中后，将另一个数组中的全部元素依次放入到nums3当中即可。

需要注意的是，首先判断nums1的元素是否遍历完了，若全部都访问了，则将数组nums2的全部元素都放入到nums3当中。

否则若数组nums2当中的全部元素都访问后，将nums1的元素放入到nums3当中。

否则，两个数组元素都没有被访问完，所以依次比较两个数组元素的大小

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {vector<int> nums3(m+n);int i=0;int j=0;int temp;while(i<m||j<n){if(i==m){temp=nums2[j];j++;}else  if(j==n){temp=nums1[i];i++;}else if(nums1[i]<nums2[j]){temp=nums1[i];i++;}else{temp=nums2[j];j++;}nums3[i+j-1]=temp;}for(int i=0;i<m+n;i++){nums1[i]=nums3[i];}}
};

2022/7/4

125. 验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: “A man, a plan, a canal: Panama”
输出: true
解释：“amanaplanacanalpanama” 是回文串

示例 2:

输入: “race a car”
输出: false
解释：“raceacar” 不是回文串

解题思路：

设置左右指针分别指向字符串的首端和末端，依次比较所指向的数字是否相同？若相同则left++，right–,直至left==right时，则遍历结束。

注意：用到的API为isalnum()函数用来检测一个字符是否是字母或十进制数字。

返回值非0表示字符为字母或十进制数字，返回值为0表示字符为非字母或非十进制数字。

2.tolower()用来将大写字母返回为小写字母。

class Solution {
public:bool isPalindrome(string s) {int left=0;string tea;for(char c:s){if(isalnum(c)){tea+=tolower(c);}}
int right=tea.size()-1;while(left<right){if(tea[left]==tea[right]){left++;right--;}else{return false;break;}}return true;}
};

时间复杂度为：O(|s|),|s|为s的长度。

空间复杂度为：O(|s|),由于我们需要将所有的字母和数字字符存放在另一个字符串中，在最坏情况下，新的字符串与原字符串完全相同，因此需要使用O(|s|)的空间。

2022/7/5

345. 反转字符串中的元音字母

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。

元音字母包括 ‘a’、‘e’、‘i’、‘o’、‘u’，且可能以大小写两种形式出现。

示例 1：

输入：s = “hello”
输出：“holle”

示例 2：

输入：s = “leetcode”
输出：“leotcede”

解题思路：

利用双指针法，首先设置2个指针left、right分别指向字符串的第0个元素和最后一个元素，当left<right时，让left指针一直向右移动直到指向一个元音字母，同时，让right指针不停地向左移动，直到指向一个元音字母，此时，若left<right,让s[left]与s[right]交换，否则所有的元音字母都遍历过了，退出过程。

class Solution {
public:string reverseVowels(string s) {int left=0;int right=s.size()-1;char temp;while(left<right){while(left<right&&s[left]!='a'&&s[left]!='e'&&s[left]!='i'&&s[left]!='o'&&s[left]!='u'&&s[left]!='A'&&s[left]!='E'&&s[left]!='I'&&s[left]!='O'&&s[left]!='U'){left++;}while(left<right&&s[right]!='a'&&s[right]!='e'&&s[right]!='i'&&s[right]!='o'&&s[right]!='u'&&s[right]!='A'&&s[right]!='E'&&s[right]!='I'&&s[right]!='O'&&s[right]!='U'){right--;}if(left<right){swap(s[left],s[right]);left++;right--;}}return s;}
};

时间复杂度：O(n)

空间复杂度：O(1)或O(n)

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

解题思路为：

双指针法，设置2个指针分别指向数组的首部第0个元素和尾部最后一个元素，设置能够盛水的最大值为min(height[left],height[right])*(right-left),在遍历完数组后输出最大的值，当left<right时比较height[left]与height[right]值的大小，若height[left]<height[right] left++，若height[left]>=height[right] right--。

class Solution {
public:int maxArea(vector<int>& height) {int ans=0;int left=0;int right=height.size()-1;int sum=0;while(left<right){sum=min(height[left],height[right])*(right-left);ans=max(ans,sum);if(height[left]>=height[right]){right--;}else if(height[left]<height[right]){left++;}}
return ans;}
};

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

2022/7/6

141. 环形链表

题目：
给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

解题思路为：

使用双指针法.

本方法需要读者对「Floyd 判圈算法」（又称龟兔赛跑算法）有所了解。
假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。

等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。

我们可以根据上述思路来解决本题。具体地，我们定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

当块指针等于null或fast->next等于null时，跳出循环。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
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;}
};