- 70. 爬楼梯
- 剑指 Offer 66. 构建乘积数组
- 剑指 Offer 46. 把数字翻译成字符串
- 198. 打家劫舍
- 213. 打家劫舍 II
- 64. 最小路径和
- 62. 不同路径
- 剑指 Offer 47. 礼物的最大价值
- 221. 最大正方形
- 剑指 Offer 14- I. 剪绳子
- 剑指 Offer 14- II. 剪绳子 II
- 303. 区域和检索 - 数组不可变
- 换钱的最小货币数
- 413. 等差数列划分
- 343. 整数拆分
- 279. 完全平方数
- 91. 解码方法
- 300. 最长递增子序列
- 最长递增子序列
- 646. 最长数对链
- 376. 摆动序列
- 152. 乘积最大子数组
- 1143. 最长公共子序列
- 416. 分割等和子集
- 494. 目标和
- 474. 一和零
- 322. 零钱兑换
- 518. 零钱兑换 II
- 139. 单词拆分
- 377. 组合总和 Ⅳ
- 剑指 Offer 60. n个骰子的点数
- 121. 买卖股票的最佳时机
- 122. 买卖股票的最佳时机 II
- 123. 买卖股票的最佳时机 III
- 188. 买卖股票的最佳时机 IV
- 309. 最佳买卖股票时机含冷冻期
- 714. 买卖股票的最佳时机含手续费
- 剑指 Offer 19. 正则表达式匹配
- 583. 两个字符串的删除操作
- 312. 戳气球
- 72. 编辑距离
- 最小编辑代价
- 650. 只有两个键的键盘
- 70. 爬楼梯
- 剑指 Offer 66. 构建乘积数组
- 剑指 Offer 46. 把数字翻译成字符串
- 198. 打家劫舍
- 213. 打家劫舍 II
- 64. 最小路径和
- 62. 不同路径
- 剑指 Offer 47. 礼物的最大价值
- 221. 最大正方形
- 剑指 Offer 14- I. 剪绳子
- 剑指 Offer 14- II. 剪绳子 II
- 303. 区域和检索 - 数组不可变
- 换钱的最小货币数
- 413. 等差数列划分
- 343. 整数拆分
- 279. 完全平方数
- 91. 解码方法
- 300. 最长递增子序列
- 最长递增子序列
- 646. 最长数对链
- 376. 摆动序列
- 152. 乘积最大子数组
- 1143. 最长公共子序列
- 416. 分割等和子集
- 494. 目标和
- 474. 一和零
- 322. 零钱兑换
- 518. 零钱兑换 II
- 139. 单词拆分
- 377. 组合总和 Ⅳ
- 剑指 Offer 60. n个骰子的点数
- 121. 买卖股票的最佳时机
- 122. 买卖股票的最佳时机 II
- 123. 买卖股票的最佳时机 III
- 188. 买卖股票的最佳时机 IV
- 309. 最佳买卖股票时机含冷冻期
- 714. 买卖股票的最佳时机含手续费
- 剑指 Offer 19. 正则表达式匹配
- 583. 两个字符串的删除操作
- 312. 戳气球
- 72. 编辑距离
- 最小编辑代价
- 650. 只有两个键的键盘
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
动态规划
定义一个数组 dp 存储上楼梯的方法数（为了方便讨论，数组下标从 1 开始），dp[i] 表示走到第 i 个楼梯的方法数目。
第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步到达，走到第 i 个楼梯的方法数为走到第 i-1 和第 i-2 个楼梯的方法数之和。
动态转移方程为：
dp[i] = dp[i-1] + dp[i-2]
考虑到 dp[i] 只与 dp[i - 1] 和 dp[i - 2] 有关，因此可以只用两个变量来存储 dp[i - 1] 和 dp[i - 2]，使得原来的 O(N) 空间复杂度优化为 O(1) 复杂度。
class Solution {public int climbStairs(int n) {if (n <= 2) {return n;}int pre1 = 1, pre2 = 2;for (int i = 2; i < n; ++i) {int cur = pre1 + pre2;pre1 = pre2;pre2 = cur;}return pre2;}}
剑指 Offer 66. 构建乘积数组
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
示例:输入: [1,2,3,4,5]输出: [120,60,40,30,24]提示：所有元素乘积之和不会溢出 32 位整数a.length <= 100000
动态规划
根据题目对 B[i] 的定义，可列表格，如下图所示。
根据表格的主对角线（全为 1 ），可将表格分为 上三角 和 下三角 两部分。分别迭代计算下三角和上三角两部分的乘积，即可 不使用除法 就获得结果。
算法流程：
- 初始化：数组 B ，其中 B[0] = 1 ；辅助变量 tmp = 1；
- 计算 B[i] 的 下三角 各元素的乘积，直接乘入 B[i] ；
- 计算 B[i] 的 上三角 各元素的乘积，记为 tmp ，并乘入 B[i] ；
- 返回 B 。
class Solution {
public int[] constructArr(int[] a) {
if (a.length == 0) {
return new int[0];
}
int[] b = new int[a.length];
b[0] = 1;
int tmp = 1;
for (int i = 1; i < a.length; i++) {
b[i] = b[i - 1] * a[i - 1];
}
for (int i = a.length - 2; i >= 0; i--) {
tmp *= a[i + 1];
b[i] *= tmp;
}
return b;
}
}
剑指 Offer 46. 把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
提示：
0 <= num < 231
动态规划
class Solution {
public int translateNum(int num) {
String str = String.valueOf(num);
int first = 1, second = 1;
for (int i = 2; i <= str.length(); i++) {
String tmp = str.substring(i - 2, i);
int cur = tmp.compareTo("10") >=0 && tmp.compareTo("25") <= 0 ? first + second : second;
first = second;
second = cur;
}
return second;
}
}
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
动态规划1
import java.lang.Math;
import java.util.*;
class Solution {
public int rob(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
if (n == 0) {
return 0;
}
if (n == 1) {
return nums[0];
}
if (n == 2) {
return Math.max(nums[1], nums[0]);
}
dp[0] = nums[0];
dp[1] = nums[1];
for (int i = 2; i < n; ++i) {
if (i == 2) {
dp[i] = nums[i] + dp[i - 2];
} else {
dp[i] = nums[i] + Math.max(dp[i-2], dp[i-3]);
}
}
return Math.max(dp[n-1], dp[n-2]);
}
}
动态规划2
class Solution {
public int rob(int[] nums) {
int preMax = 0;
int curMax = 0;
for(int x : nums) {
int temp = curMax;
curMax = Math.max(preMax + x, curMax);
preMax = temp;
}
return curMax;
}
}
213. 打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2:
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
动态规划
跟上一次思路类似，这次只不过多个选择
class Solution {
private int rob(int[] nums, int start, int last) {
int preMax = 0, curMax = 0;
for (int i = start; i <= last; i++) {
int temp = curMax;
curMax = Math.max(preMax + nums[i], curMax);
preMax = temp;
}
return curMax;
}
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
if (n == 1) {
return nums[0];
}
return Math.max(rob(nums, 0, n - 2), rob(nums, 1, n - 1));
}
}
64. 最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
动态规划
这种方法时间复杂度为O(mn),空间复杂度也为O(mn）。还可以不用开辟一个二维数组，直接在原数组上做动态规划，空间复杂度降为O(1)。还有一种方法，空间复杂度为O(n)， dp(j)=grid(i,j)+min(dp(j),dp(j+1))从右下角开始遍历，每次更新dp[j]即可。
class Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int m = grid.length, n = grid[0].length;
if (n == 1) {
return grid[0][0];
}
int[][] result = new int[m][n];
result[0][0] = grid[0][0];
for (int i = 1; i < n; ++i) {
result[0][i] = grid[0][i] + result[0][i-1];
}
for (int i = 1; i < m; ++i) {
result[i][0] = grid[i][0] + result[i-1][0];
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
result[i][j] = Math.min(grid[i][j] + result[i-1][j], grid[i][j] + result[i][j-1]);
}
}
return result[m-1][n-1];
}
}
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明：m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
动态规划
每一个位置只能从左边一格或者上方一格走到，所以动态方程为dp[i][j] = dp[i-1][j] + dp[i][j-1]
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
dp[0][0] = 1;
for (int i = 1; i < n; i++) {
dp[0][i] = 1;
}
for (int i = 1; i < m; i++) {
dp[i][0] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
动态规划优化
因为二维dp数组，可以被一维dp数组代替，之前的数据可以不保存，动态方程优化为dp[i]=dp[i]+d[i-1].
class Solution {
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
dp[j] = dp[j] + dp[j - 1];
}
}
return dp[n - 1];
}
}
剑指 Offer 47. 礼物的最大价值
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
提示：
0 < grid.length <= 200
0 < grid[0].length <= 200
动态规划
class Solution {
public int maxValue(int[][] grid) {
int m = grid.length, n = grid[0].length;
for (int i = 1; i < n; ++i) {
grid[0][i] += grid[0][i - 1];
}
for (int i = 1; i < m; ++i) {
grid[i][0] += grid[i - 1][0];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);
}
}
return grid[m - 1][n - 1];
}
}
221. 最大正方形
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
动态规划
class Solution {
public int maximalSquare(char[][] matrix) {
int maxSide = 0;
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int rows = matrix.length, columns = matrix[0].length;
int[][] dp = new int[rows][columns];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (matrix[i][j] == '1') {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
}
maxSide = Math.max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}
}
剑指 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。
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：
2 <= n <= 58
动态规划
class Solution {
public int cuttingRope(int n) {
int[] dp = new int[n + 1];
dp[1] = dp[2] = 1;
for (int i = 3; i <= n; i++) {
for (int j = 1; j < i; j++) {
dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[i - j] * j));
}
}
return dp[n];
}
}
剑指 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。
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：
2 <= n <= 1000
动态规划
class Solution {
public int cuttingRope(int n) {
if(n <= 3) return n - 1;
int b = n % 3, p = 1000000007;
long rem = 1, x = 3;
for(int a = n / 3 - 1; a > 0; a /= 2) {
if(a % 2 == 1) rem = (rem * x) % p;
x = (x * x) % p;
}
if(b == 0) return (int)(rem * 3 % p);
if(b == 1) return (int)(rem * 4 % p);
return (int)(rem * 6 % p);
}
}
303. 区域和检索 - 数组不可变
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
示例：
给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
说明:
你可以假设数组不可变。
会多次调用 sumRange 方法。
缓存
此题简单，直接看代码。
class NumArray {
private int[] sums;
public NumArray(int[] nums) {
int n = nums.length;
this.sums = new int[n + 1];
for (int i = 1; i <= n; ++i) {
sums[i] = sums[i - 1] + nums[i - 1];
}
}
public int sumRange(int i, int j) {
return sums[j + 1] - sums[i];
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(i,j);
*/
换钱的最小货币数
给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
如果无解，请返回-1.
时间复杂度O_(_n * aim)，空间复杂度O(n)。
示例1
输入
[5,2,3],20
返回值
4
解法
import java.util.*;
public class Solution {
/**
* 最少货币数
* @param arr int整型一维数组 the array
* @param aim int整型 the target
* @return int整型
*/
public int minMoney (int[] arr, int aim) {
// write code here
int[] dp = new int[aim + 1];
Arrays.fill(dp, aim + 1);
dp[0] = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = arr[i]; j <= aim; j++) {
dp[j] = Math.min(dp[j], dp[j - arr[i]] + 1);
}
}
return dp[aim] == aim + 1 ? -1 : dp[aim];
}
}
413. 等差数列划分
如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。
例如，以下数列为等差数列:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。
1, 1, 2, 5, 7
数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。
如果满足以下条件，则称子数组(P, Q)为等差数组：
元素 A[P], A[p + 1], …, A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q 。
函数要返回数组 A 中所有为等差数组的子数组个数。
示例:
A = [1, 2, 3, 4]
返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。
常数内存的动态规划
dp[i] 表示以 A[i] 为结尾的等差递增子区间的个数。
当 A[i] - A[i-1] == A[i-1] - A[i-2]，那么 [A[i-2], A[i-1], A[i]] 构成一个等差递增子区间。而且在以 A[i-1] 为结尾的递增子区间的后面再加上一个 A[i]，一样可以构成新的递增子区间。
dp[2] = 1
[0, 1, 2]
dp[3] = dp[2] + 1 = 2
[0, 1, 2, 3], // [0, 1, 2] 之后加一个 3
[1, 2, 3] // 新的递增子区间
dp[4] = dp[3] + 1 = 3
[0, 1, 2, 3, 4], // [0, 1, 2, 3] 之后加一个 4
[1, 2, 3, 4], // [1, 2, 3] 之后加一个 4
[2, 3, 4] // 新的递增子区间
综上，在 A[i] - A[i-1] == A[i-1] - A[i-2] 时，dp[i] = dp[i-1] + 1。
因为递增子区间不一定以最后一个元素为结尾，可以是任意一个元素结尾，因此需要返回 dp 数组累加的结果。
以前动态规划的标准解法，此题只用记录上次的dp值即可，所以空间复杂度可以将为O(1)
class Solution {
public int numberOfArithmeticSlices(int[] A) {
if (A == null && A.length == 0) {
return 0;
}
int n = A.length;
int temp = 0; //temp保留上次dp值
int total = 0;
for (int i = 2; i < n; ++i) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
temp = temp + 1;
total += temp;
} else { // 中断了，下次置为0
temp = 0;
}
}
return total;
}
}
343. 整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。
动态规划
状态数组dp[i]表示：数字 i 拆分为至少两个正整数之和的最大乘积。为了方便计算，dp 的长度是 n + 1，值初始化为 1。
显然dp[2]等于 1，外层循环从 3 开始遍历，一直到 n 停止。内层循环 j 从 1 开始遍历，一直到 i 之前停止，它代表着数字 i 可以拆分成 j + (i - j)。但 j * (i - j)不一定是最大乘积，因为i-j不一定大于dp[i - j]（数字i-j拆分成整数之和的最大乘积），这里要选择最大的值作为 dp[i] 的结果。
空间复杂度是 O(N)，时间复杂度是 O(N^2)。代码实现如下：
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n + 1];
dp[1] = dp[2] = 1;
for (int i = 3; i <= n; ++i) {
for (int j = 1; j < i; ++j) {
dp[i] = Math.max(dp[i], Math.max(dp[i - j] * j, j * (i - j)));
}
}
return dp[n];
}
}
279. 完全平方数
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
示例 2:
输入: n = 13
输出: 2
解释: 13 = 4 + 9.
BFS
import javafx.util.Pair;
class Solution {
public int numSquares(int n) {
if(n == 0)
return 0;
LinkedList<Pair<Integer, Integer> > queue = new LinkedList<>();
queue.addLast(new Pair<>(n, 0));
boolean[] visited = new boolean[n + 1];
visited[n] = true;
while(!queue.isEmpty()){
Pair<Integer, Integer> front = queue.removeFirst();
int num = front.getKey();
int step = front.getValue();
if(num == 0){
return step;
}
for(int i = 1; num - i * i >= 0; ++i){
int a = num - i * i;
if(!visited[a]){
if(a == 0)
return step + 1;
queue.addLast(new Pair(a, step + 1));
visited[a] = true;
}
}
}
return -1;
}
}
动态规划
标签：动态规划
首先初始化长度为n+1的数组dp，每个位置都为0
如果n为0，则结果为0
对数组进行遍历，下标为i，每次都将当前数字先更新为最大的结果，即dp[i]=i，比如i=4，最坏结果为4=1+1+1+1即为4个数字
动态转移方程为：dp[i] = MIN(dp[i], dp[i - j * j] + 1)，i表示当前数字，jj表示平方数
时间复杂度：O(nsqrt(n))，sqrt为平方根
class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
for (int i = 1; i <= n; ++i) {
dp[i] = i;
for (int j = 1; i - j * j>= 0; ++j) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
}
91. 解码方法
一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2:
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
动态规划
class Solution {
public int numDecodings(String s) {
if (s == null && s.length() == 0) {
return 0;
}
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = s.charAt(0) == '0' ? 0 : 1;
for (int i = 2; i <= n; ++i) {
int index1 = Integer.valueOf(s.substring(i - 1, i));
if (index1 != 0) {
dp[i] += dp[i - 1];
}
if (s.charAt(i - 2) == '0') {
continue;
}
int index2 = Integer.valueOf(s.substring(i - 2, i));
if (index2 <= 26) {
dp[i] += dp[i - 2];
}
}
return dp[n];
}
}
300. 最长递增子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
动态规划
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
if (nums == null || n == 0) {
return 0;
}
int[] dp = new int[n];
for (int i = 0; i < n; ++i) {
int count = 1;
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
count = Math.max(count, dp[j] + 1);
}
}
dp[i] = count;
}
int maxLength = 0;
for (int i = 0; i < n; ++i) {
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength;
}
}
二分查找
以上解法的时间复杂度为 O(N2)，可以使用二分查找将时间复杂度降低为 O(NlogN)。
定义一个 tails 数组，其中 tails[i] 存储长度为 i + 1 的最长递增子序列的最后一个元素。对于一个元素 x，
如果它大于 tails 数组所有的值，那么把它添加到 tails 后面，表示最长递增子序列长度加 1；
如果 tails[i-1] < x <= tails[i]，那么更新 tails[i] = x。
例如对于数组 [4,3,6,5]，有：
tails len num
[] 0 4
[4] 1 3
[3] 1 6
[3,6] 2 5
[3,5] 2 null
可以看出 tails 数组保持有序，因此在查找 Si 位于 tails 数组的位置时就可以使用二分查找。
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
if (nums == null || n == 0) {
return 0;
}
int[] tails = new int[n];
int maxLength = 0;
for (int num : nums) {
int index = binarySearch(tails, maxLength, num);
tails[index] = num;
if (index == maxLength) {
maxLength++;
}
}
return maxLength;
}
private int binarySearch(int[] tails, int len, int key) {
int left = 0, right = len;
while (left < right) {
int mid = left + (right - left) / 2;
if (tails[mid] == key) {
return mid;
} else if (tails[mid] > key) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
最长递增子序列
给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）
解法
import java.util.*;
public class Solution {
/**
* retrun the longest increasing subsequence
* @param arr int整型一维数组 the array
* @return int整型一维数组
*/
public int[] LIS (int[] arr) {
// write code here
int n = arr.length;
if (arr == null || n == 0) {
return new int[0];
}
// nums中存储的是最长递增子序列的个数，其索引就是arr中对应元素的位置
int[] nums = new int[n];
// temp中存储的是最长递增子序列
int[] temp = new int[n];
nums[0] = 1;
int tempIndex = 0;
temp[tempIndex] = arr[0];
for (int i = 1; i < arr.length; i++) {
int left = 0, right = tempIndex;
// 如果arr[i] > temp[tempIndex],直接将arr[i]插入到temp尾部
if (arr[i] > temp[tempIndex]) {
++tempIndex;
nums[i] = tempIndex + 1;
temp[tempIndex] = arr[i];
} else {
// 二分查找，找到arr[i]插入的位置
while (left <= right) {
int mid = right + ((left - right) >> 1);
if (temp[mid] > arr[i]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
temp[left] = arr[i];
nums[i] = left + 1;
}
}
int[] res = new int[tempIndex + 1];
for (int i = nums.length - 1; i >= 0; i--) {
if (nums[i] == tempIndex + 1) {
res[tempIndex--] = arr[i];
}
}
return res;
}
}
646. 最长数对链
给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。
现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。
给定一个对数集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。
示例 :
输入: [[1,2], [2,3], [3,4]]
输出: 2
解释: 最长的数对链是 [1,2] -> [3,4]
注意：
给出数对的个数在 [1, 1000] 范围内。
动态规划
class Solution {
public int findLongestChain(int[][] pairs) {
if (pairs == null || pairs.length == 0 || pairs[0].length == 0) {
return 0;
}
Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
int n = pairs.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (pairs[j][1] < pairs[i][0]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
int max = 0;
for (int i : dp) {
max = Math.max(i, max);
}
return max;
}
}
376. 摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
示例 1:
输入: [1,7,4,9,2,5]
输出: 6
解释: 整个序列均为摆动序列。
示例 2:
输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
示例 3:
输入: [1,2,3,4,5,6,7,8,9]
输出: 2
动态规划
class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
int up = 1, down = 1;
for (int i = 1; i < n; ++i) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
} else if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return Math.max(up, down);
}
}
152. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
动态规划
考虑负负得正的情况。
class Solution {
public int maxProduct(int[] nums) {
int size = nums.length;
if (size == 0) {
return 0;
}
if (size == 1) {
return nums[0];
}
int ans = nums[0];
int maxValue = nums[0];
int minValue = nums[0];
for (int i = 1; i < size; i++) {
int max = maxValue, min = minValue;
maxValue = Math.max(max * nums[i], Math.max(min * nums[i], nums[i]));
minValue = Math.min(max * nums[i], Math.min(min * nums[i], nums[i]));
ans = Math.max(maxValue, ans);
}
return ans;
}
}
1143. 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 1:
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。
示例 2:
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。
示例 3:
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。
提示:
1 <= text1.length <= 1000
1 <= text2.length <= 1000
输入的字符串只含有小写英文字符。
动态规划
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
if (m == 0 || n == 0) {
return 0;
}
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[m][n];
}
}
416. 分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
动态规划
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
int n = nums.length;
for (int num : nums) {
sum += num;
}
if (sum % 2 == 1) {
return false;
}
int target = sum / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums) {
for (int i = target; i >= num; i--) {
if (dp[target] == true) {
return true;
}
dp[i] = dp[i] || dp[i - num];
}
}
return dp[target];
}
}
494. 目标和
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例 1:
输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。
注意:
数组非空，且长度不会超过20。
初始的数组的和不会超过1000。
保证返回的最终结果能被32位整数存下。
动态规划
class Solution {
public int findTargetSumWays(int[] nums, int S) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum < S || (sum + S) % 2 == 1) {
return 0;
}
int target = (sum + S) / 2;
int[] dp = new int[target + 1];
dp[0] = 1;
for (int num : nums) {
for (int i = target; i >= num; i--) {
dp[i] = dp[i] + dp[i - num];
}
}
return dp[target];
}
}
474. 一和零
在计算机界中，我们总是追求用有限的资源获取最大的收益。
现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。
你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。
注意:
给定 0 和 1 的数量都不会超过 100。
给定字符串数组的长度不会超过 600。
示例 1:
输入: Array = {“10”, “0001”, “111001”, “1”, “0”}, m = 5, n = 3
输出: 4
解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 “10”,”0001”,”1”,”0” 。
示例 2:
输入: Array = {“10”, “0”, “1”}, m = 1, n = 1
输出: 2
解释: 你可以拼出 “10”，但之后就没有剩余数字了。更好的选择是拼出 “0” 和 “1” 。
动态规划
这是一个多维费用的 0-1 背包问题，有两个背包大小，0 的数量和 1 的数量。
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
if (strs == null || strs.length == 0) {
return 0;
}
int[][] dp = new int[m + 1][n + 1];
for (String s : strs) {
int ones = 0, zeros = 0;
for (char c : s.toCharArray()) {
if (c == '0') {
zeros++;
} else {
ones++;
}
}
for (int i = m; i >= zeros; i--) {
for (int j = n; j >= ones; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
}
}
}
return dp[m][n];
}
}
322. 零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。
动态规划
因为硬币可以重复使用，因此这是一个完全背包问题。完全背包只需要将 0-1 背包的逆序遍历 dp 数组改为正序遍历即可。
class Solution {
public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0) {
return -1;
}
if (amount == 0) {
return 0;
}
int[] dp = new int[amount + 1];
int coinMin = 0;
for (int coin : coins) {
for (int i = coin; i <= amount; ++i) {
if (i == coin) {
dp[i] = 1;
} else if (dp[i] == 0 && dp[i - coin] != 0) {
dp[i] = dp[i - coin] + 1;
} else if (dp[i - coin] != 0) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
if (coin < coinMin) {
coinMin = coin;
}
}
if (coinMin > amount) {
return -1;
}
return dp[amount] == 0 ? -1 : dp[amount];
}
}
518. 零钱兑换 II
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
输入: amount = 10, coins = [10]
输出: 1
注意:
你可以假设：
0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数
动态规划
完全背包问题，使用 dp 记录可达成目标的组合数目。
class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) { //将逆序遍历改为正序遍历
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
}
139. 单词拆分
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：
输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。
示例 2：
输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。
注意你可以重复使用字典中的单词。
示例 3：
输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false
动态规划
dict 中的单词没有使用次数的限制，因此这是一个完全背包问题。
该问题涉及到字典中单词的使用顺序，也就是说物品必须按一定顺序放入背包中，例如下面的 dict 就不够组成字符串 “leetcode”：
["lee", "tc", "cod"]
求解顺序的完全背包问题时，对物品的迭代应该放在最里层，对背包的迭代放在外层，只有这样才能让物品按一定顺序放入背包中。
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 0; i <= n; i++) {
for (String word : wordDict) {
int len = word.length();
if (len <= i && word.equals(s.substring(i - len, i))) {
dp[i] = dp[i] || dp[i - len];
}
}
}
return dp[n];
}
}
377. 组合总和 Ⅳ
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例:
nums = [1, 2, 3]
target = 4
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。
进阶：
如果给定的数组中含有负数会怎么样？
问题会产生什么变化？
我们需要在题目中添加什么限制来允许负数的出现？
动态规划
有顺序限制的完全背包。
class Solution {
public int combinationSum4(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[target + 1];
dp[0] = 1;
Arrays.sort(nums);
int n = nums.length;
for (int i = 1; i <= target; ++i) {
for (int j = 0; j < n && nums[j] <= i; ++j) {
dp[i] += dp[i - nums[j]];
}
}
return dp[target];
}
}
剑指 Offer 60. n个骰子的点数
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
示例 1:
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2:
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
限制：
1 <= n <= 11
动态规划
我们可以把n个骰子的点数分解为n-1个骰子的点数加上一个骰子的点数。
根据1个骰子的点数概率数组求出2的点数概率数组，根据2的点数概率数组求出3的点数概率数组….直到求出n的点数。
class Solution {
public double[] twoSum(int n) {
double[] pre = {1/6d, 1/6d, 1/6d, 1/6d, 1/6d, 1/6d};
for (int i = 2; i <= n; i++) {
// n个骰子的点数和范围为[n,6n]，所以共有6n-n+1=5n+1个值
double[] tmp = new double[5 * i + 1];
for (int j = 0; j < pre.length; j++) {
// pre[j] 乘上每一面的概率
for (int k = 0; k < 6; k++) {
tmp[j + k] += pre[j] / 6;
}
}
pre = tmp;
}
return pre;
}
}
121. 买卖股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
直接遍历
class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int maxProfit = 0;
int minPrice = prices[0];
for (int price : prices) {
if (minPrice > price) {
minPrice = price;
} else {
maxProfit = Math.max(maxProfit, price - minPrice);
}
}
return maxProfit;
}
}
122. 买卖股票的最佳时机 II
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
贪心
class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
maxProfit += Math.max(0, prices[i] - prices[i - 1]);
}
return maxProfit;
}
}
123. 买卖股票的最佳时机 III
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。
动态规划
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int firstBuy = Integer.MIN_VALUE, firstSell = 0;
int secondBuy = Integer.MIN_VALUE, secondSell = 0;
for (int price : prices) {
if (firstBuy < -price) {
firstBuy = -price;
}
firstSell = Math.max(firstSell, price + firstBuy);
if (secondBuy < firstSell - price) {
secondBuy = firstSell - price;
}
secondSell = Math.max(secondSell, secondBuy + price);
}
return secondSell;
}
}
188. 买卖股票的最佳时机 IV
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2:
输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
动态规划
class Solution {
public int maxProfit(int k, int[] prices) {
int m = prices.length;
// 假如一直买卖，最多能进行m/2次交易，上限为k，两者取较小值能得到最多的交易次数
k = Math.min(k, m / 2);
// 交易次数为0就无需计算，定然为0
if (k == 0) {
return 0;
}
int[] seller = new int[k];
int[] buyer = new int[k];
Arrays.fill(buyer, -prices[0]);
for (int i = 1; i < m; i++) {
for (int j = 0; j < k; j++) {
// 或者不交易，或者把当前持有股票卖出
seller[j] = Math.max(seller[j], prices[i] + buyer[j]);
// 或者不交易，或者按照当前价格买入
buyer[j] = Math.max(buyer[j], (j == 0 ? 0 : seller[j - 1]) - prices[i]);
}
}
return seller[k - 1];
}
}
309. 最佳买卖股票时机含冷冻期
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
动态规划
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int[] dp = new int[3];
// dp[0] 表示第i天没有持有股票，不处于冷冻期中;dp[1]表示第i天持有股票;dp[2]表示第i天没有持有股票，并且处于冷冻期中
dp[1] = Integer.MIN_VALUE;
int n = prices.length;
for (int i = 0; i < n; i++){
int temp = dp[2];
dp[2] = Math.max(dp[2], dp[1] + prices[i]);
dp[1] = Math.max(dp[1], dp[0] - prices[i]);
dp[0] = temp;
}
return dp[2];
}
}
714. 买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每次交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
示例 1:
输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8
解释: 能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
注意:
0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.
动态规划
class Solution {
public int maxProfit(int[] prices, int fee) {
if (prices == null || prices.length == 0) {
return 0;
}
int[] dp = new int[3]; // dp[0]表示第i天没有持有股票，dp[1]表示第i天持有股票
dp[1] = Integer.MIN_VALUE;
int n = prices.length;
for (int i = 0; i < n; ++i) {
int temp = dp[0]; // 记录下第i-1天没有持有股票，手里的收益。
dp[0] = Math.max(dp[0], dp[1] + prices[i]); // 计算第i天没有持有股票，手里的收益。
dp[1] = Math.max(dp[1], temp - prices[i] - fee); // 计算第i天持有股票，手里的收益,每次买入减去手续费即可。
}
return dp[0];
}
}
剑指 Offer 19. 正则表达式匹配
请实现一个函数用来匹配包含’. ‘和’_’的正则表达式。模式中的字符’.’表示任意一个字符，而’*’表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab_ac_a”匹配，但与”aa.a”和”ab_a”均不匹配。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。
解法
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
boolean[][] f = new boolean[m + 1][n + 1];
f[0][0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p.charAt(j - 1) == '*') {
f[i][j] = f[i][j - 2];
if (matches(s, p, i, j - 1)) {
f[i][j] = f[i][j] || f[i - 1][j];
}
} else {
if (matches(s, p, i, j)) {
f[i][j] = f[i - 1][j - 1];
}
}
}
}
return f[m][n];
}
private boolean matches(String s, String p, int i, int j) {
if (i == 0) {
return false;
}
if (p.charAt(j - 1) == '.') {
return true;
}
return s.charAt(i - 1) == p.charAt(j - 1);
}
}
583. 两个字符串的删除操作
给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
示例：
输入: “sea”, “eat”
输出: 2
解释: 第一步将”sea”变为”ea”，第二步将”eat”变为”ea”
提示：
给定单词的长度不超过500。
给定单词中的字符只含有小写字母。
动态规划
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return m + n - 2 * dp[m][n];
}
}
312. 戳气球
有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。
求所能获得硬币的最大数量。
说明:
你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实存在的所以并不能被戳破。
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
示例:
输入: [3,1,5,8]
输出: 167
解释: nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
动态规划
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
int[][] res = new int[n + 2][n + 2];
int[] val = new int[n + 2];
val[0] = val[n + 1] = 1;
for (int i = 1; i <= n; i++) {
val[i] = nums[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j <= n + 1; j++) {
for (int k = i + 1; k < j; k++) {
int sum = val[i] * val[k] * val[j];
sum += res[i][k] + res[k][j];
res[i][j] = Math.max(res[i][j], sum);
}
}
}
return res[0][n + 1];
}
}
72. 编辑距离
给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1:
输入: word1 = “horse”, word2 = “ros”
输出: 3
解释:
horse -> rorse (将 ‘h’ 替换为 ‘r’)
rorse -> rose (删除 ‘r’)
rose -> ros (删除 ‘e’)
示例 2:
输入: word1 = “intention”, word2 = “execution”
输出: 5
解释:
intention -> inention (删除 ‘t’)
inention -> enention (将 ‘i’ 替换为 ‘e’)
enention -> exention (将 ‘n’ 替换为 ‘x’)
exention -> exection (将 ‘n’ 替换为 ‘c’)
exection -> execution (插入 ‘u’)
动态规划
class Solution {
public int minDistance(String word1, String word2) {
if (word1 == null || word2 == null) {
return 0;
}
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
dp[i][0] = i;
}
for (int i = 1; i <= n; ++i) {
dp[0][i] = i;
}
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
}
}
}
return dp[m][n];
}
}
最小编辑代价
给定两个字符串str1和str2，再给定三个整数ic，dc和rc，分别代表插入、删除和替换一个字符的代价，请输出将str1编辑成str2的最小代价。
示例1
输入
"abc","adc",5,3,2
返回值
2
动态规划
import java.util.*;
public class Solution {
/**
* min edit cost
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @param ic int整型 insert cost
* @param dc int整型 delete cost
* @param rc int整型 replace cost
* @return int整型
*/
public int minEditCost (String str1, String str2, int ic, int dc, int rc) {
// write code here
// ic 插入 dc 删除 rc 替换
int m = str1.length();
int n = str2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
dp[i][0] = i * dc;
}
for (int i = 1; i <= n; i++) {
dp[0][i] = i * ic;
}
for (int i = 1; i <= m; i++) {
char c1 = str1.charAt(i - 1);
for (int j = 1; j <= n; j++) {
char c2 = str2.charAt(j - 1);
if (c1 == c2) {
dp[i][j] = dp[i - 1][j - 1];
} else {
int insert = dp[i][j - 1] + ic;
int delete = dp[i - 1][j] + dc;
int replace = dp[i - 1][j - 1] + rc;
dp[i][j] = Math.min(replace, Math.min(insert, delete));
}
}
}
return dp[m][n];
}
}
650. 只有两个键的键盘
最初在一个记事本上只有一个字符 ‘A’。你每次可以对这个记事本进行两种操作：
Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。
Paste (粘贴) : 你可以粘贴你上一次复制的字符。
给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 ‘A’。输出能够打印出 n 个 ‘A’ 的最少操作次数。
示例 1:
输入: 3
输出: 3
解释:
最初, 我们只有一个字符 ‘A’。
第 1 步, 我们使用 Copy All 操作。
第 2 步, 我们使用 Paste 操作来获得 ‘AA’。
第 3 步, 我们使用 Paste 操作来获得 ‘AAA’。
说明:
n 的取值范围是 [1, 1000] 。
递归
class Solution {
public int minSteps(int n) {
if (n == 1) {
return 0;
}
int h = (int) Math.sqrt(n);
for (int i = 2; i <= h; ++i) {
if (n % i == 0) {
return i + minSteps(n / i);
}
}
return n;
}
}
动态规划
i/j不等于dp[i/j]，这是动态规划，举个例子，n=20，最小操作数是9，最大因子是10，dp[10]是不等于10的，等于7。dp[20] = dp[2] + 1 + dp[20/2] - 1，dp[10] = dp[2] + 1 + dp[10/2] - 1; dp[5] = 5。一句话就是如果n的最大因子是合数，那么就是dp[i/j]，如果n的最大因子是质数就是dp[i/j]= i/j，但是显然n的最大因子是合数还是质数是不确定的，所以直接使用dp[i/j]。
class Solution {
public int minSteps(int n) {
int[] dp = new int[n + 1];
int h = (int) Math.sqrt(n);
for (int i = 2; i <= n; ++i) {
dp[i] = i;
for (int j = 2; j <= h; ++j) {
if (i % j == 0) {
dp[i] = dp[j] + dp[i / j];
break;
}
}
}
return dp[n];
}
}
若有收获，就点个赞吧
0 人点赞
