Press "Enter" to skip to content

Posts published in May 2019

花花酱 1054. Distant Barcodes

In a warehouse, there is a row of barcodes, where the i-th barcode is barcodes[i].

Rearrange the barcodes so that no two adjacent barcodes are equal.  You may return any answer, and it is guaranteed an answer exists.

Example 1:

Input: [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]

Example 2:

Input: [1,1,1,1,2,2,3,3]
Output: [1,3,1,3,2,1,2,1]

Note:

  1. 1 <= barcodes.length <= 10000
  2. 1 <= barcodes[i] <= 10000

Soluton: Sorting

Sort the element by their frequency in descending order. Fill the most frequent element first in even positions, if reach the end of the array, start from position 1 then 3, 5, …

Time complexity: O(nlogn)
Space complexity: O(n)

C++

Solution 2: Find the most frequent

Actually, we only need to find the most frequent element and put in the even positions, then put the rest of the groups of elements in any order.

e.g. [1, 1, 2, 2, 2, 2, 2, 3, 4]
Can be
5*2 [2 – 2 – 2 – 2 – 2]
4*1 [2 4 2 – 2 – 2 – 2]
3*1 [2 4 2 3 2 – 2 – 2]
1*2 [ 2 3 2 3 2 1 2 1 2]

if we start with any other groups rather than 2, if will become:
[3 2 2 – 2 – 2 – 2 ] which is wrong…

Time complexity: O(n)
Space complexity: O(n)

C++

花花酱 LeetCode 1052. Grumpy Bookstore Owner

Today, the bookstore owner has a store open for customers.length minutes.  Every minute, some number of customers (customers[i]) enter the store, and all those customers leave after the end of that minute.

On some minutes, the bookstore owner is grumpy.  If the bookstore owner is grumpy on the i-th minute, grumpy[i] = 1, otherwise grumpy[i] = 0.  When the bookstore owner is grumpy, the customers of that minute are not satisfied, otherwise they are satisfied.

The bookstore owner knows a secret technique to keep themselves not grumpy for X minutes straight, but can only use it once.

Return the maximum number of customers that can be satisfied throughout the day.

Example 1:

Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
Output: 16
Explanation: The bookstore owner keeps themselves not grumpy for the last 3 minutes. 
The maximum number of customers that can be satisfied = 1 + 1 + 1 + 1 + 7 + 5 = 16.

Note:

  • 1 <= X <= customers.length == grumpy.length <= 20000
  • 0 <= customers[i] <= 1000
  • 0 <= grumpy[i] <= 1

Solution: Sliding Window

Sum the costumers of non grumpy minutes, recording the max sum of the sliding window of size X.

Time complexity: O(n)
Space complexity: o(n)

C++

花花酱 LeetCode 1051. Height Checker

Students are asked to stand in non-decreasing order of heights for an annual photo.

Return the minimum number of students not standing in the right positions.  (This is the number of students that must move in order for all students to be standing in non-decreasing order of height.)

Example 1:

Input: [1,1,4,2,1,3]
Output: 3
Explanation: 
Students with heights 4, 3 and the last 1 are not standing in the right positions.

Note:

  1. 1 <= heights.length <= 100
  2. 1 <= heights[i] <= 100

Solution: Sorting

Time complexity: O(nlogn)
Space complexity: O(n)

C++

花花酱 LeetCode Weekly Contest 137

1046. Last Stone Weight

Solution: Simulation (priority_queue)

Time complexity: O(nlogn)
Space complexity: O(n)

C++

1047. Remove All Adjacent Duplicates In String

Solution: Stack / Deque

Time complexity: O(n)
Space complexity: O(n)

C++

1048. Longest String Chain

Solution: DP

dp[i] := max length of chain of (A[0] ~ A[i-1])

dp[i] = max{dp[j] + 1} if A[j] is prederrsor of A[i], 1 <= j <i

Time complexity: O(n^2*l)
Space complexity: O(n)

C++

1049. Last Stone Weight II

Solution: DP / target sum

Time complexity: O(n * S) = O(n * 100)

Space complexity: O(S) = O(100)

C++

花花酱 LeetCode 718. Maximum Length of Repeated Subarray

iven two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example 1:

Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation: 
The repeated subarray with maximum length is [3, 2, 1].

Note:

  1. 1 <= len(A), len(B) <= 1000
  2. 0 <= A[i], B[i] < 100

Solution: DP

dp[i][j] := max length of (A[0:i], B[0:j])

dp[i][j] = dp[i – 1][j – 1] + 1 if A[i-1] == B[j-1] else 0

Time complexity: O(m*n)
Space complexity: O(m*n) -> O(n)

C++ S:O(mn)

C++ S:O(min(m,n))