文章目录
加减的目标值
https://leetcode-cn.com/problems/YaVDxD/
剑指 Offer II 102. 加减的目标值
给定一个正整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
class Solution {
// dfs() 搜索
public int findTargetSumWays(int[] nums, int target) {
if (nums == null) {
return -1;
}
int len = nums.length;
if (len <= 0) {
return -1;
}
goalLen = len;
dfs(0, nums, nums[0], target);
dfs(0, nums, -nums[0], target);
return res;
}
private int res = 0;
private int goalLen = 0;
private void dfs(int index, int[] nums, int sum, int target) {
if (index == (goalLen - 1)) {
if (sum == target) {
res++;
return;
}
} else {
dfs(index + 1, nums, sum + nums[index + 1], target);
dfs(index + 1, nums, sum - nums[index + 1], target);
}
}
}
class Solution02 {
// DP 动态规划（二维的动态规划问题！！！）
class Solution {
/**
* 记数组的元素和为 sum，添加 - 号的元素之和为 neg，则其余添加 + 的元素之和为 sum−neg ，得到的表达式的结果为
* (sum−neg)−neg = sum−2⋅neg = target
* neg = (sum-target) / 2
*/
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int num : nums) {
sum += num;
}
int diff = sum - target;
if (diff < 0 || diff % 2 != 0) {
return 0;
}
int n = nums.length, neg = diff / 2;
/**
dp[i][j] 表示在数组 nums 的前 i 个数中选取元素，使得这些元素之和等于 j 的方案数
假设数组 nums 的长度为 n，则最终答案为 dp[n][neg]
动态规划方程是：
*/
int[][] dp = new int[n + 1][neg + 1];
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
int num = nums[i - 1];
for (int j = 0; j <= neg; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= num) {
dp[i][j] += dp[i - 1][j - num];
}
}
}
return dp[n][neg];
}
}
}
剑指 Offer II 103. 最少的硬币数目
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
https://leetcode-cn.com/problems/gaM7Ch/
public class Solution {
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
// dp[i] 表示：组成金额 i 所需最少的硬币数量
// 那么 dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
- 时间：O(n^2)
- 空间：O(n)
剑指 Offer 42. 连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
思路：DP 或者 线段树（这个感觉挺有意思的，与时间玩玩）
class Solution {
public int maxSubArray(int[] nums) {
if (nums == null) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
int res = dp[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
res = Math.max(res, dp[i]);
}
return res;
}
}
// 滚动数组优化后
public int maxSubArray(int[] nums) {
int currentMax = nums[0];
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
int previousMax = currentMax;
currentMax = Math.max(previousMax + nums[i], nums[i]);
max = Math.max(max, currentMax);
}
return max;
}
- 时间：O(n)
- 空间：O(n)，这里可以直接使用滚动数组来优化为 O(1)
64. 最小路径和
https://leetcode-cn.com/problems/minimum-path-sum/
class Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length <= 0) {
return 0;
}
int row = grid.length;
int col = grid[0].length;
int[][] dp = new int[row][col];
dp[0][0] = grid[0][0];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (i == 0 && j > 0) {
// 第一行 DP:只能从 左边 过来
dp[i][j] = dp[0][j - 1] + grid[0][j];
} else if (j == 0 && i > 0) {
// 第一列 DP:只能从 上边 过来
dp[i][j] = dp[i - 1][0] + grid[i][0];
} else if (j > 0 && i > 0) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
}
return dp[row - 1][col - 1];
}
}
- 时间：O(mn)
- 空间：O(mn)
剑指 Offer 46. 把数字翻译成字符串
https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
class Solution01 {
public int translateNum(int num) {
String str = String.valueOf(num);
if (str.length() <= 1) {
return 1;
}
int[] dp = new int[str.length()];
dp[0] = 1;
dp[1] = 1;
if (str.substring(0, 2).compareTo("25") <= 0 && str.substring(0, 2).compareTo("10") >= 0) {
dp[1] = 2;
}
for (int i = 2; i < str.length(); i++) {
dp[i] = dp[i - 1];
if (str.substring(i - 1, i + 1).compareTo("25") <= 0 && str.substring(i - 1, i + 1).compareTo("10") >= 0) {
dp[i] = Math.max(dp[i - 1] + dp[i - 2], dp[i]);
}
}
return dp[str.length() - 1];
}
}
// 整洁的一种写法：
class Solution {
public int translateNum(int num) {
String s = String.valueOf(num);
int[] dp = new int[s.length()+1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= s.length(); i ++){
String temp = s.substring(i-2, i);
if(temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0)
dp[i] = dp[i-1] + dp[i-2];
else
dp[i] = dp[i-1];
}
return dp[s.length()];
}
}
- 时间：O(n)
- 空间：O(n)
823. 带因子的二叉树
https://leetcode-cn.com/problems/binary-trees-with-factors/
思路：
// 设 dp(v) 是以 v 为根节点的树种类数。
// 其子节点就是 x*y = v
// dp[v] = dp(x) * dp(y)
// 为了快速的计算，我们使用 index 数组快速查找：如果 A[k] = A[i] / A[j]，那么 index[A[i] / A[j]] = k
class Solution {
public int numFactoredBinaryTrees(int[] arr) {
if (arr == null) {
return 0;
}
// 设 dp(v) 是以 v 为根节点的树种类数。
// 其子节点就是 x*y = v
// dp[v] = dp(x) * dp(y)
// 为了快速的计算，我们使用 index 数组快速查找：如果 A[k] = A[i] / A[j]，那么 index[A[i] / A[j]] = k
long[] dp = new long[arr.length];
Arrays.fill(dp, 1);
//在上面的例子中我们知道 x < v 和 y < v，我们可以用动态规划的方法按照升序值计算 dp[i] 的值
Arrays.sort(arr);
// arr 数值：index
HashMap<Integer, Integer> index = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
index.put(arr[i], i);
}
int MOD = 1_000_000_007;
for (int i = 0; i < arr.length; i++) {
// 在数组中 找 i 的所有因子
for (int j = 0; j < i; j++) {
if (arr[i] % arr[j] == 0) {
int right = arr[i] / arr[j];
if (index.containsKey(right)) {
dp[i] = (dp[i] + dp[j] * dp[index.get(right)]) % MOD;
}
}
}
}
long res = 0;
for (long l : dp) {
res += l;
}
return (int) (res % MOD);
}
}
- 时间：O(n^2)
- 空间：O(n)
剑指 Offer 49. 丑数
https://leetcode-cn.com/problems/chou-shu-lcof/
思路：
最小堆思路
既然是求：第n个元素，那么我们就考虑使用堆的数据结构即可。
初始时堆为空。首先将最小的丑数 11 加入堆。
每次取出堆顶元素 xx，则 xx 是堆中最小的丑数，由于 2x, 3x, 5x2x,3x,5x 也是丑数，因此将 2x, 3x, 5x2x,3x,5x 加入堆。
上述做法会导致堆中出现重复元素的情况。为了避免重复元素，可以使用哈希集合去重，避免相同元素多次加入堆。
此题中：要求是 最小堆+不重复。所以直接可以使用 TreeSet 数据结构，避免：PriorityQueue+Set 数据结构
// 刚开始写出来的，运行不对是因为最小堆中有重复元素，所以会导致结果不对。需要去重。
class Solution {
public int nthUglyNumber(int n) {
if (n <= 0) {
return 0;
}
PriorityQueue<Long> queue = new PriorityQueue<>();
Long res = null;
queue.add(1L);
for (int i = 1; i <= n; i++) {
res = queue.poll();
queue.add(res * 2);
queue.add(res * 3);
queue.add(res * 5);
}
return res.intValue();
}
}
// AC
class Solution {
public int nthUglyNumber(int n) {
if (n <= 0) {
return 0;
}
TreeSet<Long> set = new TreeSet<>();
Long res = null;
set.add(1L);
for (int i = 1; i <= n; i++) {
res = set.pollFirst();
set.add(res * 2);
set.add(res * 3);
set.add(res * 5);
}
return res.intValue();
}
}
- 时间：O(nlogN)
- 空间：O(n)
动态规划
// 我写的：通过 500 / 596 个通过测试用例（不太明白时间浪费在哪里了呐？）
class Solution {
public int nthUglyNumber(int n) {
if (n <= 0) {
return 0;
}
//下标：对应的丑数
//使用 HashMap 不使用 int[] ,主要是为了避免 Java JVM 自己默认的数组初始化，有程序员自定义
HashMap<Integer, Integer> map = new HashMap<>();
map.put(1, 1);
map.put(2, 2);
map.put(3, 3);
map.put(4, 4);
map.put(5, 5);
int index = n;
for (int i = 6; map.size() < n; i++) {
index = i;
// continue 之间有相应顺序
if (i % 2 == 0 && map.containsKey(i / 2)) {
map.put(i, map.get(i / 2) * 2);
continue;
}
if (i % 3 == 0 && map.containsKey(i / 3)) {
map.put(i, map.get(i / 3) * 3);
continue;
}
if (i % 5 == 0 && map.containsKey(i / 5)) {
map.put(i, map.get(i / 5) * 5);
continue;
}
}
return map.get(index).intValue();
}
}
70. 爬楼梯
https://leetcode-cn.com/problems/climbing-stairs/
思路
我们用 f(x) 表示爬到第 x 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：
f(x) = f(x - 1) + f(x - 2)
它意味着爬到第 xx 级台阶的方案数是爬到第 x - 1 级台阶的方案数和爬到第 x - 2 级台阶的方案数的和。很好理解，因为每次只能爬 1级或 2级，所以 f(x) 只能从 f(x - 1) 和 f(x - 2) 转移过来，而这里要统计方案总数，我们就需要对这两项的贡献求和。
class Solution {
public int climbStairs(int n) {
if (n == 0 || n == 1 || n == 2) {
return n;
}
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
- 时间：O(n)
- 空间：O(n) 这里其实可以搞为O(1)的， 因为只保存上一步和上两步的方法数即可。
120. 三角形最小路径和
https://leetcode-cn.com/problems/triangle/
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
/**
先下向上进行状态递推。
对应的数值表示：到达该点的最小路径和
从 倒数第二行 开始，因为倒数第一行就是它本身
*/
for (int i = triangle.size() - 2; i >= 0; i--) {
for (int j = 0; j < triangle.get(i).size(); j++) {
Integer current = triangle.get(i).get(j);
// 正下方
Integer xiaFang = triangle.get(i + 1).get(j);
// 斜下方
Integer xieXiafang = triangle.get(i + 1).get(j + 1);
// 状态转移方程
current = current + Math.min(xieXiafang, xiaFang);
List<Integer> tmp = triangle.get(i);
tmp.set(j, current);
triangle.set(i, tmp);
}
}
return triangle.get(0).get(0);
}
}
- 时间：O(行*列)
- 空间：（O(1)）
152. 乘积最大子数组
https://leetcode-cn.com/problems/maximum-product-subarray/
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列
思路：
dp[i] 表示从0到i最大子数组乘积，状态方程是
dp[i] = dp[i-1]*nums[i]
但是这里需要注意可能存在 -2,3,3,3,3,-9 的情况，所以还需要一个dp[]状态来保存其当前的最小值。
class Solution {
private int threeMax(int a, int b, int c) {
int tmp = Math.max(a, b);
return tmp > c ? tmp : c;
}
private int threeMin(int a, int b, int c) {
int tmp = Math.min(a, b);
return tmp < c ? tmp : c;
}
public int maxProduct(int[] nums) {
if (nums == null) {
return 0;
}
int maxRes = nums[0];
// 二维数组：因为可能存在 -2,3,3,3,3,-9 的情况
//正的最大值
int[] positiveMax = new int[nums.length];
//负的最大值
int[] negativeMax = new int[nums.length];
positiveMax[0] = nums[0];
negativeMax[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
int x = positiveMax[i - 1] * nums[i];
int y = negativeMax[i - 1] * nums[i];
positiveMax[i] = this.threeMax(x, y, nums[i]);
negativeMax[i] = this.threeMin(x, y, nums[i]);
maxRes = positiveMax[i] > maxRes ? positiveMax[i] : maxRes;
}
return maxRes;
}
}
- 时间：O(n)
- 空间：O(n)，空间还可优化，见leetcode 题解即可，这里为了不破坏dp的模板，就不展示出来了！
121 股票买卖序列
121，122，123，309，188，714 题
暂时只做：
121 和 122 系列即可，因为工作中也应该很久很久不会用到 三维的DP定义，面试自然也是用不啦~
121 从始至终只能买卖一次股票系列
思路：
- 对于第 i 个数而言，保存之前的最小值，然后判断当前 i 处卖出，利益是否最大。
- dp[i][2] 表示到 i 处所获得的最大利润。
class Solution {
public int maxProfit(int[] prices) {
if (prices == null) {
return 0;
}
// dp[i][2] i 表示到 i 处所获得的最大利润, i的范围是: 0->n
// 另外两个维度表示：0：持股 1：不持股
int[][] maxPro = new int[prices.length][2];
// 持股话利润就是 负的 prices[0]
maxPro[0][0] = -prices[0];
// 不持股的话利润就是 0
maxPro[0][1] = 0;
int maxRes = 0;
for (int i = 1; i < prices.length; i++) {
// 求今天 需持股时的最大利润（两种选择：买入 或 等待）
// 坑点：只允许交易一次，所以 手上的现金数就是当天的股价的相反数）。
maxPro[i][0] = Math.max(-prices[i], maxPro[i - 1][0]);
// 求今天 不持股时的最大利润（两种选择：卖出 或 等待）
maxPro[i][1] = Math.max(maxPro[i - 1][0] + prices[i], maxPro[i - 1][1]);
maxRes = maxPro[i][0] > maxPro[i][1] ? maxPro[i][0] : maxPro[i][1];
}
return maxRes;
//直接写为这样也可以~~~
return maxPro[prices.length - 1][1];
}
}
//因为这个是个简单问题，所以有一个简单解法如下：
public class Solution {
public int maxProfit(int prices[]) {
int minprice = Integer.MAX_VALUE;
int maxprofit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minprice) {
minprice = prices[i];
} else if (prices[i] - minprice > maxprofit) {
maxprofit = prices[i] - minprice;
}
}
return maxprofit;
}
}
- 时间：O(n)
- 空间：O(1)
- 时间：O(n)
- 空间：O(n)
122 可同天，可以交易无数次的情况
思路与121相同，只是121坑点那里不同而已。
// 坑点：只允许交易一次，所以 手上的现金数就是当天的股价的相反数）。
maxPro[i][0] = Math.max(-prices[i], maxPro[i - 1][0]);
换为：
maxPro[i][0] = Math.max(maxPro[i - 1][1] - prices[i], maxPro[i - 1][0]);
即可！！！
300. 最长递增子序列
https://leetcode-cn.com/problems/longest-increasing-subsequence/
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
思路1：动态规划
定义 dp[i] 为考虑前 i 个元素，以第 i个数字结尾的最长上升子序列的长度
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
// 初始化应该都是 1
int res = 1;
dp[0] = 1;
for (int i = 1; i < nums.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
res = Math.max(res, dp[i]);
}
return res;
}
}
- 时间：O(n^2)
- 空间：O(n)
思路2
- 贪心 + 二分查找，此思路见：https://time.geekbang.org/course/detail/100019701-69783
class Solution {
int search(int[] res, int left, int right, int target) {
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (res[mid] == target) {
//找到真正的想等值，那就直接返回。否则就返回 left 的值
return mid;
} else if (res[mid] < target) {
left = mid + 1;
} else if (res[mid] > target) {
right = mid - 1;
}
}
return left;
}
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
// 最大的值永远在：最后一个数字
int[] res = new int[nums.length];
// 两个初始化 还蛮重要的 ！
res[0] = nums[0];
int len = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > res[len]) {
len++;
res[len] = nums[i];
} else {
//std::lower_bound() 的实现
int index = search(res, 0, len, nums[i]);
res[index] = nums[i];
}
}
return len + 1;
}
}
- 时间：O(nlogn)
- 空间：O(n)