LeetCode刷题记录

Posted on | In | | 阅读数 次

96.不同的二叉搜索树

状态：不会，重做
题目
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

1
2
3
4
5
1     1      2         3       3  
 \    \     /  \       /       /            
  3    2    1   3      2       1          
 /      \            /          \
2       3           1            2

解析
动态规划  
以1,2,...,n为节点组成的BST有G[n]种，
G[n]=F(1,n)+F(2,n)+...+F(i,n)+...+F(n,n)  
其中，F(i,n)表示以i为根节点组成的BST个数，  
然而，F(i,n)=G[i-1] * G[n-i]  
注意，G[0]=1

以n=3为例，G[3]=F(1,3)+F(2,3)+F(3,3),

1
2
3
F(1,3)=G[0] * G[2]
F(2,3)=G[1] * G[1]
F(3,3)=G[2] * G[0]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        G = [0] * (n+1)
        G[0] = 1

        for i in range(1, n+1):
            for j in range(i):
                G[i] += G[j] * G[i-1-j]

        return G[n]

if __name__ == '__main__':
    a = Solution()
    print(a.numTrees(n=3))

413. 等差数列划分

状态：亟待优化
题目
如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。

例如，以下数列为等差数列:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

以下数列不是等差数列。
1, 1, 2, 5, 7

数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。
如果满足以下条件，则称子数组(P, Q)为等差数组：
元素 A[P], A[p + 1], …, A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。
函数要返回数组 A 中所有为等差数组的子数组个数。

示例:
A = [1, 2, 3, 4]
返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。

version1  
过程：

成绩：

解析    
审题一定要清楚：

  1. 给定的数组A不一定是等差数列，不要让示例先入为止；
  2. 等差子数列，题目中明确要求：元素 A[P], A[p + 1], …, A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。即表明，子数列是在原数列中不间隔选出的，且至少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
class Solution(object):
    def numberOfArithmeticSlices(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        if len(A) < 3:
            return 0
        else:
            res = 0
            for i in range(len(A)):         
                for j in range(i + 3, len(A) + 1):
                    li = A[i:j]
                    k = li[1] - li[0]#等差
                    flag = 0
                    for m in range(1, len(li)):
                        if li[m] == li[m-1] + k:
                            flag += 1
                        else:
                            break
                    if flag == len(li) - 1:
                        res += 1
                    else:
                        break                   
        return res

标准答案
以A=[1,2,3,4,5,6]为例：
10=1+2+3+4
在枚举子数列时，判断A[i-2],A[i-1],A[i]是否为等差数列，若是则根据前一个循环是否也是等差决定是否叠加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def numberOfArithmeticSlices(self, A):
        """
        :param A: List[int]
        :return: int
        """
        N = len(A)
        if N <= 2:
            return 0

        count = 0
        streak = 0
        for i in range(2, N):
            if A[i] - A[i-1] == A[i-1] - A[i-2]:
                streak += 1#以A[i]结尾的等差子数列的个数
                count += streak
            else:
                streak = 0
        return count

120. 三角形最小路径和

状态：排名85%，未考虑空间复杂度
题目  
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

1
2
3
4
5
6
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

version1  
过程：

成绩：

解析    
参考之前矩阵的题目，从最左上角开始，每次只能往下或者往右走，最佳的解题思路就是算出每走一步后的结果，依次迭代。  
那么，这里的思路也是一样的，这里的限制条件是只能走相邻的点。

代码

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 minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        if len(triangle) == 1:
            return triangle[0][0]
        elif len(triangle) == 2:
            return triangle[0][0] + min(triangle[1])
        else:
            triangle[1][0], triangle[1][1] = triangle[1][0] + triangle[0][0], triangle[1][1] + triangle[0][0]
            for row in range(2, len(triangle)):
                for idx in range(row + 1):
                    if idx == 0:
                        triangle[row][idx] += triangle[row - 1][idx]
                    elif idx == row:
                        triangle[row][idx] += triangle[row - 1][idx - 1]
                    else:
                        triangle[row][idx] += min(triangle[row - 1][idx], triangle[row - 1][idx - 1])
            return min(triangle[-1])

标准答案  
关键在于空间复杂度：  
我的解法是至上而下的，需要修改数组中的每一个元素。现在有一种解法是至下而上，只写存最后一行的内层数组空间，这种解法更节约空间。  
代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        if not triangle:
            return
        res = triangle[-1]
        for i in range(len(triangle) - 2, -1, -1):
            for j in range(len(triangle[i])):
                res[j] = min(res[j], res[j + 1]) + triangle[i][j]
        return res[0]

62. 不同路径

状态：排名95.86%
题目  
一个机器人位于一个 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

version1  
过程：

成绩：

解析  
第一次提交失败：未考虑周全矩阵的形式。  
思路和之前矩阵求最小路径和以及三角形最小路径和是一样的，计算每个节点的路径可能数，最终答案即为最后一个点的值。

代码

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 uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        if m == 1 or n == 1:
            return 1
        else:
            res = [[0 for i in range(n)] for i in range(m)]
            for i in range(m):
                for j in range(n):
                    if i == 0 and j == 0:
                        continue
                    elif i == 0:
                        res[i][j] = 1
                    elif j == 0:
                        res[i][j] = 1
                    else:
                        res[i][j] = res[i - 1][j] + res[i][j - 1]
            return res[-1][-1]

712. 两个字符串的最小ASCII删除和

状态：不会做
题目  
给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。

示例 1:
输入: s1 = “sea”, s2 = "eat"
输出: 231
解释: 在 “sea” 中删除 “s” 并将 “s” 的值(115)加入总和。
在 “eat” 中删除 “t” 并将 116 加入总和。
结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。

示例 2:
输入: s1 = “delete”, s2 = "leet"
输出: 403
解释: 在 “delete” 中删除 “dee” 字符串变成 “let”，
将 100[d]+101[e]+101[e] 加入总和。在 “leet” 中删除 “e” 将 101[e] 加入总和。
结束时，两个字符串都等于 “let”，结果即为 100+101+101+101 = 403 。
如果改为将两个字符串转换为 “lee” 或 “eet”，我们会得到 433 或 417 的结果，比答案更大。

注意:
0 < s1.length, s2.length <= 1000。
所有字符串中的字符ASCII值在[97, 122]之间。

最佳答案  
这题是经典题目“最长公共子串LCS”的变形题目。  
在弄懂LCS之后，这题就很好理解了。
LCS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
初始化dp矩阵：
----------d---e---l---e---t---e--
|___|_0_|_0_|_0_|_0_|_0_|_0_|_0_|
|_l_|_0_|_0_|_0_|_0_|_0_|_0_|_0_|
|_e_|_0_|_0_|_0_|_0_|_0_|_0_|_0_|
|_e_|_0_|_0_|_0_|_0_|_0_|_0_|_0_|
|_t_|_0_|_0_|_0_|_0_|_0_|_0_|_0_|
从s1="leet"开始遍历对比s2="delete"，
1.如果相同，那么dp[i][j]=dp[i-1][j-1]+1;
意味着，如果s1与s2最后一个元素相同，那么
LCS（s1,s2）=LCS(s1[:-1],s2[:-1])+s1[-1]
2.如果不同，那么dp[i][j]=max(dp[i-1][j],dp[i][j-1])
意味着，如果s1与s2最后一个元素不同，那么
LCS(s1,s2)=max(LCS(s1[:-1],s2),LCS(s1,s2[:-1]))
----------d---e---l---e---t---e--
|___|_0_|_0_|_0_|_0_|_0_|_0_|_0_|
|_l_|_0_|_0_|_0_|_1_|_1_|_1_|_1_|
|_e_|_0_|_0_|_1_|_1_|_2_|_2_|_2_|
|_e_|_0_|_0_|_1_|_1_|_2_|_2_|_3_|
|_t_|_0_|_0_|_1_|_1_|_2_|_3_|_3_|

标准代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def minimumDeleteSum(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: int
        """
        l1, l2 = len(s1), len(s2)
        dp = [[0] * (l2 + 1) for _ in range(l1 + 1)]
        for i in range(l1):
            for j in range(l2):
                if s1[i] == s2[j]:
                    dp[i + 1][j + 1] = dp[i][j] + ord(s1[i])
                else:
                    dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
        result = sum(map(ord, s1 + s2)) - dp[l1][l2] * 2
        return result

647. 回文子串

状态：排名23.26%
题目  
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。

示例 1:

1
2
3
输入: "abc"
输出: 3
解释: 三个回文子串: "a", "b", "c".

示例 2:

1
2
3
输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".

注意:
输入的字符串长度不会超过1000。

version1  
过程：

成绩：

解析  
首先一定搞明白回文字符串的意思，回文即正着读反着读都一样。  
所以第一次提交失败。  
第二次暴力求解，成绩亟待提高。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        flag = 0
        for i in range(len(s)):
            for j in range(i, len(s)):
                if s[i:j + 1] == s[i:j + 1][::-1]:
                    flag += 1

        return flag

303. 区域和检索 - 数组不可变

状态：排名41.91%，待提高
题目  
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

示例：

1
2
3
4
给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

说明:
你可以假设数组不可变。
会多次调用 sumRange 方法。

version1  
过程：

成绩：

解析    
这题思路很简单。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class NumArray:
    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.nums = nums

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        return sum(self.nums[i:j+1])
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

标准答案  
这题主要是要用动态规划的思想，题目要求的sumRange(i,j)，是可以在遍历数组元素的时候进行叠加求和，一次性求出新的叠加数组。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class NumArray:
    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.nums = nums

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        return sum(self.nums[i:j+1])

if __name__ == "__main__":
    a = NumArray(nums=[-2, 0, 3, -5, 2, -1])
    print(a.sumRange(0, 5))

343. 整数拆分

状态：  排名99%
题目  
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

说明: 你可以假设 n 不小于 2 且不大于 58。

version1  
过程：

version2  
过程：
 
成绩：

解析  
第二次再写，硬生生地记住了结论，解题关键要尽可能多拆分为3，若剩下1，则要将3和1转换为2和2。

标准答案  
这题主要还是没搞懂解题思路，解题的关键是神奇的质数2和质数3。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from functools import reduce

class Solution:
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 2:
            return 1
        if n == 3:
            return 2
        list_3 = [3] * int((n / 3))  # generate a list of 3
        mod_3 = n % 3
        if mod_3 == 1:  # if a 1 is left, then add it to the first element to get a 4
            list_3[0] += 1
        if mod_3 == 2:  # if a 2 is left, then put it into the list
            list_3.append(2)
        return reduce(lambda a, b: a * b, list_3)

638. 大礼包

状态：未通过，有思路但是有难点无法克服  
题目  
在LeetCode商店中， 有许多在售的物品。

然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。
现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。

每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，其他数字分别表示内含的其他种类物品的数量。

任意大礼包可无限次购买。

示例 1:

1
2
3
4
5
6
7
输入: [2,5], [[3,0,5],[1,2,10]], [3,2]
输出: 14
解释: 
有A和B两种物品，价格分别为¥2和¥5。
大礼包1，你可以以¥5的价格购买3A和0B。
大礼包2， 你可以以¥10的价格购买1A和2B。
你需要购买3个A和2个B， 所以你付了¥10购买了1A和2B（大礼包2），以及¥4购买2A。

示例 2:

1
2
3
4
5
6
7
输入: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
输出: 11
解释: 
A，B，C的价格分别为¥2，¥3，¥4.
你可以用¥4购买1A和2B，也可以用¥9购买2A，2B和1C。
你需要买1A，2B和1C，所以你付了¥4买了1A和1B（大礼包1），以及¥3购买1B， ¥4购买1C。
你不可以购买超出待购清单的物品，尽管购买大礼包2更加便宜。

说明:
最多6种物品， 100种大礼包。
每种物品，你最多只需要购买6个。
你不可以购买超出待购清单的物品，即使更便宜。

version1  
过程：  
本地编译器上未调通，有思路，但是不知道如何解决不同大礼包优惠程度的对比。

标准答案  
深度优先搜索，主要就是用大礼包或者原价购买的价格比较，不仅要比较不同大礼包之间的差别，还要比较与原价之间的价格。大礼包的比较肯定要用for循环，然后保存下来方便与后续比较。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def shoppingOffers(self, price, special, needs):
        """
        :type price: List[int]
        :type special: List[List[int]]
        :type needs: List[int]
        :rtype: int
        """
        d = {}

        def dfs(cur):
            val = sum(cur[i] * price[i] for i in range(len(needs)))  # cost without special
            for spec in special:
                tmp = [cur[j] - spec[j] for j in range(len(needs))]
                if min(tmp) >= 0:  # skip deals that exceed needs
                    val = min(val, d.get(tuple(tmp), dfs(tmp)) + spec[-1])  # .get check the dictionary first for result, otherwise perform dfs.
            d[tuple(cur)] = val
            return val

        return dfs(needs)

312. 戳气球

状态：未通过，思路错误  
题目  
有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。

1
每当你戳破一个气球 i 时，你可以获得 nums[left] * nums[i] * nums[right] 个硬币。

这里的 left 和 right 代表和 i 相邻的两个气球的序号。  
注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。

求所能获得硬币的最大数量。

说明:

1
2
你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。  
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

示例:

1
2
3
4
输入: [3,1,5,8]
输出: 167 
解释: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
     coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

version1  
过程：  
整个思考过程就是错误的。忧伤···

标准答案

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = [1] + nums + [1]
        n = len(nums)
        dp = [[0] * n for _ in xrange(n)]

        def calculate(i, j):
            if dp[i][j] or j == i + 1: # in memory or gap < 2
                return dp[i][j]
            coins = 0
            for k in xrange(i+1, j): # find the last balloon
                coins = max(coins, nums[i] * nums[k] * nums[j] + calculate(i, k) + calculate(k, j))
            dp[i][j] = coins
            return coins

        return calculate(0, n-1)

740.删除与获得点数

95.不同的二叉搜索树II

121.买卖股票的最佳时机

状态：未通过，超时  
题目  
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

1
2
3
4
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

1
2
3
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

version1  
过程：  
思路有，就是实现起来不够动态规划。所以会导致很慢，超时不通过。

标准答案  
标准答案是只需要一次遍历，求出答案，复杂度是O(N)。而我第一次版本是不止一次遍历的，不仅是明显写出的第一次循环还是隐性的求min,max（其实也是遍历）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        max_profit, min_price = 0, float('inf')
        for price in prices:
            min_price = min(min_price, price)
            profit = price - min_price
            max_profit = max(max_profit, profit)
        return max_profit

931.下降路径最小和

状态：排名98%    
题目  
给定一个方形整数数组 A，我们想要得到通过 A 的下降路径的最小和。

下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。

示例：

1
2
3
4
5
6
7
8
9
输入：[[1,2,3],[4,5,6],[7,8,9]]
输出：12
解释：
可能的下降路径有：
[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
[2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
[3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]

和最小的下降路径是 [1,4,7]，所以答案是 12。

提示：

1
2
1 <= A.length == A[0].length <= 100
-100 <= A[i][j] <= 100

version1  
过程：  

成绩：
 
这种类型的题目已经掌握了，笔试是不会怕了。
相似题目有120，62。

代码

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 minFallingPathSum(self, A):
        """
        :type A: List[List[int]]
        :rtype: int
        """
        if len(A) == 1:
            return sum(A[0])
        if len(A[0]) == 1:
            res = 0
            for row in range(len(A)):
                res += A[row][0]
            return res
        for i in range(1, len(A)):
            for j in range(len(A[0])):
                if j == 0:
                    A[i][j] += min(A[i-1][j], A[i-1][j+1])
                elif j == len(A[0])-1:
                    A[i][j] += min(A[i-1][j], A[i-1][j-1])
                else:
                    A[i][j] += min(A[i-1][j], A[i-1][j-1], A[i-1][j+1])
        return min(A[-1])

70.爬楼梯

状态：未通过
题目  
假设你正在爬楼梯。需要 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 阶

标准答案    
爬楼梯是一道经典的动态规划类型题目。  
这道题目是逆推。比如，要想爬10级楼梯，可以1次爬1级，也可以1次爬2级。如果现在考虑，只剩最后一步，那么有可能是最后一步爬1级，也有可能是最后一步爬2级。如果最后一步爬1级，那么问题转换为爬9级台阶的方式，同理可知，如果最后一步爬2级，就等价于秋节爬8级台阶的方法。  
数学表达式：
F(10)=F(9)+F(8)
F(9)=F(8)+F(7)
…

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            return self.climbStairs(n-1) + self.climbStairs(n-2)

152. 乘积最大子序列

状态：未通过
题目  
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:

1
2
3
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

1
2
3
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

标准答案    
动态规划的题目做多了，直觉告诉我这题应该一次遍历即可得到答案。  
连续子序列的最大值可能因为符号的变化，最大值瞬间变为最小值，最小值瞬间变为最大值，故这题的关键是记录当前遍历状态下的最大值与最小值。

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        maximum = big = small = nums[0]
        for n in nums[1:]:
            big, small = max(n, n * big, n * small), min(n, n * big, n * small)
            maximum = max(maximum, big)
        return maximum

122. 买卖股票的最佳时机 II

状态：未通过
题目  
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

1
2
3
4
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

1
2
3
4
5
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

1
2
3
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

标准答案    
这题的题目背景与121.买卖股票的最佳时机非常相似。但是不要搞混淆，题目给出的条件一点点的差异也可能导致解法大大不同。这题没有不允许同一天操作买入与卖出的交易行为，而121题则明确提出不可以。

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        res = []
        for i in range(len(prices)-1):
            if prices[i+1] > prices[i]:
                res.append(prices[i+1]-prices[i])
        return sum(res)

200. 岛屿的个数

状态：未通过
题目  
给定一个由’1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。
一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。
你可以假设网格的四个边均被水包围。

示例 1:

1
2
3
4
5
6
输入:
11110
11010
11000
00000
输出: 1

示例 2:

1
2
3
4
5
6
输入:
11000
11000
00100
00011
输出: 3

标准答案    
方法一：
深度优先搜索，在每次遍历中尽可能深入地迭代遍历。  
在目标函数中调用自建的dfs函数，dfs函数中递归调用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
24
25
class Solution:
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid:
            return 0

        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    count += 1
        return count

    def dfs(self, grid, i, j):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
            return
        grid[i][j] = '#'#确保已经遍历过的陆地不会再走一遍，不然会一直死循环
        self.dfs(grid, i + 1, j)
        self.dfs(grid, i - 1, j)
        self.dfs(grid, i, j + 1)
        self.dfs(grid, i, j - 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class UnionFind(object):
    def __init__(self, grid):
        m, n = len(grid), len(grid[0])
        self.count = 0#记录岛屿的数量，节省一次遍历
        self.parent = [-1] * (m*n)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    self.parent[i*n + j] = i*n + j
                    self.count += 1

    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, x, y):
        rootx = self.find(x)
        rooty = self.find(y)
        if rootx != rooty:
            self.parent[rooty] = rootx
            self.count -= 1

class Solution(object):
    def is_valid(self, grid, r, c):
        m, n = len(grid), len(grid[0])
        if r < 0 or c < 0 or r >= m or c >= n:
            return False
        return True

    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid or not grid[0]:
            return 0

        uf = UnionFind(grid)

        directions = [(0,1), (0,-1), (-1,0), (1,0)]
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    for d in directions:
                        nr, nc = i + d[0], j + d[1]
                        if self.is_valid(grid, nr, nc) and grid[nr][nc] == '1':
                            uf.union(i*n+j, nr*n+nc)
        return uf.count




if __name__ == "__main__":
    a = Solution()
    print(a.numIslands(grid=[['1','1','1','1','0'], ['1','1','0','1','0'], ['1','1','0','0','0'], ['0','0','0','0','0']]))

695. 岛屿的最大面积

状态：排名53.56%    
题目  
给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)

示例 1:

1
2
3
4
5
6
7
8
9
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。

示例 2:

1
2
3
[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。
注意: 给定的矩阵grid 的长度和宽度都不超过 50。

version1  
过程：  

成绩：
 
与200. 岛屿的个数类似，采用深度优先搜索的思想，200那题是计算岛屿的个数，这题计算岛屿的大小，大同小异。

代码

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
class Solution:
    def maxAreaOfIsland(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        res = [0]
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                area = 0
                tmp = self.dfs(grid, i, j, area)
                if tmp:
                    res.append(tmp)
        return max(res)

    def dfs(self, grid, i, j, area):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != 1:
            return
        grid[i][j] = '#'
        area = 1
        down = self.dfs(grid, i + 1, j, area)
        if down:
            area += down
        up = self.dfs(grid, i-1, j, area)
        if up:
            area += up
        right = self.dfs(grid, i, j+1, area)
        if right:
            area += right
        left = self.dfs(grid, i, j-1, area)
        if left:
            area += left
        return area

300. 最长上升子序列

状态：不会    
题目  
给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

1
2
3
输入: [10,9,2,5,3,7,101,9,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

标准答案    
动态规划，设置两个指针i,j以及一个长度与给定数组相同的数组T，核心公式：T[i]=max(T[i],T[j]+1)。  
具体讲解见Youtube：https://www.youtube.com/watch?v=CE2b_-XfVDk

代码

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:
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = []
        for i in range(len(nums)):
            tmp = self.find_bigger(cur=nums[i], rest=nums[i+1:])
            if tmp!= None:
                res.append(tmp+1)
        return max(res)

    def find_bigger(self, cur, rest):
        for i in range(len(rest)):
            if rest[i] > cur:
                tmpp = self.find_bigger(rest[i], rest[i+1:])
                if tmpp != None:
                    return tmpp+1
            elif i == len(rest)-1:
                return 0
if __name__ == "__main__":
    a = Solution()
    print(a.lengthOfLIS(nums=[10,9,2,5,3,7,101,9,18]))

416. 分割等和子集

状态：不会    
题目  
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200

示例 1:

1
2
3
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

1
2
3
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.

标准答案    
0/1背包问题，详细讲解见：
https://www.youtube.com/watch?v=8LusJS5-AGo  
这题背包的重量为sum/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 canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        total = sum(nums)
        if total % 2 == 1:
            return False
        else:
            total = int(total / 2)
            dp = [[0 for i in range(total + 1)] for j in range(len(nums))]
            for i in range(nums[0], total + 1):
                dp[0][i] = nums[0]
            for i in range(1, len(nums)):
                for j in range(nums[i], total + 1):
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i])
            if dp[len(nums) - 1][total] != total:
                return False
            else:
                return True

if __name__ == "__main__":
    a = Solution()
    print(a.canPartition(nums=[1,2,3,4,5,6,7]))

322. 零钱兑换

状态：不会    
题目  
给定不同面额的硬币 coins 和一个总金额 amount。
编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

1
2
3
输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1

示例 2:

1
2
输入: coins = [2], amount = 3
输出: -1

说明:
你可以认为每种硬币的数量是无限的。

标准答案    
经典0/1背包问题的变种类型——完全背包，与01背包不同在于每种物品可以不止使用一次，物品个数是无限的。  
解题关键在于当未计算或者使用该硬币，硬币总数量下降的就更新dp[i]。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp = [-1] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            for j in range(0, len(coins)):
                if i >= coins[j] and dp[i - coins[j]] != -1:
                    if dp[i] == -1 or dp[i] > dp[i - coins[j]] + 1:
                        dp[i] = dp[i - coins[j]] + 1
        return dp[amount]
        
if __name__ == "__main__":
    a = Solution()
    print(a.coinChange(coins = [1, 2, 5], amount = 11))

377. 组合总和 Ⅳ

状态：不会    
题目  
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

1
2
3
4
5
6
7
8
9
10
11
nums = [1, 2, 3]
target = 4

所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。

标准答案    
经典0/1背包问题的变种类型——完全背包，与Leetcode322相似，都是物品可以无限次使用，但是dp数组里记录的是不同组合个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        dp = [0] * (target + 1)
        dp[0] = 1  # if num == target
        for i in range(1, target + 1):
            for num in nums:
                if i >= num:
                    dp[i] += dp[i - num]
        return dp[target]

if __name__ == "__main__":
    a = Solution()
    print(a.combinationSum4(nums = [1, 2, 3], target = 4))

474. 一和零

状态：不会    
题目  
在计算机界中，我们总是追求用有限的资源获取最大的收益。
现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。
你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。

注意:
给定 0 和 1 的数量都不会超过 100。
给定字符串数组的长度不会超过 600。

示例 1:
输入: Array = {“10”, “0001”, “111001”, “1”, “0”}, m = 5, n = 3
输出: 4
解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 “10”,“0001”,“1”,“0” 。

示例 2:
输入: Array = {“10”, “0”, “1”}, m = 1, n = 1
输出: 2
解释: 你可以拼出 “10”，但之后就没有剩余数字了。更好的选择是拼出 “0” 和 “1” 。

标准答案    
经典0/1背包问题的变种类型——多维背包问题，不仅考虑物品的重量，而是要衡量物品的重量和体积，并且这里求的不是背包的最大价值，而是可能性中包含的最大字符串个数。

代码

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 findMaxForm(self, strs, m, n):
        """
        :type strs: List[str]
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for item in strs:
            z = item.count('0')
            o = item.count('1')
            for x in range(m, -1, -1):
                for y in range(n, -1, -1):
                    if x >= z and y >= o:
                        dp[x][y] = max(1 + dp[x - z][y - o], dp[x][y])
        return dp[m][n]

if __name__ == "__main__":
    a = Solution()
    print(a.findMaxForm(strs=["10", "0001", "111001", "1", "0"], m = 5, n = 3))

139. 单词拆分

状态：不会    
题目  
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：

1
2
3
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

1
2
3
4
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3：

1
2
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

标准答案    
属于完全背包问题,考察的标准不再是体重，价值之类的数值型标准了，而是字符串。dp数组记录当前位置i是否可分。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        dp = [False] * (len(s) + 1)  # dp[i] means s[:i+1] can be segmented into words in the wordDicts
        dp[0] = True
        for i in range(len(s)):
            for j in range(i+1, len(s)):
                if dp[i] and s[i: j] in wordDict:
                    dp[j] = True

        return dp[-1]

if __name__ == "__main__":
    a = Solution()
    print(a.wordBreak(s="catsandog", wordDict=["cats", "dog", "sand", "and", "cat"]))

494. 目标和

状态：不会    
题目  
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。
对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例 1:

1
2
3
4
5
6
7
8
9
10
输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释: 
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。

注意:
数组的长度不会超过20，并且数组中的值全为正数。
初始的数组的和不会超过1000。
保证返回的最终结果为32位整数。

标准答案    
这题要根据公式推导转换为背包问题  
在nums中，有部分正数和负数。p表示所有正数的集合，q表示所有负数的集合，那么有sum§ - sum(q) = S，
sum§ + sum(q) = sum(all)  
以上两个公式转换可得：
sum§ = (sum(all) + S)/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:
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        s = sum(nums)
        N = s + S
        if N % 2 or S > s: return 0
        N = N // 2
        dp = [0 for _ in range(N + 1)]
        dp[0] = 1
        for num in nums:
            for i in range(N, num - 1, -1):
                dp[i] += dp[i - num]
        return dp[-1]


if __name__ == "__main__":
    a = Solution()
    print(a.findTargetSumWays(nums=[1, 1, 1, 1, 1], S=3))

547. 朋友圈

状态：不会    
题目  
班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。
如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。
所谓的朋友圈，是指所有朋友的集合。

给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。
如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。
你必须输出所有学生中的已知的朋友圈总数。

示例 1:

1
2
3
4
5
6
7
输入: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
输出: 2 
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。

示例 2:

1
2
3
4
5
6
输入: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。

标准答案    
这题有两种解题思路，一个是DFS，另一个是并查集。
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
24
25
class Solution:
    def findCircleNum(self, M):
        """
        :type M: List[List[int]]
        :rtype: int
        """
        N = len(M)
        seen = set()

        def dfs(node):
            for nei, adj in enumerate(M[node]):
                if adj and nei not in seen:
                    seen.add(nei)
                    dfs(nei)

        ans = 0
        for i in range(N):
            if i not in seen:
                dfs(i)
                ans += 1
        return ans

if __name__ == "__main__":
    a = Solution()
    print(a.findCircleNum(M=[[1,1,0], [1,1,0], [0,0,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
39
40
41
42
43
44
class UnionFind(object):
    def __init__(self, grid):
        self.n = len(grid)
        self.parent = [-1] * self.n
        for idx in range(self.n):
            self.parent[idx] = idx

    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, x, y):
        rootx = self.find(x)
        rooty = self.find(y)
        if rootx != rooty:
            self.parent[rooty] = rootx

    def diff_groups(self):
        diff_groups = set()
        for i in range(self.n):
            diff_groups.add(self.find(i))
        return len(diff_groups)

class Solution(object):
    def findCircleNum(self, M):
        """
        :type M: List[List[int]]
        :rtype: int
        """
        n = len(M)
        uf = UnionFind(M)

        for i in range(n):
            for j in range(n):
                if M[i][j] == 1:
                    uf.union(i, j)

        return uf.diff_groups()

if __name__ == "__main__":
    a = Solution()
    M = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
    print(a.findCircleNum(M=M))

128. 最长连续序列

状态：第二遍通过11.11%    
题目  
给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

1
2
3
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

version2  
过程：  

成绩：

代码

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
class Solution:
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums == []:
            return 0
        nums=sorted(list(set(nums)))
        res = []
        for i in range(len(nums)):
            tmp = nums[:i+1]
            if res:
                tmp_res = res[-1]
            else:
                tmp_res = 1
            if len(tmp) == 1:
                tmp_res = 1
                res.append(tmp_res)
            elif res[-1] >= 1:
                if tmp[-1] == tmp[-2]+1:
                    tmp_res += 1
                    res[-1] = tmp_res
                elif tmp[-1] == tmp[-2]:
                    continue
                else:
                    res.append(1)
        return max(res)

标准答案
首先对数组去重即集合，遍历集合中的每个元素，并弹出该元素，找出比这个元素小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
class Solution:
   def longestConsecutive(self, nums):
       """
       :type nums: List[int]
       :rtype: int
       """
       num = set(nums)
       maxLen = 0
       while num:
           n = num.pop()
           i = n + 1
           l1 = 0
           l2 = 0
           while i in num:
               num.remove(i)
               i += 1
               l1 += 1
           i = n - 1
           while i in num:
               num.remove(i)
               i -= 1
               l2 += 1
           maxLen = max(maxLen, l1 + l2 + 1)
       return maxLen

130. 被围绕的区域

状态：不会
题目  
给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。
找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

示例:

1
2
3
4
X X X X
X O O X
X X O X
X O X X

运行你的函数后，矩阵变为：

1
2
3
4
X X X X
X X X X
X X X X
X O X X

解释:
被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。
任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。
如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

标准答案  
这一题与200. 岛屿的个数以及695. 岛屿的最大面积背景类似，解题关键在于找到边界，题目中的关键信息是把除边界以外的‘O’改成‘X’，那么就应该找到边界‘O’，不仅是四周的‘O’，还包括与边界‘O’相连的‘O’，这里就用到了深度优先搜索。

标准代码

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:
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        alive, v = set(), set()
        for r in range(len(board)):
            for c in range(len(board[r])):
                if r == 0 or r == len(board) - 1 or c == 0 or c == len(board[0]) - 1:
                    self.traverse(board, r, c, alive)
        for r in range(len(board)):
            for c in range(len(board[r])):
                if board[r][c] == 'O' and (r, c) not in alive:
                    board[r][c] = 'X'
        for i in board:
            print(i)

    def traverse(self, board, r, c, alive):
        if (r, c) in alive or r < 0 or r > len(board) - 1 or c < 0 or c > len(board[0]) - 1 or board[r][c] != 'O':
            return
        else:
            alive.add((r, c))
            self.traverse(board, r + 1, c, alive)
            self.traverse(board, r, c + 1, alive)
            self.traverse(board, r - 1, c, alive)
            self.traverse(board, r, c - 1, alive)


if __name__ == "__main__":
    a = Solution()
    a.solve(board=[['X', 'X', 'X', 'X'], ['X', 'O', 'O', 'X'], ['X', 'X', 'O', 'X'], ['X', 'O', 'X', 'X']])

3. 无重复字符的最长子串

状态：不会
题目  
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 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" 是一个子序列，不是子串。

标准答案  
题目要求找到最大的不重复子串，运用双指针方法，详细解释见
https://zhuanlan.zhihu.com/p/36074066

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        dict = {}
        begin, res = -1, 0
        for end in range(len(s)):
            if s[end] in dict and begin < dict[s[end]]:
                begin = dict[s[end]]
            else:
                res = max(res, end-begin)#end-begin记录目前不重复子串的长度，res是目前最大不重复子串的长度
            dict[s[end]] = end
        return res

if __name__ == "__main__":
    a = Solution()
    print(a.lengthOfLongestSubstring(s="pwwkew"))

684. 冗余连接

状态：不会
题目  
在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。
附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。
返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。
答案边[u, v] 应满足相同的格式 u < v。

示例 1：

1
2
3
4
5
6
输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的无向图为:
  1
 / \
2 - 3

示例 2：

1
2
3
4
5
6
输入: [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]
解释: 给定的无向图为:
5 - 1  - 2
   |   |
   4  - 3

注意:
输入的二维数组大小在 3 到 1000。
二维数组中的整数在1到N之间，其中N是输入数组的大小。

标准答案  
题目看着就很烦，他想表达的意思是找出使得图连通的最后一条边，删去这个边，输入的图就不再连通了，这一题参考博客
http://wulc.me/2017/10/12/LeetCode 解题报告(684,685,721)-并查集介绍及应用/  
可以更好地理解并查集这种数据结构，并提到了路径压缩和按等级合并，这两个步骤可以降低算法的时间复杂度。

代码

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 UnionFindSet(object):
    def __init__(self):
        self.parents = list(range(1001))
        self.rank = [0] * 1001

    def find(self, val):
        """find with path compression"""
        if self.parents[val] != val:
            self.parents[val] = self.find(self.parents[val])
        return self.parents[val]

    def union(self, v1, v2):
        """union by rank, check whether union two vertics will lead to a cycle"""
        p1, p2 = self.find(v1), self.find(v2)
        if p1 == p2:
            return True
        elif self.rank[p1] > self.rank[p2]:
            self.parents[p2] = p1
        elif self.rank[p1] < self.rank[p2]:
            self.parents[p1] = p2
        else:
            self.rank[p2] += 1
            self.parents[p1] = p2
        return False


class Solution(object):
    def findRedundantConnection(self, edges):
        """
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        ufs = UnionFindSet()
        for edge in edges:
            if ufs.union(edge[0], edge[1]):
                return edge


if __name__ == "__main__":
    a = Solution()
    print(a.findRedundantConnection(edges=[[1,2], [2,3], [3,4], [1,4], [1,5]]))

685. 冗余连接 II

状态：不会
题目  
在本问题中，有根树指满足以下条件的有向图。
该树只有一个根节点，所有其他节点都是该根节点的后继。
每一个节点只有一个父节点，除了根节点没有父节点。

输入一个有向图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。
附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组。
每一个边的元素是一对[u, v]，用以表示有向图中连接顶点 u and v和顶点的边，其中父节点u是子节点v的一个父节点。

返回一条能删除的边，使得剩下的图是有N个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

示例 1:

1
2
3
4
5
6
7
输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
解释: 给定的有向图如下:
  1
 /  \
v   v
2 -->3

示例 2:

1
2
3
4
5
6
7
输入: [[1,2], [2,3], [3,4], [4,1], [1,5]]
输出: [4,1]
解释: 给定的有向图如下:
5  <-  1  -> 2
     ^    |
     |    v
     4 <-  3

注意:
二维数组大小的在3到1000范围内。
二维数组中的每个整数在1到N之间，其中 N 是二维数组的大小。

标准答案  
这一题与Leetcode 684相似，不过难度升级，从无向图变为有向图，要返回的边使得删除这条边之后输入的有向图变为一颗合格树。 而 合格树要求每个节点只有一个父节点，根据这个要求可以先筛选一遍，看图中是否存在多个父节点的点，那么要删除的边就在里面。
参考博客：  
http://wulc.me/2017/10/12/LeetCode 解题报告(684,685,721)-并查集介绍及应用/

代码

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
class UnionFindSet(object):
    def __init__(self):
        self.parents = list(range(1001))
        self.rank = [0] * 1001

    def find(self, val):
        """find with path compression"""
        if self.parents[val] != val:
            self.parents[val] = self.find(self.parents[val])
        return self.parents[val]

    def union(self, v1, v2):
        """union by rank, check whether union two vertics will lead to a cycle"""
        p1, p2 = self.find(v1), self.find(v2)
        if p1 == p2:
            return True
        elif self.rank[p1] > self.rank[p2]:
            self.parents[p2] = p1
        elif self.rank[p1] < self.rank[p2]:
            self.parents[p1] = p2
        else:
            self.rank[p2] += 1
            self.parents[p1] = p2
        return False


class Solution(object):
    def findRedundantDirectedConnection(self, edges):
        """
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        redundant_edges = None
        count = {}
        for e in edges:
            if e[1] not in count:
                count[e[1]] = []
            count[e[1]].append(e)
            if len(count[e[1]]) == 2:
                redundant_edges = count[e[1]]
                break

        if redundant_edges:
            ufs = UnionFindSet()
            for edge in edges:
                if edge == redundant_edges[1]:
                    continue
                if ufs.union(edge[0], edge[1]):
                    return redundant_edges[0]
            return redundant_edges[1]
        else:
            ufs = UnionFindSet()
            for edge in edges:
                if ufs.union(edge[0], edge[1]):
                    return edge

if __name__ == "__main__":
    a = Solution()
    print(a.findRedundantDirectedConnection(edges=[[1,2], [1,3], [2,3]]))

721. 账户合并

状态：不会
题目  
给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，
其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该帐户的邮箱地址。

现在，我们想合并这些帐户。如果两个帐户都有一些共同的邮件地址，则两个帐户必定属于同一个人。
请注意，即使两个帐户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。
一个人最初可以拥有任意数量的帐户，但其所有帐户都具有相同的名称。

合并帐户后，按以下格式返回帐户：
每个帐户的第一个元素是名称，其余元素是按顺序排列的邮箱地址。accounts 本身可以以任意顺序返回。

例子 1:

1
2
3
4
5
6
7
8
9
10
Input: 
accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], 
["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
Output: [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  
["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
Explanation: 
  第一个和第三个 John 是同一个人，因为他们有共同的电子邮件 "johnsmith@mail.com"。 
  第二个 John 和 Mary 是不同的人，因为他们的电子邮件地址没有被其他帐户使用。
  我们可以以任何顺序返回这些列表，例如答案[['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']，
  ['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']]仍然会被接受。

注意：
accounts的长度将在[1，1000]的范围内。
accounts[i]的长度将在[1，10]的范围内。
accounts[i][j]的长度将在[1，30]的范围内。

标准答案  
使用并查集或者DFS，这道题目里用到了路径压缩(找到u所在的树根v以后，把从u到v的路径上所有点的父亲都设置为v)，注意parent是父节点并不是根节点。怎么去并，去并谁也是要想清楚的，比如这一题我们要合并的是账号，那么遍历账号，根据邮箱一样这个筛选条件去合并。

代码

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
from collections import defaultdict
class UnionFind():
    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        rootx = self.find(x)
        rooty = self.find(y)

        if rootx != rooty:
            self.parent[rooty] = rootx

class Solution:
    def accountsMerge(self, accounts):
        """
        :type accounts: List[List[str]]
        :rtype: List[List[str]]
        """
        n = len(accounts)
        uf = UnionFind(n)

        dict = {}
        for i, a in enumerate(accounts):
            for email in a[1:]:
                if email in dict:
                    r1, r2 = uf.find(i), uf.find(dict[email])
                    uf.parent[r2] = r1
                else:
                    dict[email] = i

        dict_res = defaultdict(set)
        for k in range(n):
            dict_res[uf.find(k)] |= set(accounts[k][1:])

        res = []
        for k,v in dict_res.items():
            res.append([accounts[k][0]]+sorted(v))

        return res
if __name__ == "__main__":
    a = Solution()
    print(a.accountsMerge(accounts=[["David","David0@m.co","David1@m.co"],\
                                    ["David","David3@m.co","David4@m.co"],\
                                    ["David","David4@m.co","David5@m.co"],\
                                    ["David","David2@m.co","David3@m.co"],\
                                    ["David","David1@m.co","David2@m.co"]]))

763. 划分字母区间

状态：不会
题目  
字符串 S 由小写字母组成。
我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。
返回一个表示每个字符串片段的长度的列表。

示例 1:

1
2
3
4
5
6
输入: S = "ababcbacadefegdehijhklij"
输出: [9,7,8]
解释:
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

注意:

1
2
S的长度在[1, 500]之间。
S只包含小写字母'a'到'z'。

标准答案  
记录每个字符出现的最后一个索引，遍历字符串时，将每个字符与记录索引对比从而求得每个字符区间。

代码

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:
    def partitionLabels(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        dic = dict()
        for i, ch in enumerate(S):
            dic[ch] = i
        cnt = [-1]
        cur = 0
        for i, ch in enumerate(S):
            cur = max(cur, dic[ch])
            if i == cur:
                cnt.append(cur)
                cur = i + 1
        re = []
        for i in range(1, len(cnt)):
            re.append(cnt[i] - cnt[i - 1])
        return re

if __name__ == "__main__":
    a = Solution()
    print(a.partitionLabels(S = "ababcbacadefegdehijhklij"))

93. 复原IP地址

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

示例:

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

标准答案  
DFS

代码

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:
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        res = []
        self.dfs(s, 0, "", res)
        return res

    def dfs(self, s, index, path, res):
        if index == 4:
            if not s:
                res.append(path[:-1])
            return
        for i in range(1, 4):
            if i <= len(s):
                if i == 1:
                    self.dfs(s[1:], index + 1, path + s[0] + '.', res)
                elif i == 2 and s[0] != '0':
                    self.dfs(s[2:], index + 1, path + s[:2] + '.', res)
                elif i == 3 and s[0] != '0' and int(s[:3]) < 256:
                    self.dfs(s[3:], index + 1, path + s[:3] + '.', res)

if __name__ == "__main__":
    a = Solution()
    print(a.restoreIpAddresses(s="25525511135"))

393. UTF-8 编码验证

状态：空间复杂度未通过

题目  
UTF-8 中的一个字符可能的长度为 1 到 4 字节，遵循以下的规则：
对于 1 字节的字符，字节的第一位设为0，后面7位为这个符号的unicode码。
对于 n 字节的字符 (n > 1)，第一个字节的前 n 位都设为1，第 n+1 位设为0，后面字节的前两位一律设为10。
剩下的没有提及的二进制位，全部为这个符号的unicode码。
这是 UTF-8 编码的工作方式：

Char. number range UTF-8 octet sequence
0000 0000-0000 007F 0xxxxxxx
0000 0080-0000 07FF 110xxxxx 10xxxxxx
0000 0800-0000 FFFF 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

给定一个表示数据的整数数组，返回它是否为有效的 utf-8 编码。

注意:
输入是整数数组。只有每个整数的最低 8 个有效位用来存储数据。这意味着每个整数只表示 1 字节的数据。

示例 1:

1
2
3
data = [197, 130, 1], 表示 8 位的序列: 11000101 10000010 00000001.
返回 true 。
这是有效的 utf-8 编码，为一个2字节字符，跟着一个1字节字符。

示例 2:

1
2
3
4
5
data = [235, 140, 4], 表示 8 位的序列: 11101011 10001100 00000100.
返回 false 。
前 3 位都是 1 ，第 4 位为 0 表示它是一个3字节字符。
下一个字节是开头为 10 的延续字节，这是正确的。
但第二个延续字节不以 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution:
    def validUtf8(self, data):
        """
        :type data: List[int]
        :rtype: bool
        """
        if not data:
            return True
        if self.Binary(data[0])[2] == '0':
            if len(data) == 1:
                return True
            else:
                return self.validUtf8(data[1:])
        else:
            cB = self.countB(data[0])
            if cB == 1 or cB > 4:
                return False
            if len(data) >= cB:
                for i in range(1, cB):
                    if self.Binary(data[i])[2:4] != '10':
                        return False
                return self.validUtf8(data[cB:])
            else:
                return False

    def Binary(self, num):
        b_num_len = len(bin(num))
        if b_num_len != 10:
            return '0b'+'0'*(10-b_num_len)+bin(num)[2:]
        else:
            return bin(num)

    def countB(self, num):
        cnt = 0
        for b in self.Binary(num)[2:]:
            if b == '1':
                cnt += 1
            else:
                return cnt
        return cnt

if __name__ == "__main__":
    a = Solution()
    print(a.validUtf8(data=[250,145,145,145,145]))

851. 喧闹和富有

状态：不会

题目  
在一组 N 个人（编号为 0, 1, 2, …, N-1）中，每个人都有不同数目的钱，以及不同程度的安静（quietness）。
为了方便起见，我们将编号为 x 的人简称为 "person x "。

如果能够肯定 person x 比 person y 更有钱的话，我们会说 richer[i] = [x, y] 。注意 richer 可能只是有效观察的一个子集。
另外，如果 person x 的安静程度为 q ，我们会说 quiet[x] = q 。

现在，返回答案 answer ，其中 answer[x] = y 的前提是，在所有拥有的钱不少于 person x 的人中，person y 是最安静的人（也就是安静值 quiet[y] 最小的人）。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
输出：[5,5,2,5,4,5,6,7]
解释： 
answer[0] = 5，
person 5 比 person 3 有更多的钱，person 3 比 person 1 有更多的钱，person 1 比 person 0 有更多的钱。
唯一较为安静（有较低的安静值 quiet[x]）的人是 person 7，
但是目前还不清楚他是否比 person 0 更有钱。

answer[7] = 7，
在所有拥有的钱肯定不少于 person 7 的人中(这可能包括 person 3，4，5，6 以及 7)，
最安静(有较低安静值 quiet[x])的人是 person 7。

其他的答案也可以用类似的推理来解释。

提示：
1 <= quiet.length = N <= 500
0 <= quiet[i] < N，所有 quiet[i] 都不相同。
0 <= richer.length <= N * (N-1) / 2
0 <= richer[i][j] < N
richer[i][0] != richer[i][1]
richer[i] 都是不同的。
对 richer 的观察在逻辑上是一致的。

标准答案  
综合运用动态规划和记忆存储，这道题最佳答案秒在对安静数组进行排序，导致首先遍历最安静的人，那么这个人对应的答案就是自己，因为符合比自己富有（包括自己），并且最安静的要求。  
紧接着遍历比这个人穷的人，并且标记每个穷人的答案就是这个人，因为符合相对富有且最安静的要求。

代码

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
import collections

class Solution:
    def loudAndRich(self, richer, quiet):
        """
        :type richer: List[List[int]]
        :type quiet: List[int]
        :rtype: List[int]
        """
        graph = collections.defaultdict(list)
        for a, b in richer:
            graph[a].append(b)
        qi = [[q, i] for i, q in enumerate(quiet)]

        # !! look at me
        qi.sort()

        res = [-1] * len(quiet)

        def search(i, t):
            res[i] = t
            for adj in graph[i]:
                if res[adj] == -1:
                    search(adj, t)

        for q, i in qi:
            if res[i] == -1:
                search(i, i)

        return res


if __name__ == "__main__":
    a = Solution()
    print(a.loudAndRich(richer=[[0,1],[1,2]], quiet = [0,1,2]))

5. 最长回文子串

状态：不会

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

示例 1：

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

示例 2：

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

标准答案  
回文子串一共有两种类型：  
1.aba
2.abba  
按照这两种类型的组成特点，依次从内到外遍历。利用记忆存储当前状态下的最长回文子串。

代码

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 longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        res = ""
    	  for i in xrange(len(s)):
        	# odd case, like "aba"
        	tmp = self.helper(s, i, i)
        	if len(tmp) > len(res):
            res = tmp
        	# even case, like "abba"
        	tmp = self.helper(s, i, i+1)
        	if len(tmp) > len(res):
            res = tmp
    	  return res
          
    # get the longest palindrome, l, r are the middle indexes  		 # from inner to outer
	  def helper(self, s, l, r):
    	while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1; r += 1
    	return s[l+1:r]

63. 不同路径 II

状态：排名85.07%

题目  
一个机器人位于一个 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. 向下 -> 向下 -> 向右 -> 向右

标准答案  
62. 不同路径的衍生版本，主要难点在于边界条件，在for循环之后要特别考虑有一些特殊情况容易漏掉。

代码

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 uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        if obstacleGrid[0][0] == 1:
            return 0
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])

        if m == 1:
            if 1 in obstacleGrid[0]:
                return 0
            else:
                return 1
        if n == 1:
            for row in obstacleGrid:
                if 1 in row:
                    return 0
            return 1

        res = [[0 for i in range(n)] for j in range(m)]
        res[0][0] = 1
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue
                if obstacleGrid[i][j] == 1:
                    res[i][j] = 0
                elif i == 0 and j > 0:
                    res[i][j] = res[i][j-1]
                elif j == 0 and i > 0:
                    res[i][j] = res[i-1][j]
                else:
                    res[i][j] = res[i - 1][j] + res[i][j-1]
        return res[-1][-1]

if __name__ == "__main__":
    a = Solution()
    print(a.uniquePathsWithObstacles(obstacleGrid=[[1,0],[0,0]]))

39. 组合总和

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

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

说明：
所有数字（包括target）都是正整数。
解集不能包含重复的组合。

示例 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
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
import java.util.List;
import java.util.Stack;
import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
	private List<List<Integer>> res = new ArrayList<>();
	private int[] candidates;
	private int len;
	
	private void findCombinationSum(int residue, int start, Stack<Integer> pre) {
		if (residue == 0) {
			res.add(new ArrayList<>(pre));
			return;
		}
		for (int i = start; i < len && residue - candidates[i] >= 0; i++) {
			pre.add(candidates[i]);
			
			findCombinationSum(residue-candidates[i], i, pre);
			pre.pop();
		}
	}
	
	public List<List<Integer>> combinationSum(int[] candidates, int target){
		int len = candidates.length;
		if (len == 0) {
			return res;
		}
		
		Arrays.sort(candidates);
		this.len = len;
		this.candidates = candidates;
		findCombinationSum(target, 0, new Stack<>());
		return res;
	}
	
	public static void main(String[] args) {
		int[] candidates = {2, 3, 6, 7};
		int target = 7;
		Solution solution = new Solution();
		List<List<Integer>> combinationSum = solution.combinationSum(candidates, target);
		System.out.println(combinationSum);
	}

40. 组合总和II

状态：不会  
题目  
给定一个数组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]
]

标准答案  
39. 组合总和的衍生版本，主要不同在于每个数字只能使用一次。  
参考自liweiwei1419的详细解答。

代码

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
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class Solution {
	private List<List<Integer>> res = new ArrayList();
	private int[] candidates;
	private int target;
	private int len;
	
	private void findCombinationSum(int residue, int start, Stack<Integer>pre) {
		if(residue == 0) {
			res.add(new ArrayList<>(pre));
			return;
		}
		for(int i = start; i < len && residue - candidates[i] >= 0; i++) {
			if(i > start && candidates[i] == candidates[i-1]) {
				continue;
			}
			
			pre.add(candidates[i]);
			findCombinationSum(residue-candidates[i], i+1, pre);
			pre.pop();
		}
	}
	public List<List<Integer>> combinationSum2(int[] candidates, int target) {
		this.len = candidates.length;
		this.candidates = candidates;
		if(len == 0) {
			return res;
		}
		Arrays.sort(candidates);
        findCombinationSum(target, 0, new Stack<>());
        return res;
    }

	public static void main(String[] args) {
		int[] candidates = {2, 5, 2, 1, 2};
		int target = 5;
		Solution solution = new Solution();
		List<List<Integer>> combinationSum2 = solution.combinationSum2(candidates, target);
		System.out.println(combinationSum2);
	}
}