leetcode 18. 四数之和 1394. 找出数组中的幸运数 957. N 天后的牢房 1292. 元素和小于等于阈值的正方形的最大边长

18. 四数之和

class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: result = set() nums.sort() for i in range(len(nums)-3): for j in range(i+1,len(nums)-2): left = j+1 right = len(nums)-1 while left<right: sum_four = nums[i]+nums[j]+nums[left]+nums[right] if sum_four>target: right-=1 elif sum_four<target: left+=1 else: result.add((nums[i],nums[j],nums[left],nums[right])) left+=1 right-=1 return [list(x) for x in result]

1394. 找出数组中的幸运数

class Solution: def findLucky(self, arr: List[int]) -> int: count = [0]*501 for i in arr: count[i]+=1 for i in range(500,0,-1): if count[i]==i: return i return -1

一个collections的Counter方法

from collections import Counter class Solution: def findLucky(self, arr: List[int]) -> int: count = Counter(arr) ans = -1 for k, v in count.items(): if k == v: ans = max(ans, k) return ans

957. N 天后的牢房

class Solution: def prisonAfterNDays(self, cells: List[int], N: int) -> List[int]: if N==0: return cells result = cells.copy() last_day = cells.copy() for j in range(1,7): result[j]=1 if (last_day[j-1]+last_day[j+1])%2==0 else 0 result[0]=result[7]=0 last_day=result.copy() first_day=result.copy() circle=-1 for i in range(2,N+1): for j in range(1,7): result[j]=1 if (last_day[j-1]+last_day[j+1])%2==0 else 0 last_day=result.copy() if last_day==first_day: circle=i-1 break print("循环：",circle,"天一次") if circle==-1: return result if N%circle==1: return first_day last_day=first_day.copy() for i in range(2,(N-1)%circle+2): for j in range(1,7): result[j]=1 if (last_day[j-1]+last_day[j+1])%2==0 else 0 last_day=result.copy() return result

1292. 元素和小于等于阈值的正方形的最大边长

超时

class Solution: def maxSideLength(self, mat: List[List[int]], threshold: int) -> int: currentsum = [[0]*len(mat[0]) for _ in range(len(mat))] maxlen=0 for edge in range(1,min(len(mat),len(mat[0]))+1): hasprob = False for i in range(len(mat)-edge+1): for j in range(len(mat[0])-edge+1): if currentsum[i][j]>threshold: continue col = sum([mat[x][j+edge-1] for x in range(i,i+edge-1)]) if edge>1 else 0 currentsum[i][j]+=sum(mat[i+edge-1][j:j+edge])+col if currentsum[i][j]<=threshold: hasprob = True maxlen=max(maxlen,edge) if not hasprob: break return maxlen

前缀加二分

class Solution: def maxSideLength(self, mat: List[List[int]], threshold: int) -> int: # 前缀加二分 dp = [[0] * (len(mat[0]) + 1) for _ in range(len(mat) + 1)] for i in range(len(mat)): for j in range(len(mat[0])): dp[i + 1][j + 1] = mat[i][j]+dp[i + 1][j] + dp[i][j + 1] - dp[i][j] result = 0 for i in range(1, len(mat) + 1): for j in range(1, len(mat[0]) + 1): start = 1 end = min(len(mat)-i+1, len(mat[0])-j+1) while start < end: middle = (start + end) // 2+1 area_middle = dp[i + middle-1][j + middle-1] - dp[i + middle-1][j-1] - dp[i-1][j + middle-1] + dp[i-1][j-1] if area_middle > threshold: end = middle-1 elif area_middle <= threshold: start = middle result = max(result, middle) return result