Premium* (Java) - ShuweiLeung/Thinking GitHub Wiki

    //step1: inorder tranversal by recursion to connect the original BST
    //step2: connect the head and tail to make it circular
    //Tips: Using dummy node to handle corner case
    Node prev = null;
    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        Node dummy = new Node(0, null, null);
        prev = dummy; //pre一开始指向的是dummy node
        helper(root);
        //connect head and tail
        //此时prev指向的是双向链表的末尾，dummy链接的是链表的头部
        prev.right = dummy.right;
        dummy.right.left = prev;
        return dummy.right;
    }

    private void helper (Node cur) {
        //inorder traversal
        if (cur == null) return;
        helper(cur.left);
        prev.right = cur;
        cur.left = prev;
        prev = cur;
        helper(cur.right);
    }

A -> B -> C -> D <- E <- F
               ^
               |
               G
               ^
               |
               H

1) Replace 1 char:
   s: a B c
   t: a D c
2) Delete 1 char from s: 
   s: a D  b c
   t: a    b c
3) Delete 1 char from t
   s: a   b c
   t: a D b c

public boolean isOneEditDistance(String s, String t) {
    for (int i = 0; i < Math.min(s.length(), t.length()); i++) {
	if (s.charAt(i) != t.charAt(i)) {
	    if (s.length() == t.length()) // s has the same length as t, so the only possibility is replacing one char in s and t
	        return s.substring(i + 1).equals(t.substring(i + 1));
	    else if (s.length() < t.length()) // t is longer than s, so the only possibility is deleting one char from t
		return s.substring(i).equals(t.substring(i + 1));
	    else // s is longer than t, so the only possibility is deleting one char from s
		return t.substring(i).equals(s.substring(i + 1));
	}
    }
    //All previous chars are the same, the only possibility is deleting the end char in the longer one of s and t
    return Math.abs(s.length() - t.length()) == 1;
}

public int closestValue(TreeNode root, double target) {
    int closestVal = root.val;
    while(root != null) {
        if(Math.abs(target - root.val) < 
            Math.abs(target - closestVal)) 
        {
            closestVal = root.val;    
        }
        if(target == root.val) {
            return root.val;
        }
        else if(target < root.val) {
            root = root.left;
        }
        else {
            root = root.right;
        }
    }
    return closestVal;
}

    class Point {
        int x,y;
        public Point(int _x, int _y) {x=_x;y=_y;}
    }
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int m=maze.length, n=maze[0].length;
        if (start[0]==destination[0] && start[1]==destination[1]) return true;
        int[][] dir=new int[][] {{-1,0},{0,1},{1,0},{0,-1}}; //运动方向数组
        boolean[][] visited=new boolean[m][n];  //visited矩阵
        LinkedList<Point> list=new LinkedList<>(); //存储当前可达位置
        visited[start[0]][start[1]]=true;
        list.offer(new Point(start[0], start[1]));
        while (!list.isEmpty()) {
            Point p=list.poll();
            int x=p.x, y=p.y;
            for (int i=0;i<4;i++) { //从当前点向上下左右四个方向前进
                int xx=x, yy=y;
                while (xx>=0 && xx<m && yy>=0 && yy<n && maze[xx][yy]==0) {
                    xx+=dir[i][0];
                    yy+=dir[i][1];
                }
                //往后退一步才是真正到达的位置
                xx-=dir[i][0];
                yy-=dir[i][1];
                if (visited[xx][yy]) continue; //如果是之前到达过的位置，跳过
                visited[xx][yy]=true;
                if (xx==destination[0] && yy==destination[1]) return true;
                list.offer(new Point(xx, yy)); //加入list集合中
            }
        }
        return false;
    }

奇数个
nums = [1,2,3,4,5,6,7]
	1,7,3,4,5,6,2
	1,7,3,5,4,6,2

偶数个
nums = [1,2,3,4,5,6]
        1,5,3,4,2,6
public void wiggleSort(int[] nums) {
	Arrays.sort(nums);
	
	int i = 1, j;
	
	if(nums.length % 2 == 0)
		j = nums.length - 2;
	else
		j = nums.length - 1;
	
	while(i < j) {
		int t = nums[i];
		nums[i] = nums[j];
		nums[j] = t;
		
		i += 2;
		j -= 2;
	}
}

    The final sorted nums needs to satisfy two conditions:

    If i is odd, then nums[i] >= nums[i - 1];

    If i is even, then nums[i] <= nums[i - 1].

    The code is just to fix the orderings of nums that do not satisfy 1
    and 2.

    public void wiggleSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 1) {
                if (nums[i] < nums[i - 1]) {
                    int temp = nums[i];
                    nums[i] = nums[i - 1];
                    nums[i - 1] = temp;
                }
            } else if (i != 0 && i % 2 == 0) {
                if (nums[i] > nums[i - 1]) {
                    int temp = nums[i];
                    nums[i] = nums[i - 1];
                    nums[i - 1] = temp;
                }
            }
        }
    }

    int diff = Integer.MAX_VALUE;
    String result = "";
    
    public String nextClosestTime(String time) {
        Set<Integer> set = new HashSet<>();  //存储输入time中的所有digit
        set.add(Integer.parseInt(time.substring(0, 1)));
        set.add(Integer.parseInt(time.substring(1, 2)));
        set.add(Integer.parseInt(time.substring(3, 4)));
        set.add(Integer.parseInt(time.substring(4, 5)));
        
        if (set.size() == 1) return time;
        
        List<Integer> digits = new ArrayList<>(set);
        int minute = Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(3, 5)); //将time转换为分钟

        dfs(digits, "", 0, minute);

        return result;
    }

    private void dfs(List<Integer> digits, String cur, int pos, int target) { //cur是搜索路径，pos是当前位置，target是主函数输入的时间
        if (pos == 4) { //计算当前的搜索路径所代表的时间，转换为分钟制
            int m = Integer.parseInt(cur.substring(0, 2)) * 60 + Integer.parseInt(cur.substring(2, 4));
            if (m == target) return;
            int d = m - target > 0 ? m - target : 1440 + m - target; //如果m-target小于0，说明此时cur搜索路径代表的是第二天的时间
            if (d < diff) {
                diff = d;
                result = cur.substring(0, 2) + ":" + cur.substring(2, 4);
            }
            return;
        }

        for (int i = 0; i < digits.size(); i++) {
            if (pos == 0 && digits.get(i) > 2) continue;  //一天最多只有23个小时，十位数不可能大于2
            if (pos == 1 && Integer.parseInt(cur) * 10 + digits.get(i) > 23) continue; //一天最多只有23个小时，满24进1
            if (pos == 2 && digits.get(i) > 5) continue; //一小时最多只有59分钟，十位不能大于5
            if (pos == 3 && Integer.parseInt(cur.substring(2)) * 10 + digits.get(i) > 59) continue; //一小时只有59分钟，满60进1 
            dfs(digits, cur + digits.get(i), pos + 1, target);
        }
    }

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode succ = null;
        while (root != null) {
            if (p.val < root.val) {   //当p在root的左子树上时，才记录succ，因为当前的root可能就是p的successor
                succ = root;
                root = root.left;
            }
            else
                root = root.right;  //如果p在root的右子树上时，我们不记录succ，因为肯定存在比p还大的元素，或者是null
        }
        return succ;
    }

    public boolean splitArray(int[] nums) {
        if (nums.length < 7)
            return false;
        int[] sum = new int[nums.length]; //累加和数组
        sum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sum[i] = sum[i - 1] + nums[i];
        }
        for (int j = 3; j < nums.length - 3; j++) { //确定中间指针的活动范围
            HashSet<Integer> set = new HashSet<>(); 
            for (int i = 1; i < j - 1; i++) {
                if (sum[i - 1] == sum[j - 1] - sum[i])  //先确定前半部分的符合值，按定义来求值即可
                    set.add(sum[i - 1]);
            }
            for (int k = j + 2; k < nums.length - 1; k++) { //再遍历后半部分的符合值，且该值要与前半部分相同，按定义来求值即可
                if (sum[nums.length - 1] - sum[k] == sum[k - 1] - sum[j] && set.contains(sum[k - 1] - sum[j]))
                    return true;
            }
        }
        return false;
    }

class Codec {
    // Encodes an n-ary tree to a binary tree.
    // Encode的时候，对于一个当前的根节点，转换后二叉树的左子树是原来N叉树的孩子结点，右子树是原来N叉树的兄弟结点
    public TreeNode encode(Node root) {
        if (root == null) {
            return null;
        }
        TreeNode result = new TreeNode(root.val);
        if (root.children.size() > 0) {
            result.left = encode(root.children.get(0));
        }
        TreeNode cur = result.left;
        for (int i = 1; i < root.children.size(); i++) {
            cur.right = encode(root.children.get(i));
            cur = cur.right;
        }
        return result;
    }

    // Decodes your binary tree to an n-ary tree.
    public Node decode(TreeNode root) {
        if (root == null) {
            return null;
        }
        Node result = new Node(root.val, new LinkedList<>());
        TreeNode cur = root.left;
        while (cur != null) {
            result.children.add(decode(cur)); //添加的是cur及其子树结点
            cur = cur.right;
        }
        return result;
    }
}

public List<String> findMissingRanges(int[] A, int lower, int upper) {
    List<String> result = new ArrayList<String>();
    //注意变量的类型都是long，来handle一些corner cases
    long pre = (long)lower - 1;  
    for(int i = 0 ; i <= A.length  ; i++){
        long after = i == A.length ? (long)upper + 1 : (long)A[i]; 
        if(pre + 2 == after){ //检查是差一个数还是差一个序列
            result.add(String.valueOf(pre + 1));
        }else if(pre + 2 < after){
            result.add(String.valueOf(pre + 1) + "->" + String.valueOf(after - 1));
        }
        pre = after;
    }
    return result;
}

public TreeNode[] splitBST(TreeNode root, int V) {
	// res[0]: root with values <= V
        // res[1]: root with values > V

        if (root == null)
        {
            return new TreeNode[]{null, null};
        }

        if (root.val <= V)
        {
            // The cut off is somewhere in the right subtree relative to root

            TreeNode[] res = splitBST(root.right, V);

            // res[0] is the node for all values <= V found in the right sub tree
            // since it's form the right sub tree, all values must be greater than root
            // so safe to do the following
            root.right = res[0];

            // root along with everything in its left subtree are already <= V
            // so after setting root.right=res[0], now root represents all nodes <= V

            // the node for all values greater than V is still res[1], some node found on the right subtree
            
            return new TreeNode[]{root, res[1]};
        }
        else //root.val > V
        {
            // The cut off is somewhere in the left subtree relative to root
                           
            TreeNode[] res = splitBST(root.left, V);

            // res[1] is the node for all values >V found in the left sub tree
            // since it's from the left sub tree, all values must be less than root
            // so safe to do the following
            
            root.left = res[1];
            
            // root along with everything in its right subtree are already >V
            // so after setting root.left=res[1], now root represents all values >V
            
            // the node for all values less than V is still res[0], some node found on the left subtree 
            
            return new TreeNode[]{res[0], root};
        }
}

int max = 0;
class Result {  //用于统计以当前结点作为参考，记录左右子树的连续递增、连续递减序列长度
    TreeNode node;
    int inc;
    int des;
}
    
public int longestConsecutive(TreeNode root) {
    traverse(root);
    return max;
}
    
private Result traverse(TreeNode node) {
    //使用后序遍历的方法
    if (node == null) return null;
    
    Result left = traverse(node.left);
    Result right = traverse(node.right);
        
    Result curr = new Result();
    curr.node = node;
    curr.inc = 1;
    curr.des = 1;
        
    if (left != null) {
        if (node.val - left.node.val == 1) {
            curr.inc = Math.max(curr.inc, left.inc + 1);
        }
        else if (node.val - left.node.val == -1) {
            curr.des = Math.max(curr.des, left.des + 1);
        }
    }
        
    if (right != null) {
        if (node.val - right.node.val == 1) {
            curr.inc = Math.max(curr.inc, right.inc + 1);
        }
        else if (node.val - right.node.val == -1) {
            curr.des = Math.max(curr.des, right.des + 1);
        }
    }
        
    max = Math.max(max, curr.inc + curr.des - 1);  //每一层比较完后都会更新max返回值
        
    return curr;
}

    public int largestBSTSubtree(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        if (isValid(root, null, null)) return countNode(root); //验证以当前root为根节点的子树是否是BST，是的话则统计结点数
        return Math.max(largestBSTSubtree(root.left), largestBSTSubtree(root.right));
    }

    public boolean isValid(TreeNode root, Integer min, Integer max) { //验证以当前结点为根的树是否为BST
        if (root == null) return true;
        if (min != null && min >= root.val) return false;
        if (max != null && max <= root.val) return false;
        return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
    }

    public int countNode(TreeNode root) { //统计以当前结点为根的树的大小
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        return 1 + countNode(root.left) + countNode(root.right);
    }

public int minCost(int[][] costs) {
    if(costs==null||costs.length==0){
        return 0;
    }
    for(int i=1; i<costs.length; i++){  //DP
        costs[i][0] += Math.min(costs[i-1][1],costs[i-1][2]);
        costs[i][1] += Math.min(costs[i-1][0],costs[i-1][2]);
        costs[i][2] += Math.min(costs[i-1][1],costs[i-1][0]);
    }
    int n = costs.length-1;
    return Math.min(Math.min(costs[n][0], costs[n][1]), costs[n][2]);
}

     5
    / \
   2   6
  / \
 1   3

public int find(int[] roots, int id) {
    while(roots[id] != id) {
        roots[id] = roots[roots[id]];  // optional: path compression
        id = roots[id];
    }
    return id;
}

    List<Integer> list = new ArrayList<Integer>();
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        if(root == null)
            return list;
        // Add the root to the result list
            list.add(root.val);
        // perform left boundary traversal
            leftBoundary(root.left);
        // Collect the leaf nodes of the left subtree
            collectLeafNodes(root.left);
        // Collect the leaf nodes of the right subtree
            collectLeafNodes(root.right);
        // perform right boundary traversal
            rightBoundary(root.right);
        
        return list;
    }
    
    public void leftBoundary(TreeNode root) {
        if(root != null){
            // print all the left nodes first ,if left is not there print the right nodes, if its a leaf node skip it
            if(root.left != null){
                // first add the result and then recurse call to maintain the top-down order
                list.add(root.val);
                leftBoundary(root.left);
            }else if(root.right != null){
                // first add the result and then recurse call to maintain the top-down order
                list.add(root.val);
                leftBoundary(root.right);           
            }
        }
    }
    
    public void rightBoundary(TreeNode root) {
        if(root != null){
            // print all the right nodes first ,if right is not there print the left nodes, if its a leaf node skip it
            if(root.right != null){
                // first recurse call then add to result to maintain the bottom-up order
                rightBoundary(root.right);
                list.add(root.val);
            }else if(root.left != null){
                   // first recurse call then add to result to maintain the bottom-up order
                rightBoundary(root.left); 
                list.add(root.val);          
            }
        }
    }
    
    public void collectLeafNodes(TreeNode root){
        if(root != null){
            // go to the left most depth
            collectLeafNodes(root.left);
            if(root.left == null && root.right == null)
                list.add(root.val);
            
            // go to the right half, and repeat going to its leftmost end
            collectLeafNodes(root.right);
        }
    }

    public void cleanRoom(Robot robot) {
        // A number can be added to each visited cell
        // use string to identify the class
        Set<String> set = new HashSet<>();
        int cur_dir = 0;   // 0: up, 90: right, 180: down, 270: left
        backtrack(robot, set, 0, 0, 0);
    }

    public void backtrack(Robot robot, Set<String> set, int i, int j, int cur_dir) {
	String tmp = i + "->" + j;
	if(set.contains(tmp)) 
	     return;
	        
	robot.clean();
	set.add(tmp);
	
	 for(int n = 0; n < 4; n++) {
	        // the robot can to four directions, we use right turn
	    	if(robot.move()) {
	    		// can go directly. Find the (x, y) for the next cell based on current direction
	    		int x = i, y = j;
	    		switch(cur_dir) {  //还是按照当前既定的方向前进
	    			case 0:
	    				// go up, reduce i
	    				x = i-1;
	    				break;
	    			case 90:
	    				// go right
	    				y = j+1;
	    				break;
	    			case 180:
	    				// go down
	    				x = i+1;
	    				break;
	    			case 270:
	    				// go left
	    				y = j-1;
	    				break;
	    			default:
	    				break;
	    		}
	
	    	        backtrack(robot, set, x, y, cur_dir);  //更新坐标后，方向并未改变
	                // go back to the starting position，因为要遍历上下左右所有方向
			robot.turnLeft();
	    		robot.turnLeft();
	    		robot.move();
	    		robot.turnRight();
	    		robot.turnRight();
	    	} 
	    	// turn to next direction
	    	robot.turnRight();
	    	cur_dir += 90;
	    	cur_dir %= 360;
	    }
    }

    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if(s.length() < 1) return 0;
        HashMap<Character,Integer> index = new HashMap<Character,Integer>(); //key是当前窗口内的字符，value是该字符最后一次出现的位置
        int lo = 0;
        int hi = 0;
        int maxLength = 0;  //结果变量
        while(hi < s.length()) {
        		//注意下边的两个if语句是并列的，假如新加入的字符是之前出现过的，map的长度并不改变，lo不变，hi+1
            if(index.size() <= 2) {
                char c = s.charAt(hi);
                index.put(c, hi);
                hi++;
            }
            if(index.size() > 2) {  //删去最早出现的字符，并更新lo值
                int leftMost = s.length();
                for(int i : index.values()) {
                    leftMost = Math.min(leftMost,i);
                }
                char c = s.charAt(leftMost);
                index.remove(c);
                lo = leftMost+1;
            }
            maxLength = Math.max(maxLength, hi-lo);
        }
        return maxLength;
    }

    public void reverseWords(char[] s) {
        // Three step to reverse
        // 1, reverse the whole sentence，保证每个单词在reverse前占用的空间是正确的，即eulb对应blue的位置
        reverse(s, 0, s.length - 1);
        // 2, reverse each word
        int start = 0;
        int end = -1;
        for (int i = 0; i < s.length; i++) {
            if (s[i] == ' ') {
                reverse(s, start, i - 1);
                start = i + 1;
            }
        }
        // 3, reverse the last word, if there is only one word this will solve the corner case
        reverse(s, start, s.length - 1);
    }

    public void reverse(char[] s, int start, int end) {
        while (start < end) {
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;
            start++;
            end--;
        }
    }

public int findMaxConsecutiveOnes(int[] nums) {
    if(nums == null || nums.length == 0)
        return 0;
    int res = 0, preCnt = 0, curCnt = 0;
    for (int i = 0; i < nums.length; i++) {
        //这里不判断当前i指向的数字是否为1，均将curCnt加一，是因为题目允许翻转一个0，当当前的数字是0时，由下面的if语句handle
        curCnt++; //该思路是把所有翻转的1都归咎到前半段上
        if (nums[i] == 0) {
            preCnt = curCnt; //如果nums=[1,1,1,0,1,1],当i=3时，preCnt是4，curCnt是0; 如果nums=[1,1,1,0,0,1], i=4，那么此时preCnt=1, curCnt=0
            curCnt = 0;
        }
        res = Math.max(res, preCnt + curCnt);
    }
    return res;
}

public List<List<String>> groupStrings(String[] strings) {
    List<List<String>> result = new ArrayList<List<String>>();
    Map<String, List<String>> map = new HashMap<String, List<String>>(); //map的key就是上面的类型，如'abc'
    for (String str : strings) {
        int offset = str.charAt(0) - 'a'; //计算偏移量
        String key = "";
        //下面计算当前字符串str的类型
        for (int i = 0; i < str.length(); i++) {
            char c = (char) (str.charAt(i) - offset);
            if (c < 'a') {
                c += 26;
            }
            key += c;
        }
        if (!map.containsKey(key)) { //看看之前是否有该类型出现过
            List<String> list = new ArrayList<String>();
            map.put(key, list);
        }
        map.get(key).add(str);
    }
    for (String key : map.keySet()) { //整理成符合题目要求格式的结果集
        List<String> list = map.get(key);
        Collections.sort(list); //对每个类型的list进行字母序排序
        result.add(list);
    }
    return result;
}

public TreeNode str2tree(String s) {
    // Base case
    if (s.length() == 0) return null; //空结点

    // Create root
    int i = 0, j = 0;
    while (j < s.length() && (Character.isDigit(s.charAt(j)) || s.charAt(j) == '-')) j++;  //可能树节点的值为1234，多位数字
    TreeNode root = new TreeNode(Integer.parseInt(s.substring(i, j)));

    //到该位置，j指向的应该是最外层左括号的索引

    // Left child
    if (j < s.length()) {
        i = j; //当前i指向的是下一层左子树左括号的位置
        int count = 1; //count计算括号未匹配的数量，1代表初始时为左括号
        while (j + 1 < s.length() && count != 0) { //count=0代表所有括号均已匹配，下一层的遍历结束，进行深层次递归处理
            j++; //此时指向下一层的第一个数字
            if (s.charAt(j) == ')') count--; //右括号count--
            if (s.charAt(j) == '(') count++; //左括号count++
        }
        root.left = str2tree(s.substring(i + 1, j)); // i+1才是下一层数字真正开始的地方，j现在指向下一层左子树的右括号位置
    }

    j++; //j现在指向下一层右子树的左括号位置
    // Right child
    if (j < s.length()) {
        root.right = str2tree(s.substring(j + 1, s.length() - 1));
    }

    return root;
}

public int depthSumInverse(List<NestedInteger> nestedList) {
    int prevSum = 0, totalSum = 0; // preSum代表当前层以上各层的数字之和，totalSum代表到目前层为止的所有数字和
    Queue<NestedInteger> queue = new LinkedList<>();
    for (NestedInteger ni : nestedList) {
        queue.add(ni);
    }

    while (!queue.isEmpty()) {
        int size = queue.size(), levelSum = 0; //levelSum代表当前层的和,不考虑当前层以上各层数字的和
        for (int i = 0; i < size; i++) {
            NestedInteger current = queue.poll();
            if (current.isInteger()) {
                levelSum += current.getInteger();
            } else {
                for (NestedInteger ni: current.getList()) {
                    queue.add(ni);
                }
            }
        }
        prevSum += levelSum; // 将当前层以上各层数字的和也考虑进去
        totalSum += prevSum;
    }
    return totalSum;
}

public TreeNode upsideDownBinaryTree(TreeNode root) {
    if (root == null || root.left == null && root.right == null)
        return root;

    TreeNode newRoot = upsideDownBinaryTree(root.left); //找新的根节点

    //构建新的子树关系
    root.left.left = root.right;
    root.left.right = root;

    //将新子树的原来root结点左右子树置空
    root.left = null;
    root.right = null;

    return newRoot;
}

public List<List<Integer>> getFactors(int n) {
    List<List<Integer>> result = new ArrayList<List<Integer>>(); //结果集
    helper(result, new ArrayList<Integer>(), n, 2); //DFS函数, start从2开始，不考虑因子1及其本身
    return result;
}

public void helper(List<List<Integer>> result, List<Integer> item, int n, int start){
    if (n <= 1) {
        if (item.size() > 1) { // 判断是否为一个有效的factor combination
            result.add(new ArrayList<Integer>(item));
        }
        return;
    }

    // 尝试所有可能的factor，注意因子是从start开始尝试，这样可以保证因子是升序记录的，最终的结果不会有重复
    for (int i = start; i <= n; ++i) {
        if (n % i == 0) {
            item.add(i); //加上i
            helper(result, item, n/i, i); //注意下一层循环的起始因子值是i，而不是当前层的start，去重复
            item.remove(item.size()-1); //去掉i
        }
    }
}

public String findContestMatch(int n) {
    String[] m = new String[n];
    for (int i = 0; i < n; i++) {
        m[i] = String.valueOf(i + 1);
    }

    while (n > 1) {
        for (int i = 0; i < n / 2; i++) {
            m[i] = "(" + m[i] + "," + m[n - 1 - i] + ")"; // 注意，每次都是折半的和倒数的相对位置字符串进行拼接
        }
        n /= 2; //n也是折半二分
    }

    return m[0];
}

t: index for target string
s: index for source string
ans: results

public int shortestWay(String source, String target) {
    int t = 0; //指向target字符串的指针，只会一直前进
    int ans = 0; //结果，需要多少个source的subsequence来构成target
    while (t < target.length()) {
        int pt = t; //记录一下当前loop初始时刻t的位置

        for (int s = 0; s < source.length(); s++) {
            //因为我们是拿source的subsequence去与target进行匹配，所以尽量的最大匹配，只要保证匹配的顺序一致就可以
            //假如source字符串是ababc，匹配的是abxxc还是xxabc效果均相同
            if (t < target.length() && source.charAt(s) == target.charAt(t)) {
                t++;
            }
        }

        //假如比较完source字符串后，t没有移动，说明target中一定存在source中没有的字符
        if (t == pt) {
            return -1;
        }
        ans++;
    }

    return ans;
}

int count = 0;
public int countUnivalSubtrees(TreeNode root) {
    helper(root);
    return count;
}

private boolean helper(TreeNode node) {
    if (node == null) { //当子树为空时，默认返回true，不影响上面母树的比较
        return true;
    }
    boolean left = helper(node.left); //查看左子树是否unique
    boolean right = helper(node.right); //查看右子树是否unique
    if (left && right) { //如果左右子树都unique，则比较左右子树的值与根节点的值是否相等
        if (node.left != null && node.val != node.left.val) {
            return false;
        }
        if (node.right != null && node.val != node.right.val) {
            return false;
        }
        //若根节点、左右子树均相等，则将count+1
        count++;
        return true;
    }
    return false;
}

    public int assignBikes(int[][] workers, int[][] bikes) {
        dfs(workers, 0, bikes, new boolean[bikes.length], 0);
        return min;
    }

    int min = Integer.MAX_VALUE;  //cost
    void dfs(int[][] workers, int i, int[][] bikes, boolean[] used, int sum) {
        if (i == workers.length) {  //检查是不是所有人都已经assign了bike
            min = Math.min(min, sum);
            return;
        }

        if (sum > min) return;  // early termination

        for (int j = 0; j < bikes.length; ++j) {  //尝试将所有未使用的bike都assign给当前这个人，选取最小的cost
            if (used[j]) continue;
            used[j] = true;
            dfs(workers, i+1, bikes, used, sum + getDistance(workers[i], bikes[j]));
            used[j] = false;
        }
    }

    int getDistance(int[] worker, int[] bike) {
        return Math.abs(worker[0] - bike[0]) + Math.abs(worker[1] - bike[1]);
    }

Set<Integer> used = new HashSet<Integer>();
Queue<Integer> available = new LinkedList<Integer>();
int max;

/** Initialize your data structure here
 @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
public _379_DesignPhoneDirectory(int maxNumbers) {
    max = maxNumbers;
    for (int i = 0; i < maxNumbers; i++) {
        available.offer(i);
    }
}

/** Provide a number which is not assigned to anyone.
 @return - Return an available number. Return -1 if none is available. */
public int get() {
    Integer ret = available.poll();
    if (ret == null) {
        return -1;
    }
    used.add(ret);
    return ret;
}

/** Check if a number is available or not. */
public boolean check(int number) {
    if (number >= max || number < 0) {
        return false;
    }
    return !used.contains(number);
}

/** Recycle or release a number. */
public void release(int number) {
    if (used.remove(number)) {
        available.offer(number);
    }
}

    public int findClosestLeaf(TreeNode root, int k) {
        Map<TreeNode, TreeNode> backMap = new HashMap<>();   // store all edges that trace node back to its parent
        Queue<TreeNode> queue = new LinkedList<>();          // the queue used in BFS
        Set<TreeNode> visited = new HashSet<>();             // store all visited nodes

        // DFS: search for node whoes val == k
        TreeNode kNode = DFS(root, k, backMap); //kNode使我们寻找的结点
        queue.add(kNode);
        visited.add(kNode);

        // BFS: find the shortest path
        while(!queue.isEmpty()) {
            TreeNode curr = queue.poll();
            if(curr.left == null && curr.right == null) {
                return curr.val;
            }
            if(curr.left != null && visited.add(curr.left)) {
                queue.add(curr.left);
            }
            if(curr.right != null && visited.add(curr.right)) {
                queue.add(curr.right);
            }
            //说白了就是parent结点的方向
            if(backMap.containsKey(curr) && visited.add(backMap.get(curr))) {  // go alone the back edge
                queue.add(backMap.get(curr));
            }
        }
        return -1; // never hit
    }

    private TreeNode DFS(TreeNode root, int k, Map<TreeNode, TreeNode> backMap) {
        if(root.val == k) {
            return root;
        }
        if(root.left != null) {
            // backMap存储反向遍历的边，为了在之后从target node BFS时，从三个方向left、right、backTrace(说白了就是parent结点)进行搜索
            backMap.put(root.left, root);        // add back edge
            TreeNode left = DFS(root.left, k, backMap);
            if(left != null) return left;
        }
        if(root.right != null) {
            backMap.put(root.right, root);       // add back edge
            TreeNode right = DFS(root.right, k, backMap);
            if(right != null) return right;
        }
        return null;
    }

public String addBoldTag(String s, String[] dict) {
    boolean[] bold = new boolean[s.length()]; // bold[i]表示第i字符是否需要bold
    for (int i = 0, end = 0; i < s.length(); i++) {
        for (String word : dict) {
            if (s.startsWith(word, i)) { //利用String的API来判断从当前位置开始(inclusive)，是否有dict中的word
                end = Math.max(end, i + word.length());//end表示以字符i开头，最长能bold的位置
            }
        }
        bold[i] = end > i; //当end > i时，当前的第i个字符才能加粗
    }

    StringBuilder result = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if (!bold[i]) { //不用加粗的字符直接append
            result.append(s.charAt(i));
            continue;
        }
        int j = i;
        while (j < s.length() && bold[j]) j++; //寻找当前tag能加粗的字符串结尾位置
        result.append("<b>" + s.substring(i, j) + "</b>");
        i = j - 1;
    }
    return result.toString();
}

    class Point {
        int x,y,l;
        public Point(int _x, int _y, int _l) {x=_x;y=_y;l=_l;}
    }
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int m=maze.length, n=maze[0].length;
        int[][] length=new int[m][n]; // record length，用来存储到达maze[i][j]的最短距离
        for (int i=0;i<m*n;i++) length[i/n][i%n]=Integer.MAX_VALUE;
        int[][] dir=new int[][] {{-1,0},{0,1},{1,0},{0,-1}};
        PriorityQueue<Point> list=new PriorityQueue<>((o1,o2)->o1.l-o2.l); // using priority queue，按距离远近进行排序
        list.offer(new Point(start[0], start[1], 0));
        while (!list.isEmpty()) {
            Point p=list.poll();
            if (length[p.x][p.y]<=p.l) continue; // if we have already found a route shorter
            length[p.x][p.y]=p.l;
            for (int i=0;i<4;i++) {
                int xx=p.x, yy=p.y, l=p.l;
                while (xx>=0 && xx<m && yy>=0 && yy<n && maze[xx][yy]==0) {
                    xx+=dir[i][0];
                    yy+=dir[i][1];
                    l++; //这里说明，我们重复走原来已经走过的路程，也是需要算重叠的距离的
                }
                xx-=dir[i][0];
                yy-=dir[i][1];
                //我们并不是当(xx,yy)就是destination的时候就返回距离，而是选取全局所有情况中最短的距离返回
                l--;
                list.offer(new Point(xx, yy, l));
            }
        }
        return length[destination[0]][destination[1]]==Integer.MAX_VALUE?-1:length[destination[0]][destination[1]];
    }

[10, 19, 25, 27, 56, 63, 70, 87, 96, 97]，K = 3

9，6，2，29，7，7，17，9，1

public int newInteger(int n) {
    int ans = 0;
    int base = 1;
    while (n > 0){
	ans += n % 9 * base;
	n /= 9;
	base *= 10;
    }
    return ans;
}

    public int strobogrammaticInRange(String low, String high){
        int count = 0;
        List<String> rst = new ArrayList<String>();
        for(int n = low.length(); n <= high.length(); n++){
            rst.addAll(helper(n, n));
        }
        for(String num : rst){

            if((num.length() == low.length()&&num.compareTo(low) < 0 ) ||(num.length() == high.length() && num.compareTo(high) > 0)) continue;
            count++;
        }
        return count;
    }

    private List<String> helper(int cur, int max){
        if(cur == 0) return new ArrayList<String>(Arrays.asList(""));
        if(cur == 1) return new ArrayList<String>(Arrays.asList("1", "8", "0"));

        List<String> rst = new ArrayList<String>();
        List<String> center = helper(cur - 2, max);

        for(int i = 0; i < center.size(); i++){
            String tmp = center.get(i);
            if(cur != max) rst.add("0" + tmp + "0");
            rst.add("1" + tmp + "1");
            rst.add("6" + tmp + "9");
            rst.add("8" + tmp + "8");
            rst.add("9" + tmp + "6");
        }
        return rst;
    }

//DFS
private int count = 0;
public int minTransfers(int[][] transactions) {
    Map<Integer, Integer> balance = new HashMap<>();

    for(int[] t : transactions) { //计算每个人的净利润
        balance.put(t[0], balance.getOrDefault(t[0], 0) - t[2]);
        balance.put(t[1], balance.getOrDefault(t[1], 0) + t[2]);
    }

    int[] nums = new int[balance.size()]; //将每个人的净利润存到一个数组里
    int i = 0;
    for(int val : balance.values()) {
        nums[i++] = val;
    }

    return dfs(nums, 0); //从第一个人开始遍历
}

public int dfs(int[] nums, int i) {
    while(i < nums.length && nums[i] == 0) { //对于净利润为0的人我们不需要交易直接跳过
        ++i;
    }

    if(i == nums.length) { //如果index遍历到末尾，返回0，不需要再进行额外的交易
        return 0;
    }

    int count = Integer.MAX_VALUE; //将[i,n]这个范围内的人还清债务需要最少的交易次数
    for(int j = i + 1; j < nums.length; ++j) {
        if(nums[i] * nums[j] < 0) { //当i和j有一个人挣钱有一个人欠钱
            nums[j] += nums[i]; //我们将nums[i]的债务都加到nums[j]的头上，如果nums[i]>0那么就是i帮j还钱，否则是j帮i还钱
            count = Math.min(count, dfs(nums, i + 1) + 1); //然后我们在上边交易的基础上遍历下一个人，+1代表上面一行的交易
            nums[j] -= nums[i]; //尝试所有可能的结果，将j恢复原状态
        }
    }
    return count; //返回可能的最小交易次数
}

// 核心思想就是，shuffle以后两两配对还钱交易，shuffle 1000次，找最小的交易次数
public int minTransfers(int[][] transactions) {
    if(transactions == null || transactions.length == 0) return 0;
    Map<Integer, Integer> acc = new HashMap<>();
    for(int i = 0;i<transactions.length;i++){ //计算每个人的净收入(可正可负)
        int id1 = transactions[i][0];
        int id2 = transactions[i][1];
        int m = transactions[i][2];
        acc.put(id1, acc.getOrDefault(id1, 0)-m);
        acc.put(id2, acc.getOrDefault(id2, 0)+m);
    }
    List<Integer> negs = new ArrayList<>();
    List<Integer> poss = new ArrayList<>();
    for(Integer key:acc.keySet()){ //把收入按正负分成两个集合list
        int m = acc.get(key);
        if(m == 0) continue;
        if(m<0) negs.add(-m);
        else poss.add(m);
    }
    int ans = Integer.MAX_VALUE;
    Stack<Integer> stNeg = new Stack<>(), stPos = new Stack<>();
    for(int i =0;i<1000;i++){ //shuffle 1000次
        for(Integer num:negs) stNeg.push(num);
        for(Integer num:poss) stPos.push(num);
        int cur = 0;
        while(!stNeg.isEmpty()){  //当所有欠钱的人都还清，while循环才终止
            int n = stNeg.pop();
            int p = stPos.pop();
            cur++;
            if(n == p) continue;
            if(n>p){
                stNeg.push(n-p);
            } else {
                stPos.push(p-n);
            }
        }
        ans = Math.min(ans, cur);
        Collections.shuffle(negs); //注意shuffle的是两个list，不是stack，shuffle完以后重新配对
        Collections.shuffle(poss);
    }
    return ans;
}

public int[] pourWater(int[] heights, int V, int K) {
    for(int i = 0; i < V; i++) {
        int cur = K;
        // Move left
        while(cur > 0 && heights[cur] >= heights[cur - 1]) { //注意是等于号
            cur--;
        }
        // Move right
        while(cur < heights.length - 1 && heights[cur] >= heights[cur + 1]) { //注意是等于号
            cur++;
        }
            
        /*
        当海拔高度为22211111时，K=2，那么水滴应停留在K=3处，此时三个while循环都被运行
                    ^
        */
            
        // Move left to K
        while(cur > K && heights[cur] >= heights[cur - 1]) {  //注意是等于号
            cur--;
        }
        heights[cur]++;
    }
    return heights;
}

Map<String, Integer> file = new HashMap<>(); 
    
public FileSystem() {
    file.put("", -1);
}
    
public boolean createPath(String path, int value) {
    int idx = path.lastIndexOf("/");
    String parent = path.substring(0, idx);
    if (!file.containsKey(parent)) { return false; }
    return file.putIfAbsent(path, value) == null;   
}
    
public int get(String path) {
    return file.getOrDefault(path, -1);
}

// Definition for an Interval.
class Interval {
    public int start;
    public int end;

    public Interval() {}

    public Interval(int _start,int _end) {
        start = _start;
        end = _end;
    }
};

public List<Interval> employeeFreeTime(List<List<Interval>> avails) {
    List<Interval> result = new ArrayList<>();
    List<Interval> timeLine = new ArrayList<>();
    avails.forEach(e -> timeLine.addAll(e));
    Collections.sort(timeLine, ((a, b) -> a.start - b.start));

    Interval temp = timeLine.get(0);
    for(Interval each : timeLine) {
        if(temp.end < each.start) {
            result.add(new Interval(temp.end, each.start));
            temp = each;
        }else{
            temp = temp.end < each.end ? each : temp;  //选择结束时间靠后的interval作为参照物
        }
    }
    return result;
}

    int sum = 0;
    Map<Integer, Integer> tree = new HashMap<>(); //key是level和该level的position（两个digit），value是这个node的值
    
    public int pathSum(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        
        for (int num : nums) {
            int key = num / 10;
            int value = num % 10;
            tree.put(key, value);
        }
        
        traverse(nums[0] / 10, 0);
        
        return sum;
    }
    
    private void traverse(int root, int preSum) {
        int level = root / 10;
        int pos = root % 10;
        int left = (level + 1) * 10 + pos * 2 - 1; //左子树根结点的key
        int right = (level + 1) * 10 + pos * 2; //右子树根节点的key
        
        int curSum = preSum + tree.get(root);
        
        if (!tree.containsKey(left) && !tree.containsKey(right)) { //该结点是叶子结点
            sum += curSum;
            return;
        }
        
        if (tree.containsKey(left)) traverse(left, curSum);
        if (tree.containsKey(right)) traverse(right, curSum);
    }

public boolean canConvert(String s1, String s2) {
    if (s1.equals(s2)) return true;
    Map<Character, Character> dp = new HashMap<>();
    for (int i = 0; i < s1.length(); ++i) {
        if (dp.getOrDefault(s1.charAt(i), s2.charAt(i)) != s2.charAt(i)) // 一个字母只能映射一个不同的字母，可以被多个字母映射，但不能映射多个字母
            return false;
        dp.put(s1.charAt(i), s2.charAt(i)); //存储映射关系
    }
    return new HashSet<Character>(dp.values()).size() < 26; //当映射字母为26个时，我们无法完成映射，无借用字符
}

    Map<Integer, Integer> map;
    int N;
    int res;
    public int confusingNumberII(int N) {

        map = new HashMap<>();
        map.put(0, 0);
        map.put(1, 1);
        map.put(6, 9);
        map.put(8, 8);
        map.put(9, 6);
        res = 0;
        if (N == 1000000000) {
            res++;
            N--;
        }
        
        this.N = N;
        search(0, 0);
        return res;
    }
    
    //cur永远是由0、1、6、8、9这些有效数字拼接起来的数字
    //p代表当前的digits位数，cur代表当前数字
    //下面的函数遍历所有比N小的且由0、1、6、8、9组成的数字，判断他们是否有效并计数
    private void search(int p, int cur) {
        if (p > 9 || cur > N) {
            return;
        }
        if (isConfusing(cur)) {
            res++;
        }
        for (Integer d : map.keySet()) {
            if (p == 0 && d == 0) {
                continue;
            }
            search(p + 1, cur * 10 + d); //cur是由0、1、6、8、9组成的，且cur*10+d也是由0、1、6、8、9组成的
        }
    }
    
    private boolean isConfusing(int n) {
        long rot = 0;
        int tmp = n;
        while (n > 0) {
            if(!map.containsKey(n % 10))
                return false;
            rot = rot * 10 + map.get(n % 10);
            n /= 10;
        }
        return rot != tmp;
    }

   ∅  b  d
∅  ?  ?  ?
d  ? -1 -1
b  ?  1 -1
d  ?  1  1

   ∅  b  d
∅  0 -1 -1
d  1 -1 -1
b  2  1 -1
d  3  1  1