置顶科普
年份是毕业年份，2021是指2021年毕业，不是2021年面试
鲂的2021秋招算法总结目录（已完结）
1. 分享｜2021秋招算法总结1-DFS篇
2. 分享｜2021秋招算法总结2-BFS篇
3. 分享｜2021秋招算法总结3-链表篇
4. 分享｜2021秋招算法总结4-二叉树篇
5. 分享｜2021秋招算法总结5-排序算法篇
6. 分享｜2021秋招算法总结6-字符串篇
- 分享｜2021秋招算法总结7-双指针篇
- 分享｜2021秋招算法总结8-哈希篇
- 分享｜2021秋招算法总结9-位运算
- 分享｜2021秋招算法总结10-数组篇
- 分享｜2021秋招算法总结11-动规篇
- 分享｜2021秋招算法总结12-栈篇
鲂的2021秋招经验总结（不定时更新）
1. 分享｜2021届毕业生秋招经验总结1-岗位类别介绍
2. 分享｜2021届毕业生秋招经验总结2-如何选择offer
鲂的面经整理目录（已完结）
1. 美团金融｜安卓客户端｜面经｜offer｜2021届秋招｜
2. 拼多多｜客户端开发｜面经｜offer｜2021届秋招｜
3. 网易云音乐｜安卓客户端｜面经｜offer｜2021届秋招｜
4. 阿里巴巴｜客户端开发｜面经｜2021届秋招｜
5. 花旗银行｜软件工程师｜面经｜offer｜2021届秋招｜
6. 字节跳动｜客户端开发｜面经｜2021届秋招｜
7. 叠纸游戏｜客户端开发｜面经｜2021届秋招｜
8. 腾讯｜客户端开发｜面经｜2021届秋招｜
9. 360｜安卓客户端｜面经｜offer｜2021届秋招｜
10. 作业帮｜IOS客户端｜面经｜2021届秋招｜
11. 滴滴｜安卓客户端｜面经｜2021届秋招｜
12. 百度｜IOS客户端｜面经｜2021届秋招｜
13. 快手｜客户端开发｜面经｜2021届秋招｜
14. 顺丰科技｜安卓客户端｜面经｜offer｜2021届秋招｜
鲂的内推
1. 内推+校招秋招｜美团金融服务平台｜多项岗位｜北京+上海
本篇概要
动规较难，不适合所有人都学习，但是面试前必须知道一些基础要点。能用动规的题目通常是要求：可行性、方案数和最值。本篇列写一些背包问题及其对应的力扣中的题目，还有一些简单中等的动规常见题和系列套题。
本篇整理比较功利性（面试前必备题），如果大家对动规及其解题思路特别感兴趣的话，建议去leetbook看动态规划精讲，以下是链接
比较尴尬的是这两篇LeetBook是力扣PLUS会员专属，仅供会员免费借阅，我学了第一篇的部分内容，没学完时候会员就过期了，但是认识写这两篇的作者，他整理的都很用心，作者力扣主页：FennelDumplings。此处打个没收钱的广告，如果是学生的话，可以去看看力扣针对学生的365天365元的优惠活动，我当时花了79元才充了一个月，后面才发现有这个优惠（然而用不到了，相当尴尬）。充不充取决于自己吧，我就觉得挺省钱的顺口一推罢了。
顺便吐槽一下，我出这个系列就不是为了复制别人的题解啊，只是把相似题目整理下，方便大家刷和知道怎么提升罢了，不需要就关啊，还浪费时间点踩，很让我费解。
背包问题
推荐大家去搜一下背包9讲，我是通过这个入门的，接下来的整理只包括01背包、完全背包和多重背包，其他的自行搜索或者看我的笔记。因为力扣放外来链接会被和谐，所以考验大家检索能力的时候到了。教学视频可以看看某站，文字信息可以看看某博or某开源代码库，背包9讲的原型题及其代码可以看某a开头的辅导班对应题库或者某l开头的辅导班对应题库（力扣只有变型题）。
01背包
描述：有N件物品和一个容量为V的背包。第i件物品的体积是v[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
以下列举两种写法，实际上写法可以微调的，自己探索吧。
原型题方法1：适用于数据量比较小的时候
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N];
int[] w = new int[N];
for (int i = 0; i < N; i++){
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
System.out.println(maxValue(N, V, v, w));
}
private static int maxValue(int N, int V, int[] v, int[] w){
if (N == 0 || V == 0) return 0;
int[] dp = new int[V+1];
for (int i = 0; i < N; i++){ // 外循环从0开始递增
for (int j = V; j >= v[i]; j--){ // 内循环从V开始递减
dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
}
}
return dp[V];
}
}原型题方法2：适用于数据量比较大的时候
import java.util.Scanner;
import java.util.ArrayList;
public class Main{
static class ValueHolder{
int v,w;
public ValueHolder(int v, int w) {
this.v = v;
this.w = w;
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N];
int[] w = new int[N];
for (int i = 0; i < N; i++){
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
System.out.println(maxValue(N, V, v, w));
}
private static int maxValue(int N, int V, int[] v, int[] w){
if (N == 0 || V == 0) return 0;
int[] dp = new int[V+1];
ArrayList<ValueHolder> list = new ArrayList<>();
for (int i = 0; i < N; i++){ // 外循环从0开始递增
list.add(new ValueHolder(v[i], w[i]));
}
for (ValueHolder holder : list){
for (int j = V; j >= holder.v; j--){ // 内循环从V开始递减
dp[j] = Math.max(dp[j], dp[j - holder.v] + holder.w);
}
}
return dp[V];
}
}力扣中的变型题
- 416. 分割等和子集：给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。本题推荐题解是：@liweiwei1419的动态规划（转换为 0-1 背包问题）
- 494. 目标和：给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
- 1049. 最后一块石头的重量 II：有一堆石头，每块石头的重量都是正整数。每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：如果 x == y，那么两块石头都会被完全粉碎；如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
完全背包
描述：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是v[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
原型题方法1：适用于数据量比较小的时候
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N];
int[] w = new int[N];
for (int i = 0; i < N; i++){
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
System.out.println(maxValue(N, V, v, w));
}
private static int maxValue(int N, int V, int[] v, int[] w){
if (N == 0 || V == 0) return 0;
int[] dp = new int[V+1];
for (int i = 0; i < N; i++){ // 外循环从0开始递增
for (int j = v[i]; j<= V; j++){ //内循环从v[i]开始递增
dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
}
}
return dp[V];
}
}原型题方法2：适用于数据量比较大的时候
import java.util.Scanner;
import java.util.ArrayList;
public class Main{
static class ValueHolder{
int v,w;
public ValueHolder(int v, int w) {
this.v = v;
this.w = w;
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N];
int[] w = new int[N];
for (int i = 0; i < N; i++){
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
System.out.println(maxValue(N, V, v, w));
}
private static int maxValue(int N, int V, int[] v, int[] w){
if (N == 0 || V == 0) return 0;
int[] dp = new int[V+1];
ArrayList<ValueHolder> list = new ArrayList<>();
for (int i = 0; i < N; i++){ // 外循环从0开始递增
list.add(new ValueHolder(v[i], w[i]));
}
for (ValueHolder holder : list){
for (int j = holder.v; j <= V ; j++){ //内循环从holder.v开始递增
dp[j] = Math.max(dp[j], dp[j - holder.v] + holder.w);
}
}
return dp[V];
}
}力扣中的变型题
- 322. 零钱兑换：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
- 518. 零钱兑换 II：给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
- 377. 组合总和 Ⅳ：给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
- 面试题 08.11. 硬币：硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
多重背包
描述：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的数量为s[i]，体积是v[i]，价值是w[i]。求解将哪些物品装入背包可使体积总和不超过背包容量，且价值总和最大，输出最大价值。
原型题方法1：适用于数据量比较小的时候
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N];
int[] w = new int[N];
int[] s = new int[N];
for (int i = 0; i < N; i++){
v[i] = sc.nextInt();
w[i] = sc.nextInt();
s[i] = sc.nextInt();
}
System.out.println(maxValue(N, V, v, w, s));
}
private static int maxValue(int N, int V, int[] v, int[] w, int[] s){
if (N == 0 || V == 0) return 0;
int[] dp = new int[V+1];
for (int i = 0; i < N; i++){ // 第一重循环从0开始递增
for (int j = V; j >= 0; j--){ //第二重循环从V开始递减
for (int k = 0; k <= s[i]; k++){ //第三重循环从0开始递增
if (j >= k * v[i]) { // 判断容量是否足够
dp[j] = Math.max(dp[j], dp[j - k * v[i]] + k * w[i]);
}
}
}
}
return dp[V];
}
}原型题方法2：适用于数据量比较大的时候【二进制】
import java.util.Scanner;
import java.util.ArrayList;
public class Main{
static int MAX = 101;
static class ValueHolder{
int v,w;
public ValueHolder(int v, int w) {
this.v = v;
this.w = w;
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N];
int[] w = new int[N];
int[] s = new int[N];
for (int i = 0; i < N; i++){
v[i] = sc.nextInt();
w[i] = sc.nextInt();
s[i] = sc.nextInt();
}
System.out.println(maxValue(N, V, v, w, s));
}
public static int maxValue(int N, int V, int[] v, int[] w, int[] s){
if (N == 0 || V == 0) return 0;
int[] dp = new int[V+1];
ArrayList<ValueHolder> list = new ArrayList<>();
for (int i = 0; i < N; i++){
int cnt = s[i];
for (int k = 1; k < cnt; k *= 2){
cnt -= k;
list.add(new ValueHolder(v[i] * k, w[i] * k));
}
if (cnt >= 0) {
list.add(new ValueHolder(v[i] * cnt, w[i] * cnt));
}
}
for (ValueHolder holder : list){
for (int j = V; j >= holder.v; j--){
dp[j] = Math.max(dp[j], dp[j - holder.v] + holder.w);
}
}
return dp[V];
}
}原型题方法3：适用于数据量比较大的时候【单调队列】
代码非本人撰写，原链接【如被和谐，请自行搜索】：https://www.***.com/solution/content/16038/
import java.util.*;
public class Main{
static int MAX = 101;
static class ValueHolder{
int v,w;
public ValueHolder(int v, int w) {
this.v = v;
this.w = w;
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int V = sc.nextInt();
int[] v = new int[N];
int[] w = new int[N];
int[] s = new int[N];
for (int i = 0; i < N; i++){
v[i] = sc.nextInt();
w[i] = sc.nextInt();
s[i] = sc.nextInt();
}
System.out.println(maxValue(N, V, v, w, s));
}
private static int maxValue(int N, int C, int[] ss, int[] vs, int[] qs) {
int[] dp = new int[C+1];
Deque<int[]> dq = new LinkedList<>();
int ws = 0; // window start index
int we = 0; // window end index
for (int i=0; i<N; i++) {
int s = ss[i], v = vs[i], q = qs[i];
for (int k=0; k<s; k++) { // loop s slices
dq.clear();
ws = we = k;
for (int j=k; j<=C; j+=s) { // increment each slice by s
if ((we-ws)/s == q) { // slide window already max out
if (dq.size() > 0 && dq.peekFirst()[0] == ws) { // if window start already the max, will eject it
dq.removeFirst();
}
ws+=s;
}
int m = (j-k)/s; // multiplier
while (!dq.isEmpty() && dq.peekLast()[1] <= dp[j]-m*v) { // try to add the current index
dq.removeLast();
}
dq.addLast(new int[]{j, dp[j]-m*v});
we=j;
dp[j] = dq.peekFirst()[1]+m*v;
}
}
}
return dp[C];
}
}提升：把完全背包的题目加上数量限制就是多重背包的题目了。
斐波那契数列
- 509. 斐波那契数和剑指 Offer 10- I. 斐波那契数列：写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。
- 70. 爬楼梯和剑指 Offer 10- II. 青蛙跳台阶问题：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
- 面试题 08.01. 三步问题：三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。
- 提升题（变态跳台阶）：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。java版本代码为
public class Solution {
public int JumpFloorII(int target) {
return (int) Math.pow(2,target-1);
}
}股票系列
经典必做系列，具体题目不放了，只写区别。
- 121. 买卖股票的最佳时机和剑指 Offer 63. 股票的最大利润：最多1笔交易
- 122. 买卖股票的最佳时机 II：尽可能更多次的交易
- 123. 买卖股票的最佳时机 III：2笔交易
- 188. 买卖股票的最佳时机 IV：最多k笔交易
- 309. 最佳买卖股票时机含冷冻期：与122题的区别是卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
- 714. 买卖股票的最佳时机含手续费：与122题的区别是每笔交易都需要付手续费。
鸡蛋或者其他物品掉落
高频改造题，把鸡蛋改成任意物品（比如手机），就是道新的笔试题了。
- 887. 鸡蛋掉落：你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。你的目标是确切地知道 F 的值是多少。无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
变型题：只给2个鸡蛋时候怎么办
打家劫舍
高频改造题，搞不懂有这智商为啥去打家劫舍。
- 198. 打家劫舍：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
- 213. 打家劫舍 II：你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。
- 337. 打家劫舍 III：在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
路径
- 62. 不同路径：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？
- 63. 不同路径 II：与上一题的区别是网格中有障碍物。
改造题：面试题 08.02. 迷路的机器人：是不同路径2的求路径题目（用回溯） - 64. 最小路径和：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。每次只能向下或者向右移动一步。
- 剑指 Offer 47. 礼物的最大价值：在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
- 120. 三角形最小路径和：给定一个三角形 triangle ，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
石子游戏
很多乱七八糟的，只列举前两题，注意找规律。
- 877. 石子游戏：亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比赛时返回 true ，当李赢得比赛时返回 false。PS：此题先手必胜，想清楚为什么。
- 1140. 石子游戏 II：亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。游戏一直持续到所有石子都被拿走。假设亚历克斯和李都发挥出最佳水平，返回亚历克斯可以得到的最大数量的石头。
字符串匹配
虽然是困难，但笔面试出现频率较高
- 10. 正则表达式匹配和剑指 Offer 19. 正则表达式匹配：请实现一个函数用来匹配包含'. '和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但与"aa.a"和"ab*a"均不匹配。
- 44. 通配符匹配：与正则表达式的不同：这边的’*’是匹配任意字符串包括空串的，正则里面是零至多个的前一个字符。
字符串编辑
虽然是困难，但笔面试出现频率较高
- 面试题 01.05. 一次编辑：字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
- 72. 编辑距离：字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。
会议室
笔试经常遇到会议室题目的改造，但很尴尬的是它们都是会员题,会员题不放题目了。思路是前缀和，动态规划精讲（一）中有这个专题。
- 252. 会议室
- 253. 会议室2
- 1353. 最多可以参加的会议数目：给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。请你返回你可以参加的 最大 会议数目。
状态压缩DP
- 464. 我能赢吗：给定一个整数 maxChoosableInteger （整数池中可选择的最大数）和另一个整数 desiredTotal（累计和），判断先出手的玩家是否能稳赢（假设两位玩家游戏时都表现最佳）？
- 526. 优美的排列：假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：第 i 位的数字能被 i 整除；i 能被第 i 位上的数字整除。现在给定一个整数 N，请问可以构造多少个优美的排列？
- 1349. 参加考试的最大学生数：给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的（不可用），就用 '#' 表示；否则，用 '.' 表示。学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷，但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的一起参加考试且无法作弊的最大学生人数。学生必须坐在状况良好的座位上。
数位DP
- 面试题 17.06. 2出现的次数：编写一个方法，计算从 0 到 n (含 n) 中数字 2 出现的次数。
- 902. 最大为 N 的数字组合：我们有一组排序的数字 D，它是 {'1','2','3','4','5','6','7','8','9'} 的非空子集。（请注意，'0' 不包括在内。）现在，我们用这些数字进行组合写数字，想用多少次就用多少次。例如 D = {'1','3','5'}，我们可以写出像 '13', '551', '1351315' 这样的数字。返回可以用 D 中的数字写出的小于或等于 N 的正整数的数目。
可以用贪心的高频笔面试题
笔试经常用这些题目进行改造。如果面试时候想用贪心的话，要说清楚为什么这题可以用贪心，说不清楚的话还是其他方法吧。这边的题目别纠结难度了，对初学者来说都不简单。
- 354. 俄罗斯套娃信封问题：给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。PS：本题的改造很常在笔试中出现。
- 剑指 Offer 14- I. 剪绳子：给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]k[1]...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
- 剑指 Offer 14- II. 剪绳子 II：给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]k[1]...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
- 55. 跳跃游戏：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
- 45. 跳跃游戏 II：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。
- 134. 加油站：在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
- 56. 合并区间：给出一个区间的集合，请合并所有重叠的区间。
- 605. 种花问题：假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。
- 406. 根据身高重建队列：假设有打乱顺序的一群人站成一个队列，数组 people 表示队列中一些人的属性（不一定按顺序）。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人。请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ，其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
结束语
动规题目太多了，我尽量把我笔记里面觉得 眼熟 的题目都列举出来了。如果和我一样的普通面试者（没有算法基础，只为了找工作，不面算法岗），可能面试遇到动规的概率不大（本人自己的面试好像就遇到一次，其他人的也比较少）。但是笔试时候经常会遇到要用动规的题目，此处说的眼熟是笔试、其他人的面经或者群友讨论时候看到过的。
评论 (5)
