*************
C++
topics include：
数组类算法 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台
283. 移动零 - 力扣（LeetCode）
27. 移除元素 - 力扣（LeetCode）
26. 删除有序数组中的重复项 - 力扣（LeetCode）
80. 删除有序数组中的重复项 II - 力扣（LeetCode）
75. 颜色分类 - 力扣（LeetCode）
215. 数组中的第K个最大元素 - 力扣（LeetCode）
88. 合并两个有序数组 - 力扣（LeetCode）
167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）
125. 验证回文串 - 力扣（LeetCode）
*************
As doing the array, something interesting happens:
The origininal topic is to move all 0 to the end of the array:
移动0 - 简单-CSDN博客
https://blog.csdn.net/ElseWhereR/article/details/144652952?spm=1001.2014.3001.5502And, move 0 out of the array:
移除0 - 简单-CSDN博客https://blog.csdn.net/ElseWhereR/article/details/144654458?spm=1001.2014.3001.5502
*************
And next comes a little hard, need to move and delete at the same time:
This topic likes delete the repeat. As the topic is double pointer, so use two pointer here. The first pointer moves faster so just name it fast. The second pointer moves slower and name it slow. The most significant code is
if (nums[fast + 1] != nums[fast])
{
nums[slow] = nums[fast];
}and the code comes easy:
class Solution {
public:int removeDuplicates(vector<int>& nums) {int slow = 1; // 慢指针从索引1开始for (int fast = 1; fast < n; fast++) { // 快指针从索引1开始if (nums[fast] != nums[fast - 1]) {nums[slow] = nums[fast]; // 复制不同的元素slow++; // 慢指针向前移动}}return slow; // 返回新的数组长度}
};*************
Guess what, delete repeat ones if it repeat 3 or more times：
80. 删除有序数组中的重复项 II - 力扣（LeetCode）https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/description/
It does have some challenge. The nums is orsered and it makes a little bit easy. Compare the nums[fast + 2] with nums[fast]. It ensures only 2 elements remains the same. If you want keep 3 same elements, just compare nums[fast + 3] with nums[fast].
class Solution {
public:int removeDuplicates(vector<int>& nums) {int n = nums.size();int slow = 0; // 慢指针，指向下一个可能的非重复元素的位置for (int fast = 2; fast < n; fast++) { // 快指针，遍历数组if (nums[fast] != nums[slow + 2]) { // 如果当前元素不等于慢指针前两个位置的元素nums[slow] = nums[fast]; // 将当前元素复制到慢指针的位置，并移动慢指针slow++;}}return slow; // 返回新数组的长度}
};The code dosenot run:
Line 1122: Char 34: runtime error: addition of unsigned offset to 0x503000000070 overflowed to 0x50300000006c (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14/bits/stl_vector.h:1131:34This is because data goes beyond borders. For example:
nums = [1 2 3]n = 2if fast = 2nums[2] != nums[4]however nums[4] 实际是不存在的Take borders into consideration:
class Solution {
public:int removeDuplicates(vector<int>& nums) {if (nums.size() <= 2) {return nums.size(); // 如果数组长度小于等于2，不需要删除任何元素}int slow = 2; // 慢指针，指向下一个可能的非重复元素的位置for (int fast = 2; fast < nums.size(); fast++) { // 快指针，遍历数组if (nums[fast] != nums[slow - 2]) { // 如果当前元素不等于慢指针前两个位置的元素nums[slow] = nums[fast]; // 将当前元素复制到慢指针的位置，并移动慢指针slow++;}}return slow; // 返回新数组的长度}
};*************
Nums are ordered in the topics before. And what if the order is unordered?
| 75. 颜色分类 - 力扣（LeetCode）https://leetcode.cn/problems/sort-colors/description/ |
 |
Need to order them without using sort. Let's see if I use sort:
One line code runs.
 |
And use double pointer seems a little bit noncommittal. Only 3 elements: 0 1 2, just ordering 0 and 1 is fine. The rest of the elements will place themselves at the right place. Use double pointer. If nums[left] == 0, moves left. If nums[right] == 2, moves right.
class Solution {
public:void sortColors(vector<int>& nums) {int n = nums.size();int left = 0;int right = n - 1;int current = 0;for (current = 0; current < n; current++){if (nums[current] == 0){nums[left] = nums[current];left++;} else if (nums[current] == 2){nums[right] = nums[current];right--;} }}
};A brilliant idea whit running wrong:
|
|
Simulate the progress:
- Initial array: [2, 0, 2, 1, 1, 0]
- left = 0, right = 5, current = 0
- Iteration 1:
- current = 0, nums[0] = 2
- Assign nums[5] = 2 (nums[5] was 0, now it's 2)
- right = 4
- Array: [2, 0, 2, 1, 1, 2]
- Iteration 2:
- current = 1, nums[1] = 0
- Assign nums[0] = 0
- left = 1
- Array: [0, 0, 2, 1, 1, 2]
- Iteration 3:
- current = 2, nums[2] = 2
- Assign nums[4] = 2 (nums[4] was 1, now it's 2)
- right = 3
- Array: [0, 0, 2, 1, 2, 2]
- Iteration 4:
- current = 3, nums[3] = 1
- Do nothing
- current = 4
- Iteration 5:
- current = 4, nums[4] = 2
- Assign nums[3] = 2
- right = 2
- Array: [0, 0, 2, 2, 2, 2]
- Iteration 6:
- current = 5, nums[5] = 2
- Assign nums[2] = 2
- right = 1
- Array: [0, 0, 2, 2, 2, 2]
- End of loop.
The problem is that just swap.
class Solution {
public:void sortColors(vector<int>& nums) {int n = nums.size();int left = 0;int right = n - 1;int current = 0;while (current <= right) {if (nums[current] == 0) {swap(nums[left], nums[current]);left++;current++;} else if (nums[current] == 2) {swap(nums[right], nums[current]);right--;} else { // nums[current] == 1current++;}}}
};*************
| 215. 数组中的第K个最大元素 - 力扣（LeetCode）https://leetcode.cn/problems/kth-largest-element-in-an-array/description/ |
|
|
First eye on the topic, the demand confuse me. Note that it is the kth largest element in the sorted order, not the kth distinct element. The requirement is to return nums[n - k + 1].
First at the begining, bouble sort comes first. However sorting is forbidden.
|
|
Still cannot solve it. leave it alone.
*************
| 88. 合并两个有序数组 - 力扣（LeetCode）https://leetcode.cn/problems/merge-sorted-array/ |
 |
Merge two ordered arries. Copy nums1 and nums2 to make a new array 3 and sort array 3:
class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {// 创建临时数组vector<int> temp(m + n);// 复制 nums1 的前 m 个元素到 tempfor (int i = 0; i < m; i++) {temp[i] = nums1[i];}// 复制 nums2 的前 n 个元素到 tempfor (int i = 0; i < n; i++) {temp[m + i] = nums2[i];}// 对 temp 进行排序sort(temp.begin(), temp.end());// 将排序后的 temp 复制回 nums1for (int i = 0; i < m + n; i++) {nums1[i] = temp[i];}}
};*************
| 167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/description/ |
|
|
Think about it. I have two pointers i and j. make pointer moves from left. Make pointer j moves from right. each moving estimating numbers[i[] + numsbers[j] != target.
class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {int n = numbers.size();for (int i = 0; i < n; i++){for (int j = n - 1; j > 0; j--){if (numbers[i] + numbers[j] == target){return {i + 1, j + 1};}}}return { };}
};It runs overtime. I cannot understand.
copy the answer:
class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {int left = 0;int right = numbers.size() - 1;while (left < right) {int sum = numbers[left] + numbers[right];if (sum == target) {return {left + 1, right + 1};} else if (sum < target) {left++;} else {right--;}}// 题目保证有解，所以理论上不会执行到这一步return {};}
};*************
| 125. 验证回文串 - 力扣（LeetCode）https://leetcode.cn/problems/valid-palindrome/description/ |
|
|
This topic is the last topic of this paper because I have do a lot about Longest Palindromic Substring.
In this topic, count the Longest Palindromic Substring of string:
最长回文子序列-CSDN博客https://blog.csdn.net/ElseWhereR/article/details/143785381?spm=1001.2014.3001.5502
class Solution {
public:bool isPalindrome(string s) {int n = s.size(); // get the length of the stringvector<vector<int>> dp(n, vector<int>(n, 0)); // initialise the array into elements zerofor (int i = 0; i < n; i++){dp[i][i] = 1; // ez to understand that one letter is always true}// caculate the length more than 2for (int len = 2; len <= n; ++len) { // out-cicle is the length of the new stringfor (int i = 0; i <= n - len; ++i) { // in-cicle start from the different placeint j = i + len - 1; // define the end of the stringif (s[i] == s[j]) { // in new srtring, stare == end, which has the possibility, so need checkdp[i][j] = (i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0) + 2;} else {dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);}}}// dp[0][n-1] returnreturn dp[0][n - 1];if (dp[0][n - 1] = n){return true;}else{return false;}}
};
