Huahua’s Tech Road

花花酱 LeetCode 1869. Longer Contiguous Segments of Ones than Zeros

By zxi on August 5, 2021

Given a binary string s, return true if the longest contiguous segment of 1s is strictly longer than the longest contiguous segment of 0s in s. Return false otherwise.

For example, in s = "110100010" the longest contiguous segment of 1s has length 2, and the longest contiguous segment of 0s has length 3.

Note that if there are no 0s, then the longest contiguous segment of 0s is considered to have length 0. The same applies if there are no 1s.

Example 1:

Input: s = "1101"
Output: true
Explanation:
The longest contiguous segment of 1s has length 2: "1101"
The longest contiguous segment of 0s has length 1: "1101"
The segment of 1s is longer, so return true.

Example 2:

Input: s = "111000"
Output: false
Explanation:
The longest contiguous segment of 1s has length 3: "111000"
The longest contiguous segment of 0s has length 3: "111000"
The segment of 1s is not longer, so return false.

Example 3:

Input: s = "110100010"
Output: false
Explanation:
The longest contiguous segment of 1s has length 2: "110100010"
The longest contiguous segment of 0s has length 3: "110100010"
The segment of 1s is not longer, so return false.

Constraints:

1 <= s.length <= 100
s[i] is either '0' or '1'.

Solution: Brute Force

Write a function count to count longest contiguous segment of m, return count(‘1’) > count(‘0’)

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

C++

// Author: Huahua

class Solution {

public:

bool checkZeroOnes(string s) {

auto count = [&](char m) {

int ans = 0;

int l = 0;

for (char c : s)

if (c != m) l = 0;

else ans = max(ans, ++l);

return ans;

};

return count('1') > count('0');

}

};

花花酱 LeetCode 1866. Number of Ways to Rearrange Sticks With K Sticks Visible

By zxi on August 4, 2021

There are n uniquely-sized sticks whose lengths are integers from 1 to n. You want to arrange the sticks such that exactly k sticks are visible from the left. A stick is visible from the left if there are no longer sticks to the left of it.

For example, if the sticks are arranged [1,3,2,5,4], then the sticks with lengths 1, 3, and 5 are visible from the left.

Given n and k, return the number of such arrangements. Since the answer may be large, return it modulo 10⁹ + 7.

Example 1:

Input: n = 3, k = 2
Output: 3
Explanation: [1,3,2], [2,3,1], and [2,1,3] are the only arrangements such that exactly 2 sticks are visible.
The visible sticks are underlined.

Example 2:

Input: n = 5, k = 5
Output: 1
Explanation: [1,2,3,4,5] is the only arrangement such that all 5 sticks are visible.
The visible sticks are underlined.

Example 3:

Input: n = 20, k = 11
Output: 647427950
Explanation: There are 647427950 (mod 10⁹+ 7) ways to rearrange the sticks such that exactly 11 sticks are visible.

Constraints:

1 <= n <= 1000
1 <= k <= n

Solution: DP

dp(n, k) = dp(n – 1, k – 1) + (n-1) * dp(n-1, k)

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

C++

// Author: Huahua

class Solution {

public:

int rearrangeSticks(int n, int k) {

constexpr int kMod = 1e9 + 7;

vector<vector<long>> dp(n + 1, vector<long>(k + 1));

for (int j = 1; j <= k; ++j) {

dp[j][j] = 1;

for (int i = j + 1; i <= n; ++i)

dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j] * (i - 1)) % kMod;

}

return dp[n][k];

}

};

Python3

# Author: Huahua

class Solution:

@lru_cache(maxsize=None)

def rearrangeSticks(self, n: int, k: int) -> int:

if k == 0: return 0

if k == n or n <= 2: return 1

return (self.rearrangeSticks(n - 1, k - 1) +

(n - 1) * self.rearrangeSticks(n - 1, k)) % (10**9 + 7)

花花酱 LeetCode 1865. Finding Pairs With a Certain Sum

By zxi on August 4, 2021

You are given two integer arrays nums1 and nums2. You are tasked to implement a data structure that supports queries of two types:

Add a positive integer to an element of a given index in the array nums2.
Count the number of pairs (i, j) such that nums1[i] + nums2[j] equals a given value (0 <= i < nums1.length and 0 <= j < nums2.length).

Implement the FindSumPairs class:

FindSumPairs(int[] nums1, int[] nums2) Initializes the FindSumPairs object with two integer arrays nums1 and nums2.
void add(int index, int val) Adds val to nums2[index], i.e., apply nums2[index] += val.
int count(int tot) Returns the number of pairs (i, j) such that nums1[i] + nums2[j] == tot.

Example 1:

Input
["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]
Output
[null, 8, null, 2, 1, null, null, 11]
Explanation
FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
findSumPairs.count(7); // return 8; pairs (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) make 2 + 5 and pairs (5,1), (5,5) make 3 + 4
findSumPairs.add(3, 2); // now nums2 = [1,4,5,4,5,4] 
findSumPairs.count(8); // return 2; pairs (5,2), (5,4) make 3 + 5 
findSumPairs.count(4); // return 1; pair (5,0) makes 3 + 1 
findSumPairs.add(0, 1); // now nums2 = [2,4,5,4,5,4] 
findSumPairs.add(1, 1); // now nums2 = [2,5,5,4,5,4] 
findSumPairs.count(7); // return 11; pairs (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) make 2 + 5 and pairs (5,3), (5,5) make 3 + 4

Constraints:

1 <= nums1.length <= 1000
1 <= nums2.length <= 10⁵
1 <= nums1[i] <= 10⁹
1 <= nums2[i] <= 10⁵
0 <= index < nums2.length
1 <= val <= 10⁵
1 <= tot <= 10⁹
At most 1000 calls are made to add and count each.

Solution: HashTable

Note nums1 and nums2 are unbalanced. Brute force method will take O(m*n) = O(10³*10⁵) = O(10⁸) for each count call which will TLE. We could use a hashtable to store the counts of elements from nums2, and only iterate over nums1 to reduce the time complexity.

Time complexity:

init: O(m) + O(n)
add: O(1)
count: O(m)

Total time is less than O(10⁶)

Space complexity: O(m + n)

C++

// Author: Huahua

class FindSumPairs {

public:

FindSumPairs(vector<int>& nums1,

vector<int>& nums2): nums1_(nums1), nums2_(nums2) {

for (int x : nums2_) ++freq_[x];

}

void add(int index, int val) {

if (--freq_[nums2_[index]] == 0)

freq_.erase(nums2_[index]);

++freq_[nums2_[index] += val];

}

int count(int tot) {

int ans = 0;

for (int a : nums1_) {

auto it = freq_.find(tot - a);

if (it != freq_.end()) ans += it->second;

}

return ans;

}

private:

vector<int> nums1_;

vector<int> nums2_;

unordered_map<int, int> freq_;

};

Python3

# Author: Huahua

class FindSumPairs:

def __init__(self, nums1: List[int], nums2: List[int]):

self.nums1 = nums1

self.nums2 = nums2

self.freq = Counter(nums2)

def add(self, index: int, val: int) -> None:

self.freq.subtract((self.nums2[index],))

self.nums2[index] += val

self.freq.update((self.nums2[index],))

def count(self, tot: int) -> int:

return sum(self.freq[tot - a] for a in self.nums1)

花花酱 LeetCode 1864. Minimum Number of Swaps to Make the Binary String Alternating

By zxi on August 4, 2021

Given a binary string s, return the minimum number of character swaps to make it alternating, or -1 if it is impossible.

The string is called alternating if no two adjacent characters are equal. For example, the strings "010" and "1010" are alternating, while the string "0100" is not.

Any two characters may be swapped, even if they are not adjacent.

Example 1:

Input: s = "111000"
Output: 1
Explanation: Swap positions 1 and 4: "111000" -> "101010"
The string is now alternating.

Example 2:

Input: s = "010"
Output: 0
Explanation: The string is already alternating, no swaps are needed.

Example 3:

Input: s = "1110"
Output: -1

Constraints:

1 <= s.length <= 1000
s[i] is either '0' or '1'.

Solution: Greedy

Two passes, make the string starts with ‘0’ or ‘1’, count how many 0/1 swaps needed. 0/1 swaps must equal otherwise it’s impossible to swap.

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

C++

// Author: Huahua

class Solution {

public:

int minSwaps(string s) {

auto count = [&](int m) {

vector<int> swaps(2);

for (int i = 0; i < s.length(); ++i, m ^= 1)

if (s[i] - '0' != m)

++swaps[s[i] - '0'];

return swaps[0] == swaps[1] ? swaps[0] : INT_MAX;

};

int ans = min(count(0), count(1));

return ans != INT_MAX ? ans : -1;

}

};

花花酱 LeetCode 1863. Sum of All Subset XOR Totals

By zxi on August 4, 2021

The XOR total of an array is defined as the bitwise XOR of all its elements, or 0 if the array is empty.

For example, the XOR total of the array [2,5,6] is 2 XOR 5 XOR 6 = 1.

Given an array nums, return the sum of all XOR totals for every subset of nums.

Note: Subsets with the same elements should be counted multiple times.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b.

Example 1:

Input: nums = [1,3]
Output: 6
Explanation: The 4 subsets of [1,3] are:
- The empty subset has an XOR total of 0.
- [1] has an XOR total of 1.
- [3] has an XOR total of 3.
- [1,3] has an XOR total of 1 XOR 3 = 2.
0 + 1 + 3 + 2 = 6

Example 2:

Input: nums = [5,1,6]
Output: 28
Explanation: The 8 subsets of [5,1,6] are:
- The empty subset has an XOR total of 0.
- [5] has an XOR total of 5.
- [1] has an XOR total of 1.
- [6] has an XOR total of 6.
- [5,1] has an XOR total of 5 XOR 1 = 4.
- [5,6] has an XOR total of 5 XOR 6 = 3.
- [1,6] has an XOR total of 1 XOR 6 = 7.
- [5,1,6] has an XOR total of 5 XOR 1 XOR 6 = 2.
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

Example 3:

Input: nums = [3,4,5,6,7,8]
Output: 480
Explanation: The sum of all XOR totals for every subset is 480.

Constraints:

1 <= nums.length <= 12
1 <= nums[i] <= 20

Solution 1: Brute Force

Use an array A to store all the xor subsets, for a given number x
A = A + [x ^ a for a in A]

Time complexity: O(2ⁿ)
Space complexity: O(2ⁿ)

Python3

# Author: Huahua

class Solution:

def subsetXORSum(self, nums: List[int]) -> int:

xors = [0]

for x in nums:

xors += [xor ^ x for xor in xors]

return sum(xors)

Huahua's Tech Road

花花酱 LeetCode 1869. Longer Contiguous Segments of Ones than Zeros

Solution: Brute Force

C++

花花酱 LeetCode 1866. Number of Ways to Rearrange Sticks With K Sticks Visible

Solution: DP

C++

Python3

花花酱 LeetCode 1865. Finding Pairs With a Certain Sum

Solution: HashTable

C++

Python3

花花酱 LeetCode 1864. Minimum Number of Swaps to Make the Binary String Alternating

Solution: Greedy

C++

花花酱 LeetCode 1863. Sum of All Subset XOR Totals

Solution 1: Brute Force

Python3