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])**2
    n = 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 defaultdict
    ans = 0
    for i in range(n):
        m = defaultdict(int)
        for j in range(n):
            m[matrix[i][j]]+=1
        
        for 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]=0
    m = {}
    for d in dictionary:
        m[d] =1
    for i in range(1,n+1):
        dp[i] = dp[i-1]+1
        for 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 = 0
    for w in word:
        if w=="a":
            if cur=="a":
                ans+=2
            elif cur=="b":
                ans+=1
            cur = w
        elif w=="b":
            if cur=="":
                ans +=1
            elif cur=="b":
                ans+=2
            cur = w
        else:
            if cur=="a":
                ans+=1
            elif cur=="":
                ans+=2
            cur=""
    if cur=="a":
        ans+=2
    elif cur=="b":
        ans+=1
    return ans

---

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

map统计字符串出现次数

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

---

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

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

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

---

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

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

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def deleteDuplicates(head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    top = ListNode(0)
    pre = top
    cur = head
    while cur:
        while cur.next and cur.val==cur.next.val:
            cur = cur.next
        pre.next = cur
        pre = cur
        cur = cur.next
    return top.next

---