5255. 奇数值单元格的数目
给你一个 n 行 m 列的矩阵，最开始的时候，每个单元格中的值都是 0。
另有一个索引数组 indices，indices[i] = [ri, ci] 中的 ri 和 ci 分别表示指定的行和列（从 0 开始编号）。
你需要将每对 [ri, ci] 指定的行和列上的所有单元格的值加 1。
请你在执行完所有 indices 指定的增量操作后，返回矩阵中 「奇数值单元格」 的数目。
提示：
1 <= n <= 501 <= m <= 501 <= indices.length <= 1000 <= indices[i][0] < n-
0 <= indices[i][1] < m因为范围比较小，暴力搜索或者按行列统计都是可以的
class Solution(object): def oddCells(self, n, m, indices): """ :type n: int :type m: int :type indices: List[List[int]] :rtype: int """ cntn = [0]*n cntm = [0]*m for arr in indices: cntn[arr[0]] += 1 cntm[arr[1]] += 1 ans = 0 for i in range(n): for j in range(m): ans += (cntn[i]+cntm[j])&1 return ans
5256. 重构 2 行二进制矩阵
给你一个 2 行 n 列的二进制数组：
- 矩阵是一个二进制矩阵，这意味着矩阵中的每个元素不是
0就是1。 - 第
0行的元素之和为upper。 - 第
1行的元素之和为lower。 - 第
i列（从0开始编号）的元素之和为colsum[i]，colsum是一个长度为n的整数数组。
你需要利用 upper，lower 和 colsum 来重构这个矩阵，并以二维整数数组的形式返回它。
如果有多个不同的答案，那么任意一个都可以通过本题。
如果不存在符合要求的答案，就请返回一个空的二维数组。
贪心问题，首先选择2进行填充答案数组，再逐个添加1 如果不足就返回空
class Solution(object):
def reconstructMatrix(self, upper, lower, colsum):
"""
:type upper: int
:type lower: int
:type colsum: List[int]
:rtype: List[List[int]]
"""
length = len(colsum)
ansu = [0]*length
ansv = [0]*length
for k,v in enumerate(colsum):
if v == 2:
upper -= 1
lower -= 1
ansu[k] = ansv[k] = 1
colsum[k] = 0
for k,v in enumerate(colsum):
if v==1:
if upper>0:
upper -= 1
ansu[k] = 1
elif lower>0:
lower -= 1
ansv[k] = 1
else:
return []
if upper == 0 and lower == 0:
return [ansu,ansv]
else:
return []
5257. 统计封闭岛屿的数目
有一个二维矩阵 grid ，每个位置要么是陆地（记号为 0 ）要么是水域（记号为 1 ）。
我们从一块陆地出发，每次可以往上下左右 4 个方向相邻区域走，能走到的所有陆地区域，我们将其称为一座「岛屿」。
如果一座岛屿 完全 由水域包围，即陆地边缘上下左右所有相邻区域都是水域，那么我们将其称为 「封闭岛屿」。
请返回封闭岛屿的数目。
直接dfs每个区域，被1包围的就是答案
class Solution(object):
def closedIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
n = len(grid)
m = len(grid[0])
dirs = [[1,0],[-1,0],[0,1],[0,-1]]
def dfs(x,y):
if x<0 or x>=n or y<0 or y>=m:
return False
if grid[x][y] == 1:
return True
grid[x][y] = 1
ans = True
for nowdir in dirs:
tmpx = x + nowdir[0]
tmpy = y + nowdir[1]
if not dfs(tmpx,tmpy):
ans = False
return ans
ans = 0
for i,arr in enumerate(grid):
for j,v in enumerate(arr):
if v == 0:
ans += dfs(i,j)
return ans
5258. 得分最高的单词集合
你将会得到一份单词表 words，一个字母表 letters （可能会有重复字母），以及每个字母对应的得分情况表 score。
请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」：能够由 letters 里的字母拼写出的 任意 属于 words 单词子集中，分数最高的单词集合的得分。
单词拼写游戏的规则概述如下：
- 玩家需要用字母表
letters里的字母来拼写单词表words中的单词。 - 可以只使用字母表
letters中的部分字母，但是每个字母最多被使用一次。 - 单词表
words中每个单词只能计分（使用）一次。 - 根据字母得分情况表
score，字母'a','b','c', ... ,'z'对应的得分分别为score[0],score[1], ...,score[25]。 - 本场游戏的「得分」是指：玩家所拼写出的单词集合里包含的所有字母的得分之和。
提示：
1 <= words.length <= 141 <= words[i].length <= 151 <= letters.length <= 100letters[i].length == 1score.length == 260 <= score[i] <= 10-
words[i]和letters[i]只包含小写的英文字母。入手点，words的长度决定答案集合不会太大。
可以正向数位dp，每次筛选答案。也可以用字典存储状态进行递推
class Solution(object): def maxScoreWords(self, words, letters, score): """ :type words: List[str] :type letters: List[str] :type score: List[int] :rtype: int """ dp = {} for i in letters: dp[i] = dp.get(i,0)+1 def check(now , word): ans = {} for i in word: ans[i] = ans.get(i,0)+1 tmp = True tmpans = {} for k,v in ans.items(): if now.get(k,0)<v: tmp = False for k,v in now.items(): tmpans[k] = v if tmp: cnt = 0 for k,v in ans.items(): tmpans[k] -= v cnt += score[ord(k)-ord('a')]*v return cnt,tmpans else: return 0,tmpans pre = [[0,dp]] now = [] for word in words: for arr in pre: cnt,tmpans = check(arr[1],word) if cnt: now.append([cnt+arr[0],tmpans]) now = now + pre pre = now now = [] ans = 0 for arr in pre: ans = max(arr[0],ans) return ans
下次还是拿个编辑器（或者集成开发环境）写，在网页上写太伤了
