1.回溯算法思想
leetcode 112 号算法题：路径总和
leetcode 113 号算法题：路径总和 II
leetcode 46 号算法题：全排列
leetcode 47 号算法题：全排列 II
leetcode 77 号算法题：组合
leetcode 39 号算法题：组合总和
// 输入：candidates = [2,3,6,7], target = 7,
//所求解集为：
//[
// [7],
// [2,2,3]
//]
public List<List<Integer>> combinationSum(int[] candidates, int target) {
int len = candidates.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
Deque<Integer> path = new ArrayDeque<>();
dfs(candidates, 0, len, target, path, res);
return res;
}
/**
* @param candidates 候选数组
* @param begin 搜索起点
* @param len 冗余变量，是 candidates 里的属性，可以不传
* @param target 每减去一个元素，目标值变小
* @param path 从根结点到叶子结点的路径，是一个栈
* @param res 结果集列表
*/
private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
// target 为负数和 0 的时候不再产生新的孩子结点
if (target < 0) {
return;
}
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
// 重点理解这里从 begin 开始搜索的语意
for (int i = begin; i < len; i++) {
path.addLast(candidates[i]);
// 注意：由于每一个元素可以重复使用，下一轮搜索的起点依然是 i，这里非常容易弄错
dfs(candidates, i, len, target - candidates[i], path, res);
// 状态重置
path.removeLast();
}
}
leetcode 40 号算法题：组合总和 Ⅱ
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
int len = candidates.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
Deque<Integer> path = new ArrayDeque<>();
Arrays.sort(candidates);
dfs(candidates, 0, len, target, path, res);
return res;
}
/**
* @param candidates 候选数组
* @param begin 搜索起点
* @param len 冗余变量，是 candidates 里的属性，可以不传
* @param target 每减去一个元素，目标值变小
* @param path 从根结点到叶子结点的路径，是一个栈
* @param res 结果集列表
*/
private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
// 重点理解这里从 begin 开始搜索的语意
for (int i = begin; i < len; i++) {
// 大剪枝：减去 candidates[i] 小于 0，减去后面的 candidates[i + 1]、candidates[i + 2] 肯定也小于 0，因此用 break
if(target-candidates[i]<0){
break;
}
// 小剪枝：同一层相同数值的结点，从第 2 个开始，候选数更少，结果一定发生重复，因此跳过，用 continue
if(i>begin && candidates[i]==candidates[i-1]){
System.out.println("i>>"+i+">>begin>>"+begin);
continue;
}
path.addLast(candidates[i]);
System.out.println("递归之前 => " + path + "，剩余 = " + (target - candidates[i]));
//因为不能重复 所以是i+1
dfs(candidates, i+1, len, target - candidates[i], path, res);
path.removeLast();
System.out.println("递归之后 => " + path);
}
}
leetcode 216 号算法题：组合总和 Ⅲ
public List<List<Integer>> combinationSum3(int k, int n) {
Deque<Integer> list = new LinkedList<>();
List<List<Integer>> re = new ArrayList<>();
dfs(1, re, k, n, list);
return re;
}
private void dfs(int begin, List<List<Integer>> result, int count, int target, Deque<Integer> list) {
if (count == 0 && target == 0) {
result.add(new ArrayList<>(list));
return;
}
for (int i = begin; i <=9; i++) {
if (count < 0 || target < 0) {
break;
}
System.out.println("beigin的值>>"+begin);
list.addLast(i);
System.out.println("递归之前 => " + list + "，剩余 = " + (target - i));
//因为不能重复 所以从i+1开始
dfs(i + 1, result, count - 1, target - i, list);
list.removeLast();
System.out.println("递归之后 => " + list);
}
}
leetcode 78 号算法题：子集
leetcode 90 号算法题：子集Ⅱ
leetcode 17 号算法题：电话号码的字母组合
leetcode 93 号算法题：复原 IP 地址
leetcode 22 号算法题：括号生成
leetcode 51 号算法题：N 皇后
leetcode 37 号算法题：数独问题
2.贪心算法思想
leetcode 455 号算法题：分发饼干
leetcode 322 号算法题：零钱兑换
leetcode 45 号算法题：跳跃游戏 Ⅱ
leetcode 1578 号算法题：避免重复字母的最小删除成本
leetcode 402 号算法题：移掉K位数字
3.动态规划算法思想
leetcode 509 号算法题：斐波那契数
leetcode 322 号算法题：零钱兑换
leetcode 64 号算法题：最小路径和
leetcode 53 号算法题：最大子数组之和
最大连续子序列和
public static int maxSubArray(int [] nums){
int [] dp=new int[nums.length];
int max=dp[0];
for (int i = 1; i < nums.length; i++) {
if(dp[i-1]<0){
dp[i]=nums[i];
}else {
dp[i]=nums[i]+dp[i-1];
}
max=Math.max(max,dp[i]);
}
return max;
}
leetcode 647 号算法题：回文子串
leetcode 5 号算法题：最长回文串
public String longestPalindrome(String s) {
if(s==null){
return null;
}
char[] chars = s.toCharArray();
if(chars.length==0){
return s;
}
//可能情况
//一 i-dp[i-1]-1位置和 i位置相同 则dp[i]=dp[i-1]+2
//二 不相同 则dp[i]=1
boolean [][] dp=new boolean[chars.length][chars.length];
int maxLen=1;
int begin=0;
for(int i=chars.length-1;i>=0;i--){
for(int j=i;j<chars.length;j++){
int len=j-i+1;
dp[i][j]=chars[i]==chars[j]&&(len<=2 || dp[i+1][j-1]);
if(dp[i][j]&&len>maxLen){
maxLen=len;
begin=i;
}
}
}
return new String(chars,begin,maxLen);
}
leetcode 131 号算法题：分割回文串
leetcode 516 号算法题：最长回文子序列
leetcode 300 号算法题：最长上升子序列
//输入：nums = [10,9,2,5,3,7,101,18]
//输出：4
//解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
public int lengthOfLIS(int[] nums) {
if(nums==null || nums.length==0) return 0;
int [] dp=new int[nums.length];
int max=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]){
continue;
}else{
dp[i]=Math.max(dp[i],dp[j]+1);
}
}
max=Math.max(max,dp[i]);
}
return max;
}
leetcode 1143 号算法题：最长公共子序列
leetcode 72 号算法题：编辑距离
leetcode 44 号算法题：通配符匹配
leetcode 10 号算法题：正则表达式匹配
leetcode 486 号算法题：预测赢家
leetcode 877 号算法题：石子游戏
最长有效括号
0-1 背包问题
网友评论