11.11 41. 132模式
给定一个整数序列：a1, a2, ..., an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。
输入: [-1, 3, 2, 0]
输出: True
解释: 序列中有 3 个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].
最优解
public class Solution {
public boolean find132pattern(int[] nums) {
if (nums.length < 3)
return false;
Stack < Integer > stack = new Stack < > ();
int[] min = new int[nums.length];
min[0] = nums[0];
// min数组记录每个索引位置最小的元素
for (int i = 1; i < nums.length; i++)
min[i] = Math.min(min[i - 1], nums[i]);
for (int j = nums.length - 1; j >= 0; j--) {
// 如果原数组j大于min[j],stack栈顶元素小于
if (nums[j] > min[j]) {
while (!stack.isEmpty() && stack.peek() <= min[j])
stack.pop();
if (!stack.isEmpty() && stack.peek() < nums[j])
return true;
stack.push(nums[j]);
}
}
return false;
}
}
def one_three_two(nums):
if len(nums) < 3:
return False
stack = []
min_li = [9999999]*len(nums)
min_li[0] = nums[0]
for i in range(1, len(nums)):
min_li[i] = min(min_li[i - 1], nums[i])
for j in range(len(nums) - 1, -1, -1):
if nums[j] > min_li[j]:
while stack and stack[-1] <= min_li[j]:
stack.pop()
if stack and stack[-1] < nums[j]:
return True
stack.append(nums[j])
return False
总结：
动画演示，用一个栈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 < rows and r >= 0) and (c < cols 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 < rows and r >= 0) and (c < cols 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 << n) 是将 bitmask 第 n 位设置为 0。
# 前两位置0
bitmask &= ~(3 << 2 * L)
else:
# 初始化前10个字母
for i in range(L):
bitmask <<= 2
bitmask |= nums[i]
if bitmask in seen:
output.add(s[start:start+L])
seen.add(bitmask)
return list(output)
总结
按位翻转记住 补反原还。计算机中负数的计算要取补码计算。
11.16 44. 移掉k位数字
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:
num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。
输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。
思路
- 移除所有数字为0
- 前置0肯定比其他情况小
- 如果高位从大到小顺序移除，如果从小到大移除后面的。
- 前n位移除最小的m位，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'
总结
体会为什么要从保留remian位来解决此题。正向要排除的情况比较多可以从反向来思考。
11.17 45. 去除重复字母
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
输入：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)
总结
此题关键在于什么时机 stack可以pop元素。