1. 背包问题 题目 有 N 件物品和一个容量为 V 的背包。放入第 i 件物品的耗费是 Ci，其价值为 Wi。求解将哪些物品装入背包可使价值总和最大。 状态转移方程 dp[i, v] = max(dp[i - 1, v], dp[i - 1, V - Ci] + Wi

题目 小陆每天要写一份工作日报，日报标题含有日期。几年后，他翻开以前的日报，想知道两份日报的日期是否同为星期几，请编程帮助他判断。 代码 将输入数据转换为 Date 对象进行判断 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.Calendar; import java.util.Date; import java.util.Locale; public cla...

题目 在vivo产线上，每位职工随着对手机加工流程认识的熟悉和经验的增加，日产量也会不断攀升。假设第一天量产1台，接下来2天(即第二、三天)每天量产2件，接下来3天(即第四、五、六天)每天量产3件 ... ...以此类推，请编程计算出第n天总共可以量产的手机数量。 代码 (｡･∀･)ﾉﾞ嗨，这就是差距！！！  public int solution (int n) { int production = 0; int curProduction = 1; int curTotal = 1; int total = 0; for (int i = 1; i <= n; i++) { if (...

B 树（B- 树） 概念 关于 B 树 和 B+ 树 B 树是一棵 多路平衡查找树。其定义为（一般用 m 表示 B 树 的阶数）：  每个节点最多有 m-1 个关键字 根节点最少可以只有 1 个关键字 非根节点至少有 m/2 个关键字 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的关键字都小于它，每个关键字的右子树中的关键字都大于它 所有叶子节点都位于同一层  B 树的插入 判断当前节点 key 的个数是否小于等于 m-1，如果满足，直接插入到当前节点，如果不满足，根据节点中间的 key 将这个节点一分为二，中间的节点放到父节点中。若父节点 key 的数量也超出范围，向上继...

题目 给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。 代码 深度有限搜索超时  int count; public int combinationSum4(int[] nums, int target) { count = 0; Arrays.sort(nums); dfs(nums, 0, target); return count; } private void dfs(int[] nums, int pos, int target) { if (target == 0) { count++; return; } for (int i = 0; i &lt...

题目 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。 说明  所有数字都是正整数。 解集不能包含重复的组合。  代码  // 2020-09-09 11:55:20 public List<List<Integer>> combinationSum3(int k, int n) { List<List<Integer>> res = new ArrayList<>(); int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9}; dfs(nu...

题目 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。 代码  public List<List<Integer>> combinationSum2(int[] candidates, int target) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(candidates); dfs(candidates, 0...

题目 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。 思路 简单的回溯算法的使用 代码  public List<List<Integer>> combine(int n, int k) { List<List<Integer>> res = new ArrayList<>(); if (k <= 0 || n < k) { return res; } Deque<Integer> path = new ArrayDeque<>(); dfs(n, k, 1, pat...

题目 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。 思路 根据给定数组可以想象构成一父节点的子节点为数组全部元素的树，然后利用深度优先遍历和回溯剪枝。 代码  public List<List<Integer>> combinationSum(int[] candidates, int target) { List<List<Integer>> res = new ArrayList&lt...

题目 你要出去旅游，有N元的预算住酒店，有M家酒店供你挑选，这些酒店都有价格X。 需要你正好花完这N元住酒店（不能多，也不能少）最少能住几晚？返回最少住的天数，没有匹配的返回-1  比如你有1000元，所有酒店都是大于1000的，则返回-1 比如你有1000元，有1家1000元的，有1家300，有1家700。则最少能住1晚，最多住2晚（300+700）。返回1 比如你有1000元，有1家387元，有1家2元，有一家611，则返回3（3家各住1天） 比如你有1000元，有1家1元的，有一家2元的，有一家1001元的，则返回500（1元的1000天，2元的500天）  代码 import java...

题目 小赛要去位于 A 市的小码家。小赛来到 A 市的车站，买了一张 A 市的地图，他发现这里的地形非常的复杂。A 市的街道一共有 N 个路口，M 条道路，每条道路连接着两个路口，并且有各自的长度。目前，小赛所在的车站位于编号为 1 的路口，而小码家所在的路口编号为 N，小赛准备打出租车去，当然，路程越小，付的钱就越少。问题摆在眼前：请帮助小赛寻找一条最短路径，使得他可以花最少的钱到达小码家。 代码 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impor...

题目 A、B两伙马贼意外地在一片沙漠中发现了一处金矿，双方都想独占金矿，但各自的实力都不足以吞下对方，经过谈判后，双方同意用一个公平的方式来处理这片金矿。处理的规则如下：他们把整个金矿分成n段，由A、B开始轮流从最左端或最右端占据一段，直到分完为止。  马贼A想提前知道他们能分到多少金子，因此请你帮忙计算他们最后各自拥有多少金子?（两伙马贼均会采取对己方有利的策略） 思路  二维数组 dp[i][j] 表示 A 在 i 和 j 段内所能获得的最大值 一维数组 sum[i] 表示 1~i 金矿质量和  动态规划方程为：  dp[i][j] = sum[j] - sum[i-1] + Math.m...

题目 给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。两个相邻元素间的距离为 1 。 代码 广度优先搜索，将为 0 的坐标点入队，然后递归判断当前坐标四周的点，若值为 0 跳过，否则，将其值改为当前坐标 de 值 + 1.  public int[][] updateMatrix(int[][] matrix) { Queue<int[]> queue = new LinkedList<>(); int m = matrix.length, n = matrix[0].length; for (int i = 0; i < m; i++) {...

题目 实现一个函数，检查一棵二叉树是否为二叉搜索树。 代码 中序遍历  TreeNode pre = null; public boolean isValidBST(TreeNode root) { if (root == null) return true; if (!isValidBST(root.left)) return false; if (pre != null && root.val <= pre.val) return false; pre = root; if (!isValidBST(root.right)) return false; return ...