二刷保持手感

数组篇

文章目录

• 二刷保持手感
• 二分查找
• • 二分的板子
  • 有效的完全平方数
  • x的平方根
  • 搜索插入的位置
  • 在排序数组中找元素第一个和最后一个位置
  • 其余的二分的题我在另一篇有总结
• 27.移除元素
• 977. 有序数组的平方

二分查找

二分

二分的板子

二分的板子有两个，

def search(l, r):while l < r:mid = (l+r) >> 1if check(mid): r = midelse: l = mid + 1return r

def search(l, r):while l < r:mid = (l+r+1) >> 1if check(mid): l = midelse: r = mid - 1return l

所以这道题也有两种写法

class Solution:def search(self, nums: List[int], target: int) -> int:l, r = 0, len(nums)-1while l < r:mid = (l+r) >> 1if nums[mid] >= target: r = midelse: l = mid + 1return r if nums[r] == target else -1

class Solution:def search(self, nums: List[int], target: int) -> int:l, r = 0, len(nums)-1while l < r:mid = (l+r+1) >> 1if nums[mid] <= target: l = midelse: r = mid - 1return l if nums[l] == target else -1

尝试拿c++写的第一天，c++中的循环，判断，以及变量的声明，执行语句要加分号不是很熟悉，写几道应该就熟悉了

class Solution {
public:int search(vector& nums, int target) {int l = 0;int r = nums.size() - 1;while (l < r) {int mid = (l + r) >> 1;if (nums[mid] >= target) {r = mid;} else {l = mid + 1;}}if (nums[r] == target) {return r;} else {return -1;}}
};

有效的完全平方数

class Solution {
public:bool isPerfectSquare(int num) {int l = 0;long int r = num;while (l < r) {long int mid = (l + r) >> 1;if (mid * mid >= num) {r = mid;} else {l = mid + 1;}}if (r * r == num) {return true;}else {return false;}}
};

x的平方根

这道题是要找小于等于target的最大值，要记住这种情况找大的就要从右边的区间去找，就是令l = mid
如果用板子1就是找大于等于target的最小值了，那么如果x是8，就会返回3

class Solution:def mySqrt(self, x: int) -> int:l, r = 0, xwhile l < r:mid = (l+r+1) >> 1if mid * mid <= x: l = midelse: r = mid - 1return l

搜索插入的位置

这道题首先要分析出找的是大于等于target的最小下标，找小的要从左边区间找，得出要用板子1

def searchInsert(self, nums: List[int], target: int) -> int:if nums[-1] < target: return len(nums)l, r = 0, len(nums)-1while l < r:mid = (l+r) >> 1if nums[mid] >= target: r = midelse: l = mid + 1return r

在排序数组中找元素第一个和最后一个位置

这个题的思路是，数组中元素第一个位置对应的是大于等于target的最小位置，第二个对应的是小于等于target的最大值，如果说第一个就找不到的话，直接return [-1,-1]就不用继续找了，

class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:if nums == []: return [-1, -1]res = []l, r = 0, len(nums)-1while l < r:mid = (l+r) // 2if nums[mid] >= target: r = midelse: l = mid+1if nums[r] == target: res.append(r)else: return [-1,-1]l, r = 0, len(nums)-1while l < r:mid = (l+r+1) // 2if nums[mid] <= target: l = midelse: r = mid - 1res.append(l)  #因为这个题默认都是成对出现不加if nums[l] == tar也行return res 

其余的二分的题我在另一篇有总结

27.移除元素

移除元素
这道题不想让我们用额外的数组空间

暴力解法是两个for循环, 第一个for循环从头至尾，如果找到了val就从当前的下一位开始到尾，把每一位往前移动一下

快慢指针解法时间复杂度O(n), 只用一个循环就行，快指针找的是所有不等于val的，然后把这些值赋给慢指针，慢指针的长度同时也加1；这就意味着慢指针接受了所有的不等于val的值，它最后的位置也就是新数组的长度

class Solution {
public:int removeElement(vector& nums, int val) {int j = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] != val) {nums[j++] = nums[i];}}return j;}
};

977. 有序数组的平方

977. 有序数组的平方
这个数组有负数，平方后两端应该大中间小，所以可以用两个指针从两端走，要注意终止条件是while l <= r， 为什么呢？如果终止条件是l < r，最后一对比较完，只进位一个，还会剩下一个

第二点就是提前初始化好res数组，如果不初始化好而选择append的话会出现问题，我也不明白为什么

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:res = [0] * len(nums)k = len(nums)-1i, j = 0, kwhile i <= j:if nums[i] ** 2 > nums[j] ** 2:res[k] = nums[i] ** 2k -= 1i += 1else:res[k] = nums[j] ** 2k -= 1j -= 1return res