# 解法2 class Solution: def maximumDifference(self, nums: List[int]) - int: # 维护前缀最小值 min_num nums[0] ans -1 for i in range(1, len(nums)): if min_num nums[i]: ans max(ans, nums[i] - min_num) else: min_num nums[i] return ans5882. 网格游戏
仔细看题目 这里求的不是机器人一什么时候取的点数最大值 而是机器人一怎么走 使得机器人二取得点数最小值
1. 思路 多观察题目给的条件 只有两行 机器人只能往下走或往右走 并且还是求和操作。对一个数组沿同一个方向求和 自然而然应该想到前缀和。这里求的是机器人二的得分 所以对数组第一行求后缀和 第二行求前缀和。后缀和的求法就是通过求整行的前缀和 再不断减去遍历到的数。 2. Python3代码class Solution: def gridGame(self, grid: List[List[int]]) - int: # 这里注意一下下标的位置 n len(grid[0]) r1 sum(grid[0]) - grid[0][0] r2 0 ans r1 for i in range(1, n): r1 - grid[0][i] r2 grid[1][i-1] ans min(ans, max(r1, r2)) return ans5883. 判断单词是否能放入填字游戏内 1. 思路 模拟对每个格子都尝试横竖放一遍 同时把字母翻转放一遍 即遍历四次。 2. Python3代码
class Solution: def placeWordInCrossword(self, board: List[List[str]], word: str) - bool: n, m len(board), len(board[0]) length len(word) def is_placed_in_row(i, j, idx, target, direction): while j m and board[i][j] ! # : if board[i][j] or board[i][j] word[idx]: idx direction else: break if idx target: if j 1 m or board[i][j 1] # : return True else: break return False def is_placed_in_col(i, j, idx, target, direction): while i n and board[i][j] ! # : if board[i][j] or board[i][j] word[idx]: idx direction else: break if idx target: if i 1 n or board[i 1][j] # : return True else: break return False for i in range(n): for j in range(m): # 每个空格或存在字母的格子都尝试横竖放置 if board[i][j] ! # : # 尝试横着放 if j 0 or board[i][j-1] # : if is_placed_in_row(i, j, 0, length, 1) or is_placed_in_row(i, j, length-1, -1, -1): return True # 尝试竖着放 if i 0 or board[i-1][j] # : if is_placed_in_col(i, j, 0, length, 1) or is_placed_in_col(i, j, length-1, -1, -1): return True return False5884. 解出数学表达式的学生分数 1. 思路 区间DP 2. Python3代码
# 别人题解的答案 比较好理解的。 class Solution(object): def scoreOfStudents(self, s, answers): :type s: str :type answers: List[int] :rtype: int n len(s) # 表达式长度 # 计算正确答案 stack [int(s[0])] for i in range(1,n,2): if s[i] * : pre stack.pop() stack.append(pre*int(s[i 1])) else: stack.append(int(s[i 1])) true_ans sum(stack) # 表达式中包含的数字数量 size (n 1)//2 # 状态空间 dp[i][j] 表示第i个数字-第j个数字 包含首位 的表达式的可能取值 dp [[set() for _ in range(size)] for _ in range(size)] for i in range(size): dp[i][i] [int(s[2*i])] for k in range(2,size 1): # 区间长度 k: 取值 [2,size] size 1于上文已经考虑 for i in range(size-k 1): # 区间开始位置 i, 对应区间 [i,i k-1]; i 取值范围 [0,(size-k)] for j in range(i,i k-1): # 区间分割点j ,将区间分割为 [i,j]和[j 1,i k-1] j取值为 [i,i k-2] lst1 dp[i][j] #区间1可能取值 lst2 dp[j 1][i k-1] #区间2可能取值 for e1 in lst1: for e2 in lst2: if s[2*j 1] and e1 e2 1000: dp[i][i k-1].add(e1 e2) elif s[2*j 1] * and e1*e2 1000: dp[i][i k-1].add(e1*e2) # 分数计算 dic defaultdict(int) res 0 for ans in answers: if ans true_ans: res 5 else: dic[ans] 1 for k,v in dic.items(): if k in dp[0][size-1]: res 2*v return res
