y-a-b-e

摘要：算法链表总结翻转链表二叉树数搜索区间矩阵走法，数组矩阵字符串一个数组能否分成两堆数，使两堆数的和相等先求总和，若有一堆数，和为，那么就没问题。

【LC总结】翻转链表 Swap in Pairs, Reverse in k-Group, Reverse LinkedList###Reverse a doubly linkedlist

Iteration:

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode pre = null;
    while (head != null) {
        ListNode temp = head.next;    
        head.next = pre;
        pre = head;
        head = temp;
    }
    return pre;
}

Recursion:

public reverseList(ListNode head) {
    return helper(head, null);
}
public ListNode helper(ListNode head, ListNode newHead) {
    if (head == null) return head;
    ListNode temp = head.next;
    head.next = newHead;
    return helper(temp, head);
}

public class Solution {
    public boolean isSubtree(TreeNode T1, TreeNode T2) {
        if (T2 == null) return true;
        if (T1 == null) return false;
        if (isEqual(T1, T2)) return true;
        return (isSubtree(T1.left, T2) || isSubtree(T1.right, T2));
    }
    public boolean isEqual(TreeNode A, TreeNode B) {
        if (A == null || B == null) return A == B;
        if (A.val != B.val) return false;
        return isEqual(A.left, B.left) && isEqual(A.right, B.right);
    }
}

If is required bottom-up, use Collections.reverse(res);

public class Solution {
    public List> levelOrder(TreeNode root) {
        List> res = new ArrayList<>();
        if (root == null) return res;
        Queue q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            List cur = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                cur.add(node.val);
                if (node.left != null) q.offer(node.left);
                if (node.right != null) q.offer(node.right);
            }
            res.add(cur);
        }
        return res;
    }
}

public class BSTIterator {
    Stack stack = new Stack<>();
    public BSTIterator(TreeNode root) {
        pushLeft(root);
    }
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    /** @return the next smallest number */
    public int next() {
        if (hasNext()) {
            TreeNode node = stack.pop();
            pushLeft(node.right);
            return node.val;
        }
        return -1;
    }
    public void pushLeft(TreeNode root) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }
}

Recursion:

public int maxheight(TreeNode root) {
    if (root == null) return 0;
    return Math.max(maxheight(root.left), maxheight(root.right))+1;
}

Iteration:

    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Queue q = new LinkedList<>();
        q.offer(root);
        int max = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            max++;
            while (size > 0) {
                TreeNode cur = q.poll();
                if (cur.left != null) q.offer(cur.left);
                if (cur.right != null) q.offer(cur.right);
                size--;
            }
        }
        return max;
    }

Follow-up: find the min depth of BST

    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        if(root.left != null && root.right != null) return Math.min(minDepth(root.left), minDepth(root.right))+1;
        else if (root.left == null) return minDepth(root.right)+1;
        else return minDepth(root.left)+1;
    }

class TrieNode {
    boolean exist;
    char ch;
    TrieNode[] children;
    public TrieNode() {}
    public TrieNode(char ch) {
        this.ch = ch;
    }
}

public class Trie {
    private TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    
    // Inserts a word into the trie.
    public void insert(String word) {
        if (word == null || word.length() == 0) return;
        TrieNode pre = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - "a";
            if (pre.children == null) pre.children = new TrieNode[26];
            if (pre.children[index] == null) pre.children[index] = new TrieNode(word.charAt(i));
            pre = pre.children[index];
            if (i == word.length()-1) pre.exist = true;
        }
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        if (word == null || word.length() == 0) return false;
        TrieNode pre = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - "a";
            if (pre.children == null || pre.children[index] == null) return false;
            if (i == word.length()-1 && pre.children[index].exist == false) return false;
            pre = pre.children[index];
        }
        return true;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        if (prefix == null || prefix.length() == 0) return false;
        TrieNode pre = root;
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i) - "a";
            if (pre.children == null || pre.children[index] == null) return false;
            pre = pre.children[index];
        }
        return true;
    }
}

public class Solution {
    public int search(int[] A, int target) {
        int start = 0, end = A.length-1, mid = 0;
        while (start <= end) {
            mid = (start+end)/2;
            if (A[mid] == target) return mid;
            if (A[start] <= A[mid]) {
                if (A[start] <= target && target < A[mid]) end = mid-1;
                else start = mid+1;
            }
            else {
                if (A[mid] <= target && target <= A[end]) start = mid+1;
                else end = mid-1;
            }
        }
        return -1;
    }
}

class Solution {
    public ArrayList insert(ArrayList A, Interval one) {
        if (A == null) {
            ArrayList res = new ArrayList<>();
            res.add(one);
            return res;
        }
        if (A.size() == 0) {
            A.add(one);
            return A;
        }
        int pos = -1;
        for (int i = 0; i < A.size(); i++) {
            if (A.get(i).start < one.start) pos = i;
            else break;
        }
        A.add(pos+1, one);
        Interval pre = A.get(0);
        for (int i = 1; i < A.size(); i++) {
            Interval cur = A.get(i);
            if (cur.start <= pre.end) {
                pre.end = pre.end > cur.end ? pre.end: cur.end;
                A.remove(cur);
                i--;
            }
            else pre = cur;
        }
        return A;
    }
}

I

public class Solution {
    public boolean isUgly(int num) {
        if(num == 0){
            return false;
        }
        int rem2 = num % 2;
        int rem3 = num % 3;
        int rem5 = num % 5;
        while(rem2 == 0 || rem3 == 0 || rem5 == 0){
            if(rem2 == 0){
                num = num / 2;
            } else if(rem3 == 0){
                num = num / 3;
            } else {
                num = num / 5;
            }
            rem2 = num % 2;
            rem3 = num % 3;
            rem5 = num % 5;
        }
        return num == 1;
    }
}

II

public class Solution {
    public int nthUglyNumber(int n) {
        List res = new ArrayList<>();
        res.add(1);
        int i2 = 0, i3 = 0, i5 = 0;
        while (res.size() < n) {
            int u2 = res.get(i2) * 2;
            int u3 = res.get(i3) * 3;
            int u5 = res.get(i5) * 5;
            int min = Math.min(u2, Math.min(u3, u5));
            res.add(min);
            if (min == u2) i2++;
            if (min == u3) i3++;
            if (min == u5) i5++;
        }
        return res.get(n-1);
    }
}

public class Solution {
    List> res = new ArrayList<>();
    public List> combine(int n, int k) {
        if (n < k || n == 0) return res;
        helper(1, n, k, new ArrayList());
        return res;
    }
    public void helper(int start, int n, int k, List pre) {
        if (pre.size() == k) res.add(pre);
        for (int i = start; i <= n; i++) {
            List cur = new ArrayList<>(pre);
            cur.add(i);
            helper(i+1, n, k, cur);
        }
    }
}

Without Obstacles

public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 1;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

With Obstacles

public class Solution {
    public int uniquePathsWithObstacles(int[][] A) {
        int m = A.length, n = A[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            if (A[i][0] == 0) dp[i][0] = 1;
            else break;
        }
        for (int j = 0; j < n; j++) {
            if (A[0][j] == 0) dp[0][j] = 1;
            else break;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (A[i][j] == 0) dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
        return dp[m-1][n-1];
    }
}

public class Solution {
    public boolean canAttendMeetings(Interval[] intervals) {
        for (int i = 0; i < intervals.length-1; i++) {
            for (int j = i+1; j < intervals.length; j++) {
                Interval a = intervals[i];
                Interval b = intervals[j];
                if (a.end <= b.start || a.start >= b.end) continue;
                else return false;
            }
        }
        return true;
    }
}

Given a ordered set of integers from 1 to 9. Combine them using + or - or nothing, such that the resulting equation sum is 100.
 Ex: 1 + 2 + 34 - 5 + 67 - 8 + 9 = 100;
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100;

public List getAllCombination(int sum) {
    List res = new ArrayList<>();
    String nums = “123456789”;
    helper(nums, 0, “”, sum, res);
    return res;
}

public void helper(String nums, int index, String pre, int sum, List res) {
    if (index == nums.length() && sum == 0) {
        res.add(pre);
        return;
    }
    for (int i = index; i < nums.length(); i++) {
        String str = nums.substring(index, i+1);
        int val = Integer.valueOf(str);
        if (pre.length() == 0) helper(nums, i+1, str, sum-val, res);
        else {
            helper(nums, i+1, pre + ”+” + str, sum-val, res);
            helper(nums, i+1, pre + “-“ + str, sum+val, res);
        }
    }
}

public class Solution {
    public boolean anagram(String s, String t) {
        if (s == null) return t == null;
        if (t == null) return s == null;
        if (s.length() != t.length()) return false;
        int[] dict = new int[256];
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            dict[(int)ch]++;
        }
        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            dict[(int)ch]--;
            if (dict[(int)ch] < 0) return false;
        }
        return true;
    }
};

一个数组能否分成两堆数，使两堆数的和相等？
先求总和volumn，若有一堆数，和为volumn/2，那么就没问题。
Use DP as Backpack problem to solve this.

public class Solution {
    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length < 2) return false;
        int volumn = 0;
        for (int num: nums) volumn += num;
        if (volumn%2 == 1) return false;
        int sum = volumn/2;
        boolean[] dp = new boolean[sum+1];
        dp[0] = true;
        for (int i = 0; i < nums.length; i++) {
            for (int j = sum; j >= nums[i]; j--) {
                dp[j] = dp[j] || dp[j-nums[i]];
            }
        }
        return dp[sum];
    }
}

public class Solution {
    public int backPackV(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >= 0; j--) {
                if (j >= nums[i]) dp[j] += dp[j-nums[i]];
            }
        }
        return dp[target];
    }
}

public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        Arrays.sort(nums);
        int max = 1;
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]+1) count++;
            else if (nums[i] == nums[i-1]) continue;
            else count = 1;
            max = Math.max(max, count);
        }
        return max;
    }
}

public class Solution {
    public String largestNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = Integer.toString(nums[i]);
        }
//这里有个技巧，就是我们把两个数拼在一起，
//然后再把这两个数换个顺序再拼在一起，这时候就可以直接比较了
        Arrays.sort(strs, new Comparator(){
            public int compare(String s1, String s2) {
                return (s2 + s1).compareTo(s1 + s2);
            }
            });
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < strs.length; i++) {
            sb.append(strs[i]);
        }
        String result = sb.toString();
        if (result.charAt(0) == "0") return "0";
        return result;
    }
}

subsequence

public int findPalindromeSubsequence(int[] A) {
    if (A == null || A.length == 0) return 0;
    int n = A.length;
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int i = 2; i < n; i++) {
        for (int j = 0; j <= n-i; j++) {
            int k = j+i-1;
            if(A[k] == A[j] && i == 2) dp[j][k] = 2;
            else if (A[k] == A[j]) dp[j][k] = dp[j+1][k-1]+2;
            else dp[j][k] = Math.max(dp[j+1][k], dp[j][k-1]);
        }
    }
    return dp[0][n-1];
}

any order to form

public int longestPalindrome(String s) {
        if(s==null || s.length()==0) return 0;
        HashSet hs = new HashSet();
        int count = 0;
        for(int i=0; i
Longest Common Subarray
public int longestCommonSubarray(int[] A, int[] B) {
    if (A == null || B == null || A.length == 0 || B.length == 0) return 0;
    int m = A.length, n = B.length;
    int max = 0;
    int[][] dp = new int[m+1][n+1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (A[i] == B[j]) dp[i][j] = dp[i-1][j-1]+1;
            max = Math.max(max, dp[i][j]);
        }
    }
    return max;
}
Longest Common Subsequence
public class Solution {
    public int longestCommonSubsequence(String A, String B) {
        int m = A.length(), n = B.length(), max = 0;
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (A.charAt(i-1) == B.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = Math.max(Math.max(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]);
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }
}
longest common prefix
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        if (strs.length == 1) return strs[0];
        StringBuilder sb = new StringBuilder();
        String temp = strs[0];
        for (String str: strs) {
            int i = 0;
            while (i < temp.length() && i < str.length() && temp.charAt(i) == str.charAt(i)) {
                i++;
            }
            if (i == 0) return "";
            else temp = temp.substring(0, i);
        }
        return temp;
    }
Max Sliding Window
Sliding Window Maximum
public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];
        int[] left = new int[nums.length];
        int[] right = new int[nums.length];
        left[0] = nums[0];
        right[nums.length-1] = nums[nums.length-1];
        for (int i = 1; i < nums.length; i++) {
            left[i] = i%k == 0 ? nums[i] : Math.max(left[i-1], nums[i]);
            int j = nums.length-1-i;
            right[j] = j%k == 0 ? nums[j] : Math.max(right[j+1], nums[j]);
        }
        int[] max = new int[nums.length-k+1];
        int index = 0;
        for (int i = 0; i < max.length; i++) {
            max[index++] = Math.max(right[i], left[i+k-1]); 
        }
        return max;
    }
}
Move 0"s to the end
public void moveToEnd(int[] nums) {
    if (nums == null || nums.length == 0) return;
    int i = 0, j = 0;
    while (j < nums.length) {
        if (nums[j] != 0) {
            nums[i] = nums[j];
            i++; j++;
        } 
        else j++;
    }
    while (i < nums.length) nums[i++] = 0;
}
Permutations
I. Unique
public class Solution {
    public List> permute(int[] nums) {
        List> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        helper(nums, new ArrayList(), res);
        return res;
    }
    public void helper(int[] nums, List cur, List> res) {
        if (cur.size() == nums.length) res.add(new ArrayList(cur));
        else for (int i = 0; i < nums.length; i++) {
            if (cur.contains(nums[i])) continue;
            cur.add(nums[i]);
            helper(nums, cur, res);
            cur.remove(cur.size()-1);
        }
    }
}
II. Duplicate
public class Solution {
    public List> permuteUnique(int[] nums) {
        List> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        Arrays.sort(nums);
        helper(nums, new ArrayList(), res, new boolean[nums.length]);
        return res;
    }
    public void helper(int[] nums, List cur, List> res, boolean[] used) {
        if (cur.size() == nums.length) {
            res.add(new ArrayList (cur));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || (i != 0 && nums[i] == nums[i-1] && !used[i-1])) continue;
            else {    
                used[i] = true;
                cur.add(nums[i]);
                helper(nums, cur, res, used);
                used[i] = false;
                cur.remove(cur.size()-1);
            }
        }
    }
}
Rearrange Words —— Next Permutation of char[]
    static String rearrangeWord(String word) {
        char[] ch = word.toCharArray();
        if (ch.length <= 1) return "no answer";
        int n = ch.length;
        StringBuilder sb = new StringBuilder();
        int i = n-1;
        for (; i >= 1; i--) {
            if (ch[i]-"a" > ch[i-1]-"a") break;
        }
        if (i == 0) return "no answer";
        else swap(ch, i-1);
        reverse(ch, i);
        for (i = 0; i < n; i++) sb.append(ch[i]);
        String res = sb.toString();
        if (res.equals(word)) return "no answer";
        else return res;
    }
static void swap(char[] ch, int i) {
    for(int k = ch.length-1; k > i; k--) {
        if (ch[k]-"a" > ch[i]-"a") {
            char temp = ch[k];
            ch[k] = ch[i];
            ch[i] = temp;
            break;
        }
    }
}
static void reverse(char[] ch, int i) {
    int start = i, end = ch.length-1;
    while (start < end) {
        char temp = ch[start];
        ch[start] = ch[end];
        ch[end] = temp;
        start++;
        end--;
    }
}
Number of Islands
public class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == "1") {
                    count++;
                    mark(grid, i, j);
                }
            }
        }
        return count;
    }
    public void mark(char[][] grid, int i, int j) {
        if (grid[i][j] == "1" && i >= 0 && i < grid.length && j >= 0 && j < grid[0].length) {
            grid[i][j] = "0";
            if (i-1 >= 0) mark(grid, i-1, j);
            if (i+1 < grid.length) mark(grid, i+1, j);
            if (j-1 >= 0) mark(grid, i, j-1);
            if (j+1 < grid[0].length) mark(grid, i, j+1);
        }
    }
}
N-Queens
https://segmentfault.com/a/11...
Random Range Expansion
Given function to generate number from 1 to 5, make it generate number from 1 to 7;
random() --> 1, 2, 3, 4, 5
12345
67123
45671
23456
70000
Use random() twice to get the index i, j, ignore the last four 0"s.
Java基础知识点
Variable Storage Classes
•    Local Variable: they are inside methods, blocks or constructors.
•    Instance Variable: they are within a class but outside the methods. They are instantiated when the class is loaded.
•    Class Variable: they are declared with keyword static, inside a class but outside the methods.
OOP Concepts
•    Inheritance: subclasses can inherit properties from superclasses.
•    Overloading / Overriding: subclasses can determine what method of superclass is to be used at compile-time / subclasses can override the existing method of superclass at run-time.
•    Polymorphism: Polymorphism is the ability of an object to take on many forms and do different things. For example:
public class sedan extends automobile implements car {
sedan camry = new sedan();
}
Therefore, camry is a car, is an automobile, is a sedan, is an Object. As it has multiple inheritances, camry is polymorphic.
Polymorphism in Java has two types: 
Compile time polymorphism (static binding) and Runtime polymorphism (dynamic binding). Method overloading is an example of static polymorphism, while method overriding is an example of dynamic polymorphism.
•    Abstraction: it means hiding the implementation details from the user. Abstract class helps to reduce complexity and improves maintainability and reusability of the system. The implementation of abstract class is determined by its child classes.
•    Encapsulation: it means hiding the implementation details from users by wrapping the variables and code together as a single unit, known as data hiding, can be accessed only through their current class. You can declare fields private, and provide the access to the fields via public methods within the class.
Access Modifiers
Access Modifiers are used to set access level for classes, variables, methods and constructors.
protected
Variables, methods or constructors which are declared protected, can be accessed only by its subclasses(in this package or other package) or package member.
synchronized
The modifier synchronized indicates that the method can be accessed by only one thread at a time.
class Package Subclass World
public 4
protected 3
no modifier 2
private 1
Generics
Overloading vs. Overriding
Overriding means having two methods with the same method name and parameters (i.e., method signature). Overriding allows a child class to provide a specific implementation of a method provided by its parent class.
The real object type in the run-time, not the reference variable"s type, determines which overridden method is used at runtime. 
Overloading means a class has multiple functions with same name but different parameters. Reference type determines which overloaded method will be used at compile time. 
Notice:
Polymorphism applies to overriding, not to overloading.
Overriding is a run-time concept while overloading is a compile-time concept.
Exceptions
Exception - Unchecked Exception:

Unchecked exception are the ones not checked at compile time, so it’s not forced by the compiler to either handle or specify these exceptions.

Unchecked exception inherits from RuntimeException.

Runtime exception can be avoided by the programmer and can be ignored during compilation, you will need to extend the RuntimeException class if you want to write a runtime exception.


Exception - Checked Exception (compile-time exception):

Checked Exception is a problem that cannot be foreseen by the programmer, they are checked at compile time.

The method has to handle the checked exceptions either in try-catch clause or it must specify the exception using throws keyword.

A Checked Exception thrown by subclass enforces a contract on the superclass to catch or throw it.

You will need to extend the Exception class if you want to write a Checked Exception. In Java, everything under throwable is checked.


final vs. finalize() vs. finally
Final is a keyword, final is used to apply restrictions on class, method and variable. Final class can"t be inherited, final method can"t be overridden and final variable value can"t be changed. 
Finally is a block, finally is used to place important code, it will be executed whether exception is handled or not. 
Finalize is a method, finalize is used to perform clean up processing just before object is garbage collected.
Garbage Collection
o    It makes java memory efficient because garbage collector removes the unreferenced objects from heap memory.
o    It is automatically done by the garbage collector (a part of JVM) so we don"t need to make extra efforts.
RESTful API
Representational State Transfer
We can call it a resource-based, client-server structured, stateless and cacheable architecture, or protocol, in web development. Basically, client just need to make HTTP requests to call REST services via a uniform interface.
Singleton
Normally like this:
public Class Singleton {
    private static Singleton instance = null;
    protected Singleton() {}
    public static synchronized Singleton getInstance() {
        if (instance == null) {
            instance = new Singleton();
        }
        return instance;
    }
}
OR
public class Singleton {
    private static final Singleton instance = new Singleton();
    protected Singleton() {}
    public static Singleton getInstance() {
        return instance;
    }
}
OR double-checked locking solution
public class Singleton {
    private static final Singleton instance;
    protected Singleton() {}
    public static Singleton getInstance() {
        if (instance == null) {
            synchronized(Singleton.class) {
                if (instance == null) instance = new Singleton();
            }
        }
        return instance;
    }
}
数据结构
Stack vs. Heap
Stack memory is used to store local variables and function call;
Heap memory is used to store objects in Java.
Map
HashMap

HashMap maintains key-value pairs mapping and implements Map Interface.

HashMap methods are unsynchronized, unlike HashTable.

HashMap methods allow null key and null value, unlike HashTable.

HashMap allows one null key and any number of null value.

HashMap doesn’t maintain any order for the key-value pairs.

Insert and search runtime complexity: O(1).

Based on hashCode(), equals() implementations.

To synchronize it: Map m = Collections.synchronizedMap(new HashMap<>(…));

Implemented by an array of buckets, each bucket is a LinkedList of entries.


How to sort HashMap:
    Map map = new HashMap<>();
    Set set = map.entrySet();
    Iterator iterator = set.iterator();
    While (iterator.hasNext()) {
        Map.Entry m = (Map.Entry) iterator.next();
        System.out.println(m.getKey() + “: “ + m.getValue());
    }

    //After sorted
    
    Map tm = new TreeMap<> (map);
    Set set2 = tm.entrySet();
    Iterator iterator 2 = set2.iterator();
    While (iterator2.hasNext()) {
        Map.Entry m2 = (Map.Entry) iterator2.next();
        System.out.println(m2.getKey() + “: “ + m2.getValue());
    }
TreeMap
TreeMap底层通过Red-Black Tree实现，是非同步unsynchronized的，如果需要在多线程环境使用，需要wrap包装为synchronized:
SortedMap map = Collections.sysnchronizedSortedMap(new TreeMap(…));

TreeMap is sorted by keys, provide the feature of ordered iteration.

Insert and search time complexity: O(logN).

Implemented by a red-black tree.

higherKey(), lowerKey() methods can be used to get the predecessor and successor of a given key.

Member of Java Collection Framework.

TreeMap doesn’t allow null key or null values.

More functionalities: pollFirstEntry(), pollLastEntry(), tailMap(), firstKey(), lastKey()…

Implement NavigableMap Interface.


List
ArrayList vs. LinkedList
ArrayList 
Random Access.
Only objects can be added;
Remove() will shift all elements after the removed one to fill in the space created;
Less memory used.
Get(): O(1)
Add()/Remove(): O(n)
Search: O(n)
Search by position: O(1)
linkedList
Sequential Access.
ListNode contains prev/next node link and its own value;
Remove() is faster since only two neighbor nodes pointers are changed;
More memory consumption.
Get(): O(n)
Add()/Remove(): O(1) at end, O(n) insert
Search: O(n)
Search by position: O(1)
Sort
**Merge sort
public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        // Write your code here
        if (A.length <= 1) return;
        int[] B = new int[A.length];
        sort(A, 0, A.length-1, B);
    }
    void sort(int[] A, int start, int end, int[] B) {
        if (start >= end) return;
        int mid = start+(end-start)/2;
        sort(A, start, mid, B);
        sort(A, mid+1, end, B);
        merge(A, start, mid, end, B);
    }
    void merge(int[] A, int start, int mid, int end, int[] B) {
        int i = start, j = mid+1, index = start;
        while (i <= mid && j <= end) {
            if (A[i] < A[j]) B[index++] = A[i++];
            else B[index++] = A[j++];
        }
        while (j <= end) B[index++] = A[j++];
        while (i <= mid) B[index++] = A[i++];

        for (int k = start; k <= end; k++) A[k] = B[k];
    }
}
Quick sort
public class Solution {
    public void sortIntegers2(int[] A) {
        if (A.length <= 1) return;
        quicksort(A, 0, A.length-1);
    }
    public void quicksort(int[] A, int start, int end) {
        if (start >= end) return;
        int i = start, j = end;
        int pivot = A[start+(end-start)/2];
        while (i <= j) {
            while (i <= j && A[i] < pivot) i++;
            while (i <= j && A[j] > pivot) j--;
            if (i <= j) {
                int temp = A[i];
                A[i] = A[j];
                A[j] = temp;
                i++;
                j--;
            }
        }
        quicksort(A, start, j);
        quicksort(A, i, end);
    }
}
Heap Sort
public class Solution {
    public void sortIntegers2(int[] A) {
        buildheap(A);
        int n = A.length-1;
        for(int i = n; i > 0; i--){
            exchange(A, 0, i);
            n = n-1;
            maxheap(A, 0, n);
        }
    }
    public static void buildheap(int[] a){
        int n = a.length-1;
        for(int i = n/2; i>=0; i--){
            maxheap(a, i, n);
        }
    }
public static void maxheap(int[] a, int i, int n){ 
    int left = 2*i;
    int right = 2*i+1;
    int max = 0;
    if(left <= n && a[left] > a[i]) max = left;
    else max = i;
    if(right <= n && a[right] > a[max]) max = right;
    if(max != i){
        exchange(a, i, max);
        maxheap(a, max, n);
    }
}
public static void exchange(int[] a, int i, int j){
    int t = a[i];
    a[i] = a[j];
    a[j] = t; 
}
}
多线程、并发
表现问题
Why yabe?