62. 圆圈中最后剩下的数字
0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例 1：
输入: n = 5, m = 3
输出: 3
示例 2：
输入: n = 10, m = 17
输出: 2
// 思路是进行模拟，但不是走一遍，而是从当前位置+n 取模，注意，从0开始，每次加m-1
public int lastRemaining(int n, int m) {
if(n <= 1){
return 0;
}
List<Integer> list = new ArrayList<>();
for(int i=0;i<n;i++){
list.add(i);
}
int index = 0;
while(list.size()>1){
index = (index + (m-1)) % list.size();
list.remove(index);
}
return list.get(0);
}
15. 二进制中1的个数
请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
// 思路：num & (num - 1) 消去一个1 ，统计消去的次数
public int hammingWeight(int n) {
int count = 0;
while(n != 0){
n = n & (n-1);
count++;
}
return count;
}
44. 数字序列中某一位的数字
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第n位对应的数字。
示例 1：
输入：n = 3
输出：3
示例 2：
输入：n = 11
输出：0
注意这里必须是long 类型
// 思路是：0 ~ 9 9
// 10 ~ 99 90
// 100 999 900
// 先找到那个数，然后转str,通过余数取到对应位
public int findNthDigit(int n) {
// 1 10 100 基数
int start = 1;
// 位数
int digit = 1;
// 当前的数
int count = 9;
// 开始从10 不会出现问题
while (n > count){
n -= count;
start *= 10;
digit += 1;
count = 9 * start * digit;
}
// 确定是哪一个数
long num = start + (n-1) / digit;
return Long.toString(num).charAt((n-1)%digit) - '0';
}
45. 把数组排成最小的数
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: "102"
示例 2:
输入: [3,30,34,5,9]
输出: "3033459"
public String minNumber(int[] nums) {
if (nums.length == 1){
return String.valueOf(nums[0]);
}
String[] numstr = new String[nums.length];
for (int i =0;i<nums.length;i++){
numstr[i] = String.valueOf(nums[i]);
}
Arrays.sort(numstr, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
String a = o1 + o2;
String b = o2 + o1;
return a.compareTo(b);
}
});
StringBuilder sb = new StringBuilder();
for (String s: numstr){
sb.append(s);
}
return sb.toString();
}
135. 分发糖果
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？
示例 1:
输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2:
输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
// 思路是两次遍历
public int candy(int[] ratings) {
if(ratings == null || ratings.length == 0){
return 0;
}
int[] candys = new int[ratings.length];
Arrays.fill(candys,1);
for(int i=1;i < candys.length;i++){
if(ratings[i] > ratings[i-1]){
candys[i] = candys[i-1] + 1;
}
}
// 注意第二次遍历的时候如果已经满足条件就不增加数量
for(int i=candys.length-2;i>=0;i--){
if(ratings[i] > ratings[i+1]){
if(candys[i] <= candys[i+1]){
candys[i] = candys[i+1] + 1;
}
}
}
int total = 0;
for(int i=0;i<candys.length;i++){
total += candys[i];
}
return total;
}
134. 加油站
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
说明:
如果题目有解，该答案即为唯一答案。
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。
示例 1:
输入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
输出: 3
// 思路是从正数出发，然后进行模拟
public int canCompleteCircuit(int[] gas, int[] cost) {
int[] diff = new int[gas.length];
for(int i=0;i<gas.length;i++){
diff[i] = gas[i] - cost[i];
}
for(int i=0;i<gas.length;i++){
if(diff[i] >= 0){
int total = diff[i];
boolean flag = false;
for(int j=1;j<gas.length;j++){
total += diff[(j+i) % gas.length];
if(total < 0){
flag = true;
break;
}
}
if(!flag){
return i;
}
}
}
return -1;
}
贪心的思路是，只要总和大于0 就可以绕一圈，
开始位置的贪心思路是，如果从刚开始sum小于0，一定不是从之前开始，而是从当前下一个位置，sum = 0 清空
// 思路是从正数出发，然后进行模拟
public int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0;
int sum = 0;
int start = 0;
for(int i=0;i<gas.length;i++){
total += gas[i] - cost[i];
sum += gas[i] - cost[i];
if(sum < 0){
start = i + 1;
sum = 0;
}
}
return total >=0 ? start : -1;
}
45. 跳跃游戏2
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
// 思路是统计当前范围的最大值，基数
public int jump(int[] nums) {
if(nums == null || nums.length < 2){
return 0;
}
int max = 0;
int maxPosition = 0;
int step = 0;
for(int i = 0;i< nums.length;i++){
max = Math.max(max,nums[i] + i);
if(i == nums.length - 1){
break;
}
if(i == maxPosition){
maxPosition = max;
step ++;
max = 0;
}
}
return step;
}
55. 跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
public boolean canJump(int[] nums) {
int maxPosition = 0;
int max = 0;
int cur = 0;
while(cur <= maxPosition && cur < nums.length){
max = Math.max(nums[cur]+cur,max);
if(cur == maxPosition){
maxPosition = max;
max = 0;
}
cur++;
}
return cur == nums.length;
}
91. 解码方法
一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
这里一定注意 第一个数为0 的情况，s.charAt(0) == '0' 第一个为0 要直接返回0 才行
// 直接使用动态规划
// 如果 最后两个数小于27 ，可以 拆分为两个
public int numDecodings(String s) {
int len = s.length();
if (len == 0 || s.charAt(0) == '0') return 0;
// 转int
int[] nums = new int[s.length()];
for(int i=0;i<s.length();i++){
nums[i] = s.charAt(i) - '0';
}
int[] dp = new int[len + 1];
dp[0] = 1;
dp[1] = 1;
for(int i=2;i<=len;i++){
int x = nums[i-2] * 10 + nums[i-1];
if(x < 27 && x > 9){
dp[i] += dp[i-2];
}
if(nums[i-1] != 0){
dp[i] += dp[i-1];
}
}
return dp[len];
}
121. 买股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
// 状态机， 1 当前位的最大卖出价， 0 当前为最小买入价
public int maxProfit(int[] prices) {
if(prices == null || prices.length == 0){
return 0;
}
int[][] dp = new int[prices.length][2];
dp[0][1] = 0;
dp[0][0] = -prices[0];
int total = 0;
for(int i=1;i<prices.length;i++){
dp[i][1] = Math.max(dp[i-1][0] + prices[i], dp[i-1][1]);
dp[i][0] = Math.max(dp[i-1][0] , -prices[i]);
total = Math.max(total, dp[i][1]);
}
return total;
}
// 状态机， 1 当前位的最大卖出价， 0 当前为最小买入价
// 因为只和前一个状态相关所以，可以不使用数组
public int maxProfit(int[] prices) {
if(prices == null || prices.length == 0){
return 0;
}
int dp_i_1 = 0;
int dp_i_0 = -prices[0];
int total = 0;
for(int i=1;i<prices.length;i++){
dp_i_1 = Math.max(dp_i_0 + prices[i], dp_i_1);
dp_i_0 = Math.max(dp_i_0 , -prices[i]);
total = Math.max(total, dp_i_1);
}
return total;
}
97. 交错字符串
给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1:
输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
public boolean isInterleave(String s1, String s2, String s3) {
// 使用 dp[m][n] 前s1 的m , s2 的 n 组成s3
int m = s1.length();
int n = s2.length();
int len = s3.length();
if(m + n != len){
return false;
}
// 使用动态规划，可以在同一个位置尝试两种可能，只要一种完成即可
int[][] dp = new int[m + 1][n + 1];
dp[0][0] = 1;
for(int i=1;i<=m;i++){
if(dp[i-1][0] == 1 && s1.charAt(i-1) == s3.charAt(i-1)){
dp[i][0] = 1;
}
}
for(int i=1;i<=n;i++){
if(dp[0][i-1] == 1 && s2.charAt(i-1) == s3.charAt(i-1)){
dp[0][i] = 1;
}
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(dp[i][j-1] == 1 && s2.charAt(j-1) == s3.charAt(j+i-1) ||
dp[i-1][j] == 1 && s1.charAt(i-1) == s3.charAt(j+i-1)){
dp[i][j] = 1;
}
}
}
return dp[m][n] == 1;
}
10. 正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
public boolean isMatch(String s, String p) {
int lens = s.length();
int lenp = p.length();
if(lenp == 0){
return lens == 0;
}
// 避免 “” 串
boolean firstMatch = lens > 0 && (s.charAt(0) == p.charAt(0)|| p.charAt(0) == '.');
// 有两个字符的可以进行检测*
if(lenp > 1 && p.charAt(1) == '*'){
// 匹配零个或者多个
// 匹配多个 第一个firstMatch匹配，看下一个substring(1)是否匹配，已经直接跳过*
return (firstMatch && isMatch(s.substring(1),p)) || isMatch(s,p.substring(2));
}
return firstMatch && isMatch(s.substring(1),p.substring(1));
}
// 改为动态规划
public boolean isMatch(String s, String p) {
int lens = s.length();
int lenp = p.length();
boolean[][] dp = new boolean[lens + 1][lenp + 1];
dp[lens][lenp] = true;
for(int i=lens;i>=0;i--){
for(int j=lenp-1;j>=0;j--){
boolean match = i < lens &&
(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
if(j+1 < lenp && p.charAt(j+1) == '*'){
dp[i][j] = dp[i][j+2] || (match && dp[i+1][j]);
}else{
dp[i][j] = match && dp[i+1][j+1];
}
}
}
return dp[0][0];
}
329. 矩阵中的最长的递增路径
给定一个整数矩阵，找出最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
示例 1:
输入: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
输出: 4
解释: 最长递增路径为 [1, 2, 6, 9]。
使用带记忆的可以避免超时
int[][] next = {{0,1},{0,-1},{1,0},{-1,0}};
int m,n;
int[][] matrix;
public int longestIncreasingPath(int[][] matrix) {
// 这里不需要vis 的原因，是下次访问的位置值必须大于当前值
if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
return 0;
}
this.matrix = matrix;
m = matrix.length;
n = matrix[0].length;
int[][] cache = new int[m][n];
int longestLen = 0;
for (int i=0;i<m;i++){
for (int j=0;j<n;j++){
longestLen = Math.max(longestLen, dfs(i,j,cache));
}
}
return longestLen;
}
private int dfs(int x, int y,int[][] cache) {
if (cache[x][y] != 0) return cache[x][y];
for (int i=0;i<next.length;i++){
int xx = x + next[i][0];
int yy = y + next[i][1];
if (xx >=0 && xx < m && yy >= 0 && yy < n && matrix[x][y] < matrix[xx][yy]){
cache[x][y] = Math.max(dfs(xx,yy,cache),cache[x][y]);
}
}
return ++cache[x][y];
}
使用动态规划解题
public int longestIncreasingPath(int[][] matrix) {
// 这里不需要vis 的原因，是下次访问的位置值必须大于当前值
if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
return 0;
}
PriorityQueue<int[]> minHeap = new PriorityQueue<>((pre,next)-> pre[0] - next[0]);
for (int i=0;i<matrix.length;i++){
for(int j=0;j<matrix[0].length;j++) {
minHeap.offer(new int[]{matrix[i][j],i,j});
}
}
int[][] dp = new int[matrix.length][matrix[0].length];
int maxLen = 0;
while (!minHeap.isEmpty()){
int[] cur = minHeap.poll();
int value = cur[0];
int x = cur[1];
int y = cur[2];
int curMax = 1;
if(x > 0 && value > matrix[x-1][y]){
curMax = Math.max(curMax,dp[x-1][y] + 1);
}
if (y > 0 && value > matrix[x][y-1]){
curMax = Math.max(curMax,dp[x][y-1] + 1);
}
if (x < matrix.length-1 && value > matrix[x+1][y]){
curMax = Math.max(curMax,dp[x+1][y] + 1);
}
if (y < matrix[0].length-1 && value > matrix[x][y+1]){
curMax = Math.max(curMax,dp[x][y+1] + 1);
}
dp[x][y] = curMax;
maxLen = Math.max(curMax,maxLen);
}
return maxLen;
}
368. 最大整除子集
给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。
如果有多个目标子集，返回其中任何一个均可。
示例 1:
输入: [1,2,3]
输出: [1,2] (当然, [1,3] 也正确)
public List<Integer> largestDivisibleSubset(int[] nums) {
if(nums == null || nums.length == 0){
return new ArrayList<>();
}
// 找到这个数
Arrays.sort(nums);
List<List<Integer>> list = new ArrayList<>();
List<Integer> res = new ArrayList<>();
for(int i=0;i<nums.length;i++){
List<Integer> curList = new ArrayList<>();
int j = i - 1;
while(j >= 0){
if(nums[i] % nums[j] == 0 && list.get(j).size() > curList.size()) {
curList = list.get(j);
}
j--;
}
// 添加list 时要 new ArrayList 避免 添加的只是一个引用
list.add(new ArrayList<>(curList));
// 在新建对象添加值，而不是在引用中添加值
list.get(i).add(nums[i]);
if(res.size() < list.get(i).size()){
res = list.get(i);
}
}
return res;
}
354. 俄罗斯套娃
给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
说明:
不允许旋转信封。
示例:
输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
标准的动态规划
// dp[i] = for(max dp[i]) + 1
public int maxEnvelopes(int[][] envelopes) {
if(envelopes == null || envelopes.length == 0 || envelopes[0].length == 0){
return 0;
}
int[] dp = new int[envelopes.length];
dp[0] = 1;
Arrays.sort(envelopes, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[0] == o2[0]){
return o1[1] - o2[1];
}
return o1[0] - o2[0];
}
});
int max = 1;
for(int i=1;i<dp.length;i++){
int curMax = 0;
for (int j=i-1;j>=0;j--){
if(envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]){
curMax = Math.max(curMax,dp[j]);
}
}
dp[i] = curMax + 1;
max = Math.max(max, dp[i]);
}
return max;
}
403. 青蛙过河
一只青蛙想要过河。 假定河流被等分为 x 个单元格，并且在每一个单元格内都有可能放有一石子（也有可能没有）。 青蛙可以跳上石头，但是不可以跳入水中。
给定石子的位置列表（用单元格序号升序表示）， 请判定青蛙能否成功过河（即能否在最后一步跳至最后一个石子上）。 开始时， 青蛙默认已站在第一个石子上，并可以假定它第一步只能跳跃一个单位（即只能从单元格1跳至单元格2）。
如果青蛙上一步跳跃了 k 个单位，那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。
请注意：
石子的数量 ≥ 2 且 < 1100；
每一个石子的位置序号都是一个非负整数，且其 < 231；
第一个石子的位置永远是0。
示例 1:
[0,1,3,5,6,8,12,17]
true
使用数组+ 链表枚举所有的可能
public boolean canCross(int[] stones) {
HashMap<Integer, Set<Integer>> map = new HashMap<>();
for(int i=0;i < stones.length;i++){
map.put(stones[i],new HashSet<Integer>());
}
map.get(0).add(0);
for (int i=0; i< stones.length;i++){
for(int k : map.get(stones[i])){
for(int step = k-1;step<=k+1;step++){
if (step > 0 && map.containsKey(stones[i] + step)){
map.get(stones[i] + step).add(step);
}
}
}
}
return map.get(stones[stones.length-1]).size() > 0;
}
72. 编辑距离
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
// 编辑距离， dp[i-1][j-1],dp[i-1][j],dp[i][j-1] 中最小的加1
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
int[][] dp = new int[len1+1][len2+1];
for(int i=1;i<=len2;i++){
dp[0][i] = i;
}
for(int i=1;i<=len1;i++){
dp[i][0] = i;
}
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;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-1][j],dp[i][j-1])) + 1;
}
}
}
return dp[len1][len2];
}
322. 零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1
// dp[i] = dp[i-coins[i]]
public int coinChange(int[] coins, int amount) {
Arrays.sort(coins);
int[] dp = new int[amount+1];
dp[0] = 0;
for(int i=1;i<amount+1;i++){
int curMin = amount+1;
for(int j=0;j<coins.length && coins[j] <= i;j++){
curMin = Math.min(dp[i-coins[j]],curMin);
}
dp[i] = curMin + 1;
}
return dp[amount] > amount ? -1 : dp[amount];
}
5. 最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
public String longestPalindrome(String s) {
if(s == null || s.length() < 2){
return s;
}
int k = 0;
int maxLen = 0;
for(int i=0;i<s.length()-1;i++){
int len1 = expendString(s,i,i);
int len2 = expendString(s,i,i+1);
int len = Math.max(len1,len2);
if(len > maxLen){
k = i;
maxLen = len;
}
}
int left = k - (maxLen-1) / 2;
int right = k + maxLen / 2;
return s.substring(left,right+1);
}
// 从中心进行扩展
public int expendString(String s,int l, int r){
while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
l--;
r++;
}
return r - l - 1;
}
115. 不同的子序列
给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。
一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
题目数据保证答案符合 32 位带符号整数范围。
示例 1：
输入：S = "rabbbit", T = "rabbit"
输出：3
public int numDistinct(String s, String t) {
int len1 = s.length();
int len2 = t.length();
// dp i,j 表示的是 前i个字符和前j个字符的不同子序列数
// 如果 i，j 不同，前 i，j个不同序列是 i,j-1 是一样的，因为i代表t
// 如果相同，dp i,j = dp i-1,j-1 + dp i,j-1, 意思是可以直接将两者视为相同，也可以看做不同
int[][] dp = new int[len2+1][len1+1];
for(int i=0;i<=len1;i++){
dp[0][i] = 1;
}
for(int i=1;i<=len2;i++){
for(int j=1;j<=len1;j++){
if(s.charAt(j-1) == t.charAt(i-1)){
dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
}else{
dp[i][j] = dp[i][j-1];
}
}
}
return dp[len2][len1];
}
300. 最长上升子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
// 动态规划， dp[i] 表示以i位置结尾的最长上升子序列
// dp[i] = for 0 ~ i-1 max(dp[j])
public int lengthOfLIS(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
int[] dp = new int[nums.length];
int max = 1;
dp[0] = 1;
for(int i=1;i<nums.length;i++){
int curMax = 0;
for(int j=i-1;j>=0;j--){
if(nums[j] < nums[i]){
curMax = Math.max(curMax, dp[j]);
}
}
dp[i] = curMax + 1;
max = Math.max(dp[i], max);
}
return max;
}
使用二分查询
// 二分查找，依次将元素，替换对应位置，留下来的就是最长的那个序列
public int lengthOfLIS(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
// list 不能修改数字,set不能超过特定范围
List<Integer> list = new ArrayList<>();
int end = 0;
for(int i=0;i<nums.length;i++){
int left = 0, right = end;
while(left < right){
int mid = left + (right - left)/2;
if(list.get(mid) < nums[i]){
left = mid + 1;
}else{
right = mid;
}
}
if(left >= end){
list.add(nums[i]);
end++;
}else{
list.set(left, nums[i]);
}
}
return list.size();
}
// 二分查找，依次将元素，替换对应位置，留下来的就是最长的那个序列
public int lengthOfLIS(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
// list 不能修改数字,set不能超过特定范围
int[] list = new int[nums.length];
int end = 0;
for(int i=0;i<nums.length;i++){
int left = 0, right = end;
while(left < right){
int mid = left + (right - left)/2;
if(list[mid] < nums[i]){
left = mid + 1;
}else{
right = mid;
}
}
list[left] = nums[i];
if(left >= end){
end++;
}
}
return end;
}
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
// 使用 dp 进行 计算最大矩形的面积
public int maximalSquare(char[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return 0;
}
int[][] dp = new int[matrix.length][matrix[0].length];
int max = 0;
for(int i=0;i<matrix.length;i++){
if(matrix[i][0] == '1'){
dp[i][0] = 1;
max = 1;
}
}
for (int i=0;i<matrix[0].length;i++){
if(matrix[0][i] == '1'){
dp[0][i] = 1;
max = 1;
}
}
for(int i=1;i<matrix.length;i++){
for(int j=1;j<matrix[0].length;j++){
if(matrix[i][j] == '1'){
dp[i][j] = 1 + Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]));
}
max = Math.max(dp[i][j],max);
}
}
// 面积
return max*max;
}
279. 完全平方数
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
// 问题类似于coins问题
public int numSquares(int n) {
if(n < 2){
return n;
}
int sqrtn = (int)Math.sqrt(n);
int[] squares = new int[sqrtn];
for(int i=1;i<=sqrtn;i++){
squares[i-1] = i * i;
}
int[] dp = new int[n+1];
dp[1] = 1;
for(int i=2;i<=n;i++){
int curMin = n;
for(int j=0;j<sqrtn && squares[j] <= i;j++){
curMin = Math.min(dp[i-squares[j]],curMin);
}
dp[i] = curMin + 1;
}
return dp[n];
}
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
// dp[i] = Math.max(dp[i-1],dp[i-2] + nums[i]);
public int rob(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
int[] dp = new int[nums.length+2];
dp[0] = 0;
dp[1] = 0;
for(int i=2;i<nums.length +2;i++){
dp[i] = Math.max(dp[i-1],dp[i-2] + nums[i-2]);
}
return Math.max(dp[nums.length+1],dp[nums.length]);
}
213. 打家劫舍2
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [2,3,2]
输出: 3
思路是忽略第一个求一个结果，忽略最后一个求一个结果，只要一个时一个结果
// 思路首尾不互相打，打首不打尾，打尾不打手
public int rob(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
if(nums.length == 1){
return nums[0];
}
int[] dp = new int[nums.length+2];
for(int i=2;i<nums.length+1;i++){
dp[i] = Math.max(dp[i-1],dp[i-2] + nums[i-2]);
}
int max1 = Math.max(dp[nums.length],dp[nums.length-1]);
Arrays.fill(dp,0);
nums[0] = 0;
for(int i=2;i<nums.length+2;i++){
dp[i] = Math.max(dp[i-1],dp[i-2] + nums[i-2]);
}
int max2 = Math.max(dp[nums.length+1],dp[nums.length]);
return Math.max(max1,max2);
}
// 可以使用rangeCopy 将其放入一个函数中求解
public int rob(int[] nums) {
if (nums == null || nums.length == 0){
return 0;
}
if (nums.length == 1){
return nums[0];
}
int max = Math.max(myRob(Arrays.copyOfRange(nums, 0, nums.length - 1)), myRob(Arrays.copyOfRange(nums, 1, nums.length)));
return max;
}
private int myRob(int[] nums) {
int pre = 0, cur = 0, tmp;
for(int num : nums) {
tmp = cur;
cur = Math.max(pre + num, cur);
pre = tmp;
}
return cur;
}
120. 三角形最小路径和
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
例如，给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
// 动态规划， dp[i] = min(t[i-1],t[i])+dp[i]
public int minimumTotal(List<List<Integer>> triangle) {
if(triangle == null || triangle.size() == 0){
return 0;
}
List<Integer> list = triangle.get(triangle.size()-1);
int len = list.size();
int[] dp = new int[len];
for(int i=0;i<len;i++){
dp[i] = list.get(i);
}
for(int i=triangle.size()-2;i>=0;i--){
list = triangle.get(i);
for(int j=0;j<list.size();j++){
dp[j] = Math.min(dp[j],dp[j+1]) + list.get(j);
}
}
return dp[0];
}
}
64. 最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
// 动态规划， dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + num[i][j]
public int minPathSum(int[][] grid) {
if(grid == null || grid.length == 0 || grid[0].length == 0){
return 0;
}
int[][] dp = new int[grid.length][grid[0].length];
// init
dp[0][0] = grid[0][0];
for(int i=1;i<grid.length;i++){
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for(int i=1;i<grid[0].length;i++){
dp[0][i] = dp[0][i-1] + grid[0][i];
}
for(int i=1;i<grid.length;i++){
for(int j=1;j<grid[0].length;j++){
dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
}
}
return dp[grid.length-1][grid[0].length-1];
}
63.不同路径2
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
// dp[i][j] = dp[i-1][j] + dp[i][j-1] if i = m j = n 只有一个方法
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if(obstacleGrid == null || obstacleGrid.length == 0|| obstacleGrid[0].length == 0){
return 0;
}
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
// init
for(int i=m-1;i>=0;i--){
if(obstacleGrid[i][n-1] == 1){
break;
}
dp[i][n-1] = 1;
}
for(int i=n-1;i>=0;i--){
if(obstacleGrid[m-1][i] == 1){
break;
}
dp[m-1][i] = 1;
}
// dp
for(int i=m-2;i>=0;i--){
for(int j=n-2;j>=0;j--){
if(obstacleGrid[i][j] != 1){
dp[i][j] = dp[i+1][j] + dp[i][j+1];
}
}
}
return dp[0][0];
}
62. 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
// init
for(int i=m-1;i>=0;i--){
dp[i][n-1] = 1;
}
for(int i=n-1;i>=0;i--){
dp[m-1][i] = 1;
}
// dp
for(int i=m-2;i>=0;i--){
for(int j=n-2;j>=0;j--){
dp[i][j] = dp[i+1][j] + dp[i][j+1];
}
}
return dp[0][0];
}
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
public int climbStairs(int n) {
if(n < 3){
return n;
}
int dp_i_1 = 2;
int dp_i_2 = 1;
int dp = 0;
for(int i=3;i<=n;i++){
dp = dp_i_1 + dp_i_2;
dp_i_2 = dp_i_1;
dp_i_1 = dp;
}
return dp;
}
