General
Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
public int climbStairs(int n) {
if (n == 0 || n == 1) return n;
int[] f = new int[n+1];
f[0] = 1;
f[1] = 1;
for (int i=2; i<=n; i++){
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it.
Func: f[i] = f[i-1](if s[i-1]!='0')+f[i-2](if(s[i-2]s[i-1] == '10'-'26'))
Init f[0]=f[1]=1
Ans f[n]
def numDecodings(self, s: str) -> int:
dp = [0] * (len(s)+1)
dp[0] = 1
dp[1] = 1 if s[0] != '0' else 0
for i in range(2, len(s)+1):
if s[i-1] != '0':
dp[i] = dp[i-1]
if 10 <= int(s[i-2:i]) <= 26:
dp[i] += dp[i-2]
return dp[len(s)]
300 Longest Increasing Subsequence
Given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.
Example For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3 For [4, 2, 4, 5, 3, 7], the LIS is [2, 4, 5, 7], return 4
Brute Time O(2^n)
State: f[i] = LIS in index i
Init: f[0...i] = 1
function: f[i] = max{f[j]+1}, j<i && num[j]<num[i]
Ans: max{f[0...i]}
Time O(n^2), Space O(n)
Compare to Longest Consecutive Sequence
public int longestIncreasingSubsequence(int[] nums) {
int[] f = new int[nums.length];
int ans = 0;
for (int i=1; i<nums.length; i++){
f[i] = 1; // init
for(int j=0; j<i; j++){
// 1 is f[j] itself
if(nums[j] < nums[i] && f[j]+1 > f[i]){
f[i] = f[j] + 1;
}
}
ans = Math.max(ans, f[i]);
}
return ans;
}
53. Maximum Subarray
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
dp[i]: in nums[0:i], the maximum subarray containing nums[i]
dp[i] = max(dp[i-1]+nums[i], nums[i])
public int maxSubArray(int[] nums) {
int maxSum = nums[0];
int ans = nums[0];
for(int i=1; i<nums.length; i++){
maxSum = Math.max(maxSum+nums[i], nums[i]);
ans = Math.max(ans, maxSum);
}
return ans;
}
152. Maximum Product Subarray
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
max[i]: in nums[0:i], the maximum product subarray containing nums[i]
Maintain a min and a max variable, if nums[i] is negative, swap them
ans[i] = max(max[i-1]+nums[i], nums[i])
public int maxProduct(int[] nums) {
int ans=nums[0], min=nums[0], max=nums[0];
for(int i=1; i<nums.length; i++){
if(nums[i] < 0){
int tmp = min;
min = max;
max = tmp;
}
// if nums[i]==0, both max and min will be updated as 0, so disrupt the continuous
max = Math.max(nums[i], max*nums[i]);
min = Math.min(nums[i], min*nums[i]);
ans = Math.max(ans, max);
}
return ans;
}
96. Unique Binary Search Tree
Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
[1, 2, 3, 4, 5, 6, 7]
with 3
as the root, left subsequence [1, 2]
and the right subsequence [4, 5, 6, 7],
dp[2] * dp[4] to dp[7]
"""
dp[i] 為數字 i 所以可構成的BST個數
dp[i] = sum of dp[j-1] * dp[i-j] for 1 <= j <= i
"""
class Solution:
def numTrees(self, n: int) -> int:
dp = [0] * (n+1)
dp[0], dp[1] = 1, 1
for i in range(2, n+1):
for j in range(1, i+1):
dp[i] += dp[j-1] * dp[i-j]
return dp[n]
95. Unique Binary Search Tree II
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
def generateTrees(self, n: int) -> List[TreeNode]:
if not n: return []
return self.helper(1, n)
def helper(self, start, end):
if start > end:
return [None]
if start == end:
return [TreeNode(start)]
res = []
for i in range(start, end+1):
lefts = self.helper(start, i-1)
rights = self.helper(i+1, end)
for l in lefts:
for r in rights:
node = TreeNode(i)
node.left = l
node.right = r
res.append(node)
return res
1235. Maximum Profit in Job Scheduling
We have n
jobs, where every job is scheduled to be done from startTime[i]
to endTime[i]
, obtaining a profit of profit[i]
.
DP + binary search
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
# sort by end, 如果sort by start, 有可能其中一個period 很長
# 而這個period 中間如果有更高的profit 就會搜尋不到
jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
# base case
dp = [[0, 0]]
for s, e, p in jobs:
# start day+1 作為upper bound
idx = bisect.bisect(dp, [s+1])-1
# 如果每一次都update
# corner case: 有重複的start and end 的時候, 不一定拿到較大profit那個
if dp[idx][1] + p > dp[-1][1]:
dp.append([e, dp[idx][1]+p])
return dp[-1][1]
Last updated
Was this helpful?