2397. 被列覆盖的最多行数
回溯法,未剪枝
import copy
from typing import List
class Solution:
def maximumRows(self, matrix: List[List[int]], numSelect: int) -> int:
info: List[List[int]] = [[] for i in range(len(matrix))]
for i in range(len(matrix)):
for j in range(len(matrix[i])):
if matrix[i][j] == 1:
info[i].append(j)
return self.recursion(info, set(), 0, numSelect, 0)
def recursion(self, info: List[List[int]], selected: set, index: int, able_select: int, max_row):
# 不选当前行
max_row_without_select = max_row
for i in range(index + 1, len(info)):
max_row_without_select = max(
self.recursion(info, copy.deepcopy(selected), i, able_select, max_row),
max_row_without_select)
# 选择当前行
for i in range(len(info[index])):
if info[index][i] in selected:
continue
able_select -= 1
selected.add(info[index][i])
max_row_with_select = max_row
if able_select >= 0:
max_row_with_select += 1
for i in range(index + 1, len(info)):
max_row_with_select = max(
self.recursion(info, copy.deepcopy(selected), i, able_select, max_row + 1),
max_row_with_select)
# print(index, max(max_row_with_select, max_row_without_select))
return max(max_row_with_select, max_row_without_select)
383. 赎金信
from collections import Counter
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
c = Counter(magazine)
for char in ransomNote:
c[char] -= 1
if c[char] < 0:
return False
return True
876. 链表的中间结点
快慢指针
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
p0 = head
p1 = head
while p1.next:
for i in range(2):
if p1.next:
p1 = p1.next
else:
break
p0 = p0.next
return p0
581. 最短无序连续子数组
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
new_nums = nums[:]
new_nums.sort()
start = None
for i in range(len(nums)):
if new_nums[i] != nums[i]:
start = i
break
end = None
for i in range(len(nums) - 1, -1, -1):
if new_nums[i] != nums[i]:
end = i
break
if start is None and end is None:
return 0
return end - start + 1
Comments | NOTHING