Python Leetcode_list_python pre = -inf

53. 最大子序和

方法一：动态规划

f(i) 代表以第 i 个数结尾的「连续子数组的最大和」
动态规划转移方程：

f ( i ) = max ⁡ { f ( i − 1 ) + nums [ i ] , nums [ i ] } f(i) = \max \{ f(i-1) + \textit{nums}[i], \textit{nums}[i] \} f(i)=max{f(i−1)+nums[i],nums[i]}

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:       
        # res, pre = -inf, 0
        # for i in nums:
        #     pre += i
        #     res = max(res, pre)
        #     # 如果 pre < 0，重新开始找子序串
        #     pre = max(0, pre)

        # return res

        pre, maxAns = 0, nums[0]
        for x in nums:    
            pre = max(pre + x, x)
            maxAns = max(maxAns, pre)

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

66. 加一

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for i in range(len(digits)-1,-1,-1): # 倒序遍历
            if digits[i] != 9: # 不需要进位，直接 + 1
                digits[i] += 1                
                return digits
            # 是 9 变成 0 ，给下一个数 + 1
            digits[i] = 0
        # 说明全是 9，已经都变成 0  
        return [1] + digits
   
        # return  [int(j) for j in str(eval(''.join([str(i) for i in digits]))+1)]
        # return list(map(int, str(eval(''.join(map(str, digits))) + 1)))
        # return list(map(int, str(int("".join(map(str, digits)))+1)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

class Solution:
    def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
        # w1 = ''.join(word1)
        # w2 = ''.join(word2)
        
        # return w2 == w1

        return ''.join(word1) == ''.join(word2)
1
2
3
4
5
6
7
8

2、434. 字符串中的单词数

方法一：split

class Solution:
    def countSegments(self, s: str) -> int:
        return len(s.split())
1
2
3

方法二：标记

class Solution:
    def countSegments(self, s: str) -> int:
        res = 0
        flag = True
        for c in s:
            if c != ' ':
                if flag:
                    res += 1
                flag = False
            else:
                flag = True
        return res
1
2
3
4
5
6
7
8
9
10
11
12

方法三：

class Solution:
    def countSegments(self, s: str) -> int:
        res = 0
        for i, c in enumerate(s):
            if (i == 0 or s[i-1] == ' ') and c != ' ':
                res += 1
        return res
1
2
3
4
5
6
7

3、169. 多数元素

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        '''
        n = len(nums)
        nums.sort()
        return nums[n//2]
        '''
        c, x = 0, None
        for num in nums:
            if not c:
                x = num
            c += 1 if num == x else -1
        return x
1
2
3
4
5
6
7
8
9
10
11
12
13

4、917. 仅仅反转字母

知识点： list isalpha join 推导式 pop 交换元素

class Solution:
    def reverseOnlyLetters(self, s: str) -> str:
        '''
        x = list(s)
        i, j = 0, len(s)-1
        while i < j:
            a, b = x[i].isalpha(),x[j].isalpha()
            if not a:  i += 1
            if not b:  j -= 1
            if a and b:
                x[i], x[j] = x[j], x[i]
                i += 1
                j -= 1
                
        return "".join(x)    
        ''' 
        # 栈先进后出
        res = [c for c in s if c.isalpha()]
        ans = ""        
        for c in s:
            if c.isalpha():
                ans += res.pop()
            else:
                ans += c
        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

5、1047. 删除字符串中的所有相邻重复项

class Solution:
    def removeDuplicates(self, s: str) -> str:
        '''      
        i = 1        
        while i < len(s):
            if i > 0 and s[i] == s[i-1]:
                s = s[:i-1] + s[i+1:]
                i -= 2
            i += 1
        return s
        '''

        # 方法二：使用双指针模拟栈
        res = list(s)
        slow = fast = 0
        n = len(res)

        # while fast < n:
        #     # 如果一样直接换，不一样会把后面的填在 slow 的位置
        #     res[slow] = res[fast]
            
        #     # 如果发现和前一个一样，就退一格指针
        #     if slow > 0 and res[slow] == res[slow - 1]:
        #         slow -= 1
        #     else:
        #         slow += 1

        #     fast += 1
        for i in range(n):
            res[slow] = res[i]
            if slow > 0 and res[slow] == res[slow-1]:
                slow -= 1
            else:
                slow += 1
            
        return ''.join(res[:slow])
        
        '''
        # 方法三：栈
        x = []
        for c in s:
            # if not x or c != x[-1]:
            #     x.append(c)   
            # else:
            #     x.pop()
            
            if x and c == x[-1]:
                x.pop()
            else:
                x.append(c)
                
        return ''.join(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
46
47
48
49
50
51
52
53

6、1528. 重新排列字符串

方法一：模拟

定义一个数组，长度为 len(s)；循环（循环变量 i），填充数组；将 indices[i] 为索引，s[i] 填充。
将列表用""连接并返回。

class Solution:
    def restoreString(self, s: str, indices: List[int]) -> str:
        res = [''] * len(s)
    
        # for i, j in enumerate(indices):       
        #     res[j] = s[i]
        
        for i, c in enumerate(s):
            res[indices[i]] = c

        return ''.join(res)
1
2
3
4
5
6
7
8
9
10
11

7、1436. 旅行终点站

知识点： 列表 list，append。
教程：Python 1-14 列表

class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        start, end = [], []
        for s, e in paths:
            start.append(s)
            end.append(e)

        for x in end:
            if x not in start:
                return x
1
2
3
4
5
6
7
8
9
10

**知识点：**推导式，生成器，next。
教程：Python 推导式

class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        citiesA = {path[0] for path in paths}
        return next(path[1] for path in paths if path[1] not in citiesA)
1
2
3
4

8、1967. 作为子字符串出现在单词中的字符串数目

class Solution:
    def numOfStrings(self, patterns: List[str], word: str) -> int:
        # res = 0
        # for w in patterns:
        #     if w in word:
        #         res += 1
        
        # return res

        return sum(w in word for w in patterns) # sum 可统计逻辑值 True 的个数
1
2
3
4
5
6
7
8
9
10

9、1684. 统计一致字符串的数目

class Solution:
    def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
        res = 0
        for w in words:
            for c in w:
                if c not in allowed:
                    break            
            else:
                res += 1
        
        return res
1
2
3
4
5
6
7
8
9
10
11

1184. 公交站间的距离

class Solution:
    def distanceBetweenBusStops(self, distance: List[int], start: int, destination: int) -> int:
       
        if destination < start: # 交换出发点和目的地距离相等
            start, destination = destination, start
            
        d = sum(distance[start:destination]) # 出发点到目的地距离

        return min(d, sum(distance) - d)
1
2
3
4
5
6
7
8
9

1544. 整理字符串

方法一：模拟

知识点： list，lower，append，pop，join，split，ord，chr。
教程：

从左到右扫描字符串 s 的每个字符。扫描过程中，维护当前整理好的字符串，记为 res。当扫描到字符 ch 时，有两种情况：

字符 ch 与字符串 res 的最后一个字符互为同一个字母的大小写：根据题意，两个字符都要在整理过程中被删除，因此要弹出 res 的最后一个字符；否则：两个字符都需要被保留，因此要将字符 ch 附加在字符串 res 的后面。

判断两个字母是否是互为大小写：

res[-1].lower() == ch.lower() and res[-1] != ch # 方法一
abs(ord(res[-1]) - ord(ch)) == 32: # 方法二：大小写字母 ASCII 值相差 32
ord(ch) ^ 32 == ord(res[-1]) # 方法三：运用异或判断是否互为大小写 ord('a') ^ 32 = ord('A'); ord('A') ^ 32 = ord('a');
1
2
3

ord() 函数是 chr() 函数（对于 8 位的 ASCII 字符串）的配对函数，它以一个字符串（Unicode 字符）作为参数，返回对应的 ASCII 数值，或者 Unicode 数值。

ord("中") # 20013
chr(20013) # '中'
1
2

class Solution:
    def makeGood(self, s: str) -> str:
        res = list()
        for ch in s:
            # if res and res[-1].lower() == ch.lower() and res[-1] != ch:
            # if res and abs(ord(res[-1]) - ord(ch)) == 32: # 大小写字母 ASII 值相差 32
            if res and ord(ch) ^ 32 == ord(res[-1]):            
                res.pop()
            else:
                res.append(ch)

        return "".join(res)
1
2
3
4
5
6
7
8
9
10
11
12

1700. 无法吃午餐的学生数量

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        # n = 0
        # while n < len(students):
        #     if students[0] == sandwiches[0]:
        #         students.pop(0)
        #         sandwiches.pop(0)
        #         n = 0
        #     else:
        #         students = students[1:] + [students[0]]
        #         n += 1
        # return n

        cnt = [0, 0]  # 统计喜欢圆形和方形三明治学生数量
        for i in students:
            cnt[i] += 1

        for i in sandwiches:    # 依次取出栈顶三明治,直到没有学生喜欢 i。
            if cnt[i] == 0:                
                break

            cnt[i] -= 1

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

1437. 是否所有 1 都至少相隔 k 个元素

class Solution:
    def kLengthApart(self, nums: List[int], k: int) -> bool:
        tmp = k
        for i in range(len(nums)):
            if nums[i] == 1:
                if k > tmp:return False
                tmp = 0
            else:
                tmp += 1

        return True 
1
2
3
4
5
6
7
8
9
10
11

1200. 最小绝对差

方法一：超时

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        res, n, tmp = [], len(arr), inf
        
        for i in range(n-1):
            for j in range(i+1,n):
                a, b = arr[i], arr[j]
                if a > b:
                    a, b = b, a
                x = b - a
                
                if x == tmp: 
                    res.append([a, b])
                   
                elif x < tmp:
                    tmp = x
                    res = [[a, b]]

        res.sort()
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

方法二：排序

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        arr.sort()
        min_, res, n = inf, [], len(arr)
        for i in range(1, n):
            a, b = arr[i-1], arr[i]
            if (x := b - a) < min_: # 因为有序， x >= 0
                res = [[a, b]]
                min_ = x
            elif x == min_:
                res.append([a, b])
                
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13