第六周 贪心、动态规划
题目数：14
本周作业
（Easy）半年内出题频次：
| 字节跳动 | 微软 | Amazon | 华为 | 百度 | 腾讯 | Apple | |||
|---|---|---|---|---|---|---|---|---|---|
| 2 | 17 | 9 | 19 | 3 | 2 | 10 | 4 | 2 | 3 |
// 方法一：记忆化搜索
var mp = map[int]int{}
func climbStairs(n int) int {
if n <= 2 {
return n
}
if k, ok := mp[n]; ok {
return k
}
count := climbStairs(n - 1) + climbStairs(n - 2)
mp[n] = count
return mp[n]
}
// 方法二：标准动态规划
func climbStairs(n int) int {
dp := make([]int, n+1)
dp[1] = 1
dp[2] = 2
for i := 3; i <= n; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
// 方法三：简化dp
func climbStairs(n int) int {
i, j := 1, 1
for k := 2; k <= n; k++ {
i, j = j, i + j
}
return j
}
// 官方题解
func climbStairs(n int) int {
p, q, r := 0, 0, 1
for i := 1; i <= n; i++ {
p = q
q = r
r = p + q
}
return r
}
// 方法四：通项公式
func climbStairs(n int) int {
sqrt5 := math.Sqrt(5)
pow1 := math.Pow((1+sqrt5)/2, float64(n+1))
pow2 := math.Pow((1-sqrt5)/2, float64(n+1))
return int(math.Round((pow1 - pow2) / sqrt5))
}
// 方法五：矩阵
type matrix [2][2]int
func mul(a, b matrix) (c matrix) {
for i := 0; i < 2; i++ {
for j := 0; j < 2; j++ {
c[i][j] = a[i][0]*b[0][j] + a[i][1]*b[1][j]
}
}
return c
}
func pow(a matrix, n int) matrix {
res := matrix{{1, 0}, {0, 1}}
for ; n > 0; n >>= 1 {
if n&1 == 1 {
res = mul(res, a)
}
a = mul(a, a)
}
return res
}
func climbStairs(n int) int {
res := pow(matrix{{1, 1}, {1, 0}}, n)
return res[0][0]
}
（Medium）半年内出题频次：
| Amazon | 百度 | |
|---|---|---|
| 2 | 5 | 2 |
// 方法一：动态规划
func minimumTotal(triangle [][]int) int {
n := len(triangle)
dp := triangle[n-1]
for i := n - 2; i >=0; i-- {
for j := 0; j < len(triangle[i]); j++ {
dp[j] = triangle[i][j] + min(dp[j], dp[j+1])
}
}
return dp[0]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
// 方法二：递归+记忆化
- 673.最长递增子序列的个数 重点重点重点
（Medium）半年内出题频次：
| 微软 | Amazon | ||
|---|---|---|---|
| 4 | 3 | 3 | 2 |
// 方法一：动态规划 时间：O(n^2) 空间：O(n)
func findNumberOfLIS(nums []int) (ans int) {
maxLen := 0
n := len(nums)
dp := make([]int, n)
cnt := make([]int, n)
for i, x := range nums {
dp[i] = 1
cnt[i] = 1
for j, y := range nums[:i] {
if x > y {
if dp[j] + 1 > dp[i] {
dp[i] = dp[j] + 1
cnt[i] = cnt[j] // 重置计数
} else if dp[j] + 1 == dp[i] {
cnt[i] += cnt[j]
}
}
}
if maxLen < dp[i] {
maxLen = dp[i]
ans = cnt[i] // 重置计数
} else if maxLen == dp[i] {
ans += cnt[i]
}
}
return ans
}
// 方法二：贪心 + 前缀和 + 二分查找 官方题解
func findNumberOfLIS(nums []int) int {
d := [][]int{}
cnt := [][]int{}
for _, v := range nums {
i := sort.Search(len(d), func(i int) bool { return d[i][len(d[i])-1] >= v })
c := 1
if i > 0 {
k := sort.Search(len(d[i-1]), func(k int) bool { return d[i-1][k] < v })
c = cnt[i-1][len(cnt[i-1])-1] - cnt[i-1][k]
}
if i == len(d) {
d = append(d, []int{v})
cnt = append(cnt, []int{0, c})
} else {
d[i] = append(d[i], v)
cnt[i] = append(cnt[i], cnt[i][len(cnt[i])-1]+c)
}
}
c := cnt[len(cnt)-1]
return c[len(c)-1]
}
实战例题
以下为课上实战例题
第 11 课 贪心
贪心
（Medium）半年内出题频次：
| 字节跳动 | 微软 | Amazon | 蔚来 | 美团 | 商汤 | Apple | ||
|---|---|---|---|---|---|---|---|---|
| 2 | 5 | 17 | 17 | 4 | 3 | 5 | 2 | 6 |
// 方法一：动态规划
func coinChange(coins []int, amount int) int {
dp := make([]int, amount + 1) // 可以循环初始化
for i := 1; i <= amount; i++ {
dp[i] = amount + 1
for _, coin := range coins {
if coin <= i && dp[i-coin] + 1 < dp[i] { // 可以提取为 min 函数
dp[i] = dp[i-coin] + 1
}
}
}
if dp[amount] > amount {
return -1
}
return dp[amount]
}
// 方法二：记忆化搜索
（Easy）半年内出题频次：
| 华为 |
|---|
| 2 |
// 训练营：
var mp map[int]int
func lemonadeChange(bills []int) bool {
mp = make(map[int]int)
for _, bill := range bills {
mp[bill]++
if !exchange(bill - 5) {
return false
}
}
return true
}
func exchange(coin int) bool {
for _, c := range []int{20, 10, 5} {
for coin >= c && mp[c] > 0{
coin -= c
mp[c]--
}
}
return coin == 0
}
// 写法一：
func lemonadeChange(bills []int) bool {
five, ten := 0, 0
for _, bill := range bills {
if bill == 5 {
five++
} else if bill == 10 {
if five <= 0 {
return false
}
five--
ten++
} else {
if five > 0 && ten > 0 {
five--
ten--
} else if five >= 3 {
five -= 3
} else {
return false
}
}
}
return true
}
// 写法二：
func lemonadeChange(bills []int) bool {
five, ten := 0, 0
for _, bill := range bills {
if bill == 5 {
five++
} else if bill == 10 { // 10元是5元找零
five, ten = five - 1, ten + 1
} else if ten > 0 { // 有10元
five, ten = five - 1, ten - 1
} else { // 没有10元
five -= 3
}
if five < 0 { // 判断5元个数是否小于0
return false
}
}
return true
}
- 455.分发饼干 重点记忆优化代码
（Easy）半年内出题频次：
| 字节跳动 | |
|---|---|
| 3 | 2 |
// 方法一：贪心
func findContentChildren(g []int, s []int) int {
sort.Ints(g)
sort.Ints(s)
child := 0
for i := 0; i < len(s) && child < len(g); i++ {
if g[child] <= s[i] {
child++
}
}
return child
}
股票问题系列通解 （Easy）半年内出题频次：
| 字节跳动 | Amazon | 高盛集团 | Apple | 微软 | |
|---|---|---|---|---|---|
| 4 | 13 | 2 | 2 | 2 | 5 |
// 方法一：贪心
func maxProfit(prices []int) (ans int) {
for i := 1; i < len(prices); i++ {
if prices[i-1] < prices[i] {
ans += prices[i] - prices[i-1]
}
}
return ans
}
// 方法二：动态规划
func maxProfit(prices []int) int {
n := len(prices)
if n < 2 {
return 0
}
dp0, dp1 := 0, -prices[0]
for i := 1; i < n; i++ {
tmp := dp0
//不持有股票
dp0 = max(dp0, dp1 + prices[i])
//持有股票
dp1 = max(dp1, tmp - prices[i])
}
return dp0
}
// 标准dp
func maxProfit(prices []int) int {
n := len(prices)
dp := make([][2]int, n)
dp[0][1] = -prices[0]
for i := 1; i < n; i++ {
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][0]-prices[i]) // 持有股票
}
return dp[n-1][0]
}
// dp 优化 1
func maxProfit(prices []int) int {
dp0, dp1 := 0, -prices[0]
for i := 1; i < len(prices); i++ {
dp0, dp1 = max(dp0, dp1 + prices[i]), max(dp0 - prices[i], dp1)
}
return dp0
}
// dp 优化2
func maxProfit(prices []int) int {
if len(prices) < 2 {
return 0
}
// 不持有股票，持有股票
dp0, dp1 := 0, -prices[0]
for _, price := range prices[1:] {
dp0, dp1 = max(dp0, dp1 + price), max(dp1, dp0 - price)
}
return dp0
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
- 45.跳跃游戏 II 重点
（Medium）半年内出题频次：
| 字节跳动 | 华为 | Amazon | 微软 | Apple | 阿里巴巴 | ||
|---|---|---|---|---|---|---|---|
| 6 | 6 | 10 | 17 | 3 | 2 | 5 | 2 |
// 自己：贪心
func jump(nums []int) (ans int) {
n := len(nums)
if n < 2 {
return ans
}
ans, curMaxJump, preMaxJump := 1, nums[0], nums[0]
for i := 1; i < n; i++ {
if i > curMaxJump {
curMaxJump = preMaxJump
ans++
}
if i + nums[i] > preMaxJump {
preMaxJump = i + nums[i]
}
}
return ans
}
// 官方：贪心 正向
func jump(nums []int) int {
length := len(nums)
end := 0
maxPosition := 0
steps := 0
for i := 0; i < length - 1; i++ {
maxPosition = max(maxPosition, i + nums[i])
if i == end {
end = maxPosition
steps++
}
}
return steps
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
// 官方：反向
func jump(nums []int) int {
position := len(nums) - 1
steps := 0
for position > 0 {
// 找可以跳到pos
for i := 0; i < position; i++ {
if i + nums[i] >= position {
position = i
steps++
break
}
}
}
return steps
}
- 1665.完成所有任务的最少初始能量 重点重点重点重点重点
（Hard）半年内出题频次：
| eBay |
|---|
| 2 |
// 贪心
func minimumEffort(tasks [][]int) (ans int) {
sort.Slice(tasks, func(i, j int) bool {
u, v := tasks[i], tasks[j]
return u[0] - u[1] < v[0] - v[1]
})
suma := 0
for _, task := range tasks {
if ans < suma + task[1] {
ans = suma + task[1]
}
// 实际需要能量
suma += task[0]
}
return ans
}
// 训练营写法
func minimumEffort(tasks [][]int) (ans int) {
sort.Slice(tasks, func(i, j int) bool {
u, v := tasks[i], tasks[j]
// 升序
return u[0] - u[1] < v[0] - v[1]
})
// 倒序遍历
for i := len(tasks) - 1; i >= 0; i-- {
ans = max(tasks[i][1], ans + tasks[i][0])
}
return ans
}
// 训练营反向
func minimumEffort(tasks [][]int) (ans int) {
sort.Slice(tasks, func(i, j int) bool {
u, v := tasks[i], tasks[j]
// 降序
return u[0] - u[1] > v[0] - v[1]
})
for _, task := range tasks {
ans = max(task[1], ans + task[0])
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
第 12 课 动态规划
动态规划（一）
- 322.零钱兑换 （Medium）半年内出题频次：
| 字节跳动 | 微软 | Amazon | 蔚来 | 美团 | 商汤 | Apple | ||
|---|---|---|---|---|---|---|---|---|
| 2 | 5 | 17 | 17 | 4 | 3 | 5 | 2 | 6 |
// 方法一：动态规划
func coinChange(coins []int, amount int) int {
dp := make([]int, amount + 1)
for i := 1; i <= amount; i++ {
dp[i] = math.MaxInt32
for _, coin := range coins {
if coin <= i && dp[i-coin] + 1 < dp[i] {
dp[i] = dp[i-coin] + 1
}
}
}
if dp[amount] > amount {
return -1
}
return dp[amount]
}
// 方法二：记忆化搜索
func coinChange(coins []int, amount int) int {
if amount < 1 {
return 0
}
count := make([]int, amount)
var dp func(rem int) int
dp = func(rem int) int {
if rem < 0 {
return -1
}
if rem == 0 {
return 0
}
if count[rem-1] != 0 {
return count[rem-1]
}
min := math.MaxInt32
for _, coin := range coins {
res := dp(rem-coin)
if res >= 0 && res < min {
min = res + 1
}
}
if min == math.MaxInt32 {
count[rem-1] = -1
} else {
count[rem-1] = min
}
return count[rem-1]
}
return dp(amount)
}
（Medium）半年内出题频次：
| 字节跳动 | 微软 | Amazon | ||
|---|---|---|---|---|
| 2 | 6 | 2 | 6 | 2 |
// 方法一：标准dp
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
if obstacleGrid[0][0] == 1 {
return 0
}
m, n := len(obstacleGrid), len(obstacleGrid[0])
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
}
dp[0][0] = 1
// 第一行
for i := 1; i < n; i++ {
dp[0][i] = dp[0][i-1]
if obstacleGrid[0][i] == 1 {
dp[0][i] = 0
}
}
// 第一列
for i := 1; i < m; i++ {
dp[i][0] = dp[i-1][0]
if obstacleGrid[i][0] == 1 {
dp[i][0] = 0
}
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if obstacleGrid[i][j] == 1 {
dp[i][j] = 0
} else {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
}
return dp[m-1][n-1]
}
// 方法二：降维dp
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
m, n := len(obstacleGrid), len(obstacleGrid[0])
dp := make([]int, n)
if obstacleGrid[0][0] == 0 {
dp[0] = 1
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if obstacleGrid[i][j] == 1 {
dp[j] = 0
} else if j > 0 { // 第一列不用处理
dp[j] += dp[j-1]
}
}
}
return dp[n-1]
}
- 1143.最长公共子序列 重点重点
（Medium）半年内出题频次：
| 字节跳动 | 美团 | Amazon | 小米 | VMware | ||
|---|---|---|---|---|---|---|
| 2 | 8 | 3 | 6 | 7 | 3 | 3 |
// 注释为训练营[java]版本
func longestCommonSubsequence(text1 string, text2 string) int {
m, n := len(text1), len(text2)
// text1, text2 = " " + text1, " " + text2
f := make([][]int, m + 1)
for i := 0; i <= m; i++ {
f[i] = make([]int, n + 1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
// if text1[i] == text2[j] {
if text1[i-1] == text2[j-1] {
f[i][j] = f[i-1][j-1] + 1
} else {
f[i][j] = max(f[i-1][j], f[i][j-1])
}
}
}
return f[m][n]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
// 速度极快
func longestCommonSubsequence(text1 string, text2 string) int {
m := len(text1)
n := len(text2)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
for i, c1 := range text1 {
for j, c2 := range text2 {
if c1 == c2 {
dp[i+1][j+1] = dp[i][j] +1
} else {
dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
}
}
}
return dp[m][n]
}
// 训练营扩展练习
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int f[][] = new int[m + 1][n + 1];
int preType[][] = new int[m + 1][n + 1];
text1 = " " + text1;
text2 = " " + text2;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i) == text2.charAt(j)) {
f[i][j] = f[i-1][j-1] + 1;
preType[i][j] = 2;
} else {
if (f[i-1][j] > f[i][j-1]) {
f[i][j] = f[i-1][j];
preType[i][j] = 0;
} else {
f[i][j] = f[i][j-1];
preType[i][j] = 1;
}
}
}
}
print(text1, text2, preType, m, n);
return f[m][n];
}
void print(String text1, String text2, int[][] preType, int i, int j) {
if (i == 0 || j == 0) return;
if (preType[i][j] == 0) {
print(text1, text2, preType, i - 1, j);
} else if (preType[i][j] == 1){
print(text1, text2, preType, i, j - 1);
} else {
print(text1, text2, preType, i - 1, j - 1);
System.out.print(text1.charAt(i));
}
}
}
- 300.最长递增子序列 重点重点重点
（Medium）半年内出题频次：
| 华为 | 字节跳动 | 微软 | Amazon | VMware | 滴滴 | 三星 | Apple | ||
|---|---|---|---|---|---|---|---|---|---|
| 4 | 16 | 10 | 6 | 3 | 3 | 13 | 3 | 4 | 2 |
// 训练营[java]
func lengthOfLIS(nums []int) int {
n := len(nums)
f := make([]int, n)
for i := 0; i < n; i++ {
f[i] = 1
}
for i := 1; i < n; i++ {
for j := 0; j < i; j++ {
if nums[j] < nums[i] {
f[i] = max(f[i], f[j] + 1)
}
}
}
ans := 0
for i := 0; i < n; i++ {
ans = max(ans, f[i])
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
// 扩展版本
func lengthOfLIS(nums []int) int {
n := len(nums)
f, pre := make([]int, n), make([]int, n)
for i := 0; i < n; i++ {
f[i], pre[i] = 1, -1
}
for i := 1; i < n; i++ {
for j := 0; j < i; j++ {
if nums[j] < nums[i] && f[i] < f[j] + 1 {
f[i], pre[i] = f[j] + 1, j
}
}
}
ans, end := 0, -1
for i := 0; i < n; i++ {
if ans < f[i] {
ans = f[i]
end = i
}
}
print(nums, pre, end)
return ans
}
func print(nums, pre []int, i int) {
if pre[i] != -1 {
print(nums, pre, pre[i])
}
fmt.Println(nums[i])
}
// 训练营扩展，打印具体子序列
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int f[] = new int[n];
int pre[] = new int[n];
for (int i = 0; i < n; i++) {
f[i] = 1;
pre[i] = -1;
}
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i] && f[i] < f[j] + 1) {
f[i] = f[j] + 1;
pre[i] = j;
}
}
}
int ans = 0;
int end = -1;
for (int i = 0; i < n; i++) {
if (ans < f[i]) {
ans = f[i];
end = i;
}
}
print(nums, pre, end);
return ans;
}
void print(int[] nums, int[] pre, int i) {
if (pre[i] != -1) print(nums, pre, pre[i]);
System.out.println(nums[i]);
}
}
// 方法一：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int row = nums.size();
if (row == 0) {
return 0;
}
std::vector<int> stack;
stack.push_back(nums[0]);
for (int i = 1; i < row; i++) {
// 比栈顶元素大，push
if (nums[i] > stack.back()) {
stack.push_back(nums[i]);
} else {
for (int j = 0; j < stack.size(); j++) {
if (nums[i] <= stack[j]) {
stack[j] = nums[i];
break;
}
}
}
}
return stack.size();
}
};
// 方法二:
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int row = nums.size();
if (row == 0) {
return 0;
}
std::vector<int> stack;
stack.push_back(nums[0]);
for (int i = 1; i < row; i++) {
//比栈顶元素大，push
if (nums[i] > stack.back()) {
stack.push_back(nums[i]);
} else {
int pos = binary_search(stack, nums[i]);
stack[pos] = nums[i];
}
}
return stack.size();
}
int binary_search(vector<int> stack, int num) {
int start = 0;
int end = stack.size() - 1;
while (start <= end) {
int mid = start + ((end - start) >> 1);
if (num <= stack[mid]) {
if (mid == 0 || stack[mid - 1] < num) {
return mid;
} else {
end = mid -1;
}
} else {
start = mid + 1;
}
}
return -1;
}
};
// 官方题解
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int len = 1, n = (int)nums.size();
if (n == 0) {
return 0;
}
vector<int> d(n + 1, 0);
d[len] = nums[0];
for (int i = 1; i < n; ++i) {
if (nums[i] > d[len]) {
d[++len] = nums[i];
} else {
// 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
int l = 1, r = len, pos = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (d[mid] < nums[i]) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
d[pos + 1] = nums[i];
}
}
return len;
}
};
（Easy）半年内出题频次：
| 字节跳动 | 微软 | Amazon | Intel | 阿里巴巴 | eBay | Apple | |||
|---|---|---|---|---|---|---|---|---|---|
| 5 | 10 | 13 | 35 | 30 | 4 | 9 | 3 | 5 | 11 |
// 自己
func maxSubArray(nums []int) int {
n := len(nums)
if n == 0 {
return 0
}
dp, ans := make([]int, n), nums[0]
dp[0] = nums[0]
for i := 1; i < n; i++ {
dp[i] = max(nums[i], nums[i]+dp[i-1])
ans = max(ans, dp[i])
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
// 官方
func maxSubArray(nums []int) int {
max, n := nums[0], len(nums)
for i := 1; i < n; i++ {
if nums[i] + nums[i-1] > nums[i] {
nums[i] += nums[i-1]
}
if nums[i] > max {
max = nums[i]
}
}
return max
}
（Medium）半年内出题频次：
| 字节跳动 | 微软 | Amazon | 阿里巴巴 | 百度 | Apple | 网易 | |||
|---|---|---|---|---|---|---|---|---|---|
| 6 | 7 | 3 | 11 | 2 | 2 | 6 | 13 | 2 | 2 |
// 简化dp
func maxProduct(nums []int) int {
n := len(nums)
ans, dp1, dp2 := nums[0], nums[0], nums[0]
for i := 1; i < n; i++ {
if nums[i] < 0 {
dp1, dp2 = dp2, dp1
}
dp1, dp2 = max(nums[i], dp1 * nums[i]), min(nums[i], dp2 * nums[i])
ans = max(ans, dp1)
}
return ans
}
// 标准dp
func maxProduct(nums []int) int {
n := len(nums)
dp1 := make([]int, n)
dp2 := make([]int, n)
dp1[0], dp2[0] = nums[0], nums[0]
ans := nums[0]
for i := 1; i < n; i++ {
if nums[i] < 0 {
dp1, dp2 = dp2, dp1
}
dp1[i], dp2[i] = max(nums[i], dp1[i-1] * nums[i]), min(nums[i], dp2[i-1] * nums[i])
ans = max(ans, dp1[i])
}
return ans
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}