最优做网站/网课培训机构排名前十

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

---

5/9 942. 增减字符串匹配

如果s[i]=I 那么假设perm[i]=最小值 min(nums)
此时无论i+1取何值 必定满足perm[i]<perm[i+1]
同理如果s[i]=D perm[i] = max(nums)

def diStringMatch(s):""":type s: str:rtype: List[int]"""n = len(s)l = [0]*(n+1)minv = 0maxv = nfor loc,c in enumerate(s):if c=="I":l[loc] = minvminv+=1else:l[loc] = maxvmaxv-=1l[n] = minvreturn l

---

5/10 1728. 猫和老鼠 II

没想出来
缓存lru_cache
参考https://leetcode.cn/problems/cat-and-mouse-ii/solution/python-ji-xiao-ji-da-bo-yi-by-himymben-ukbk/

def canMouseWin(grid, catJump, mouseJump):""":type grid: List[str]:type catJump: int:type mouseJump: int:rtype: bool"""move = [(0,1),(0,-1),(-1,0),(1,0)]n,m = len(grid),len(grid[0])for i in range(n):for j in range(m):if grid[i][j]=="C":cat = (i,j)elif grid[i][j] =="F":food = (i,j)elif grid[i][j] == "M":mouse = (i,j)@lru_cache(None)def dfs(mloc,cloc,i):if mloc==cloc or cloc==food or i>128:return Falseif mloc == food:return Truepos,jump = mloc,mouseJumpcat_turn = Falseif i%2:pos,jump = cloc,catJumpcat_turn = Truefor dx,dy in move:for step in range(jump+1):nx,ny = pos[0]+dx*step,pos[1]+dy*stepif nx<0 or ny<0 or nx>=n or ny>=m or grid[nx][ny]=="#":breakif not cat_turn and dfs((nx,ny),cloc,i+1):return Trueelif cat_turn and not dfs(mloc,(nx,ny),i+1):return Falsereturn cat_turnreturn dfs(mouse,cat,0)

---

5/11 449. 序列化和反序列化二叉搜索树

后序遍历

class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Codec:def serialize(self, root: TreeNode) -> str:"""Encodes a tree to a single string."""ans = []def find(node):if node:find(node.left)find(node.right)ans.append(node.val)find(root)return " ".join(map(str,ans))def deserialize(self, data: str) -> TreeNode:"""Decodes your encoded data to tree."""l = list(map(int,data.split()))def build(minv,maxv):if l==[] or l[-1]<minv or l[-1]>maxv:return Noneval = l.pop()node = TreeNode(val)node.right = build(val,maxv)node.left = build(minv,val)return nodereturn build(-1,10001)

---

5/12 944. 删列造序

依次比较 每个字符串有n个字符
从第1位开始 比较每一个字符串该位置是否升序

def minDeletionSize(strs):""":type strs: List[str]:rtype: int"""n = len(strs[0])ans = 0if len(strs)==0:return ansfor i in range(n):cur = strs[0][i]for c in strs[1:]:if c[i]<cur:ans +=1breakcur = c[i]return ans

---

5/13 面试题 01.05. 一次编辑

两个字符串长度差不能大于1
如果长度相同 记录不同字符的次数 不能大于1
如果长度不同 从头比较 遇到不同的 长字符串跳过 继续比较

def oneEditAway(first, second):""":type first: str:type second: str:rtype: bool"""if first==second:return Truen = len(first)m = len(second)if abs(n-m)>1:return Falseif n>m:first,second=second,firstn,m=m,nif n<m:i,j=0,0check = Truewhile j<m:if i==n:return Trueif first[i]!=second[j]:if check:j+=1check = Falseelse:return Falseelse:i+=1j+=1return Trueelse:diff=[]for i in range(n):if first[i]!=second[i]:if len(diff)==1:return Falsediff.append(i)if len(diff)<2:return Truereturn False

---

5/14 691. 贴纸拼词

target最多15位 用一个15位的二进制mask用来标识target的子序列
首先判断target是否包含sticker中没有的字母 如果有则返回-1
mem[mask]记录以判断过得子序列最优解
dfs判断mask的最优解
遍历每一个sticker left为mask去除sticker内字符后的子序列

def minStickers(stickers, target):""":type stickers: List[str]:type target: str:rtype: int"""from collections import defaultdictn = len(target)has = 0for s in stickers:for c in s:has |= 1<<(ord(c)-ord("a"))for c in target:if has&(1<<(ord(c)-ord("a")))==0:return -1mem = {}mem[0] = 0def find(mask):if mask in mem:return mem[mask]ans = n+1for s in stickers:left = maskm = defaultdict(int)for c in s:m[c]+=1for i,c in enumerate(target):if mask>>i &1 and m[c]:m[c]-=1left ^= 1<<iif left<mask:ans = min(ans,find(left)+1)mem[mask] = ansreturn ansans = find((1<<n)-1)return ans

---

5/15 812. 最大三角形面积

海伦公式 三角形三条边a,b,c
面积= 根号(p(p-a)(p-b)(p-c)) p=(a+b+c)/2
点的个数小于等于50 三重循环遍历
小数有误差判断一下 在同一条直线 tmp<0情况

def largestTriangleArea(points):""":type points: List[List[int]]:rtype: float"""import mathdef findlen(a,b):return math.sqrt(math.pow(a[0]-b[0],2)+math.pow(a[1]-b[1],2))cur = 0n = len(points)for i in range(n):for j in range(i+1,n):for k in range(j+1,n):a = findlen(points[i],points[j])b = findlen(points[i],points[k])c = findlen(points[k],points[j])p = (a+b+c)*0.5tmp = p*(p-a)*(p-b)*(p-c)if tmp<0:continues = (p*(p-a)*(p-b)*(p-c))**0.5cur = max(cur,s)return cur

---