LeetCode 每日一题 2021/6/27-2021/7/3

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

---

6/27522. 最长特殊序列 II

check(a,b)判断b是否包含子序列a
较长的序列肯定不是短序列的子序列
将数组内序列从长倒短排序
判断某一序列是否满足独有子序列条件

def findLUSlength(strs):
    """
    :type strs: List[str]
    :rtype: int
    """
    def check(a,b):
        loca,locb = 0,0
        while loca<len(a) and locb<len(b):
            if a[loca]==b[locb]:
                loca+=1
            locb+=1
        return loca==len(a)
    strs.sort(key=lambda x:len(x),reverse=True)
    for i,s in enumerate(strs):
        tag = True
        for j,t in enumerate(strs):
            if len(t)<len(s):
                break
            if i!=j and check(s,t):
                tag = False
                break
        if tag:
            return len(s)
    return -1


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

---

6/28 324. 摆动排序 II

排序
分为小数部分 和 大数部分
偶数位放小数 奇数位放大数

def wiggleSort(nums):
    """
    :type nums: List[int]
    :rtype: None Do not return anything, modify nums in-place instead.
    """
    n = len(nums)
    snums = sorted(nums)
    l,r = (n+1)//2-1,n-1
    for i in range(0,n,2):
        nums[i] = snums[l]
        if i+1<n:
            nums[i+1] = snums[r]
        l-=1
        r-=1


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

---

6/29 535. TinyURL 的加密与解密

id用来对不同url个数计数
short用来储存shorturl对应longurl
long用来储存longurl对应shorturl

class Codec:
    
    def __init__(self):
        self.id = 0
        self.short = {}
        self.long = {}

    def encode(self, longUrl):
        """Encodes a URL to a shortened URL.
        
        :type longUrl: str
        :rtype: str
        """
        if longUrl not in self.long:
            short = "http://tinyurl.com/"+str(self.id)
            self.short[short] = longUrl
            self.long[longUrl] = short
            self.id +=1
        return self.long[longUrl]
        
        

    def decode(self, shortUrl):
        """Decodes a shortened URL to its original URL.
        
        :type shortUrl: str
        :rtype: str
        """
        return self.short[shortUrl]

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

---

6/30 1175. 质数排列

将数字分为质数 非质数
分开考虑

def numPrimeArrangements(n):
    """
    :type n: int
    :rtype: int
    """
    MOD = 10**9+7
    primes = []
    isprime = [True]*(n+1)
    for i in range(2,n+1):
        if isprime[i]:
            primes.append(i)
        for prime in primes:
            if i*prime>n:
                break
            isprime[i*prime]=False
            if i%prime==0:
                break
    num = len(primes)
    ans = 1
    for i in range(1,num+1):
        ans = (ans*i)%MOD
    for i in range(1,n-num+1):
        ans = (ans*i)%MOD
    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

---

7/1 241. 为运算表达式设计优先级

对于每一个运算符
左右两边均为完整表达式
两个表达式内结果 一一对应运算
为该运算符能得到的所有结果

def diffWaysToCompute(expression):
    """
    :type expression: str
    :rtype: List[int]
    """
    def check(exp):
        if exp.isdigit():
            return [int(exp)]
        ans = []
        for i,c in enumerate(exp):
            if c in ['+','-','*']:
                left = check(exp[:i])
                right = check(exp[i+1:])
                for l in left:
                    for r in right:
                        if c=='+':
                            ans.append(l+r)
                        elif c=='-':
                            ans.append(l-r)
                        else:
                            ans.append(l*r)
        return ans
    return check(expression)


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

---

7/28 71. 最低加油次数

依次经过加油站 将能够加的油放入大顶堆中
如果无法到达加油站 从能够加的油中选出最多的加入

def minRefuelStops(target, startFuel, stations):
    """
    :type target: int
    :type startFuel: int
    :type stations: List[List[int]]
    :rtype: int
    """
    import heapq
    fuel = startFuel
    pre = 0
    ans = 0
    stations.append([target,0])
    l = []
    for loc,f in stations:
        v = loc-pre
        fuel -= v
        while fuel<0 and l:
            tmp = -heapq.heappop(l)
            ans +=1
            fuel += tmp
        if fuel < 0:
            return -1
        heapq.heappush(l,-f)
        pre = loc
        
    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

---

7/3 556. 下一个更大元素 III

转换成字符串处理
第一次从尾部往前 找到第一个nums[i]<nums[i+1]的位置
此时 i之后的序列为降序
第二次从尾部往前 找到最先出现的nums[j]>nums[i]
将两个位置交换 并将i后的部分倒序变为升序

def nextGreaterElement(n):
    """
    :type n: int
    :rtype: int
    """
    nums = list(str(n))
    i = len(nums)-2
    while i>=0 and nums[i]>=nums[i+1]:
        i -= 1
    if i<0:
        return -1
    j = len(nums)-1
    while j>=0 and nums[i]>=nums[j]:
        j -= 1
    nums[i],nums[j] = nums[j],nums[i]
    nums[i+1:] = nums[i+1:][::-1]
    ans = int("".join(nums))
    return ans if ans<2**31 else -1


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

---