2024年7月31日，今日复习了数组的基础知识；巩固了二分法的写法，保证可以快速准确写出；学习了双指针的应用，双指针是为了让多个for循环压缩为一个循环，学习的时候尤其注意循环的写法。
1. 数组基础知识
定义：数组是存放在连续内存空间上的相同类型数据的集合。
几个特点：
- 数组下标都是从0开始的。
- 数组内存空间的地址是连续的。
- 数组的元素是不能删的，只能覆盖。
C++中数组是连续存放的，java中就不是。所以未必。
2. 704 二分查找
最基本的mid，left和right，需要注意初始值right=nums.size()-1。
while中是<=,因为=是有意义的。
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int middle = left + ((right - left) / 2);
if (nums[middle] > target) {
right = middle - 1; // target 在左区间，所以[left, middle - 1]
} else if (nums[middle] < target) {
left = middle + 1; // target 在右区间，所以[middle + 1, right]
} else { // nums[middle] == target
return middle; // 数组中找到目标值，直接返回下标
}
}
return -1;
}
3. 27 移除元素 （双指针）
初始思路：顺着往后看数组，只要是需要移除的val，就将val置为-1。结束以后，再来一个for循环，将数组往前移（这个过程是两个for嵌套）。
改进思路：不要再来一次for循环了，第一次遍历就将数组前移。需要两个指针。
双指针法,通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
- 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
- 慢指针：指向更新 新数组下标的位置
需要注意这个遍历的写法，因为明确的知道每个快指针会遍历数组一次，所以for循环里写fast和数组的长度n即可。不要舍近求远用while倒腾了。
int removeElement(vector<int>& nums, int val) {
int n = nums.size();
int left = 0;
for (int right = 0; right < n; right++) {
if (nums[right] != val) {
nums[left] = nums[right];
left++;
}
}
return left;
}
4. 977 有序数组的平方（双指针）
直接暴力解法：先平方再排序可以过。
双指针解法：
因为本来的数组是有序的，所以平方之后的最大值在两端出现。因此使用两个指针i和j分别指向两端，谁的平方大把谁放到结果r中。
注意循环的写法：i和j的初始值设置好，然后只需要保证i<=j,具体i和j的变化情况需要在循环中的if里分情况写。
for(int i = 0,j = A.size()-1; i<=j;)i和j的平方相等可以单拿出来讨论，也可以不管，因为此次不放到r里，下个循环必会处理。
vector<int> sortedSquares(vector<int>& A) {
int k = A.size() - 1;
vector<int> result(A.size(), 0);
for (int i = 0, j = A.size() - 1; i <= j;) {
if (A[i] * A[i] < A[j] * A[j]) {
result[k--] = A[j] * A[j];
j--;
}
else {
result[k--] = A[i] * A[i];
i++;
}
}
return result;
}
今日古诗
酹江月·夜凉
宋 黄升
西风解事，为人间、洗尽三庚烦暑。一枕新凉宜客梦，飞入藕花深处。冰雪襟怀，琉璃世界，夜气清如许。刬然长啸，起来秋满庭户。
应笑楚客才高，兰成愁悴，遗恨传千古。作赋吟诗空自好，不直一杯秋露。淡月阑干，微云河汉，耿耿天催曙。此情谁会，梧桐叶上疏雨。