import java.util.*; public class Solution { //f[i] 表示该位置必选时最打金额 //g[i] 表示该位置不选时最大金额 public int rob (int[] nums) { // write code here int n = nums.length; int[] f= new int [n]; //必选 int[] g = new int [n]; //不选 //1.初始化 必选为发nums[0] f[0] = nums[0]; g[0] = 0; //2.填表 1.必选时，此时的值即为g[i-1](表示i-1不选) + nums[i]。...

import java.util.*; public class Solution { //反序列化位置 int index =0; String Serialize(TreeNode root) { if(root ==null){ return "#"; } StringBuilder res = new StringBuilder(); se(root,res); return res.toString(); } //处理序列化 private void se(TreeNode root ,StringBuilder str){ if(root==null){ str...

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param A string字符串 * @return int整型 */ //dp[i][j] 表示以i-j的回文字符串 public int getLongestPalindrome (String A) { // write code here int n = A.length(); boolean[][] dp = new boolean[n][n]; //1.初始化 虚拟节点为""...

import java.util.*; public class Solution { //dp[i][j]表示字符串1前i个和字符串2前j个中最长公共子串，注意的说，我们子串连续 public static String LCS (String str1, String str2) { // write code here //1.建表 int n = str1.length(),m = str2.length(); String[][] dp = new String[n+1][m+1]; //虚拟节点设为空即可 for(int i=0;i<=n;i++){ for(int j=0;...

import java.util.*; public class Solution { //dp[i][j],表示字符串1以i位置元素结尾和字符串2以j位置结尾的最长公共子序列 public String LCS (String s1, String s2) { //1建表 int m = s1.length(); int n = s2.length(); String [][] dp = new String[m+1][n+1]; // 2.初始化null为“ ” for(int i=0;i<=m;i++){ for(int j=0;j<=n;j++){ dp[i][j] = &...

import java.util.*; /** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val = val; * } * } * */ import java.util.ArrayList; public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> ret = ...

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return string字符串 */ public String replaceSpace (String s) { // write code here StringBuilder s1 = new StringBuilder(); int l = s.length(); for(int i=0;i<l;i++){ if(s.charAt(i)==' '){...

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param target int整型 * @param array int整型二维数组 * @return bool布尔型 */ public boolean Find (int target, int[][] array) { // write code here //特殊情况 int m= array.length; int n = array[0].length; if(m==1&&n=...

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param numbers int整型一维数组 * @return int整型 */ public int duplicate (int[] numbers) { // write code here int n = numbers.length; int[] arr = new int[n]; for(int i =0;i<n;i++){ arr[numbers[i]] += 1; } //遍历存储元...

import java.util.*; //子数组必须连续，子序列不用连续。 public class Solution { //dp[i] 表示以i位置元素结尾的最长上升子序列长度 //两种情况：1.单独i位置为一个子序列 //2.跟在前面某个子序列（最长）后面构成子序列 public int LIS (int[] arr) { // write code here //1.创建dp表 int n = arr.length; if(n==0) return 0; int[] dp = new int[n]; //2.初始化为1 for(int i=0;i<n;i++){ dp[i] =...

import java.util.Scanner; import java.util.*; //dp[i][j]表示从i个物品中选 //总体积不超过j的最大价值和 public class Main { static int N = 1010; static int n,V; //总数、总体积 static int[] v = new int[N]; //表示体积 static int[] w = new int[N]; //表示价值 static int[][] dp = new int[N][N]; public static void main(String[] args) { Scan...

import java.util.*; public class Solution { //解码：第i个字符结尾有多少种编码方式 //解码：i 单独解码，i与i-1结合解码，解码成功或失败 public int solve (String nums) { // write code here //1.创建dp int n= nums.length(); int[] dp = new int[n]; char[] c = nums.toCharArray(); //2。初始化, 要初始化前两个，防止越界 //单独解码 if(c[0]!='0') dp[0] +=1; //解码成功 if(n==1...

import java.util.*; public class Solution { //1.以第dp[i][j]结尾的最小路径和。 public static int minPathSum (int[][] matrix) { // write code here int m = matrix.length; int n = matrix[0].length; int[][] dp = new int[m+1][n+1]; //1,初始化 要保证dp数组的第一列和第一行填表时满足逻辑 dp[0][0] = matrix[0][0]; //处理第一行 for(int i=1;i<n;i...

import java.util.*; public class Solution { public int uniquePaths (int m, int n) { int[][] dp = new int [m+1][n+1]; //添加虚拟点 //1.初始化 ；让起点一列为1，其他虚拟节点为0 dp[0][1] = 1; //2.填表 :从实际的开始 for(int i=1;i<m+1;i++){ for(int j=1;j<n+1;j++){ dp[i][j] = dp[i-1][j] +dp[i][j-1]; } } return dp[m][n]; } }