Leetcode刷题——数组

• • Python数组增删改查
  • 刷题
  • 小结

需要先检查 i 的范围是否在合法的范围区间，即 0 <= i <= len(nums) - 1，再进行操作。Python 中的 list 直接封装了部分数组操作，调用方法参数即可实现。

参考资料：
https://github.com/itcharge/LeetCode-Py

• 66. 加⼀
      判断末位+1 是否小于10 ，是则继续计算，否则进位，将目前位置设为0，前一位置+1
      调整输出结果，若首位为0 ，则从第二位开始输出，首位不为0则正常输出

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        digits = [0]+digits
        digits[len(digits)-1] += 1
        for i in range (len(digits)-1,0,-1):
            if digits[i] != 10:
                break
            else:
                digits[i] = 0
                digits[i-1] += 1
        if digits[0] == 0:
            return digits[1:]
        else:
            return digits 

• 724. 寻找数组的中⼼下标
       滑窗缓存代替sum，减少执行用时
       左求和*2+中心索引值 = 总和

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        sum = 0
        for i in range(len(nums)):
            sum += nums[i]
        curr_sum = 0
        for i in range (len(nums)):
            if curr_sum * 2 + nums[i] == sum :
                return i 
            curr_sum  += nums[i]
        return -1

• 189. 旋转数组
       要求使用空间复杂度为 O(1) 的原地算法
       旋转步骤如下：
       反转整个字符串
       反转区间为前k的子串
       反转区间为k到末尾的子串
       需要注意的是题目输入k大于nums.size怎么办？
       其实就是右移 k % nums.size() 次，即：15 % 7 = 1
       来源：https://github.com/youngyangyang04/leetcode-master

class Solution:
    def rotate(self, A: List[int], k: int) -> None:
        def reverse(i, j):
            while i < j:
                A[i], A[j] = A[j], A[i]
                i += 1
                j -= 1
        n = len(A)
        k %= n
        reverse(0, n - 1)
        reverse(0, k - 1)
        reverse(k, n - 1)

• 48. 旋转图像
      原矩阵可以通过一次上下水平翻转+主对角线翻转得到旋转后的二维矩阵

def rotate(self, matrix: List[List[int]]) -> None:
    n = len(matrix)
    for i in range(n//2):
        for j in range(n):
            matrix[i][j], matrix[n-i-1][j] = matrix[n-i-1][j], matrix[i][j]
    for i in range(n):
        for j in range(i):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

• 54. 螺旋矩阵
      定义上、下、左、右的边界，然后按照逆时针的顺序从边界上依次访问元素。当访问完当前边界之后，要更新一下边界位置，缩小范围，方便下一轮进行访问。并判断是否超出可访问边界。

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        up, down, left, right = 0, len(matrix)-1, 0, len(matrix[0])-1
        ans = []
        while True:
            for i in range(left, right + 1):
                ans.append(matrix[up][i])
            up += 1
            if up > down:
                break
            for i in range(up, down + 1):
                ans.append(matrix[i][right])
            right -= 1
            if right < left:
                break
            for i in range(right, left - 1, -1):
                ans.append(matrix[down][i])
            down -= 1
            if down < up:
                break
            for i in range(down, up - 1, -1):
                ans.append(matrix[i][left])
            left += 1
            if left > right:
                break
        return ans

• 498. 对角线遍历
       先不考虑问题中遍历的方向，将遍历方向只视为从左下到右上
       发现规律：第0层i+j=0，第1层i+j=1, …, 第k层i+j=k, 第m+n-2层i+j=m+n-2（m,n 行列数）
       从上述规律中看出：共遍历m+n-1层，起始点为第一列和最后一行的元素
       针对第k（k从0开始）层，起始点i=k, j=k-i（起始点在第1列）或i=m-1，j=k-i（起始点在最后一行）,从起始点向右上遍历（i -= 1, j = k - i），当i<0或j>=n时遍历终止
       将偶数(k % i == 1)层的遍历结果逆置
       参考：https://leetcode-cn.com/problems/diagonal-traverse/solution/si-lu-jian-dan-ming-liao-yi-ci-tong-guo-i6x8p/
       https://leetcode-cn.com/problems/diagonal-traverse/solution/498-dui-jiao-xian-bian-li-zui-jian-dan-y-ibu3/

def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
    m, n = len(mat), len(mat[0])
    res = []
    for k in range(m + n - 1):
        tmp = []
        
        i = k if k < m else m -1
        j = k - i
        while i >= 0 and j < n:
            tmp.append(mat[i][j])
            i -= 1
            j = k - i

        if k % 2 == 0:
            res.extend(tmp)
        else:
            res.extend(tmp[::-1])
        
    return res

学习数组基础知识，结合Python语言封装方法完成增删改查基础操作。练习力扣题时发觉：分析问题解决思路的数学规律很重要，其次是编程实现能力，至少要熟记一个解题方法。目前仍在学习阶段，积累一定解题思路后，希望可以快速给出自己的解决方案。