网站被抄袭怎么投诉,小程序云开发的弊端,wordpress添加html,我要做网店官网记录了初步解题思路 以及本地实现代码#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 2/24 1656. 设计有序流2/25 2502. 设计内存分配器2/26 1472. 设计浏览器历史记录2/27 2296. 设计一个文本编辑器2/28 2353. 设计食物评分系统3/1 131. 分割回文串3/2 132. …记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步 目录 2/24 1656. 设计有序流2/25 2502. 设计内存分配器2/26 1472. 设计浏览器历史记录2/27 2296. 设计一个文本编辑器2/28 2353. 设计食物评分系统3/1 131. 分割回文串3/2 132. 分割回文串 II 2/24 1656. 设计有序流 数组保存数据 插入数据后 检查指针节点是否可以往后移动 class OrderedStream(object):def __init__(self, n)::type n: intself.n nself.ptr 0self.l []*(n1)def insert(self, idKey, value)::type idKey: int:type value: str:rtype: List[str]ans []self.l[idKey] valuewhile self.ptrself.n and self.l[self.ptr1]!:ans.append(self.l[self.ptr1])self.ptr 1if self.ptrself.n:breakreturn ans 2/25 2502. 设计内存分配器 使用长度为n的数字 记录每个位置内存使用情况 class Allocator(object):def __init__(self, n)::type n: intself.nnself.mem[0]*ndef allocate(self, size, mID)::type size: int:type mID: int:rtype: intcnt 0for i in range(self.n):if self.mem[i]0:cnt0else:cnt1if cntsize:for j in range(i-cnt1,i1):self.mem[j]mIDreturn i-cnt1return -1def freeMemory(self, mID)::type mID: int:rtype: intcnt 0for i in range(self.n):if self.mem[i]mID:cnt1self.mem[i]0return cnt 2/26 1472. 设计浏览器历史记录 模拟 使用一个数组urls保存网页记录 cur指向当前访问的网页索引 class BrowserHistory(object):def __init__(self, homepage)::type homepage: strself.urls [homepage]self.cur 0def visit(self, url)::type url: str:rtype: Noneself.urls self.urls[:self.cur1]self.urls.append(url)self.cur1def back(self, steps)::type steps: int:rtype: strself.cur max(0,self.cur-steps)return self.urls[self.cur]def forward(self, steps)::type steps: int:rtype: strself.cur min(len(self.urls)-1,self.cursteps)return self.urls[self.cur] 2/27 2296. 设计一个文本编辑器 使用left,right两个栈分别存储光标左右的内容 add:将text压入left中 delete:从left中取出k个直至为空 cursorleft:将left中取出放入right中 cursorright:将right中取出放入left中 class TextEditor(object):def __init__(self):self.left[]self.right[]def addText(self, text)::type text: str:rtype: Noneself.left.extend(text)def deleteText(self, k)::type k: int:rtype: intcntmin(k,len(self.left))del self.left[-cnt:]return cntdef cursorLeft(self, k)::type k: int:rtype: strfor _ in range(min(k,len(self.left))):self.right.append(self.left.pop())return .join(self.left[-10:])def cursorRight(self, k)::type k: int:rtype: strfor _ in range(min(k,len(self.right))):self.left.append(self.right.pop())return .join(self.left[-10:]) 2/28 2353. 设计食物评分系统 foodmap维护food对应的分数和烹饪方法 ratemap[cuisines] 使用最小堆维护同一烹饪方法中的分数 用负数变为最大堆 import heapq
class FoodRatings(object):def __init__(self, foods, cuisines, ratings)::type foods: List[str]:type cuisines: List[str]:type ratings: List[int]self.food{}self.rate{}self.nlen(foods)for i in range(self.n):f foods[i]c cuisines[i]r ratings[i]self.food[f](c,r)if c not in self.rate:self.rate[c][]heapq.heappush(self.rate[c], (-r,f))def changeRating(self, food, newRating)::type food: str:type newRating: int:rtype: Nonec,r self.food[food]heapq.heappush(self.rate[c], (-newRating,food))self.food[food](c,newRating)def highestRated(self, cuisine)::type cuisine: str:rtype: strwhile self.rate[cuisine]:r,f self.rate[cuisine][0]if -r self.food[f][1]:return fheapq.heappop(self.rate[cuisine])return 3/1 131. 分割回文串 check检查字符串l是否回文 pdic存放pos开头所有回文的子串 def partition(s)::type s: str:rtype: List[List[str]]def check(l):t Trueif len(l)0:return twhile t and len(l)1:if l[0]l[-1]:l.pop(0)l.pop(-1)else:t Falseif len(l)1:return Falseelse:return Trueret []if len(s)0:return retl list(s) dic {}for i in range(len(l)):begin l[i]for j in range(len(l)-1,i-1,-1):if begin l[j]:if check(l[i:j1]):dic[(i,j)] l[i:j1]pdic {}for i in dic:pos i[0]tmp pdic.get(pos,[])tmp.append(i)pdic[pos] tmpdef combine(begin):ret []va pdic[begin]for v in va:end v[1]if end (len(s)-1):ret.append([v])else:l combine(end1)for t in l:t.insert(0,v)ret.extend(l) return retr combine(0)for v in r:tmp []for i in v:tmp.append(.join(dic[i]))ret.append(tmp)return ret 3/2 132. 分割回文串 II m[i][j]true表示[i,j]为回文串 dp[i]记录0~i最少分割切几次 def minCut(s)::type s: str:rtype: intn len(s)##预处理 判断i,j是否为回文串m [[True]*n for _ in range(n)] for i in range(n-1,-1,-1):for j in range(i1,n):m[i][j] (s[i]s[j]) and m[i1][j-1]dp [float(inf)] * nfor i in range(n):if m[0][i]: ##如果0-i为回文串 不需要切割dp[i]0else:for j in range(i):if m[j1][i]:dp[i] min(dp[i],dp[j]1)return dp[n-1]
