LIKE CODING: December 2020

Tuesday, December 15, 2020

[LeetCode] 379 Design Phone Directory

Design a Phone Directory which supports the following operations:

get: Provide a number which is not assigned to anyone.
check: Check if a number is available or not.
release: Recycle or release a number.

Example:

// Init a phone directory containing a total of 3 numbers: 0, 1, and 2.
PhoneDirectory directory = new PhoneDirectory(3);

// It can return any available phone number. Here we assume it returns 0.
directory.get();

// Assume it returns 1.
directory.get();

// The number 2 is available, so return true.
directory.check(2);

// It returns 2, the only number that is left.
directory.get();

// The number 2 is no longer available, so return false.
directory.check(2);

// Release number 2 back to the pool.
directory.release(2);

// Number 2 is available again, return true.
directory.check(2);

Constraints:

1 <= maxNumbers <= 10^4
0 <= number < maxNumbers
The total number of call of the methods is between [0 - 20000]

class PhoneDirectory {
    int Cap;
    Set<Integer> set0;
    Set<Integer> set1;
    /** Initialize your data structure here
        @param maxNumbers - The maximum numbers that can be stored in the phone directory. */
    public PhoneDirectory(int maxNumbers) {
        Cap = maxNumbers;
        set0 = new HashSet<>();
        set1 = new HashSet<>();
        for(int i=0; i<Cap; ++i) set0.add(i);
    }
    
    /** Provide a number which is not assigned to anyone.
        @return - Return an available number. Return -1 if none is available. */
    public int get() {
        Iterator<Integer> it = set0.iterator();
        if(!it.hasNext()){
            return -1;
        }else{
            Integer v = it.next();
            set0.remove(v);
            set1.add(v);
            return v;
        }
    }
    
    /** Check if a number is available or not. */
    public boolean check(int number) {
        return set0.contains(number);
    }
    
    /** Recycle or release a number. */
    public void release(int number) {
        set1.remove(number);
        set0.add(number);
    }
}

/**
 * Your PhoneDirectory object will be instantiated and called as such:
 * PhoneDirectory obj = new PhoneDirectory(maxNumbers);
 * int param_1 = obj.get();
 * boolean param_2 = obj.check(number);
 * obj.release(number);
 */

Friday, December 4, 2020

LeetCode [1182] Shortest Distance to Target Color

1182. Shortest Distance to Target Color

Medium

You are given an array colors, in which there are three colors: 1, 2 and 3.

You are also given some queries. Each query consists of two integers i and c, return the shortest distance between the given index i and the target color c. If there is no solution return -1.

Example 1:

Input: colors = [1,1,2,1,3,2,2,3,3], queries = [[1,3],[2,2],[6,1]]
Output: [3,0,3]
Explanation: 
The nearest 3 from index 1 is at index 4 (3 steps away).
The nearest 2 from index 2 is at index 2 itself (0 steps away).
The nearest 1 from index 6 is at index 3 (3 steps away).

Example 2:

Input: colors = [1,2], queries = [[0,3]]
Output: [-1]
Explanation: There is no 3 in the array.

Constraints:

1 <= colors.length <= 5*10^4
1 <= colors[i] <= 3
1 <= queries.length <= 5*10^4
queries[i].length == 2
0 <= queries[i][0] < colors.length
1 <= queries[i][1] <= 3

class Solution {
    public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < colors.length; i++) {
            int c = colors[i];
            map.putIfAbsent(c, new ArrayList<>());
            map.get(c).add(i);
        }
        List<Integer> ans = new ArrayList<>();
        for (int[] query : queries) {
            int index = query[0];
            int c = query[1];
            if (!map.containsKey(c)) {
                ans.add(-1);
            } else {
                ans.add(binarySearch(index, map.get(c)));
            }
        }
        return ans;
    }
    
    public int binarySearch(int index, List<Integer> list) {
        int left = 0;
        int right = list.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid) < index) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        int res = left;
        if (left - 1 >= 0 && index - list.get(left - 1) < list.get(left) - index) {
            res = left - 1;
        }
        return Math.abs(list.get(res) - index);
    }
}

YMSF

第二轮利口1182 要求pre compute o（n），follow up二维color矩阵，要求pre compute o（mn），之后query o（k），k为query次数

请问第二轮, 要怎么pre computer达到时间复杂度的要求?

是color number是constant吗?还是有甚么办法呢?

樓主二維的precompute是這樣做嗎?

比方說

[[1,2,1],

[2,1,1],

[1,1,1]]

生成 pre[color][x][y]

pre[2][][] initialize, 同色mark 0, O(xy):

[999,0,999],

[0,999,999],

[999,999,999]

pre[2][][]: Queue 存 (0,1) (1,0) bfs 四周 if not visited mark +1, 存到queue

[1,0,1],

[0,1,2],

[1,2,3]

class Solution {
    Map<Integer, TreeSet<Integer>> map = new HashMap<>();
    public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {
        for(int i=0; i<colors.length; ++i){
            int c = colors[i];
            map.computeIfAbsent(c, k->new TreeSet<>()).add(i);
        }
        List<Integer> list = new ArrayList<>();
        for(int[] q : queries){
            list.add(getDistance(q[0], q[1]));
        }
        
        return list;
    }
    
    int getDistance(int index, int color){
        if(!map.containsKey(color)) return -1;
        Integer l = map.get(color).floor(index);
        Integer r = map.get(color).ceiling(index);
        int d = Integer.MAX_VALUE;
        if(l!=null) d = Math.min(d, Math.abs(l-index));
        if(r!=null) d = Math.min(d, Math.abs(r-index));
        return d==Integer.MAX_VALUE?-1:d;
    }
}

LeetCode [360] Sort Transformed Array

360. Sort Transformed Array

Medium

Given a sorted array of integers nums and integer values a, b and c. Apply a quadratic function of the form f(x) = ax2 + bx + c to each element x in the array.

The returned array must be in sorted order.

Expected time complexity: O(n)

Example 1:

Input: nums = [-4,-2,2,4], a = 1, b = 3, c = 5
Output: [3,9,15,33]

Example 2:

Input: nums = [-4,-2,2,4], a = -1, b = 3, c = 5
Output: [-23,-5,1,7]

public class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        int n = nums.length;
        int[] sorted = new int[n];
        int i = 0, j = n - 1;
        int index = a >= 0 ? n - 1 : 0;
        while (i <= j) {
            if (a >= 0) {
                sorted[index--] = quad(nums[i], a, b, c) >= quad(nums[j], a, b, c) ? quad(nums[i++], a, b, c) : quad(nums[j--], a, b, c);
            } else {
                sorted[index++] = quad(nums[i], a, b, c) >= quad(nums[j], a, b, c) ? quad(nums[j--], a, b, c) : quad(nums[i++], a, b, c);
            }
        }
        return sorted;
    }
    
    private int quad(int x, int a, int b, int c) {
        return a * x * x + b * x + c;
    }
}

YMSF

2. given a sorted list x, a function f(x) = a*x^2+b*x+c, return a list of y = f(x) in sorted order.

要求 O(N) complexity

是有点，需要考虑下 a，b大于，小于和等于0的情况。然后用two pointer找下一个更大的数就好了

// 蠡口安全商

public int[] sortTransformedArray(int[] nums, int a, int b, int c) {

int n = nums.length, d = a >= 0 ? 1 : -1, start = (n - 1) / 2 * (d + 1);

int[] ans = new int[n];

for (int i = 0, j = n - 1; i <= j; start -= d) {

ans[start] = f(nums, a, b) * d >= f(nums[j], a, b) * d ? f(nums[i++], a, b) : f(nums[j--], a, b);

}

return ans;

}

private int f(int x, int a, int b) { // , int c

return a * x * x + b * x; // + c

}

https://leetcode.com/problems/sort-transformed-array/discuss/83317/My-easy-to-understand-Java-AC-solution-using-Two-pointers

就是三六零