ChengGuang

Integer BreakLeetCode 343. 12345678910public int integerBreak(int n) { int[] dp = new int[n + 1]; dp[1] = 1; for (int i = 2; i <= n; i++) { for (int j = 1; j <= i - 1; j++) { dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j))); } } return dp[n];} Mathematical solution12345678910111213141516171819class Solution { public int integerBreak(int n) { if(n <=3){ return n -1;  ...

Longest Palindromic SubsequenceLeetCode 516. Use dp[i][j] denote the length of the longest palindrome subsequence in the subscript range [i, j] of the string s. when i < j if s[i] = s[j] ​ dp[i][j] = dp[i+1][j - 1] + 2; if s[i] != s[j] ​ dp[i][j] = Math.max(dp[i+1][j],dp[i][j - 1]); 1234567891011121314151617181920212223class Solution { public int longestPalindromeSubseq(String s) { if(s == null || s.length() == 0) return 0; int n = s.length(); ...

Tree DFS自顶而下 是否需要双重递归(即调用根节点的dfs函数后，继续调用根节点的左右节点的pathsum函数): 看题目是从根节点开始，还是从任意节点开始。 是否需要return： 取决于题目是否要求找到叶子节点满足条件的路径，如果是必须到叶节点，就要return。 是否需要回溯: 大部分二叉树不需要，因为dfs(root.left) 和 dfs(root.right) 已经把可能的路径穷尽了。 一般路径123456789101112131415List<List<Integer>> res;public void dfs(TreeNode root, List<Integer> path){ //recursion stop condition if(root == null) return; path.add(root.val); if(root.left == null && root.right == null){ //collect the ...

Isomorphic StringsLeetcode 205. 123456789101112131415class Solution { public boolean isIsomorphic(String s, String t) { int[] s1 = new int[256]; int[] t1 = new int[256]; for(int i = 0; i < s.length();i++){ char sc = s.charAt(i); char tc = t.charAt(i); if(s1[sc] != t1[tc]) return false; s1[sc] = i + 1; t1[tc] = i + 1; } return true; }}

Longest PalindromeLeetcode 409. Version 112345678910111213141516171819202122232425class Solution { public int longestPalindrome(String s) { int length = s.length(); int[] arr = new int[58]; for(int i = 0; i < length;i++){ arr[s.charAt(i) - 'A']++; } int max = 0; int oddMax = 0; int passedIndex = 0; for(int i = 0; i < arr.length;i++){ int value = arr[i]; if(value % 2 == 0){ ...

Valid AnagramLeetcode 242. Version 112345678910111213141516171819class Solution { public boolean isAnagram(String s, String t) { int l1 = s.length(); int l2 = t.length(); if(l1 != l2) return false; int[] store = new int[26]; for(int i = 0, j = 0; i < l1 && j < l2;i++,j++){ store[s.charAt(i) - 'a']++; store[t.charAt(j) - 'a']--; } for(int value: store){ if(value != 0) ...

Odd Even Linked ListLeetcode 328. 123456789101112131415161718192021222324252627/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode oddEvenList(ListNode head) { if(head == null) return head; ListN ...

Split Linked List in PartsLeetcode 725. 1234567891011121314151617181920212223242526272829303132333435363738/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode[] splitListToParts(ListNode root, int k) { int originalSize = 0; ListNode temp = root; while(temp != null){ originalSize++; temp = tem ...

Palindrome Linked ListLeetcode 234. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public boolean isPalindrome(ListNode head) { ...

Add Two Numbers IILeetcode 455. version 1 Without Modify the original Linked Lists123456789101112131415161718192021222324252627282930313233343536/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { Stack<Integer> l1Stack = buildStack(l1); Stack<Integer> l2Stack = buildStack( ...