vampire`blogs

leetcode-978. 最长湍流子数组 题解思路 123456789101112131415161718192021222324252627282930313233343536class Solution { public int maxTurbulenceSize(int[] A) { int n = A.length; int[][] dp = new int[n+1][2]; //初始化dp,第二位的0代表前一是下降,1代表为上升 dp[1][0] = 1; dp[1][1] = 1; for (int i = 2; i <= n; i++) { if (A[i - 2] < A[i - 1]) { // 当前为上升,所有前一个应该为下降 dp[i][1] = dp[i - 1][0] + 1; // 此时设置下降为1 ...

leetcode-面试题 17.11. 单词距离 原始思路 123456789101112131415161718192021222324252627282930class Solution { Map<String, List<Integer>> map = new HashMap<>(); public int findClosest(String[] words, String word1, String word2) { for (int i = 0; i < words.length; i++) { if (map.containsKey(words[i])) { List<Integer> list = map.get(words[i]); list.add(i); map.put(words[i], list);
...

leetcode-24. 两两交换链表中的节点 原始思路 1234567891011121314151617181920212223242526272829class Solution { ListNode root = null; public ListNode swapPairs(ListNode head) { if(head == null){ return head; } return dfs(head); } public ListNode dfs(ListNode root){ if(root == null){ return root; } ListNode node1 = new ListNode(root.val); if(root.next == null){ return node1; ...

leetcode-213. 打家劫舍 II 原始思路 1234567891011121314151617181920212223242526272829class Solution { public int rob(int[] nums) { int n = nums.length; int[][][] dp = new int[n+1][2][2]; dp[1][0][0] = 0; dp[1][1][1] = nums[0]; for(int i = 2; i <= n; i++){ //第一家房子没有被抢 if(i == 2){ dp[i][0][0] = dp[i-1][0][0]; }else{ dp[i][0][0] = Math.max(dp[i-1][0][0],dp[i-1][1][0]); ...

leetcode-198. 打家劫舍 原始思路 12345678910111213class Solution { public int rob(int[] nums) { int n = nums.length; int[][] dp = new int[n+1][2]; for(int i = 1; i <= n; i++){ dp[i][0] = Math.max(dp[i-1][1], dp[i-1][0]); dp[i][1] = dp[i-1][0] + nums[i-1]; } return Math.max(dp[n][0],dp[n][1]); }}

leetcode-1043. 分隔数组以得到最大和 题解思路 12345678910111213141516class Solution { public int maxSumAfterPartitioning(int[] arr, int k) { int n = arr.length; int[] dp = new int[n + 1]; for (int i = 1; i <= n; i++) { //前i个dp的和 int max = Integer.MIN_VALUE; for (int j = 1; j <= Math.min(k, i); j++) { max = Math.max(max, arr[i - j]); dp[i] = Math.max(dp[i], dp[i - j] + j * max); } ...

leetcode-剑指 Offer 47. 礼物的最大价值 1234567891011121314151617181920212223class Solution { public int maxValue(int[][] grid) { int n1 = grid.length; int n2 = grid[0].length; int[][] dp = new int[n1][n2]; // 初始化dp dp[0][0] = grid[0][0]; for (int i = 1; i < n1; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; } for (int i = 1; i < n2; i++) { dp[0][i] = dp[0][i - 1] + grid[0][i]; } ...

leetcode-338. 比特位计数 动规思路 123456789101112131415161718192021222324252627282930313233343536class Solution { public int[] countBits(int num) { int[] dp = new int[num + 1]; dp[0] = 0; if (num == 0) { return dp; } dp[1] = 1; if (num == 1) { return dp; } for (int i = 2; i <= num; i++){ if (((i-1) & 1) == 1) { //说明为奇数 String str = Integ ...

leetcode-面试题 04.03. 特定深度节点链表 原始思路 12345678910111213141516171819202122232425262728293031323334353637383940414243class Solution { LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); List<ListNode> list = new ArrayList<>(); public ListNode[] listOfDepth(TreeNode tree) { if (tree == null) { return null; } queue.offer(tree); while (!queue.isEmpty()) { ListNode root = null; List ...

leetcode-877. 石子游戏 123456789101112131415161718192021222324class Solution { public boolean stoneGame(int[] piles) { int n = piles.length; int[][] dp = new int[n][n]; //初始化dp,当i==j时,证明只有这个数字可选了 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == j) { dp[i][j] = piles[i]; } } } // 斜着遍历距离,每次求先手的与后手的差值 for (int i = n ...