LeetCode 每日一题 2022/9/26-2022/10/2

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

---

9/26 面试题 17.19. 消失的两个数字

1.数学法求a+b ab a-b
2.异或法
将原有数组内所有数字异或之后 继续同1~N异或得到结果为a^b
在结果中找到一位loc位置异或结果为1 说明在loc位 a,b不同
遍历原数组+1~N 将所有数分为两类 loc位为1一类 为0一类
将两类分别异或 结果为a,b

def missingTwo(nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    import math
    n = len(nums)+2
    s1 = 0
    m1 = 1
    for num in nums:
        s1 +=num
        m1 *=num
    s2 = 0
    m2 = 1
    for num in range(1,n+1):
        s2 +=num
        m2 *=num
    x = s2-s1 #a+b
    y = m2//m1 #a*b
    z = int(math.sqrt(x**2-4*y)) #a-b

    a = (z+x)//2
    b = x-a
    return [a,b]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

9/27 面试题 01.02. 判定是否互为字符重排

统计两个字符串内各个字符出现次数是否相同

def CheckPermutation(s1: str, s2: str) -> bool:
    if len(s1)!=len(s2):
        return False
    m = {}
    for c in s1:
        m[c] = m.get(c,0)+1
        
    for c in s2:
        if c not in m:
            return False
        m[c] -=1
        if m[c]<0:
            return False
    return True



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

---

9/28 面试题 17.09. 第 k 个数

dp保留所有数
c3,c5,c7记录3,5,7倍数当前位置

def getKthMagicNumber(k):
    """
    :type k: int
    :rtype: int
    """
    dp = [1]
    c3,c5,c7 = 0,0,0
    for i in range(1,k):
        dp.append(min(dp[c3]*3,dp[c5]*5,dp[c7]*7))
        if dp[i] == dp[c3]*3:
            c3+=1
        if dp[i] == dp[c5]*5:
            c5+=1
        if dp[i] == dp[c7]*7:
            c7+=1
    return dp[k-1]


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

---

9/29 面试题 01.09. 字符串轮转

长度不一样返回false
一次判断s1旋转i位后是否与s2相同

def isFlipedString(s1, s2):
    """
    :type s1: str
    :type s2: str
    :rtype: bool
    """
    if len(s1)!=len(s2):
        return False
    if len(s1)==0:
        return True
    for i in range(len(s1)):
        tmp = s1[i:]+s1[:i]
        if tmp==s2:
            return True
    return False


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

---

9/30 面试题 01.08. 零矩阵

记录所有0的点 根据点将横竖赋值为0

def setZeroes(matrix):
    """
    :type matrix: List[List[int]]
    :rtype: None Do not return anything, modify matrix in-place instead.
    """
    m = len(matrix)
    if m==0:
        return
    n = len(matrix[0])
    l = set()
    for i in range(m):
        for j in range(n):
            if matrix[i][j]==0:
                l.add((i,j))
        
    for x,y in l:
        for i in range(n):
            matrix[x][i]=0
        for i in range(m):
            matrix[i][y]=0
    return


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

---

10/1 1694. 重新格式化电话号码

去除空格破折 三个一组取出

def reformatNumber(number):
    """
    :type number: str
    :rtype: str
    """
    number=number.replace(" ","")
    number=number.replace("-","")
    num = len(number)
    ans = ""
    loc = 0
    while num>0:
        if num<=3:
            ans+=number[loc:]
            break
        elif num==4:
            ans += number[loc:loc+2]+"-"+number[loc+2:]
        else:
            ans += number[loc:loc+3]+"-"
            loc+=3
            num-=3
    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

---

10/2 777. 在LR字符串中交换相邻字符

XL->LX L可以往左移动
RX->XR R可以往右移动
双指针找到第一个非X值 start[i],end[j] 如果这两个不同则不满足
如果为start[i]为L 则需要满足i>=j
如果为R 则需要满足i<=j

def canTransform(start, end):
    """
    :type start: str
    :type end: str
    :rtype: bool
    """
    n = len(start)
    i,j=0,0
    while i<n and j<n:
        while i<n and start[i]=='X':
            i+=1
        while j<n and end[j]=='X':
            j+=1
        if i<n and j<n:
            if start[i]!=end[j]:
                return False
            s = start[i]
            if (s=='L' and i<j) or (s=='R' and i>j):
                return False
            i+=1
            j+=1
    while i<n:
        if start[i]!='X':
            return False
        i+=1
    while j<n:
        if end[j]!='X':
            return False
        j+=1
    return True


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

---