本文主要是介绍【代码随想录37期】 第一周总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
周末再写一遍
【代码随想录37期】Day01 二分查找 + 移除元素
【代码随想录37期】Day02 有序数组的平方、长度最小的子数组、螺旋矩阵Ⅱ
【代码随想录37期】Day03 移除链表元素、设计链表、反转链表
【代码随想录37期】Day04 两两交换链表中的节点、删除链表的倒数第N个节点、链表相交、环形链表II
补充
长度最小的子数组
v2.0：使用滑动窗口
滑动窗口的思想其实很简单，传统暴力使用两个for循环分别控制窗口的边界
滑动窗口重点在于滑~ 所以其中一个边界是靠条件来操控的
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int sum = 0, len = 0,left = 0;vector<int> result;result.push_back(0);for(int right = 0; right<nums.size();right++){sum+=nums[right];len++;while(sum>=target&&left<nums.size()){result.push_back(len);sum-=nums[left++];len--;}}sort(result.begin(), result.end());return result.size()>1?result[1]:result[0];}
};v3.0：
前面使用vector有点大材小用，这里将result声明为INT32_MAX可以直接迭代
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int sum = 0, len = 0,left = 0,result = INT32_MAX;for(int right = 0; right<nums.size();right++){sum+=nums[right];len++;while(sum>=target&&left<nums.size()){result = len<result?len:result;sum-=nums[left++];len--;}}return result==INT32_MAX?0:result;}
};
v4.0:
int minSubArrayLen(int target, vector<int>& nums) {int left = 0, right = 0, len = 0, sum = 0, min = INT32_MAX;for (; right < nums.size(); right++){sum += nums[right];len++;while (sum >= target){if (len < min)min = len;sum -= nums[left];len--;left++;}}return min==INT32_MAX? 0 : min;
}
关键点
为什么要写INTMAX_32?
题目条件：1 <= nums.length <= 10^ 5，写一个比10^5大的数就行
INT_MAX 和 INT_MIN 是 C++ 的两个宏，代表了整型变量能够存储的最大正整数和最小负整数，分别为 2147483647 和 -2147483648，这两个宏在头文件 <limits.h> 中定义。
2147483647约等于10的9次方
9223372036854775807(long long)约等于10的18次方
记忆方法：2的10次幂(1024)约等于10的3次幂，那2的32次约等于10的9次幂，2的64次约等于10的18次
为什么最后一种写法while不用加left < nums.size()？
已知进入for循环时right<nums.size()，要满足sum >= target，left与right之间至少要有一个数，也就是nums[right]，此时left<right<nums.size();
设计链表
class MyLinkedList {
public:struct LinkNode{int val;LinkNode* next;LinkNode() :val(0), next(nullptr) {};LinkNode(int n) :val(n), next(nullptr) {};};MyLinkedList() {dummyHead = new LinkNode();size = 0;}int get(int index) {if (index > size - 1)return -1;LinkNode* curNode = dummyHead->next;while (index--){curNode = curNode->next;}return curNode->val;}void addAtHead(int val) {LinkNode* newNode = new LinkNode(val);newNode->next = dummyHead->next;dummyHead->next = newNode;size++;}void addAtTail(int val) {LinkNode* newNode = new LinkNode(val);LinkNode* curNode = new LinkNode();curNode = dummyHead;while (curNode->next){curNode = curNode->next;}curNode->next = newNode;size++;}void addAtIndex(int index, int val) {if (index > size)return;LinkNode* newNode = new LinkNode(val);LinkNode* curNode = new LinkNode();curNode = dummyHead;while (index--){curNode = curNode->next;}newNode->next = curNode->next;curNode->next = newNode;size++;}void deleteAtIndex(int index) {if (index > size-1)return;LinkNode* curNode = new LinkNode();curNode = dummyHead;while (index--){curNode = curNode->next;}LinkNode* toDelete = curNode->next;curNode->next = curNode->next->next;delete toDelete;size--;}private:LinkNode* dummyHead;int size;
};
##关键点
为什么有的时候curNode = dummyHead？，有时候curNode = dummyHead->next?
总之都会有一个while循环，无论是while(curNode)还是while(curNode->Next)
宗旨有2：
- 当链表为空时也可以访问curNode；
- curNode遍历完curNode指向最后一个节点而不是nullptr；
一般考虑这两个情况即可，也就是链表的边界情况
反转链表
1. 用指针定义的结构体或类的成员用->访问，cur->next等价于(*cur).next
2. 链表双指针重要的是指针朝向的更新，循环条件看看是不是快指针，但是返回的指针注意不要是指向null的
3. 指针的结构体：
struct LinkedList{int val;LinkedList* next;
};class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* tmp;ListNode* cur = head;ListNode* pre = nullptr;while(cur){tmp = cur->next;cur->next = pre;pre = cur;cur = tmp;}return pre;}
};v2.0:使用虚拟头节点来做这道题，可见虚拟头节点并不是必要的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* reverseList(ListNode* head) {ListNode *dummyHead = new ListNode(0);dummyHead->next = head;ListNode *slow = nullptr;ListNode *fast = head;ListNode *tmp;while(fast){tmp = fast->next;fast->next = slow;slow = fast;fast = tmp;}// delete dummyHead;dummyHead = nullptr;return slow;}
};v3.0:写反转链表完全不需要虚拟头节点，把nullptr"作为"头节点即可
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* left = nullptr;ListNode* right = head;while (right){ListNode* tmp = right->next;right->next = left;left = right;right = tmp;}return left;}
};
为什么反转链表不需要虚拟头节点？什么情况下需要呢？
反转链表中，我们如果有虚拟头节点，最后还要去掉，因为我们最后的head发生了变化，不能直接通过虚拟头节点访问了，所以在这里是冗余的，涉及到最终无法访问head节点、head节点发生变化导致无法从虚拟头节点访问时，就不要用虚拟头节点。
两两交换链表中的节点
/*** 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* swapPairs(ListNode* head) {ListNode *dummyHead = new ListNode(0);dummyHead->next = head;ListNode *cur = dummyHead; while(cur->next&&cur->next->next){ListNode* tmp = cur->next; // 记录临时节点ListNode* tmp1 = cur->next->next->next; // 记录临时节点cur->next = cur->next->next; // 步骤一cur->next->next = tmp; // 步骤二cur->next->next->next = tmp1; // 步骤三cur = cur->next->next; // cur移动两位，准备下一轮交换}return dummyHead->next;}
};
class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummyHead = new ListNode();dummyHead->next = head;ListNode* pre = dummyHead;while (pre->next&&pre->next->next){ListNode* left = pre->next;ListNode* right = pre->next->next;pre->next = right;left->next = right->next;right->next = left;pre = left;}return dummyHead->next;
}
};
关键点
为什么要判断pre->next&&pre->next->next？
检查pre->next->next是因为循环体中会访问pre->next->next的next，不检查会越界
检查pre->next是因为要检查pre->next->next首先要访问pre->next的next，不检查也会越界
这道题有些绕
确实，我目前是这样理解的，主要有三个指针需要交换，除了两个节点还有两个节点的前一个节点，也就是pre，left和right
这道题的left和right要写成局部变量，不然不好处理while的条件
删除链表中的倒数第N个节点
注意使用虚拟头节点，可以避免对头节点的判断，防止各种复杂情况
/*** 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* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* slow = dummyHead;ListNode* fast = dummyHead;while(n--&&fast){fast = fast->next;}fast = fast->next;while(fast){fast = fast->next;slow = slow->next;}slow->next = slow->next->next;return dummyHead->next;}
};
/*** 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* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* slow = dummyHead;ListNode* fast = dummyHead;while(n--&&fast){fast = fast->next;}fast = fast->next;while(fast){fast = fast->next;slow = slow->next;}slow->next = slow->next->next;return dummyHead->next;}
};
ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyHead = new ListNode();dummyHead->next = head;ListNode* fast = dummyHead;while (n--){fast = fast->next;}ListNode* slow = dummyHead;while (fast->next){slow = slow->next;fast = fast->next;}ListNode* todelete = slow->next;slow->next = slow->next->next;delete todelete;return dummyHead->next;
}
关键点
为什么不直接返回head？
因为head有可能被删掉
这种题该怎么写？
链表题主要需要想象节点之间的连接关系，一定要画图来做，我常用的一个例子就是：
虚拟节点(0)->head(1)->(2)->(3)->(4)->nullptr
环形链表Ⅱ
这道题值得多做几遍
v1.0 这道题很巧妙，是看了随想录的讲解才做出来的
1. 判断有无环:定义快慢指针，快指针一次走两个节点，慢指针走一个，快指针追上慢指针说明有环
2. 追上时需要纸笔列下式子，此时快慢指针走过的节点数量，然后要求的是从开始节点到进入环的节点的长度
3. 具体推导可以看随想录，总之就是需要列一下式子就可以找出关系了~
/*** 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 *dummyHead = new ListNode(0);dummyHead->next = head;ListNode *fast = head;ListNode *slow = head;ListNode *aux = head;while(fast&&fast->next){fast= fast->next->next;slow = slow->next;if(fast==slow){while(aux!=slow){slow=slow->next;aux=aux->next;}return aux;}}return nullptr;}
};
靠视觉记忆记住这张图吧
快指针走了：a + b + k(b+c)
慢指针走了：a + b
所以a +b + k(b+c) = 2（a+b）
得到a + b = k （b + c）
所以a - c = k（b+c）
补充一个哈希表做法保底：
/*** 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) {unordered_set<ListNode*> visited;ListNode* cur = head;while (cur){if (visited.count(cur)){return cur;}visited.insert(cur);cur = cur->next;}return nullptr;
}
};
这篇关于【代码随想录37期】 第一周总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
