LeetCode 特训 ---- Week1

目录

LeetCode 特训 --- Week1

两数之和

最长回文子串

删除有序数组中的重复项

删除有序数组中的重复项Ⅱ

删除链表中的重复元素

移动0

旋转链表

分隔链表

快慢指针（前后指针）用的好，链表，数组起码轻松打十个。

LeetCode 特训 --- Week1

两数之和

力扣

解题思路

方式1：很明显我们可以利用记录前面走过的值，记忆化，的方式来查找前面是否有我们想要的值。每两个值的和都可能是target，当前遍历的值val, 如果前面走过的值中存在target - val，答案可得。

处置方式，前面使用一种快速查找的数据结构来维护我们已经遍历过的路径path. 每遍历新的值val，都从path中查询 (target - val).

hash，或者红黑树。。。来解决这一系列的问题，包括两数和以及三数和...

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> inds;for (int i = 0; i < nums.size(); i ++) {int distance = target - nums[i];//不是ans, 加入hash表中if (inds.empty() || inds.find(distance) == inds.end()) {inds[nums[i]] = i;continue;} return {inds[distance], i};}return {-1, -1};}
};

方式2：很明显借助排序之后结果用左右指针遍历搜索也可以达到目的，反正只要存在答案，我们遍历所有可能成为答案的情况就一定可以找到结果。

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {std::vector<int> copy_nums(nums.begin(), nums.end());std::sort(nums.begin(), nums.end()); //sortint l = 0, r = nums.size() - 1; //左右指针记录answhile (l < r) {if (nums[l] + nums[r] == target) {break;} else {if (nums[l] + nums[r] < target) {l ++;} else {r --;}}}if (l >= r) {return {-1, -1};}std::vector<int> ans;for (int i = 0; i < nums.size(); i ++) {if (copy_nums[i] == nums[l] || copy_nums[i] == nums[r]) {ans.push_back(i);}}return ans;}
};

最长回文子串

力扣

解题思路：

1. 因为是子序列问题，不清楚边界，方式1，在每一个位置都可能是结果，从中间向两边自由扩散获取结果。(老哥给的经验，边界不明确的问题，可以直接的进行一个一点点的扩大，一点点的从中间向两边扩散找边界)

//边界问题是写双指针最应该注意的.
class Solution {//寻找以lbegin, rbegin左右扩散的最长回文子串std::string subPalindrome(std::string& s, int lbegin, int rbegin) {int l = lbegin, r = rbegin, n = s.size();while (l >= 0 && r < n && s[l] == s[r]) {l --, r ++;}//l位置不可取 【l+1, r-1】区间元素个数(r-1-l-1+1) = (r-l-1)个return s.substr(l + 1, r - l - 1);}
public:string longestPalindrome(string s) {std::string ans = "";for (int i = 0; i < s.size(); i++) {std::string s1 = subPalindrome(s, i, i);//奇数串 std::string s2 = subPalindrome(s, i, i + 1);//偶数串ans = ans.size() >= s1.size() ? ans : s1; ans = ans.size() >= s2.size() ? ans : s2; //std::cout << ans << std::endl;}return ans;}
};

2. 可以使用动态规划，记忆化搜索的方式，用空间来提高效率。

删除有序数组中的重复项

力扣力扣 

class Solution {
public:int removeDuplicates(vector<int>& nums) {int last = 0, front = 0;while (front < nums.size()) {if (nums[last] != nums[front]) {   //非重复, 符合题意的值，放入slow结果序列nums[++last] = nums[front]; }front ++;                          //前指针继续向前探路，寻求非重复值}return last + 1;}
};

删除有序数组中的重复项Ⅱ

力扣

核心思路还是前后（快慢）指针，只不过中间需要维护一个计数器

class Solution {
public:int removeDuplicates(vector<int>& nums) {int last = 0, front = 0, n = nums.size();int count = 0;int preval = nums[0];       //记录前面的遍历值while (front < n) {if (nums[front] != preval) {//一个子序列值遍历完毕count = 0;preval = nums[front];}if (count < 2) {nums[last++] = nums[front];}front ++;           //向后寻求符合要求的值，count ++;           //计数}return last;}
};

删除链表中的重复元素

力扣

解题思路还是哪个思路，向后寻找非重复元素链接到前面去就OK了。 前面的p指针相当于是做数组题目时候的last指针，维护着结果序列

class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if (head == nullptr) return nullptr;ListNode* last = head, *front = head;while (front) {if (last->val != front->val) {  //非重复值，留下来.last->next = front;last = last->next;}front = front->next;  //向前探路}last->next = nullptr;return head;}
};
​

移动0

力扣

class Solution {
public:void moveZeroes(vector<int>& nums) {int last = 0, front = 0, n = nums.size();while (front < n) {if (nums[front] != 0) {     //寻求到非零数字, 放到last结果序列中nums[last++] = nums[front];} front ++;                   //向后寻求非零数字}//将后续制0while (last < n) {nums[last++] = 0;}}
};

快慢指针，前后指针的核心思想在那里？

慢指针停留在后面，保留的是最终结果，快指针跑在前面探路，寻找的是可以留下来当作结果的值。（符合题意，需要留下的值）

旋转链表

力扣

思路：很明显，右边移动几个位置，相当于是头结点换成了右边的第k%num个结点。所以很自然的可以想到先成环，再断开。链表的操作注意头部结点和边界问题。

class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {if (head == nullptr) { return nullptr; }int cnt = 1;ListNode* p = head;while (p->next) {//计算元素个数并且p走到尽头cnt ++;p = p->next;}p->next = head;//成环k %= cnt;// 走到cnt-k节点处断开int n = cnt - k; p = head;while (--n) {p = p->next;}ListNode* ans = p->next;p->next = nullptr;return ans;}
};

分隔链表

力扣 

思路：很明显的按照题意走即可。遍历原链表拆成两个部分的子链表，然后两个子链表连起来就OK了。还是需要注意边界，结束位置要有nullptr，链表的题目往往难度不在思维，在乎对于指针的控制，以及边界的顾及。

class Solution {
public:ListNode* partition(ListNode* head, int x) {if (head == nullptr) { return nullptr; }ListNode h1, h2, *t1, *t2;//记录两条链表的头尾t1 = &h1, t2 = &h2;ListNode *p = head; while (p) {if (p->val < x) {t1->next = p;t1 = t1->next;} else {t2->next = p;t2 = t2->next;}p = p->next;}t1->next = h2.next;//中间衔接t2->next = nullptr;//末尾制空，否则死循环了 细节。。。return h1.next;}
};

快慢指针（前后指针）用的好，链表，数组起码轻松打十个。

快慢指针真好用，快指针（前指针）跑在前面探路，做个侦察小兵，寻找符合题目要求的结点或者值，慢指针维护结果序列，存储快指针找到的一系列符合题目要求的值。