import java.util.Arrays; import java.util.LinkedList; public class TreeSerialization { // 方法一：DFS，先序遍历 // 序列化方法 public String serialize(TreeNode root) { // 定义一个StringBuffer来保存序列化结果 StringBuffer result = new StringBuffer(); result.append("["); dfs_serialize(root, result); result.deleteCharA...

import java.util.ArrayList; import java.util.HashMap; import java.util.List; public class LetterCombination { // 用一个HashMap来记录数字和字母的对应关系 HashMap<Character, String> numberMap = new HashMap<Character, String>(){ { put('2', "abc"); put('3', "def"); put('4', "ghi&quo...

import java.util.ArrayList; import java.util.Collections; import java.util.HashSet; import java.util.List; public class Permutation { //方法一：回溯 public List<List<Integer>> permute1(int[] nums) { //定义保存结果的list ArrayList<List<Integer>> result = new ArrayList<>(); //用一个Array...

import java.util.*; public class EightQueens { // 方法一：暴力穷举 public List<int[]> eightQueens1(){ // 定义保存结果的List ArrayList<int[]> result = new ArrayList<>(); // 用一个int[8]数组保存一组解 int[] solution = new int[8]; // 遍历八皇后每种可以摆放的场景，判断是否符合题目限制 for (solution[0] = 0; solution[0] < 8; solution...

public class LCS { //动态规划 public int longestCommonSubsequence(String text1, String text2) { int l1 = text1.length(); int l2 = text2.length(); //定义一个二位矩阵 int[][] dp = new int[l1+1][l2+1]; //遍历所有的状态,递推求解 for (int i = 1; i <=l1; i++) { for (int j = 1;j<=l2;j++){ //判断两个新增字符关系，进行状态转移 if(text1.charA...

public class CoinChange { // 动态规划 public int coinChange(int[] coins, int amount){ int n = coins.length; // 硬币种类数 // 定义dp数组，保存金额为i的对应最少硬币数为dp[i] int[] dp = new int[amount + 1]; // 初始状态 dp[0] = 0; // 遍历状态，依次转移 for (int i = 1; i <= amount; i++){ // 保留当前硬币的最小数量 int minNum = Integer.MAX_VALUE; // 遍历所有...

public class HouseRobber { //方法一：动态规划 public int rob1(int[] nums) { int n = nums.length; //特殊情况 if(nums==null||n==0){ return 0; } //定义状态，将前i个房屋能偷到的最大金额保存到dp[i]中 int[] dp = new int[n+1]; //定义初始状态 dp[0] = 0; dp[1] = nums[0]; //遍历状态，依次转移 for (int i = 2; i <=n; i++) { dp[i] = Math.max(dp[i-1],dp[i-2]...

public class ClimbStairs { //方法一：动态规划 public int climbStairs1(int n) { //定义两个临时变量，保存前两个状态 int pre2 = 1,pre1 = 1;//fib(1)和fib(2) int curr; for (int i = 1; i <n ; i++) { //定义一个临时变量,保存当前的状态 curr = pre1+pre2; pre2 = pre1; pre1 = curr; } return pre1; } //方法二：数学公式法 public int climbStairs(int n) { doubl...

public class BestTimeToBuyAndSellStock { //方法一：暴力破解 public static int maxProfit1(int prices[]) { int maxProfit = 0; //遍历所有可能的买入卖出的情况 for (int i = 0; i <prices.length-1 ; i++) { for (int j = i;j<prices.length;j++){ int currProfit = prices[j]-prices[i]; maxProfit = Math.max(maxProfit,currProfit)...

public class KnapsackProblem { //动态规划实现 public int maxValue1(int capacity,int[] weights,int[] values){ int n = weights.length; //定义状态 int[][] dp = new int[n+1][capacity+1]; //遍历所有子问题，依次计算状态 for (int i = 1; i <=n ; i++) { for (int j = 0; j <=capacity ; j++) { //判断当前的背包容量j是否能放下物品i if(j>=weigh...

public class Fibonacci { // 方法一：利用数学递推式，直接递归 public int fib1(int n){ // 基准情况 if (n == 0) return 0; if (n == 1) return 1; // 递归调用 return fib1(n - 2) + fib1(n - 1); } // 方法二：动态规划 public int fib2(int n){ // 返回基准情况 if (n == 1 || n == 2) return 1; // 定义一个状态数组，保存就是fib(n)的计算结果 int[] dp = new int[n]; dp[0] ...

import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.Map; public class TaskScheduler { //方法一：模拟法 public int leastInterval1(char[] tasks, int n) { //用hashmap进行统计每个任务出现的次数 HashMap<Character, Integer> countMap = new HashMap<>(); for (char task...

public class JumpGames2 { //方法一：反向跳跃 public int jump1(int[] nums) { //定义一个变量保存跳跃步数 int steps = 0; //定义循环变量 int currPosition = nums.length-1; //不停的向前跳跃，以最远的距离 while (currPosition>0){ //从前到后遍历数组元素，找到当前距离最远的“上一步位置” for (int i = 0; i <currPosition ; i++) { if(i+nums[i]>=currPosition){{ currPosi...

public class JumpGames { //方法一：暴力，遇到0的时候就去判断一下前面的数是否可以跳过这个0，如果最后一个数是0，判断是否可以刚好到达或者跳跃该数 public boolean canJump1(int[] nums) { if(nums[0]==0&&nums.length!=1) return false; for (int i = 1; i <nums.length ; i++) { if(nums[i]==0){ //写一个方法判断这个0是否可以跳跃过去 boolean fl = flag(nums,i); if(fl){ continu...