LeetCode 每日一题 2022/8/8-2022/8/14

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

8/8 761. 特殊的二进制序列

递归
对于一个特殊二进制序列
开头必定为1 结尾必定是0
因为性质一序列内1,0数量相等 如果结尾为1 则不满足性质二
去掉开头结尾 可以在内部考虑是否由多个特殊序列组成
按降序排序

def makeLargestSpecial(s):
    """
    :type s: str
    :rtype: str
    """
    def check(s):
        if len(s)<=2:
            return s
        left,num = 0,0
        l = []
        for i,c in enumerate(s):
            if c=="1":
                num+=1
            else:
                num-=1
                if num==0:
                    tmp = check(s[left+1:i])
                    l.append("1"+tmp+"0")
                    left = i+1
        l.sort(reverse=True)
        return "".join(l)
    return check(s)


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

8/9 1413. 逐步求和得到正数的最小值

根据题意从头到尾累加 得到最小的负数
如果最小数为正数 则startvalue为1即可

def minStartValue(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    ans = 0
    cur = 0
    for num in nums:
        cur += num
        ans = min(ans,cur)
    return  -min(0,ans)+1


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

8/10 640. 求解方程

将所有移到左边
x记录未知数前的参数
value记录常数值
cur记录当前数值
isx记录是否是未知数
left标记是在等号左侧1 还是右侧-1
最后根据x值和常数值得到未知数的值

def solveEquation(equation):
    """
    :type equation: str
    :rtype: str
    """
    x = 0
    left = 1
    cur = float("-inf")
    isx = False
    value = 0
    add = 1
    equation +="+"
    for c in equation:
        if c in ["+","-","="]:
            if isx:
                x += left*cur
                isx = False
            else:
                if cur !=float("-inf"):
                    value += left*cur
            cur = float("-inf")
            if c=="+":
                add = 1
            elif c=="-":
                add = -1
            else:
                add = 1
                left = -1
        elif c=="x":
            if cur==float("-inf"):
                cur = add
            isx=True
        else:
            if cur ==float("-inf"):
                cur = add*int(c)
            else:
                cur = 10*cur + add*int(c)
    if x==0:
        if value == 0:
            return "Infinite solutions"
        else:
            return "No solution"
    return "x="+str(-value//x)


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
39
40
41
42
43
44
45

单片机8 8点阵程序及电路图

application/x-rar 5星 超过95%的资源 113KB

下载

8/11 1417. 重新格式化字符串

将数字和字母分别统计 如果个数相差超过1则无法格式化

def reformat(s):
    """
    :type s: str
    :rtype: str
    """
    dig,st = [],[]
    ans = ""
    for c in s:
        if c.isdigit():
            dig.append(c)
        else:
            st.append(c)
    if abs(len(dig)-len(st))>1:
        return ans
    long,short = [],[]
    if len(dig)>len(st):
        long,short=dig,st
    else:
        long,short=st,dig
        
    for i in range(len(short)):
        ans+=long[i]+short[i]
    
    if len(long)>len(short):
        ans+=long[-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
25
26
27
28

8/12 1282. 用户分组

用哈希表m[x]存储 要求组内人数为x的当前人员
如果当前人员到达x个 则将其分为一组加入答案中

def groupThePeople(groupSizes):
    """
    :type groupSizes: List[int]
    :rtype: List[List[int]]
    """
    from collections import defaultdict
    m = defaultdict(list)
    ans = []
    for i,v in enumerate(groupSizes):
        m[v].append(i)
        if len(m[v])==v:
            ans.append(m[v])
            m[v]=[]
    return ans


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

8/13 768. 最多能完成排序的块 II

单调栈
对于一个块 如果添加一个末尾数x x大于等于该块的最大值
则x可以单独为一块
否则 x需要添加进这个块中
使用单调非减栈来记录块的个数

def maxChunksToSorted(arr):
    """
    :type arr: List[int]
    :rtype: int
    """
    stack = []
    for v in arr:
        if not stack or v>=stack[-1]:
            stack.append(v)
        else:
            mx = stack.pop()
            while stack and stack[-1]>v:
                stack.pop(-1)
            stack.append(mx)
    return len(stack)
        


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

8/14 1422. 分割字符串的最大得分

先统计所有1的个数one
从最左边开始统计当前出现过的0的次数cur0 1的次数cur1
当前得分为cur0+one-cur1
注意不能将所有的字符归为一串

def maxScore(s):
    """
    :type s: str
    :rtype: int
    """
    one = s.count("1")
    ans = 0
    cur0,cur1 = 0,0
    for c in s[:-1]:
        if c=="1":
            cur1+=1
        else:
            cur0+=1
        ans = max(cur0+one-cur1,ans)
    return ans


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