Huahua's Tech Road

花花酱 LeetCode 1551. Minimum Operations to Make Array Equal

By zxi on August 15, 2020

You have an array arr of length n where arr[i] = (2 * i) + 1 for all valid values of i (i.e. 0 <= i < n).

In one operation, you can select two indices x and y where 0 <= x, y < n and subtract 1 from arr[x] and add 1 to arr[y] (i.e. perform arr[x] -=1 and arr[y] += 1). The goal is to make all the elements of the array equal. It is guaranteed that all the elements of the array can be made equal using some operations.

Given an integer n, the length of the array. Return the minimum number of operations needed to make all the elements of arr equal.

Example 1:

Input: n = 3
Output: 2
Explanation: arr = [1, 3, 5]
First operation choose x = 2 and y = 0, this leads arr to be [2, 3, 4]
In the second operation choose x = 2 and y = 0 again, thus arr = [3, 3, 3].

Example 2:

Input: n = 6
Output: 9

Constraints:

1 <= n <= 10^4

Solution: Math

1: Find the mean (final value) of the array, assuming x, easy to show x == n
2: Compute the sum of an arithmetic progression of (x – 1) + (x – 3) + … for n // 2 pairs

e.g. n = 6
arr = [1, 3, 5, 7, 9, 11]
x = (1 + 2 * n – 1) / 2 = 6 = n
steps = (6 – 1) + (6 – 3) + (6 – 5) = (n // 2) * (n – (1 + n – 1) / 2) = (n // 2) * (n – n // 2) = 3 * 3 = 9

e.g. n = 5
arr = [1,3,5,7,9]
x = (1 + 2 * n – 1) / 2 = 5 = n
steps = (5 – 1) + (5 – 3)= (n//2) * (n – n // 2) = (n // 2) * ((n + 1) // 2) = 2 * 3 = 6

Time complexity: O(1)
Space complexity: O(1)

C++

class Solution {

public:

int minOperations(int n) {

return (n / 2) * ((n + 1) / 2);

}

};

花花酱 LeetCode 1550. Three Consecutive Odds

By zxi on August 15, 2020

Given an integer array arr, return true if there are three consecutive odd numbers in the array. Otherwise, return false.

Example 1:

Input: arr = [2,6,4,1]
Output: false
Explanation: There are no three consecutive odds.

Example 2:

Input: arr = [1,2,34,3,4,5,7,23,12]
Output: true
Explanation: [5,7,23] are three consecutive odds.

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000

Solution: Counting

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

C++

class Solution {

public:

bool threeConsecutiveOdds(vector<int>& arr) {

int count = 0;

for (int x : arr) {

if (x & 1) {

if (++count == 3) return true;

} else {

count = 0;

}

return false;

}

};

花花酱 LeetCode 1547. Minimum Cost to Cut a Stick

By zxi on August 11, 2020

Given a wooden stick of length n units. The stick is labelled from 0 to n. For example, a stick of length 6 is labelled as follows:

Given an integer array cuts where cuts[i] denotes a position you should perform a cut at.

You should perform the cuts in order, you can change the order of the cuts as you wish.

The cost of one cut is the length of the stick to be cut, the total cost is the sum of costs of all cuts. When you cut a stick, it will be split into two smaller sticks (i.e. the sum of their lengths is the length of the stick before the cut). Please refer to the first example for a better explanation.

Return the minimum total cost of the cuts.

Example 1:

Input: n = 7, cuts = [1,3,4,5]
Output: 16
Explanation: Using cuts order = [1, 3, 4, 5] as in the input leads to the following scenario:

The first cut is done to a rod of length 7 so the cost is 7. The second cut is done to a rod of length 6 (i.e. the second part of the first cut), the third is done to a rod of length 4 and the last cut is to a rod of length 3. The total cost is 7 + 6 + 4 + 3 = 20.
Rearranging the cuts to be [3, 5, 1, 4] for example will lead to a scenario with total cost = 16 (as shown in the example photo 7 + 4 + 3 + 2 = 16).

Example 2:

Input: n = 9, cuts = [5,6,1,4,2]
Output: 22
Explanation: If you try the given cuts ordering the cost will be 25.
There are much ordering with total cost <= 25, for example, the order [4, 6, 5, 2, 1] has total cost = 22 which is the minimum possible.

Constraints:

2 <= n <= 10^6
1 <= cuts.length <= min(n - 1, 100)
1 <= cuts[i] <= n - 1
All the integers in cuts array are distinct.

Solution: Range DP

dp[i][j] := min cost to finish the i-th cuts to the j-th (in sorted order)
dp[i][j] = r – l + min(dp[i][k – 1], dp[k + 1][j]) # [l, r] is the current stick range.

Time complexity: O(n^3)
Space complexity: O(n^2)

C++

class Solution {

public:

int minCost(int n, vector<int>& cuts) {

const int kInf = 1e9;

sort(begin(cuts), end(cuts));

const int c = cuts.size();

vector<vector<int>> cost(c + 1, vector<int>(c + 1, kInf));

// Min cost to finish i-th cuts to the j-th cut with stick in range [l, r].

function<int(int, int, int, int)> dp = [&](int i, int j, int l, int r) {

if (i > j) return 0; // Done

if (i == j) return r - l; // One cut, the length of the stick.

if (cost[i][j] != kInf) return cost[i][j];

int& ans = cost[i][j];

for (int k = i; k <= j; ++k)

ans = min(ans, r - l

+ dp(i, k - 1, l, cuts[k])

+ dp(k + 1, j, cuts[k], r));

return ans;

};

return dp(0, c - 1, 0, n);

}

};

Java

class Solution {

public int minCost(int n, int[] cuts) {

Arrays.sort(cuts);

final int c = cuts.length;

int[][] dp = new int[c][c];

return solve(dp, cuts, 0, c - 1, 0, n);

}

private int solve(int[][] dp, int[] cuts, int i, int j, int l, int r) {

if (i > j) return 0;

if (i == j) return r - l;

if (dp[i][j] != 0) return dp[i][j];

int ans = Integer.MAX_VALUE;

for (int k = i; k <= j; ++k)

ans = Math.min(ans, r - l

+ solve(dp, cuts, i, k - 1, l, cuts[k])

+ solve(dp, cuts, k + 1, j, cuts[k], r));

return dp[i][j] = ans;

}

Python3

class Solution:

def minCost(self, n: int, cuts: List[int]) -> int:

@lru_cache(maxsize=None)

def dp(i, j, l, r):

if i > j: return 0

if i == j: return r - l

return r - l + min(dp(i, k - 1, l, cuts[k])

+ dp(k + 1, j, cuts[k], r)

for k in range(i, j + 1))

cuts.sort()

return dp(0, len(cuts) - 1, 0, n)

花花酱 LeetCode 1546. Maximum Number of Non-Overlapping Subarrays With Sum Equals Target

By zxi on August 11, 2020

Given an array nums and an integer target.

Return the maximum number of non-empty non-overlapping subarrays such that the sum of values in each subarray is equal to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 2
Output: 2
Explanation: There are 2 non-overlapping subarrays [1,1,1,1,1] with sum equals to target(2).

Example 2:

Input: nums = [-1,3,5,1,4,2,-9], target = 6
Output: 2
Explanation: There are 3 subarrays with sum equal to 6.
([5,1], [4,2], [3,5,1,4,2,-9]) but only the first 2 are non-overlapping.

Example 3:

Input: nums = [-2,6,6,3,5,4,1,2,8], target = 10
Output: 3

Example 4:

Input: nums = [0,0,0], target = 0
Output: 3

Constraints:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
0 <= target <= 10^6

Solution: Prefix Sum + DP

Use a hashmap index to record the last index when a given prefix sum occurs.
dp[i] := max # of non-overlapping subarrays of nums[0~i], nums[i] is not required to be included.
dp[i+1] = max(dp[i], // skip nums[i]
dp[index[sum – target] + 1] + 1) // use nums[i] to form a new subarray
ans = dp[n]

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

C++

class Solution {

public:

int maxNonOverlapping(vector<int>& nums, int target) {

const int n = nums.size();

vector<int> dp(n + 1, 0); // ans at nums[i];

unordered_map<int, int> index; // {prefix sum -> last_index}

index[0] = -1;

int sum = 0;

for (int i = 0; i < n; ++i) {

sum += nums[i];

int t = sum - target;

dp[i + 1] = dp[i];

if (index.count(t))

dp[i + 1] = max(dp[i + 1], dp[index[t] + 1] + 1);

index[sum] = i;

}

return dp[n];

}

};

花花酱 LeetCode 1545. Find Kth Bit in Nth Binary String

By zxi on August 10, 2020

Given two positive integers n and k, the binary string S_n is formed as follows:

S₁ = "0"
S_i = S_i-1 + "1" + reverse(invert(S_i-1)) for i > 1

Where + denotes the concatenation operation, reverse(x) returns the reversed string x, and invert(x) inverts all the bits in x (0 changes to 1 and 1 changes to 0).

For example, the first 4 strings in the above sequence are:

S₁= "0"
S₂= "011"
S₃= "0111001"
S₄ = "011100110110001"

Return the k^th bit in S_n. It is guaranteed that k is valid for the given n.

Example 1:

Input: n = 3, k = 1
Output: "0"
Explanation: S₃ is "0111001". The first bit is "0".

Example 2:

Input: n = 4, k = 11
Output: "1"
Explanation: S₄ is "011100110110001". The 11th bit is "1".

Example 3:

Input: n = 1, k = 1
Output: "0"

Example 4:

Input: n = 2, k = 3
Output: "1"

Constraints:

1 <= n <= 20
1 <= k <= 2ⁿ - 1

Solution 1: Brute Force / Simulation

Generate the string till Sn or length >= k.

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

C++

class Solution {

public:

char findKthBit(int n, int k) {

string ans = "0";

for (int i = 2; i <= n && ans.length() < k; ++i) {

string tmp(rbegin(ans), rend(ans));

for (char& c : tmp)

c = '1' - c + '0';

ans = ans + "1" + tmp;

}

return ans[k - 1];

}

};

Solution 2: Recursion

All the strings have odd length of L = (1 << n) – 1,
Let say the center m = (L + 1) / 2
if n == 1, k should be 1 and ans is “0”.
Otherwise
if k == m, we know it’s “1”.
if k < m, the answer is the same as find(n-1, K)
if k > m, we are finding a flipped and mirror char in S(n-1), thus the answer is flip(find(n-1, L – k + 1)).

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

C++

class Solution {

public:

char findKthBit(int n, int k) {

if (n == 1) return '0';

int l = (1 << n) - 1;

if (k == (l + 1) / 2) return '1';

else if (k < (l + 1) / 2)

return findKthBit(n - 1, k);

else

return '1' - findKthBit(n - 1, l - k + 1) + '0';

}

};

Java

class Solution {

public char findKthBit(int n, int k) {

if (n == 1) return '0';

int l = (1 << n) - 1;

if (k == (l + 1) / 2) return '1';

else if (k < (l + 1) / 2)

return findKthBit(n - 1, k);

else

return (char)('1' - findKthBit(n - 1, l - k + 1) + '0');

}

Python3

class Solution:

def findKthBit(self, n: int, k: int) -> str:

if n == 1: return "0"

l = (1 << n) - 1

if k == (l + 1) / 2:

return "1"

elif k < (l + 1) / 2:

return self.findKthBit(n - 1, k)

else:

return str(1 - int(self.findKthBit(n - 1, l - k + 1)))