LeetCode 每日一题 2024/1/8-2024/1/14

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

1/8 447. 回旋镖的数量

matrix[i][j] 记录点i 点j之间的距离
遍历每一个点 相同距离的点个数
计算

def numberOfBoomerangs(points):""":type points: List[List[int]]:rtype: int"""def dist(x,y):return (y[1]-x[1])**2+(y[0]-x[0])**2n = len(points)matrix = [[0]*n for _ in range(n)]for i in range(n):for j in range(n):matrix[i][j] = dist(points[i],points[j])from collections import defaultdictans = 0for i in range(n):m = defaultdict(int)for j in range(n):m[matrix[i][j]]+=1for k,v in m.items():if v>1:ans += v*(v-1)return ans

1/9 2707. 字符串中的额外字符

dp[i]表示s[:i]额外字符个数
首先将s[i]认为是额外字符 初始化dp[i]=dp[i-1]+1
再判断s[j:i]是否在字典中 如果在 则dp[i]=min(dp[j],dp[i])
map用来判断字符串是否在字典中

def minExtraChar(s, dictionary):""":type s: str:type dictionary: List[str]:rtype: int"""n=len(s)dp = [float("inf")]*(n+1)dp[0]=0m = {}for d in dictionary:m[d] =1for i in range(1,n+1):dp[i] = dp[i-1]+1for j in range(i-1,-1,-1):if s[j:i] in m:dp[i] = min(dp[j],dp[i])return dp[n]

1/10 2696. 删除子串后的字符串最小长度

栈 将字母放入栈中 判断栈顶两个字符

def minLength(s):""":type s: str:rtype: int"""st = []for c in s:st.append(c)if len(st)>=2 and (''.join(st[-2:])=="AB" or ''.join(st[-2:])=="CD"):st.pop()st.pop()return len(st)

1/11 2645. 构造有效字符串的最少插入数

从头遍历 记录当前状态

def addMinimum(word):""":type word: str:rtype: int"""cur = ""ans = 0for w in word:if w=="a":if cur=="a":ans+=2elif cur=="b":ans+=1cur = welif w=="b":if cur=="":ans +=1elif cur=="b":ans+=2cur = welse:if cur=="a":ans+=1elif cur=="":ans+=2cur=""if cur=="a":ans+=2elif cur=="b":ans+=1return ans

1/12 2085. 统计出现过一次的公共字符串

map统计字符串出现次数

def countWords(words1, words2):""":type words1: List[str]:type words2: List[str]:rtype: int"""ans = 0m1,m2={},{}for w in words1:m1[w]=m1.get(w,0)+1for w in words2:m2[w]=m2.get(w,0)+1for k,v in m1.items():if v!=1:continueif m2.get(k,0)==1:ans+=1return ans

1/13 2182. 构造限制重复的字符串

选择字典序最高的字符加入 如果超过次数
则加一个次高的字符然后继续换成最大字符加入

def repeatLimitedString(s, repeatLimit):""":type s: str:type repeatLimit: int:rtype: str"""cnt = [0]*26for c in s:cnt[ord(c)-ord('a')]+=1ret=[]i,j,cur = 25,24,0while i>=0 and j>=0:if cnt[i]==0:i-=1cur=0elif cur<repeatLimit:cnt[i]-=1cur+=1ret.append(chr(ord('a')+i))elif j>=i or cnt[j]==0:j-=1else:cnt[j]-=1cur=0ret.append(chr(ord('a')+j))return ''.join(ret)

1/14 83. 删除排序链表中的重复元素

已排序 从头到尾判断
如果相同跳过

class ListNode(object):def __init__(self, val=0, next=None):self.val = valself.next = next
def deleteDuplicates(head):""":type head: ListNode:rtype: ListNode"""top = ListNode(0)pre = topcur = headwhile cur:while cur.next and cur.val==cur.next.val:cur = cur.nextpre.next = curpre = curcur = cur.nextreturn top.next