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

数组理论基础

1.数组是存放在连续内存空间上的相同类型数据的集合。
2.数组的元素是不能删除的，只能覆盖。
3.不同语言不一样，在C++中，二维数组是连续分布的

704.二分查找

题目

思路与解法

第一想法： 简单的二分查找，三个指针：left、right、mid。while left <= right 就持续进行二分查找。若是直到 left > right 都没找到，就是找不到了。

class Solution:def search(self, nums: List[int], target: int) -> int:left = 0right = len(nums) - 1while left <= right :mid = (left + right) // 2if target == nums[mid]:return midelif target < nums[mid]:right = mid -1else:left = mid + 1return -1

carl的讲解： 二分法有一个比较重要的思想 循环不变量。循环不变量 是指，在二分查找中，保持不变量（区间的定义就是不变量），就是在while寻找每一次边界的 处理逻辑 都要坚持根据区间的定义来操作。简单来说，怎么定义区间，就决定了数据取舍的逻辑。

27.移除元素

题目

思路与解法

第一想法：
1.暴力法，找到一个就把后面的提上来，如下：

class Solution:def removeElement(self, nums: List[int], val: int) -> int:lens = len(nums)i = 0while i < lens:# print(i)if nums[i] == val:# print(nums[i])j  = iwhile j < lens-1 :nums[j] = nums[j+1]j += 1lens = lens - 1else:i = i + 1print(lens)return lens

2.快慢指针。慢指针是最终结果，快指针是用于遍历。 起初，快指针一直往后遍历，当值不等于value时，慢指针等于快指针；当遇到与value相同的值时，慢指针停下，快指针继续往后。如下：

class Solution:def removeElement(self, nums: List[int], val: int) -> int:slow = fast = 0lens = len(nums)while fast < lens:if nums[fast] != val:nums[slow] = nums[fast]slow += 1fast += 1elif nums[fast] == val:fast += 1return slow

977.有序数组的平方

题目

思路与解法

第一想法： 1. 暴力法

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:for i in range(len(nums)):nums[i] = nums[i] * nums[i]nums.sort()return nums

carl: 双指针。想要速度快，自然要想到用空间换

# 双指针（提前定义定长列表）
class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:res = [float('inf')] * len(nums)left = 0right = len(nums) -1 i = len(nums) -1while left <= right:if nums[left] * nums[left] > nums[right] * nums[right]:res[i] = nums[left] * nums[left]i -= 1 left += 1else :res[i] = nums[right] * nums[right]right -= 1i -= 1# res.reverse()return res

# 双指针 + 反转列表
class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:res = []left = 0right = len(nums) -1 while left <= right:if nums[left] * nums[left] > nums[right] * nums[right]:res.append(nums[left] * nums[left])left += 1else :res.append(nums[right] * nums[right])right -= 1# res.reverse()return res[::-1]