LeetCode704
2025-01-22 18:30:38 星期三
代码随想录视频内容简记
梳理一下三个比较重要的部分
-
首先是对于整个代码的循环条件，这个很重要
-
判断middle位置在我看来初学也是比较重要一步
注意：所有的middle位置判断都是if语句实现的，固定的大于和小于。这个不用纠结一不一样
-
更新left和right位置
左闭右闭
大致代码内容
-
while(left <= right) -
if(nums[middle] > target) -
则判断middle位置，位于左区间的右边界，则更新right
如果是
if(nums[middle] < target)，则更新右区间的左边界，也就是更新left。因为nums[middle]始终是在区间正中的 -
right = middle - 1，关于此处做了着重的讲解。因为第二步中的判断，nums[middle]已经大于了target值，所以此时如果赋right = middle会错误引入一个边界之外的值，引入到哪里？就是引入到下一次while循环，这样就出问题了，所以只能是right = middle - 1
左闭右开
-
首先是需要注意这个的
right = number赋值的时候有些区别，和上面的左闭右闭不一样，后者是right = number - 1 -
其次时需要注意在循环体分别更新left和right的方式不一样
大致代码内容
-
while(left < right)这里因为右边界取不到，所以是<
-
依然是条件
if(nums[middle] > target)此时此时更新左区间的右边界，也就是
right，right = middle，因为下一次循环不包含右边界，所以可以等于middle，加上等于号。如果是
if(nums[middle] < target)，则更新右区间的左边界，也就是更新left。这个需要区分开，这个是left = middle + 1，因为下一次循环包含左边界，所以既然nums[middle]不一样，就不能把他再引入下一次循环，所以是middle + 1
LeetCode测试
写出代码均是一遍通过，好用得很，没有什么不明白的地方。
左闭右闭
点击查看代码
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while(left <= right){
int middle = (left + right)/2;
if(nums[middle] < target){
left = middle + 1 ;
}
else if(nums[middle] > target){
right = middle - 1;
}
else{
return middle;
}
}
return -1;
}
};
左闭右开
点击查看代码
class Solution {
public:
int search (vector<int>& nums, int target) {
int left = 0, right = nums.size();
while (left < right) {
int middle = (left + right) / 2;
if (nums[middle] < target) {
left = middle + 1;
}
else if (nums[middle] > target) {
right = middle;
}
else return middle;
}
return -1;
}
};
LeetCode27
代码随想录视频内容简记
首先是数组在内存中的实际大小是5，当我们删除了一个元素3之后，虽然返回的数组大小应该是4，但是其实3只是被覆盖了，其实际的数组大小仍然是5没有变
暴力解法
个人感觉暴力解法还是有一些坑在的，因为卡哥的视频里没有详细讲解，
下面先梳理一下
-
首先是两层循环嵌套用来解决数组的移动问题
-
for循环的条件判断，这个很重要
-
针对于特殊的测试用例[0,1,2,2,...]的i--
大致代码内容
-
因为每当找到一次
val值之后，从他开始整体向前移动，所以循环的条件判断不能再仅仅写i < nums.size()，而需要在一开始进行赋值一个size = nums.size()，然后对size在每一次找到之后进行size--操作 -
因为上面说的这个[0,1,2,2]这个特殊用例，我们可以设想，如果是两层for循环，外层循环在找到2之后进入循环内部，此时的第二个2会往前移动一位。此时的数组比如是[0,1,2,3]。但是内层循环结束之后，外层循环又会进行
i++操作，导致i指针会跳过第二个2，直接判断下一位3。这样出现的问题就是还有一个存在。
所以每次内层循环结束之后还要进行的操作就是i--，让i往前移动一位重新进行判断
双指针法
梳理
-
核心是一个for循环，
for (int fast = 0; fast < nums.size(); fast++)是一个时间复杂度为\(O(n)\)的算法。 -
首先是一个快指针fast，还有一个慢指针slow
-
快指针用来获取新数组的元素，而慢指针用来更新新数组的位置
大致代码内容
-
if (nums[fast] != val)这里就是快指针要获取新数组元素的特性，所以写为nums[fast] -
另外需要注意，是
!=才需要更新slow指针
LeetCode测试
暴力解法
点击查看代码
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
for (int i = 0; i < size; i++){
if (val == nums[i]){
for (int j = i + 1; j < size; j++){
nums[j - 1] = nums[j];
}
i--;
size--;
}
}
return size;
}
};
这个时间复杂度是\(O(n^2)\)
双指针法
点击查看代码
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow = 0;
for (int fast = 0; fast < nums.size(); fast++){
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
};
LeetCode977
代码随想录视频内容简记
题目中给出一个非递减顺序的数组，要求其每一位数平方之后按从小到大排列，并返回该数组
梳理
- 左右向中间依次递减
[-5,1,2,3]这样的一个数组，其平方之后得到[25,1,4,9]，注意观察后发现是左右大，中间小
- 从最大获取数组元素
对两边同时进行比较，得到最大的元素。所以，双指针思想的应用在此，有一点特殊，需要额外引入一个指针j来和i同时进行比较出最大的。由此，我们才是完成了双指针中中获取新数组元素的一步
- 从最后更新数组位置
得到想要的新数组元素之后，需要对其进行更新。按照题目要求，需要从最后更新，来保持从小到大的排列
大致代码内容
-
k = nums.size() - 1这个待会用来更新数组位置用 -
for (int i = 0, int j = nums.size() - 1; i <= j;)注意这个for循环有点特殊，首先是没有操作语句的，而且在初始化语句中有两个分别是i和j的初始化，还有就是这个条件判断是i和j作比较，感觉我没见过这种的这里的条件判断就是为了让循环向中间合拢，所以这么写
-
下面的if判断，应该是分为三种，首先是
nums[i] * nums[i] < nums[j] * nums[j]，则我们更新nums[k] = nums[j]，这里就用上前面的k了。然后剩下分别是nums[i] * nums[i] > nums[j] * nums[j]和nums[i] * nums[i] = nums[j] * nums[j]。但是这里也有一点特殊，就是当nums[i] * nums[i] = nums[j] * nums[j]时，随便怎么写成nums[k] = nums[j]或者nums[k] = nums[i]都ok的
LeetCode测试
库函数解法
需要用到一个库函数sort()
点击查看代码
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
for (int i = 0; i < nums.size(); i++){
nums[i] = nums[i] * nums[i];
}
sort(nums.begin(), nums.end());
return nums;
}
};
双指针法
这个有坑，一测试的时候发现了
不能像27题一样，想当然用nums[k] = nums[j] * nums[j]这样的操作。因为这个题不是顺序遍历的，而且涉及到3个索引的值，分别是i,j,k，所以会有互相覆盖的情况产生。
举例：
-
刚开始是
[-4,-1,0,3,10]，-4和10比较之后应该赋k为100，第一遍循环得到[-4,-1,0,3,100]，正常。 -
第二遍循环，-4和3比较之后赋k为16，此时得到的是
[-4,-1,0,16,100]，会把3覆盖掉，影响到了正常下一次的-1和3的比较，所以要新开辟一个vectorresult来单独存放k更新的结果。
修改之前的代码
点击查看代码
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int k = nums.size() - 1;
for (int i = 0, j = nums.size() - 1; i <= j;){
if (nums[i] * nums[i] < nums[j] * nums[j]){
nums[k] = nums[j] * nums[j];
j--;
k--;
}
else{
nums[k] = nums[i] * nums[i];
i++;
k--;
}
}
return nums;
}
};
修改后的代码
点击查看代码
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int k = nums.size() - 1;
vector<int> result(nums.size(), 0);
for (int i = 0, j = nums.size() - 1; i <= j;){
if (nums[i] * nums[i] < nums[j] * nums[j]){
result[k] = nums[j] * nums[j];
j--;
k--;
}
else{
result[k] = nums[i] * nums[i];
i++;
k--;
}
}
return result;
}
};