<repo_name>lizongkai-big/LeetCode<file_sep>/src/TAG/LinkedList/LRU.java
package TAG.LinkedList;

import java.util.HashMap;

/**
 * 双向链表
 */
class DLinkedNode {
    public int val;
    // 用于hash表查找、删除
    public String key;
    public DLinkedNode pre, post;

    public DLinkedNode(int v) {
        val = v;
        key = "";
        pre = null;
        post = null;
    }
}

/**
 * 使用hash表 + 双向链表模拟实现的LRU，使得放入和移除都是 O(1)，
 * 参考：https://blog.csdn.net/hopeztm/article/details/79547052
 * hash表：保证查找的时间复杂度是O(1)
 * 链表：保证删除、插入的时间复杂度是O(1)
 * 双向：方便删除节点之后链表的恢复
 *
 * 缺点：如果LRU链表本身很短，双向链表的双指针会显得浪费空间
 */
public class LRU {
    private HashMap<String, DLinkedNode>
            cache;
    private int count;
    private int capacity;
    private DLinkedNode head, tail;

    public LRU(int capacity) {
        this.count = 0;
        this.capacity = capacity;
        this.cache = new HashMap<>();

        head = new DLinkedNode(-1);
        tail = new DLinkedNode(-1);
        head.pre = null;
        head.post = tail;
        tail.pre = head;
        tail.post = null;
    }

    public int get(int value) {
        DLinkedNode node = cache.get(value + "");
        if (node == null) {
            return -1; // should raise exception here.
        }
        // move the accessed node to the head;
        this.moveToHead(node);
        return node.val;
    }

    public void set(int value) {
        DLinkedNode node = cache.get(value + "");

        if (node == null) {
            DLinkedNode newNode = new DLinkedNode(value);
            newNode.key = value + "";
            this.cache.put(value + "", newNode);
            this.insertHead(newNode);
            ++count;
            if (count > capacity) {
                // pop the tail
                DLinkedNode tail = this.popTail();
                this.cache.remove(tail.key);
                --count;
            }
        } else {
            this.moveToHead(node);
        }
    }

    /**
     * 双向链表中插入表头
     *
     * @param node
     */
    private void insertHead(DLinkedNode node) {
        DLinkedNode next = head.post;
        head.post = node;
        node.pre = head;
        node.post = next;
        next.pre = node;
    }

    /**
     * 双向链表中删除节点
     *
     * @param node
     */
    private void removeNode(DLinkedNode node) {
        DLinkedNode pre = node.pre;
        DLinkedNode post = node.post;
        pre.post = post;
        post.pre = pre;
        node.post = null;
        node.pre = null;
    }

    /**
     * 将某个节点移动到双向链表表头
     *
     * @param node
     */
    private void moveToHead(DLinkedNode node) {
        this.removeNode(node);
        this.insertHead(node);
    }

    /**
     * 删除表尾
     *
     * @return
     */
    private DLinkedNode popTail() {
        DLinkedNode pre = tail.pre;
        this.removeNode(pre);
        return pre;
    }

    public DLinkedNode getTail() {
        return tail;
    }

    public DLinkedNode getHead() {
        return head;
    }

    public void print() {
        DLinkedNode tmp = head.post;
        while (tmp != null && tmp != tail) {
            System.out.printf(tmp.val + " ");
            tmp = tmp.post;
        }
        System.out.println();
    }

    public void printRvsOrder() {
        DLinkedNode tmp = tail.pre;
        while (tmp != null && tmp != head) {
            System.out.printf(tmp.val + " ");
            tmp = tmp.pre;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LRU lru = new LRU(4);
        for (int i = 0; i < 200; i++) {
            int rand = (int) (Math.random() * 10);
            System.out.print("set: " + rand + "\n");
            lru.set(rand);
            lru.print();
            rand = (int) (Math.random() * 10);
            System.out.print("get: " + rand + "\n");
            int find = lru.get(rand);
            System.out.println(find);
            if(find != -1)
                lru.print();
        }
    }
}
<file_sep>/src/Ordered/_24__Swap_Nodes_in_Pairs.java
package Ordered;

import utils.ListNode;

public class _24__Swap_Nodes_in_Pairs {
    public ListNode swapPairs_Iteration_Mine01(ListNode head) {
        if(head == null)
            return null;
        // dummy 节点
        ListNode res = new ListNode(0);
        res.next = head;
        ListNode slow = head;
        ListNode fast = head.next;
        ListNode front = res;
        while(fast != null) {
            slow.next = fast.next;
            fast.next = slow;
            front.next = fast;

            front = slow;
            if(slow.next != null && slow.next.next != null) {
                fast = slow.next.next;
                slow = slow.next;
            }
            else{
                slow = null;
                fast = null;
            }
        }
        return res.next;
    }

    public ListNode swapPairs_Iteration_Others(ListNode head) {
        // 对于空链表或只有一个节点的链表，无需swap
        if(head == null || head.next == null)
            return head;
        // dummy Node
        ListNode res = new ListNode(0);
        res.next = head;
        // 要有前节点
        ListNode front = res;
        // 如果链表的剩余部分为空或只有一个节点，无需swap
        while(front.next != null && front.next.next != null) {
            // 草纸上模拟下就晓得了
            ListNode slow = front.next;
            ListNode fast = front.next.next;

            slow.next = fast.next;
            fast.next = slow;
            front.next = fast;

            front = slow;
        }
        return res.next;
    }

    public ListNode swapPairs_Iteration(ListNode head) {
        // 对于空链表和只有一个节点的链表，不做交换直接返回
        if(head == null || head.next == null)
            return head;
        // n 表示第二个节点
        ListNode n = head.next;
        // 交换前两个节点，现在的头结点就成了n
        n.next = head;
        // 把第二个节点之后的链表当成一个新的链表
        head.next = swapPairs_Iteration(head.next.next);
        return n;
    }
}
<file_sep>/src/TAG/LinkedList/_234__Palindrome_Linked_List.java
package TAG.LinkedList;

import utils.ListNode;

/**
 * 判断一个单链表是否为回文的
 */
public class _234__Palindrome_Linked_List {
    /**
     * https://github.com/andavid/leetcode-java/blob/master/note/234/README.md
     * 利用快慢指针，让slow指向链表的中点，并倒置前半个链表，最后比较中点两侧的链表是否相等
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        // zero node or only one node
        if(head == null || head.next == null) return true;
        ListNode pre = null; // pre初始化不能是head，不然在倒置时会有head.next = pre(head)，而head.next本身指向head，形成一个循环！
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            // 倒置结点，需要一个临时结点，仅靠slow，fast不能实现倒置
            ListNode tmp = slow;
            /*-------slow和fast的向后移动，要在倒置结点之前----------*/
            slow = slow.next;
            fast = fast.next.next;

            tmp.next = pre;
            pre = tmp;
        }
        /*让slow指向链表的后半部分的开始*/
        /**设链表长度为len, 因为fast走了奇数（1+2*x）步，slow走了1+x步。
         * 如果链表长度是偶数，则循环的跳出条件是fast==null，fast.next!==null，
         * 此时fast走了len+1步，根据len+1=1+2*x，slow走了len/2+1步，已经指向链表的后一半的第一个元素；
         * 如果链表长度为奇数，循环跳出条件为fast.next==null，fast!=null，
         * 此时fast走了len步，根据len+1=1+2*x，此时slow走了(len-1)/2+1，也就是(len+1)/2步，正指向链表的中间元素，
         * 所以要后移一位
         * */
        if(fast != null)
            slow = slow.next;
        while(slow != null) {
            if(slow.val != pre.val) {
                return false;
            }
            slow = slow.next;
            pre = pre.next;
        }
        // 恢复现场
        return true;
    }

    public void two_points_practice(ListNode head) {
        if(head == null || head.next == null) return;
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if(fast != null)
            slow = slow.next;
    }
}
<file_sep>/src/TAG/StringMatching/Trie.java
package TAG.StringMatching;

class TrieNode {
    char c;
    final int SIZE = 26;
    TrieNode[] children = new TrieNode[SIZE];
    boolean isEndingChar = false;

    public TrieNode(char c) {
        this.c = c;
    }
}

public class Trie {
    private TrieNode root = new TrieNode('/');

    public void insert(char[] text) {
        TrieNode node = root;
        for(char c: text) {
            int inx = c - 'a';
            if(node.children[inx] == null) {
                node.children[inx] = new TrieNode(c);
            }
            node = node.children[inx];
        }
        node.isEndingChar = true;
    }

    public boolean find(char[] pattern) {
        TrieNode node = root;
        for (char c: pattern) {
            int inx = c - 'a';
            if(node.children[inx] == null)
                return false;
            node = node.children[inx];
        }
        return node.isEndingChar;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        char[][] words = new char[][]{{'h','e','l','l','o'}, {'e','e','l','l','o'},
                {'h','e','l','o','o'}, {'h','e','l','l','e'}, };
        System.out.println("对空的Trie树进行查找------------------");
        for(char[] w: words) {
            System.out.println(trie.find(w));
        }
        System.out.println("先插入，再查找------------------");
        for(char[] w: words) {
            trie.insert(w);
        }
        for(char[] w: words) {
            System.out.println(trie.find(w));
        }
        System.out.println("再插入，再查找------------------");
        for(char[] w: words) {
            trie.insert(w);
        }
        for(char[] w: words) {
            System.out.println(trie.find(w));
        }
        System.out.println("查找一个不存在的字符串------------------");
        System.out.println(trie.find(new char[]{'l', 'o', 'o'}));

    }
}
<file_sep>/src/TAG/DP/Longest_Common_Subsequence.java
package TAG.DP;

import java.util.Arrays;

// 最长公共子序列

/**
 *              0                   i = 0 || j == 0
 * LCS[i, j] =  LCS[i-1, j-1] + 1   i,j > 0 && Xi == Yj
 *              Max{LCS[i-1,j],     i,j > 0 && Xi != Yj
 *              LCS[i,j-1]}
 */
public class Longest_Common_Subsequence {
    public String lcs(String s, String t) {
        int m = s.length();
        int n = t.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        // return dp[m][n];
        StringBuilder sb = new StringBuilder();
        for (int i = m, j = n; i >= 1 && j >= 1;) {
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                sb.append(s.charAt(i - 1));
                j --;
                i --;
            } else {
                if (dp[i][j - 1] >= dp[i - 1][j]) {
                    sb.append(s.charAt(j - 1));
                    j --;
                } else {
                    sb.append(s.charAt(i - 1));
                    i --;
                }
            }
        }
        return sb.reverse().toString();
    }

    public static void main(String[] args) {
        Longest_Common_Subsequence longest_common_subsequence = new Longest_Common_Subsequence();
        String s = "abababa";
        System.out.println(longest_common_subsequence.lcs(s, s));
    }
}
<file_sep>/src/Ordered/_30__Substring_with_Concatenation_of_All_Words.java
package Ordered;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * 如果是把words重新组合，则没有考虑到words中字符串都是相同长度的条件
 * 感觉这道题比较没营养，可以学到map 的使用、越界的判断、break的条件
 */
public class _30__Substring_with_Concatenation_of_All_Words {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new LinkedList<>();
        int wordNum = words.length;
        int slen = s.length();
        if(slen == 0 || wordNum == 0)
            return res;
        int wordLen = words[0].length();
        Map<String ,Integer> wordMap = new HashMap<>();
        for (int i = 0; i < wordNum; i++) {
            if(words[i].length() != wordLen) {
                return res;
            }
            wordMap.put(words[i], wordMap.getOrDefault(words[i], 0) + 1);
        }
        for (int i = 0; i < slen - wordLen * wordNum + 1; i++) {
            Map<String, Integer> tmpMap = new HashMap<>();
            int j = 0;
            for (; j < wordNum; j++) {
                String tmp = s.substring(i + j * wordLen, i + (j+1) * wordLen);
                if(!wordMap.containsKey(tmp)) {
                    break;
                }
                tmpMap.put(tmp, tmpMap.getOrDefault(tmp, 0) + 1);
                if(tmpMap.get(tmp) > wordMap.get(tmp)) {
                    break;
                }
            }
            if(j == wordNum) {
                res.add(i);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        _30__Substring_with_Concatenation_of_All_Words substringWithConcatenationOfAllWords = new _30__Substring_with_Concatenation_of_All_Words();
        String s = "barfoothefoobarman";
        String[] words = {"foo","bar"};
        System.out.println(substringWithConcatenationOfAllWords.findSubstring(s, words));
    }
}
<file_sep>/src/TAG/BackTracking/_46__Permutations.java
package TAG.BackTracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _46__Permutations {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        backtrack(res, new ArrayList<Integer>(), nums);
        return res;
    }

    public void backtrack(List<List<Integer>> res, List<Integer> tmpList, int[] nums) {
        if (tmpList.size() == nums.length) {
            res.add(new ArrayList<>(tmpList));
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (tmpList.contains(nums[i])) continue;
                tmpList.add(nums[i]);
                backtrack(res, tmpList, nums);
                tmpList.remove(tmpList.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        _46__Permutations permutations = new _46__Permutations();
        List<List<Integer>> lists = (permutations.permute(new int[]{1, 2, 3, 4, 7}));
        for (List<Integer> list : lists)
            System.out.println(list);
    }
}
<file_sep>/src/TAG/DP/_91__Decode_Ways.java
package TAG.DP;

public class _91__Decode_Ways {
    public static void main(String[] args) {


    }
}
<file_sep>/src/TAG/String/DelContinuouslyChar.java
package TAG.String;


import java.util.Stack;

// #stack
public class DelContinuouslyChar {
    // 删除str中连续的字符 如AAABA->BA，返回字符串最终的长度
    public int del_Recur(String str) {
        int len = str.length();
        int lent;
        if (len == 0) return 0;
        StringBuilder stringBuilder = new StringBuilder();
        str += "#";
        int l = 0;
        for (int i = 1; i <= len; i++) {
            if (str.charAt(i) != str.charAt(i - 1)) {
                if (l == i - 1)
                    stringBuilder.append(str.charAt(i - 1));
                l = i;
            }
        }
        if ((lent = stringBuilder.length()) == len) return 0;
        return len - lent + del_Recur(stringBuilder.toString());
    }

    public int del_Iter(String str) {
        int len = str.length();
        if (len == 0) return 0;
        Stack<Character> stack = new Stack<>();
        int i = 0;
        while (i < len) {
            if (stack.isEmpty()) {
                stack.push(str.charAt(i));
                i++;
                continue;
            }
            while (!stack.isEmpty() && i < len) {
                char c = str.charAt(i);
                char peek = stack.peek();
                if (peek == c) {
                    stack.pop();
                    i++;
                } else {
                    stack.push(c);
                    i++;
                    break;
                }
            }
        }
        return stack.size();
    }

    public int del_Iter_optimize(String str) {
        int len = str.length();
        if (len == 0) return 0;
        Stack<Character> stack = new Stack<>();
        int i = 0;
        while (i < len) {
            // 栈不空 && 字符串下标不越界 && 满足一定条件
            while (!stack.isEmpty() && i < len && str.charAt(i) == stack.peek()) {
                stack.pop();
                i++;
            }
            stack.push(str.charAt(i));
            i++;
        }
        return stack.size();
    }

}
<file_sep>/src/Ordered/_59__Spiral_Matrix_II.java
package Ordered;

public class _59__Spiral_Matrix_II {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int top = 0, bottom = n-1, left = 0, right = n-1;
        for (int i = 1; i <= n*n; ) {
            for (int j = left; j <= right; j++) {
                res[top][j] = i;
                i ++;
            }
            top ++;
            for (int j = top; j <= bottom; j++) {
                res[j][right] = i;
                i ++;
            }
            right --;
            for (int j = right; j >= left; j--) {
                res[bottom][j] = i;
                i ++;
            }
            bottom --;
            for (int j = bottom; j >= top; j--) {
                res[j][left] = i;
                i ++;
            }
            left ++;
        }
        return res;
    }
}
<file_sep>/src/TAG/Brainteaser/WhenOneMeetZero.java
package TAG.Brainteaser;

import java.util.Scanner;
import java.util.Stack;

/**
 * 给定一个字符串，字符串中1,0相遇会互相抵消，抵消之后的字符串长度
 * 如10101 --> 1 长度为1
 * 0000 --》 0000 长度为4
 * 1010 --》 "" 长度为0
 */
public class WhenOneMeetZero {
    public static int solveWithStack(int m, String str) {
        Stack<Character> stack = new Stack<>();
        int i = 0;
        while (i < m) {
            if(stack.isEmpty()) {
                stack.push(str.charAt(i));
                i++;
                continue;
            }
            while (!stack.isEmpty() && i < m) {
                char c = str.charAt(i);
                char top = stack.peek();
                if(top == '0' && c == '1' ||
                        top == '1' && c == '0') {
                    stack.pop();
                    i ++;
                }
                else {
                    stack.push(str.charAt(i));
                    i ++;
                    break;
                }
            }
        }
        return stack.size();
    }

    public static int solveWithTrick(int m, String str) {
        int ones = 0;
        int zeros = 0;
        for (int i = 0; i < m; i++) {
            if(str.charAt(i) == '0') zeros ++;
            else if(str.charAt(i) == '1') ones ++;
        }
        return Math.abs(ones-zeros);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int m = Integer.parseInt(sc.nextLine());
            String str = sc.nextLine();
            System.out.println(solveWithStack(m, str) == solveWithTrick(m, str));
        }
    }
}
<file_sep>/src/Easy/_26__Remove_Duplicates_from_Sorted_Array.java
package Easy;

public class _26__Remove_Duplicates_from_Sorted_Array {
    /**
     * elegant, and a little
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if(len < 2)
            return len;
        int id = 1;
        for(int i = 1; i < len; i ++) {
            if(nums[i] != nums[i-1]) {
                nums[id++] = nums[i];
            }
        }
        return id;
    }

    public int strStr(String haystack, String needle) {
        int lenStack = haystack.length();
        int lenNeedle = needle.length();
        int res = -1;
        for (int i = 0; i < lenStack; i++) {
            int j = 0;
            for (; j < lenNeedle; j++) {
                if(!((i+j) < lenStack && haystack.charAt(i+j) == needle.charAt(j))) {
                    break;
                }
            }
            if(j == lenNeedle) {
                res = i;
                break;
            }
        }
        return res;
    }
}
<file_sep>/src/Ordered/_11__Container_With_Most_Water.java
package Ordered;

public class _11__Container_With_Most_Water {
    /**
     * https://leetcode.com/problems/container-with-most-water/discuss/6099/Yet-another-way-to-see-what-happens-in-the-O(n)-algorithm
     * 容器容积计算公式：Math.min(height[i], height[j]) * (j-i)
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        int len = height.length;
        int res = 0;
        // 两个指针，分别代表容器的两边；初始状态使底长最大
        int i=0, j = len-1;
        while(i < j) {
            // 高度 * 底长
            res = Math.max(res, Math.min(height[i], height[j]) * (j-i));
            // 为了Math.min(height[i], height[j])更大些，就让小的边寻求大些
            // 如果高度一致，就都向内靠拢咯
            if (height[i] == height[j]) {i++; j--;}
            else if (height[i] < height[j]) i ++;
            else j--;
        }
        return res;
    }
}
<file_sep>/src/Ordered/_41__First_Missing_Positive.java
class _41__First_Missing_Positive {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
		// first, put nums[i] into right place.
        for(int i = 0; i < nums.length; i++) {
			// nums[i]'s right place is in (0, n]
            while(nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i]) {
                // use temparory inx, because nums[i] will change, so nums[i]-1 also change.
				int inx = nums[i]-1;
                int t = nums[i];
                nums[i] = nums[inx];
                nums[inx] = t;
            }
        }
		// find the one not in right place.
        for(int i = 0; i < n; i++) {
            if(nums[i] != i+1) {
                return i+1;
            }
        }
        return n+1;
    }
}
<file_sep>/src/TAG/DP/_62__Unique_Paths.java
package TAG.DP;

import java.util.Arrays;

/**
 * 精进案例
 */
public class _62__Unique_Paths {
    public int uniquePaths_mine(int m, int n) {
        if(m == 0 || n == 0) return 0;
        int[][] pathNums = getPaths(m, n);
        return pathNums[m-1][n-1];
    }

    /**
     * 事实上，getPaths(m, n)计算pathNums时，只用到了上一行和本行的前一列，所以只需要两行就行了
     * O(2*min(m, n)) space complexity
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths_optimization_1(int m, int n) {
        /*好评，以前总想着要交换n, m*/
        if (m > n) return uniquePaths_optimization_1(n, m);
        int[] cur = new int[n];
        Arrays.fill(cur, 1);
        int[] pre = new int[n];
        Arrays.fill(pre, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                cur[j] = cur[j - 1] + pre[j];
            }
            // swap cur-pre
            pre = cur;
        }
        return cur[n-1];
    }

    /**
     * 两行，本质上就是一行嘛
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths_optimization_2(int m, int n) {
        if(m == 0 || n == 0) return 0;
        if (m > n) return uniquePaths_optimization_2(n, m);
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for(int i = 1; i < m; i ++) { // 从第二行开始
            for(int j = 1; j < n; j ++) {
                dp[j] += dp[j-1];
            }
        }
        return dp[n-1];
    }

    /**
     * 函数依据P[i][j] = P[i - 1][j] + P[i][j - 1]的特点，但是需要O(n^2)的空间
     * @param m
     * @param n
     * @return
     */
    public int[][] getPaths(int m, int n) {
        int[][] pathNums = new int[m][n];
        pathNums[0][0] = 1;
        for(int i = 0; i < m; i ++) {
            for(int j = 0; j < n; j ++) {
                if(i == 0 || j == 0) {
                    pathNums[i][j] = 1;
                }
                else {
                    pathNums[i][j] = pathNums[i][j-1] + pathNums[i-1][j];
                }
            }
        }
        return pathNums;
    }
}
<file_sep>/src/TAG/BinarySearch/_74__Search_a_2D_Matrix.java
package TAG.BinarySearch;

public class _74__Search_a_2D_Matrix {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
        int m = matrix.length, n = matrix[0].length;
        int lo = 0, hi = m-1;
        int row = 0, col = 0;
        // 最后一个小于等于target的元素
        while (lo <= hi) {
            int mid = lo + ((hi-lo) >> 1);
            if(matrix[mid][0] <= target) {
                if(matrix[mid][0] == target) return true;
                if(matrix[mid+1][0] > target) row = target;
                lo = mid + 1;
            }
            else {
                hi = mid - 1;
            }
        }
        lo = 0;
        hi = n - 1;
        while (lo < hi) {
            int mid = lo + ((hi-lo) >> 1);
            if(matrix[row][mid] <= target) {
                if(matrix[row][mid] == target) return true;
                if(matrix[row][mid] > target) ;
                lo = mid + 1;
            }
            else {
                hi = mid - 1;
            }
        }
        return false;
    }
}
<file_sep>/src/TAG/Tree/_101_Symmetric_Tree.java
package TAG.Tree;

import utils.TreeNode;

/**
 * Given a binary tree,
 * check whether it is a mirror of itself (ie, symmetric around its center).
 */
public class _101_Symmetric_Tree {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isSymmetricHelper(root.left, root.right);
    }

    public boolean isSymmetricHelper(TreeNode node1, TreeNode node2) {
        if(node1 == null || node2 == null) return node1 == node2;
        if(node1.val != node2.val) return false;
        return isSymmetricHelper(node1.left, node2.right) && isSymmetricHelper(node1.right, node2.left);
    }
}
<file_sep>/src/Ordered/_88__Merge_Sorted_Array.java
package Ordered;

public class _88__Merge_Sorted_Array {
    // 使用插入排序的思想，往已知有序的nums1中插入nums2中的数字；
    // 涉及到nums1中数字的后移，时间复杂度是O(mn)
    public void merge_Mine(int[] nums1, int m, int[] nums2, int n) {
        int i = 0, j = 0;
        for(; j < n && i < m;) {
            for(; i < m; i++) {
                if(nums1[i] > nums2[j]) {
                    for(int k = m-1; k >= i; k--)
                        nums1[k+1] = nums1[k];
                    nums1[i] = nums2[j];
                    m ++;
                    j++;
                    break;
                }
            }
        }
        while(j < n) {
            nums1[i ++] = nums2[j++];
        }
    }

    // 按顺序从后往前加入混合之后的数组末尾，时间复杂度是O(m+n)
    public void merge_optimization(int[] nums1, int m, int[] nums2, int n) {
        int length = m+n-1;
        m --;
        n --;
        while (m >= 0 && n >= 0) {
            if(nums1[m] > nums2[n]) {
                nums1[length --] = nums1[m--];
            }
            else {
                nums1[length --] = nums2[n--];
            }
        }
        while (n >= 0)
            nums1[length--] = nums2[n--];
    }
}
<file_sep>/src/TAG/Recrusion/_687__Longest_Univalue_Path.java
package TAG.Recrusion;

import utils.TreeNode;

public class _687__Longest_Univalue_Path {
    int max = 0;
    public int longestUnivaluePath(TreeNode root) {
        getPath(root);
        return max;
    }

    public int getPath(TreeNode root) {
        if(root == null || root.left == null && root.right == null) return 0;
        int left = getPath(root.left);
        int right = getPath(root.right);
        // 以当前节点为根的子树的longestUnivaluePath，Longest-Univalue-Path-Across - node
        int maxLength = 0;
        // 以当前节点为根的子树，单向最长路径，对父节点而言
        int pathLen = 0;

        if(root.left != null && root.val == root.left.val) {
            maxLength += (left+1);
            pathLen = left+1;
        }
        if(root.right != null && root.val == root.right.val) {
            maxLength += (right+1);
            if(right+1>pathLen)
                pathLen = right + 1;
        }
        if(maxLength > max) max = maxLength;

        return pathLen;
    }
}
<file_sep>/src/Ordered/_6__ZigZag_Conversion.java
package Ordered;

public class _6__ZigZag_Conversion {
    /**
     * 硬扛的裱糊匠！啰嗦、不够优雅
     * @param s
     * @param numRows
     * @return
     */
    public String convert_stupid(String s, int numRows) {
        int diff = numRows + numRows - 2;
        // i: row num
        // diff: 两个元素的下标的差值
        int len = s.length();
        if(numRows <= 1 || len <= 1) {
            return s;
        }
        char[] res = new char[len];
        // point to res's subscript
        int point = 0;
        // 第一行
        for(int i = 0, j = diff; i < len; i += diff) {
            res[point ++] = s.charAt(i);
        }
        // 第二行至倒数第二行
        for(int i = 1, j = diff; i < numRows-1; i++, j -= 2) {
            if(i < len)
                res[point ++] = s.charAt(i);
            int firstDiff = j - 2;
            int secondDiff = diff - firstDiff;
            while(i + firstDiff < len) {
                res[point ++] = s.charAt(i + firstDiff);
                i += firstDiff;
                if(numRows != 3 && i + secondDiff < len){
                    res[point ++] = s.charAt(i + secondDiff);
                }
                if(numRows != 3) {
                    i += secondDiff;
                }
            }
        }
        // 最后一行
        for(int i = numRows - 1, j = diff; i < len; i += diff) {
            res[point ++] = s.charAt(i);
        }
        return new String(res);
    }

    /**
     * elegant approach
     * 另一个角度看待 zigzag pattern
     * @param s
     * @param numRows
     * @return
     */
    public String convert_elegant(String s, int numRows) {
        if(numRows == 1)
            return s;
        int len = s.length();
        StringBuilder[] res = new StringBuilder[numRows];
        for(int i = 0; i < numRows; i ++) {
            /*init every res element **important step!!!!*/
            // if not, res[i] is null
            res[i] = new StringBuilder();
        }
        int direction = 1;
        int inx = 0;
        for(int i = 0; i < len; i ++) {
            res[inx].append(s.charAt(i));
            // change the direction **important step!!!!
            if(inx == 0) direction = 1;
            if(inx == numRows - 1) direction = -1;
            inx += direction;
            // attention to outOfBounds, new test cases
            if(inx >= numRows) inx = numRows-1;
            if(inx < 0) inx = 0;
        }
        for(int i = 1; i < numRows; i ++) {
            res[0].append(res[i]);
        }
        return res[0].toString();
    }

    public static void main(String[] args) {
        _6__ZigZag_Conversion zigZagConversion = new _6__ZigZag_Conversion();

        System.out.println(zigZagConversion.convert_stupid("PAYPALISHIRING", 4));
    }
}
<file_sep>/src/TAG/Brainteaser/_319__Bulb_Switcher.java
package TAG.Brainteaser;

/**
 * 2015盏灯，一开始全部熄灭，序号分别是1-2015，先把1的倍数序号的灯的开关全部按一次，然后把2的倍数的灯的开关全部按一次，
 * 然后把3的倍数的开关按一次，以此类推，最后把2015的倍数灯的开关按一次。问最后亮着的灯有多少盏？
 *
 * 最后亮着的灯都被按了奇数次，也就是那些约数个数是奇数个的灯，约数有奇数个的数都是完全平方数（整数自乘）
 * 证明，假设一个数m有奇数个约数，其中一个约数是n，则有另一个约数为m/n，如果n!=m/n则它的约数是以n, m/n成对出现的，
 * 应该有偶数个约数，不符合！所以n==m/n，则该数为n^2，即为完全平方数
 *
 * 一个数中完全平方数的个数为sqrt(n)向下取整。如44^2<2015<45^2，所以2015中有44个完全平方数（1,2,3...44）
 */
public class _319__Bulb_Switcher {
    public int bulbSwitch(int n) {
        return (int)Math.sqrt(n);
    }
}
<file_sep>/src/Ordered/_56__Merge_Intervals.java
package Ordered;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class _56__Merge_Intervals {
    public class Interval {
        int start;
        int end;
        Interval() { start = 0; end = 0; }
        Interval(int s, int e) { start = s; end = e; }
    }

    /**
     * 不算优点的优点：在原有的ArrayList中做处理
     * 缺点：List.remove(int index); 涉及大量的数组复制操作，效率很低；不如直接新建一个List
     * @param intervals
     * @return
     */
    public List<Interval> merge_mine(List<Interval> intervals) {
        bubbleSort(intervals);
        int inx = 0;
        for(int i = 1; i < intervals.size();) {
            if(intervals.get(inx).start == intervals.get(i).start ||
                    intervals.get(inx).start < intervals.get(i).start && intervals.get(inx).end >= intervals.get(i).start ||
                    intervals.get(inx).start > intervals.get(i).start && intervals.get(i).end >= intervals.get(inx).start
                    ) {
                intervals.get(inx).start = Math.min(intervals.get(inx).start, intervals.get(i).start);
                intervals.get(inx).end = Math.max(intervals.get(inx).end, intervals.get(i).end);
                intervals.remove(i);
            }
            else {
                i++;
                inx ++;
            }
        }
        return intervals;
    }



    public List<Interval> merge_optimization1(List<Interval> intervals) {
        List<Interval> list=new ArrayList<>();

        int []start=new int[intervals.size()];
        int []end=new int[intervals.size()];

        for(int i=0;i<intervals.size();i++){
            start[i]=intervals.get(i).start;
            end[i]=intervals.get(i).end;
        }

        Arrays.sort(start);
        Arrays.sort(end);

        for(int i=0,j=0;i<intervals.size();i++){
            /* 到了最后一个元素或者不再有重叠*/
            if(i==intervals.size()-1 || start[i+1]>end[i]){
                list.add(new Interval(start[j],end[i]));
                j=i+1;
            }
        }

        return list;

    }

    public List<Interval> merge_optimization2(List<Interval> intervals) {
        if (intervals.size() <= 1)
            return intervals;

        // Sort by ascending starting point using an anonymous Comparator
        intervals.sort((i1, i2) -> Integer.compare(i1.start, i2.start));

        /*线性单链表 好评！*/
        List<Interval> result = new LinkedList<Interval>();
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        Interval last = new Interval(0,0);
        for (Interval interval : intervals) {
            /*if (interval.start > end){
                last = new Interval(start, end);
                result.add(last);
            }
            else {
                last.end = Math.max(last.end, interval.end);
            }*/
            if (interval.start <= end) // Overlapping intervals, move the end if needed
                end = Math.max(end, interval.end);
            else {                     // Disjoint intervals, add the previous one and reset bounds
                result.add(new Interval(start, end));
                start = interval.start;
                end = interval.end;
            }
        }

        // Add the last interval
        result.add(new Interval(start, end));
        return result;
    }

    public void bubbleSort(List<Interval> intervals) {
        boolean swap = false;
        for(int i = 0; i < intervals.size(); i++) {
            for(int j = 0; j <= intervals.size()-i-1-1; j++) {
                if(intervals.get(j).start > intervals.get(j+1).start) {
                    Interval temp = intervals.get(j);
                    intervals.set(j, intervals.get(j+1));
                    intervals.set(j+1, temp);
                    swap = true;
                }
            }
            // if(!swap) break;
        }
    }
}
<file_sep>/src/TAG/TwoPointers/_345__Reverse_Vowels_of_a_String.java
package TAG.TwoPointers;

// Two pointers
public class _345__Reverse_Vowels_of_a_String {
    public String reverseVowels(String s) {
        char[] vowels = new char[]{'a','e','i','o','u','A','E','I','O','U'};
        char[] array = s.toCharArray();
        int len = array.length;
        int i = 0;
        int j = len-1;
        while(i < j) {
            while(i < j && !isVowels(vowels, array[i])) i++;
            while(i < j && !isVowels(vowels, array[j])) j--;
            char c = array[i];
            array[i] = array[j];
            array[j] = c;
            i ++;
            j --;
        }
        return new String(array);
    }
    private boolean isVowels(char[] vowels, char c) {
        for(char v: vowels) {
            if(v == c)
                return true;
        }
        return false;
    }
}
<file_sep>/src/Ordered/_54__Spiral_Matrix.java
package Ordered;

import java.util.ArrayList;
import java.util.List;

public class _54__Spiral_Matrix {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int row = matrix.length;
        if(row == 0) return res;
        int col = matrix[0].length;
        int top = 0, left = 0, bottom = row - 1, right = col - 1;
        while(true) {
            // r row
            for(int j = left; j <= right; j++) {
                res.add(matrix[top][j]);
            }
            top++;
            if(left>right || top>bottom) break;
            // col-c-1 colum
            for(int i = top; i <= bottom; i++) {
                res.add(matrix[i][right]);
            }
            right--;
            if(left>right || top>bottom) break;
            // row-r-1 row
            for(int j = right; j >= left; j--) {
                res.add(matrix[bottom][j]);
            }
            bottom--;
            if(left>right || top>bottom) break;
            // c colum
            for(int i = bottom; i >= top; i--) {
                res.add(matrix[i][left]);
            }
            left++;
            if(left>right || top>bottom) break;
        }
        return res;
    }
}
<file_sep>/src/TAG/Greedy/_870__Advantage_Shuffle.java
package TAG.Greedy;

import java.util.Arrays;

/**
 * 田忌赛马
 * 利用贪心思想，首先对自己的马的性能进行排序（方便二分查找），对于对方的任何一匹马A，找出自己的马群中第一个性能大于A的马，
 * 如果没有大于A的马，则用最小的那匹马
 * 因为有数组移动的操作，时间复杂度为 O(n^2)
 *
 * https://leetcode.com/problems/advantage-shuffle/discuss/149822/JAVA-Greedy-6-lines-with-Explanation
 * 换个思路，使用大顶堆存储B的数字和对应下标，尽量满足大顶堆的堆顶，能满足就使用A中的最大值，不能满足就使用A中的最小值
 * 因为存储了下标，时间复杂度为O(nlogn)
 *
 */
public class _870__Advantage_Shuffle {
    public int[] advantageCount(int[] A, int[] B) {
        Arrays.sort(A);
        int[] res = new int[A.length];
        int len = A.length;
        for (int i = 0; i < B.length; i++) {
            int inx = binarySearch(A, B[i], len);
            if(inx == -1) {
                res[i] = A[0];
                coverInx(A, 0, len);
            }
            else {
                res[i] = A[inx];
                coverInx(A, inx, len);
            }
            len --;
        }
        return res;
    }
    
    public void coverInx(int[] array, int inx, int len) {
        for (int i = inx; i < len-1; i++) {
            array[i] = array[i+1];
        }
    }

    /**
     * 使用二分查找的思想，找到array中第一个大于target的值
     * @param array
     * @param target
     * @return
     */
    public int binarySearch(int[] array, int target, int len) {
        int lo = 0, hi = len-1;
        while (lo <= hi) {
            int mid = lo + ((hi-lo) >> 1);
            if(array[mid] <= target) {
                lo = mid + 1;
            }
            else {
                if(mid == 0 || array[mid-1] <= target) {
                    return mid;
                }
                hi = mid-1;
            }
        }
        return -1;
    }
}
<file_sep>/src/TAG/Tree/searchBST_Solution.java
package TAG.Tree;

/**
 * Given the root node of a binary search tree (BST) and a value.
 * You need to find the node in the BST that the node's value equals the given value.
 * Return the subtree rooted with that node. If such node doesn't exist, you should return NULL.
 */
public class searchBST_Solution {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
     }
    public TreeNode searchBST(TreeNode root, int val) {
        /*1. iteration*/
        /*
        while(true) {
            if(root == null) {
                return null;
            }
            if(root.val == val) {
                return root;
            }
            else if(root.val < val) {
                root = root.right;
            }
            else {
                root = root.left;
            }
        }
        */
        /*2. recrusion*/

        if(root == null) {
            return null;
        }
        TreeNode res;
        if(root.val == val) {
            res = root;
        }
        else if(root.val < val) {
            res = searchBST(root.right, val);
        }
        else {
            res = searchBST(root.left, val);
        }
        return res;
    }
}
<file_sep>/src/TAG/Tree/leafSimilar_Solution.java
package TAG.Tree;

import utils.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class leafSimilar_Solution {
    // 1.分别先序遍历得到序列，比较序列
    public boolean leafSimilar1(TreeNode root1, TreeNode root2) {
        List<Integer> leaves1 = getLeaves(root1);
        List<Integer> leaves2 = getLeaves(root2);
        int size = leaves1.size();
        if(size != leaves2.size()){
            return false;
        }
        /* 判断两个长度相同的list是否完全相等
        // solution 1
        for(int i = 0; i < size; i++){
            if(leaves1.get(i) != leaves2.get(i))
                return false;
        }
        return true;
        */
        // solution 2
        return leaves1.equals(leaves2);
    }
    // 2.分别遍历得到一个叶子节点，判断是否相等；利用栈可以做到
    public boolean leafSimilar2(TreeNode root1, TreeNode root2) {
        // if(root1 == null && root2 == null)
        //     return true;
        // else if(root1 != null && root2 == null || root2 != null && root1 == null)
        //     return false;
        Stack<TreeNode> s1 = new Stack<>(), s2 = new Stack<>();
        s1.push(root1); s2.push(root2);
        while(!s1.isEmpty() && !s2.isEmpty()) {
            if(dfs(s1) != dfs(s2))
                return false;
        }
        return s1.isEmpty() && s2.isEmpty();
    }
    public int dfs(Stack<TreeNode> s) {
        while(true) {
            TreeNode root = s.pop();
            if(root.left != null)
                s.push(root.left);
            if(root.right != null)
                s.push(root.right);
            // 返回叶子节点
            if(root.left == null && root.right == null)
                return root.val;
        }
    }
    List getLeaves(TreeNode root) {
        List<Integer> leaves = new ArrayList<>();
        if(root != null){
            forEach(root, leaves);
        }
        Integer[] xx = leaves.toArray(new Integer[leaves.size()]);
        return leaves;
    }
    void forEach(TreeNode root, List leaves){
        if(root.left == null && root.right == null) {
            leaves.add(root.val);
            return;
        }
        if(root.left != null) {
            forEach(root.left, leaves);
        }
        if(root.right != null) {
            forEach(root.right, leaves);
        }
    }
    TreeNode listToTree(List<Integer> list) {
        if(list == null) {
            return null;
        }
        TreeNode res = new TreeNode(list.get(0));
        for (int i = 1; i < list.size(); i++) {
            if(list.get(i) != null) {

            }
        }
        return res;
    }
    public static void main(String[] args) {

    }
}
<file_sep>/src/Ordered/_5__Longest_Palindromic_Substring.java
package Ordered;

/**
 * 寻找最长的回文数，回文数长度可能为偶数，可能是奇数
 */
public class _5__Longest_Palindromic_Substring {
    static int startInx = 0, validLen = 0;
    static int left = 0, right = 0;
    /**
     * 中心扩展算法 时间复杂度O(n^2) 空间复杂度O(n)
     * @param s
     * @return
     */
    public static String longestPalindrome_CenterExtend(String s) {
        int len = s.length();
        char[] c = s.toCharArray();
        int i = 0;
        /*循环记得要自增，不然就是死循环咯*/
        while(i < len - 1) {
            // assume even length.
            if(c[i] == c[i + 1]) {
                left = i;
                right = i + 1;
                findMaxPalindromic(c, left, right);
            }
            // assume odd length, try to extend Palindrome as possible
            left = right = i;
            findMaxPalindromic(c, left, right);
            i++;
        }
        /*substring(beginIndex, endInx)*/
        return s.substring(startInx, startInx+validLen);
    }
    /**
     * 以left、right为起点，向两侧寻找最长的回文数，并记录startInx, validLen
     * 左右起点可能相同
     * @param c  数组
     * @param left 左起点
     * @param right 右起点
     */
    public static void findMaxPalindromic(char[] c, int left, int right) {
        int len = c.length;
        // 向左右延伸，判断是否认为回文数
        while(left >= 0 && right < len && c[left] == c[right]) {
            // 变化left\right即可，不需要一个step
            left --;
            right ++;
        }
        /*此时的left, right正好指向回文数之外的位置，所以有效的wide为right-left-1*/
        int wide = right - left - 1;
        // 更新validLen, startInx
        if(wide > validLen) {
            validLen = wide;
            startInx = left + 1;
        }
    }

    /**
     * dp[j][i]表示s区间[j,i]是否回文字符串，j,i指向一个字符串的首尾
     * when j == i, dp[j][i] == true
     * when j<i, if s[j]==s[i]（字符串的首尾不相等必然不是回文字符串）
     *              &&
     *              (i - j < 3 （字符串的首尾相邻（i-j==1）或者首尾之间只隔了一个元素（i-j==2））
     *              ||
     *              dp[j+1][i-1]) （看首尾各减1形成的字符串是否为回文字符串；如果是的话，就相当于回文字符串得到了扩展）
     * @param s
     * @return
     */
    public static String longestPalindrome_DP(String s) {
        int len = s.length();
        /* 特例判断 */
        if(len == 0)
            return s;
        /*len>=1的情况，dp算法就可以执行，而且substring可以剪切出一个子串*/
        char[] c = s.toCharArray();
        boolean[][] dp = new boolean[len][len];
        for(int i = 0; i < len; i ++) {
            for(int j = 0; j < i; j ++) {
                // j+1, i-1不怕越界吗？
                // because j<i && max(j+1)==i，而i<len； min(j+1)==1 ;所以1 <= j+1 <= len 不会越界
                // min(i) == 1, max(i) == len -1, so 0 <= i-1 <= len-2 不会越界
                /**/
                dp[j][i] = (c[i] == c[j] && (i - j < 3 || dp[j + 1][i - 1]));
                // 更新right, left
                // 当len==2时候真正的长度，并不是validLen，所以为了使代码更为简洁，validLen只是为了长度的比较，
                // 并不是真正的长度，该if语句是为了更新left,right，真正的长度=right-left+1
                if(dp[j][i] && i-j+1 > validLen) {
                    validLen = i - j + 1;
                    left = j;
                    right = i;
                }
            }
            /*放在j的循环前后都无所谓啦*/
            dp[i][i] = true;
        }
        return s.substring(left, right + 1);
    }

    /**
     * 马拉车算法 O(n)
     * 最长回文字符串的字符个数 = resLen - 1
     * 起始位置 = (resCenter-resLen) / 2
     * @param s
     * @return
     */
    public static String longestPalindrome_Manacher(String s) {
        StringBuilder t = new StringBuilder("$#");
        for(char c: s.toCharArray()) {
            t.append(c+"#");
        }
        int len = t.length();
        // p[i] 表示以s[i]为字符中心的回文子串的半径
        int[] p = new int[len];
        for(int i = 0; i < len; i ++) {
            p[i] = 0;
        }
        char[] c = t.toString().toCharArray();
        // mx表示已知回文字符串的最靠右的位置，id表示mx对应回文字符串的中心位置；
        // resLen最长的回文字符串长度，resCenter是最长的回文字符串的中心位置在c中的下标
        int mx = 0, id = 0, resLen = 0, resCenter = 0;
        // 从第一个 # 开始
        for(int i = 1; i < len; i ++) {
            // 根据mx和i的关系，得到一个回文字符串半径的经验值
            p[i] = mx > i ? Math.min(mx - i, p[id + id - i]) : 1;
            /*在下标不越界的情况下，向两侧延伸回文字符串*/
            while(i + p[i] < len && i - p[i] >= 0 && c[i + p[i]] == c[i - p[i]]) p[i] ++;
            // 更新mx和id
            if(mx < i + p[i]) {
                mx = i + p[i];
                id = i;
            }
            // 更新resLen 和 resCenter
            if(resLen < p[i]) {
                resLen = p[i];
                resCenter = i;
            }
        }
        return s.substring((resCenter-resLen)/2, (resCenter-resLen)/2 + resLen - 1);
    }

    public static void main(String[] args) {
        System.out.println(longestPalindrome_Manacher("babadada"));
    }
}
<file_sep>/Readme.md
对于一道题，要有一个模型、要能发现它的特征

超过半小时想不出则看答案，看下别人的思路，自己的盲点，千万不要死抠！！

写链表代码还是主要为了*锻炼写代码的能力*，倒不是思考解决办法

不是完全想不出，而是想出来的思路不能解决问题；多做题，把思路整理好；在草纸上多演算



如果报错，记下来你的错误，第二次提交，记下错误，以此类推。

第二天，第三天接着做，一直做到一提交就bugfree

切忌盲目刷题，要记思路不记题目

心态：坚持刷、看题解、思考
不要怪题目太刁钻，是你没想出解决办法啦

tag: 精进案例，bit

two points: i, j 
快慢指针（链表）
bit manipulation
滑动窗口

二分查找：旋转的有序数组中查找特定值，旋转的有序数组中求最小值

链表：判断有无环、判断环入口、环长度、链表长度、环中节点的对面节点、两个无环链表是否相交并判断相交点<file_sep>/src/TAG/Stack/_155__Min_Stack.java
package TAG.Stack;

import java.util.Stack;

/**
 * 以O(1)的时间获取栈中的最小值，
 * 最朴素的想法是getMin()方法调用时，遍历栈来获得最小值，getMin()时间复杂度为O(n)；
 * 为了让getMin()时间复杂度是O(1)，可以用两个栈，一个存储数据，另一个存储当前数据集下的最小值，两个栈大小相同，
 * 缺点是空间复杂度为O(n)；
 * 还可以用一个栈，如果新值是最小值，栈会记录一个之前的最小值，再记录新值，时间和空间复杂度分别是O(1)和O(n)；
 */
public class _155__Min_Stack {

}



/**
 * 该类使用一个栈来实现
 */
class MinStack {
    Stack<Integer> stack;
    int min = Integer.MAX_VALUE;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
    }

    public void push(int x) {
        // why =？因为对于栈顶是最小值的情况，pop()会弹出两次，如果新值等于最小值，如果只放如入栈一次，则pop()会出错
        if(x <= min) {
            stack.push(min);
            min = x;
        }
        stack.push(x);
    }

    public void pop() {

        if(min == stack.pop())
            min = stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min;
    }
}

class MinStack_TwoStack {
    Stack<Integer> stack;
    Stack<Integer> min;
    /** initialize your data structure here. */
    public MinStack_TwoStack() {
        stack = new Stack<>();
        min = new Stack<>();
    }

    public void push(int x) {
        if(min.isEmpty() || x <= min.peek()) {
            min.push(x);
        }
        else {
            min.push(min.peek());
        }
        stack.push(x);
    }

    public void pop() {
        min.pop();
        stack.pop();
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min.peek();
    }
}

class MinStack_Worst {
    private int[] items;
    private int n = 20;
    private int count = 0;
    /** initialize your data structure here. */
    public MinStack_Worst() {
        items = new int[n];
    }

    public void push(int x) {
        if(count == n) {
            int[] newItems = new int[n * 2];
            for(int i = 0; i < n; i ++) {
                newItems[i] = items[i];
            }
            items = newItems;
            n *= 2;
        }
        items[count ++] = x;
    }

    public void pop() {
        if(count == 0) return;
        count --;
    }

    public int top() {
        if(count == 0) return 0;
        return items[count - 1];
    }

    public int getMin() {
        int min = items[count - 1];
        for(int i = 0; i < count; i ++) {
            if(items[i] < min) min = items[i];
        }
        return min;
    }
}<file_sep>/src/Ordered/_75__Sort_Colors.java
package Ordered;

public class _75__Sort_Colors {
    public void sortColors(int[] nums) {
        int second = nums.length, zero = 0;
        for (int i = 0; i < second; ) {
            if(nums[i] == 2) {
                swap(nums[i], nums[second --]);
                i ++;
            }
            if(nums[i] == 0) {
                swap(nums[i], nums[zero ++]);
            }
        }

    }

    public void swap(int n, int m) {
        int t = n;
        n = m;
        m = t;
    }
}
<file_sep>/src/TAG/Tree/averageOfLevels_Solution.java
package TAG.Tree;

import utils.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 要知道每层的个数，和值才能求平均
 * 可以使用BFS DFS两种方法
 */
public class averageOfLevels_Solution {
    /**
     * BFS：利用队列按层遍历
     * @param root
     * @return
     */
    public List<Double> averageOfLevels1(TreeNode root) {
        if(root == null) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int preLevelCount = 1;
        List<Double> res = new ArrayList<>();
        // 按层遍历队列
        while(!queue.isEmpty()) {
            int curLevelCount = 0;
            double sum = 0;
            // 从队列中取出上一层的元素；求和，取平均，加入res；更新preLevelCount
            for(int i = 0; i < preLevelCount; i ++) {
                TreeNode node = queue.poll();
                sum += node.val;
                if(node.left != null) {
                    curLevelCount ++;
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    curLevelCount ++;
                    queue.offer(node.right);
                }
            }
            res.add(sum / preLevelCount);
            preLevelCount = curLevelCount;
        }
        return res;
    }

    class Node {
        double sum;
        int count;
        Node (double d, int c) {
            sum = d;
            count = c;
        }
    }
    /**
     * DFS：利用
     * @param root
     * @return
     */
    public List<Double> averageOfLevels2(TreeNode root) {
        List<Node> temp = new ArrayList<>();
        helper(root, temp, 0);
        List<Double> result = new LinkedList<>();
        for (int i = 0; i < temp.size(); i++) {
            result.add(temp.get(i).sum / temp.get(i).count);
        }
        return result;
    }
    public void helper(TreeNode root, List<Node> temp, int level) {
        if (root == null) return;
        // temp中每个值是Node，对应的是Tree中每层节点的总和以及个数
        if (level == temp.size()) {
            Node node = new Node((double)root.val, 1);
            temp.add(node);
        } else {
            temp.get(level).sum += root.val;
            temp.get(level).count++;
        }
        helper(root.left, temp, level + 1);
        helper(root.right, temp, level + 1);
    }
}
<file_sep>/src/SwordOffer/_1.java
package SwordOffer;

public class _1 {
    // 二维数组array中，每一行都从左到右递增排序，
    // 每一列都从上到下递增排序
    public boolean Find(int target, int [][] array) {
        if(array == null)
            return false;
        int row = array.length;
        int col = array[0].length;
        if(col == 0)
            return false;
        int i = 0, j = col - 1;
        boolean found = false;
        while(i < row && j >= 0) {
            if(array[i][j] == target) {
                found = true;
                break;
            }
            else if(array[i][j] < target) {
                i ++;
            }
            else {
                j --;
            }
        }
        return found;
    }
}
<file_sep>/src/Ordered/_904__Fruit_Into_Baskets.java
package Ordered;

/**
 * 往两个篮子里放水果，每个篮子里水果的种类是相同的；
 * 面对新的种类的水果，要么停止搜索，要么放进某个篮子中一个；
 * 那么对于一行树，求两个篮子最多能放的水果数目
 */
public class _904__Fruit_Into_Baskets {
    public int totalFruit(int[] tree) {
        int max = 0;
        int len = tree.length;
        /*按照一种模型：...aaabbbc...
        * 对于一种新的类型c，分为三种情况
        * 1. c == a
        * 2. c == b
        * 3. c != a && c != b
        * */
        int a = -1, b = -1;
        // 笼统地知道a,b的数目是没有用的，因为题目虽然要求a, b可以不连续，但是一旦出现一个新的type（c），你根本不知到a和c之间的b有多少，
        // 所以，要有一个统计b的数目的变量
        int cur = 0, cb = 0;

        for(int i = 0; i < len; i ++) {
            if(tree[i] == a) {
                a = b;
                b = tree[i];
                cb = 1;
                cur ++;
            }
            else if(tree[i] == b) {
                cur ++;
                cb ++;
            }
            else if(tree[i] != a && tree[i] != b) {
                a = b;
                b = tree[i];

                cur = cb + 1;
                cb = 1;
            }
            max = cur > max ? cur : max;
        }
        return max;
    }

    public static void main(String[] args) {
        _904__Fruit_Into_Baskets fruit_into_baskets = new _904__Fruit_Into_Baskets();
        fruit_into_baskets.totalFruit(new int[]{1,0,1,4,1,4,1,2,3});
    }
}
<file_sep>/src/TAG/TwoPointers/_443__String_Compression.java
package TAG.TwoPointers;

public class _443__String_Compression {
    public int compress(char[] chars) {
        if(chars.length < 2) return chars.length;
        int i = 0, j = 0, num = 0;
        for (j = 0; j < chars.length; j++) {
            num++;
            if(j == chars.length-1 || chars[j] != chars[j+1]) {
                chars[i++] = chars[j];
                if(num != 1) {
                    String s = String.valueOf(num);
                    for (int k = 0; k < s.length(); k++) {
                        chars[i++] = s.charAt(k);
                    }
                }
                num = 0;
            }
        }
        return i;
    }
}
<file_sep>/src/TAG/BackTracking/_22__Generate_Parentheses.java
package TAG.BackTracking;

import java.util.*;

public class _22__Generate_Parentheses {
    /**
     * 遍历所有情况，通过剪枝来减少无效情况的发生
     * 通过判断左右括号的个数，以及是有效括号字符串来加入结果集
     *
     * @param n
     * @return
     */
    public List<String> generateParenthesis_Mine(int n) {
        List<String> res = new ArrayList<>();
        // find all situations, keep valid parenthes
        findAllParenthes(res, "", 0, 0, n);
        return res;
    }

    // 剪枝
    public void findAllParenthes(List<String> res, String s, int leftParenthesNum, int rightParenthesNum, int total) {
        /*递归的返回条件放在第一行，说明需要多一次递归；可以把判断条件放在内部，减少一次递归*/
        // if(leftParenthesNum > total || rightParenthesNum > total) return;
        if (leftParenthesNum == total && rightParenthesNum == total && isValid(s)) { //
            res.add(s);
            return;
        }
        /************************************KEY DIFFERENCE*************************************/
        // 只限制左右括号的个数，而忽略两者之间的关系，就需要另外判断形成的字符串是否有效
        if (leftParenthesNum < total)
            findAllParenthes(res, s + "(", leftParenthesNum + 1, rightParenthesNum, total);
        if (rightParenthesNum < total)
            findAllParenthes(res, s + ")", leftParenthesNum, rightParenthesNum + 1, total);
    }

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) == '(')
                stack.push(s.charAt(i));
            else { // ')'
                if (stack.isEmpty() || stack.pop() != '(') {
                    return false;
                }
            }
        }
        if (stack.isEmpty())
            return true;
        return false;
    }

    /**
     * 回溯，带有剪枝
     *
     * @param n
     * @return
     */
    public List<String> generateParenthesis_Others(int n) {
        List<String> list = new ArrayList<String>();
        backtrack(list, "", 0, 0, n);
        return list;
    }

    public void backtrack(List<String> list, String str, int open, int close, int max) {
        if (str.length() == max * 2) { // equal to (open == max && close == max)
            list.add(str);
            return;
        }
        /************************************KEY DIFFERENCE*************************************/
        // 既考虑左右括号的个数，也考虑两者之间的关系，就能够保证最终形成的字符串是有效的
        if (open < max)
            // str要和“(”相加，以对带(的情况进行回溯，同时又要保持本色，以对别的情形进行回溯，所以str + "("正合适；open+1同理
            backtrack(list, str + "(", open + 1, close, max);
        if (close < open)
            backtrack(list, str + ")", open, close + 1, max);
    }


    public static void main(String[] args) {
        _22__Generate_Parentheses generateParentheses = new _22__Generate_Parentheses();
        System.out.println(generateParentheses.generateParenthesis_Mine(2));
        System.out.println(generateParentheses.generateParenthesis_Others(2));
    }
}
<file_sep>/src/TAG/Tree/_236__Lowest_Common_Ancestor_of_a_Binary_Tree.java
package TAG.Tree;

import utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 最近公共祖先
 */
public class _236__Lowest_Common_Ancestor_of_a_Binary_Tree {

    /**
     * If the current (sub)tree contains both p and q, then the function result is their LCA.
     * If only one of them is in that subtree, then the result is that one of them.
     * If neither are in that subtree, the result is null/None/nil.
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        return left == null ? right : right == null ? left : root;
    }

    /**
     * 将寻找最近公共祖先转换为两个数组找公共节点。时间复杂度是O(n)
     * 分别找到p,q的公共祖先序列，然后找到最近的公共祖先
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor_MINE(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pAncestor = new ArrayList<>();
        List<TreeNode> qAncestor = new ArrayList<>();
        isAncestor(root, p, pAncestor);
        isAncestor(root, q, qAncestor);
        int len1 = pAncestor.size();
        int len2 = qAncestor.size();
        int i = len1-1, j = len2-1;
        for(; i>=0 && j>= 0;) {
            if(pAncestor.get(i) == qAncestor.get(j)) {
                i --;
                j --;
            }
            else {
                break;
            }
        }
        return pAncestor.get(i+1);
    }

    /**
     * Is node p's ancester?
     * 将p的祖先节点保存在list中
     * @param node
     * @param p
     * @param list
     * @return
     */
    public boolean isAncestor(TreeNode node, TreeNode p, List<TreeNode> list) {
        if(node == null) return false;
        if(node == p) {
            // 把p节点放进list
            list.add(node);
            return true;
        }
        boolean found = false;
        if(isAncestor(node.left, p, list) || isAncestor(node.right, p, list)) {
            found = true;
            // 把p的祖先节点放进list
            list.add(node);
        }
        return found;
    }
}
<file_sep>/src/TAG/Tree/_114__Flatten_Binary_Tree_to_Linked_List.java
package TAG.Tree;

import utils.TreeNode;

public class _114__Flatten_Binary_Tree_to_Linked_List {
    public void flatten(TreeNode root) {
        if(root == null) return;

        if(root.left != null) flatten(root.left);
        if(root.right != null) flatten(root.right);
        TreeNode node = root.right;
        root.right = root.left;
        root.left = null; // nessesary? yes! because it maybe has TreeNode before, need to be set null.
        while(root.right != null) root = root.right;
        root.right = node;

    }
}
<file_sep>/src/SwordOffer/_4_ReConstructBinaryTree.java
package SwordOffer;

import utils.TreeNode;

import java.util.Arrays;

/**
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
 * */
public class _4_ReConstructBinaryTree {
    public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
        TreeNode dummy = new TreeNode(0);
        dummy.left = recru(pre, in);
        return dummy.left;
    }
    private TreeNode recru(int[] pre, int[] in) {
        if(pre.length == 0 && in.length ==0)return null;
        // 树顶点
        int i = 0;
        for(; i < in.length; i ++) {
            if(in[i] == pre[0])
                break;
        }
        TreeNode node = new TreeNode(pre[0]);
        if(i <= 0) // i+1>pre.length || i >in.length
            node.left = null;
        else
            node.left = recru(Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i));
        if(pre.length - i - 1 <= 0) // i+1>=pre.length || i+1 >=in.length
            node.left = null;
        else
            node.right = recru(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1, in.length));
        return node;
    }

    public TreeNode reConstructBinaryTreeIterative(int [] pre, int [] in) {
        if(pre == null || pre.length == 0)
            return null;
        int j = 0;
        while(in[j] != pre[0]) {j ++;}
        TreeNode node = new TreeNode(pre[0]);
        node.left = reConstructBinaryTreeIterative(Arrays.copyOfRange(pre, 1, j+1), Arrays.copyOfRange(in, 0, j));
        node.right = reConstructBinaryTreeIterative(Arrays.copyOfRange(pre, j+1, pre.length), Arrays.copyOfRange(in, j+1, in.length));
        return node;
    }
}
<file_sep>/src/utils/ListNode.java
package utils;

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) {val = x;}

    public static ListNode buildListNode(int[] num) {
        ListNode dummy = new ListNode(-1);
        ListNode head = dummy;
        for (int i: num) {
            dummy.next = new ListNode(i);
            dummy = dummy.next;
        }
        return head.next;
    }

    public static void printListNode(ListNode head) {
        if(head == null) {
            System.out.println("This ListNode is NULL!");
            return;
        }
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }

    public static ListNode reverseIterative(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode tmp = cur;
            cur = cur.next;
            tmp.next = pre;
            pre = tmp;
        }
        return pre;
    }

    public static ListNode reverseRecursive(ListNode head) {
        return reverseListRecursive(head, null);
    }

    private static ListNode reverseListRecursive(ListNode cur, ListNode pre) {
        if(cur == null) return pre;
        ListNode tmp = cur;
        cur = cur.next;
        tmp.next = pre;
        pre = tmp;
        return reverseListRecursive(cur, pre);
    }

    public static void main(String[] args) {
        int[] num = new int[]{3,4,5,0,1,2};
        ListNode head = ListNode.buildListNode(num);
        ListNode.printListNode(head);
        head = ListNode.reverseIterative(head);
        ListNode.printListNode(head);
        head = ListNode.reverseRecursive(head);
        ListNode.printListNode(head);
    }
}
<file_sep>/src/TAG/Tree/_437_PathSumIII.java
package TAG.Tree;

import utils.TreeNode;

public class _437_PathSumIII {
    /**
     * 双重递归
     * pathSum递归选择root point（起始结点）
     * pathSumHelper 拿着root point递归遍历这条树，直到leaf
     * @param root
     * @param sum
     * @return
     */
    public int pathSum(TreeNode root, int sum) {
        if(root == null) return 0;
        return pathSumHelper(root, sum) +
                pathSum(root.left, sum) +
                pathSum(root.right, sum);
    }

    public int pathSumHelper(TreeNode root, int sum) {
        if(root == null) return 0;
        int count = 0;
        if(root.val == sum) count++;
        count += pathSumHelper(root.left, sum - root.val);
        count += pathSumHelper(root.right, sum - root.val);
        return count;
    }
}
<file_sep>/src/TAG/Math/Bit_Manipulation/_136__Single_Number.java
package TAG.Math.Bit_Manipulation;

public class _136__Single_Number {
    public int singleNumber(int[] nums) {
        int x = 0;
        for(int i: nums) {
            x ^= i;
        }
        return x;
    }

    public static void main(String[] args) {
        _136__Single_Number single_number = new _136__Single_Number();
        System.out.println(single_number.singleNumber(new int[]{1,1,2}));
    }
}
<file_sep>/src/Ordered/_73__Set_Matrix_Zeroes.java
package Ordered;

/**
 * Given a m x n matrix, if an element is 0, set its entire row and column to 0.
 * 精进案例
 * 1. A straight forward solution using O(mn) space is probably a bad idea.
 * 新建一个与matrix同样大小的数组newArray，以matrix为参照操作newArray
 * 2. A simple improvement uses O(m + n) space, but still not the best solution.
 * 问题本身是设置某行和列为0，so, 新建一个一行大小和一个一列大小的数组，分别表示该列和行是否要置零
 * 3. Could you devise a constant space solution?
 * 直接使用matrix的首行和首列来标识该列和行是否置零，至于首行和首列是否置零单独用变量标识
 */
public class _73__Set_Matrix_Zeroes {
    public void setZeroes(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return;
        boolean fr = false, fc = false;
        int m = matrix.length;
        int n = matrix[0].length;
        // 如果matrix[i,j]==0，就让列首、行首为0（标记），如果行首、列首存在为0的情形，则让fr，fc为true
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] == 0) {
                    if(i == 0) fr = true;
                    if(j == 0) fc = true;
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }

        for(int i = 1; i < m; i ++) {
            for(int j = 1; j < n; j ++) {
                if(matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        if(fr)
            for(int j = 0; j < n; j ++) {
                matrix[0][j] = 0;
            }
        if(fc)
            for(int i = 0; i < m; i ++) {
                matrix[i][0] = 0;
            }
    }
}
<file_sep>/src/TAG/Math/One_Num_Binary.java
package TAG.Math;

/**
 * 一个数的二进制中1的个数
 */
public class One_Num_Binary {
    /**
     * 移位 + 计数
     * 与n的二进制位数有关，最多循环32次
     * @param n
     * @return
     */
    public int BitCount_Normal(int n) {
        int c = 0; // 计数器
        while (n > 0) {
            if ((n & 1) == 1) // 当前位是1
                ++c; // 计数器加1
            n >>= 1; // 移位
        }
        return c;
    }

    public int BitCount_Normal_Ahead(int n) {
        int c = 0;
        for (; n > 0; n >>= 1) {
            c += n & 1;
        }
        return c;
    }

    /**
     * 通过 n &= (n-1) 清除n的二进制数中的最低位的1，正负数都适用
     * @param n
     * @return
     */
    public int BitCount_Quick_Negative(int n) {
        int c = 0;
        // n中1的个数
        for (; n != 0; c ++) {
            // 清除 n 的最低位的 1
            n &= (n - 1);
        }
        return c;
    }

    public int BitCount_Dynamic_Table(int n) {
        char[] bitsSetTable256 = new char[256];
        for (int i = 0; i < bitsSetTable256.length; i++) {
            bitsSetTable256[i] = 0;
        }
        for (int i = 0; i < bitsSetTable256.length; i++) {
            // ((i & 1) == 0 ? '0' : '1')
            // function BitCount(i) 指的是 i 的二进制中 1 的个数
            // 如果i是偶数，i二进制最后1位是0，BitCount(i)==BitCount(i>>1);
            // 如果i是奇数，i二进制最后1位是1，BitCount(i)==BitCount(i>>1) + 1;
            // 综上得出以下计算公式
            bitsSetTable256[i] = (char)(bitsSetTable256[i / 2] + (i & 1));
        }
        int c = 0;
        // 把n按8位分成4份，分别求其中1的个数
        c = bitsSetTable256[(n & 0xFF000000) >> 24] +
                bitsSetTable256[(n & 0x00FF0000) >> 16] +
                bitsSetTable256[(n & 0x0000FF00) >> 8] +
                bitsSetTable256[(n & 0x000000FF)];
        return c;
    }

    public int BitCount_Static_Table(int n) {
        int[] table = {
            0, 1, 1, 2,
            1, 2, 2, 3,
            1, 2, 2, 3,
            2, 3, 3, 4
        };
        int c = 0;
        while(n > 0) {
            c += table[n & 0xF];
            n >>= 4;
        }
        return c;
    }

    public int BitCount_Static_Table_2(int n) {
        // 数字0, 1, 2, 3对应的二进制数的个数
        int[] table = {
            0, 1, 1, 2
        };
        int c = 0;
        while(n > 0) {
            c += table[n & 0x3];
            n >>= 2;
        }
        return c;
    }

    public int BitCount_negative(int n) {
        if(n == 0 ) return 0;
        int i = 1;
        int count = 0;
        while (i != 0) {
            if((n & i) == i) {
                count ++;
            }
            i >>= 1;
        }
        return count;
    }


    public static void main(String[] args) {
        int i = 100;

        Long c = Long.valueOf(-2147483648);
        System.out.println(false ^ true);
        One_Num_Binary one_numDecimal = new One_Num_Binary();
        int num = -217;
        System.out.println(Integer.toBinaryString(num));
        System.out.println(one_numDecimal.BitCount_Quick_Negative(num));
        if(num < 0) return;
        System.out.println(one_numDecimal.BitCount_Normal(num));
        System.out.println(one_numDecimal.BitCount_Normal_Ahead(num));
        System.out.println(one_numDecimal.BitCount_Dynamic_Table(num));
        System.out.println(one_numDecimal.BitCount_Static_Table(num));
        System.out.println(one_numDecimal.BitCount_Static_Table_2(num));

    }
}
