LeetCode 每日一题 2022/10/31-2022/11/6

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

---

10/31 481. 神奇字符串

起始1,2,2
l记录个数的位置 r记录已经依次添加的最新位置

def magicalString(n):
    """
    :type n: int
    :rtype: int
    """
    if n<4:
        return 1
    s = [0]*n
    s[:3] = [1,2,2]
    ans = 1
    l,r = 2,3
    while r<n:
        size = s[l]
        num = 3-s[r-1]
        while size and r<n:
            s[r] = num
            if num==1:
                ans +=1
            r+=1
            size-=1
        l+=1
    return ans


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

11/1 1662. 检查两个字符串数组是否相等

拼接后比较

def arrayStringsAreEqual(word1, word2):
    """
    :type word1: List[str]
    :type word2: List[str]
    :rtype: bool
    """
    return ''.join(word1)==''.join(word2)


1
2
3
4
5
6
7
8
9

---

11/2 1620. 网络信号最好的坐标

找到信号塔最大范围xmax,ymax 信号最大必定在这个范围内
遍历范围内一个点 计算每个塔对这个点的信号贡献
记录最大值

def bestCoordinate(towers, radius):
    """
    :type towers: List[List[int]]
    :type radius: int
    :rtype: List[int]
    """
    xmax = max(t[0] for t in towers)
    ymax = max(t[1] for t in towers)
    cx,cy = 0,0
    maxq = -1
    for x in range(xmax+1):
        for y in range(ymax+1):
            cq = 0
            for tx,ty,q in towers:
                d = (x-tx)**2+(y-ty)**2
                if d<=radius**2:
                    cq+=int(q/(1+d**0.5))
            if cq>maxq:
                cx,cy,maxq=x,y,cq
    return [cx,cy]


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

11/3 1668. 最大重复子字符串

dp[i]记录以i为结尾 前面最多有几个连续的word
对于i位置 一一比较前面是否是一个word
如果是则当前dp[i] = dp[i-m]+1

def maxRepeating(sequence, word):
        """
        :type sequence: str
        :type word: str
        :rtype: int
        """
        n,m = len(sequence),len(word)
        if n<m:
            return 0
        ans = 0
        dp = [0]*n
        for i in range(m-1,n):
            tag = True
            for j in range(m):
                if sequence[i-m+j+1]!=word[j]:
                    tag = False
                    break
            if tag:
                if i==m-1:
                    dp[i]=1
                else:
                    dp[i] = dp[i-m]+1
            ans = max(ans,dp[i])
        return ans


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

---

11/4 754. 到达终点数字

target正负无所谓 只考虑正数情况
此时只要朝着一个方向不停的靠近target就可以
假设走了k步 到达或者超过了target 及sum(1,2,3,…,k)>=abs(target)
如果等于 则答案即为k
如果超过 需要分情况考虑超过部分 d=abs(target-sum(1,2,…,k)) d 如果d是个偶数 则只要在过程中将d/2的那一步朝反方向走 结果就可以减少d 到达target 此时也只要k步
如果d是个奇数 又要分两种情况
如果k是个偶数
我们继续向前走k+1 此时差距为k+1+d 是个偶数 可以在将(k+1+d)/2 朝反方向走 答案为k+1步
如果k是个奇数 此时差距k+1+d是个奇数 无法通过改变一步来减少
所以需要再走一步k+2 才可以使得差距为偶数 改变里面若干步使得差为0

def reachNumber(target):
        """
        :type target: int
        :rtype: int
        """
        target = abs(target)
        k = 0
        while target > 0:
            k += 1
            target -= k
        return k if target % 2 == 0 else k + 1 + k % 2


1
2
3
4
5
6
7
8
9
10
11
12
13

---

11/5 1106. 解析布尔表达式

栈 从左到右遍历表达式 分情况处理
如果是逗号 跳过
如果是除了逗号和右括号以外的 则压入栈中
如果是右括号 则表达式结束 将栈内字符 弹出一直到左括号 记录期间t,f个数
接着弹出左括号 和 前一个运算符
根据运算符 得到结果压入栈中
最后返回栈中结果

def parseBoolExpr(expression):
    """
    :type expression: str
    :rtype: bool
    """
    stack = []
    for c in expression:
        if c==',':
            continue
        if c!=')':
            stack.append(c)
            continue
        t,f = 0,0
        while stack[-1]!='(':
            if stack.pop()=='t':
                t+=1
            else:
                f+=1
        stack.pop()
        op = stack.pop()
        if op=='!':
            if t==1:
                stack.append('f')
            else:
                stack.append('t')
        elif op=='&':
            if f==0:
                stack.append('t')
            else:
                stack.append('f')
        else:
            if t>0:
                stack.append('t')
            else:
                stack.append('f')
    return stack[-1]=='t'


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

---

11/6 1678. 设计 Goal 解析器

依序遍历 分别对应不同情况

def interpret(command):
        """
        :type command: str
        :rtype: str
        """
        ans = ""
        loc = 0
        while loc<len(command):
            if command[loc]=="G":
                ans += "G"
                loc +=1
            elif command[loc+1]==")":
                ans +="o"
                loc +=2
            else:
                ans +="al"
                loc +=4
        return ans


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---