LeetCode每周刷题总结2.20-2.26

本栏目记录本人每周写的力扣题的相关学习总结。
虽然开新的栏目都没有完成
70.爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

解题思路：
斐波那契数列+递归

class Solution {
public:int climbStairs(int n) {int a=0,b=0,c=1;if(n<=2)return n;for(int i =1;i<=n;i++){a=b,b=c,c=a+b;}return c;}
};

1.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

解题思路：
暴力枚举

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int i,j;for(i=0;i<nums.size()-1;i++){for(j=i+1;j<nums.size();j++){if(nums[i]+nums[j]==target){return {i,j};}}}return {i,j};};
};

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

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

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

解题思路：最后必须返回的是nums1数组，wa了2发，把nums2数组加到nums1数组后面，然后进行排序即可。

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

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

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

解题思路：采用双指针，左指针指向已处理好的数组尾部，有指针指向未处理的部分，右指针向右 遇到非零数左右指针交换，同时左指针右移。

• 左指针左边均为非零数；

• 右指针左边直到左指针处均为零。

class Solution {
public:void moveZeroes(vector<int>& nums) {int n = nums.size(), left = 0, right = 0;while (right < n) {if (nums[right]) {swap(nums[left], nums[right]);left++;}right++;}}
};

448. 找到所有数组中消失的数字
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

解题思路：哈希表记录数组内的数字， 记录后再用哈希表检查[1,n]中的每一个数是否出现，从而找到缺失的数字。

class Solution {
public:vector<int> findDisappearedNumbers(vector<int>& nums) {vector<int> v;int n=nums.size();for(auto &i:nums){int x=(i-1)%n;nums[x]+=n;}for(int i = 0;i<n;i++){if(nums[i]<=n){v.push_back(i+1);}}return v;}
};

21. 合并两个有序链表

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

解题思路：分治排序

/*** 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) {if(list1==NULL){return list2;}if(list2==NULL){return list1;}if(list1->val<=list2->val){list1->next= mergeTwoLists(list1->next,list2);return list1;}list2->next=mergeTwoLists(list1,list2->next);return list2;}
};

83. 删除排序链表中的重复元素

给定一个已排序的链表的头 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* deleteDuplicates(ListNode* head) {if(head==NULL) return head;ListNode* node = head;while(node->next!=NULL){if(node->next->val==node->val){node->next=node->next->next;}elsenode = node->next;}return head;}
};

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

解题思路：分治排序

/*** 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) {if(list1==NULL){return list2;}if(list2==NULL){return list1;}if(list1->val<=list2->val){list1->next= mergeTwoLists(list1->next,list2);return list1;}list2->next=mergeTwoLists(list1,list2->next);return list2;}
};

141. 环形链表
142.环形链表2
给你一个链表的头节点 head ，判断链表中是否有环。

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

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

解题思路：
利用哈希集合判断链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。借助哈希表可以很方便地实现。

/*** 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) {unordered_set<ListNode *> s;while(head!=NULL){if(s.count(head))return true;s.insert(head);head=head->next;}return false;}
};

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。
解题思路：
判断两个链表是否相交，可以使用哈希集合存储链表节点。

首先遍历链表 headA，并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中：

如果当前节点不在哈希集合中，则继续遍历下一个节点；

如果当前节点在哈希集合中，则后面的节点都在哈希集合中，即从当前节点开始的所有节点都在两个链表的相交部分，因此在链表 headB 中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点，返回该节点。

如果链表 headB 中的所有节点都不在哈希集合中，则两个链表不相交，返回 null

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_set<ListNode *> s;ListNode* node =headA;while(node!=nullptr){s.insert(node);node=node->next;}node = headB;while(node!=nullptr){if(s.count(node)){return node;}s.insert(node);node=node->next;}return nullptr;}
};

206.反转链表
给你单链表的头节点 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* reverseList(ListNode* head) {ListNode* L;L= head;stack<int> s;while(L!=nullptr){s.push(L->val);L=L->next;} L=head;while(L!=nullptr){L->val=s.top();s.pop();L=L->next;} return head;}
};

234. 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

解题思路：
传进数组内遍历比较。

/*** 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:bool isPalindrome(ListNode* head) {ListNode* L;L=head;vector<int> s;while(L!=nullptr){s.push_back(L->val);L=L->next;}int j = s.size()-1;for(int i= 0;i<s.size()/2;i++,j--){if(s[i]!=s[j])return false;}return true;}
};

876. 链表的中间结点
给你单链表的头结点 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* middleNode(ListNode* head) {vector<ListNode*> A = {head};while (A.back()->next != NULL)A.push_back(A.back()->next);return A[A.size() / 2];}
};

感谢观看