算法题记录 40

3375.使数组的值全部为K的最少操作次数（1383）

给你一个整数数组 nums 和一个整数 k 。

如果一个数组中所有严格大于 h 的整数值都相等，那么我们称整数 h 是合法的。

比方说，如果 nums = [10, 8, 10, 8] ，那么 h = 9 是一个合法整数，因为所有满足 nums[i] > 9 的数都等于 10 ，但是 5 不是合法整数。

你可以对 nums 执行以下操作：

选择一个整数 h ，它对于当前 nums 中的值是合法的。
对于每个下标 i ，如果它满足 nums[i] > h ，那么将 nums[i] 变为 h 。
你的目标是将 nums 中的所有元素都变为 k ，请你返回最少操作次数。如果无法将所有元素都变 k ，那么返回 -1 。

涉及知识点

脑筋急转弯

解决思路

实际上是统计nums中大于k的元素的个数，返回这个个数即可。

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
       mn=min(nums)
       if k > mn:
           return -1
       return len(set(nums))-(k==mn)

209.长度最小的子数组（中等）

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

涉及知识点

滑动窗口

解决思路

枚举子数组的右端点，维护一个变量s记录当前子数组的和，枚举子数组的左端点，尽量缩小子数组的长度。每次更新答案时，判断当前子数组的和是否大于等于target，如果是，则更新答案。
整体更新思路跟蜗牛蠕动比较像。右端点进一步，左端点尽可能向右移动。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        ans = n + 1  # 也可以写 inf
        s = left = 0
        for right, x in enumerate(nums):  # 枚举子数组右端点
            s += x
            while s - nums[left] >= target:  # 尽量缩小子数组长度
                s -= nums[left]
                left += 1  # 左端点右移
            if s >= target:
                ans = min(ans, right-left+1)
        return ans if ans <= n else 0

289.生命游戏（中等）

根据百度百科，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

给定当前 board 的状态，更新 board 到下一个状态。

注意你不需要返回任何东西。

涉及知识点

矩阵

解决思路

按题目规则模拟即可。

DIRECTIONS = [(0, 1), (1, 0), (0, -1), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)]
class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def count_live_neightbors(i:int,j:int)->int:
            cnt = 0
            for xi,yi in DIRECTIONS:
                ni,nj = i+xi,j+yi
                if 0 <= ni < len(board) and 0 <=nj < len(board[0]):
                    cnt += board[ni][nj] & 1
            return cnt
        board_new=[[0]*len(board[0]) for _ in range(len(board))]
        for i in range(len(board)):
            for j in range(len(board[0])):
                live =board[i][j] & 1
                live_neighbors = count_live_neightbors(i,j)
                if live:
                    if live_neighbors < 2 or live_neighbors > 3:
                        board_new[i][j] = 0
                    else:
                        board_new[i][j] = 1
                else:
                    if live_neighbors == 3:
                        board_new[i][j] = 1
                    else:
                        board_new[i][j] = 0
        board[:] =board_new