LeetCode [1089] Duplicate Zeros

 1089. Duplicate Zeros

Easy

Given a fixed length array arr of integers, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written.

Do the above modifications to the input array in place, do not return anything from your function.

 

Example 1:

Input: [1,0,2,3,0,4,5,0]
Output: null
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Example 2:

Input: [1,2,3]
Output: null
Explanation: After calling your function, the input array is modified to: [1,2,3]

 

Note:

1. 1 <= arr.length <= 10000
2. 0 <= arr[i] <= 9

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { public void duplicateZeros(int[] arr) { int n = arr.length; int zeros = 0; for(int i : arr){ if(i==0) zeros++; } int n1 = n + zeros; int i=n-1, j = n1-1; while(j>=0){ int x = arr[i--]; if(x==0){//the duplicated zero if(j<n) arr[j--] = x; else j--; } if(j<n) arr[j--] = x; else j--; } } }

[LeetCode] 379 Design Phone Directory

 Design a Phone Directory which supports the following operations:

 

1. get: Provide a number which is not assigned to anyone.
2. check: Check if a number is available or not.
3. 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]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

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); */

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

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]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

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]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

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

就是三六零

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

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; } };