晨曦微光
0%

Veröffentlicht am Bearbeitet am in

1. 缺失的第一个正数(Hard)

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。

示例 1:

1
2
输入: [1,2,0]
输出: 3

示例 2:

1
2
输入: [3,4,-1,1]
输出: 2

示例 3:

1
2
输入: [7,8,9,11,12]
输出: 1

说明:

你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。

解答：

思路：

官方题解：还是哈希表，不过，key是nums的索引，value是正负号，如果nums[i]出现过，则为正号，否则为负号，nums[i]因为映射到索引，所以是按顺序来的。

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
class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if 1 not in nums:
            return 1
        if len(nums) == 1:
            return 2
        for i in range(len(nums)):
            if nums[i]<= 0 or nums[i] > len(nums):
                nums[i] = 1
            
        for i in range(len(nums)):
            a = abs(nums[i])
            if a == len(nums):
                nums[0] = -abs(nums[0])
            else:
                nums[a] = -abs(nums[a])
        
        for i in range(1,len(nums)):
            if nums[i]>0:
                return i
        if nums[0] > 0:
            return len(nums)
        return len(nums)+1

2. 接雨水(Hard)

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例:

1
2
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解答：

思路：

题目有几个特性可用，bar width = 1,然后第一个和最后一个是不能trap water，其次中间的部分能trap多少水是看左右高度差较低的那个 - 本身的高度

设置双指针l和r，然后获取左右最低的那个高度min_h，因为短板效应，所以水的高度不可能大于min_h，所以我们继续移动双指针，如果接下来移动的位置的高度小于min_h，则可以装水，直到遇到高度高于min_h，更新l和r继续这个过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        l,r = 0,len(height)-1
        water = 0
        min_height = 0
        while l < r:
            min_height = min(height[l],height[r])
            while l < r and height[l] <= min_height:
                water += min_height - height[l]
                l += 1
            while l < r and height[r] <= min_height:
                water += min_height - height[r]
                r -= 1
        return water

3. 字符串相乘(Medium)

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

1
2
输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

1
2
输入: num1 = "123", num2 = "456"
输出: "56088"

说明：

  1. num1 和 num2 的长度小于110。
  2. num1 和 num2 只包含数字 0-9。
  3. num1 和 num2 均不以零开头，除非是数字 0 本身。
  4. 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

解答：

思路：

完全模拟乘法过程。

  1. m位的数字乘以n位的数字的结果最大为m+n位：
    • 99999 < 1000100 = 100000，最多为3+2 = 5位数。
  2. 先将字符串逆序便于从最低位开始计算。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        lookup = {'0':0,'1':1,'2':2,'3':3,'4':4,'5':5,'6':6,'7':7,'8':8,'9':9}
        if num1 == '0' or num2 == '0':
            return '0'
        num1,num2 = num1[::-1],num2[::-1]
        
        tmp_res = [0 for _ in range(len(num1)+len(num2))]
        for i in range(len(num1)):
            for j in range(len(num2)):
                tmp_res[i+j] += lookup[num1[i]] * lookup[num2[j]]
        res = [0 for _ in range(len(num1)+len(num2))]
        for i in range(len(tmp_res)):
            res[i] = tmp_res[i]%10
            if i < len(num1)+len(num2)-1:
                tmp_res[i+1] += tmp_res[i]/10
        return ''.join(str(i) for i in res[::-1]).lstrip('0')

4. 字符串相加(Easy)(415)

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和。

注意：

  1. num1 和num2 的长度都小于 5100.
  2. num1 和num2 都只包含数字 0-9.
  3. num1 和num2 都不包含任何前导零。
  4. 你不能使用任何內建 BigInteger 库， 也不能直接将输入的字符串转换为整数形式。

解答：

思路：

和上述同样的题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def addStrings(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        num1,num2 = num1[::-1],num2[::-1]
        l1 = len(num1)
        l2 = len(num2)
        if l1 < l2:
            num1,num2 = num2,num1
            l1,l2 = l2,l1
        tmp = 0
        res = []
        for i in range(l1):
            tmp += int(num1[i])
            if i < l2:
                tmp += int(num2[i])
            res.append(tmp%10)
            tmp = tmp/10
        if tmp:
            res.append(tmp)
        return ''.join(str(c) for c in res[::-1])

5. 通配符匹配(Hard)

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

1
2
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明:

  • s 可能为空，且只包含从 a-z 的小写字母。
  • p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

示例 1:

1
2
3
4
5
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

1
2
3
4
5
输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

示例 3:

1
2
3
4
5
输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

示例 4:

1
2
3
4
5
输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

示例 5:

1
2
3
4
输入:
s = "acdcb"
p = "a*c?b"
输入: false

解答：

思路：

很显然，第一种思想，动态规划，

dp[i][j]表示s[:i]和p[:j]是否匹配。

首先dp[0][0] = True

其次，dp[0][j] = dp[0][j-1] if p[j] == ‘*’

其次，dp[j][0] = False

动态方程：

1
2
3
4
if s[i] == p[j] or p[j] == '?' and dp[i-1][j-1]:
		dp[i][j] = True
if p[j] == '*':
  	dp[i][j] = dp[i-1][j] or dp[i][j-1]

下面是代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        dp = [[False] * (len(p)+1) for i in range(len(s)+1)]
        dp[0][0] = True
        for j in range(1,len(p)+1):
            if p[j-1] == '*':
                dp[0][j] = dp[0][j-1]
        for i in range(1,len(s)+1):
            for j in range(1,len(p)+1):
                if p[j-1] == '*':
                    dp[i][j] = dp[i-1][j] or dp[i][j-1]
                elif s[i-1]==p[j-1] or p[j-1] == '?':
                    dp[i][j] = dp[i-1][j-1]
        return dp[-1][-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
27
class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        point_s,point_p = 0,0
        match = 0
        star = -1
        while point_s < len(s):
            if point_p < len(p) and (s[point_s] == p[point_p] or p[point_p] == '?'):
                point_s += 1
                point_p += 1
            elif point_p < len(p) and p[point_p] == '*':
                star = point_p
                match = point_s
                point_p += 1
            elif star != -1:
                point_p = star + 1
                match += 1
                point_s = match
            else:
                return False
        while point_p < len(p) and p[point_p] == '*':
            point_p += 1
        return point_p == len(p)

6. 跳跃游戏2(Hard)

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

1
2
3
4
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明:

假设你总是可以到达数组的最后一个位置。

解答：

思路：

贪心规律

*  在到达**某点**前，若一直不跳跃，如果发现**从该点无法跳跃更远的地方**了，在这之前，肯定有一次必要的跳跃
  • 在无法到达更远的地方时，在这之前应该跳到一个可以到达更远位置的位置

算法思路

  1. 设置cur 为当前可达的最远位置
  2. pre 为遍历各个位置过程中，各个位置能达到的最远位置
  3. res 为最少跳跃次数
  4. 利用i遍历nums数组，如超过cur 则res加1, cur=pre
  5. 遍历过程中，如果pre< nums[i] + i 则更新pre
  6. i表示当前位置，num[i]表示当前可以跳多远
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums)<2:
            return 0
        cur = nums[0]
        pre = nums[0]
        res = 1
        for i in range(len(nums)):
            if cur < i:
                cur = pre
                res += 1
            pre = max(pre,i + nums[i])
        return res

另一份AC代码可能更好理解：

cur_far表示当前下一步可跳最远距离

cur_end表示上一跳所跳的位置

i表示当前所在的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cur_end, cur_farthest, step = 0, 0, 0
        for i in range(len(nums)-1):
            cur_farthest = max(cur_farthest, i+nums[i])
            if cur_farthest >= len(nums) - 1:
                step += 1
                return step
            if i == cur_end:
                cur_end = cur_farthest
                step += 1
        return step

Very elegant method, but it took me a long time to understand. Some comment for the above:

e: longest distance in current minimum step

sc: minimum steps for reaching e

From i to e, even max is changed in a loop, it is reachable in one step.

思路三：动态规划

超级容易理解。
dp[i]代表的是到达index为i的位置的最少步数, 依然超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums or len(nums) == 0:
            return 0
        dp = [sys.maxsize] * len(nums)
        dp[0] = 0
        for i in range(1, len(nums)):
            for j in range(i):
                if j + nums[j] >= i:
                    dp[i] = min(dp[i], dp[j]+1)
        return dp[-1]

Veröffentlicht am Bearbeitet am in

1. 有效的数独(Medium)

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

img

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: true

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
     但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

说明:

  • 一个有效的数独（部分已被填充）不一定是可解的。
  • 只需要根据以上规则，验证已经填入的数字是否有效即可。
  • 给定数独序列只包含数字 1-9 和字符 '.' 。
  • 给定数独永远是 9x9 形式的。

解答：

思路：

首先还是理清题意，就是每一行、每一列、每一个小正方形都不能重复出现相同数字,如下图所示：

Snipaste_2019-05-08_15-33-58.png

所以我们最直接想到就是，就是记录它的行，列和小正方形的值，有重复就false。

  1. 我们用一个字典，分别记录行，列，和小正方形！

  2. 行,列我们直接可以用数字表示，小正方形如何表示呢？

  3. 这里,我们发现一个规律,我们可以把小正方形变成用二维唯一标识,比如(0,0)表示左上角那个,(1,1)表示中间那个,他们和行列的关系就是(i//3,j//3)，

  4. 所以任何位置我们都能找出它在哪个行，哪个列，哪个小正方形里！

  5. 时间复杂度都是常数级的。

  1. ```python
    class Solution(object):
    def isValidSudoku(self, board):
    """
    :type board: List[List[str]]
    :rtype: bool
    """
    row = [{} for i in range(len(board))]
    col = [{} for j in range(len(board[0]))]
    box = [{} for i in range(len(board))]
    
    for i in range(9):
        for j in range(9):
            num = board[i][j]
            if num != '.':
                num = int(num)
                box_index = (i//3)*3+j//3
                
                row[i][num] = row[i].get(num,0)+1
                col[j][num] = col[j].get(num,0)+1
                box[box_index][num] = box[box_index].get(num,0)+1
                
                if row[i][num]>1 or col[j][num]>1 or box[box_index][num]>1:
                    return False
    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
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69

    ## 2. 解数独(Hard)

    编写一个程序，通过已填充的空格来解决数独问题。

    一个数独的解法需**遵循如下规则**：

    1. 数字 `1-9` 在每一行只能出现一次。
    2. 数字 `1-9` 在每一列只能出现一次。
    3. 数字 `1-9` 在每一个以粗实线分隔的 `3x3` 宫内只能出现一次。

    空白格用 `'.'` 表示。

    ![img](http://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png)

    一个数独。

    ![img](http://upload.wikimedia.org/wikipedia/commons/thumb/3/31/Sudoku-by-L2G-20050714_solution.svg/250px-Sudoku-by-L2G-20050714_solution.svg.png)

    答案被标成红色。

    **Note:**

    - 给定的数独序列只包含数字 `1-9` 和字符 `'.'` 。
    - 你可以假设给定的数独只有唯一解。
    - 给定数独永远是 `9x9` 形式的。



    **解答：**

    **思路：**

    经典backtrack

    对于每一个为'.'的点都从1试到9，如果valid就继续往下走，不valid立马backtrack

    ```python
    class Solution(object):
        def solveSudoku(self, board):
            """
            :type board: List[List[str]]
            :rtype: None Do not return anything, modify board in-place instead.
            """
            self.backtrack(board)
            
        def backtrack(self,board):
            for i in range(9):
                for j in range(9):
                    if board[i][j] == '.':
                        for c in '123456789':
                            if self.isPointValid(board,i,j,c):
                                board[i][j] = c
                                if self.backtrack(board):
                                    return True
                                else:
                                    board[i][j] = '.'
                        return False
            return True
            
        def isPointValid(self,board,x,y,c):
            for i in range(9):
                if board[i][y] == c:
                    return False
                if board[x][i] == c:
                    return False
                if board[(x//3)*3+i//3][(y//3)*3+i%3] == c:
                    return False
            return True

3. 报数(Easy)

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1
2
3
4
5
1.     1
2.     11
3.     21
4.     1211
5.     111221

1 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2", “one 1" （"一个二" , "一个一") , 即 1211。

给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。

注意：整数顺序将表示为一个字符串。

示例 1:

1
2
输入: 1
输出: "1"

示例 2:

1
2
输入: 4
输出: "1211"

解答：

思路一：

  1. i代表字符下标，从0开始取值，也就是从第一个字符开始，因为要让i取到最后一个字符，并且后面还要进行i+1的操作，所以将原字符串随意加上一个‘*’字符防止溢出
  2. count代表此时已经连续相同的字符个数
  3. res代表最终输出的字符串
  • 只要i下标对应的字符等于下一个字符，则sum和i都加1，无限循环
  • 如果i下标对应的字符不等于下一个字符了，则res应该加上str(sum)和i下标对应的那个字符，并且i加1，sum复原回0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        if n == 1:
            return '1'
        s = self.countAndSay(n-1) + '*'
        res,count = '',1
        for i in range(len(s)-1):
            if s[i]==s[i+1]:
                count += 1
            else:
                res += str(count) + str(s[i])
                count = 1
        return res

思路二：一句话解释: 不断由前一个数推下一个数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        def next_num(tmp):
            n = len(tmp)
            res = ''
            i = 0
            while i < n:
                count = 1
                while i < n-1 and tmp[i] == tmp[i+1]:
                    count += 1
                    i += 1
                res += str(count)+str(tmp[i])
                i += 1
            return res
        
        res = '1'
        for i in range(1,n):
            res = next_num(res)
        return res

4. 组合总和(Medium)

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

  1. 所有数字（包括 target）都是正整数。
  2. 解集不能包含重复的组合。
    示例 1:
1
2
3
4
5
6
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

示例 2:

1
2
3
4
5
6
7
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

解答：

思路：递归解法

此问题可以拆分成子问题求解。

每一个子问题，可以分成两步：

  1. 跳过当前数字

    1. 取当前数字并继续保留当前数字为candidates

失败条件是tmp_sum>target或者i==n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        n = len(candidates)
        res = []
        def helper(i,tmp_sum,tmp):
            if tmp_sum > target or i == n:
                return
            if tmp_sum == target:
                res.append(tmp)
                return
            helper(i,tmp_sum+candidates[i],tmp+[candidates[i]])
            helper(i+1,tmp_sum,tmp)
        helper(0,0,[])
        return res

思路二：回溯算法

标准的回溯算法解答格式

这类题目都是同一类型的,用回溯算法!

其实回溯算法关键在于:不合适就退回上一步

然后通过约束条件, 减少时间复杂度.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        n = len(candidates)
        res = []
        def backtrack(i,tmp_sum,tmp):
            if tmp_sum > target or i == n:
                return
            if tmp_sum == target:
                res.append(tmp)
                return
            for j in range(i,n):
                if tmp_sum + candidates[j]>target:
                    break
                backtrack(j,tmp_sum+candidates[j],tmp+[candidates[j]])
        backtrack(0,0,[])
        return res

5. 组合总和2(Medium)

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

  • 所有数字（包括目标数）都是正整数。
  • 解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

示例 2:

1
2
3
4
5
6
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

解答：

思路：回溯算法

和上一题一样的模版，一样的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        n = len(candidates)
        res = []
        def backtrack(i,tmp_sum,tmp):
            if tmp_sum == target:
                res.append(tmp)
                return
            for j in range(i,n):
                if tmp_sum + candidates[j] > target:
                    break
                if j > i and candidates[j] == candidates[j-1]:
                    continue
                backtrack(j+1,tmp_sum+candidates[j],tmp+[candidates[j]])
        backtrack(0,0,[])
        return res

Veröffentlicht am Bearbeitet am in

1. 下一个排列(Medium)

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

1
2
3
4
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解答：

思路：

首先，我们观察到对于任何给定序列的降序，没有可能的下一个更大的排列。

例如，以下数组不可能有下一个排列：[9, 5, 4, 3, 1]

我们需要从右边找到第一对两个连续的数字 $a[i]$ 和 $a[i-1]$，它们满足 $a[i]>a[i-1]$。现在，没有对 $a[i-1]$右侧的重新排列可以创建更大的排列，因为该子数组由数字按降序组成。因此，我们需要重新排列 $a[i-1]$ 右边的数字，包括它自己。

现在，什么样子的重新排列将产生下一个更大的数字呢？我们想要创建比当前更大的排列。因此，我们需要将数字 $a[i-1]$ 替换为位于其右侧区域的数字中比它更大的数字，例如 $a[j]$。

Next Permutation

我们交换数字 $a[i-1]$ 和 $a[j]$。我们现在在索引 $i-1$ 处有正确的数字。 但目前的排列仍然不是我们正在寻找的排列。我们需要通过仅使用 $a[i-1]$右边的数字来形成最小的排列。 因此，我们需要放置那些按升序排列的数字，以获得最小的排列。

但是，请记住，在从右侧扫描数字时，我们只是继续递减索引直到我们找到 $a[i]$ 和 $a[i-1]$ 这对数。其中，$a[i] > a[i-1]$。因此，$a[i-1]$ 右边的所有数字都已按降序排序。此外，交换 $a[i-1]$和 $a[j]$ 并未改变该顺序。因此，我们只需要反转$ a[i-1]$ 之后的数字，以获得下一个最小的字典排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        if len(nums) == 0:
            return 
        idx = 0
        for i in range(len(nums)-1,0,-1):
            if nums[i] > nums[i-1]:
                idx = i
                break
        if idx != 0:
            for i in range(len(nums)-1,idx-1,-1):
                if nums[i] > nums[idx-1]:
                    nums[i],nums[idx-1] = nums[idx-1],nums[i]
                    break
        nums[idx:] = nums[idx:][::-1]

2. 最长有效括号(Hard)

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

1
2
3
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

1
2
3
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

解答：

思路：动态规划

  1. 用一个dp数组来存放以每个index为结尾的最长有效括号子串长度，例如：dp[3] = 2代表以index为3结尾的最长有效括号子串长度为2
  2. 很明显dp[i]和dp[i-1]之间是有关系的
  • 当s[i] == ‘(’时，dp[i]显然为0, 由于我们初始化dp的时候就全部设为0了，所以这种情况压根不用写
  • 当s[i] == ')'时， 如果在dp[i-1]的所表示的最长有效括号子串之前还有一个'('与s[i]对应，那么dp[i] = dp[i-1] + 2, 并且还可以继续往前追溯（如果前面还能连起来的话)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 0:
            return 0
        dp = [0 for i in range(len(s))]
        for i in range(1,len(s)):
            if s[i] == ')':
                left = i-1-dp[i-1]
                if left >= 0 and s[left] == '(':
                    dp[i] = dp[i-1]+2
                    if left > 0:
                        dp[i] += dp[left-1]
        return max(dp)

思路二：栈

与找到每个可能的子字符串后再判断它的有效性不同，我们可以用栈在遍历给定字符串的过程中去判断到目前为止扫描的子字符串的有效性，同时能的都最长有效字符串的长度。我们首先将0放入栈顶。

对于遇到的每个’(‘ ，我们将0放入栈中。 对于遇到的每个‘)’ ，如果当前栈长度大于1，我们弹出栈顶的元素并加2(意思是当前读到的’)’和上一个’(‘做匹配，长度为2，同时删除掉一个’(‘)，将得到的值加到栈顶元素，表示读到当前字符时的最长有效括号长度。通过这种方法，我们继续计算有效子字符串的长度，并最终返回最长有效子字符串的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = [0]
        longest = 0
        for c in s:
            if c == '(':
                stack.append(0)
            else:
                if len(stack)>1:
                    val = stack.pop()
                    stack[-1] += val + 2
                    longest = max(longest,stack[-1])
                else:
                    stack = [0]
        return longest

3. 搜索旋转排序数组(Medium)

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

1
2
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:

1
2
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

解答：

思路：二分法

很简单。

直接使用二分法，判断那个二分点,有几种可能性

  1. 直接等于target

  2. 在左半边的递增区域

    a. target 在 left 和 mid 之间

    b. 不在之间

  3. 在右半边的递增区域

    a. target 在 mid 和 right 之间

    b. 不在之间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = l + ((r - l) >> 2)
            if nums[mid] == target:
                return mid
            if nums[mid] <= nums[r]:
                if nums[mid] < target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1
            else:
                if nums[l] <= target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
        return -1

4. 在排序数组中查找元素的第一个和最后一个位置(Medium)

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

1
2
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

1
2
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

解答：

思路：

二分法，先找target出现的左边界，判断是否有target后再判断右边界

  • 找左边界：二分，找到一个index
    • 该index对应的值为target
    • 并且它左边index-1对应的值不是target（如果index为0则不需要判断此条件）
    • 如果存在index就将其append到res中
  • 判断此时res是否为空，如果为空，说明压根不存在target，返回[-1, -1]
  • 找右边界：二分，找到一个index（但是此时用于二分循环的l可以保持不变，r重置为len(nums)-1，这样程序可以更快一些）
    • 该index对应的值为target
    • 并且它右边index+1对应的值不是target（如果index为len(nums)-1则不需要判断此条件）
    • 如果存在index就将其append到res中
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
class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if not nums or len(nums) == 0: 
            return [-1, -1]
        res = []
        l, r = 0, len(nums)-1
        # search for left bound
        while l <= r:
            mid = l + ((r - l) >> 2)
            if nums[mid] == target and (mid == 0 or nums[mid-1] != target):
                res.append(mid)
                break
            elif nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
        if not res:
            return [-1, -1]
        # search for right bound, now we don't need to reset left pointer
        r = len(nums)-1
        while l <= r:
            mid = l + ((r - l) >> 2)
            if nums[mid] == target and (mid == len(nums)-1 or nums[mid+1] != target):
                res.append(mid)
                break
            elif nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1 
        # 这里直接返回res是因为前面如果判断左边界没返回的话就说明我们判断右边界的时候一定会append元素
        return res

5. 搜索插入位置(Easy)

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

1
2
输入: [1,3,5,6], 5
输出: 2

示例 2:

1
2
输入: [1,3,5,6], 2
输出: 1

示例 3:

1
2
输入: [1,3,5,6], 7
输出: 4

示例 4:

1
2
输入: [1,3,5,6], 0
输出: 0

解答：

思路：

很简单，二分法。

  • 寻找插入点使用二分法，但与寻找某数字不同的是，需要考虑一些边界条件：

    • 当插入数字和nums中某数字相等时，插入到左边还是右边？本题要求插到左边；
    • 插入数字在nums第一个数字左边，或在最后一个数字右边；

  • 推荐记住其中的几个关键点写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        l,r = 0,len(nums)-1
        while l <= r:
            mid = (r + l)>>1
            if  target > nums[mid]:
                l = mid + 1
            else:
                r = mid - 1
        return l

Veröffentlicht am Bearbeitet am in

1. 删除排序数组中的重复项(Easy)

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

1
2
3
4
5
给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。

示例 2:

1
2
3
4
5
给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

1
2
3
4
5
6
7
8
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解答：

思路一：双指针法

快指针遍历旧数组，满指针指向新数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        slow = 0
        for fast in range(len(nums)):
            if nums[slow] != nums[fast]:
                slow += 1
                nums[slow] = nums[fast]
        return slow+1

思路二：

很简单，一看就明白

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        idx = 0
        for num in nums:
            if idx < 1 or num != nums[idx-1]:
                nums[idx] = num
                idx += 1
        return idx

2. 移除元素(Easy)

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

1
2
3
4
5
给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

1
2
3
4
5
6
7
给定 nums = [0,1,2,2,3,0,4,2], val = 2,

函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

注意这五个元素可为任意顺序。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

1
2
3
4
5
6
7
8
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

解答：

思路：

这个题很简单。思路也很简单。

如果当前数字等于$val$，就把当前数字换成数组的最后一个数字，然后删除掉数组最后一个数字，这样可以实现时间$O(N)$了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        idx = 0
        while idx < len(nums):
            if nums[idx] == val:
                nums[idx] = nums[-1]
                del nums[-1]
            else:
                idx += 1
        return len(nums)

思路二：双指针法

双指针法真是好用，在数组问题里面。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        slow = 0
        for fast in range(len(nums)):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
        return slow

3. 实现strStr()(Easy)

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1:

1
2
输入: haystack = "hello", needle = "ll"
输出: 2

示例 2:

1
2
输入: haystack = "aaaaa", needle = "bba"
输出: -1

说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

解答：

思路一：

KMP算法

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
class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """        
        if not needle : return 0
        _next = [0] * len(needle)
        def getNext(p, _next):
            _next[0] = -1
            i = 0
            j = -1
            while i < len(p) - 1:
                if j == -1 or p[i] == p[j]:
                    i += 1
                    j += 1
                    _next[i] = j
                else:
                    j = _next[j]
        getNext(needle, _next)
        i = 0
        j = 0
        while i < len(haystack) and j < len(needle):
            if j == -1 or haystack[i] == needle[j]:
                i += 1
                j += 1
            else:
                j = _next[j]
        if j == len(needle):
            return i - j
        return -1

思路二：暴力搜索

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """    
        for i in range(len(haystack) - len(needle) + 1):
            if haystack[i:i+len(needle)] == needle:
                return i
        return -1

4. 两数相除(Medium)

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:

1
2
输入: dividend = 10, divisor = 3
输出: 3

示例 2:

1
2
输入: dividend = 7, divisor = -3
输出: -2

说明:

  1. 被除数和除数均为 32 位有符号整数。
  2. 除数不为 0。

假设我们的环境只能存储 32 位有符号整数，其数值范围是 $[−2^{31}, 2^{31} − 1]$。本题中，如果除法结果溢出，则返回 $2^{31} − 1$。

解答：

思路一：

不能乘除，所以我们改用位运算，运用二分的思想，beats 100%

因为最坏的情况就是最大的数除以1，即2**31 / 1, 所以时间复杂度就是O(1)，如果assuming n is the number of bits， 那就是O(lgN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        res = 0
        positive = 1 if dividend^divisor>=0 else -1
        dividend = abs(dividend)
        divisor = abs(divisor)
        while dividend >= divisor:
            tmp,cnt = divisor,1
            while dividend >= tmp:
                dividend -= tmp
                res += cnt
                tmp <<= 1
                cnt <<= 1
        res = positive * res
        return max(min(res,2**31-1),-2**31)

5. 串联所有单词的字串(Hard)

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

示例 1：

1
2
3
4
5
6
7
输入：
  s = "barfoothefoobarman",
  words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoor" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

1
2
3
4
输入：
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
输出：[]

解答：

思路：滑动窗口+双指针

把words里面的word和其频率都记下来，然后对s做双指针记录，只要匹配上了words就append到res中去

但是由于从不同起点开始结果不一样，所以最前面还要做一个for循环for i in range(word_len):这样从每个起点开始都能到达最后

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
class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        from collections import Counter
        if not s or not words:
            return []
        one_word = len(words[0])
        word_num = len(words)
        n = len(s)
        if n < one_word:
            return []
        words = Counter(words)
        res = []
        for i in range(0,one_word):
            cur_cnt = 0
            left = i
            right = i
            cur_Counter = Counter()
            while right+one_word<=n:
                w = s[right:right+one_word]
                right += one_word
                if w not in words:
                    left = right
                    cur_Counter.clear()
                    cur_cnt = 0
                else:
                    cur_Counter[w] += 1
                    cur_cnt += 1
                    while cur_Counter[w] > words[w]:
                        left_w = s[left:left+one_word]
                        left += one_word
                        cur_Counter[left_w] -= 1
                        cur_cnt -= 1
                    if cur_cnt == word_num:
                        res.append(left)
        return res

Veröffentlicht am Bearbeitet am in

1. 合并两个有序链表(Easy)

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

1
2
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

解答：

思路：时间复杂度: $O(n)$，空间复杂度:$ O(1)$

同样是dummy head

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1:
            return l2
        if not l2:
            return l1
        dummy = cur = ListNode(-1)
        while l1 and l2:
            if l1.val<l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 if l1 else l2
        return dummy.next

2. 括号生成(Medium)

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

1
2
3
4
5
6
7
8
例如，给出 n = 3，生成结果为：
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

解答：

思路一：

官方解答：回溯法

只有在我们知道序列仍然保持有效时才添加 ‘(‘ or ‘)’，而不是每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，

如果我们还剩一个位置，我们可以开始放一个左括号。 如果它不超过左括号的数量，我们可以放一个右括号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        ans = []
        def backtrack(s='',left = 0,right = 0,n = n):
            if len(s) == 2 * n:
                ans.append(s)
                return
            if left < n:
                backtrack(s+'(',left+1,right,n)
            if right < left:
                backtrack(s+')',left,right+1,n)
            
        backtrack()
        return ans

以这道题为例，backtrack的题应该怎么去思考？

所谓Backtracking都是这样的思路：在当前局面下，你有若干种选择。那么尝试每一种选择。如果已经发现某种选择肯定不行（因为违反了某些限定条件），就返回；如果某种选择试到最后发现是正确解，就将其加入解集

所以你思考递归题时，只要明确三点就行：选择 (Options)，限制 (Restraints)，结束条件 (Termination)。即“ORT原则”（这个是我自己编的）。

对于这道题，在任何时刻，你都有两种选择：

  1. 加左括号。
  2. 加右括号。

同时有以下限制：

  1. 如果左括号已经用完了，则不能再加左括号了。
  2. 如果已经出现的右括号和左括号一样多，则不能再加右括号了。因为那样的话新加入的右括号一定无法匹配。

结束条件是：左右括号都已经用完。

结束后的正确性：

左右括号用完以后，一定是正确解。因为1. 左右括号一样多，2. 每个右括号都一定有与之配对的左括号。因此一旦结束就可以加入解集（有时也可能出现结束以后不一定是正确解的情况，这时要多一步判断）。

递归函数传入参数：

限制和结束条件中有“用完”和“一样多”字样，因此你需要知道左右括号的数目。当然你还需要知道当前局面sublist和解集res。

1
2
3
4
5
6
7
8
9
10
if (左右括号都已用完) {
  加入解集，返回
}
//否则开始试各种选择
if (还有左括号可以用) {
  加一个左括号，继续递归
}
if (右括号小于左括号) {
  加一个右括号，继续递归
}

这题其实是最好的backtracking初学练习之一，因为ORT三者都非常简单明显。你不妨按上述思路再梳理一遍，还有问题的话再说。

以上文字来自 1point3arces的牛人解答

复杂度分析：

我们的复杂度分析依赖于理解 $generateParenthesis(n)$ 中有多少个元素。这个分析超出了本文的范畴，但事实证明这是第 n 个卡塔兰数 $\dfrac{1}{n+1}\binom{2n}{n} $，这是由 $\dfrac{4^n}{n\sqrt{n}} $ 渐近界定的。

时间复杂度：$O(\dfrac{4^n}{\sqrt{n}})$，在回溯过程中，每个有效序列最多需要 n 步。

空间复杂度：$O(\dfrac{4^n}{\sqrt{n}})$，如上所述，并使用 $O(n)$ 的空间来存储序列。

思路二：动态规划

来自本题题解的解答。

在此题中，动态规划的思想类似于数学归纳法，当知道所有i<n的情况时，我们可以通过某种算法算出i=n的情况。 本题最核心的思想是，考虑i=n时相比n-1组括号增加的那一组括号的位置。

具体思路如下： 当我们清楚所有i<n时括号的可能生成排列后，对与i=n的情况，我们考虑整个括号排列中最左边的括号。 它一定是一个左括号，那么它可以和它对应的右括号组成一组完整的括号”( )”，我们认为这一组是相比n-1增加进来的括号。

那么，剩下n-1组括号有可能在哪呢？ 剩下的括号要么在这一组新增的括号内部，要么在这一组新增括号的外部（右侧）。既然知道了i<n的情况，那我们就可以对所有情况进行遍历： “(“ + 【i=p时所有括号的排列组合】 + “)” + 【i=q时所有括号的排列组合】 其中 p + q = n-1，且p q均为非负整数。 事实上，当上述p从0取到n-1，q从n-1取到0后，所有情况就遍历完了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0:
            return []
        total_l = []
        total_l.append([None])
        total_l.append(["()"])
        for i in range(2,n+1):  # 开始计算i时的括号组合，记为l
            l = []
            for j in range(i): #遍历所有可能的括号内外组合
                now_list1 = total_l[j]
                now_list2 = total_l[i-1-j]
                for k1 in now_list1:  #开始具体取内外组合的实例
                    for k2 in now_list2:
                        if k1 == None:
                            k1 = ""
                        if k2 == None:
                            k2 = ""
                        el = "(" + k1 + ")" + k2
                        l.append(el)
            total_l.append(l)
        return total_l[n]

3. 合并K个有序列表(Hard)

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

1
2
3
4
5
6
7
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

解答：

这道题有多种解法，都可以轻松理解，重要的是掌握和记住。

思路一：暴力解法。

  • 遍历所有链表，将所有节点的值放到一个数组中。
  • 将这个数组排序，然后遍历所有元素得到正确顺序的值。
  • 用遍历得到的值，创建一个新的有序链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        self.nodes = []
        head = point = ListNode(0)
        for l in lists:
            while l:
                self.nodes.append(l.val)
                l = l.next
        for x in sorted(self.nodes):
            point.next = ListNode(x)
            point = point.next
        return head.next

复杂度分析

时间复杂度：$O(N\log N)$ ，其中 $N$ 是节点的总数目。

  1. 遍历所有的值需花费 $O(N)$ 的时间。
  2. 一个稳定的排序算法花费 $O(N\log N)$ 的时间。
  3. 遍历同时创建新的有序链表花费 $O(N)$ 的时间。

空间复杂度：$O(N)$。

  1. 排序花费 $O(N)$ 空间（这取决于你选择的算法）。
  2. 创建一个新的链表花费 $O(N)$ 的空间。

执行用时 :132 ms, 在所有 Python 提交中击败了63.46%的用户

思路二：优先队列（必须掌握）

算法：

  • 比较 k 个节点（每个链表的首节点），获得最小值的节点。
  • 将选中的节点接在最终有序链表的后面。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        import heapq
        dummy = ListNode(0)
        p = dummy
        head = []
        for i in range(len(lists)):
            if lists[i] :
                heapq.heappush(head, (lists[i].val, i))
                lists[i] = lists[i].next
        while head:
            val, idx = heapq.heappop(head)
            p.next = ListNode(val)
            p = p.next
            if lists[idx]:
                heapq.heappush(head, (lists[idx].val, idx))
                lists[idx] = lists[idx].next
        return dummy.next

执行用时 :116 ms, 在所有 Python 提交中击败了79.42%的用户

思路三：分治算法

类似于归并排序

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists:return 
        n = len(lists)
        return self.merge(lists, 0, n-1)
    def merge(self,lists, left, right):
        if left == right:
            return lists[left]
        mid = left + (right - left) // 2
        l1 = self.merge(lists, left, mid)
        l2 = self.merge(lists, mid+1, right)
        return self.mergeTwoLists(l1, l2)
    def mergeTwoLists(self,l1, l2):
        if not l1:return l2
        if not l2:return l1
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

执行用时 :136 ms, 在所有 Python 提交中击败了60.55%的用户

4. 两两交换链表中的节点(Medium)

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

1
给定 1->2->3->4, 你应该返回 2->1->4->3.

解答：

思路一：递归

一眼就看出来要用递归来做。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        tmp = head.next
        head.next = self.swapPairs(head.next.next)
        tmp.next = head
        return tmp

执行用时 :20 ms, 在所有 Python 提交中击败了93.45%的用户

思路二：用loop做，and dummy大法对于nodeList这类题简直无敌。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        cur = dummy = ListNode(-1)
        dummy.next = head        
        while cur.next and cur.next.next:
            one,two,three = cur.next,cur.next.next,cur.next.next.next
            cur.next = two
            two.next = one
            one.next = three
            cur = one
        return dummy.next

执行用时 :12 ms, 在所有 Python 提交中击败了100.00%的用户

5. K个一组翻转链表(Hard)

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例 :

1
2
3
4
5
给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明 :你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

解答：

思路一：递归版本

可以递归操作, 有两种情况：

  1. 就是压根没有k个node，那么我们直接保持这个k-group不动返回head
  2. 如果有k个node的话，那么我们先找到第k个node之后的递归结果 node = nxt，然后反转前面k个node，让反转结果的结尾 tail.next = nxt

也可以这样理解，在解决所有node时，将前k个node和剩余的node分开，剩余的node可以递归调用解决，这样，问题就变成了前k个node链表方向依次反向来解决。

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution(object):
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        cur = head
        cnt = 0
        while cur and cnt != k:
            cur = cur.next
            cnt += 1
        if cnt == k:
            cur = self.reverseKGroup(cur,k)
            while cnt:
                tmp = head.next
                head.next = cur
                cur = head
                head = tmp
                cnt -= 1
            head = cur
        return head

思路二：用堆栈

用栈，我们把 k 个数压入栈中，然后弹出来的顺序就是翻转的！

这里要注意几个问题：

  1. 第一，剩下的链表个数够不够 k 个（因为不够 k 个不用翻转）；

  2. 第二，已经翻转的部分要与剩下链表连接起来

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
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = ListNode(0)
        p = dummy
        while True:
            count = k 
            stack = []
            tmp = head
            while count and tmp:
                stack.append(tmp)
                tmp = tmp.next
                count -= 1
            # 注意,目前tmp所在k+1位置
            # 说明剩下的链表不够k个,跳出循环
            if count : 
                p.next = head
                break
            # 翻转操作
            while stack:
                p.next = stack.pop()
                p = p.next
            #与剩下链表连接起来 
            p.next = tmp
            head = tmp        
        return dummy.next

思路三：尾插法

见本题题解

Veröffentlicht am in

1. 最接近的三数之和(Medium)

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

1
2
3
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

解答：

思路：

排序加双指针。很简单。

  1. 标签：排序和双指针
  2. 本题目因为要计算三个数，如果靠暴力枚举的话时间复杂度会到 $O(n^3)$，需要降低时间复杂度
  3. 首先进行数组排序，时间复杂度 $O(nlogn)$
  4. 在数组 nums 中，进行遍历，每遍历一个值利用其下标i，形成一个固定值 nums[i]
  5. 再使用前指针指向 start = i + 1 处，后指针指向 end = nums.length - 1 处，也就是结尾处
  6. 根据 sum = nums[i] + nums[start] + nums[end] 的结果，判断 sum 与目标 target 的距离，如果更近则更新结果 ans
  7. 同时判断 sum 与 target 的大小关系，因为数组有序，如果 sum > target 则 end–，如果 sum < target 则 start++，如果 sum == target 则说明距离为 0 直接返回结果
  8. 整个遍历过程，固定值为$ n$ 次，双指针为 $n$ 次，时间复杂度为 $O(n^2)$
  9. 总时间复杂度：$O(nlogn) + O(n^2) = O(n^2)$。
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
class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        n = len(nums)
        res = float('inf')
        for i in range(n):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l = i+1
            r = n-1
            while l < r:
                cur = nums[i] + nums[l] + nums[r]
                if cur == target:
                    return target
                if abs(res - target) > abs(cur - target):
                    res = cur
                if cur > target:
                    r -= 1
                if cur < target:
                    l += 1
        return res

思路二：

见提交记录最快的答案。

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
class Solution(object):
    def threeSumClosest(self,nums,target):
        nums.sort()
        length = len(nums)
        closest = []
        for i, num in enumerate(nums[0:-2]):
            l, r = i + 1, length - 1
            
            # different with others' solution
            if num + nums[r] + nums[r - 1] < target:
                closest.append(num + nums[r] + nums[r - 1])
            elif num + nums[l] + nums[l + 1] > target:
                closest.append(num + nums[l] + nums[l + 1])
            else:
                while l < r:
                    closest.append(num + nums[l] + nums[r])
                    if num + nums[l] + nums[r] < target:
                        l += 1
                    elif num + nums[l] + nums[r] > target:
                        r -= 1
                    else:
                        return target

        closest.sort(key=lambda x: abs(x - target))
        return closest[0]

执行用时 :32 ms, 在所有 Python 提交中击败了100.00%的用户

内存消耗 :11.8 MB, 在所有 Python 提交中击败了14.55%的用户

2. 电话号码中的字母组合(Medium)

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

1
2
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

解答：

思路：

回溯算法
回溯是一种通过穷举所有可能情况来找到所有解的算法。如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。

给出如下回溯函数 backtrack(combination, next_digits) ，它将一个目前已经产生的组合 combination 和接下来准备要输入的数字 next_digits 作为参数。

如果没有更多的数字需要被输入，那意味着当前的组合已经产生好了。 如果还有数字需要被输入：遍历下一个数字所对应的所有映射的字母。将当前的字母添加到组合最后，也就是 combination = combination + letter 。 重复这个过程，输入剩下的数字： backtrack(combination + letter, next_digits[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
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        phone = {'2': ['a', 'b', 'c'],
                 '3': ['d', 'e', 'f'],
                 '4': ['g', 'h', 'i'],
                 '5': ['j', 'k', 'l'],
                 '6': ['m', 'n', 'o'],
                 '7': ['p', 'q', 'r', 's'],
                 '8': ['t', 'u', 'v'],
                 '9': ['w', 'x', 'y', 'z']}
        def backtrack(combination,next_digits):
            if len(next_digits) == 0:
                output.append(combination)
            else:
                for char in phone[next_digits[0]]:
                    backtrack(combination+char,next_digits[1:])
        output = []
        if not digits or len(digits) == 0:
            return output
        backtrack('',digits)
        return output

思路二：

每次更新一个字母，类似BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        num2char = {'2':['a','b','c'],
                   '3':['d','e','f'],
                   '4':['g','h','i'],
                   '5':['j','k','l'],
                   '6':['m','n','o'],
                   '7':['p','q','r','s'],
                   '8':['t','u','v'],
                   '9':['w','x','y','z']}    
        if not digits:
            return []
        res = [""]
        for num in digits:
            next_res = []
            for alp in num2char[num]:
                for tmp in res:
                    next_res.append(tmp + alp)
            res = next_res
        return res

执行用时 :16 ms, 在所有 Python 提交中击败了99.12%的用户

3. 四数之和(Medium)

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：答案中不可以包含重复的四元组。

示例：

1
2
3
4
5
6
7
8
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

解答：

思路一：时间复杂度$O(n^3)$，空间复杂度$O(1)$

使用3sum改，固定两个数，活动别的

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
class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        n = len(nums)
        nums.sort()
        res = []
        for i in range(n):
            for j in range(i + 1, n):
                l, r = j + 1, n - 1
                while l < r:
                    temp = nums[i] + nums[j] + nums[l] + nums[r]
                    if temp == target:
                        if [nums[i], nums[j], nums[l], nums[r]] not in res:
                            res.append([nums[i], nums[j], nums[l], nums[r]])
                        l += 1
                        r -= 1
                    elif temp > target:
                        r -= 1
                    else:
                        l += 1
        return res

思路：时间复杂度$O(n^3)$，空间复杂度$O(1)​$

使用双循环固定两个数，用双指针找另外两个数，通过比较与target 的大小，移动指针。里面有一些优化，可以直接看代码，很好理解！所以时间复杂度不超过$O(n^3)$

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
class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        n = len(nums)
        if n < 4:
            return []
        nums.sort()
        res = []
        for i in range(n-3):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:
                break
            if nums[i] + nums[n-1] + nums[n-2] + nums[n-2] < target:
                continue
            for j in range(i+1,n-2):
                if j - i > 1 and nums[j] == nums[j-1]:
                    continue
                if nums[i] + nums[j] + nums[j+1] + nums[j+2] > target:
                    break
                if nums[i] + nums[j] + nums[n-1] + nums[n-2] < target:
                    continue
                l = j+1
                r = n-1
                while l < r:
                    tmp = nums[i] + nums[j] + nums[l] + nums[r]
                    if tmp == target:
                        res.append([nums[i],nums[j],nums[l],nums[r]])
                        while l < r and nums[l] == nums[l+1]:
                            l += 1
                        while l < r and nums[r] == nums[r-1]:
                            r -= 1
                    if tmp > target:
                        r -= 1
                    else:
                        l += 1
        return res

4. 删除链表中倒数第N个节点(Medium)

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

1
2
3
给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：给定的 n 保证是有效的。

解答：

思路一：核心词，dummy head,快慢指针，双指针。

  1. 标签：链表
  2. 整体思路是让前面的指针先移动n步，之后前后指针共同移动直到前面的指针到尾部为止
  3. 首先设立预先指针 pre，预先指针是一个小技巧：对于链表问题，返回结果为头结点时，通常需要先初始化一个预先指针 pre，该指针的下一个节点指向真正的头结点head。使用预先指针的目的在于链表初始化时无可用节点值，而且链表构造过程需要指针移动，进而会导致头指针丢失，无法返回结果。
  4. 设预先指针 pre 的下一个节点指向 head，设前指针为 start，后指针为 end，二者都等于 pre
  5. start 先向前移动n步
  6. 之后 start 和 end 共同向前移动，此时二者的距离为 n，当 start 到尾部时，end 的位置恰好为倒数第 n 个节点
  7. 因为要删除该节点，所以要移动到该节点的前一个才能删除，所以循环结束条件为 start.next != null
  8. 删除后返回 pre.next，为什么不直接返回 head 呢，因为 head 有可能是被删掉的点
  9. 时间复杂度：$O(n)$

切记最后要返回dummy.next而不是head，因为可能删的就是head，例如：

输入链表为[1], n = 1, 应该返回None而不是[1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        slow = fast = dummy = ListNode(-1)
        dummy.next = head
        for i in range(n):
            fast = fast.next
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next

Follow Up

Could you do this in one pass?

思路：把for loop放到while 里面来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        slow = fast = dummy = ListNode(-1)
        dummy.next = head
        count = 0
        while fast.next:
            if count < n:
                count += 1
                fast= fast.next
            else:
                fast = fast.next
                slow = slow.next
        slow.next = slow.next.next
        return dummy.next

5. 有效的括号(Easy)

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

1
2
输入: "()"
输出: true

示例 2:

1
2
输入: "()[]{}"
输出: true

示例 3:

1
2
输入: "(]"
输出: false

示例 4:

1
2
输入: "([)]"
输出: false

示例 5:

1
2
输入: "{[]}"
输出: true

解答：

思路一：利用栈,时间复杂度$O(n)$，空间复杂度$O(n)$

算法

  1. 初始化栈 S。
  2. 一次处理表达式的每个括号。
  3. 如果遇到开括号，我们只需将其推到栈上即可。这意味着我们将稍后处理它，让我们简单地转到前面的 子表达式。
  4. 如果我们遇到一个闭括号，那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的 左括号，那么我们将它从栈中弹出并继续处理。否则，这意味着表达式无效。
  5. 如果到最后我们剩下的栈中仍然有元素，那么这意味着表达式无效。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        mapping = {')':'(','}':'{',']':'['}
        stack = []
        for char in s:
            if char in mapping:
                top_ele = stack.pop() if stack else '#'
                if top_ele != mapping[char]:
                    return False                                
            else:
                stack.append(char)
        return not stack

思路二：时间复杂度$O(n)$，空间复杂度$O(n)$

因为一共只有三种状况”(“ -> “)”, “[“ -> “]”, “{“ -> “}”.

一遇到左括号就入栈，右括号出栈，这样来寻找对应

需要检查几件事：

  • 出现右括号时stack里还有没有东西
  • 出stack时是否对应
  • 最终stack是否为空
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        leftP = '([{'
        rightP = ')]}'
        stack = []
        for char in s:
            if char in leftP:
                stack.append(char)
            if char in rightP:
                if not stack:
                    return False
                tmp = stack.pop()
                if char == ')' and tmp != '(':
                    return False
                if char == ']' and tmp != '[':
                    return False       
                if char == '}' and tmp != '{':
                    return False
        return stack == []

Veröffentlicht am Bearbeitet am in

1. 正则表达式匹配(Hard)

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

1
2
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

  • s 可能为空，且只包含从 a-z 的小写字母。
  • p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
    示例 1:
1
2
3
4
5
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

1
2
3
4
5
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

1
2
3
4
5
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:

1
2
3
4
5
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

1
2
3
4
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

解答：

思路一：

先尝试暴力解法，难点就在 * 身上， * 不会单独出现，它一定是和前面一个字母或"."配成一对。看成一对后"X*"，它的性质就是：要不匹配0个，要不匹配连续的“X”.所以尝试暴力解法的时候一个trick是从后往前匹配.

是这样来分情况看得:

  • 如果s[i] = p[j] 或者 p[j]= '.'： 往前匹配一位
  • 如果p[j] = ' * ', 检查一下，如果这个时候p[j-1] = '.' 或者p[j-1] = s[i] ，那么就往前匹配，如果这样能匹配过，就return True（注意如果这样不能最终匹配成功的话我们不能直接返回False，因为还可以直接忽略' X* '进行一下匹配试试是否可行）， 否则我们忽略 ' X* ',这里注意里面的递推关系
  • 再处理一下边界状况：
    • s已经匹配完了， 如果此时p还有，那么如果剩下的是 X* 这种可以过，所以检查
    • p匹配完毕，如果s还有那么报错
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        def helper(s,i,p,j):
            if j == -1:
                return i == -1
            if i == -1:
                if p[j] != '*':
                    return False
                return helper(s,i,p,j-2)
            if p[j] == '*':
                if p[j-1] == '.' or p[j-1] == s[i]:
                    if helper(s,i-1,p,j):
                        return True
                return helper(s,i,p,j-2)
            if p[j] == '.' or p[j] == s[i]:
                return helper(s,i-1,p,j-1)
            return False
        return helper(s,len(s)-1,p,len(p)-1)

思路二：时间复杂度$O(TP)$，空间复杂度$O(T P)​$

动态规划

因为题目拥有 最优子结构 ，一个自然的想法是将中间结果保存起来。我们通过用 $dp(i,j)$ 表示 $s[i:]$ 和 $p[j:]$ 是否能匹配。我们可以用更短的字符串匹配问题来表示原本的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        dp = [[False] * (len(p)+1) for _ in range(len(s)+1)]
        
        dp[-1][-1] = True
        for i in range(len(s),-1,-1):
            for j in range(len(p)-1,-1,-1):
                first = i<len(s) and p[j] in {s[i],'.'}
                if j+1 < len(p) and p[j+1] == '*':
                    dp[i][j] = dp[i][j+2] or first and dp[i+1][j]
                else:
                    dp[i][j] = first and dp[i+1][j+1]
        
        return dp[0][0]

复杂度分析

时间复杂度：用 $T$ 和$P$ 分别表示匹配串和模式串的长度。对于$i=0, … , T$和 $j=0, … ,P$ 每一个 $dp(i, j)$只会被计算一次，所以后面每次调用都是 $O(1)$ 的时间。因此，总时间复杂度为 $O(TP)$ 。

空间复杂度：我们用到的空间仅有 $O(TP)$ 个 boolean 类型的缓存变量。所以，空间复杂度为 $O(TP)$。

2. 盛最多水的容器(Medium)

给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

img

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例:

1
2
输入: [1,8,6,2,5,4,8,3,7]
输出: 49

解答：

思路：时间复杂度，空间复杂度

双指针法，很简单。

矩阵的面积与两个因素有关：

  1. 矩阵的长度：两条垂直线的距离
  2. 矩阵的宽度：两条垂直线其中较短一条的长度

因此，要矩阵面积最大化，两条垂直线的距离越远越好，两条垂直线的最短长度也要越长越好。

我们设置两个指针 left 和 right，分别指向数组的最左端和最右端。此时，两条垂直线的距离是最远的，若要下一个矩阵面积比当前面积来得大，必须要把 height[left] 和 height[right] 中较短的垂直线往中间移动，看看是否可以找到更长的垂直线。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        left = 0
        right = len(height) - 1
        area = 0      
        while left < right:
            area = max(area,min(height[left], height[right]) * (right - left))
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1         
        return area

3. 整数转罗马数字(Medium)

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

1
2
3
4
5
6
7
8
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如，罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

示例 1:

1
2
输入: 3
输出: "III"

示例 2:

1
2
输入: 4
输出: "IV"

示例 3:

1
2
输入: 9
输出: "IX"

示例 4:

1
2
3
输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例 5:

1
2
3
输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

解答：

思路：时间复杂度$O(n)$，空间复杂度$O(1)$

首先我学习了一下罗马字母是如何表示的。然后感慨，这个阿拉伯数字是多么好的发明

上图基于的是这些个Symbol：

1
2
1    5   10  50  100 500 1000
I    V   X    L   C   D   M

罗马数字表示法见Leetcode 013

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
class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        lookup = {
            1:'I',
            4:'IV',
            5:'V',
            9:'IX',
            10:'X',
            40:'XL',
            50:'L',
            90:'XC',
            100:'C',
            400:'CD',
            500:'D',
            900:'CM',
            1000:'M'     
        }
        res = ''
        for key in sorted(lookup.keys())[::-1]:
            a = num // key
            if a == 0:
                continue
            res += (lookup[key] * a)
            num -= a * key
            if num == 0:
                break
        return res

4. 罗马数字转整数(Easy)

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

1
2
3
4
5
6
7
8
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  1. I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  2. X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  3. C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:

1
2
输入: "III"
输出: 3

示例 2:

1
2
输入: "IV"
输出: 4

示例 3:

1
2
输入: "IX"
输出: 9

示例 4:

1
2
3
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

1
2
3
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

解答：

思路一：时间复杂度$O(n)$，空间复杂度$O(1)$

简单高效

用字典存储各个罗马数字代表的阿拉伯数字

按顺序读取罗马数字，当前数字小于下一个数字，则是下一个数字减去当前数字，否则直接相加

比如IV就是*-1+5=4*，而IIV这种情况是不存在的，对于其他量级的数字也是同理。

实际处理的时候最后一个数字无法和它下一个数字比较，因为不存在下一个数字。

但是最后一个数字永远是加的而不是减的，所以就单独拎出来处理就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        dict = {'I':1,
               'V':5,
               'X':10,
               'L':50,
               'C':100,
               'D':500,
               'M':1000}
        res = 0
        for i,char in enumerate(s[:-1]):
            if dict[char] >= dict[s[i+1]]:
                res += dict[char]
            else:
                res -= dict[char]
        res += dict[s[-1]]
        return res

思路二：

思路 1

  • ```
    罗马数字是最古老的数字表示方式，比阿拉伯数组早2000多年，起源于罗马罗马数字有如下符号：基本字符 I V X L C D M
    对应阿拉伯数字 1 5 10 50 100 500 1000计数规则：
    • 相同的数字连写，所表示的数等于这些数字相加得到的数，例如：III = 3
    • 小的数字在大的数字右边，所表示的数等于这些数字相加得到的数，例如：VIII = 8
    • 小的数字，限于（I、X和C）在大的数字左边，所表示的数等于大数减去小数所得的数，例如：IV = 4,这条规则好像这题不管
    • 正常使用时，连续的数字重复不得超过三次
    • 在一个数的上面画横线，表示这个数扩大1000倍（本题只考虑3999以内的数，所以用不到这条规则）
    • 从前向后遍历罗马数字，如果某个数比前一个数小，则加上该数。反之，减去前一个数的两倍然后加上该数
      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

        integer to Roman 是 Medium，这个roman to integer是easy

        - 从前往后扫描，用一个临时变量记录分段数字。
        - 如果当前比前一个大，说明这一段的值应当是这个值减去上一个值。比如IV = 5-1 =4; 否则，将当前值加入到结果中，然后开始下一段记录，比如VI = 5 + 1, II = 1 +1

      ```python
      class Solution(object):
          def romanToInt(self, s):
              """
              :type s: str
              :rtype: int
              """
              lookup = {
                  'I': 1,
                  'V': 5,
                  'X': 10,
                  'L': 50,
                  'C': 100,
                  'D': 500,
                  'M': 1000
              }
              res = 0
              for i in range(len(s)):
                  if i > 0 and lookup[s[i]] > lookup[s[i-1]]:
                      res += lookup[s[i]] - 2 * lookup[s[i-1]]
                  else:
                      res += lookup[s[i]]
              return res

5. 最长公共前缀(Hard)

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1:

1
2
输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

1
2
3
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。

解答：

**思路一：时间复杂度：$O(S)$**，$S$ 是所有字符串中字符数量的总和。

最坏的情况下，$n$ 个字符串都是相同的。算法会将 $S1$与其他字符串$ [S_2 \ldots S_n]$都做一次比较。这样就会进行 $S$次字符比较，其中$ S$ 是输入数据中所有字符数量。

空间复杂度：$O(1)​$，我们只需要使用常数级别的额外空间。

水平扫描法

首先，我们将描述一种查找一组字符串的最长公共前缀 $LCP(S_1 \ldots S_n)$的简单方法。 我们将会用到这样的结论：

$LCP(S_1 \ldots S_n) = LCP(LCP(LCP(S_1, S_2),S_3),\ldots S_n)$

算法

为了运用这种思想，算法要依次遍历字符串 $[S_1 \ldots S_n]$，当遍历到第$i$个字符串的时候，找到最长公共前缀 $LCP(S_1 \ldots S_i)$。当 $LCP(S_1 \ldots S_i)$是一个空串的时候，算法就结束了。 否则，在执行了 $n$ 次遍历之后，算法就会返回最终答案 $LCP(S_1 \ldots S_n)$。

找到最长公共前缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        
        if len(strs) == 0:
            return ''
        prefix = strs[0]
        for i in range(1,len(strs)):
            while(strs[i].find(prefix) != 0):
                prefix = prefix[0:len(prefix)-1]
                if len(prefix) == 0:
                    return ''
        return prefix

思路二：时间复杂度，空间复杂度

最坏情况下，我们有 $n$ 个长度为 $m$ 的相同字符串。

时间复杂度：$O(S)$，$S$ 是所有字符串中字符数量的总和，$S=m*n$。

时间复杂度的递推式为 $T(n)=2\cdot T(\frac{n}{2})+O(m)$， 化简后可知其就是 $O(S)$。最好情况下，算法会进行 $minLen\cdot n$ 次比较，其中 $minLen$ 是数组中最短字符串的长度。

空间复杂度：$O(m \cdot log(n))$

内存开支主要是递归过程中使用的栈空间所消耗的。 一共会进行 $log(n)$ 次递归，每次需要 $m$ 的空间存储返回结果，所以空间复杂度为 $O(m\cdot log(n))$。

分治法：

这个算法的思路来自于$LCP$操作的结合律。 我们可以发现： $LCP(S_1 \ldots S_n) = LCP(LCP(S_1 \ldots S_k), LCP (S_{k+1} \ldots S_n))$，其中 $LCP(S_1 \ldots S_n)$是字符串$ [S_1 \ldots S_n] $的最长公共前缀，$1 < k < n$。

算法

为了应用上述的结论，我们使用分治的技巧，将原问题 $LCP(S_i\cdots S_j)$ 分成两个子问题 $LCP(S_i\cdots S_{mid})$与$ LCP(S_{mid+1}, S_j)$ ，其中$ mid = \frac{i+j}{2} $ 。 我们用子问题的解 lcpLeft 与 lcpRight 构造原问题的解 $LCP(S_i \cdots S_j)$ 从头到尾挨个比较 lcpLeft 与 lcpRight 中的字符，直到不能再匹配为止。 计算所得的 lcpLeft 与 lcpRight 最长公共前缀就是原问题的解 $LCP(S_i\cdots S_j)$。

寻找最长公共前缀的分治方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if len(strs)==0:
            return ""
        return self.CommonPrefix(strs,0,len(strs)-1)    
    def CommonPrefix(self,strs,l,r):
        if l==r:
            return strs[int(l)]
        else:
            mid=(l+r)//2
            lcpLeft=self.CommonPrefix(strs,l,mid)
            lcpRight=self.CommonPrefix(strs,mid+1,r)
            return self.Prefix(lcpLeft,lcpRight)   
    def Prefix(self,left,right):
        min_=min(len(left),len(right))
        for i in range(min_):
            if left[i]!=right[i]:
                return left[0:i]
        return left[0:min_]

思路三：二分查找

思路四：前缀树

思路五：最强python

1
2
3
4
5
6
7
class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        return os.path.commonprefix(strs)

6. 三数之和(Medium)

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

1
2
3
4
5
6
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解答：

思路一：时间复杂度，空间复杂度

暴力搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        n = len(nums)
        res = []
        nums.sort()
        for i in range(n):
            for j in range(i,n):
                for k in range(j,n):
                    if nums[i] + nums[j] + nums[k] == 0 and j != i and k != j and k != i: 
                        curRes = [nums[i],nums[j],nums[k]]
                        if curRes not in res:
                            res.append(curRes)

        return res

思路二：时间复杂度，空间复杂度

双指针法

固定一个值，找另外二个值它们和等于 0，

如何找另外两个值，用的是双指针。

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
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        res = []
        for i in range(n):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            left = i + 1
            right = n - 1
            while left < right:
                cur_sum = nums[i] + nums[left] + nums[right]
                if cur_sum == 0:
                    tmp = [nums[i],nums[left],nums[right]]
                    res.append(tmp)
                    while left < right and nums[left] == nums[left+1]:
                        left += 1
                    while left < right and nums[right] == nums[right-1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif cur_sum > 0:
                    right -= 1
                else:
                    left += 1
        return res

思路三：

将数组分成正负数，其中一个在正数序列中循环，一个在负数序列中循环，寻求第三个数。

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
class Solution(object):
    def threeSum(self, nums):
        
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        dic = {}
        res = []
        for i in nums:
            if i in dic:
                dic[i] += 1
            else:
                dic[i] = 1
        pos =[i for i in dic if i > 0]
        neg =[i for i in dic if i < 0]
        neg.sort()
        if 0 in dic and dic[0] >= 3:
            res.append([0,0,0])
        for i in pos:
            for j in neg:
                k = -i-j
                if k in dic:
                    if (k==i or k==j) and dic[k] >= 2:
                        res.append([i,k,j])
                    elif i>k>j:
                        res.append([i,k,j])
                    if k < j:
                        break
        return res

此方法运行时间最快。

Veröffentlicht am in

1. 整数反转(Easy)

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例 1:

1
2
输入: 123
输出: 321

示例 2:

1
2
输入: -123
输出: -321

示例 3:

1
2
输入: 120
输出: 21

解答：

思路一：时间复杂度$O(log(n))$，空间复杂度$O(1)$

翻转数字问题需要注意的就是溢出问题，为什么会存在溢出问题呢，我们知道int型的数值范围是 -2147483648～2147483647 (-2^31 ~ 2^31 - 1)， 那么如果我们要翻转 1000000009 这个在范围内的数得到 9000000001，而翻转后的数就超过了范围。

如果输入的是负数，就递归调用原函数，参数变成-x即可

每次得到最后一位digit，并将其作为结果中的当前最高位

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 0:
            return -self.reverse(-x)
        res = 0
        while x:
            res = res * 10 + x%10
            x //= 10
        return res if res <= 0x7fffffff else 0

2. 字符串转换整数(Medium)

请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，qing返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:

1
2
输入: "42"
输出: 42

示例 2:

1
2
3
4
输入: "   -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
     我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

示例 3:

1
2
3
输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。

示例 4:

1
2
3
4
输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
     因此无法执行有效的转换。

示例 5:

1
2
3
4
输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
     因此返回 INT_MIN (−231) 。

解答：

思路一：时间复杂度$O(n)$，空间复杂度$O(1)$

需要考虑比较多的边界条件&特殊情况

  1. 首先输入可能会有空格，所以先去掉空格
  2. 去掉空格后要考虑空字符串情况
  3. 字符串首位可能会有正负号，要考虑
  4. 开始转换成数字，题目说只要遇到非数字就可以break了
  5. 结果太大或者太小超过int限制就要返回特定数字 2147483647 或者 -2147483648
  6. 根据之前的正负号结果返回对应数值
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
class Solution(object):
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        str = str.strip()
        if len(str) == 0:
            return 0
        
        positive = True
        if str[0] == '+' or str[0] == '-':
            if str[0] == '-':
                positive = False
            str = str[1:]
        elif str[0] < '0' or str[0] > '9':
            return 0
        
        res = 0
        for c in str:
            if c >= '0' and c <= '9':
                res = res * 10 + ord(c) - ord('0')
            else:
                break
        if res > 2**31-1:
            if positive == False:
                return -2**31
            else:
                return 2**31-1
        if not positive:
            res = -res
        return res

3. 回文数(Easy)

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

1
2
输入: 121
输出: true

示例 2:

1
2
3
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:

1
2
3
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

解答：

思路一：时间复杂度$O(1)$，空间复杂$O(1)$度

反转一半数字

映入脑海的第一个想法是将数字转换为字符串，并检查字符串是否为回文。但是，这需要额外的非常量空间来创建问题描述中所不允许的字符串。

第二个想法是将数字本身反转，然后将反转后的数字与原始数字进行比较，如果它们是相同的，那么这个数字就是回文。 但是，如果反转后的数字大于$int\ MAX$，我们将遇到整数溢出问题。

按照第二个想法，为了避免数字反转可能导致的溢出问题，为什么不考虑只反转 $ int$数字的一半？毕竟，如果该数字是回文，其后半部分反转后应该与原始数字的前半部分相同。

例如，输入 1221，我们可以将数字 “1221” 的后半部分从 “21” 反转为 “12”，并将其与前半部分 “12” 进行比较，因为二者相同，我们得知数字 1221 是回文。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x < 0 or (x%10 == 0 and x != 0):
            return False
        res = 0
        while x > res:
            res = res * 10 + x%10
            x //= 10
        return x == res or x == res/10

思路二：时间复杂度$O(1)$，空间复杂度$O(1)​$

  • 排除负数

  • 通过字符串进行反转，对比数字是否相等就行

  • class Solution:
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x < 0:
            return False
        elif x != int(str(x)[::-1]):
            return False
        else:
            return True

Veröffentlicht am Bearbeitet am in

1. 寻找两个有序数组的中位数(Hard)

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

1
2
3
4
nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

解答：

*思路一：时间复杂度$O((m+n)log(m+n))$，空间复杂度$O(m+n)$

首先最简单粗暴的方法，就是我们将两个数字列表合并起来，排好序，找到中间的median就ok了，但是千万要注意一点，如果median有两个，需要算平均。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        nums = sorted(nums1 + nums2)
        if len(nums) % 2 == 1:
            return nums[len(nums)//2]
        else:
            return (nums[len(nums)//2-1] + nums[len(nums)//2]) / 2.0

思路二：时间复杂度$O(log(m+n))$，空间复杂度$O(1)$

这时候我们观察到题目给的一个条件，nums1和nums2本身也是有序的，放着这个条件不用反而用思路一是不是有点浪费了？换句话说我们没必要把他们整个排序，于是我们可以把它转化成经典的 findKth问题。

首先转成求A和B数组中第k小的数的问题, 然后用k//2在A和B中分别找。

比如 k = 6, 分别看A和B中的第3个数, 已知 A1 <= A2 <= A3 <= A4 <= A5...和 B1 <= B2 <= B3 <= B4 <= B5..., 如果A3 <＝ B3, 那么第6小的数肯定不会是A1, A2, A3, 因为最多有两个数小于A1(B1, B2), 三个数小于A2(A1, B1, B2), 四个数小于A3(A1, A2, B1, B2)。 关键点是从k//2 开始来找。那就可以排除掉A1, A2, A3, 转成求A4, A5, ... B1, B2, B3, ...这些数中第3小的数的问题, k就被减半了。

当k == 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
27
28
29
30
31
32
33
34
35
36
37
38
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        def findKth(A,B,k):
            if len(A) == 0:
                return B[k-1]
            if len(B) == 0:
                return A[k-1]
            if k == 1:
                return min(A[0],B[0])
            
            a = A[k//2-1] if len(A) >= k // 2 else None
            b = B[k//2-1] if len(B) >= k // 2 else None
            
            # if a is None: 
            #     return findKth(A, B[k // 2:], k - k // 2) # 这里要注意：因为 k//2 不一定等于 (k - k//2)
            # if b is None:
            #     return findKth(A[k // 2:], B, k - k // 2)
            # if a < b:
            #     return findKth(A[k // 2:], B, k - k // 2)
            # else:
            #     return findKth(A, B[k // 2:], k - k // 2)

            if b is None or (a is not None and a < b):
                return findKth(A[k // 2:], B, k - k // 2)
            return findKth(A, B[k // 2:], k - k // 2) 
        
        n = len(nums1) + len(nums2)
        if n % 2 == 1:
            return findKth(nums1,nums2,n//2+1)
        else:
            small = findKth(nums1,nums2,n//2)
            large = findKth(nums1,nums2,n//2+1)
            return (small + large) / 2.0

思路三：时间复杂度$O(log(m+n))$，空间复杂度$O(1)$

findKth 函数我们可以用双指针的方式实现

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
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        def findKth(A, pa, B, pb, k):
            res = 0
            m = 0
            while pa < len(A) and pb < len(B) and m < k:
                if A[pa] < B[pb]:
                    res = A[pa]
                    pa += 1
                else:
                    res = B[pb]
                    pb += 1
                m += 1
            while pa < len(A) and m < k:
                res = A[pa]
                pa += 1
                m += 1
            while pb < len(B) and m < k:
                res = B[pb]
                pb += 1
                m += 1
            return res
        n = len(nums1) + len(nums2)
        if n % 2 == 1:
            return findKth(nums1, 0, nums2, 0, n // 2 + 1)
        else:
            smaller = findKth(nums1, 0, nums2, 0, n // 2)
            bigger = findKth(nums1, 0, nums2, 0, n // 2 + 1)
            return (smaller + bigger) / 2.0

2. 最长回文字串(Medium)

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

1
2
3
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

1
2
输入: "cbbd"
输出: "bb"

解答：

思路一：时间复杂度$O(n^2)$，空间复杂度$O(n^2)​$

动态规划思想：dp[i][j]表示s[i:j+1]是否是palindrome

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        res = ''
        dp = [[False] * len(s) for i in range(len(s))]
        for i in range(len(s),-1,-1):
            for j in range(i,len(s)):
                dp[i][j] = (s[i] == s[j]) and (j-i<3 or dp[i+1][j-1])
                if dp[i][j] and j-i+1>len(res):
                    res = s[i:j+1]
        return res

思路二：时间复杂度$O(n^2)$，空间复杂度$O(1)​$

回文字符串长度为奇数和偶数是不一样的：

  1. 奇数：'xxx s[i] xxx', 比如 'abcdcba'
  2. 偶数：'xxx s[i] s[i+1] xxx', 比如 'abcddcba'

我们区分回文字符串长度为奇数和偶数的情况，然后依次把每一个字符当做回文字符串的中间字符，向左右扩展到满足回文的最大长度，不停更新满足回文条件的最长子串的左右index: l 和r，最后返回s[l:r+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
27
28
29
30
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        l = 0 # left index of the current substring
        r = 0 # right index of the current substring
        max_len = 0 # length of the longest palindromic substring for now
        n = len(s)
        for i in range(n):
            # odd case: 'xxx s[i] xxx', such as 'abcdcba' 
            for j in range(min(i+1, n-i)): # 向左最多移动 i 位，向右最多移动 (n-1-i) 位
                if s[i-j] != s[i+j]: # 不对称了就不用继续往下判断了
                    break
                if 2 * j + 1 > max_len: # 如果当前子串长度大于目前最长长度
                    max_len = 2 * j + 1
                    l = i - j
                    r = i + j

            # even case: 'xxx s[i] s[i+1] xxx', such as 'abcddcba' 
            if i+1 < n and s[i] == s[i+1]:
                for j in range(min(i+1, n-i-1)): # s[i]向左最多移动 i 位，s[i+1]向右最多移动 [n-1-(i+1)] 位
                    if s[i-j] != s[i+1+j]: # 不对称了就不用继续往下判断了
                        break
                    if 2 * j + 2 > max_len:
                        max_len = 2 * j + 2
                        l = i - j
                        r = i + 1 + j
        return s[l:r+1]

思路三：时间复杂度$O(n)$，空间复杂度$O(n)​$

Manacher算法

Useful link

3. Z字形变换(Medium)

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时，排列如下：

1
2
3
L   C   I   R
E T O E S I I G
E   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”LCIRETOESIIGEDHN”。

请你实现这个将字符串进行指定行数变换的函数：

1
string convert(string s, int numRows);

示例 1:

1
2
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"

示例 2:

1
2
3
4
5
6
7
8
9
输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:

L     D     R
E   O E   I I
E C   I H   N
T     S     G

解答：

思路一：时间复杂度$O(n)$，空间复杂度$O(n)​$

idx从0开始，自增直到numRows-1，此后又一直自减到0，重复执行。

给个例子容易懂一些：s = “abcdefghijklmn”, numRows = 4

1
2
3
4
a    g    n 
b  f h  l   m 
c e  i k
d    j

从第一行开始往下，走到第四行又往上走，这里用 step = 1 代表往下走， step = -1代表往上走

因为只会有一次遍历，同时把每一行的元素都存下来，所以时间复杂度和空间复杂度都是 O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows == 1 or len(s) <= numRows:
            return s
        
        res = [''] * numRows
        idx,step = 0,1
        
        for c in s:
            res[idx] += c
            if idx == 0:
                step = 1
            elif idx == numRows - 1:
                step = -1
            idx += step
        return ''.join(res)

思路二：模拟过程

Z字形，就是两种状态，一种垂直向下，还有一种斜向上

控制好边界情况就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if not s:
            return ""
        if numRows == 1:return s
        s_Rows = [""] * numRows
        i  = 0
        n = len(s)
        while i < n:
            for j in range(numRows):
                if i < n:
                    s_Rows[j] += s[i]
                    i += 1
            for j in range(numRows-2,0,-1):
                if i < n:
                    s_Rows[j] += s[i]
                    i += 1
        return "".join(s_Rows)

Veröffentlicht am Bearbeitet am in

1. 两数之和(Easy)

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例：

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]

解答：

思路一：时间复杂度$O(n^2)$，空间复杂度：O(1)

暴力解法，两轮遍历

第一轮取出index为i的数num1，第二轮取出更靠后的index为j的num2

  • 如果第二轮取出的是num1之前的数，其实我们之前已经考虑到这种情况了
  • 如果第二轮再取num1的话，就不符合题目要求了

题目要求只需要找到一种，所以一旦找到就返回。

时间复杂度中的N是代表nums序列的长度。

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i] + nums[j] == target:
                    return [i,j]

思路二：时间复杂度$O(n)$，空间复杂度$O(n)$

上面思路一的时间复杂度太高了，典型的加快时间的方法有牺牲空间换取时间。

我们希望在我们的顺序遍历中取得一个数num1的时候，就知道和它配对的数是否在我们的nums中，并且不单单是存在，比如说target为4，nums 为[2,3]，假设我们此时取得的num1为2，那么和它配对的2确实在nums中，但是数字2在nums中只出现了一次，我们无法取得两次，所以也是不行的。

因此我们有了下面的步骤

  1. 建立字典 lookup 存放第一个数字，并存放该数字的 index
  2. 判断 lookup 中是否存在 target - 当前数字cur， 则当前值cur和某个lookup中的key值相加之和为 target.
  3. 如果存在，则返回： target - 当前数字cur 的 index 与 当前值cur的index
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        lookup = {}
        for i,num in enumerate(nums):
            if target - num in lookup:
                return [lookup[target-num],i]
            else:
                lookup[num] = i

就像之前提到的特殊情况一样，这里注意我们要边遍历边将 num: idx放入lookup中，而不是在做遍历操作之前就将所有内容放入lookup中。

2. 两数相加(Easy)

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

解答：

思路一：时间复杂度$O(n)$，空间复杂度$O(n)$

将l1和l2全部变成数字做加法再换回去呗，这是我们最直接的想法。

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        val1, val2 = [l1.val], [l2.val]

        while l1.next:
            val1.append(l1.next.val)
            l1 = l1.next
        while l2.next:
            val2.append(l2.next.val)
            l2 = l2.next

        # 求出 l1 和 l2 代表的数字
        num1 = ''.join([str(i) for i in val1[::-1]])
        num2 = ''.join([str(i) for i in val2[::-1]])

        # 得到 l1 和 l2 相加之和
        sums = int(num1) + int(num2)

        # 将 sums 转成题目中 linkedlist 所对应的表示形式
        sums = str(sums)[::-1]

        # dummy 作为返回结果
        dummy = head = ListNode(int(sums[0]))
        for i in range(1, len(sums)):
            head.next = ListNode(int(sums[i]))
            head = head.next
        return dummy

思路二：时间复杂度$O(n)$，空间复杂度$O(1)$

因为时间复杂度无法减小，我们一定得遍历完l1和l2的每一位才能得到最终的结果，O(N)没得商量

但是我们可以考虑减小我们的空间复杂度了，刚才我们是将l1和l2全部转回数字，然后用两个列表将他们的数字形式存了下来，这消耗了O(N)的空间。

实际上我们完全可以模拟真正的加法操作，即从个位数开始相加，如果有进位就记录一下，等到十位数相加的时候记得加上那个进位1就可以了，这是我们小学就学过的知识。

那么我们就先处理个位数的相加，然后我们发现处理十位数，百位数和后面的位数都和个位数相加的操作是一个样子的，只不过后面计算的结果乘上10再加上个位数相加的结果，这才是最终的结果。

于是我们就想到了用递归的方法，即一步一步将大问题转化为更小的问题，直到遇到基础情况（这里指的是个位数相加）返回即可。

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1 and not l2:
            return
        elif not (l1 and l2):
            return l1 or l2
        else:
            if l1.val + l2.val < 10:
                l3 = ListNode(l1.val + l2.val)
                l3.next = self.addTwoNumbers(l1.next,l2.next)
            else:
                l3 = ListNode(l1.val+l2.val-10)
                l3.next = self.addTwoNumbers(l1.next,self.addTwoNumbers(l2.next,ListNode(1)))
        return l3

3. 无重复字符的最长字串(Medium)

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

1
2
3
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

思路一：时间复杂度$O(n)$，空间复杂度$O(n)$

求一个最长的字串，里面不带任何重复字符。

假设input为"abcabcbb"，我们先从第一个字符开始，只有一个字符肯定不会重复吧，“a”满足条件，更新最大长度为1，然后走到第二个字符，“ab”也满足，更新最大长度为2，走到第三个字符，“abc”也满足，更新最大长度为3，走到第四个字符，我们发现“a”已经出现过了，于是我们就必须要删除之前的一些字符来继续满足无重复字符的条件，但是我们不知道前面已经出现过一次的“a”的index在哪里呀，所以我们只能一个一个找了，从当前子串的“abca”的第一个字符开始找，删除第一个字符“a”，发现这时候只剩下一个“a”了，我们又满足条件了，更新最大长度为3，以此类推

1
2
3
4
5
6
7
8
9
start
end
 | 
 | 
 v 

 a  b  c  a  b  c  b  b 

end 指针不停往前走，只要当前子串 s[start:end+1] 不满足无重复字符条件的时候，我们就让 start 指针往前走直到满足条件为止，每次满足条件我们都要update一下最大长度，即 res

滑动窗口slide window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        
        start,end = 0,0
        res,lookup = 0,set()
        while start < len(s) and end < len(s):
            if s[end] not in lookup:
                lookup.add(s[end])
                res = max(res,end-start+1)
                end += 1
            else:
                lookup.discard(s[start])
                start += 1
                
        return res

思路二：时间复杂度时间复杂度$O(n)$，空间复杂度$O(n)$

那么为了之后 LeetCode 里面一些类似的题目，我们这里做一个 slide window 的模版，以后就可以重复使用了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        lookup = collections.defaultdict(int)
        l,r,counter,res = 0,0,0,0
        while r < len(s):
            lookup[s[r]] += 1
            if lookup[s[r]] == 1:
                counter += 1
            r += 1
            
            while l < r and counter < r - l:
                lookup[s[l]] -= 1
                if lookup[s[l]] == 0:
                    counter -= 1
                
                l += 1
            res = max(res,r - l)
        return res

思路三：时间复杂度时间复杂度$O(n)$，空间复杂度$O(n)$

刚才思路一中有这样一句话：但是我们不知道前面已经出现过一次的“a”的index在哪里呀，所以我们只能一个一个找了

我们可以对这里做一个优化，就不需要一个个去找了，我们只需要用一个字典，对于当前子串中的每一个字符，将其在input中的来源index记录下来即可

我们先从第一个字符开始，只要碰到已经出现过的字符我们就必须从之前出现该字符的index开始重新往后看。

例如‘xyzxlkjh’，当看到第二个‘x’时我们就应该从第一个x后面的y开始重新往后看了。

我们将每一个已经阅读过的字符作为key，而它的值就是它在原字符串中的index，如果我们现在的字符不在字典里面我们就把它加进字典中去，因此，只要end指针指向的的这个字符c在该字典中的值大于等于了当前子串首字符的index时，就说明c在当前子串中已经出现过了，我们就将当前子串的首字符的index加1，即从后一位又重新开始读，此时当前子串已经满足条件了，然后我们更新res。

程序变量解释

  • start 是当前无重复字符的子串首字符的 index
  • maps 放置每一个字符的 index，如果 maps.get(s[i], -1) 大于等于 start 的话，就说明字符重复了，此时就要重置 res 和 start 的值了
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        maps = {}
        res,start = 0,0
        for i in range(len(s)):
            start = max(start,maps.get(s[i],-1) + 1)
            res = max(res,i - start + 1)
            maps[s[i]] = i
        return res