vampire`blogs

leetcode-121. 买卖股票的最佳时机 原始思路 123456789101112131415161718192021class Solution { public int maxProfit(int[] prices) { if (prices.length < 2){ return 0; } int n = prices.length; //定义dp数组 int[][] dp = new int[n][2]; //初始化数组 dp[0][0] = 0; dp[0][1] = -prices[0]; for (int i = 1; i < prices.length; i++) { dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); //此处-pric ...

152. 乘积最大子数组 原始思路 1234567891011121314151617181920212223242526272829303132class Solution { public int maxProduct(int[] nums) { int n = nums.length; int[][] dp = new int[n][2]; //初始化状态值dp[i][0]代表最小值,dp[i][1]代表最大值 dp[0][0] = nums[0]; dp[0][1] = nums[0]; //从第二个数开始遍历 for(int i = 1; i < n; i++){ if(nums[i] <= 0){ //小于0时,如果最小值为负数,此时相乘为最大值 dp[i][0] = Math.min(nums[i], d ...

leetcode-637. 二叉树的层平均值 1234567891011121314151617181920212223242526272829class Solution { List<Double> result = new ArrayList<>(); public List<Double> averageOfLevels(TreeNode root) { LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); queue.add(root); while (!queue.isEmpty()) { long sum = 0; int size = queue.size(); for (int i = 0; i < size; i++) { TreeNode node = ...

leetcode-120. 三角形最小路径和 原始思路 1234567891011121314151617class Solution { public int minimumTotal(List<List<Integer>> triangle) { int n = triangle.size(); // 初始记录的状态的数组 int[][] dp = new int[n+1][n+1]; // 自底向上递推 for (int i = n - 1; i >=0 ; i--) { //从左到右 for (int j = 0; j <= i; j++) { // 定义状态转移方程 dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + triangle.get(i).get(j); ...

leetcode-70.爬楼梯 原始思路 123456789101112131415class Solution { public int climbStairs(int n) { if (n == 0 || n == 1){ return n; } // 定义初始状态 int[] mem = new int[n+1]; mem[1] = 1; mem[2] = 2; for (int i = 3; i<= n; i++){ mem[i] = mem[i-1] + mem[i-2]; } return mem[n]; }}

leetcode-459.重复的子字符串 123456789101112131415161718192021class Solution { public boolean repeatedSubstringPattern(String s) { int n = s.length(); //暴力法,假设重复的个数是1到n for (int i = 1; i*2 <= n; i++) { if (n % i == 0){ Boolean bool = true; for (int j = i; j < n; j++) { if (s.charAt(j - i) != s.charAt(j)) { bool = false; break; ...

leetcode-面试题16.11跳水板 原始思路 123456789101112131415161718192021222324class Solution { public int[] divingBoard(int shorter, int longer, int k) { if(k == 0){ return new int[0]; } List<Integer> result = new ArrayList<>(); HashSet<Integer> set = new HashSet<>(); for(int i = 0; i <= k; i++){ int num = shorter*i+longer*(k - i); if(!set.contains(num)){ resul ...

leetcode-547.朋友圈 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455class Solution { public int findCircleNum(int[][] M) { // 初始化存储父节点 int[] parent = new int[M.length]; // 将所有的数的parent均初始化为-1,表示自己指向自己 for (int i = 0; i < parent.length; i++) { parent[i] = i; } //遍历矩阵 for (int i = 0; i < M.length ; i++) { for (int j = 0; j < M.length ; j++) & ...

leetcode-491.递增子序列 原始思路 1234567891011121314151617181920212223242526272829class Solution { List<List<Integer>> result = new ArrayList<>(); List<Integer> ans = new ArrayList<>(); Set<String> set = new HashSet<>(); public List<List<Integer>> findSubsequences(int[] nums) { dfs(-101, 0 , nums); return result; } public void dfs(int pre, int begin, int[] nums){ if (begin > nums.length)&# ...

leetcode-17. 电话号码的字母组合 原始思路 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748class Solution { List<String> result = new ArrayList<>(); StringBuffer sb = new StringBuffer(); public List<java.lang.String> letterCombinations(String digits) { //初始化数组,输入如23 String[] arr = new String[]{"a","b","c","d","e","f","g","h","i" ...