LIKE CODING: 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

就是三六零

Monday, November 30, 2020

LeetCode [934] Shortest Bridge

934. Shortest Bridge

Medium

In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)

Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.

Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)

Example 1:

Input: A = [[0,1],[1,0]]
Output: 1

Example 2:

Input: A = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2

Example 3:

Input: A = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1

Constraints:

2 <= A.length == A[0].length <= 100
A[i][j] == 0 or A[i][j] == 1

class Solution {
public:
int paint(vector<vector<int>>& A, int i, int j) {
    if (i < 0 || j < 0 || i == A.size() || j == A.size() || A[i][j] != 1) return 0;
    A[i][j] = 2;
    return 1 + paint(A, i + 1, j) + paint(A, i - 1, j) + paint(A, i, j + 1) + paint(A, i, j - 1);
}
bool expand(vector<vector<int>>& A, int i, int j, int cl) {
    if (i < 0 || j < 0 || i == A.size() || j == A.size()) return false;
    if (A[i][j] == 0) A[i][j] = cl + 1;
    return A[i][j] == 1;
}  
int shortestBridge(vector<vector<int>>& A) {
    for (int i = 0, found = 0; !found && i < A.size(); ++i)
        for (int j = 0; !found && j < A[0].size(); ++j) found = paint(A, i, j);
    
    for (int cl = 2; ; ++cl)
        for (int i = 0; i < A.size(); ++i)
            for (int j = 0; j < A.size(); ++j) 
                if (A[i][j] == cl && ((expand(A, i - 1, j, cl) || expand(A, i, j - 1, cl) || 
                    expand(A, i + 1, j, cl) || expand(A, i, j + 1, cl))))
                        return cl - 2;
}
};

Saturday, November 28, 2020

LeetCode [1259] Handshakes That Don't Cross

1259. Handshakes That Don't Cross

Hard

You are given an even number of people num_people that stand around a circle and each person shakes hands with someone else, so that there are num_people / 2 handshakes total.

Return the number of ways these handshakes could occur such that none of the handshakes cross.

Since this number could be very big, return the answer mod 10^9 + 7

Example 1:

Input: num_people = 2
Output: 1

Example 2:

Input: num_people = 4
Output: 2
Explanation: There are two ways to do it, the first way is [(1,2),(3,4)] and the second one is [(2,3),(4,1)].

Example 3:

Input: num_people = 6
Output: 5

Example 4:

Input: num_people = 8
Output: 14

Constraints:

2 <= num_people <= 1000
num_people % 2 == 0

class Solution {
    public int numberOfWays(int n) {
        long mod = (long)1e9 + 7;
        long[] dp = new long[n / 2 + 1];
        dp[0] = 1;
        for (int k = 1; k <= n / 2; ++k) {
            for (int i = 0; i < k; ++i) {
                dp[k] = (dp[k] + dp[i] * dp[k - 1 - i]) % mod;
            }
        }
        return (int)dp[n / 2];
    }
}