本身昨天才加入，加入得比较晚，遂按顺序补上前面的打卡

数组理论基础

• 主要是数组的存储，主要注意下标为0开始，且内存空间地址连续，在删除和增添元素的时候，需要移动其他元素的地址。
• 删除实际上是让其他元素来覆盖地址。（对应题目2）
• 二维数组在地址空间上是连续的。

704. 二分查找

题目：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

思路整理：

1.暴力开解：遍历整个数组nums判断下标对应值是否为target，若存在，返回对应值；若不存在，返回-1：

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        for i in range(len(nums)):
            if nums[i] == target:
                return i
        return -1

执行用时自然偏长

暴力求解分析

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums) - 1
        middle = 0
        while left <= right:
            middle = left + (right - left) // 2
            if nums[middle] > target: 
                # 表示需要查找的数可能在middle的左侧
                right = middle - 1
            elif nums[middle] < target:
                # 表示需要查找的数可能在middle的右侧
                left = middle + 1
            else:
                return middle
        return -1

第二种写法锻炼左闭右开，标注释的地方是自己写的时候debug出问题的地方，之后要注意这几点：

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums) # 注意修改right位置
        middle = 0
        while left < right: # 二分查找的运行条件需要去掉等于号
            middle = left + (right - left) // 2
            if nums[middle] > target: 
                right = middle # right更新是直接排除原middle的位置的
            elif nums[middle] < target:
                left = middle + 1
            else:
                return middle
        return -1

27. 移除元素

题目：

给你一个数组 nums和一个值 val，你需要 原地 移除所有数值等于 val的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

• 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
• 返回 k。

思路整理：

1.暴力解法：万物皆可暴力。通过判断是否有不能与所求 val的，有则赋值指向下一位置，所有元素前移，没有则跳过。

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        i, l = 0, len(nums)
        while i < l:
            if (nums[i] == val):
                for j in range(i + 1, l):
                    # 原地移除，即剔除该数，并将数组后面数字都往前挪一位
                    # 操作到第i个位置，即从i+1开始，注意同步修改数组长度l，而不是用原长度len(nums)
                    nums[j - 1] = nums[j]
                l -= 1
                i -= 1
            i += 1
        return l

暴力求解，消耗内存较多

2.双指针法：
快慢指针，通过快指针去遍历需要寻找的相等的数，而慢指针则指向新的数组对应位置：

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        fast = 0
        slow = 0
        size = len(nums)
        while fast < size:
            # fast对应0 - (size - 1)范围，故fast < size时成立
            if nums[fast] != val:
                # 不等于val时更新slow对应的新数组
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

3.相向双指针法：
代码随想录中还提供了一种方法，前两种可以自己想到，但这种了解完应该会修改数组原本的顺序，它是通过right指针查找靠右侧不符合val的值，返回地址覆盖left指向的等于val的值。

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        n = len(nums)
        left,right = 0, n-1
        while left <= right:
            while left <= right and nums[left] != val:
                # left左侧表示保留不为val的新数组
                left += 1
            while left <= right and nums[right] == val:
                # right右侧表示剔除的为val的部分
                right -= 1
            if left < right:
                # left指向数组中需要移除的部分，由最右侧right指向的地址进行替换
                nums[left] = nums[right]
                left += 1
                right -= 1
        return left

977.有序数组的平方

题目：

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

思路整理：

1.一行秒了
直接使用sorted解了（对应暴力排序+列表推导法）

class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        return sorted(num * num for num in nums)

2、暴力排序法：
即将所有元素平方后再使用sort进行排序.

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

3.两个双指针法
a. 利用示例里非递减的顺序，将头尾两个数平方后进行比较，从后往前安插各个元素，随之调整指针的位置（达成非递减的要求）

class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        l, r, i = 0, len(nums)-1, len(nums)-1 # 注意为len(nums) - 1
        res = [float('inf')] * len(nums) # 需要提前定义列表，存放结果
        while l <= r:  # 需要取等号
            if nums[l] ** 2 < nums[r] ** 2: 
                res[i] = nums[r] ** 2
                r -= 1 
            else:
                res[i] = nums[l] ** 2
                l += 1 
            i -= 1 
        return res

b.双指针 + 反转列表
先按照绝对值从大到小顺序排列，再将列表反转
list先进排序在先

class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        new_list = []
        left, right = 0, len(nums) - 1
        while left <= right:
            # 注意算法逻辑，保证绝对值大的先进列表，哪个指针对应数进去就移动哪个指针
            if abs(nums[left]) < abs(nums[right]):
                new_list.append(nums[right] ** 2)
                right -= 1
            else:
                new_list.append(nums[left] ** 2)
                left += 1
        return new_list[::-1]
        # 输出[start:stop:step]，从开始到结束，用-1实现反向遍历