Huahua’s Tech Road

花花酱 LeetCode 1664. Ways to Make a Fair Array

By zxi on November 22, 2020

You are given an integer array nums. You can choose exactly one index (0-indexed) and remove the element. Notice that the index of the elements may change after the removal.

For example, if nums = [6,1,7,4,1]:

Choosing to remove index 1 results in nums = [6,7,4,1].
Choosing to remove index 2 results in nums = [6,1,4,1].
Choosing to remove index 4 results in nums = [6,1,7,4].

An array is fair if the sum of the odd-indexed values equals the sum of the even-indexed values.

Return the number of indices that you could choose such that after the removal, numsis fair.

Example 1:

Input: nums = [2,1,6,4]
Output: 1
Explanation:
Remove index 0: [1,6,4] -> Even sum: 1 + 4 = 5. Odd sum: 6. Not fair.
Remove index 1: [2,6,4] -> Even sum: 2 + 4 = 6. Odd sum: 6. Fair.
Remove index 2: [2,1,4] -> Even sum: 2 + 4 = 6. Odd sum: 1. Not fair.
Remove index 3: [2,1,6] -> Even sum: 2 + 6 = 8. Odd sum: 1. Not fair.
There is 1 index that you can remove to make nums fair.

Example 2:

Input: nums = [1,1,1]
Output: 3
Explanation: You can remove any index and the remaining array is fair.

Example 3:

Input: nums = [1,2,3]
Output: 0
Explanation: You cannot make a fair array after removing any index.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴

Solution: Prefix Sum

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

C++

// Author: Huahua

class Solution {

public:

int waysToMakeFair(vector<int>& nums) {

int n = nums.size();

vector<int> odds(n + 1);

vector<int> evens(n + 1);

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

odds[i + 1] = odds[i] + (i % 2 == 1) * nums[i];

evens[i + 1] = evens[i] + (i % 2 == 0) * nums[i];

}

int ans = 0;

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

const int odd = odds[i] + (evens[n] - evens[i + 1]);

const int even = evens[i] + (odds[n] - odds[i + 1]);

ans += odd == even;

}

return ans;

}

};

花花酱 LeetCode 1663. Smallest String With A Given Numeric Value

By zxi on November 22, 2020

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.

The numeric value of a string consisting of lowercase characters is defined as the sum of its characters’ numeric values. For example, the numeric value of the string "abe" is equal to 1 + 2 + 5 = 8.

You are given two integers n and k. Return the lexicographically smallest string with length equal to n and numeric value equal to k.

Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.

Example 1:

Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.

Example 2:

Input: n = 5, k = 73
Output: "aaszz"

Constraints:

1 <= n <= 10⁵
n <= k <= 26 * n

Solution: Greedy, Fill in reverse order

Fill the entire string with ‘a’, k-=n, then fill in reverse order, replace ‘a’ with ‘z’ until not enough k left.

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

C++

// Author: Huahua

class Solution {

public:

string getSmallestString(int n, int k) {

string ans(n, 'a');

k -= n;

while (k) {

int d = min(k, 25);

ans[--n] += d;

k -= d;

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

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

ans = ['a'] * n

k -= n

i = n - 1

while k:

d = min(k, 25)

ans[i] = chr(ord(ans[i]) + d)

k -= d

i -= 1

return ''.join(ans)

花花酱 LeetCode 1662. Check If Two String Arrays are Equivalent

By zxi on November 22, 2020

Given two string arrays word1 and word2, returntrue if the two arrays represent the same string, and false otherwise.

A string is represented by an array if the array elements concatenated in order forms the string.

Example 1:

Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.

Example 2:

Input: word1 = ["a", "cb"], word2 = ["ab", "c"]
Output: false

Example 3:

Input: word1  = ["abc", "d", "defg"], word2 = ["abcddefg"]
Output: true

Constraints:

1 <= word1.length, word2.length <= 10³
1 <= word1[i].length, word2[i].length <= 10³
1 <= sum(word1[i].length), sum(word2[i].length) <= 10³
word1[i] and word2[i] consist of lowercase letters.

Solution1: Construct the string

Time complexity: O(l1 + l2)
Space complexity: O(l1 + l2)

C++

class Solution {

public:

bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {

string s1, s2;

for (const string& w1 : word1) s1 += w1;

for (const string& w2 : word2) s2 += w2;

return s1 == s2;

}

};

Solution 2: Pointers

Time complexity: O(l1 + l2)
Space complexity: O(1)

C++

class Solution {

public:

bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {

int i1 = 0, j1 = 0;

int i2 = 0, j2 = 0;

while (i1 < word1.size() || i2 < word2.size()) {

char c1 = i1 < word1.size() ? word1[i1][j1++] : '\0';

char c2 = i2 < word2.size() ? word2[i2][j2++] : '\0';

if (c1 != c2) return false;

if (i1 < word1.size() && j1 == word1[i1].length())

++i1, j1 = 0;

if (i2 < word2.size() && j2 == word2[i2].length())

++i2, j2 = 0;

}

return true;

}

};

花花酱 Min Heap SP21

By zxi on November 18, 2020

C++

// Author: Huahua

#include <assert.h>

#include <iostream>

#include <vector>

using namespace std;

class MinHeap {

public:

// Return the min element.

int peek() const { return data_[0]; }

// Extract the min element.

int pop() {

// Swap the min element with the last one. O(1)

swap(data_.back(), data_[0]);

// Get the min element. O(1)

int min_el = data_.back();

// Evict the min element. O(1)

data_.pop_back();

// Maintain heap property. θ(logn)

heapifyDown(0);

return min_el;

}

// Add a new element to the heap.

void push(int key) {

// Add the element to the end of the array. O(1)

data_.push_back(key);

// Maintain heap property. θ(logn)

heapifyUp(data_.size() - 1);

}

// Return the size of the heap.

int size() const { return data_.size(); }

private:

void heapifyUp(int index) {

// Stop at root.

if (index == 0) return;

int parent = (index - 1) / 2;

// Stop if greater or euqal to parent.

if (data_[index] >= data_[parent]) return;

// Swap with parent.

swap(data_[index], data_[parent]);

// Continue heapifyUp on parent.

heapifyUp(parent);

}

void heapifyDown(int index) {

int left = index * 2 + 1;

int right = index * 2 + 2;

// Stop if has no left child.

if (left >= data_.size()) return;

// Get the min child.

int min_child =

right < data_.size() && data_[right] < data_[left] ? right : left;

// Stop if less or euqal to min child.

if (data_[index] <= data_[min_child])

return;

// Swap with min child.

swap(data_[index], data_[min_child]);

// Continue heapifyDown on min_child.

heapifyDown(min_child);

}

vector<int> data_;

};

int main() {

vector<int> data{5,1,3,5,3,4,3,7};

MinHeap heap;

for (int x : data)

heap.push(x);

vector<int> output;

while (heap.size())

output.push_back(heap.pop());

assert(output == vector<int>({1,3,3,3,4,5,5,7}));

}

Python3

# Author: Huahua

class MinHeap:

def __init__(self, data = None):

self.data = list(data) if data else []

for i in range((len(self.data)) // 2, -1, -1):

self.heapifyDown(i)

def push(self, key):

self.data.append(key)

self.heapifyUp(len(self.data) - 1)

def pop(self):

self.swap(0, -1)

min_el = self.data.pop()

self.heapifyDown(0)

return min_el

def size(self):

return len(self.data)

def swap(self, i, j):

self.data[i], self.data[j] = self.data[j], self.data[i]

def heapifyDown(self, i):

smallest = i

for c in [2 * i + 1, 2 * i + 2]:

if c < self.size() and self.data[c] < self.data[smallest]: smallest = c

if smallest != i:

self.swap(i, smallest)

self.heapifyDown(smallest)

def heapifyUp(self, i):

if i == 0: return

parent = (i - 1) // 2

if self.data[i] >= self.data[parent]: return

self.swap(i, parent)

self.heapifyUp(parent)

def test():

data = [5,1,3,5,3,4,3,7]

heap = MinHeap()

for x in data: heap.push(x)

output = []

while heap.size():

output.append(heap.pop())

assert output == sorted(data)

def testBuildHeap():

data = [5,1,3,5,3,4,3,7]

heap = MinHeap(data)

output = []

while heap.size():

output.append(heap.pop())

assert output == sorted(data)

def main():

test()

testBuildHeap()

if __name__ == '__main__':

main()

花花酱 LeetCode 1658. Minimum Operations to Reduce X to Zero

By zxi on November 14, 2020

You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.

Return the minimum number of operations to reduce x to exactly 0 if it’s possible, otherwise, return -1.

Example 1:

Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.

Example 2:

Input: nums = [5,6,7,8,9], x = 4
Output: -1

Example 3:

Input: nums = [3,2,20,1,1,3], x = 10
Output: 5
Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴
1 <= x <= 10⁹

Solution1: Prefix Sum + Hashtable

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

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<int>& nums, int x) {

const int n = nums.size();

vector<int> l(n), r(n);

unordered_map<int, int> ml, mr;

ml[0] = mr[0] = -1;

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

l[i] = nums[i] + (i > 0 ? l[i - 1] : 0);

r[i] = nums[n - i - 1] + (i > 0 ? r[i - 1]: 0);

ml[l[i]] = mr[r[i]] = i;

}

int ans = INT_MAX;

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

int s1 = x - l[i];

auto it1 = mr.find(s1);

if (it1 != mr.end()) ans = min(ans, i + 1 + it1->second + 1);

int s2 = x - r[i];

auto it2 = ml.find(s2);

if (it2 != ml.end()) ans = min(ans, i + 1 + it2->second + 1);

}

return ans > n ? -1 : ans;

}

};

Solution2: Sliding Window

Find the longest sliding window whose sum of elements equals sum(nums) – x
ans = n – window_size

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

C++

// Author: Huahua

class Solution {

public:

int minOperations(vector<int>& nums, int x) {

const int n = nums.size();

int target = accumulate(begin(nums), end(nums), 0) - x;

int ans = INT_MAX;

for (int s = 0, l = 0, r = 0; r < n; ++r) {

s += nums[r];

while (s > target && l <= r) s -= nums[l++];

if (s == target) ans = min(ans, n - (r - l + 1));

}

return ans > n ? -1 : ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1664. Ways to Make a Fair Array

Solution: Prefix Sum

C++

花花酱 LeetCode 1663. Smallest String With A Given Numeric Value

Solution: Greedy, Fill in reverse order

C++

Python3

花花酱 LeetCode 1662. Check If Two String Arrays are Equivalent

Solution1: Construct the string

C++

Solution 2: Pointers

C++

花花酱 Min Heap SP21

C++

Python3

花花酱 LeetCode 1658. Minimum Operations to Reduce X to Zero

Solution1: Prefix Sum + Hashtable

C++

Solution2: Sliding Window

C++