晨曦微光
0%

Veröffentlicht am Bearbeitet am in

1. 分隔链表(Medium)

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

示例:

1
2
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

解答：

思路：双指针，dummy大法

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(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        p1 = dummy1 = ListNode(-1)
        p2 = dummy2 = ListNode(-1)
        while head:
            if head.val < x:
                p1.next = ListNode(head.val)
                p1 = p1.next
            else:
                p2.next = ListNode(head.val)
                p2 = p2.next
            head = head.next
        p2.next = None
        p1.next = dummy2.next
        return dummy1.next

2. 扰乱字符串(Hard)

给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树。

下图是字符串 s1 = "great" 的一种可能的表示形式。

1
2
3
4
5
6
7
    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

在扰乱这个字符串的过程中，我们可以挑选任何一个非叶节点，然后交换它的两个子节点。

例如，如果我们挑选非叶节点 "gr" ，交换它的两个子节点，将会产生扰乱字符串 "rgeat" 。

1
2
3
4
5
6
7
    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

我们将 "rgeat” 称作 "great" 的一个扰乱字符串。

同样地，如果我们继续将其节点 "eat" 和 "at" 进行交换，将会产生另一个新的扰乱字符串 "rgtae" 。

1
2
3
4
5
6
7
    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

我们将 "rgtae” 称作 "great" 的一个扰乱字符串。

给出两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。

示例 1:

1
2
输入: s1 = "great", s2 = "rgeat"
输出: true

示例 2:

1
2
输入: s1 = "abcde", s2 = "caebd"
输出: false

解答：

思路：递归法，很好理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def isScramble(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if len(s1) != len(s2) or sorted(s1) != sorted(s2):
            return False
        if len(s1) < 4 or s1 == s2:
            return True
        for i in range(1,len(s1)):
            if self.isScramble(s1[:i],s2[:i]) and self.isScramble(s1[i:],s2[i:]):
                return True
            if self.isScramble(s1[:i],s2[-i:]) and self.isScramble(s1[i:],s2[:-i]):
                return True
        return False

3. 合并两个有序数组(Easy)

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

说明:

  • 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
  • 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2中的元素。

示例:

1
2
3
4
5
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

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

解答：

思路：双指针，很简单

合并两个有序数组，从后往前依次读取存储到数组中，减少了空间复杂度

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 merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        p1 = m-1
        p2 = n-1
        p = m+n-1
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] > nums2[p2]:
                nums1[p] = nums1[p1]
                p1 -= 1
            else:
                nums1[p] = nums2[p2]
                p2 -= 1
            p -= 1
        nums1[:p2+1] = nums2[:p2+1]

4. 格雷编码(Medium)

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。

给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入: 2
输出: [0,1,3,2]
解释:
00 - 0
01 - 1
11 - 3
10 - 2

对于给定的 n，其格雷编码序列并不唯一。
例如，[0,2,3,1] 也是一个有效的格雷编码序列。

00 - 0
10 - 2
11 - 3
01 - 1

示例 2:

1
2
3
4
5
输入: 0
输出: [0]
解释: 我们定义格雷编码序列必须以 0 开头。
     给定编码总位数为 n 的格雷编码序列，其长度为 2n。当 n = 0 时，长度为 20 = 1。
     因此，当 n = 0 时，其格雷编码序列为 [0]。

解答：

思路：格雷码的计算公式

image.png

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        res = []
        for i in range(2**n):
            res.append((i>>1)^i)
        return res

5. 子集2(Medium)

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

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

解答：

思路：回溯算法，之后会建一个回溯算法专题专门讲回溯系列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        nums.sort()
        def helper(idx,tmp):
            res.append(tmp)
            for i in range(idx,len(nums)):
                if i > idx and nums[i] == nums[i-1]:
                    continue
                helper(i+1,tmp+[nums[i]])
        helper(0,[])
        return res

6. 解码方法(Medium)

一条包含字母 A-Z 的消息通过以下方式进行了编码：

1
2
3
4
'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

1
2
3
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

1
2
3
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

解答：

思路：动态规划：

$dp(i) = dp(i-1) + dp(i-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
27
class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s or len(s) == 0:
            return 0
        dp = [0] * len(s)
        if s[0] == '0':
            return 0
        else:
            dp[0] = 1
        if len(s) == 1:
            return dp[-1]
        if s[1] !=  '0':
            dp[1] += 1
        if 10 <= int(s[:2]) <= 26:
            dp[1] += 1
        for i in range(2,len(s)):
            if s[i]+s[i-1] == '00':
                return 0
            if s[i] != '0':
                dp[i] += dp[i-1]
            if 10 <= int(s[i-1:i+1]) <= 26:
                dp[i] += dp[i-2]
        return dp[-1]

7. 反转链表2(Medium)

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

1
2
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

解答：

思路：题解区一个解题思路，很简单。

对于链表的问题，根据以往的经验一般都是要建一个dummy node，连上原链表的头结点，这样的话就算头结点变动了，我们还可以通过dummy->next来获得新链表的头结点。这道题的要求是只通过一次遍历完成，就拿题目中的例子来说，变换的是2,3,4这三个点，我们需要找到第一个开始变换结点的前一个结点，只要让pre向后走m-1步即可，为啥要减1呢，因为题目中是从1开始计数的，这里只走了1步，就是结点1，用pre指向它。万一是结点1开始变换的怎么办，这就是我们为啥要用dummy结点了，pre也可以指向dummy结点。然后就要开始交换了，由于一次只能交换两个结点，所以我们按如下的交换顺序：

1 -> 2 -> 3 -> 4 -> 5 -> NULL

1 -> 3 -> 2 -> 4 -> 5 -> NULL

1 -> 4 -> 3 -> 2 -> 5 -> NULL

我们可以看出来，总共需要n-m步即可，第一步是将结点3放到结点1的后面，第二步将结点4放到结点1的后面。这是很有规律的操作，那么我们就说一个就行了，比如刚开始，pre指向结点1，cur指向结点2，然后我们建立一个临时的结点t，指向结点3（注意我们用临时变量保存某个结点就是为了首先断开该结点和前面结点之间的联系，这可以当作一个规律记下来），然后我们断开结点2和结点3，将结点2的next连到结点4上，也就是 cur->next = t->next，再把结点3连到结点1的后面结点（即结点2）的前面，即 t->next = pre->next，最后再将原来的结点1和结点2的连接断开，将结点1连到结点3，即 pre->next = t。这样我们就完成了将结点3取出，加入结点1的后方。第二步将结点4取出，加入结点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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        if not head or m == n:
            return head
        pre = dummy = ListNode(None)
        dummy.next = head
        for i in range(m-1):
            pre = pre.next
        cur = pre.next
        for i in range(n-m):
            tmp = cur.next
            cur.next = tmp.next
            tmp.next = pre.next
            pre.next = tmp
        return dummy.next

8. 复原IP地址(Medium)

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

1
2
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

解答：

思路：回溯算法

在回溯算法专题中详细讲解。

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 restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        res = []
        n = len(s)
        def backtrack(i,tmp,flag):
            if i == n and flag == 0:
                res.append(tmp[:-1])
                return 
            if flag < 0:
                return
            for j in range(i, i+3):
                if j < n:
                    if i == j and s[j] == '0':
                        backtrack(j+1,tmp+s[j]+'.',flag-1)
                        break
                    if 0 < int(s[i:j+1]) <= 255:
                        backtrack(j+1,tmp+s[i:j+1]+'.',flag-1)
        backtrack(0,'',4)
        return res

9. 二叉树的中序遍历(Medium)

给定一个二叉树，返回它的中序 遍历。

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解答：

思路一：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        res = []
        if root.left:
            res += self.inorderTraversal(root.left)
        res.append(root.val)
        if root.right:
            res += self.inorderTraversal(root.right)
        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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        res = []
        stack = []
        p = root
        while p or len(stack):
            while p:
                stack.append(p)
                p = p.left
            if stack:
                p = stack.pop()
                res.append(p.val)
                p = p.right
        return res

同时，附上如何进行前序遍历和后续遍历

前序遍历的两种方式：

递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        res = []
        res.append(root.val)
        res += self.preorderTraversal(root.left)
        res += self.preorderTraversal(root.right)
        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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        res = []
        stack = [root]
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        res = []
        node = root
        stack = []
        while node or len(stack)>0:
            while node:
                stack.append(node)
                res.append(node.val)
                node = node.left
            if len(stack)>0:
                node = stack.pop()
                node = node.right
        return res

后序遍历：**

递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        if not root:
            return res
        res += self.postorderTraversal(root.left)
        res += self.postorderTraversal(root.right)
        res.append(root.val)
        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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        if not root:
            return res
        stack = [root]
        while stack:
            node = stack.pop()
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
            res.append(node.val)
        return res[::-1]

10. 不同的搜索二叉树2(Medium)

给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入: 3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

解答：

思路：递归调用，有意思。

因为知道这是一棵二叉搜索树，所以left.val < root.val < right.val

然后可以任意取一个node作为root，递归调用左边用返回的node作为left，递归调用右边用返回的node作为right

注意考虑n为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
27
28
29
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n == 0:
            return []
        
        def helper(nums):
            if not nums:
                return [None]
            res = []
            for i in range(len(nums)):
                for l in helper(nums[:i]):
                    for r in helper(nums[i+1:]):
                        node = TreeNode(nums[i])
                        node.left = l
                        node.right = r
                        res.append(node)
            return res
        return helper(list(range(1,n+1)))

11. 不同的二叉搜索树(Medium)

​ 给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:

1
2
3
4
5
6
7
8
9
10
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

解答：

思路：动态规划
假设n个节点存在二叉排序树的个数是$G(n)$，令$f(i)$为以$i$为根的二叉搜索树的个数，则
$G(n) = f(1) + f(2) + f(3) + f(4) + … + f(n)$

当$i$为根节点时，其左子树节点个数为$i-1$个，右子树节点为$n-i$，则
$f(i) = G(i-1)*G(n-i)$

综合两个公式可以得到 卡特兰数 公式
$G(n) = G(0)G(n-1)+G(1)(n-2)+…+G(n-1)*G(0)$

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [0] * (n+1)
        dp[0] = 1
        dp[1] = 1
        for i in range(2,n+1):
            for j in range(i):
                dp[i] += dp[j] * dp[i-j-1]
        return dp[-1]

12. 交错字符串(Hard)

给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

示例 1:

1
2
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true

示例 2:

1
2
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false

解答：

思路：动态规划

动态方程:

用$dp[i][j]$表示s1的前i元素和s2前j元素是否交错组成s3前i+j元素

所以有动态方程:

$dp[i][j] = (dp[i-1][j] && s3[i+j-1] == s1[i-1]) || (dp[i][j-1] && s2[j-1] == s3[i+j-1])$

注意:针对第一行,第一列要单独考虑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        if len(s1) +len(s2) != len(s3):
            return False
        dp = [[False] * (len(s2)+1) for _ in range(len(s1)+1)]
        dp[0][0] = True
        for i in range(1,len(s1)+1):
            dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
        for j in range(1,len(s2)+1):
            dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]
        for i in range(1,len(s1)+1):
            for j in range(1,len(s2)+1):
                dp[i][j] = (dp[i-1][j] and s1[i-1]== s3[i+j-1]) or (dp[i][j-1] and s2[j-1]==s3[i+j-1])
        return dp[-1][-1]

13. 验证二叉搜索树(Medium)

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

1
2
3
4
5
输入:
    2
   / \
  1   3
输出: true

示例 2:

1
2
3
4
5
6
7
8
9
输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

解答：

思路一：最大最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def isBST(root,min_val,max_val):
            if not root:
                return True
            if root.val >= max_val or root.val <= min_val:
                return False
            return isBST(root.left,min_val,root.val) and isBST(root.right,root.val,max_val)
        return isBST(root,float('-inf'),float('inf'))

思路二：利用中序遍历比较大小

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 a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        stack = []
        p = root
        pre = None
        while p or stack:
            while p:
                stack.append(p)
                p = p.left
            if stack:
                p = stack.pop()
                if pre and p.val <= pre.val:
                    return False
                pre = p
                p = p.right
        return True

14. 恢复二叉搜索树(Hard)

二叉搜索树中的两个节点被错误地交换。

请在不改变其结构的情况下，恢复这棵树。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入: [1,3,null,null,2]

   1
  /
 3
  \
   2

输出: [3,1,null,null,2]

   3
  /
 1
  \
   2

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

输出: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

进阶:

  • 使用 O(n) 空间复杂度的解法很容易实现。
  • 你能想出一个只使用常数空间的解决方案吗？

解答：

思路：

这道题难点,是找到那两个交换节点,把它交换过来就行了.

这里我们二叉树搜索树的中序遍历(中序遍历遍历元素是递增的)

如下图所示, 中序遍历顺序是 4,2,3,1,我们只要找到节点4和节点1交换顺序即可!

1561339663404.png

这里我们有个规律发现这两个节点:

第一个节点,是第一个按照中序遍历时候前一个节点大于后一个节点,我们选取前一个节点,这里指节点4;

第二个节点,是在第一个节点找到之后, 后面出现前一个节点大于后一个节点,我们选择后一个节点,这里指节点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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        first = second = None
        pre = None
        stack = []
        p = root
        while p or stack:
            while p:
                stack.append(p)
                p = p.left
            if stack:
                p = stack.pop()
            if not first and  pre and pre.val > p.val:
                first = pre
            if first and  pre and pre.val > p.val:
                second = p
            pre = p
            p = p.right
        first.val,second.val = second.val,first.val

15. 相同的树(Easy)

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1:

1
2
3
4
5
6
7
输入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true

示例 2:

1
2
3
4
5
6
7
输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false

示例 3:

1
2
3
4
5
6
7
输入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false

解答：

思路：二叉树算法的基本思路：明确一个节点要做的事情，然后剩下的事抛给框架。

1
2
3
4
5
6
void traverse(TreeNode root) {
    // root 需要做什么？在这做。
    // 其他的不用 root 操心，抛给框架
    traverse(root.left);
    traverse(root.right);
}

举两个简单的例子体会一下这个思路。

如何把二叉树所有的节点中的值加一？

1
2
3
4
5
6
void plusOne(TreeNode root) {
    if (root == null) return;
    		root.val += 1;
		plusOne(root.left);
		plusOne(root.right);
}

本题便是如此：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if not p and not q:
            return True
        if p and q and p.val == q.val:
            return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        return False

Veröffentlicht am Bearbeitet am in

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

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

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

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

示例 1:

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

示例 2:

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

进阶:

  • 这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。
  • 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

解答：

思路：二分法

判断二分点,几种可能性

  1. 直接nums[mid] == target

  2. 当数组为[1,2,1,1,1],nums[mid] == nums[left] == nums[right],需要left++, right –;

  3. 当nums[left]<= nums[mid],说明是在左半边的递增区域

    a. nums[left] <=target < nums[mid],说明target在left和mid之间.我们令right = mid - 1;

    b. 不在之间, 我们令 left = mid + 1;

  4. 当nums[mid] < nums[right],说明是在右半边的递增区域

    a. nums[mid] < target <= nums[right],说明target在mid 和right之间,我们令left = mid + 1

    b. 不在之间,我们令right = mid - 1;

时间复杂度:$O(logn)$

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 search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        l,r = 0,len(nums)-1
        while l <= r:
            mid = (l+r)>>1
            if nums[mid] == target:
                return True
            if nums[mid] == nums[l] == nums[r]:
                l += 1
                r -= 1
            elif nums[mid] >= nums[l]:
                if nums[l] <= target < nums[mid]:
                    r = mid-1
                else:
                    l = mid+1
            else:
                if nums[mid] < target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid-1
        return False

2. 删除排序链表中的重复项2(Medium)

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:

1
2
输入: 1->2->3->3->4->4->5
输出: 1->2->5

示例 2:

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

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        while not head or not head.next:
            return head
        dummy = ListNode(-1)
        dummy.next = head
        slow = dummy
        fast = dummy.next
        while fast:
            if fast.next and fast.val == fast.next.val:
                tmp = fast.val
                while fast and fast.val == tmp:
                    fast = fast.next
            else:
                slow.next = fast
                slow = fast
                fast = fast.next
        slow.next = fast
        return dummy.next

执行用时 :28 ms, 在所有 Python 提交中击败了96.83%

思路二：更省时间的方法是用一个prev 和 cur 指针，这样loop一次即可解决问题。

pre描述重复字段的左起点

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

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        while not head or not head.next:
            return head
        dummy = cur = pre = ListNode(None)
        while head:
            while head and ((head.val == pre.val) or (head.next and head.val == head.next.val)):
                pre = head
                head = head.next
            cur.next = head
            cur = cur.next
            if head:
                head = head.next
        return dummy.next

3. 删除排序链表中的重复项(Easy)

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

1
2
输入: 1->1->2
输出: 1->2

示例 2:

1
2
输入: 1->1->2->3->3
输出: 1->2->3

解答：

思路：dummy大法

很简单啊，dummy大法在解决这种链表问题上，很有用。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy = head
        while head:
            while head.next and head.next.val == head.val:
                head.next = head.next.next    # skip duplicated node
            head = head.next     # not duplicate of current node, move to next node
        return dummy

4. 柱状图中最大的矩形(Medium)

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

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

解答：

思路：

暴力解法$O(n^2)$

超时，很简单。

首先，要想找到第 i 位置最大面积是什么？

是以i 为中心，向左找第一个小于 heights[i] 的位置 left_i；向右找第一个小于于 heights[i] 的位置 right_i，即最大面积为 heights[i] * (right_i - left_i -1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        res = 0
        n = len(heights)
        for i in range(n):
            l = i
            r = i
            while l >= 0 and heights[l] >= heights[i]:
                l -= 1
            while r < n and heights[r] >= heights[i]:
                r += 1
            res = max(res,heights[i]*(r-l-1))
        return res

暴力解法2:思路很简单，同样也超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        res = 0
        n = len(heights)
        for i in range(n):
            minHeight = float('inf')
            for j in range(i,n):
                minHeight = min(minHeight,heights[j])
                res = max(res,minHeight*(j-i+1))
        return res

思路三：这个题是真的难。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        stack = [-1]
        res = 0
        n = len(heights)
        for i in range(n):
            while stack[-1] != -1 and heights[stack[-1]] >= heights[i]:
                tmp = stack.pop()
                res = max(res,heights[tmp] * (i-stack[-1]-1))
            stack.append(i)
        while stack[-1] != -1:
            tmp = stack.pop()
            res = max(res,heights[tmp]*(n-stack[-1]-1))
        return res

我个人觉得，下面这个解答，更容易理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        heights.append(0)
        area, stack = 0, [-1]
        for idx, height in enumerate(heights):
            while height < heights[stack[-1]]:
                h = heights[stack.pop()]
                w = idx - stack[-1] - 1
                area = max(w*h, area)
            stack.append(idx)
        return area

5. 最大矩形(Hard)

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例:

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

解答：

思路：

巧用上一题的思路，分行读取，每一行高度累积到一个长度为col的数组中，

将问题转化为上一题的意思。

每一行都执行一遍84题

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 maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix or not matrix[0]:
            return 0
        row = len(matrix)
        col = len(matrix[0])
        height = [0] * (col+2)
        res = 0
        for i in range(row):
            stack = []
            for j in range(col+2):
                if 1<= j<=col:
                    if matrix[i][j-1] == '1':
                        height[j] += 1
                    else:
                        height[j] = 0
                while stack and height[stack[-1]] > height[j]:
                    cur = stack.pop()
                    res = max(res,(j-stack[-1]-1)*height[cur])
                stack.append(j)
        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
31
32
33
34
35
36
37
38
39
40
class Solution(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix or not matrix[0]:
            return 0
        row = len(matrix)
        col = len(matrix[0])
        left = [-1]*col
        right = [col]*col
        height = [0]*col
        res = 0
        for i in range(row):
            cur_l = -1
            cur_r = col
            for j in range(col):
                if matrix[i][j] == '1':
                    height[j] += 1
                else:
                    height[j] = 0
                    
            for j in range(col):
                if matrix[i][j] == '1':
                    left[j] = max(left[j],cur_l)
                else:
                    left[j] = -1
                    cur_l = j
            
            for j in range(col-1,-1,-1):
                if matrix[i][j] == '1':
                    right[j] = min(right[j],cur_r)
                else:
                    right[j] = col
                    cur_r = j
            
            for j in range(col):
                res = max(res,(right[j] - left[j] - 1)*height[j])
        return res

Veröffentlicht am Bearbeitet am in

1. 最小覆盖子串(Hard)

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

示例：

1
2
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

说明：

  • 如果 S 中不存这样的子串，则返回空字符串 ""。
  • 如果 S 中存在这样的子串，我们保证它是唯一的答案。

解答：

思路：滑动窗口算法

本问题要求我们返回字符串S 中包含字符串T的全部字符的最小窗口。我们称包含T的全部字母的窗口为可行窗口。

可以用简单的滑动窗口法来解决本问题。

在滑动窗口类型的问题中都会有两个指针。一个用于延伸现有窗口的 right指针，和一个用于收缩窗口的left 指针。在任意时刻，只有一个指针运动，而另一个保持静止。

本题的解法很符合直觉。我们通过移动right指针不断扩张窗口。当窗口包含全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。

答案是最小的可行窗口。

  1. 初始，left指针和right指针都指向S的第一个元素.
1
2
3
for c in t:
    lookup[c] += 1
left = right = 0
  1. 将 right 指针右移，扩张窗口，直到得到一个可行窗口，亦即包含T的全部字母的窗口。
1
2
3
4
5
while right < len(s):
        if lookup[s[right]] > 0:
            count -= 1
        lookup[s[right]] -= 1
        right += 1
  1. 得到可行的窗口后，将left指针逐个右移，若得到的窗口依然可行，则更新最小窗口大小。
1
2
3
4
5
6
7
8
while count == 0:
          if min_len > right-left:
              min_len = right-left
              res = s[left:right]
          if lookup[s[left]] == 0:
              count += 1
          lookup[s[left]] += 1
          left += 1
  1. 若窗口不再可行，则跳转至 2。
1
2
3
4
5
6
7
8
9
10
11
12
13
while right < len(s):
    if lookup[s[right]] > 0:
        count -= 1
    lookup[s[right]] -= 1
    right += 1
    while count == 0:
        if min_len > right-left:
            min_len = right-left
            res = s[left:right]
        if lookup[s[left]] == 0:
            count += 1
        lookup[s[left]] += 1
        left += 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
class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        from collections import defaultdict
        lookup = defaultdict(int)
        for c in t:
            lookup[c] += 1
        left = right = 0
        min_len = float('inf')
        count = len(t)
        res = ''
        while right < len(s):
            if lookup[s[right]] > 0:
                count -= 1
            lookup[s[right]] -= 1
            right += 1
            while count == 0:
                if min_len > right-left:
                    min_len = right-left
                    res = s[left:right]
                if lookup[s[left]] == 0:
                    count += 1
                lookup[s[left]] += 1
                left += 1
        return res

2. 组合(Medium)

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

1
2
3
4
5
6
7
8
9
10
输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

解答：

*思路：回溯算法

回溯法 是一种通过遍历所有可能成员来寻找全部可行解的算法。若候选 不是 可行解 (或者至少不是 最后一个 解)，回溯法会在前一步进行一些修改以舍弃该候选，换而言之， 回溯 并再次尝试。

这是一个回溯法函数。

它将第一个添加到组合中的数和现有的组合作为参数。 backtrack(first, curr)

  1. 若组合完成- 添加到输出中。
  2. 遍历从 first t到 n的所有整数。
    • 将整数 i 添加到现有组合 curr中。
    • 继续向组合中添加更多整数 : backtrack(i + 1, curr)。
    • 将 i 从 curr中移除，实现回溯。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def backtrack(first = 1, curr = []):
            if len(curr) == k:  
                output.append(curr[:])
            for i in range(first, n + 1):
                curr.append(i)
                backtrack(i + 1, curr)
                curr.pop()
        
        output = []
        backtrack()
        return output

下面是我的解答，上面是官方的解答。

异曲同工。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        res = []
        def helper(i,k,tmp):
            if k == 0:
                res.append(tmp)
            for j in range(i,n+1):
                helper(j+1,k-1,tmp+[j])
        helper(1,k,[])
        return res

3. 子集(Medium)

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解答：

思路：回溯算法

思考方式很简单，从0和[]出发，逐步加上每一个元素，递归式的扩展下去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        n = len(nums)
        def helper(i,tmp):
            res.append(tmp)
            for j in range(i,n):
                helper(j+1,tmp+[nums[j]])
        helper(0,[])
        return res

思路二：迭代

当然还有更加简单明显的迭代算法

1
2
3
4
5
6
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        for i in nums:
            res = res + [[i] + num for num in res]
        return res

4. 单词搜索(Medium)

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

1
2
3
4
5
6
7
8
9
10
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

解答：

思路：回溯算法+DFS

这道题一看就很简单，回溯加DFS，这两个几乎都是同时出现的。

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 exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        if not board:
            return False
        if not word:
            return True
        row = len(board)
        col = len(board[0]) if row else 0
        def dfs(i,j,idx):
            if not 0<=i<row or not 0<=j<col or board[i][j] != word[idx]:
                return False
            if idx == len(word) - 1:
                return True
            board[i][j] = '*'
            res = dfs(i+1,j,idx+1) or dfs(i-1,j,idx+1) or dfs(i,j+1,idx+1) or dfs(i,j-1,idx+1)
            board[i][j] = word[idx]
            return res
        return any(dfs(i,j,0) for i in range(row) for j in range(col))

5. 删除排序数组中的重复项(Medium)

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

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

示例 1:

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

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

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

示例 2:

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

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

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

说明:

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

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

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

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
class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        for n in nums:
            if i < 2 or n != nums[i-2]:
                nums[i] = n
                i += 1
        return i

此题可以有通用模板，将2改成k的话：

1
2
3
4
5
6
7
8
class Solution:
    def removeDuplicates(self, nums， k):
        i = 0
        for n in nums:
            if i < k or n != nums[i-k]:
                nums[i] = n
                i += 1
        return i

Veröffentlicht am in

1. 简化路径(Medium)

以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径

请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。

示例 1：

1
2
3
输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。

示例 2：

1
2
3
输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。

示例 3：

1
2
3
输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：

1
2
输入："/a/./b/../../c/"
输出："/c"

示例 5：

1
2
输入："/a/../../b/../c//.//"
输出："/c"

示例 6：

1
2
输入："/a//b////c/d//././/.."
输出："/a/b/c"

解答：

思路：

非常简单的模拟题，利用一个栈来储存当前的路径。用 “/“ 将输入的全路径分割成多个部分，对于每一个部分循环处理：如果为空或者 “.” 则忽略，如果是 “..” ，则出栈顶部元素（如果栈为空则忽略），其他情况直接压入栈即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def simplifyPath(self, path):
        """
        :type path: str
        :rtype: str
        """
        stack = []
        for item in path.split('/'):
            if item and item != '.':
                if item == '..':
                    if stack:
                        stack.pop()
                else:
                    stack.append(item)
        if not stack:
            return '/'
        else:
            return '/' +'/'.join(stack)

2. 编辑距离(Hard)

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  1. 插入一个字符
  2. 删除一个字符
  3. 替换一个字符

示例 1:

1
2
3
4
5
6
输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

1
2
3
4
5
6
7
8
输入: word1 = "intention", word2 = "execution"
输出: 5
解释: 
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

解答：

思路：动态规划

其实这个题很简单。如果你学过编辑距离的话。

就是一个动态规划。

dp(i,j) = min(dp(i-1,j)+1,dp(i,j-1)+1,dp(i-1,j-1 + tmp))

Tmp = 0 if w[i] == s[j] else 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        n = len(word1)
        m = len(word2)
        if n == 0 or m == 0:
            return max(n,m)
        dp = [[i+j for j in range(m+1)] for i in range(n+1)]
        for i in range(1,n+1):
            for j in range(1,m+1):
                tmp = 0 if word1[i-1] == word2[j-1] else 1
                dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+tmp)
        return dp[-1][-1]

3. 矩阵置零(Medium)

给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
输入: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
输入: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

进阶:

  • 一个直接的解决方案是使用 O(m**n) 的额外空间，但这并不是一个好的解决方案。
  • 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
  • 你能想出一个常数空间的解决方案吗？

解答：

思路一：

如果矩阵中任意一个格子有零我们就记录下它的行号和列号，这些行和列的所有格子在下一轮中全部赋为零。

算法

  1. 我们扫描一遍原始矩阵，找到所有为零的元素。
  2. 如果我们找到 [i, j] 的元素值为零，我们需要记录下行号 i 和列号 j。
  3. 用两个 sets ，一个记录行信息一个记录列信息。
  4. 最后，我们迭代原始矩阵，对于每个格子检查行 r 和列 c 是否被标记过，如果是就将矩阵格子的值设为 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        row = len(matrix)
        col = len(matrix[0])
        rows,cols = set(),set()
        
        for i in range(row):
            for j in range(col):
                if matrix[i][j] == 0:
                    rows.add(i)
                    cols.add(j)
        for i in range(row):
            for j in range(col):
                if i in rows or j in cols:
                    matrix[i][j] = 0

思路二：常数空间

关键思想: 用matrix第一行和第一列记录该行该列是否有0,作为标志位

但是对于第一行,和第一列要设置一个标志位,为了防止自己这一行(一列)也有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
27
28
29
30
31
32
33
34
35
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        row = len(matrix)
        col = len(matrix[0])
        row0_flag = False
        col0_flag = False
        # 找第一行是否有0
        for j in range(col):
            if matrix[0][j] == 0:
                row0_flag = True
                break
        # 第一列是否有0
        for i in range(row):
            if matrix[i][0] == 0:
                col0_flag = True
                break
        # 把第一行或者第一列作为 标志位
        for i in range(1, row):
            for j in range(1, col):
                if matrix[i][j] == 0:
                    matrix[i][0] = matrix[0][j] = 0
                    
        for i in range(1, row):
            for j in range(1, col):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
        if row0_flag:
            for j in range(col):
                matrix[0][j] = 0
        if col0_flag:
            for i in range(row):
                matrix[i][0] = 0

4. 搜索二维矩阵(Medium)

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

示例 1:

1
2
3
4
5
6
7
8
输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
输出: true

示例 2:

1
2
3
4
5
6
7
8
输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
输出: false

解答：

思路：很明显用二分法，不假思索。

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 searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix or not matrix[0]:
            return False
        row = len(matrix)
        col = len(matrix[0])
        l,r = 0,row*col-1
        while l <= r:
            mid = (l+r)>>1
            value = matrix[mid//col][mid%col]
            if target == value:
                return True
            elif target < value:
                r = mid -1
            else:
                l = mid + 1
        return False

5. 颜色分类(Medium)

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

注意:
不能使用代码库中的排序函数来解决这道题。

示例:

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

进阶：

  • 一个直观的解决方案是使用计数排序的两趟扫描算法。
    首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
  • 你能想出一个仅使用常数空间的一趟扫描算法吗？

解答：

思路：

以前见过这道题，第一时间想到双指针，但是没办法记录当前指针位置。

所以很明显，三指针法。

我们用三个指针（begin, end 和curr）来分别追踪0的最右边界，2的最左边界和当前考虑的元素。

这里是用三个指针，begin, cur, end，cur需要遍历整个数组

  • cur 指向0，交换begin与cur， begin++,cur++
  • cur 指向1，不做任何交换，cur++
  • cur 指向2，交换end与cur，end–
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        p0 = curr = 0
        p2 = len(nums) - 1
        while curr <= p2:
            if nums[curr] == 0:
                nums[p0],nums[curr] = nums[curr],nums[p0]
                p0 += 1
                curr += 1
            elif nums[curr] == 2:
                nums[p2],nums[curr] = nums[curr],nums[p2]
                p2 -= 1
            else:
                curr += 1

几个易错点：

  1. 一定要按照这个顺序来比较，先比较0，再比较2，再比较1，具体可以灵活，需要自己领悟。
  2. 一定是if-elif-else的顺序

思路二：

考虑数字和index之间的关系，从而替换数字。

这个思路明显，很巧妙。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        n0, n1, n2 = -1, -1, -1
        for i in range(len(nums)):
            if nums[i] == 0:
                n0, n1, n2 = n0+1, n1+1, n2+1
                nums[n2] = 2
                nums[n1] = 1
                nums[n0] = 0
            elif nums[i] == 1:
                n1, n2 = n1+1, n2+1
                nums[n2] = 2
                nums[n1] = 1
            else:
                n2 += 1
                nums[n2] = 2

Veröffentlicht am in

1. 加一(Easy)

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:

1
2
3
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。

示例 2:

1
2
3
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

解答：

思路一：递归

这里是用的递归，很容易理解，如果空列表直接加1，最后一位小于9，那么直接就最后一位加1，否则添加一个0，然后再把余下的递归加1

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        if not digits:
            return [1]
        if digits[-1] < 9:
            return digits[:-1]+[digits[-1]+1]
        else:
            return self.plusOne(digits[:-1])+[0]

思路二：

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        carry = 1
        for i in range(len(digits)-1,-1,-1):
            digits[i] += carry
            if digits[i] < 10:
                carry = 0
                break
            else:
                digits[i] = 0
        return [1] + digits if carry == 1 else digits

迭代用时比递归慢。。。。

2. 二进制求和(Easy)

给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

示例 1:

1
2
输入: a = "11", b = "1"
输出: "100"

示例 2:

1
2
输入: a = "1010", b = "1011"
输出: "10101"

解答：

思路：

这个就比较简单，递归。

考虑是否进位。然后递归结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        if a == '' or b == '':
            return a+b
        if a[-1] == '0' and b[-1] == '0':
            return self.addBinary(a[:-1],b[:-1]) +'0'
        elif a[-1] == '1' and b[-1] == '1':
            return self.addBinary(a[:-1],self.addBinary(b[:-1],'1')) + '0'
        else:
            return self.addBinary(a[:-1],b[:-1]) + '1'

3. 文本左右对齐(Hard)

给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

说明:

  • 单词是指由非空格字符组成的字符序列。
  • 每个单词的长度大于 0，小于等于 maxWidth。
  • 输入单词数组 words 至少包含一个单词。

示例:

1
2
3
4
5
6
7
8
9
输入:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
输出:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
输入:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
输出:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
     因为最后一行应为左对齐，而不是左右两端对齐。       
     第二行同样为左对齐，这是因为这行只包含一个单词。

示例 3:

1
2
3
4
5
6
7
8
9
10
11
12
13
输入:
words = ["Science","is","what","we","understand","well","enough","to","explain",
         "to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20
输出:
[
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]

解答：

思路：

这道题确实难。

解答和思考过程参考题解部分。

思路:
首先要理顺题意,给定一堆单词,让你放在固定长度字符串里

  1. 两个单词之间至少有一个空格,如果单词加空格长度超过maxWidth,说明该单词放不下,比如示例1:当我们保证this is an 再加入example变成this is an example总长度超过maxWidth,所以这一行只能放下this is an 这三个单词;
  2. this is an长度小于maxWidth,我们考虑分配空格,并保证左边空格数大于右边的
  3. 最后一行,要尽量靠左,例如示例2的:”shall be “

我们针对上面三个问题,有如下解决方案.

  1. 先找到一行最多可以容下几个单词;
  2. 分配空格,例如this is an ,对于宽度为maxWidth,我们可以用maxWidth - all_word_len 与需要空格数商为 单词间 空格至少的个数,余数是一个一个分配给左边.就能保证左边空格数大于右边的.例如 16 - 8 = 8 ,a = 8 / 2, b = 8 % 2两个单词间要有4个空格,因为余数为零不用分配;
  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 fullJustify(self, words, maxWidth):
        """
        :type words: List[str]
        :type maxWidth: int
        :rtype: List[str]
        """
        res = []
        n = len(words)
        i = 0
        def one_row_words(i):
            left = i
            cur_row = len(words[i])
            i += 1
            while i < n:
                if cur_row + len(words[i]) + 1 > maxWidth:
                    break
                cur_row += len(words[i]) + 1
                i += 1
            return left,i
        while i < n:
            left,i = one_row_words(i)
            one_row = words[left:i]
            if i == n:
                res.append(' '.join(one_row).ljust(maxWidth,' '))
                break
            all_word_len = sum(len(i) for i in one_row)
            space_num = i - left - 1
            remain_space = maxWidth - all_word_len 
            if space_num:
                a,b = divmod(remain_space,space_num)
            tmp = ''
            for word in one_row:
                if tmp:
                    tmp += ' '*a
                    if b:
                        tmp += ' '
                        b -= 1
                tmp += word
            res.append(tmp.ljust(maxWidth,' '))
        return res

4. x的平方根(Easy)

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

1
2
输入: 4
输出: 2

示例 2:

1
2
3
4
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

解答：

思路：很明显，就是二分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if  x == 0:
            return 0
        if x == 1:
            return 1
        l ,r = 0,x-1
        while l <= r:
            mid = l +((r-l)>>1)
            if mid * mid <= x and (mid+1) * (mid +1) > x:
                return mid
            elif mid * mid <x:
                l = mid + 1
            else:
                r = mid - 1

思路二：牛顿法

image.png

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        t = x
        while t * t >x:
            t = (t + x/t)/2
        return t

5. 爬楼梯(Easy)

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

1
2
3
4
5
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

1
2
3
4
5
6
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

解答：

思路：动态规划

很明显。dp(n) =dp(n-1) + dp(n-2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        a = 1
        b = 2
        if n == 1:
            return 1
        if n == 2:
            return 2
        for i in range(2,n):
            a,b = b,a+b
        return b

Veröffentlicht am Bearbeitet am

1. 旋转链表(Medium)

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

1
2
3
4
5
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

1
2
3
4
5
6
7
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

解答：

思路：

链表中的点已经相连，一次旋转操作意味着：

  • 先将链表闭合成环
  • 找到相应的位置断开这个环，确定新的链表头和链表尾

新的链表头在哪里？

  • 在位置 n-k 处，其中 n 是链表中点的个数，新的链表尾就在头的前面，位于位置 n-k-1。

  • 我们这里假设 k < n

  • 如果 k >= n 怎么处理？

  • k 可以被写成 k = (k // n) * n + k % n 两者加和的形式，其中前面的部分不影响最终的结果，因此只需要考虑 k%n 的部分，这个值一定比 n 小。

算法

算法实现很直接：

  1. 找到旧的尾部并将其与链表头相连 old_tail.next = head，整个链表闭合成环，同时计算出链表的长度 n。
  2. 找到新的尾部，第 (n - k % n - 1) 个节点 ，新的链表头是第 (n - k % n) 个节点。
  3. 断开环 new_tail.next = None，并返回新的链表头 new_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
28
29
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head:
            return None
        if not head.next:
            return head
        old_tail = head
        n = 1
        while old_tail.next:
            old_tail = old_tail.next
            n += 1
        old_tail.next = head
        new_tail = head
        for i in range(n-k%n-1):
            new_tail = new_tail.next
        new_head = new_tail.next
        new_tail.next = None
        return new_head

2. 不同路径(Medium)

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m 和 n 的值均不超过 100。

示例 1:

1
2
3
4
5
6
7
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:

1
2
输入: m = 7, n = 3
输出: 28

解答：

思路一：动态规划

很简单。

在考虑dp(m,n)时，可以从上方dp(m,n-1)来，也可以从左边dp(m-1,n)来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        if m<1 or n<1:
            return 0
        dp = [[1] * m for i in range(n)]
        for i in range(1,n):
            for j in range(1,m):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]

思路二：降低空间复杂度的动态规划

好像所有的动态规划都可以做到空间复杂度降低。

优化：因为我们每次只需要 dp[i-1][j],dp[i][j-1]

所以我们只要记录这两个数，直接看代码吧！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        if m<1 or n<1:
            return 0
        cur = [1]*n
        for i in range(1,m):
            for j in range(1,n):
                cur[j] += cur[j-1]
        return cur[-1]

思路三：数学方法

因为机器到底右下角，向下几步，向右几步都是固定的，

比如，m=3, n=2，我们只要向下 1 步，向右 2 步就一定能到达终点。

所以有$ C_{m+n-2}^{m-1}$

1
2
def uniquePaths(self, m: int, n: int) -> int:
        return int(math.factorial(m+n-2)/math.factorial(m-1)/math.factorial(n-1))

3. 不同路径2(Medium)

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m 和 n 的值均不超过 100。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
输入:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

解答：

思路一：递归+DFS

很简单，很明显，但是超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        self.res = 0
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        def travel(x,y):
            if x == m-1 and y == n-1 and obstacleGrid[x][y] != 1:
                self.res += 1
            if x +1 < m and obstacleGrid[x+1][y] != 1:
                travel(x+1,y)
            if y+1 < n and obstacleGrid[x][y+1] != 1:
                travel(x,y+1)
        if obstacleGrid[0][0] == 1:
            return 0
        travel(0,0)
        return self.res

思路二：动态规划

算法

  1. 如果第一个格点 obstacleGrid[0,0] 是 1，说明有障碍物，那么机器人不能做任何移动，我们返回结果 0。
  2. 否则，如果 obstacleGrid[0,0] 是 0，我们初始化这个值为 1 然后继续算法。
  3. 遍历第一行，如果有一个格点初始值为 1 ，说明当前节点有障碍物，没有路径可以通过，设值为 0 ；否则设这个值是前一个节点的值 obstacleGrid[i,j] = obstacleGrid[i,j-1]。
  4. 遍历第一列，如果有一个格点初始值为 1 ，说明当前节点有障碍物，没有路径可以通过，设值为 0 ；否则设这个值是前一个节点的值 obstacleGrid[i,j] = obstacleGrid[i-1,j]。
  5. 现在，从 obstacleGrid[1,1] 开始遍历整个数组，如果某个格点初始不包含任何障碍物，就把值赋为上方和左侧两个格点方案数之和 obstacleGrid[i,j] = obstacleGrid[i-1,j] + obstacleGrid[i,j-1]。
  6. 如果这个点有障碍物，设值为 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
class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        if not obstacleGrid or not obstacleGrid[0]:
            return 0
        row = len(obstacleGrid)
        col = len(obstacleGrid[0])
        dp = [[0]*col for _ in range(row)]
        dp[0][0] = 1 if obstacleGrid[0][0] != 1 else 0
        if dp[0][0]==0:
            return 0
        for j in range(1,col):
            if obstacleGrid[0][j] != 1:
                dp[0][j] = dp[0][j-1]
        for i in range(1,row):
            if obstacleGrid[i][0] != 1:
                dp[i][0] = dp[i-1][0]
        for i in range(1,row):
            for j in range(1,col):
                if obstacleGrid[i][j] != 1:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]

4. 最小路径和(Medium)

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

1
2
3
4
5
6
7
8
输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

解答：

思路：动态规划

很简单的一道题

我们新建一个额外的 dp 数组，与原矩阵大小相同。在这个矩阵中，dp(i, j)表示从坐标 (i, j) 到右下角的最小路径权值。我们初始化右下角的 dp 值为对应的原矩阵值，然后去填整个矩阵，对于每个元素考虑移动到右边或者下面，因此获得最小路径和我们有如下递推公式：

$dp(i, j)= \mathrm{grid}(i,j)+\min\big(dp(i-1,j),dp(i,j-1)\big)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid:
            return 0
        row = len(grid)
        col = len(grid[0])
        dp = [[0] * col for _ in range(row)]
        dp[0][0] = grid[0][0]
        for j in range(1,col):
            dp[0][j] = grid[0][j]+dp[0][j-1]
        for i in range(1,row):
            dp[i][0] = grid[i][0]+dp[i-1][0]
        for i in range(1,row):
            for j in range(1,col):
                dp[i][j] = grid[i][j] + min(dp[i-1][j],dp[i][j-1])
        return dp[-1][-1]

当然，必存在可节约空间的做法。

稍后奉上。

5. 有效数字(Hard)

验证给定的字符串是否可以解释为十进制数字。

例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
"0"` => `true`
`" 0.1 "` => `true`
`"abc"` => `false`
`"1 a"` => `false`
`"2e10"` => `true`
`" -90e3   "` => `true`
`" 1e"` => `false`
`"e3"` => `false`
`" 6e-1"` => `true`
`" 99e2.5 "` => `false`
`"53.5e93"` => `true`
`" --6 "` => `false`
`"-+3"` => `false`
`"95a54e53"` => `false

说明: 我们有意将问题陈述地比较模糊。在实现代码之前，你应当事先思考所有可能的情况。这里给出一份可能存在于有效十进制数字中的字符列表：

  • 数字 0-9
  • 指数 - “e”
  • 正/负号 - “+”/“-“
  • 小数点 - “.”

当然，在输入中，这些字符的上下文也很重要。

更新于 2015-02-10:
C++函数的形式已经更新了。如果你仍然看见你的函数接收 const char * 类型的参数，请点击重载按钮重置你的代码。

解答：

思路一：暴力枚举

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 isNumber(self, s: str):
        s = s.strip()
        #print(s)
        dot_seen = False
        e_seen = False
        num_seen = False
        for i, a in enumerate(s):
            if a.isdigit():
                num_seen = True
            elif a == ".":
                if e_seen or dot_seen:
                    return False
                dot_seen = True
            elif a == "e":
                if e_seen or not num_seen:
                    return False
                num_seen = False
                e_seen = True
            elif a in "+-":
                if i > 0 and s[i - 1] != "e":
                    return False
            else:
                return False
        return num_seen

思路二：有限自动机DFA

1.png

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
class Solution:
    def isNumber(self, s: str) -> bool:
        state = [
            {},
            # 状态1,初始状态(扫描通过的空格)
            {"blank": 1, "sign": 2, "digit": 3, ".": 4},
            # 状态2,发现符号位(后面跟数字或者小数点)
            {"digit": 3, ".": 4},
            # 状态3,数字(一直循环到非数字)
            {"digit": 3, ".": 5, "e": 6, "blank": 9},
            # 状态4,小数点(后面只有紧接数字)
            {"digit": 5},
            # 状态5,小数点之后(后面只能为数字,e,或者以空格结束)
            {"digit": 5, "e": 6, "blank": 9},
            # 状态6,发现e(后面只能符号位, 和数字)
            {"sign": 7, "digit": 8},
            # 状态7,e之后(只能为数字)
            {"digit": 8},
            # 状态8,e之后的数字后面(只能为数字或者以空格结束)
            {"digit": 8, "blank": 9},
            # 状态9, 终止状态 (如果发现非空,就失败)
            {"blank": 9}
        ]
        cur_state = 1
        for c in s:
            if c.isdigit():
                c = "digit"
            elif c in " ":
                c = "blank"
            elif c in "+-":
                c = "sign"
            if c not in state[cur_state]:
                return False
            cur_state = state[cur_state][c]
        if cur_state not in [3, 5, 8, 9]:
            return False
        return True

tql

Veröffentlicht am Bearbeitet am in

1. 合并区间(Medium)

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

1
2
3
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

1
2
3
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

解答：

思路：先排序，再合并。

如果我们按照区间的 start 大小排序，那么在这个排序的列表中可以合并的区间一定是连续的。

  1. 先按首位置进行排序;

  2. 接下来,如何判断两个区间是否重叠呢?比如a = [1,4],b = [2,3]

  3. 当a[1] >= b[0]说明两个区间有重叠.

  4. 但是如何把这个区间找出来呢?

  5. 左边位置一定是确定,就是a[0],而右边位置是max(a[1], b[1])

  6. 所以,我们就能找出整个区间为:[1,4]

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        res = []
        for i in sorted(intervals,key = lambda x:x[0]):
            if res and i[0] <= res[-1][1]:
                res[-1][1] = max(res[-1][1],i[1])
            else:
                res.append(i)
        return res

2. 插入区间(Hard)

给出一个无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1:

1
2
输入: intervals = [[1,3],[6,9]], newInterval = [2,5]
输出: [[1,5],[6,9]]

示例 2:

1
2
3
输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出: [[1,2],[3,10],[12,16]]
解释: 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

解答：

思路：二分法

  1. 采用二分查找找到新插入取间[A,B]， A在所有左侧点中插入位置(或直接命中)，B在所有右侧点中插入位置（或直接命中）
  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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[List[int]]
        :type newInterval: List[int]
        :rtype: List[List[int]]
        """
        if not intervals:
            return [newInterval]
        
        def find(lis, k, i):
            lefti = 0
            leftj = len(lis) - 1

            while lefti <= leftj:
                mid = (lefti + leftj) // 2
                if lis[mid][i] > k:
                    leftj = mid - 1
                elif lis[mid][i] < k:
                    lefti = mid + 1
                else:
                    return mid
            return lefti

        left = find(intervals, newInterval[0], 0)
        right = find(intervals, newInterval[1], 1)
        
        l = max(left-1, 0)
        r = min(right+1, len(intervals))

        leftlis = intervals[:l]
        rightlis = intervals[r:]
        midlis = intervals[l:r]

        if midlis:
            if newInterval[0] <= midlis[0][1] and newInterval[1] >= midlis[-1][0]:
                midlis = [[min(midlis[0][0], newInterval[0]), max(midlis[-1][1], newInterval[1])]]
            elif newInterval[0] > midlis[0][1] and newInterval[1] >= midlis[-1][0]:
                midlis = [midlis[0], [newInterval[0], max(midlis[-1][1], newInterval[1])]]
            elif newInterval[0] <= midlis[0][1] and newInterval[1] < midlis[-1][0]:
                midlis = [[min(midlis[0][0], newInterval[0]), newInterval[1]], midlis[-1]]
            else:
                midlis = [midlis[0], newInterval, midlis[-1]]
        else:
            midlis = [newInterval]

        ans = leftlis + midlis + rightlis

        return ans

思路二：

也可以借鉴上一题的解法，不同在于，先把new插进去

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 insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        if not intervals or len(intervals) == 0:
            return [newInterval]
        idx = -1
        for i in range(len(intervals)):
            if intervals[i].start > newInterval.start:
                idx = i
                break
        if idx != -1:
            intervals.insert(i, newInterval)
        else:
            intervals.append(newInterval)
        res = []
        for interval in intervals:
            if res and res[-1].end >= interval.start:
                res[-1].end = max(res[-1].end, interval.end)
            else:
                res.append(interval)
        return res

3. 最后一个单词的长度(Easy)

给定一个仅包含大小写字母和空格 ' ' 的字符串，返回其最后一个单词的长度。

如果不存在最后一个单词，请返回 0 。

说明：一个单词是指由字母组成，但不包含任何空格的字符串。

示例:

1
2
输入: "Hello World"
输出: 5

解答：

思路：

很简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        if n == 0:
            return 0
        res = 0
        flag = 0
        for i in range(n-1,-1,-1):
            if s[i] != ' ':
                res += 1
                flag = 1
            elif s[i] == ' ' and flag:
                return res
        return res

思路二：

直接找最后一个单词

先找最后一个单词最后一个字母

再找最后一个单词第一个字母

1
2
3
4
5
6
7
8
9
10
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        end = len(s) - 1
        while end >= 0 and s[end] == " ":
            end -= 1
        if end == -1: return 0
        start = end
        while start >= 0 and s[start] != " ":
            start -= 1
        return end - start

4. 螺旋矩阵2(Medium)

给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

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

解答：

思路：

这个题和螺旋矩阵题目很像。

模拟顺时针转向

假设数组有R 行 C 列，seen[r][c]表示第 r 行第 c 列的单元格之前已经被访问过了。当前所在位置为 (r, c)，前进方向是 di。我们希望访问所有 R x C 个单元格。

当我们遍历整个矩阵，下一步候选移动位置是(next_r, next_c)。如果这个候选位置在矩阵范围内并且没有被访问过，那么它将会变成下一步移动的位置；否则，我们将前进方向顺时针旋转之后再计算下一步的移动位置。

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 generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        seen = [[False]*n for _ in range(n)]
        dr = [0,1,0,-1]
        dc = [1,0,-1,0]
        r,c,di = 0,0,0
        ans = [[-1]*n for _ in range(n)]
        for i in range(1,n*n+1):
            ans[r][c] = i
            seen[r][c] = True
            next_r,next_c = r+dr[di],c+dc[di]
            if 0<= next_r<n and 0<=next_c<n and not seen[next_r][next_c]:
                r = next_r
                c = next_c
            else:
                di = (di+1)%4
                r,c = r+dr[di],c+dc[di]
        return ans

5. 第K个排列(Medium)

给出集合 [1,2,3,…,*n*]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

给定 n 和 k，返回第 k 个排列。

说明：

  • 给定 n 的范围是 [1, 9]。
  • 给定 k 的范围是[1, n!]。

示例 1:

1
2
输入: n = 3, k = 3
输出: "213"

示例 2:

1
2
输入: n = 4, k = 9
输出: "2314"

解答：

思路一：回溯算法

当然是暴力直接算出所有的排列然后取第k个，但是会超时

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 getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        s = ''.join([str(i) for i in range(1, n+1)])
        print(s)
        def permunation(s):
            if len(s) == 0:
                return
            if len(s) == 1:
                return [s]
            res = []
            for i in range(len(s)):
                x = s[i]
                xs = s[:i] + s[i+1:]
                for j in permunation(xs):
                    res.append(x+j)
            return res
        return permunation(s)[k-1]

思路二：找规律

当有n位集合时，可以知道第一位显然有n个可能，而每一个第一位确定后，引申出来的可能性有 (n-1)! 个。

所以反过来呢，第k个排列的第一位，就是 k/(n-1)! 余数记为mod。

于是第二位的答案也呼之欲出： mod/(n-2)!。

这就是最核心的计算方法。下面讲解下实现的一些小细节。

  1. 需要先定义从1到n的数组。上文中说的 k/(n-1)! 和 mod/(n-2)! 其实并不严谨，第二位实际上应该是算完第一位后排除第一位的答案后，剩余数组的第 mod/(n-2)! 个元素。
  2. 由于引入了数组，第一位计算前mod 应该为 k-1。
  3. 当余数为0时，实际上没有必要继续计算了，只需将剩余数组元素，依次添加进答案即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        res = ''
        fac = [1] * (n+1)
        for i in range(1,n+1):
            fac[i] = fac[i-1]*i
        nums = [i for i in range(1,n+1)]
        k -= 1
        for i in range(1,n+1):
            idx = k/fac[n-i]
            res += str(nums[idx])
            nums.pop(idx)
            k -= idx * fac[n-i]
        return res

Veröffentlicht am Bearbeitet am in

1. N皇后(Hard)

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例:

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

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

解答：

思路：回溯算法

这个题很难，大一就觉得好难。。。

在建立算法之前，我们来考虑两个有用的细节。

  1. 一行只可能有一个皇后且一列也只可能有一个皇后。

  2. 这意味着没有必要再棋盘上考虑所有的方格。只需要按列循环即可。

  3. 对于所有的主对角线有 行号 + 列号 = 常数，对于所有的次对角线有 行号 - 列号 = 常数.

  4. 这可以让我们标记已经在攻击范围下的对角线并且检查一个方格 (行号, 列号) 是否处在攻击位置。

现在已经可以写回溯函数 backtrack(row = 0).

  • 从第一个 row = 0 开始.

  • 循环列并且试图在每个 column 中放置皇后.

    • 如果方格 (row, column) 不在攻击范围内
      • 在 (row, column) 方格上放置皇后。
      • 排除对应行，列和两个对角线的位置。
      • If 所有的行被考虑过，row == N
      • 意味着我们找到了一个解
      • ​ Else
        • 继续考虑接下来的皇后放置 backtrack(row + 1).
      • ​ 回溯：将在 (row, column) 方格的皇后移除.
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
class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        def could_place(row,col):
            return not (cols[col] + hill[row - col] + dale[row + col])
        def place_queen(row,col):
            queens.add((row,col))
            cols[col] = 1
            hill[row - col] = 1
            dale[row + col] = 1
        def remove_queen(row,col):
            queens.remove((row,col))
            cols[col] = 0
            hill[row - col] = 0
            dale[row + col] = 0
        def add_solution():
            solution = []
            for _,col in sorted(queens):
                solution.append('.'*col+'Q'+'.'*(n-col-1))
            output.append(solution)
        def backtrack(row = 0):
            for col in range(n):
                if could_place(row,col):
                    place_queen(row,col)
                    if row + 1 == n:
                        add_solution()
                    else:
                        backtrack(row + 1)
                    remove_queen(row,col)
        cols = [0] * n
        hill = [0] * (2*n-1)
        dale = [0] * (2*n-1)
        queens = set()
        output = []
        backtrack()
        return output

思路二：DFS

八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。

对于任意(x,y),如果要让新的点和它不能处于同一条横行、纵行或斜线上，则新点(p,q)必须要满足p+q != x+y 和p-q!= x-y, 前者针对左下右上斜线，后者针对左上右下斜线，两者同时都保证了不在同一条横行和纵行上。

代码中变量的含义:

  • cols_lst: 每一行皇后的column位置组成的列表
  • cur_row：目前正在判断的row的index
  • xy_diff：所有x-y组成的列表
  • xy_sum：所有x+y组成的列表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        def dfs(cols_lst, xy_diff, xy_sum):
            cur_row = len(cols_lst)
            if cur_row == n:
                ress.append(cols_lst)
            for col in range(n):
                if col not in cols_lst and cur_row - col not in xy_diff and cur_row + col not in xy_sum:
                    dfs(cols_lst+[col], xy_diff+[cur_row-col], xy_sum+[cur_row+col])
        ress = []
        dfs([], [], [])
        return [['.' * i + 'Q' + '.' * (n-i-1) for i in res] for res in ress]

2. N皇后2(Hard)

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回 n 皇后不同的解决方案的数量。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: 4
输出: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

解答：

思路：

和上题完全一模一样，只是最后输出的时候，输出的是结果的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def totalNQueens(self, n):
        """
        :type n: int
        :rtype: int
        """
        def dfs(col_list,xy_diff,xy_sum):
            cur_row = len(col_list)
            if cur_row == n:
                ress.append(col_list)
            for col in range(n):
                if col not in col_list and cur_row-col not in xy_diff and cur_row+col not in xy_sum:
                    dfs(col_list+[col],xy_diff+[cur_row-col],xy_sum+[cur_row+col])
        ress = []
        dfs([],[],[])
        return len(ress)

3. 最大子序和(Easy)

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

1
2
3
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

解答：

思路：

这道题很简单，动态规划，逐步更新局部最优解和全局最优解。

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

4. 螺旋矩阵(Medium)

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

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

示例 2:

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

解答：

思路：

绘制螺旋轨迹路径，我们发现当路径超出界限或者进入之前访问过的单元格时，会顺时针旋转方向。

算法

假设数组有R 行 C 列，seen[r][c]表示第 r 行第 c 列的单元格之前已经被访问过了。当前所在位置为 (r, c)，前进方向是 di。我们希望访问所有 R x C 个单元格。

当我们遍历整个矩阵，下一步候选移动位置是(next_r, next_c)。如果这个候选位置在矩阵范围内并且没有被访问过，那么它将会变成下一步移动的位置；否则，我们将前进方向顺时针旋转之后再计算下一步的移动位置。

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 spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if not matrix:
            return []
        R = len(matrix)
        C = len(matrix[0])
        seen = [[False]*C for _ in matrix]
        dr = [0,1,0,-1]
        dc = [1,0,-1,0]
        r = c = di = 0
        ans = []
        for _ in range(R*C):
            ans.append(matrix[r][c])
            seen[r][c] = True
            next_r,next_c = r+dr[di],c+dc[di]
            if 0<= next_r < R and 0<= next_c < C and not seen[next_r][next_c]:
                r = next_r
                c = next_c
            else:
                di = (di+1)%4
                r = r + dr[di]
                c = c + dc[di]
        return ans

5. 跳跃游戏(Medium)

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

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

判断你是否能够到达最后一个位置。

示例 1:

1
2
3
输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

示例 2:

1
2
3
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

解答：

思路：

这个题很好想。

就是从后往前倒推，如果倒数第二个能到底倒数第一个位置，那么可以就去求是否可以达到倒数第二个位置。

就是反复往回推的过程。

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

Veröffentlicht am in

1. 全排列(Medium)

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

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

解答：

思路一：

这个题说简单也简单，说难也难。

主要思想还是回溯，就看你理解回溯算法程度深不深了。

代码里很好的解释了回溯算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        def backtrack(nums,tmp):
            if not nums:
                res.append(tmp)
                return
            for i in range(len(nums)):
                backtrack(nums[:i]+nums[i+1:],tmp+[nums[i]])
        backtrack(nums,[])
        return res

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

当然，如果你觉得这个不好理解，还有更容易理解的方法。

思路二：

每次取一个作为prefix, 剩下的继续做permutation，然后连接起来加入res中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) == 0:
            return []
        if len(nums) == 1:
            return [nums]
        res = []
        for i in range(len(nums)):
            prefix = nums[i]
            rest = nums[:i] + nums[i+1:]
            for j in self.permute(rest):
                res.append([prefix]+j)
        return res

2. 全排列2(Medium)

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

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

解答：

思路：

这一题怎么说呢，和上一题一模一样，唯一就是不能重复，所以，稍微修改一下上一题的代码就可以AC了

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

3. 旋转图像(Medium)

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

说明：

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

原地旋转输入矩阵，使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

解答：

思路：

这个题想明白翻转过程就OK了

我们可以先沿对角线翻转，然后对每一行翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        row = len(matrix)
        col = len(matrix[0])
        for i in range(row):
            for j in range(i,col):
                matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j]
        for i in range(row):
            matrix[i].reverse()

4. 字母异位词分组(Medium)

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

1
2
3
4
5
6
7
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明：

  • 所有输入均为小写字母。
  • 不考虑答案输出的顺序。

解答：

思路：

这个题可以先将每个str字典序排序，比较是否一样，然后按key存入字典里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        maps = {}
        for i in strs:
            tmp = ''.join(sorted(list(i)))
            if tmp in maps:
                maps[tmp].append(i)
            else:
                maps[tmp] = [i]
        return maps.values()

5. Pow(x,n)(Medium)

实现 pow(x, n) ，即计算 x 的 n 次幂函数。

示例 1:

1
2
输入: 2.00000, 10
输出: 1024.00000

示例 2:

1
2
输入: 2.10000, 3
输出: 9.26100

示例 3:

1
2
3
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

解答：

思路：

这个题就很简单了，剑指offer原题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n < 0:
            x = 1/x
            n = -n
        res = 1
        while n:
            if n & 1:
                res *= x
            x *= x
            n >>= 1
        return res

也可以用递归，递归的坏处在于可能发生递归调用栈溢出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n == 0:
            return 1
        if n < 0:
            return self.myPow(1/x,-n)
        if n & 1:
            return x * self.myPow(x*x,n>>1)
        else:
            return self.myPow(x*x,n>>1)

可能与测试用例有关。。。递归比迭代要快。