Array

189. 旋转数组

https://leetcode-cn.com/problems/rotate-array/
我自己能想到的就是python的slicing

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums) < 2:
            return nums
        k = k%len(nums)
        nums[k:],nums[:k]   = nums[:-k],nums[-k:]
        return nums

这个题看到比较有趣的一个办法就是三次反转法
先把[0, n - k - 1]翻转
然后把[n - k, n - 1]翻转
最后把[0, n - 1]翻转

剑指 Offer 29. 顺时针打印矩阵

https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/
先来个普通的常规的思路

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

再来一个牛逼plus的思路：拿着矩阵每次就从左向右输出最上面的一行，然后逆时针翻转90度，这样下一排刚输出的元素就又到了矩阵的第一行，且顺序是从左向右

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        while matrix:
            res += matrix.pop(0)
            matrix = list(zip(*matrix))[::-1]
        return res

剑指 Offer 59 - I. 滑动窗口的最大值

https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/

215. 数组中的第K个最大元素

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

import random
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def partition(nums,lo,hi):
            random_no = random.randint(lo,hi)
            nums[hi], nums[random_no] = nums[random_no], nums[hi]
            pivot = nums[hi]
            left = lo
            for i in range(lo,hi):
                if nums[i] < pivot:
                    nums[i], nums[left] = nums[left], nums[i]
                    left+=1
            nums[left], nums[hi] = nums[hi], nums[left]
            return left
        low = 0
        high = len(nums)-1
        k = len(nums)-k
        while True:
            j = partition(nums,low, high)
            if j<k:
                low=j+1
            elif j>k:
                high=j-1
            else:
                return nums[j]

692. 前K个高频单词

https://leetcode-cn.com/problems/top-k-frequent-words/
比215稍微复杂一下，除了比较数字，还需要比较对应的字符串的大小，注意用到cmp_to_key的功能

48. 旋转图像

https://leetcode-cn.com/problems/rotate-image/
可以先逐行翻转，再沿着斜对角翻转
也可以先沿对角线翻转，再逐行翻转 （这个方式代码写起来简单一些）

419. 甲板上的战舰

https://leetcode-cn.com/problems/battleships-in-a-board/
用战舰的头来判断数量

1. 如果是第一行或者第一列为x， 那么计算一列战舰
2. 如果在中间出现x，而这个点的左边或者上边是x，那么这肯定是战舰中部，这列战舰在遇到头部的时候已经计算过了，无需再重复计算

   class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        count = 0
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == '.': continue
                if i > 0 and board[i-1][j] == 'X': continue
                if j > 0 and board[i][j-1] == 'X': continue
                count+=1
        return count

   1314. 矩阵区域和

   https://leetcode-cn.com/problems/matrix-block-sum/
   所有的前缀和，都需要额外加个0前缀和，用来给第一个元素的前缀和用
   前缀和，注意包括和不包括的情况， 前缀和矩阵里的[rows,cols]是开区间，意思到[rows-1,cols-1]之间所有元素的和
   所以在计算answer的时候max_x需要+1，因为max_x的位置需要包括；而min_x的地方不+1

   class Solution:
    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:
        rows, cols = len(mat), len(mat[0])
        k = K
        answer = [[0 for _ in range(cols)] for _ in range(rows)]
        pre_sum = [[0 for _ in range(cols+1)] for _ in range(rows+1)]
        for i in range(1, rows+1):
            for j in range(1, cols+1):
                pre_sum[i][j] = pre_sum[i-1][j] + pre_sum[i][j-1] - pre_sum[i-1][j-1]+mat[i-1][j-1]
        for i in range(rows):
            for j in range(cols):
                min_rows = i-k if i-k>=0 else 0
                max_rows = i+k if i+k<rows else rows-1
                min_cols = j-k if j-k>=0 else 0
                max_cols = j+k if j+k<cols else cols-1
                answer[i][j] = pre_sum[max_rows+1][max_cols+1] - pre_sum[min_rows][max_cols+1] - pre_sum[max_rows+1][min_cols] + pre_sum[min_rows][min_cols]
        return answer