代码随想录算法训练营第一天| 704.二分查找、27.移除元素、977.有序数组的平方

704.二分查找 题目链接：https://leetcode.cn/problems/binary-search/ 解题思路：定义一个中间索引middle,如果nums[middle]>target,则更新左区间的右边界，如果target>nums[middle],则更新右区间的左边界 注意点！！！始终按照[left,right]左闭右闭的区间定义 代码实现：left = 0right = len(nums) - 1while left <= right: #left=right的时候，左闭右闭区间是合法的middle = left + (right - left) / 2 #防止溢出if nums[middle] > target:right = middle - 1 #取middle的时候肯定不等于target，所以right从middle-1开始elif target > nums[middle]:left = middle + 1 #取middle的时候肯定不等于target，所以left从middle+1开始else:return middlereturn -127.移除元素 题目链接：https://leetcode.cn/problems/remove-element/ 方法一：暴力值法 解题思路：找到等于val的值，将他后面的所有元素向前移一个索引，即遍历后面的所有值，去覆盖原先的值 代码实现：# l, r = 0, len(nums)# while l < r:# if nums[l] == val:# for j in range(l+1,r): #遍历后面所有值# nums[j-1] = nums[j] #覆盖前值# l -= 1# r -= 1 #索引的位置都向前移动1# l += 1# return l方法二：双指针法 代码实现：fast = 0slow = 0size = len(nums)while fast < size:if nums[fast] != val:nums[slow] = nums[fast] #赋值给慢指针slow += 1 #在新列表中，每新增一个值，slow要往后移动一个单位fast += 1return slow977.有序数组的平方 题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/ 方法：双指针法 注意点！！！非递减序列即递增序列，刚开始读题没读懂这层意思。 解题思路：可能会有负数，整组数组中最大值要么在最左边，要么在最右边，所以左右分别设置一个指针，比较大小，指针数较大的赋值给k索引，向里移动一个单位，继续比较。由于要求新数组也要递增排列，所以将每次较大的值赋给最大的索引（即最大值会出现在最右边） 代码实现：l, r = 0, len(nums) - 1k = len(nums) - 1result = [0] * len(nums) #初始化一个长度为len(nums)的列表while l <= r: #当左右指针指向一个数的时候合法，可以取等号if nums[l] ** 2 < nums[r] ** 2: #右边大result[k] = nums[r] ** 2r -= 1 #右指针左移else: #包含左边等于右边的情况，可以将任何一个赋值给kresult[k] = nums[l] ** 2l += 1 # 左指针右移k -= 1return result