武汉做便宜网站中国旺旺(00151) 股吧

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

---

2/13 1234. 替换子串得到平衡字符串

对于剩余子串 只要所有字符出现次数少于等于s/4即可
待替换字符串使用滑动窗口l,r 从小到大枚举所有l
为了使[l,r]最小 需要找到最近的r

def balancedString(s):""":type s: str:rtype: int"""from collections import Countercnt = Counter(s)ave = len(s)//4def check():if cnt['Q']>ave or cnt['W']>ave or cnt['E']>ave or cnt['R']>ave:return Falsereturn Trueif check():return 0ans = len(s)r = 0for l,c in enumerate(s):while r<len(s) and not check():cnt[s[r]]-=1r+=1if not check():breakans = min(ans,r-l)cnt[c]+=1return ans

---

2/14 1124. 表现良好的最长时间段

大于8为1 小于等于8为-1
要求将某一段时间和大于0
前缀和 并用哈希表记录某一值第一次出现的位置

def longestWPI(hours):""":type hours: List[int]:rtype: int"""cur = 0ans = 0m = {}for i,h in enumerate(hours):if h>8:cur+=1else:cur-=1if cur>0:ans = max(ans,i+1)else:if cur-1 in m:ans = max(ans,i-m[cur-1])if cur not in m:m[cur]=ireturn ans

---

2/15 1250. 检查「好数组」

只要两个数i,j最大公约数为1 可以得到ix-jy=1
只要数组内最大公约数为1既满足

def isGoodArray(nums):""":type nums: List[int]:rtype: bool"""from functools import reducefrom math import gcdreturn reduce(gcd,nums)==1

---

2/16 2341. 数组能形成多少数对

遍历统计每个数出现次数

def numberOfPairs(nums):""":type nums: List[int]:rtype: List[int]"""m={}for num in nums:m[num] = m.get(num,0)+1a,b = 0,0for v in m.values():a += v//2b += v%2return [a,b]

---

2/17 1139. 最大的以 1 为边界的正方形

row,col分别记录行、列的前缀和
前缀和相减即可得到某行某列一段长度是否都为1
ans记录当前能够满足的最大边长
遍历每一个点从ans长度开始判断是否满足
判断四条边总和是否等于当前判断的长度cur
无论是否可以 不断增大直到无法满足

def largest1BorderedSquare(grid):""":type grid: List[List[int]]:rtype: int"""ans = 0m,n = len(grid),len(grid[0])row,col  = [[0]*(n+1) for _ in range(m)],[[0]*n for _ in range(m+1)]for i in range(m):for j in range(n):row[i][j+1] = row[i][j]+grid[i][j]for j in range(n):for i in range(m):col[i+1][j] = col[i][j]+grid[i][j]for i in range(m):for j in range(n):if grid[i][j]==1:cur = answhile i+cur<m and j+cur<n:if row[i][j+cur+1]-row[i][j]!=cur+1:cur+=1continueif col[i+cur+1][j]-col[i][j]!=cur+1:cur+=1continueif row[i+cur][j+cur+1]-row[i+cur][j]!=cur+1:cur+=1continueif col[i+cur+1][j+cur]-col[i][j+cur]!=cur+1:cur+=1continuecur+=1ans = curreturn ans*ans

---

2/18 1237. 找出给定方程的正整数解

已知函数根据x,y都是单调递增的
如果f(x1,y1)=f(x2,y2)=z
x1<x2 则一定有y1>y2
可以从小到大遍历x 从大到小遍历y

def findSolution(customfunction, z):""":type num: int:type z: int:rtype: List[List[int]]"""ans = []y = 1000for x in range(1,1001):while y>0 and customfunction.f(x,y)>z:y-=1if y==0:breakif customfunction.f(x,y)==z:ans.append([x,y])return ans

---

2/19

---