代码随想录二刷day01

• • • 704. 二分查找
    • 27. 移除元素
    • 977. 有序数组的平方

704. 二分查找

题目链接
做这种题最好现在纸上写一写，如果在大脑中想，可能一会就晕了。 二刷的时候发现了一个新的知识点 即： >>的作用
二分法第二种写法：左闭右开[left, right）

• left <=right 时没有意义
• if (nums[middle] > target) right 要赋值为 middle ，因为当前这个nums[middle]一定不是target
• if (nums[middle] < target) left 要赋值为 middle ，因为当前这个nums[middle]一定不是target

class Solution {
public:int search(vector& nums, int target) {int left = 0;int right = nums.size(); // 定义target在左闭右开的区间里，即：[left, right)while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间，所以使用 > 1);if (nums[middle] > target) {right = middle; // target 在左区间，在[left, middle)中} else if (nums[middle] < target) {left = middle + 1; // target 在右区间，在[middle + 1, right)中} else { // nums[middle] == targetreturn middle; // 数组中找到目标值，直接返回下标}}// 未找到目标值return -1;}
};

中 int middle = left + ((right - left) >> 1) 相当于 int middle = left + ((right - left) / 2)
举个小栗子

>>: 二进制右移
举个例子: 1010 >> 1 == 0101
1010 十进制 10
0101 十进制 5
综上 >> 1 作用相当于除二

所以 left + ((right -left) >> 1) ==> left + ((right -left)/2)

为什么不直接用(left + right) /2 而用left + ((right -left) >> 1)
答: 是因为left + right 在某种情况下可能会超过基本类型所能容纳的最大值,而且 >> (位运算) 比 / 运算要快一点。

27. 移除元素

题目链接
解题思路： 双指针(快慢指针法) 一快一慢。

本题中：

• 快指针 是用来获取新数组中的元素；
• 慢指针是用来获取新数组中需要更新的位置。

// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
public:int removeElement(vector& nums, int val) {int slowIndex = 0;for(int fastIndex = 0; fastIndex < nums.size();fastIndex++){if(val != nums[fastIndex]){nums[slowIndex++] = nums[fastIndex];}}return slowIndex;}
};

注：数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

977. 有序数组的平方

题目链接
注：本题中给出的数组是有序的，则最大值应该在两端，不可能在中间。
采用双指针，从两边向中间就行遍历，并比较大小，将大的放在右端。
i 指向 起始位置，j指向终止位置

class Solution {
public:vector sortedSquares(vector& nums) {int k = nums.size() - 1;vector 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[i] *nums[i];i++;}else{result[k--] = nums[j] * nums[j];j-- ;}}return result; //最终返回排序好的平方和数组}
};

最终返回排序好的平方和数组。