853. Car Fleet

853. Car Fleet

N cars are going to the same destination along a one lane road.  The destination is target miles away.

Each car i has a constant speed speed[i] (in miles per hour), and initial position position[i] miles towards the target along the road.

A car can never pass another car ahead of it, but it can catch up to it, and drive bumper to bumper at the same speed.

The distance between these two cars is ignored - they are assumed to have the same position.

A car fleet is some non-empty set of cars driving at the same position and same speed.  Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

How many car fleets will arrive at the destination?

Example 1:

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
The cars starting at 10 and 8 become a fleet, meeting each other at 12.
The car starting at 0 doesn't catch up to any other car, so it is a fleet by itself.
The cars starting at 5 and 3 become a fleet, meeting each other at 6.
Note that no other cars meet these fleets before the destination, so the answer is 3.

Note:

1. 0 <= N <= 10 ^ 4
2. 0 < target <= 10 ^ 6
3. 0 < speed[i] <= 10 ^ 6
4. 0 <= position[i] < target
5. All initial positions are different.

---------------------------
也可以自己写个数据结构然后排序

按距离排序，计算每一辆车到达终点的时间，如果后后一辆车的时间少于前一辆，说明能追上。

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        TreeMap<Integer, Double> posToTime = new TreeMap<>(Collections.reverseOrder());
        
        for (int i = 0; i < position.length; i++) {
            posToTime.put(position[i], (target - position[i]) * 1.0 / speed[i]);
        }
        
        int fleet = 0;
        double pre = 0;
        for (double time : posToTime.values()) {
            if (time > pre) {
                fleet++;
                pre = time;
            }
        }
        
        return fleet;
    }
}

497. Random Point in Non-overlapping Rectangles

497. Random Point in Non-overlapping Rectangles

Given a list of non-overlapping axis-aligned rectangles rects, write a function pick which randomly and uniformily picks an integer point in the space covered by the rectangles.

Note:

1. An integer point is a point that has integer coordinates. 
2. A point on the perimeter of a rectangle is included in the space covered by the rectangles. 
3. ith rectangle = rects[i] = [x1,y1,x2,y2], where [x1, y1] are the integer coordinates of the bottom-left corner, and [x2, y2] are the integer coordinates of the top-right corner.
4. length and width of each rectangle does not exceed 2000.
5. 1 <= rects.length <= 100
6. pick return a point as an array of integer coordinates [p_x, p_y]
7. pick is called at most 10000 times.

Example 1:

Input: 
["Solution","pick","pick","pick"]
[[[[1,1,5,5]]],[],[],[]]
Output: 
[null,[4,1],[4,1],[3,3]]

Example 2:

Input: 
["Solution","pick","pick","pick","pick","pick"]
[[[[-2,-2,-1,-1],[1,0,3,0]]],[],[],[],[],[]]
Output: 
[null,[-1,-2],[2,0],[-2,-1],[3,0],[-2,-2]]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution's constructor has one argument, the array of rectangles rects. pick has no arguments. Arguments are always wrapped with a list, even if there aren't any.

--------------------------
按累加和来做，面积的大小就是点的个数，累加后2分搜索找到矩形并计算坐标。
要点：
1. 2分搜索，也可以用treeset
2. 计算坐标时 order / hi, order % hi 可以替换为 order % wid, order / wid, 顺序不能变。
画一个3 x 4的2维矩阵就明白了。

class Solution {

    private List<Integer> rec;
    private int[][] rects;
    private Random rand = new Random();
    private int total;
    
    public Solution(int[][] rects) {
        
        this.rects = rects;
        rec = new ArrayList<>();
        total = 0;
        for (int[] r : rects) {
            total += (r[3] - r[1] + 1) * (r[2] - r[0] + 1);
            rec.add(total);
        }
    }
    
    public int[] pick() {
        int next = rand.nextInt(total);
        int index = findRect(next);

        int hi = rects[index][3] - rects[index][1] + 1;
        int wid = rects[index][2] - rects[index][0] + 1;
        int low = rec.get(index) - wid * hi;
        int order = next - low;
        
        int[] rt = new int[2];        
        rt[0] = rects[index][0] + order / hi;
        rt[1] = rects[index][1] + order % hi;
        
        return rt;        
    }
    
    private int findRect(int p) {
        int left = 0, right = rects.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (p < rec.get(mid) && (mid == 0 || p >= rec.get(mid - 1))) {
                return mid;
            }else if (p >= rec.get(mid)) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        
        return left;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(rects);
 * int[] param_1 = obj.pick();
 */

233. Number of Digit One

233. Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

Example:

Input: 13
Output: 6 
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

-----------------------
以百位上1的个数举例，3种情况：
55023 -> 55 * 100
55123 -> 55 * 100 + 23  + 1
55523 -> (55 + 1) * 100

class Solution {
    public int countDigitOne(int n) {
        long rt = 0;
        for (long i = 1; i <= n; i *= 10) {
            long first = n / i, second = n % i;
            long mid = first % 10;
            if (mid == 0) {
                rt += first / 10 * i;
            }else if (mid == 1) {
                rt += first / 10 * i + second + 1;
            }else {
                rt += (first / 10 + 1) * i;
            }
        }
        
        return (int)rt;
    }
}

479. Largest Palindrome Product

479. Largest Palindrome Product

Find the largest palindrome made from the product of two n-digit numbers.

Since the result could be very large, you should return the largest palindrome mod 1337.

Example:

Input: 2

Output: 987

Explanation: 99 x 91 = 9009, 9009 % 1337 = 987

Note:

The range of n is [1,8].

-----------------------
又恶心！
Solution#1, 找出上下边界，做遍历。超时
Solution#2 在上下边界内遍历所有的palindrome，找出符合的

class Solution {
    public int largestPalindrome(int n) {
        if (n == 1) return 9;
        
        long upper = (long)Math.pow(10, n) - 1;
        long lower = (long)Math.pow(10, n - 1);
        long max = (long)upper * (long)upper;        
        long firstHalf = max / (long)Math.pow(10, n);
        
        boolean found = false;
        long pal = 0;
        while (!found) {
            pal = createPal(firstHalf);
            for (long i = upper; i >= lower; i--) {
                if (pal > i * i) break;
                if (pal % i == 0) {
                    found = true;
                    break;        
                }
            }
            firstHalf--;
        }
        
        return (int)(pal % 1337);
    }
    
    private long createPal(long firstHalf) {
        String s = firstHalf + new StringBuilder().append(firstHalf).reverse().toString();
        return Long.parseLong(s);
    }
}

724. Find Pivot Index

724. Find Pivot Index

Given an array of integers nums, write a method that returns the "pivot" index of this array.

We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index.

If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

Example 1:

Input: 
nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation: 
The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.
Also, 3 is the first index where this occurs.

Example 2:

Input: 
nums = [1, 2, 3]
Output: -1
Explanation: 
There is no index that satisfies the conditions in the problem statement.

Note:

The length of nums will be in the range [0, 10000].

Each element nums[i] will be an integer in the range [-1000, 1000].

----------------------
左右各存一个sum

class Solution {
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int left = 0;
        for (int i = 0; i < n; i++) {
            left += nums[i];
        }
        
        int right = 0;
        int rt = -1;
        for (int i = n - 1; i >= 0; i--) {
            left -= nums[i];
            if (left == right) rt = i;
            right += nums[i];
        }
        
        return rt;
    }
}

855. Exam Room

855. Exam Room

In an exam room, there are N seats in a single row, numbered 0, 1, 2, ..., N-1.

When a student enters the room, they must sit in the seat that maximizes the distance to the closest person.  If there are multiple such seats, they sit in the seat with the lowest number.  (Also, if no one is in the room, then the student sits at seat number 0.)

Return a class ExamRoom(int N) that exposes two functions: ExamRoom.seat() returning an int representing what seat the student sat in, and ExamRoom.leave(int p) representing that the student in seat number p now leaves the room.  It is guaranteed that any calls to ExamRoom.leave(p) have a student sitting in seat p.

Example 1:

Input: ["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]]
Output: [null,0,9,4,2,null,5]
Explanation:
ExamRoom(10) -> null
seat() -> 0, no one is in the room, then the student sits at seat number 0.
seat() -> 9, the student sits at the last seat number 9.
seat() -> 4, the student sits at the last seat number 4.
seat() -> 2, the student sits at the last seat number 2.
leave(4) -> null
seat() -> 5, the student sits at the last seat number 5.

Note:

1. 1 <= N <= 10^9
2. ExamRoom.seat() and ExamRoom.leave() will be called at most 10^4 times across all test cases.
3. Calls to ExamRoom.leave(p) are guaranteed to have a student currently sitting in seat number p.

------------------------
Solution #1 ref: https://leetcode.com/problems/exam-room/solution/
用TreeSet来存位置，seat O(n), leave O(logn)
注意要处理起始点跟终止点

class ExamRoom {
    private TreeSet<Integer> set;
    private int n;
    public ExamRoom(int N) {
        set = new TreeSet<>();
        n = N;
    }
    
    public int seat() {
        int st = 0;
        if (set.size() > 0) {
            
            int max = set.first();
            Integer pre = null;
            
            for (Integer cur : set) {
                
                if (pre != null) {
                    int dis = (cur - pre) / 2;
                    if (dis > max) {
                        max = dis;
                        st = pre + dis;
                    }
                }
                pre = cur;
            }
            
            if (n - 1 - set.last() > max) {
                st = n - 1;
            }
        }
        
        set.add(st);
        return st;
    }
    
    public void leave(int p) {
        set.remove(p);
    }
}

/**
 * Your ExamRoom object will be instantiated and called as such:
 * ExamRoom obj = new ExamRoom(N);
 * int param_1 = obj.seat();
 * obj.leave(p);
 */

Solution #2
PriorityQueue里存的是interval，按距离
要点：
1. 距离的计算方式，开头和末尾
2. interval存的是[start, mid] [mid, end], 前后2个interval会共享一个点

class ExamRoom {

    private PriorityQueue<Interval> que;
    private int n;
    public ExamRoom(int N) {
        que = new PriorityQueue<>((a, b) -> {
            if (a.dis == b.dis) return a.start - b.start;
            return b.dis - a.dis;
        });
        
        n = N;
        que.add(new Interval(-1, n));
    }
    
    public int seat() {
        Interval top = que.poll();
            
        int mid = (top.start + top.end) / 2;
        if (top.start == -1) {
            que.add(new Interval(0, top.end));
            mid = 0;
        }else if (top.end == n) {
            que.add(new Interval(top.start, n - 1));
            mid = n - 1;
        }else {
            que.add(new Interval(top.start, mid));
            que.add(new Interval(mid, top.end));
        }
        return mid;
    }
    
    public void leave(int p) {
        Interval merged = new Interval(-1,n);
        Interval head = null, tail = null;
        for (Interval top : que) {            
            if (p == 0 && top.start == 0) {
                merged.end = top.end;
                head = top;
            }else if (p == n - 1 && top.end == n - 1) {
                merged.start = top.start;
                head = top;
            }else if (top.start == p) {
                merged.end = top.end;
                head = top;
            }else if (top.end == p) {
                merged.start = top.start;
                tail = top;
            }
        }
        
        que.remove(head);
        que.remove(tail);
        que.add(new Interval(merged.start, merged.end));
    }
    
    class Interval{
        public int start;
        public int end;
        public int dis;
        public Interval(int start, int end) {
            this.start = start;
            this.end = end;
            if (start == -1) {
                dis = end;
            }else if (end == n) {
                dis = n - start - 1;
            }else {
                dis = (end - start) / 2;
            }
        }
    }
}

890. Find and Replace Pattern

890. Find and Replace Pattern

You have a list of words and a pattern, and you want to know which words in words matches the pattern.

A word matches the pattern if there exists a permutation of letters p so that after replacing every letter x in the pattern with p(x), we get the desired word.

(Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.)

Return a list of the words in words that match the given pattern. 

You may return the answer in any order.

Example 1:

Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]
Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}. 
"ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation,
since a and b map to the same letter.

Note:

• 1 <= words.length <= 50
• 1 <= pattern.length = words[i].length <= 20

----------------------

class Solution {
    public List findAndReplacePattern(String[] words, String pattern) {
        List rt = new ArrayList<>();
        for (String w : words) {
            if (helper(w, pattern)) {
                rt.add(w);
            }
        }
        
        return rt;
    }
    
    private boolean helper(String word, String p) {
        Map map = new HashMap<>();
        Set used = new HashSet<>();
        
        for (int i = 0; i < p.length(); i++) {
            char pc = p.charAt(i);
            char c = word.charAt(i);
            if (map.containsKey(pc) && map.get(pc) != c) return false;
            if (!map.containsKey(pc) && used.contains(c)) return false;
            
            map.put(pc, c);
            used.add(c);
        }
        
        return true;
    }
}