Leetcode 数组篇

Leetcode刷题记录——数组篇

Leetcode704 二分查找

使用二分查找的前提条件：

• 数组有序
• 数组内无重复元素（因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的）

二分查找涉及的很多的边界条件，逻辑比较简单，但就是写不好。例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1？

因此要遵循循环不变量原则，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作

区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)，本题采用左闭右闭的写法

区间的定义这就决定了二分法的代码应该如何写，因为定义target在[left, right]区间，所以有如下两点：

• while (left <= right) 要使用 <= ，因为left == right是有意义的，在[left, right]区间是合法的，所以使用 <=
• if (nums[middle] > target) right 要赋值为 middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1

Python代码如下：

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

Leetcode35 搜索插入位置

看到有序数组就可以想到二分

与上题一样，考虑循环不变量，注意区间整体保持一致

Python代码如下：

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

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

一开始思路想的太复杂了

依旧是二分的思路，可以先不管里面是有重复的值，我只需要确定能找到就行

找到之后退出循环，定义start，end一个往前，一个往后，找到区间位置

如果退出循环的时候，left >= right。说明在之前的循环里，没有找到middle，就是说nums里没有target，直接返回[-1,-1]

Python代码如下：

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = 0
        right = len(nums)
        middle = 0
        while left < right:
            middle = left + (right-left) // 2
            if target > nums[middle]:
                left = middle + 1
            elif target < nums[middle]:
                right = middle
            else :
                break
        if left >= right:
            return [-1, -1]
        start = middle
        end = middle
        while start > 0 and nums[start-1] == target:
            start -= 1
        while end < len(nums)-1 and nums[end+1] == target:
            end += 1
        return [start, end]

Leetcode69 x的平方根

依然可以考虑二分查

要注意的是平方根开不尽的话要向下取整

给定的数的平方根一定在某两个整数之间

Python代码如下：

class Solution:
    def mySqrt(self, x: int) -> int:
        left = 0
        right = x
        ans = 0
        while left <= right:
            middle = left + (right-left) // 2
            if middle * middle <= x:
                ans = middle
                # 注意是更新left, 向后面去找 
                left = middle + 1
            else:
                # 注意是更新right
                right = middle - 1
        return ans

Leetcode367 有效的完全平方数

还是一样的二分查找

Python代码如下：

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        left = 0
        right = num
        while left <= right:
            middle = left + (right-left) // 2
            if middle * middle < num:
                left = middle + 1
            elif middle * middle > num:
                right = middle - 1
            else:
                return True
        return False

Leetcode26 删除有序数组中的重复项

数组是有序的，那么出现不同的元素一定是相邻的

定义两个快慢指针，slow=0、 fast=1

fast往后走，遇到与slow不相同的数值时，把值赋给slow+1，之后slow+1

重复此过程，直到fast走到底

Python代码如下：

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        slow = 0
        fast = 1
        while fast < len(nums):
            if nums[fast] == nums[slow]:
                fast += 1
            else:
                nums[slow+1] = nums[fast]
                slow += 1
                fast += 1
        return slow+1

Leetcode27 移除元素

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作

定义快慢指针

• 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
• 慢指针：指向更新 新数组下标的位置

也就是快指针去寻找符合条件的元素，慢指针用来更新需要返回的数组，这样在一次遍历中，即可完成数组的更新

Python代码如下：

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

Leetcode844 比较含退格的字符串

因为'#'的出现是要删除前面的字符，所以考虑从后往前遍历

具体地，定义 skip 表示当前待删除的字符的数量。每次我们遍历到一个字符：

若该字符为退格符，则我们需要多删除一个普通字符，我们让 skip 加 1；

若该字符为普通字符：

若 skip 为 0，则说明当前字符不需要删去；

若 skip 不为 0，则说明当前字符需要删去，让 skip 减 1

这样，定义两个指针，分别指向两字符串的末尾

每次让两指针逆序地遍历两字符串，直到两字符串能够各自确定一个字符，然后将这两个字符进行比较

重复这一过程直到找到的两个字符不相等，或其中某个字符串遍历完为止

Python代码如下：

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        skipS = 0
        skipT = 0
        i = len(s) - 1
        j = len(t) - 1
        while i >= 0 or j >= 0:
            while i >= 0:
                if s[i] != '#' and skipS > 0:
                    skipS -= 1
                    i -= 1
                if s[i] != '#' and skipS == 0:
                    break
                if s[i] == '#':
                    skipS += 1
                    i -= 1
            while j >= 0:
                if t[j] != '#' and skipT > 0:
                    skipT -= 1
                    j -= 1
                if t[j] != '#' and skipT == 0:
                    break
                if t[j] == '#':
                    skipT += 1
                    j -= 1
            if i >= 0 and j >= 0:
                if s[i] != t[j]:
                    return False
            elif i < 0 and j >= 0:
                return False
            elif i >= 0 and j < 0:
                return False
            i -= 1
            j -= 1
        return True

Leetcode283 移动零

依旧是双指针的思路

定义两个快慢指针，slow=0、 fast=0

判断当前fast指针所在位置元素是否等于0

若不等于0，则与slow指针指向的元素交换位置，也就是把非零元素移到前面；若等于0，fast继续往后走

之后slow+1、 fast+1，直到fast走到底

最后非零元素则是全部移动到了最后

Python代码如下：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return  nums
        slow = 0
        fast = 0
        while fast < len(nums):
            if nums[fast] != 0:
                nums[slow], nums[fast] = nums[fast], nums[slow]
                slow += 1
                fast += 1
            else:
                fast += 1
        return nums

Leetcode977 有序数组的平方

数组其实是有序的， 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，head指向起始位置，tail指向终止位置。

定义一个新数组res，和nums数组一样的大小，让index指向res数组终止位置。

Pytho代码如下：

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        length = len(nums)
        head = 0
        tail = length - 1
        index = length - 1
        res = [float('inf')] * len(nums)
        while head <= tail:
            if abs(nums[head]) > abs(nums[tail]):
                res[index] = nums[head] * nums[head]
                index -= 1
                head += 1
            else:
                res[index] = nums[tail] * nums[tail]
                index -= 1
                tail -= 1
        return res

Leetcode209 长度最小的子数组

首先想到的暴力法，思路很简单，两个for循环，找到所有的连续子组合，如果该组合>=target则记录长度，最终返回长度最小的记录即可

这道题可以用滑动窗口的思想来解决：

在暴力解法中，是一个for循环为滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环 完成了一个不断搜索区间的过程

那么滑动窗口如何用一个for循环来完成这个操作呢？

首先要思考，如果用一个for循环，那么应该表示滑动窗口的起始位置，还是终止位置？

如果只用一个for循环来表示滑动窗口的起始位置，那么如何遍历剩下的终止位置？

此时难免再次陷入暴力解法的怪圈

所以 如果只用一个for循环，那么这个循环的索引，一定是表示滑动窗口的终止位置

Python代码如下：

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        sum = 0
        start = 0
        end = 0
        length = len(nums)
        max_len = float('inf')
        for end in range(length):
            sum = sum + nums[end]
            while sum >= target:
                # 如果此时窗口内的和>=target,那么试着剔除窗口的第一个元素，看是否还成立
                # 但操作前,需要先记录此时成立情况下的窗口长度
                res = end - start + 1
                if res < max_len:
                    max_len = res
                sum = sum - nums[start]
                start += 1

        if max_len == inf:
            return 0
        else:
            return max_len

Leetcode904 水果成篮

题目翻译成人话：找至多包含两种元素的最长子串，并返回其长度

这道题的思路和滑动窗口类似

一个for循环去遍历end的位置，遍历所有种类小于2的情况，中间记录最大的长度，最后返回

用一个map记录出现的元素以及次数

每次将end移动一个位置，并将当前元素加入哈希表

如果此时哈希表不满足要求（即哈希表中出现超过两个键值对），那么我们需要不断移动start，并将 fruits[start]从哈希表中对应的值-1，需要注意的是，将 fruits[start]从哈希表中-1后，如果 fruits[start]在哈希表中的出现次数减少为 0，需要将对应的键值对从哈希表中移除

Python代码如下：

class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        map = {}
        max_len = 0
        start = 0
        for end, item in enumerate(fruits):
            map[item] = map.get(item, 0) + 1
            while len(map) > 2:
                map[fruits[start]] -= 1
                if map[fruits[start]] == 0:
                    del map[fruits[start]]
                start += 1
            max_len = max(max_len, end-start+1)
        return max_len

Leetcode76 最小覆盖子串

依然是滑动窗口方法

首先用一个map存储t中所有的元素以及出现的次数

定义start、end指针

定义一个for循环，先让end指针在s中往后走，走到第一个符合条件的位置(遇到map里的元素，对应位置-1，表示用过该元素一次了)

符合条件的语句为all(value <= 0 for value in map.values())，表示map中所有位置的元素均小于等于0，因为s中的子串只要包含t即可，不一定所有元素一一对应的包含，比方说s里面’…aa…’，但是t中只有’.a…’也算是包含

接着让start指针往后走，看看有没有更优解

如果s[start]未在map中，那么start可以直接+1

如果s[start]出现在map中，那么map中的对应位置要+1，start+1

start在走的时候要套在while循环里，也就是说当while循环不成立时，start走到了第一次不成立的位置，此后end再继续往后走

遍历的时候一直在记录成立的子串，最后返回最短的那个即可

Python代码如下：

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        map = {}
        res = ''
        for i in t:
            map[i] = map.get(i, 0) + 1
        start = 0
        min_len = float('inf')
        for end, item in enumerate(s):
            if item in map:
                map[item] -= 1
            while all(value <= 0 for value in map.values()):
                if end-start+1 < min_len:
                    min_len = end-start+1
                    res = s[start:end+1]
                if s[start] in map:
                    map[s[start]] += 1
                start += 1
        return res

Leetcode54 螺旋矩阵

在二维数组中，记住这个求行列大小的方法

rows = len(matrix)
cols = len(matrix[0])

用一个visted记录matrix某个位置是否被访问过

定义directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]表示方向

例如，往右走是row+0，col+1，定义在directions[0]中

接下来就是按照顺序在matrix中走，判断row，col是否越界的同时判断visted是否被访问过来改变走的方向

每一次循环都会填入一个值，循环结束返回即可

Python代码如下：

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        rows = len(matrix)
        cols = len(matrix[0])
        nums = [0] * (rows * cols)
        visted = [[0] * cols for _ in range(rows)]
        directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        row, col = 0, 0
        directionIndex = 0
        for i in range(len(nums)):
            nums[i] = matrix[row][col]
            visted[row][col] = 1
            nextRow = row + directions[directionIndex][0]
            newtCol = col + directions[directionIndex][1]
            if nextRow < 0 or nextRow >= rows or newtCol < 0 or newtCol >= cols or visted[nextRow][newtCol] == 1:
                directionIndex = (directionIndex+1) % 4
            row += directions[directionIndex][0]
            col += directions[directionIndex][1]
        return nums

Leetcode59 螺旋矩阵II

这道题考察对代码的掌控能力，仍然会遇到复杂的边界问题，坚持循环不变量原则

模拟顺时针画矩阵的过程:

• 填充上行从左到右
• 填充右列从上到下
• 填充下行从右到左
• 填充左列从下到上

要处理好边界问题，就要坚持循环不变量原则

本题采用左闭右开的写法

Python代码如下：

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        # 先创建 n * n 的全0矩阵
        nums = [[0] * n for _ in range(n)]
        x = 0
        y = 0
        # 偶数n能走完整圈,奇数n会留中间一个空
        loop = n // 2
        # n为奇数时, 矩阵的中间位置为nums[mid][mid]
        mid = n // 2
        # 用来给矩阵中每一个空格赋值
        count = 1
        offset = 1
        while loop:
            # 从左到右
            for i in range(x, n - offset):
                nums[x][i] = count
                count += 1
            # 从上到下
            for i in range(y, n - offset):
                nums[i][n - offset] = count
                count += 1
            # 从右到左
            for i in range(n - offset, x, -1):
                nums[n - offset][i] = count
                count += 1
            # 从下到上
            for i in range(n - offset, y, -1):
                nums[i][y] = count
                count += 1
            x += 1
            y += 1
            offset += 1
            loop -= 1
        if n % 2 != 0:
            nums[mid][mid] = count
        return nums