public class Solution {
    public int minPatches(int[] nums, int n) {
        long count = 0, absent = 1, ind = 0;
        while (absent <= n) {
            if (ind < nums.length && nums[(int) ind] <= absent) {
                absent += nums[(int) ind++];
            } else {
                ++count;
                absent += absent;
            }
        }
        return (int) count;
    }
}

public boolean hasCycle(ListNode head) {
    if(head==null) return false;
    ListNode walker = head;
    ListNode runner = head;
    while(runner.next!=null && runner.next.next!=null) {
        walker = walker.next;
        runner = runner.next.next;
        if (walker==runner) return true;
    }
    return false;
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            // 找到快指针和慢指针的汇合点，说明loop存在
            if (fast == slow){
                ListNode slow2 = head;
                // 分别从链表头和汇合点出发的指针，在loop入口处相遇
                while (slow2 != slow){
                    slow = slow.next;
                    slow2 = slow2.next;
                }
                return slow;
            }
        }
        return null;
    }
}

public class Solution {
    public int findDuplicate(int[] nums) {
        int slow=nums[0], fast=nums[nums[0]];
        while (fast != slow) {
            slow=nums[slow];
            fast=nums[nums[fast]];
        }
        fast = 0;
        while (fast != slow) {
            slow=nums[slow];
            fast=nums[fast];
        }
        return fast;
    }
}

master(A):
    n ← length[A]
    count ← 1
    seed ← A[0]
    找候选主元素，即数目最多的那个元素
    for i ← 1 to n – 1
        do if A[i] = seed
            then count ← count + 1
        else if count > 0
            then count ← count – 1
        else seed ← A[i]
    查找候选主元素是否是主元素
    count ← 0
    for i ← 0 to n – 1
        do if A[i] = seed
            then count ← count + 1
        if count > n/2
            then return seed and count
        else
            return null

public Class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> ret = new ArrayList<Integer>();
        if (nums.length == 0) return ret;
        int cand1=0,cand2=0,count1=0,count2=0;
        for (int i=0; i<nums.length; i++) {
            // if elseif可以防止cand1,cand2相同
            if (nums[i] == cand1) ++count1;
            else if (nums[i] == cand2) ++count2;
            else if (count1 == 0) { cand1 = nums[i]; count1 = 1; }
            else if (count2 == 0) { cand2 = nums[i]; count2 = 1; }
            else { --count1; --count2; }
        }
        count1=0; count2=0;
        // 判断候选元素数目是否满足条件
        for (int i=0; i < nums.length; i++) {
            if (nums[i] == cand1) ++count1;
            else if (nums[i] == cand2) ++count2;
        }
        if (count1 > nums.length/3) ret.add(cand1);
        if (count2 > nums.length/3) ret.add(cand2);
        return ret;
    }
}

Input: an integer n > 1
Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.

for i = 2, 3, 4, ..., not exceeding √n:
    if A[i] is true:
        for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n :
            A[j] := false

Output: all i such that A[i] is true.

// 构造函数
public BitSet();
public BitSet(int nbits);
// 方法
public void set(int pos); //位置pos的字位设置为true
public void set(int bitIndex, boolean value); //将指定索引处的位设置为指定的值
public void clear(int pos); //位置pos的字位设置为false
public void clear(); //将此 BitSet 中的所有位设置为 false
public int cardinality(); //返回此 BitSet 中设置为 true 的位数
public boolean get(int pos); //返回位置是pos的字位值
public void and(BitSet other); //other同该字位集进行与操作，结果作为该字位集的新值
public void or(BitSet other); //other同该字位集进行或操作，结果作为该字位集的新值
public void xor(BitSet other); //other同该字位集进行异或操作，结果作为该字位集的新值
public void andNot(BitSet set); //清除此 BitSet 中所有的位,set-用来屏蔽此 BitSet 的 BitSet
public int size(); //返回此 BitSet 表示位值时实际使用空间的位数
public int length(); //返回此 BitSet 的“逻辑大小”：BitSet 中最高设置位的索引加 1
public int hashCode(); //返回该集合Hash 码， 这个码同集合中的字位值有关
public boolean equals(Object other); //如果other中的字位同集合中的字位相同，返回true
public Object clone(); //克隆此 BitSet，生成一个与之相等的新 BitSet
public String toString(); //返回此位 set 的字符串表示形式

public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] pos = new int[primes.length], un = new int[n];
        un[0] = 1;
        for (int i=1; i<n; i++) {
            un[i] = Integer.MAX_VALUE;
            // 找当下最小的数
            for (int j=0; j<primes.length; j++)
                un[i] = Math.min(primes[j]*un[pos[j]], un[i]);
            // 去重
            for (int j=0; j<primes.length; j++)
                while (primes[j]*un[pos[j]] <= un[i]) pos[j]++;
        }
        return un[n-1];
    }
}

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m=0, n=0, ret=0;
        if ((m=matrix.length)==0 || (n=matrix[0].length)==0) return 0;
        int[] height=new int[n], left=new int[n], right=new int[n];
        for (int j=0; j<n; j++) right[j] = n-1;
        for (int i=0; i<m; i++) {
            // left_most是当前点左侧最近0点的下一位
            // right_most是当前点右侧最近0点的前一个
            // 这两个变量可以确定以当前点为中心，连续为1的长度
            int left_most = 0, right_most = n-1;
            // 要想使用上一行的left值，本行的left_most必须小于等于上一行对应位的left值
            for (int j=0; j<n; j++) {
                if (matrix[i][j]=='0') {left_most=Math.max(left_most, j+1); left[j] = 0;}
                else left[j] = Math.max(left[j], left_most);
            }
            for (int j=n-1; j>=0; j--) {
                if (matrix[i][j]=='1') right[j] = Math.min(right[j], right_most);
                else {right_most = Math.min(right_most, j-1); right[j] = n-1;}
            }
            // 更新height值，并计算以本行中每个点为底，最高的矩形的面积
            for (int j=0; j<n; j++) {
                if (matrix[i][j]=='0') height[j] = 0;
                else height[j] += 1;
                ret = Math.max(ret, (right[j]-left[j]+1)*height[j]);
            }
        }
        return ret;
    }
}

public class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return Collections.singletonList(0);
        HashMap<Integer, Set<Integer>> map = new HashMap<>();
        // 建立邻接表
        for (int[] edge : edges) {
            map.computeIfAbsent(edge[0], k->new HashSet<Integer>()).add(edge[1]);
            map.computeIfAbsent(edge[1], k->new HashSet<Integer>()).add(edge[0]);
        }
        // 叶节点集合
        List<Integer> leafs = new LinkedList<>();
        for (Integer key : map.keySet())
            if (map.get(key).size() == 1) leafs.add(key);
        while (n > 2) {
            n -= leafs.size();
            List<Integer> new_leafs = new LinkedList<>();
            for (Integer leaf : leafs) {
                // 删除指向此叶节点的边
                int box = map.get(leaf).iterator().next();
                map.get(box).remove(leaf);
                // 新的叶节点出现
                if (map.get(box).size() == 1) new_leafs.add(box);
            }
            leafs = new_leafs;
        }
        return leafs;
    }
}

public boolean increasingTriplet(int[] nums) {
    int min = Integer.MAX_VALUE, secondMin = Integer.MAX_VALUE;
    for(int num : nums){
        if(num <= min) min = num;
        else if(num < secondMin) secondMin = num;
        else if(num > secondMin) return true;
    }
    return false;
}

Twitter twitter = new Twitter();

// User 1 posts a new tweet (id = 5).
twitter.postTweet(1, 5);

// User 1's news feed should return a list with 1 tweet id -> [5].
twitter.getNewsFeed(1);

// User 1 follows user 2.
twitter.follow(1, 2);

// User 2 posts a new tweet (id = 6).
twitter.postTweet(2, 6);

// User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.getNewsFeed(1);

// User 1 unfollows user 2.
twitter.unfollow(1, 2);

// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.
twitter.getNewsFeed(1);

public class Twitter {
    HashMap<Integer, Set<Integer>> cmap;
    HashMap<Integer, List<int[]>> tw;
    int count;
    /** Initialize your data structure here. */
    public Twitter() {
        cmap = new HashMap<>();
        tw = new HashMap<>();
        count = 0;
    }

    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        int[] tmp = {count++, tweetId};
        tw.computeIfAbsent(userId, k->new LinkedList<>()).add(0,tmp);
        System.out.println(count);
    }

    /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
    public List<Integer> getNewsFeed(int userId) {
        int n = 0;
        Set<Integer> tmp = cmap.containsKey(userId)?cmap.get(userId):new HashSet<Integer>();
        List<Integer> ret = new LinkedList<>();

        PriorityQueue<List<int[]> > pq = new PriorityQueue<>(new Comparator<List<int[]>>(){

            @Override
            public int compare(List<int[]> o1, List<int[]> o2) {
                // TODO Auto-generated method stub
                return o2.get(0)[0] - o1.get(0)[0];
            }});
        if (tw.containsKey(userId) && tw.get(userId).size()>0) pq.offer(tw.get(userId));
        for (Integer it : tmp) {
            if (!tw.containsKey(it) || tw.get(it).size()==0) continue;
            pq.offer(tw.get(it));
        }
        while (pq.size()>0 && n++<10) {
            List<int[]> list = pq.poll();
            ret.add(list.get(0)[1]);
            if (list.size()>1) pq.offer(list.subList(1, list.size()));
        }
        return ret;
    }

    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    public void follow(int followerId, int followeeId) {
        if (followerId == followeeId) return;
        cmap.computeIfAbsent(followerId, k -> new HashSet<Integer>()).add(followeeId);
    }

    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    public void unfollow(int followerId, int followeeId) {
        if (followerId==followeeId || !cmap.containsKey(followerId)) return;
        Set<Integer> tmp = cmap.get(followerId);
        if (!tmp.contains(followeeId)) return;
        tmp.remove(followeeId);
    }
}