LeetCode (3)

Posted on Edited on In Views:
Symbols count in article: 18k Reading time ≈ 17 mins.

题目库: [1688， 79, 78, 46, 22, 90, 47, 39, 40, 93, 53, 70, 121, 122, 118, 392, 62, 198, 5, 55, 64, 322, 63, 120, 93, 45 213, 343, 300, 279, 1143, 494, 152, 518, 377, 416, 309, 337, 221, 139, 119, '面试题17.16', 746, 376]

Backtracking

1688 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def numberOfMatches(self, n: int) -> int:
        def find_matches(n):
            if n == 1:
                return 0
            else:
                if n % 2 == 0:
                    counts = find_matches(n // 2)
                else:
                    counts = find_matches(n // 2 + 1) 
                
                return counts + n // 2
            
        return find_matches(n)

79 Medium

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
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        n, d, k = len(board), len(board[0]), len(word)

        def find_word(i, j, target_index, parent):
            if target_index >= k:
                return True

            if board[i][j] != word[target_index]:
                return False

            result = []
            parent.append((i, j))
            if i > 0:
                if (i - 1, j) not in parent:
                    result.append(find_word(i - 1, j, target_index + 1, parent[:]))
            
            if i < (n - 1):
                if (i + 1, j) not in parent:
                    result.append(find_word(i + 1, j, target_index + 1, parent[:]))
            
            if j > 0:
                if (i, j - 1) not in parent:
                    result.append(find_word(i, j - 1, target_index + 1, parent[:]))
            
            if j < (d - 1):
                if (i, j + 1) not in parent:
                    result.append(find_word(i, j + 1, target_index + 1, parent[:]))

            if not result:
                if target_index < (k - 1):
                    return False

                return True

            return any(result)
        
        for i in range(n):
            for j in range(d):
                if board[i][j] == word[0]:
                    r = find_word(i, j, 0, [])
                    if r:
                        return True
        
        return False

78 Medium

通过 j + 1来分支

1
2
3
4
5
6
7
8
9
10
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        results = []
        def find_subsets(start, curr_sets):
            results.append(curr_sets)
            for j in range(start, len(nums)):
                find_subsets(j + 1, curr_sets + [nums[j]])
        
        find_subsets(0, [])
        return results

46 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        results = []
        n = len(nums)
        def find_permutation(head, nums):
            if len(head) == n:
                results.append(head)
            else:
                for i in range(len(nums)):
                    temp = nums[:]
                    val = temp.pop(i)
                    find_permutation(head + [val], temp)

        find_permutation([], nums)
        return results

22 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        results = []
        def parenthesis(curr_str, open_brac, close_brac):
            if (open_brac == 0) and (close_brac == 0):
                results.append(curr_str)
                return

            if (close_brac >= open_brac) and (open_brac >=0) and (close_brac >= 0):
                if open_brac < close_brac:
                    parenthesis(curr_str + ')', open_brac, close_brac - 1)

                parenthesis(curr_str + '(', open_brac - 1, close_brac)
        
        parenthesis('', n, n)
        return results

90 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        results = []
        nums.sort()

        def find_subsets(i, curr_subset, curr_seen):
            results.append(curr_subset)
            for j in range(i, len(nums)):
                if nums[j] not in curr_seen:
                    find_subsets(j + 1, curr_subset + [nums[j]], [])
                    curr_seen.append(nums[j])

        find_subsets(0, [], [])
        return results

47 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        results = []

        def permuatation(curr_nums, next_choice, previous):
            if len(curr_nums) == n:
                results.append(curr_nums)
            else:
                for i in range(len(next_choice)):
                    if next_choice[i] not in previous:
                        permuatation(curr_nums + [next_choice[i]], next_choice[:i] + next_choice[i+1:], [])
                        previous.append(next_choice[i])
        
        permuatation([], nums, [])
        return results

39 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        results = []

        def find_combination(i, curr_comb):
            curr_sum = sum(curr_comb)

            if curr_sum == target:
                results.append(curr_comb)
                return
            
            if curr_sum < target:
                for j in range(i, len(candidates)):
                    find_combination(j, curr_comb + [candidates[j]])
        
        find_combination(0, [])
        return results

40 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        results = []
        candidates.sort()
        def find_combination(i, nums):
            curr_sum = sum(nums)
            if curr_sum == target:
                results.append(nums)
                return
            
            if curr_sum < target:
                for j in range(i, len(candidates)):
                    if not (j != i and candidates[j - 1] == candidates[j]):
                        find_combination(j + 1, nums + [candidates[j]])
        
        find_combination(0, [])
        return results

93 Medium

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:
    def restoreIpAddresses(self, s: str) -> List[str]:
        results = []
        def find_ip(curr_ip, curr_can):
            if (len(curr_ip) == 4) and (len(curr_can) == 0):
                results.append('.'.join(curr_ip))
                return

            if (len(curr_can) <= (4 - len(curr_ip)) * 3) and (len(curr_can) >= 4 - len(curr_ip)):
                find_ip(curr_ip + [curr_can[0]], curr_can[1:])
                if (curr_can[0] != '0') and (len(curr_can) >= 2):
                    find_ip(curr_ip + [curr_can[:2]], curr_can[2:])
                    if len(curr_can) >= 3 and int(curr_can[:3]) <= 255:
                        find_ip(curr_ip + [curr_can[:3]], curr_can[3:])
        
        new_s = ''
        for i in s:
            if i.isdigit():
                new_s = ''.join([new_s, i])

        find_ip([], new_s)
        return results

Dynamic Programming

53 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        curr_max = nums[0]
        prev_sum = nums[0]
        # find the largest sum end with nums[i]
        for i in range(1, len(nums)):
            # if f[i - 1] + f[i] > f(i) then largest sum end with f[i] is f[i - 1] + f[i] else f[i]
            # in this case, it is same as max(f[i - 1] + f[i], f[i])
            curr_sum = max(nums[i], prev_sum + nums[i]) 
            prev_sum = curr_sum            
            if curr_sum > curr_max:
                curr_max = curr_sum
                
        return curr_max

70 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1

        if n == 2:
            return 2

        prev_1 = 1
        prev_2 = 2
        for i in range(3, n):
            temp = prev_1
            prev_1 = prev_2
            prev_2 = prev_2 + temp
        
        return prev_1 + prev_2

121 Easy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # f(n) = max profit if sell at day n
        # diff(n, n - 1) = prices[n] - price[n - 1] 
        # f(n) = max(f(n - 1) + diff(n, n - 1), diff(n, n - 1))

        curr_max = 0
        prev_profit = 0
        for i in range(1, len(prices)):
            diff = prices[i] - prices[i - 1]
            curr_profit = max(prev_profit + diff, diff)
            if curr_profit > curr_max:
                curr_max = curr_profit

            prev_profit = curr_profit
        
        return curr_max

122 Easy

1
2
3
4
5
6
7
8
9
10
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # f(n) = sum of positive gain til end of day n
        # f(n) = f(n - 1) + max(0, profit)
        curr_sum = 0
        for i in range(1, len(prices)):
            profit = prices[i] - prices[i - 1]
            curr_sum = max(0, profit) + curr_sum
        
        return curr_sum

118 Easy

1
2
3
4
5
6
7
8
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        out = [[1]]
        for i in range(1, numRows):
            curr_row = [1] + [out[i - 1][j - 1] + out[i - 1][j] for j in range(1, len(out[i - 1]))] + [1]
            out.append(curr_row)
        
        return out

392 Easy

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 isSubsequence(self, s: str, t: str) -> bool:
        # f(n): # of common items
        # f(0) = 0
        # f(n) = f(n - 1) + I(s[i] == t[j])

        i, j, n, k = 0, 0, len(s), len(t)
        if n > k:
            return False
        
        curr_com = 0
        while (i < n) and (j < k):
            if s[i] == t[j]:
                curr_com += 1
                i += 1

            j += 1
            
        if curr_com == n:
            return True
        else:
            return False

62 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # f(m, n) = number of paths to cell (m, n)
        # f(0, :) = 1
        # f(:, 0) = 1
        # f(m, n) = f(m - 1, n) + f(n, m - 1)
        matrix = [[1] * n]
        for i in range(1, m):
            curr_row = [1]
            for j in range(1, n):
                prev_up = matrix[i - 1][j]
                prev_left = curr_row[-1]
                
                curr_row.append(prev_left + prev_up)

            matrix.append(curr_row)
        
        return matrix[-1][-1]

198 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def rob(self, nums: List[int]) -> int:
        # f(n): max # of cash at house n
        # f(1): nums[1]
        # f(2): max(nums[1], nums[2])
        # f(n): max(nums[n] + f(n - 2), f(n - 1))
        if len(nums) == 1:
            return nums[0]
        
        two_before = nums[0]
        one_before = max(nums[1], nums[0])
        curr_total = one_before
        for i in range(2, len(nums)):
            temp = one_before
            curr_total = max(two_before + nums[i], one_before)
            one_before = curr_total
            two_before = temp

        return curr_total

5 Medium

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 longestPalindrome(self, s: str) -> str:
        # f(i, j): 1 if i -> j is a palindromic substring
        # f(i, i): 1
        # f(i, i + 1): 1 if i -> i+1 is a palindromic substring
        # f(i, j): 1 if s[i] == s[j] and f[i+1 : j-1] else 0

        dp = [[0] * len(s) for _ in range(len(s))]
        level = 1
        out_str = s[0]
        if len(s) == 1:
            return s
        
        for i in range(len(s)):
            dp[i][i] = 1

        while level < len(s):
            for j in range(len(s) - level):
                if s[j] == s[j + level]:
                    l = j + 1
                    r = j + level - 1
                    if (level == 1) or (dp[l][r]):
                        dp[j][j + level] = 1
                        out_str = s[j:j + level + 1]

            level += 1
            
        return out_str

55 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # f(n): if we can get from n -> nums[-1]
        # f(-1): True
        # f(n): True if any([f(n) for i in range(n)])
        dp = [False] * len(nums)
        dp[-1] = True
        for i in range(len(nums) - 2, -1, -1):
            for j in range(min(nums[i], len(nums) - i) + 1):
                if dp[j + i]:
                    dp[i] = True
                    break
        
        return dp[0]

64 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # f(i, j) = min sum at position (i, j)
        # f(0, 1:) = f(0, j) + f(0, j - 1)
        # f(1:, 0) = f(i, 0) + f(i - 1, 0)
        # f(i, j) = min(f(i - 1, j), f(i, j - 1)) + grid[i][j]
        m, n = len(grid), len(grid[0])
        for i in range(1, n):
            grid[0][i] = grid[0][i] + grid[0][i - 1]
        
        for i in range(1, m):
            grid[i][0] = grid[i][0] + grid[i - 1][0]
        
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] = min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
        
        return grid[-1][-1]

322 Medium

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 coinChange(self, coins: List[int], amount: int) -> int:
        # f(i): Minimum coins to get amount, -1 if cannot
        # coins[j]
        # f(0): 0
        # options = []
        # if i - j < 0: pass, if f(i - j) == -1: pass, else options.append(f(i - j) + 1)
        # f(i) = min(options)

        dp = [0] * (amount + 1)
        for i in range(1, len(dp)):
            options = []
            for j in coins:
                if (i - j >= 0) and (dp[i - j] != -1):
                    options.append(dp[i - j] + 1)

            if not options:
                dp[i] = -1
            else:
                dp[i] = min(options)
        
        return dp[-1]

63 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # the key is to set 1 to 0 and initialization 
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        assign_num = 1
        if obstacleGrid[0][0] == 1:
            return 0

        for i in range(n):
            if obstacleGrid[0][i] == 1:
                obstacleGrid[0][i] = 0
                assign_num = 0
            else:
                obstacleGrid[0][i] = assign_num
        
        assign_num = 1
        for i in range(1, m):
            if obstacleGrid[i][0] == 1:
                obstacleGrid[i][0] = 0
                assign_num = 0
            else:
                obstacleGrid[i][0] = assign_num
        
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    obstacleGrid[i][j] = 0
                else:
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1]
        
        return obstacleGrid[-1][-1]

120 Medium

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # f(n, i): Minimum distance to layer n, position i
        # f(len(triangle), :) = triangle[-1]
        # f(n, i) = min(f(n + 1, i), f(n + 1, i + 1)) + triangle[n][i]

        depth = len(triangle)
        for n in range(depth - 2, -1, -1):
            for i in range(len(triangle[n])):
                triangle[n][i] = min(triangle[n + 1][i], triangle[n + 1][i + 1]) + triangle[n][i]
        
        return triangle[0][0]

91 Medium

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 numDecodings(self, s: str) -> int:
        # counts = 0
        # cache = {}
        # def find_combo(curr_str, cand):
        #     if len(curr_str) + len(cand) != len(s):
        #         return

        #     if not cand:
        #         nonlocal counts
        #         counts += 1
        #         return
            
        #     for i in range(len(cand)):
        #         single = cand[i]
        #         double = cand[i:i+2]
        #         if int(single) > 0:
        #             find_combo(curr_str + single, cand[i+1:])
        #             if (len(double) > len(single)) and (10 <= int(double) <= 26):
        #                 find_combo(curr_str + double, cand[i+2:])
            
        # find_combo('', s)
        # return counts

        n = len(s)
        s = ' ' + s
        f = [0] * 3
        f[0] = 1
        for i in range(1,n + 1):
            f[i % 3] = 0
            a = ord(s[i]) - ord('0')
            b = ( ord(s[i - 1]) - ord('0') ) * 10 + ord(s[i]) - ord('0')
            if 1 <= a <= 9:
                f[i % 3] = f[(i - 1) % 3]
            if 10 <= b <= 26:
                f[i % 3] += f[(i - 2) % 3]
        return f[n % 3]

45 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def jump(self, nums: List[int]) -> int:
        # f(n): min jumps to nums[-1]
        # f(n): 0
        # f(n - 1): float('inf') if 0 else 1
        # f(i): min([f(i) + 1 for i in range(min(n, i))]) 
        if len(nums) == 1:
            return 0

        nums[-1] = 0
        nums[-2] = float('inf') if nums[-2] == 0 else 1
        for i in range(len(nums) - 3, -1, -1):
            curr_min = float('inf')
            for j in range(1, min(nums[i], len(nums) - 1 - i) + 1):
                curr_jumps = 1 + nums[i + j]
                if curr_min > curr_jumps:
                    curr_min = curr_jumps

            nums[i] = curr_min
        
        return num

213 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) in [1, 2, 3]:
            return max(nums)
        
        seq_1 = nums[:-1]
        seq_2 = nums[1:]
        seq_1[1] = max(seq_1[0], seq_1[1])
        seq_2[1] = max(seq_2[0], seq_2[1])

        for i in range(2, len(seq_1)):
            seq_1[i] = max(seq_1[i - 2] + seq_1[i], seq_1[i - 1])
            seq_2[i] = max(seq_2[i - 2] + seq_2[i], seq_2[i - 1])
        
        return max(seq_1[-1], seq_2[-1])

343 Medium

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 integerBreak(self, n: int) -> int:
        # f(n): max mul
        # f(2): 1
        # f(3): 2
        # f(n): f(i) * f(j) where i != j
        
        if n == 2:
            return 1
        
        if n == 3:
            return 2

        dp = [i for i in range(n + 1)]
        for i in range(4, n + 1):
            l, r = 2, i - 2
            while l <= r:
                curr_prod = dp[l] * dp[r]
                if curr_prod > dp[i]:
                    dp[i] = curr_prod

                l += 1
                r -= 1
        
        return dp[-1]

300 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # f(n): max strictly increasing sub sequence ending with n
        # f(0): 1
        # f(n): 
        dp = [1] * len(nums)
        curr_max = 1
        for i in range(1, len(nums)):
            vals = []
            for j in range(i, -1, -1):
                if nums[i] > nums[j]:
                    vals.append(dp[j])

            dp[i] = 1 if not vals else max(vals) + 1
            if dp[i] > curr_max:
                curr_max = dp[i]
        
        return curr_max

279 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def numSquares(self, n: int) -> int:
        dp = [0] * (n + 1)
        vals = []
        for i in range(1, n + 1):
            if i ** 2 <= n:
                dp[i ** 2] = 1
            else:
                break

            vals.append(i ** 2)

        for i in range(2, len(dp)):
            curr_min = i
            if i not in vals:
                j = 0
                while (j < len(vals)) and (vals[j] <= i):
                    curr_counts = 1 + dp[i - vals[j]]
                    if curr_counts < curr_min:
                        curr_min = curr_counts
                    
                    j += 1
            
                dp[i] = curr_min
        
        return dp[-1]

1143 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # f(i, j): largest number of substring match text1[:i], text2[:j]
        # If text1[i] != text2[j], f(i, j) = max(f(i, j - 1), f(i - 1, j))
        # If text1[i] == text2[j], f(i, j) = f(i - 1, j - 1) + 1
        M, N = len(text1), len(text2)
        dp = [[0] * (N + 1) for _ in range(M + 1)]
        for i in range(1, M + 1):
            for j in range(1, N + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[M][N]

494 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def findTargetSumWays(self, nums: List[int], S: int) -> int:
        sumAll = sum(nums)
        if S > sumAll or (S + sumAll) % 2:
            return 0
        target = (S + sumAll) // 2

        dp = [0] * (target + 1)
        dp[0] = 1

        for num in nums:
            for j in range(target, num - 1, -1):
                dp[j] = dp[j] + dp[j - num]
        return dp[-1]

152 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # f(i): max product at i
        # min_prod: current min product
        # max_prod: current max product
        # f(i): max(f(i - 1), max_prod)
        
        min_prod = nums[0]
        max_prod = nums[0]
        for i in range(1, len(nums)):
            temp = min_prod
            min_prod = min(min_prod * nums[i], nums[i], max_prod * nums[i])
            max_prod = max(temp * nums[i], nums[i], max_prod * nums[i])
            nums[i] = max(nums[i - 1], max_prod)

        return nums[-1]

518 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n, m = len(coins), amount + 1
        dp = [1] * m
        for i in range(1, m):
            if i % coins[0] != 0:
                dp[i] = 0
        
        for i in range(1, n):
            for j in range(1, m):
                if coins[i] <= j:
                    dp[j] = dp[j - coins[i]] + dp[j]

        return dp[-1]

377 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        # 定义 f[i][j]: 为组合长度为 i 凑成总和为 j 的方案数是多少
        # f[0][0] = 1
        # dp.shape = ((target + 1), (target + 1))

        dp = [[0] * (target + 1) for _ in range(target + 1)]
        dp[0][0] = 1
        
        out = 0
        for i in range(1, target + 1):
            for j in range(1, target + 1):
                for num in nums:
                    if num <= j:
                        dp[i][j] += dp[i - 1][j - num]
        
            out += dp[i][j]

        return out

416 Medium

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 canPartition(self, nums: List[int]) -> bool:
        # f(i, j): whether we can form num ber j with nums[:i] items 
        # 0/1 knapsack problem.
        
        num_sum = sum(nums)
        if num_sum % 2 != 0:
            return False
        
        target = num_sum // 2
        dp = [True] + [False] * (target)
        if nums[0] <= (target):
            dp[nums[0]] = True
        
        for i in range(1, len(nums)):
            # right to left in order to avoid overrdie of dp[j - nums[i]]
            for j in range(target, -1, -1):
                if nums[i] <= j:
                    dp[j] = dp[j - nums[i]] or dp[j]

                if j == target and dp[j]:
                    return True

        return False

309 Medium

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
# // 思路：
# //     考虑有多少种状态，每种状态有哪些选择，或者是做了哪些选择后得到哪种状态。
# //     注意：到底是先选择了才有状态，还是先由状态才能选择。这里是先选择了，才有状态

# // 状态类型有2种：天数和是否持有。
# //     天数：一共为1-n天
# //     是否持有：分为持有状态、没持有状态1、没持有状态2。
# //         持有状态：选择 无处理 和 买入 都有可能达到该状态
# //         没持有状态1：选择 无处理 后达到该状态。
# //         没持有状态2：选择 卖出 后达到该状态。注意，卖出后进入一天的冻结期。
# //     注意：这里为什么要分两种没持有状态，这是为了便于后续状态转移，如果不区分这两种状态，状态转移没法确定当天是否可以进行买入操作。

# // dp表示的含义：
# //     dp[i][2] : 第i天为没持有状态2时，此时的最大利润
# //     dp[i][1] : 第i天为没持有状态1时，此时的最大利润
# //     dp[i][0] ： 第i天为持有状态时，此时的最大利润
# // 状态转移方程：
# //     dp[i][0]: 第i天为持有状态时，此时的最大利润
# //         无处理后达到该状态： dp[i][0] = dp[i-1][0] // 第i天没有处理就持有股票，证明上一天也持有
# //         买入后达到该状态： dp[i][0] = dp[i-1][1]-prices[n] // 第i天能买入股票，证明上一天没持有股票，且没进行卖出操作
# //         所以dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[n]); // 这里思考个问题，两种情况都能到达这个状态的话，那如何选择？为什么是取他们的max？
# //     dp[i][1]: 第i天为没持有状态1时，此时的最大利润
# //         无处理后达到该状态： dp[i][1] = max(dp[i-1][1], dp[i-1][2]) // 有两种到达该状态的情况，取最大那个
# //     dp[i][2]: 第i天为没持有状态2时，此时的最大利润
# //         卖出后达到该状态： dp[i][2] = dp[i-1][0]+prices[i]

# // 最后max(dp[n-1][1], dp[n-1][2])就是题目所需答案。即第n-1天没持有股票时的最大收益

# // test case: 
# // [1,2,3,0,2]
# // [1,2,-2,0,33,0,2]
# // [1,2,3,0,2,3,9,0,2,4]
# // [2,1]

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 1:
            return 0

        n = len(prices)
        dp = [[0] * 3 for _ in range(n)]
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        dp[0][2] = 0
        for i in range(1, n):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-1][2])
            dp[i][2] = dp[i-1][0] + prices[i]

        return max(dp[n-1][1], dp[n-1][2]);

337 Medium

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

        def try_rob(node):
            if not node:
                return [0, 0]
            
            left_node = try_rob(node.left)
            right_node = try_rob(node.right)

            # do not rob this node, we can rob root.left and root.right
            val_1 = max(left_node[0], left_node[1]) + max(right_node[0], right_node[1])
            # rob this node, this implies that we cannot rob root.left or root.right
            val_2 = left_node[0] + right_node[0] + node.val

            return [val_1, val_2]
        
        return max(try_rob(root))

221 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return 0
        
        maxSide = 0
        rows, columns = len(matrix), len(matrix[0])
        dp = [[0] * columns for _ in range(rows)]
        for i in range(rows):
            for j in range(columns):
                if matrix[i][j] == '1':
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                    maxSide = max(maxSide, dp[i][j])
        
        maxSquare = maxSide * maxSide
        return maxSquare

139 Medium

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s) + 1
        dp = [False] * n
        dp[0] = True 
        for i in range(1, n):
            for j in range(i, -1, -1):
                if (s[j:i] in wordDict) and dp[j]:
                    dp[i] = True
                    break
        return dp[-1]

119 Easy

1
2
3
4
5
6
7
8
9
10
class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        dp = [1]
        for i in range(1, rowIndex + 1):
            curr_dp = []
            for j in range(len(dp) - 1):
                curr_dp.append(dp[j] + dp[j + 1])
            dp = [1] + curr_dp + [1]

        return dp

面试题 17.16 Easy

1
2
3
4
5
6
7
8
9
10
class Solution:
    def massage(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return sum(nums)

        nums[1] = max(nums[1], nums[0])
        for i in range(2, len(nums)):
            nums[i] = max(nums[i - 1], nums[i] + nums[i - 2])
        
        return nums[-1]

746 Easy

1
2
3
4
5
6
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        for i in range(len(cost) - 3, -1, -1):
            cost[i] += min(cost[i + 1], cost[i + 2])
        
        return min(cost[0], cost[1])

376 Medium

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:        
        diff = []
        for i in range(len(nums) - 1):
            if nums[i] - nums[i + 1] != 0:
                diff.append(nums[i] - nums[i + 1])

        if not diff:
            return 1
            
        dp = [0] * len(diff)
        dp[0] = 1
        for i in range(1, len(dp)):
            cand = [0]
            for j in range(i):
                if (diff[j] > 0 and diff[i] < 0) or (diff[j] < 0 and diff[i] > 0):
                    cand.append(dp[j] + 1)
            
            dp[i] = max(cand)
        
        return max(dp) + 1
Related Posts