第9周LeetCode记录

总结：

动画演示，用一个栈A记录遍历过程中最小的值，另一个栈B：原数组倒序遍历，入栈，碰到比栈顶元素大的，出栈。

如果出栈元素大于栈A同索引元素，则说明132满足。

用一个栈去记录每个索引最小元素，另一个栈出栈时肯定满足32，再将1和2比较是否成立。

11.12 42. 声明游戏

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

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。

输入： 
[
  [0,1,0],
  [0,0,1],
  [1,1,1],
  [0,0,0]
]
输出：
[
  [0,0,0],
  [1,0,1],
  [0,1,1],
  [0,1,0]
]

最优解一：暴力解法

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """

        neighbors = [(1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1), (0,1), (1,1)]

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

        # 从原数组复制一份到 copy_board 中
        copy_board = [[board[row][col] for col in range(cols)] for row in range(rows)]

        # 遍历面板每一个格子里的细胞
        for row in range(rows):
            for col in range(cols):

                # 对于每一个细胞统计其八个相邻位置里的活细胞数量
                live_neighbors = 0
                for neighbor in neighbors:

                    r = (row + neighbor[0])
                    c = (col + neighbor[1])

                    # 查看相邻的细胞是否是活细胞
                    if (r = 0) and (c = 0) and (copy_board[r][c] == 1):
                        live_neighbors += 1

                # 规则 1 或规则 3        
                if copy_board[row][col] == 1 and (live_neighbors <2 or live_neighbors > 3):
                    board[row][col] = 0
                # 规则 4
                if copy_board[row][col] == 0 and live_neighbors == 3:
                    board[row][col] = 1

最优解总结

复制了一个数组作为生成的数组，用8个方向来遍历原数组，得到新数组

最优解二：使用额外状态。

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """

        neighbors = [(1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1), (0,1), (1,1)]

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

        # 遍历面板每一个格子里的细胞
        for row in range(rows):
            for col in range(cols):

                # 对于每一个细胞统计其八个相邻位置里的活细胞数量
                live_neighbors = 0
                for neighbor in neighbors:

                    # 相邻位置的坐标
                    r = (row + neighbor[0])
                    c = (col + neighbor[1])

                    # 查看相邻的细胞是否是活细胞
                    if (r = 0) and (c = 0) and abs(board[r][c]) == 1:
                        live_neighbors += 1

                # 规则 1 或规则 3 
                if board[row][col] == 1 and (live_neighbors <2 or live_neighbors > 3):
                    # -1 代表这个细胞过去是活的现在死了
                    board[row][col] = -1
                # 规则 4
                if board[row][col] == 0 and live_neighbors == 3:
                    # 2 代表这个细胞过去是死的现在活了
                    board[row][col] = 2

        # 遍历 board 得到一次更新后的状态
        for row in range(rows):
            for col in range(cols):
                if board[row][col] > 0:
                    board[row][col] = 1
                else:
                    board[row][col] = 0

总结

每个单元格重新定义一种状态既可以记录当前信息，也可以保存之前的信息，就可以避免复制数组的操作。

11.14 43. 重复DNA序列

所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。

编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]

输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]

思路

KMP字符串匹配算法，目标字符串由输入字符串截取，输入字符串长度为n，目标字符串最多为n-9种。

我的解（滑动窗口遍历）

class Solution:
    @classmethod
    def findRepeatedDnaSequences(self, s: str) -> list:
        has_seen = set()
        s_len = len(s)
        target = set()
        for index in range(s_len - 9):
            get_s = s[index:index + 10]
            if get_s not in has_seen:
                has_seen.add(get_s)
            else:
                target.add(get_s)
        return list(target)

最优解（位运算）

python中的按位取反符号为 ~

定义一个变量为 a=60

在做~a时候，需要经历以下步骤：

1）转换为2进制：    0011 1100 （第一位是符号位，0表示正数，1表示负数）

2）计算补码：          0011 1100（正数的补码不变，负数的话，除去符号位，其他按位取反，最后加1）

3）按位取反操作：   1100 0011

4）转换为原码：       1011 1101（补码的补码就是原码）

5）转换为10进制：    -61

• 负数的与运算都要转化为补码

class Solution:
    @classmethod
    def findRepeatedDnaSequences(self, s: str) -> list:
        L, n = 10, len(s)

        to_int = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
        nums = [to_int.get(s[i]) for i in range(n)]

        bitmask = 0
        seen, output = set(), set()
        # 滑动窗口遍历次数
        for start in range(n - L + 1):
            if start != 0:
                bitmask <<= 2
                bitmask |= nums[start + L - 1]
                # bitmask &= ~(1 <

输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        if len(num) <= k:
            return "0"
        
        remain = len(num) - k
        for i in num:
            while k and stack and stack[-1] > i:
                stack.pop()
                k -= 1
            stack.append(i)

        return ''.join(stack[:remain]).lstrip('0') or '0'

输入：s = "bcabc"
输出："abc"

输入：s = "cbacdcbc"
输出："acdb"

class Solution:
    @classmethod
    def removeDuplicateLetters(self, s: str) -> str:
        from collections import Counter
        s_dic = Counter(s)
        stack = []
        for i in s:
            if i not in stack:
                while stack and stack[-1] > i and s_dic[stack[-1]] > 0:
                    stack.pop()
                stack.append(i)
            s_dic[i] -= 1
        return ''.join(stack)