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

class Solution {

    public int findMinDifference(List<String> timePoints) {
        int[] times = new int[timePoints.size()];
        int count = 0;
        for (String time : timePoints) {
            times[count++] = convert(time);
        }
        Arrays.sort(times);
        int min = Integer.MAX_VALUE;
        for(int i = 0;i<times.length-1;i++){
            min = Math.min(min,times[i+1]-times[i]);
        }
        min = Math.min(min,Math.abs(times[0]+24*60-times[times.length-1]));
        return min;

    }

    private int convert(String time) {
        //use split will cause time waste.
        //since you know the format, can call them directly.
        int hour = 10 * (time.charAt(0) - '0') + (time.charAt(1) - '0');
        int minute = 10 * (time.charAt(3) - '0') + (time.charAt(4) - '0');
        return hour * 60 + minute;
    }


}

/**
 * Definition for singly-linked list. public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }
 */
class Solution {

    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = dummy.next;
        while (cur != null && cur.next != null) {
            ListNode sec = cur.next;
            cur.next = sec.next;
            sec.next = cur;
            pre.next = sec;
            pre = cur;
            cur = cur.next;
        }
        return dummy.next;
    }
}

class Solution {
    public String simplifyPath(String path) {
        Deque<String> stack = new LinkedList<>();
        for (String s : path.split("/")) {
            if (s.equals("..")) {
                //use poll() can avoid empty with pop()
                stack.poll();
            } else if (!s.equals("") && !s.equals(".")) {
                stack.push(s);
            }
        }
        StringBuilder sb = new StringBuilder();
        if (stack.size() == 0) {
            return "/";
        }
        while (stack.size() != 0) {
            sb.append("/").append(stack.pollLast());
        }
        return sb.toString();
    }
}

import java.util.Stack;

/**
 * Definition for a binary tree node. public class TreeNode { int val; TreeNode left; TreeNode
 * right; TreeNode(int x) { val = x; } }
 */
class BSTIterator {

    Stack<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        pushAll(root);
    }

    /**
     * @return the next smallest number
     */
    public int next() {
        TreeNode cur = stack.pop();
        //next node will always on its right.
        pushAll(cur.right);
        return cur.val;
    }

    private void pushAll(TreeNode root) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }

    /**
     * @return whether we have a next smallest number
     */
    public boolean hasNext() {
        return !stack.isEmpty();
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such: BSTIterator obj = new
 * BSTIterator(root); int param_1 = obj.next(); boolean param_2 = obj.hasNext();
 */

/**
 * Definition for singly-linked list. public class ListNode { int val; ListNode next; ListNode(int
 * x) { val = x; } }
 */
class Solution {
    //We just need to form a linked list of all odd nodes(X) and another linked list of all even nodes(Y). Afterwards, we link Y to the end of X, and return the head of X.
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode odd = head, even = head.next, evenHead = even;
        while (even != null && even.next != null) {
            odd.next = odd.next.next;
            even.next = even.next.next;
            odd = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }

}

class NumMatrix {

    int[][] sum;

    public NumMatrix(int[][] matrix) {
        
        int Y = matrix.length;
        //how to handle null matrix or matrix of size 0;
        if(Y==0) return;
        int X = matrix[0].length;
        sum = new int[Y][X];
        sum[0][0] = matrix[0][0];
        for (int x = 1; x < X; x++) {
            sum[0][x] = sum[0][x - 1] + matrix[0][x];
        }
        for (int y = 1; y < Y; y++) {
            sum[y][0] = sum[y - 1][0] + matrix[y][0];
        }
        for (int y = 1; y < Y; y++) {
            for (int x = 1; x < X; x++) {
                sum[y][x] = matrix[y][x] + sum[y - 1][x] + sum[y][x - 1] - sum[y - 1][x - 1];
            }
        }

    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if (col1 - 1 < 0 && row1 - 1 < 0) {
            return sum[row2][col2];
        }
        if (col1 - 1 < 0) {
            return sum[row2][col2] + -sum[row1 - 1][col2];
        }
        if (row1 - 1 < 0) {
            return sum[row2][col2] + -sum[row2][col1 - 1];
        }
        return sum[row2][col2] + sum[row1 - 1][col1 - 1] - sum[row1 - 1][col2] - sum[row2][col1 - 1];
    }

    
}

/**
 * Your NumMatrix object will be instantiated and called as such: NumMatrix obj = new
 * NumMatrix(matrix); int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

class Solution {

     public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for(int num:nums)sum += num;
        //sum cannot be divided by k then there's no way to split.
        if(k <= 0 || sum%k != 0)return false;
        int[] visited = new int[nums.length];
        return canPartition(nums, visited, 0, k, 0, 0, sum/k);
    }
    
    public boolean canPartition(int[] nums, int[] visited, int start_index, int k, int cur_sum, int cur_num, int target){
        //already found k-1 subsets then the rest is guarenteed to have sum k
        if(k==1)return true;
        //found a subset, and looking for next subset.
        //start from 0 to end, and look in the rest unvisited element.
        if(cur_sum == target && cur_num>0)return canPartition(nums, visited, 0, k-1, 0, 0, target);
        //will skip the loop and save lots of time.
        if(cur_sum>target) return false;
        for(int i = start_index; i<nums.length; i++){
            if(visited[i] == 0){
                visited[i] = 1;
                if(canPartition(nums, visited, i+1, k, cur_sum + nums[i], cur_num++, target))return true;
                visited[i] = 0;
            }
        }
        return false;
    }
}

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    public String largestNumber(int[] nums) {
        if (nums == null || nums.length == 0)
            return "";
        String[] s_nums = new String[nums.length];
        for (int i = 0; i < nums.length; i++)
            s_nums[i] = String.valueOf(nums[i]);

        //compare by string but not integer.
        Comparator<String> comp = new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                String s1 =o1 + o2;
                String s2 = o2 + o1;
                return s2.compareTo(s1);
            }
        };
        Arrays.sort(s_nums,comp);
        if(s_nums[0].charAt(0) == '0')
                    return "0";
        StringBuilder sb =new StringBuilder();
        for(String s: s_nums){
            sb.append(s);
        }
        return sb.toString();

    }

}

/* The knows API is defined in the parent class Relation.
      boolean knows(int a, int b); */
//no need build a graph and implement topological sort.
public class Solution extends Relation {

    public int findCelebrity(int n) {
        int candidate = 0;
        for (int i = 1; i < n; i++) {
            if(knows(candidate,i)) candidate = i;
        }

        for(int i = 0;i<n;i++){
            if(i !=candidate && (knows(candidate,i) || !knows(i,candidate)))
                return -1;
        }
        return candidate;
    }
}

class WordDictionary {

    private class Node {

        Node[] alpha;
        boolean isEnd;

        public Node() {
            alpha = new Node[26];
            isEnd = false;
        }

    }

    Node root;

    /**
     * Initialize your data structure here.
     */
    public WordDictionary() {
        root = new Node();
    }

    /**
     * Adds a word into the data structure.
     */
    public void addWord(String word) {
        char[] c_list = word.toCharArray();
        Node cur = root;
        for (char c : c_list) {
            if (cur.alpha[c - 'a'] == null) {
                cur.alpha[c - 'a'] = new Node();
            }
            cur = cur.alpha[c - 'a'];
        }
        cur.isEnd = true;
    }

    /**
     * Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
     */
    public boolean search(String word) {
        return searchUtil(word.toCharArray(), 0, root);
    }

    //main idea is when met a '.', use for loop to check.
    private boolean searchUtil(char[] word, int idx, Node cur) {
        if (idx == word.length) {
            return cur.isEnd;
        }
        if (word[idx] != '.') {
            return cur.alpha[word[idx] - 'a'] != null && searchUtil(word, idx + 1, cur.alpha[word[idx] - 'a']);
        } else {
            for (int i = 0; i < 26; i++) {
                if (cur.alpha[i] != null) {
                    if(searchUtil(word,idx+1,cur.alpha[i])){
                        return true;
                    }
                }
            }

        }
        return false;

    }
}

/**
 * Your WordDictionary object will be instantiated and called as such: WordDictionary obj = new WordDictionary(); obj.addWord(word); boolean param_2 =
 * obj.search(word);
 */

import java.util.HashMap;

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        if (numerator == 0) {
            return "0";
        }
        StringBuilder sb = new StringBuilder();
        if ((numerator > 0) ^ (denominator > 0)) {
            sb.append("-");
        }
        long num = Math.abs((long) numerator);
        long den = Math.abs((long) denominator);

        sb.append(num / den);
        num %= den;
        if (num == 0)
            return sb.toString();

        sb.append(".");
        HashMap<Long, Integer> map = new HashMap<>();
        map.put(num, sb.length());

        //num 是个余数，如果这个余数出现过，那就会出现循环，就可以在这里结束。
        while (num != 0) {
            num *= 10;
            sb.append(num / den);
            num %= den;
            if (map.containsKey(num)) {
                int idx = map.get(num);
                //map记录了余数出现的位置，插入左括号。
                sb.insert(idx, "(");
                sb.append(")");
                return sb.toString();
            } else {
                map.put(num, sb.length());
            }
        }

        return sb.toString();
    }
}

class Solution {
    //(x,y) is the location of chopper.
    //d[i] is the direction he is facing.
    //i = (i + 1) % 4 will turn right
    //i = (i + 3) % 4 will turn left
Check the final status after instructions.
    public boolean isRobotBounded(String instructions) {
        int[][] dirs = new int[][][[0, 1], [1, 0], [0, -1], [-1, 0]];
        int x = 0, y = 0;
        int dir = 0;
        //if at the end of instruction, the robot does not face north,
        //then it will go back with 4 insc.
        for (char c : instructions.toCharArray()) {
            if (c == 'R') {
                dir = (dir + 1) % 4;
            } else if (c == 'L') {
                dir = (dir + 3) % 4;
            } else {
                x += dirs[dir][0];
                y += dirs[dir][1];
            }
        }
        return (x == 0 && y == 0) || dir != 0;
    }
}

class Solution {
    //sliding window to count max.
       public int maxSatisfied(int[] customers, int[] grumpy, int X) {
        int len = customers.length;
        int sum = 0;
        int sum_grumpy = 0;
        for (int i = 0; i < len; i++) {
            if (grumpy[i] == 0) {
                sum += customers[i];
                customers[i] = 0;
            } else {
                sum_grumpy += customers[i];
            }
        }
        if (len <= X) {
            return sum_grumpy + sum;
        }
        sum_grumpy = 0;
        int max_time = Integer.MIN_VALUE;
        for (int i = 0; i < X; i++) {
            sum_grumpy += customers[i];
        }
           max_time = Math.max(sum_grumpy,max_time);
        for (int i = 1; i < len - X +1; i++) {
            sum_grumpy -= customers[i-1] ;
            sum_grumpy += customers[i+X-1];
            max_time = Math.max(sum_grumpy,max_time);
        }
        return sum+max_time;
    }
}

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

class Solution {

    List<List<String>> res;
    List<String> currLst;

    public List<List<String>> partition(String s) {
        res = new ArrayList<>();
        currLst = new ArrayList<>();
        helper(s,0);
        return res;
    }

    private void helper(String s, int left){
        if(left >= s.length() && currLst.size()!=0){
            res.add(new ArrayList<>(currLst));
            return;
        }

        for(int i = left; i<s.length();i++){
            if(isPalindrome(s,left,i)){
                if(i == left){
                    currLst.add(Character.toString(s.charAt(i)));
                }else{
                    currLst.add(s.substring(left,i+1));
                }
                helper(s,i+1);
                currLst.remove(currLst.size()-1);
            }
        }
    }


    private boolean isPalindrome(String str, int l, int r){
        if(l==r) return true;
        while(l<r){
            if(str.charAt(l)!=str.charAt(r)) return false;
            l++;r--;
        }
        return true;
    }
}

class Solution {
    public int mctFromLeafValues(int[] arr) {
        int len = arr.length;
        int[][] dp = new int[len][len];
        int[][] localMax = new int[len][len];
        for (int i = 0; i < len; i++) {
            int localmax = 0;
            for (int j = i; j < len; j++) {
                if (arr[j] > localmax) {
                    localmax = arr[j];
                }
                localMax[i][j] = localmax;
            }
        }
        for (int j = 1; j < len; j++) {
            for (int i = j-1; i>=0;i--) {
                dp[i][j] = Integer.MAX_VALUE;
                if (j == i + 1) {
                    dp[i][j] = arr[i] * arr[j];
                } else {
                    for(int k = i;k<j;k++){
                        //dp[i][j] is the sum of non-leaves node in range i and j.
                        //add up left and right tree, then add the production of max leaf node in left and right.
                        int temp = dp[i][k] + dp[k+1][j] + localMax[i][k]*localMax[k+1][j];
                        dp[i][j] = Math.min(dp[i][j],temp);
                    }
                }
            }
        }
        return dp[0][len-1];
    }
}

//Simple BFS
class Solution {

    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return -1;
        }
        int X = grid[0].length;
        int Y = grid.length;
        if (grid[0][0] == 1 || grid[Y - 1][X - 1] == 1) {
            return -1;
        }
        int res = 1;
        boolean[][] visited = new boolean[Y][X];
        int[][] dirs = new int[][][[-1, -1], [0, -1], [1, -1], [-1, 0], [1, 0], [-1, 1], [0, 1], [1, 1]];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0, 0});
        while (!queue.isEmpty()) {
            Queue<int[]> queue_temp = new LinkedList<>();
            while (!queue.isEmpty()) {
                int[] cur = queue.poll();
                if (cur[0] == Y - 1 && cur[1] == X - 1) {
                    return res;
                }
                for (int dir = 0; dir < 8; dir++) {
                    int nextX = cur[0] + dirs[dir][0];
                    int nextY = cur[1] + dirs[dir][1];
                    if (nextX >= 0 && nextX < X && nextY >= 0 && nextY < Y &&
                        !visited[nextX][nextY] && grid[nextX][nextY] == 0) {
                        visited[nextX][nextY] = true;
                        queue_temp.offer(new int[]{nextX,nextY});
                    }
                }

            }
            queue = queue_temp;
            res++;
        }
        return -1;
    }
}

class Solution {

    public int[] prisonAfterNDays(int[] cells, int N) {
        Map<String, Integer> seen = new HashMap<>();

        while (N > 0) {
            int[] cellsNext = new int[8];
            for(int i = 1;i<7;i++){
                cellsNext[i] = cells[i-1]==cells[i+1]?1:0;
            }
            seen.put(Arrays.toString(cells),N--);
            cells = cellsNext;
            String cells_str = Arrays.toString(cells);
            //met before,and the loop size is {seen.get(cells_str)-N}
            if(seen.containsKey(cells_str)){
                N %= (seen.get(cells_str)-N);
            }
        }
        return cells;
    }


}

class Solution {

    public int[] exclusiveTime(int n, List<String> logs) {
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[n];
        int prevTime = 0;
        for(String log :logs){
            String[] logArray = log.split(":");
            int idx = Integer.parseInt(logArray[0]);
            int curTime = Integer.parseInt(logArray[2]);
            if(!stack.isEmpty()){
                res[stack.peek()] +=  curTime- prevTime;
            }
            prevTime = curTime;
            if("start".equals(logArray[1])){
                stack.push(idx);
            }else {
                //why plus 1? 
                //at the end, this one second belongs to current function.
                //i.e. method 1 start from 2 , end at 5, occupy 2,3,4,5 total 4 sec.
                //so prevTime will also increase one at the end of 5 which is start of 6.
                res[stack.pop()] ++;
                prevTime++;
            }
        }
        return res;
    }
}

class Solution {

    public int snakesAndLadders(int[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return -1;
        }
        int N = board.length;
        int target = N * N;
        boolean[] visited = new boolean[N * N + 1];
        visited[1] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        int step = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                for (int j = 1; j <= 6; j++) {
                        int[] pos = numToPos(cur + j, N);
                        int next;
                        if (board[pos[0]][pos[1]] == -1) {
                            next = cur + j;
                        } else {
                            next = board[pos[0]][pos[1]];
                        }
                        if (next == target) {
                            return step;
                        }
                        //should mark next as visited.
                        //otherwise consider this:
                        //[1, 1, -1]
                        //[1, 1, 1]
                        //[-1,1, 1]
                        //it will cause infinent loop if not do so.
                        if(!visited[next]){
                            queue.offer(next);
                            visited[next] = true;
                        }
                }
            }
            step++;
        }
        return -1;
    }

    private int posToNum(int[] pos, int n) {
        int row = n - 1 - pos[0];
        int col = row % 2 == 0 ? pos[1] + 1 : n - pos[1];
        return row * n + col;
    }

    private int[] numToPos(int target, int n) {
        int row = (target - 1) / n;
        int col = (target - 1) % n;
        int x = n - 1 - row;
        int y = row % 2 == 0 ? col : n - 1 - col;
        return new int[]{x, y};
    }
}

import java.util.Arrays;

class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        int maxPile = Arrays.stream(piles).max().getAsInt();
        int low = 1, high = maxPile;
        //binary search if they can finish, if not, then increase K.
        while(low<=high){
            int mid = low + (high-low)/2;
            if(!canEatAll(piles,mid,H)){
                low = mid+1;
            }else{
                high = mid-1;
            }
        }
        return low;
    }

    private boolean canEatAll(int[] piles, int K, int H){
        int sum = 0;
        for(int num:piles){
        
            sum += num/K;
            if(num%K != 0){
                sum++;
            }
        }
        return sum <= H;
    }

}

class Solution {
    public List<List<String>> findDuplicate(String[] paths) {
        List<List<String>> res = new ArrayList<>();
        int len = paths.length;
        if(len == 0) return res;

        Map<String, Set<String>> map = new HashMap<>();
        for(String path: paths){
            String[] strs = path.split(" ");
            for(int i = 1;i<strs.length;i++){
                int idx = strs[i].indexOf("(");
                String fileName = strs[0] + "/" + strs[i].substring(0,idx);
                String content = strs[i].substring(idx);
                Set<String> fileNames = map.getOrDefault(content,new HashSet<>());
                fileNames.add(fileName);
                map.put(content,fileNames);
            }
        }
        for (String key : map.keySet()) {
            if (map.get(key).size() > 1) {
                res.add(new ArrayList<String>(map.get(key)));
            }
        }
        return res;
    }
}

import java.io.File;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.nio.file.attribute.BasicFileAttributes;

import java.security.MessageDigest;
import java.math.BigInteger;

class Directory {
    List<Directory> subDirectories;
    List<File> files;
}

public static String makeHashQuick(File file) {
    try {
        FileInputStream fileInput = new FileInputStream(file);
        byte[] data = new byte[(int) file.length()];
        fileInput.read(data);
        fileInput.close();

        MessageDigest md = MessageDigest.getInstance("MD5");
        String fileHash = new BigInteger(1, md.digest(data)).toString(16);
        return fileHash;
    } catch (IOException e) {
        throw new RuntimeException("can't read file: " + file.getAbsolutePath(), e);
    }
}

public static void findDuplicatedFilesByMD5FromFile(Map<String, List<String>> lists, File file) {
    String fileHash = makeHashQuick(file)
    List<String> list = lists.get(fileHash);
    if (list==null) {
        list = new LinkedList<String>();
        lists.put(fileHash, list);
    }
    list.add(file.getAbsolutePath());
}

public static void findDuplicatedFilesByMD5(Map<String, List<String>> lists, Directory dir) {
    for (File file: dir.files) {
        findDuplicatedFilesByMD5FromFile(lists, file);
    }
    for (Directory curDir: dir.subDirectories) {
        findDuplicatedFilesByMD5(lists, curDir);
    }
}

public static List<List<String>> storeDuplicateFiles(Directory dir) {
    List<List<String>> ret = new ArrayList<List<String>>();
    Map<String, List<String>> listsByMD5 = new HashMap<String, List<String>>();
    findDuplicatedFilesByMD5(listsByMD5, dir);
    for (List<String> list: listsByMD5) {
        if (list.size()>1) {
            ret.add(list);
        }
    }
    return ret;
}

public static void findDuplicatedFilesBySizeFromFile(Map<Integer, List<String>> lists, File file) {
    try {
        Path filePath = Paths.get(file.getAbsolutePath());
        BasicFileAttributes attr = Files.readAttributes(filePath, BasicFileAttributes.class);
        int size = attr.size();
        List<String> list = lists.get(size);
        if (list==null) {
            list = new LinkedList<String>();
            lists.put(size, list);
        }
        list.add(file.getAbsolutePath());
    } catch (IOException e) {
        throw new RuntimeException("can't read file attributes: " + file.getAbsolutePath(), e);
    }
}

public static void findDuplicatedFilesBySize(Map<Integer, List<String>> lists, Directory dir) {
    for (File file: dir.files) {
        findDuplicatedFilesBySizeFromFile(lists, file);
    }
    for (Directory curDir: dir.subDirectories) {
        findDuplicatedFilesBySize(lists, curDir);
    }
}

public static List<List<String>> storeDuplicateFiles(Directory dir) {
    List<List<String>> ret = new ArrayList<List<String>>();
    Map<Integer, List<String>> listsBySize = new HashMap<Integer, List<String>>();
    findDuplicatedFilesBySize(listsBySize, dir);
    Map<String, List<String>> listsByMD5 = new HashMap<String, List<String>>)();
    for (List<String> list: listsBySize) {
        if (list.size()>1) {
            for (String fileName: list) {
                findDuplicatedFilesByMD5FromFile(listsByMD5, new File(fileName));
            }
        }
    }
    for (List<String> list: listsByMD5) {
        if (list.size()>1) {
            ret.add(list);
        }
    }
    return ret;
}

import java.io.RandomAccessFile;

public static String makeHashLean(File infile) {
    RandomAccessFile file = new RandomAccessFile(infile, "r");
    int buffSize = 1024;
    byte[] buffer = new byte[buffSize];
    // calculate the hash of the whole file
    long offset = file.length();
    long read = 0;
    int unitsize;
    while(read<offset) {
        unitsize = (int) (((offset-read)>=buffSize)?buffSize:(offset-read));
        file.read(buffer, 0, unitsize);
        md.update(buffer, 0, unitsize);
        read += unitsize;
    }
    file.close();
    String hash = new BigInteger(1, md.digest()).toString(16);
    return hash;
}

class Directory{
     List<Directory> subDirectories;
     List<File> files;
}

/*
There are three rules to tell if a cell is a 'head':
The cell is a 'X' (board[i][j] == 'X')
No left side neighbor, or the left neighbor is a '.' (i == 0 || board[i - 1][j] == '.')
No right side neighbor, or the right neighbor is a '.' (j == 0 || board[i][j - 1] == '.')
*/
class Solution {
    public int countBattleships(char[][] board) {

        int count = 0;
        if(board==null || board.length==0 || board[0].length==0){
            return count;
        }
        for(int i = 0;i<board.length;i++){
            for(int j = 0;j<board[0].length;j++){
                if(board[i][j]=='X' && (i==0 || board[i-1][j]=='.') && (j==0 || board[i][j-1]=='.')){
                    count++;
                }
            }
        }
        return count;
    }
}

class Solution {

//greedy.
    //if odd, should have
    //i-1 <= i
    //if even, should have
    //i-1 >= i
    //for example, for i is odd:
    //if i-1 <= i, then no need to swap.
    //if i-1 > i:
    //already known i-2 >= i-1 > i
    //swap, then i-2 > i, i< i-1, wiggled.
    public void wiggleSort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {\
            if (i % 2 == 0) {
                if (nums[i - 1] < nums[i]) {
                    swap(i - 1, i, nums);
                }
            }else if(nums[i-1]>nums[i]){
                swap(i-1,i,nums);
            }
        }
    }

    private void swap(int i, int j, int[] nums) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

/*
This problem is essentially let us to find whether there are several numbers in a set which are able to sum to a specific value (in this problem, the value is sum/2).

Actually, this is a 0/1 knapsack problem, for each number, we can pick it or not. Let us assume dp[i][j] means whether the specific sum j can be gotten from the first i numbers. If we can pick such a series of numbers from 0-i whose sum is j, dp[i][j] is true, otherwise it is false.

Base case: dp[0][0] is true; (zero number consists of sum 0 is true)

Transition function: For each number, if we don't pick it, dp[i][j] = dp[i-1][j], which means if the first i-1 elements has made it to j, dp[i][j] would also make it to j (we can just ignore nums[i]). If we pick nums[i]. dp[i][j] = dp[i-1][j-nums[i]], which represents that j is composed of the current value nums[i] and the remaining composed of other previous numbers. Thus, the transition function is dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]]

============solution2===============
dp[i] : if sum i can be reached.
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]] => dp[i] = dp[i] || dp[i-num]
*/
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int num:nums){
            sum += num;
        }
        if(sum %2 != 0){
            return false;
        }
        sum /= 2;
        boolean[] dp = new boolean[sum +1];
        for(int num: nums){
            for(int i = sum;i>=num;i--){
                dp[i] = dp[i] || dp[i-num];
            }
        }
        return dp[sum];
    }
}

visit from board and turn all adjacenet cell to R, and remaining cell is X, turn R to O, that is all.
class Solution {

    int[][] dirs = new int[][][[1, 0], [-1, 0], [0, 1], [0, -1]];
    int X, Y;

    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }
        X = board[0].length;
        Y = board.length;
        boolean[][] visited = new boolean[Y][X];
        for (int i = 0; i < Y; i++) {
            if (board[i][0] == 'O') {
                helper(0, i, board, visited);
            }
            if (board[i][X - 1] == 'O') {
                helper(X - 1, i, board, visited);
            }
        }
        for (int i = 1; i < X - 1; i++) {
            if (board[0][i] == 'O') {
                helper(i, 0, board, visited);
            }
            if (board[Y - 1][i] == 'O') {
                helper(i, Y - 1, board, visited);
            }
        }

        for(int x = 0;x<X;x++){
            for(int y = 0;y<Y;y++){
                if(board[y][x]=='O'){
                    board[y][x]='X';
                }
                if(board[y][x]=='R'){
                    board[y][x]='O';
                }
            }
        }
    }

    private void helper(int x, int y, char[][] board, boolean[][] visited) {
        board[y][x] = 'R';
        visited[y][x] = true;
        for (int[] dir : dirs) {
            int next_x = x + dir[0];
            int next_y = y + dir[1];
            if (next_x >= 0 && next_x < X && next_y >= 0 && next_y < Y && !visited[next_y][next_x] && board[next_y][next_x] == 'O') {
                helper(next_x, next_y, board, visited);
            }
        }
    }
}

/*
For e.g. in case of the array [23,2,6,4,7] the running sum is [23,25,31,35,42] and the remainders are [5,1,1,5,0]. We got remainder 5 at index 0 and at index 3. That means, in between these two indexes we must have added a number which is multiple of the k. 
*/
public boolean checkSubarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();;
    //find a solution when met same %.
    int runningSum = 0;
    for (int i=0;i<nums.length;i++) {
        runningSum += nums[i];
        if (k != 0) runningSum %= k; 
        Integer prev = map.get(runningSum);
        if (prev != null) {
            if (i - prev > 1) return true;
        }
        else map.put(runningSum, i);
    }
    return false;
}

public int shortestWay(String source, String target) {
    char[] cs = source.toCharArray(), ts = target.toCharArray();
    boolean[] map = new boolean[26];
    for (int i = 0; i < cs.length; i++) 
        map[cs[i] - 'a'] = true;
    int j = 0, res = 1;
    for (int i = 0; i < ts.length; i++,j++) {
        if (!map[ts[i] - 'a']) return -1;
        while (j < cs.length && cs[j] != ts[i]) {
            j++;
        }
        if (j == cs.length) {
            j = -1;
            res++;
            i--;
        }
    }
    return res;
}

public int shortestWay(String source, String target) {
    char[] cs = source.toCharArray(), ts = target.toCharArray();
    int res = 0;
    for (int i = 0; i < ts.length; ) {
        int oriI = i;
        for (int j = 0; j < cs.length; j++) {
            if (i < ts.length && cs[j] == ts[i])
                i++;
        }
        if (i == oriI) return -1;
        res++;
    }
    return res;
}

public int shortestWay(String source, String target) {
    char[] cs = source.toCharArray(), ts = target.toCharArray();
    int res = 1;
    List<Integer>[] idx = new List[26];
    for (int i = 0; i < 26; i++) idx[i] = new ArrayList<>();
    for (int i = 0; i < cs.length; i++) idx[cs[i] - 'a'].add(i);
    int j = 0;
    for (int i = 0; i < ts.length; ) {
        List<Integer> tar = idx[ts[i] - 'a'];
        if (tar.isEmpty()) return -1;
        int k = Collections.binarySearch(tar,j);
        if (k < 0) k = -k - 1;
        if (k == tar.size()) {
            res++;
            j = 0;
        } else {
            j = tar.get(k) + 1;
            i++;
        }

    }
    return res;
}

public int shortestWay(String source, String target) {
    char[] cs = source.toCharArray(), ts = target.toCharArray();
    int[][] idx = new int[26][cs.length];
    for (int i = 0; i < cs.length; i++) idx[cs[i] - 'a'][i] = i + 1;
    for (int i = 0; i < 26; i++) {
        for (int j = cs.length - 1, pre = 0; j >= 0; j--) {
            if (idx[i][j] == 0) idx[i][j] = pre;
            else pre = idx[i][j];
        }
    }
    int res = 1, j = 0;
    for (int i = 0; i < ts.length; i++) {
        if (j == cs.length) {
            j = 0;
            res++;
        }
        if (idx[ts[i] - 'a'][0] == 0) return -1;
        j = idx[ts[i] - 'a'][j];
        if (j == 0 ) {
            res++;
            i--;
        }
    }
    return  res;
}

public int shortestWay(String source, String target) {
    char[] cs = source.toCharArray(), ts = target.toCharArray();
    int[][] idx = new int[cs.length][26];
    idx[cs.length - 1][cs[cs.length - 1] - 'a'] = cs.length; 
    for (int i = cs.length - 2; i >= 0; i--) {
        idx[i] = Arrays.copyOf(idx[i + 1],26);
        idx[i][cs[i] - 'a'] = i + 1; 
    }
    int j = 0, res = 1;
    for (int i = 0; i < ts.length; i++) {
        if (j == cs.length) {
            j = 0;
            res++;
        }
        j = idx[j][ts[i] - 'a'];
        if (idx[0][ts[i] - 'a'] == 0) return -1;
        if (j == 0) {
            res++;
            i--;
        }
    }
    return res;
}

//use Integer to store position info to avoid using board[][]
class SnakeGame {

    /** Initialize your data structure here.
     @param width - screen width
     @param height - screen height
     @param food - A list of food positions
     E.g food = [[1,1], [1,0]] means the first food is positioned at [1,1], the second is at [1,0].
     **/
    Set<Integer> set; // this copy is good for fast loop-up for eating body case
    Deque<Integer> body; // this copy is good for updating tail
    int score;
    int[][] food;
    int foodIndex;
    int width;
    int height;

    public SnakeGame(int width, int height, int[][] food) {
        this.width = width;
        this.height = height;
        this.food = food;
        set = new HashSet<>();
        set.add(0); //intially at [0][0]
        body = new LinkedList<>();
        body.offerLast(0);
    }

    /** Moves the snake.
     @param direction - 'U' = Up, 'L' = Left, 'R' = Right, 'D' = Down
     @return The game's score after the move. Return -1 if game over.
     Game over when snake crosses the screen boundary or bites its body. */
    public int move(String direction) {
        if (score == -1) {
            return -1;
        }
        int rowHead = body.peekFirst() / width;
        int colHead = body.peekFirst() % width;
        switch (direction) {
            case "U" : rowHead--;
                break;
            case "D" : rowHead++;
                break;
            case "L" : colHead--;
                break;
            default :  colHead++;
        }
        int head = rowHead * width + colHead;
        set.remove(body.peekLast()); // new head is legal to be in old tail's position, remove from set temporarily
        if (rowHead < 0 || rowHead == height || colHead < 0 || colHead == width || set.contains(head)) {
            return score = -1;
        }

        // add head for case2 and case3
        set.add(head);
        body.offerFirst(head);

        //case2: eating food, keep tail, add head
        if (foodIndex < food.length && rowHead == food[foodIndex][0] && colHead == food[foodIndex][1]) {
            set.add(body.peekLast()); // old tail does not change, so add it back to set
            foodIndex++;
            return ++score;
        }

        //case3: normal move, remove tail, add head
        body.pollLast();
        return score;
    }
}

/**
 * Your SnakeGame object will be instantiated and called as such:
 * SnakeGame obj = new SnakeGame(width, height, food);
 * int param_1 = obj.move(direction);
 */

class Solution {
    public int minIncrementForUnique(int[] A) {
        int require = 0, incSum = 0;
        Arrays.sort(A);
        for(int num:A){
            incSum += Math.max(require-num,0);
            require = Math.max(require,num)+1;
        }
        return incSum;
    }
}

/*
from Left: 
    even: head + step;
    odd:  head + step;
from right:
    even: head;
    odd:  head + step;
remaining /= 2, no matter even or odd.
when remaining is 1, head is the answer.
*/
class Solution {
    public int lastRemaining(int n) {
        int head = 1, step = 1, remaining = n;
        boolean isLeft = true;
        while (remaining != 1) {
            if(isLeft || remaining%2 != 0){
                head += step;
            }
            step *= 2;
            remaining /= 2;
            isLeft = !isLeft;
        }
        return head;
    }
}

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

class Solution {

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> tempPath = new ArrayList<>();
        tempPath.add(0);
        dfs(graph,0,tempPath,res);
        return res;
    }

    public void dfs(int[][] graph, int node, List<Integer> tempPath, List<List<Integer>> res) {
        if(node == graph.length-1){
            res.add(new ArrayList<>(tempPath));
            return;
        }
        for(int nextNode : graph[node]){
            tempPath.add(nextNode);
            dfs(graph,nextNode,tempPath,res);
            tempPath.remove(tempPath.size()-1);
        }
    }
}