Huahua’s Tech Road

花花酱 LeetCode 1832. Check if the Sentence Is Pangram

By zxi on April 18, 2021

A pangram is a sentence where every letter of the English alphabet appears at least once.

Given a string sentence containing only lowercase English letters, returntrue if sentence is a pangram, or false otherwise.

Example 1:

Input: sentence = "thequickbrownfoxjumpsoverthelazydog"
Output: true
Explanation: sentence contains at least one of every letter of the English alphabet.

Example 2:

Input: sentence = "leetcode"
Output: false

Constraints:

1 <= sentence.length <= 1000
sentence consists of lowercase English letters.

Solution: Hashset

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

C++

class Solution {

public:

bool checkIfPangram(string sentence) {

unordered_set<char> s;

for (char c : sentence)

s.insert(c);

return s.size() == 26;

}

};

Python3

class Solution:

def checkIfPangram(self, sentence: str) -> bool:

return len(set(sentence)) == 26

花花酱 LeetCode 1830. Minimum Number of Operations to Make String Sorted

By zxi on April 18, 2021

You are given a string s (0-indexed). You are asked to perform the following operation on s until you get a sorted string:

Find the largest index i such that 1 <= i < s.length and s[i] < s[i - 1].
Find the largest index j such that i <= j < s.length and s[k] < s[i - 1] for all the possible values of k in the range [i, j] inclusive.
Swap the two characters at indices i - 1 and j.
Reverse the suffix starting at index i.

Return the number of operations needed to make the string sorted. Since the answer can be too large, return it modulo 10⁹ + 7.

Example 1:

Input: s = "cba"
Output: 5
Explanation: The simulation goes as follows:
Operation 1: i=2, j=2. Swap s[1] and s[2] to get s="cab", then reverse the suffix starting at 2. Now, s="cab".
Operation 2: i=1, j=2. Swap s[0] and s[2] to get s="bac", then reverse the suffix starting at 1. Now, s="bca".
Operation 3: i=2, j=2. Swap s[1] and s[2] to get s="bac", then reverse the suffix starting at 2. Now, s="bac".
Operation 4: i=1, j=1. Swap s[0] and s[1] to get s="abc", then reverse the suffix starting at 1. Now, s="acb".
Operation 5: i=2, j=2. Swap s[1] and s[2] to get s="abc", then reverse the suffix starting at 2. Now, s="abc".

Example 2:

Input: s = "aabaa"
Output: 2
Explanation: The simulation goes as follows:
Operation 1: i=3, j=4. Swap s[2] and s[4] to get s="aaaab", then reverse the substring starting at 3. Now, s="aaaba".
Operation 2: i=4, j=4. Swap s[3] and s[4] to get s="aaaab", then reverse the substring starting at 4. Now, s="aaaab".

Example 3:

Input: s = "cdbea"
Output: 63

Example 4:

Input: s = "leetcodeleetcodeleetcode"
Output: 982157772

Constraints:

1 <= s.length <= 3000
s consists only of lowercase English letters.

Solution: Math

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

C++

constexpr int kMod = 1e9 + 7;

int64_t powm(int64_t b, int64_t p) {

int64_t ans = 1;

while (p) {

if (p & 1) ans = (ans * b) % kMod;

b = (b * b) % kMod;

p >>= 1;

}

return ans;

}

class Solution {

public:

int makeStringSorted(string s) {

const int n = s.length();

vector<int64_t> fact(n + 1, 1);

vector<int64_t> inv(n + 1, 1);

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

fact[i] = (fact[i - 1] * i) % kMod;

inv[i] = powm(fact[i], kMod - 2);

}

int64_t ans = 0;

vector<int> freq(26);

for (int i = n - 1; i >= 0; --i) {

const int idx = s[i] - 'a';

++freq[idx];

int64_t cur = accumulate(begin(freq), begin(freq) + idx, 0ll) *

fact[n - i - 1] % kMod;

for (int f : freq)

cur = cur * inv[f] % kMod;

ans = (ans + cur) % kMod;

}

return ans;

}

};

花花酱 LeetCode 1829. Maximum XOR for Each Query

By zxi on April 17, 2021

You are given a sorted array nums of n non-negative integers and an integer maximumBit. You want to perform the following query n times:

Find a non-negative integer k < 2^maximumBit such that nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k is maximized. k is the answer to the i^th query.
Remove the last element from the current array nums.

Return an array answer, where answer[i] is the answer to the i^th query.

Example 1:

Input: nums = [0,1,1,3], maximumBit = 2
Output: [0,3,2,3]
Explanation: The queries are answered as follows:
1^st query: nums = [0,1,1,3], k = 0 since 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3.
2^nd query: nums = [0,1,1], k = 3 since 0 XOR 1 XOR 1 XOR 3 = 3.
3^rd query: nums = [0,1], k = 2 since 0 XOR 1 XOR 2 = 3.
4^th query: nums = [0], k = 3 since 0 XOR 3 = 3.

Example 2:

Input: nums = [2,3,4,7], maximumBit = 3
Output: [5,2,6,5]
Explanation: The queries are answered as follows:
1^st query: nums = [2,3,4,7], k = 5 since 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7.
2^nd query: nums = [2,3,4], k = 2 since 2 XOR 3 XOR 4 XOR 2 = 7.
3^rd query: nums = [2,3], k = 6 since 2 XOR 3 XOR 6 = 7.
4^th query: nums = [2], k = 5 since 2 XOR 5 = 7.

Example 3:

Input: nums = [0,1,2,2,5,7], maximumBit = 3
Output: [4,3,6,4,6,7]

Constraints:

nums.length == n
1 <= n <= 10⁵
1 <= maximumBit <= 20
0 <= nums[i] < 2^maximumBit
nums is sorted in ascending order.

Solution: Prefix XOR

Compute s = nums[0] ^ nums[1] ^ … nums[n-1] first

to remove nums[i], we just need to do s ^= nums[i]

We can always maximize the xor of s and k to (2^maxbit – 1)
k = (2 ^ maxbit – 1) ^ s

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

C++

// Author: Huahua

class Solution {

public:

vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {

const int t = (1 << maximumBit) - 1;

const int n = nums.size();

vector<int> ans(n);

int s = 0;

for (int x : nums) s ^= x;

for (int i = n - 1; i >= 0; --i) {

ans[n - i - 1] = t ^ s;

s ^= nums[i];

}

return ans;

}

};

花花酱 LeetCode 1828. Queries on Number of Points Inside a Circle

By zxi on April 17, 2021

You are given an array points where points[i] = [x_i, y_i] is the coordinates of the i^th point on a 2D plane. Multiple points can have the same coordinates.

You are also given an array queries where queries[j] = [x_j, y_j, r_j] describes a circle centered at (x_j, y_j) with a radius of r_j.

For each query queries[j], compute the number of points inside the j^th circle. Points on the border of the circle are considered inside.

Return an array answer, where answer[j] is the answer to the j^th query.

Example 1:

Input: points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]]
Output: [3,2,2]
Explanation: The points and circles are shown above.
queries[0] is the green circle, queries[1] is the red circle, and queries[2] is the blue circle.

Example 2:

Input: points = [[1,1],[2,2],[3,3],[4,4],[5,5]], queries = [[1,2,2],[2,2,2],[4,3,2],[4,3,3]]
Output: [2,3,2,4]
Explanation: The points and circles are shown above.
queries[0] is green, queries[1] is red, queries[2] is blue, and queries[3] is purple.

Constraints:

1 <= points.length <= 500
points[i].length == 2
0 <= x_i, y_i <= 500
1 <= queries.length <= 500
queries[j].length == 3
0 <= x_j, y_j <= 500
1 <= r_j <= 500
All coordinates are integers.

Solution: Brute Force

Time complexity: O(P * Q)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) {

vector<int> ans;

ans.reserve(queries.size());

for (const auto& q : queries) {

const int rs = q[2] * q[2];

int cnt = 0;

for (const auto& p : points)

if ((q[0] - p[0]) * (q[0] - p[0]) +

(q[1] - p[1]) * (q[1] - p[1]) <= rs)

++cnt;

ans.push_back(cnt);

}

return ans;

}

};

花花酱 LeetCode 1827. Minimum Operations to Make the Array Increasing

By zxi on April 17, 2021

You are given an integer array nums (0-indexed). In one operation, you can choose an element of the array and increment it by 1.

For example, if nums = [1,2,3], you can choose to increment nums[1] to make nums = [1,3,3].

Return the minimum number of operations needed to make nums strictly increasing.

An array nums is strictly increasing if nums[i] < nums[i+1] for all 0 <= i < nums.length - 1. An array of length 1 is trivially strictly increasing.

Example 1:

Input: nums = [1,1,1]
Output: 3
Explanation: You can do the following operations:
1) Increment nums[2], so nums becomes [1,1,2].
2) Increment nums[1], so nums becomes [1,2,2].
3) Increment nums[2], so nums becomes [1,2,3].

Example 2:

Input: nums = [1,5,2,4,1]
Output: 14

Example 3:

Input: nums = [8]
Output: 0

Constraints:

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

Solution: Track Last

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

C++

class Solution {

public:

int minOperations(vector<int>& nums) {

int ans = 0, last = 0;

for (int x : nums)

if (x <= last)

ans += ++last - x;

else

last = x;

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1832. Check if the Sentence Is Pangram

Solution: Hashset

C++

Python3

花花酱 LeetCode 1830. Minimum Number of Operations to Make String Sorted

Solution: Math

C++

花花酱 LeetCode 1829. Maximum XOR for Each Query

Solution: Prefix XOR

C++

花花酱 LeetCode 1828. Queries on Number of Points Inside a Circle

Solution: Brute Force

C++

花花酱 LeetCode 1827. Minimum Operations to Make the Array Increasing

Solution: Track Last

C++