27. 移除元素
题意描述：
给你一个数组
nums和一个值val，你需要 原地 移除所有数值等于val的元素。元素的顺序可能发生改变。然后返回nums中与val不同的元素的数量。假设
nums中不等于val的元素数量为k，要通过此题，您需要执行以下操作：
- 更改
nums数组，使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。- 返回
k。
思路：
定义快慢指针fast、slow，fast记录新数组元素，slow记录新数组下标。
AC代码：
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow = 0;
for(int fast = 0 ; fast < nums.size() ; fast ++){
if(nums[fast] != val) nums[slow++] = nums[fast];
}
return slow;
}
};
344.反转字符串
题意描述：
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组
s的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = ["h","e","l","l","o"] 输出：["o","l","l","e","h"]示例 2：
输入：s = ["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]提示：
1 <= s.length <= 105s[i]都是 ASCII 码表中的可打印字符
思路：
定义双指针i 从左边开始遍历、j从右边开始遍历，每次交换字符元素。
AC代码：
class Solution{
public:
void reverseString(vector<char>& s){
for(int i = 0 , j = s.size() - 1 ; i < s.size() / 2 ; i ++ , j --) swap(s[i] , s[j]);
}
};//函数是void，故不用return
替换数字
题意描述：
给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。
例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。
对于输入字符串 "a5b"，函数应该将其转换为 "anumberb"
输入：一个字符串 s,s 仅包含小写字母和数字字符。
输出：打印一个新的字符串，其中每个数字字符都被替换为了number
样例输入：a1b2c3
样例输出：anumberbnumbercnumber
数据范围：1 <= s.length < 10000。
思路：
先统计原字符串
s中数字的个数cnt， 将s扩容到目标大小，即s.size() + 5 * cnt，然后定义新旧指针（我这里用的快慢）分别指向新旧字符串数组的最后一个元素，如果遇到数字，新数组倒序输入number,其他情况复制旧数组元素到新数组。
AC代码：
#include<iostream>
using namespace std;
int main(){
string s;
cin >> s;
int n = s.size(), cnt = 0;
for(int fast = 0 ; fast < n ; fast++){
if(s[fast] >= '0' && s[fast] <= '9') cnt++;
}
s.resize( n + 5 * cnt);
for(int fast = s.size() - 1 , slow = n - 1; slow >= 0 ;slow -- ){
if(s[slow] >= '0' && s[slow] <= '9'){
s[fast --] = 'r';
s[fast --] = 'e';
s[fast --] = 'b';
s[fast --] = 'm';
s[fast --] = 'u';
s[fast --] = 'n';
}
else {
s[fast --] = s[slow];
}
}
cout << s;
}
其实很多数组填充类的问题，其做法都是先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
这么做有两个好处：
- 不用申请新数组。
- 从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。
M:151.翻转字符串里的单词
题意描述：
给你一个字符串
s，请你反转字符串中 单词 的顺序。单词 是由非空格字符组成的字符串。
s中使用至少一个空格将字符串中的 单词 分隔开。返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串
s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。示例 1：
输入：s = "the sky is blue" 输出："blue is sky the"示例 2：
输入：s = " hello world " 输出："world hello" 解释：反转后的字符串中不能存在前导空格和尾随空格。示例 3：
输入：s = "a good example" 输出："example good a" 解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。提示：
1 <= s.length <= 104s包含英文大小写字母、数字和空格' 's中 至少存在一个 单词进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用
O(1)额外空间复杂度的 原地 解法。
思路：
- 去除多余空格，思路与移除元素相同，val = ‘ ’；
- 用reverse函数将整个字符串翻转
- 翻转单词
AC代码：
removeExtraSpaces函数，从去除前面，中间，后面空格的顺序来写。
//版本一
void removeExtraSpaces(string& s){
int slow = 0, fast = 0;
// 去掉字符串前面的空格
while(s.size() > 0 && fast < s.size() && s[fast] == ' ') fast ++;
// 去掉字符串中间部分的冗余空格
for( ; fast < s.size() ; fast++){
if(fast - 1 > 0 && s[fast - 1] == s[fast] && s[fast] == ' ') continue;
else s[slow ++] = s[fast];
}
//后面此时最多有一个空格,重新设置字符串大小
if(slow - 1 > 0 && s[slow - 1] == ' ') s.resize(slow - 1)
else s.resize(slow);
}
// 版本二
void removeExtraSpaces(string& s){
int slow = 0;
for(int fast = 0 ; fast < s.size() ; fast ++){
//遇到非空格就处理,否则跳出到下一吃循环,这里删除了所有空格。
if(s[fast] != ' '){
//给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。
if(slow != 0) s[slow ++] = ' ';
//补上该单词，遇到空格说明单词结束。
while(fast < s.size() && s[fast] != ' ') s[slow ++] = s[fast ++];
}
}
//slow的大小即为去除多余空格后的大小。
s.resize(slow);
}
整体代码：
class Solution{
public:
/*翻转，区间写法：左闭右闭 []
void reverse(string& s , int start , int end){
for(int i = start , j = end ; i < j ; i ++ , j --) swap(s[i] , s[j]);
}
我这里用库函数reverse
*/
void removeExtraSpaces(string& s){
int slow = 0;
for(int fast = 0 ; fast < s.size() ; fast ++){
//遇到非空格就处理,否则跳出到下一吃循环,这里删除了所有空格。
if(s[fast] != ' '){
//给单词之间添加空格。slow != 0说明不是第一个单词，需要在单词前添加空格。
if(slow != 0) s[slow ++] = ' ';
//补上该单词，遇到空格说明单词结束。
while(fast < s.size() && s[fast] != ' ') s[slow ++] = s[fast ++];
}
}
//slow的大小即为去除多余空格后的大小。
s.resize(slow);
}
string reverseWords(string s) {
//去除多余空格，保证单词之间之只有一个空格，且字符串首尾没空格。
removeExtraSpaces(s);
reverse(s.begin() , s.end());//STL中reverse函数是左闭右开
//removeExtraSpaces后保证第一个单词的开始下标一定是0。
int start = 0;
for(int i = 0 ; i <= s.size() ; i++){
//到达空格或者串尾，说明一个单词结束。进行翻转。
if(i == s.size() || s[i] == ' ') {
//翻转，注意是左闭右闭 []的翻转。start ~ i - 1
reverse(s.begin() + start , s.begin() + i);
//更新下一个单词的开始下标start
start = i + 1;
}
}
return s;
}
};
206.反转链表
题意描述：
题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
思路：
只需改变next指针朝向，原地翻转即可，定义pre ， cur ， tmp 指针分别指向 前， 现在， 下 节点。
AC代码：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* tmp; // 保存cur的下一个节点
ListNode* cur = head;
ListNode* pre = NULL;
while(cur) {
tmp = cur->next; // 保存一下 cur的下一个节点，因为接下来要改变cur->next
cur->next = pre; // 翻转操作
// 更新pre 和 cur指针
pre = cur;
cur = tmp;
}
return pre;
}
};
另解：递归法
递归法相对抽象一些，但是其实和双指针法是一样的逻辑，同样是当
cur为空的时候循环结束，不断将cur指向pre的过程。关键是初始化的地方，可能有的同学会不理解， 可以看到双指针法中初始化
cur = head``，pre = NULL，在递归法中可以从如下代码看出初始化的逻辑也是一样的，只不过写法变了。具体可以看代码（已经详细注释），双指针法写出来之后，理解如下递归写法就不难了，代码逻辑都是一样的。
class Solution {
public:
ListNode* reverse(ListNode* pre,ListNode* cur){
if(cur == NULL) return pre;
ListNode* temp = cur->next;
cur->next = pre;
// 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
// pre = cur;
// cur = temp;
return reverse(cur,temp);
}
ListNode* reverseList(ListNode* head) {
// 和双指针法初始化是一样的逻辑
// ListNode* cur = head;
// ListNode* pre = NULL;
return reverse(NULL, head);
}
};
- 时间复杂度: O(n), 要递归处理链表的每个节点
- 空间复杂度: O(n), 递归调用了 n 层栈空间
我们可以发现，上面的递归写法和双指针法实质上都是从前往后翻转指针指向，其实还有另外一种与双指针法不同思路的递归写法：从后往前翻转指针指向。
具体代码如下（带详细注释）：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// 边缘条件判断
if(head == NULL) return NULL;
if (head->next == NULL) return head;
// 递归调用，翻转第二个节点开始往后的链表，这一步仔细体会
ListNode *last = reverseList(head->next);
// 翻转头节点与第二个节点的指向
head->next->next = head;
// 此时的 head 节点为尾节点，next 需要指向 NULL
head->next = NULL;
return last;
}
};
19.删除链表的倒数第N个节点
题意描述：
给你一个链表，删除链表的倒数第
n个结点，并且返回链表的头结点。示例 1：
输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1 输出：[]
示例 3：
输入：head = [1,2], n = 1 输出：[1]
思路：
定义双指针
fast 、 slow，先让fast走n + 1 步 ，然后fast 、 slow同时走，fast走到结尾时，slow的下一个元素恰好是待删除元素，此时令slow-> next = slow -> next -> next即可。
AC代码：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* slow = dummyHead;
ListNode* fast = dummyHead;
//while(n --)执行顺序说明：先判断n>0? 如果是则 -1
while(n-- && fast != NULL) {
fast = fast->next;
}
fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点,结合上面的图可以理解，这一步很重要
while (fast != NULL) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
// ListNode *tmp = slow->next; C++释放内存的逻辑
// slow->next = tmp->next;
// delete tmp;
return dummyHead->next;
}
};
面试题 02.07. 链表相交
题意描述：
给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回null。图示两个链表在节点
c1开始相交：[
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at '8' 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。示例 2：
[
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Intersected at '2' 解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。示例 3：
[
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 这两个链表不相交，因此返回 null 。提示：
listA中节点数目为mlistB中节点数目为n0 <= m, n <= 3 * 1041 <= Node.val <= 1050 <= skipA <= m0 <= skipB <= n- 如果
listA和listB没有交点，intersectVal为0- 如果
listA和listB有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]进阶：你能否设计一个时间复杂度
O(n)、仅用O(1)内存的解决方案？
思路：
定义双指针
curA 、curB, 目前curA指向链表A的头结点，curB指向链表B的头结点,计算AB链表长度差gap假如lenA > lenB（如果不是就swap（lenA，lenB）, swap(curA , curB)。让curA先走gap步，然后curA、curB同时走到末尾，过程中比较指针是否相等即可。
AC代码：
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 0, lenB = 0;
while (curA != NULL) { // 求链表A的长度
lenA++;
curA = curA->next;
}
while (curB != NULL) { // 求链表B的长度
lenB++;
curB = curB->next;
}
curA = headA;
curB = headB;
// 让curA为最长链表的头，lenA为其长度
if (lenB > lenA) {
swap (lenA, lenB);
swap (curA, curB);
}
// 求长度差
int gap = lenA - lenB;
// 让curA和curB在同一起点上（末尾位置对齐）
while (gap--) {
curA = curA->next;
}
// 遍历curA 和 curB，遇到相同则直接返回
while (curA != NULL) {
if (curA == curB) {
return curA;
}
curA = curA->next;
curB = curB->next;
}
return NULL;
}
};
M:142.环形链表II
题意描述：
给定一个链表的头节点
head，返回链表开始入环的第一个节点。 如果链表无环，则返回null。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果pos是-1，则在该链表中没有环。注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。示例 3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。提示：
- 链表中节点的数目范围在范围
[0, 104]内-105 <= Node.val <= 105pos的值为-1或者链表中的一个有效索引进阶：你是否可以使用
O(1)空间解决此题？
思路：
主要考察两知识点：
- 判断链表是否环
- 如果有环，如何找到这个环的入口
- 判断是否有环
定义快慢指针
fast、slow，fast每次走两步 ，slow每次走一步 ， 若循环中相遇则有环。
- 环的入口
假设从头结点到环形入口节点 的节点数为
x。 环形入口节点到fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为z。 如图所示：
那么相遇时：
slow指针走过的节点数为:x + y，fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A。因为fast指针是一步走两个节点，
slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：(x + y) * 2 = x + y + n (y + z)两边消掉一个（x+y）:
x + y = n (y + z)因为要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。
所以要求x ，将x单独放在左面：
x = n (y + z) - y,再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：
x = (n - 1) (y + z) + z注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。取n为1，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。
当 n为1的时候，公式就化解为
x = z，这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
也就是在相遇节点处，定义一个指针
index1，在头结点处定一个指针index2。让
index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。
AC代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
//这里的判断条件是fast和fast->next不为空
while(fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
// 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇。上面推导n = 1的情况。
if (slow == fast) {
ListNode* index1 = fast;
ListNode* index2 = head;
while (index1 != index2) {
index1 = index1->next;
index2 = index2->next;
}
return index2; // 返回环的入口
}
}
return NULL;
}
};
M:第15题. 三数之和
题意描述：
给你一个整数数组
nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为
0且不重复的三元组。注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。示例 2：
输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。示例 3：
输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105
思路：
滑动窗口思想，先排序数组，然后去重处理。一层for循环控制i遍历整个数组，然后定义双指针l、 r分别在
nums[i] + nums[l] + nums[j] < 0和>0时右滑/左滑。如果三数之和=0，则保存进res，然后去重处理处理，将r左移、l右移。代码注意的几点：
- 结果返回的是[] 、[]的三元组形式，故定义
res为二重数组vector<vector<int>>,然后在res.push_back的时候，参数是{vector<int>{nums[i] , nums[l] , nums[r]}}else的逻辑，在三数之和 = 0时需将左右窗口分别移动，else push_back那里括号较多，应分行写。res的return在for循环之后，写完要检查
AC代码：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin() , nums.end());
for(int i = 0 ; i < nums.size() ; i++){
if(nums[i] > 0) return res;
if(i > 0 && nums[i] == nums[i - 1]) continue;
int l = i + 1 , r = nums.size() - 1;
while(r > l){
if(nums[i] + nums[l] + nums[r] > 0) r--;
else if(nums[i] + nums[l] + nums[r] <0) l++;
else {
res.push_back(vector<int>{nums[i] , nums[l] , nums[r]});
while(r > l && nums[r] == nums[r - 1]) r--;
while(r > l && nums[l] == nums[l + 1]) l ++;
r --;
l ++;
}
}
}
return res;
}
};
第18题. 四数之和
题意描述：
给你一个由
n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2：
输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]提示：
1 <= nums.length <= 200-109 <= nums[i] <= 109-109 <= target <= 109
思路：
四数之和，和三数之和 是一个思路，都是使用双指针法, 基本解法就是再套一层for循环。
但是有一些细节需要注意，例如： 不要判断
nums[k] > target就返回了，三数之和 可以通过nums[i] > 0就返回了，因为 0 已经是确定的数了，四数之和这道题目target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。类似的二级剪枝：
nums[i] + nums[j] > target && (nums[i] + nums[j] >= 0)去重操作还是一样的。
三数之和 的双指针解法是一层for循环
num[i]为确定值，然后循环内有left和right下标作为双指针，找到nums[i] + nums[left] + nums[right] == 0。四数之和的双指针解法是两层for循环
nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n2)，四数之和的时间复杂度是O(n3) 。那么一样的道理，五数之和、六数之和等等都采用这种解法。
AC代码：
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
sort(nums.begin() , nums.end());
for(int i = 0 ; i < nums.size() ; i++){
// 剪枝处理
if(nums[i] > target && nums[i] >= 0) break;// 这里使用break，统一通过最后的return返回
// 对nums[i]去重
if(i > 0 && nums[i] == nums[i - 1]) continue;
for(int j = i + 1 ; j < nums.size() ; j++){
// 二级剪枝处理
if(nums[i] + nums[j] > target && nums[i] + nums[j] >= 0) break;
// 对nums[i]去重
if(j > i + 1 && nums[j] == nums[j - 1]) continue;
int l = j + 1 , r = nums.size() - 1;
while(r > l){
// nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
if((long)nums[i] + nums[j] + nums[l] + nums[r] > target) r--;
else if((long)nums[i] + nums[j] + nums[l] + nums[r] < target) l++;
else {
res.push_back(vector<int>{nums[i] , nums[j] , nums[l] , nums[r]});
// 对nums[left]和nums[right]去重
while(r > l && nums[r] == nums[r - 1]) r--;
while(r > l && nums[l] == nums[l + 1]) l ++;
// 找到答案时，双指针同时收缩
r --;
l ++;
}
}
}
}
return res;
}
};