LeetCode Minimum Window Substring

76. Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"


Note:

• If there is no such window in S that covers all characters in T, return the empty string "".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

hard题，用双指针+滑动窗口。核心思想是找到滑动窗口[i,j)，首先++j，加入右边界的字符；然后检查[i,j)是否能覆盖t；再然后++i，丢掉左边界的字符。

class Solution {
public:
string minWindow(string s, string t) {
int m = s.size(), n = t.size();
vector<int> required(128, 0);
for (int i = 0; i < n; ++i) {
++required[t[i]];
}

int min_len = m + 1, start_id = 0, found = 0;
int i = 0, j = 0;
while (j < m) {
--required[s[j]];
if (required[s[j]] >= 0) { // s[j]在t中
++found;
}
++j;

while (found == n) {
int cur_len = j - i;
if (cur_len < min_len) {
min_len = cur_len;
start_id = i;
}
++required[s[i]];
if (required[s[i]] > 0) --found;
++i;
}
}
if (min_len == m + 1) return "";
else return s.substr(start_id, min_len);
}
};

LeetCode Maximum Number of Vowels in a Substring of Given Length

5417. Maximum Number of Vowels in a Substring of Given Length

Given a string s and an integer k.

Return the maximum number of vowel letters in any substring of s with length k.

Vowel letters in English are (a, e, i, o, u).

Example 1:

Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.


Example 2:

Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.


Example 3:

Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels.


Example 4:

Input: s = "rhythms", k = 4
Output: 0
Explanation: We can see that s doesn't have any vowel letters.


Example 5:

Input: s = "tryhard", k = 4
Output: 1


Constraints:

• 1 <= s.length <= 10^5
• s consists of lowercase English letters.
• 1 <= k <= s.length

class Solution {
public:
bool IsVol(const char &c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int maxVowels(string s, int k) {
int ans = 0;
int i = 0, j = k - 1, n = s.size();
for (int k = i; k <= j; ++k) {
if (IsVol(s[k]))++ans;
}
int cur = ans;
while (j < n - 1) {
++j;
if (IsVol(s[j]))++cur;
if (IsVol(s[i]))--cur;
++i;
ans = max(ans, cur);
}
return ans;
}
};

LeetCode Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Given an array of integers nums and an integer limit, return the size of the longest continuous subarray such that the absolute difference between any two elements is less than or equal to limit.

In case there is no subarray satisfying the given condition return 0.

Example 1:

Input: nums = [8,2,4,7], limit = 4
Output: 2
Explanation: All subarrays are:
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4.
Therefore, the size of the longest subarray is 2.


Example 2:

Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.


Example 3:

Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3


Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 0 <= limit <= 10^9

class Solution {
public:
int longestSubarray(vector<int>& nums, int limit) {
int n = nums.size();
int ans = 1; // 最小值是1

for (int i = 0; i < n; ++i) {
vector<int> dp_max(n, 0), dp_min(n, INT_MAX);
dp_max[i] = dp_min[i] = nums[i];
for (int len = 2; len <= n; ++len) {
int j = i + len - 1;
if (j >= n)break;
dp_max[j] = max(dp_max[j - 1], nums[j]);
dp_min[j] = min(dp_min[j - 1], nums[j]);
int diff = dp_max[j] - dp_min[j];
if (diff <= limit) {
ans = max(ans, j - i + 1);
}
else {
break;
}
}
}
return ans;
}
};

class Solution {
public:
int longestSubarray(vector<int>& A, int limit) {
int res = 0, n = A.size(), i = 0, j;
multiset<int> m;
for (j = 0; j < n; ++j) {
m.insert(A[j]);
if (*m.rbegin() - *m.begin() > limit)
m.erase(m.find(A[i++]));
else
res=max(res,j-i+1);
}
return res;
}
};

LeetCode Check If All 1’s Are at Least Length K Places Away

1437. Check If All 1’s Are at Least Length K Places Away

Given an array nums of 0s and 1s and an integer k, return True if all 1’s are at least k places away from each other, otherwise return False.

Example 1:

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.


Example 2:

Input: nums = [1,0,0,1,0,1], k = 2
Output: false
Explanation: The second 1 and third 1 are only one apart from each other.

Example 3:

Input: nums = [1,1,1,1,1], k = 0
Output: true


Example 4:

Input: nums = [0,1,0,1], k = 1
Output: true


Constraints:

• 1 <= nums.length <= 10^5
• 0 <= k <= nums.length
• nums[i] is 0 or 1

class Solution {
public:
bool kLengthApart(vector<int>& nums, int k) {
int n = nums.size();
int i = 0, j = 0;
while (i < n) {
while (i < n&&nums[i] == 0)++i;
if (i >= n - 1)break;
j = i + 1;
while (j < n&&nums[j] == 0)++j;
if (j - i - 1 < k)return false;
i = j;
}
return true;
}
};

hihoCoder 1543-SCI表示法

hihoCoder 1543-SCI表示法

输出

2
15
8

5
1

LeetCode Smallest Range

LeetCode Smallest Range You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the k lists. We define the range [a,b] is smaller than range [c language=",d"][/c] if b-a < d-c or a < c if b-a == d-c. Example 1:

Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation:
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Note:
1. The given list may contain duplicates, so ascending order means >= here.
2. 1 <= k <= 3500
3. -105 <= value of elements <= 105.
4. For Java users, please note that the input type has been changed to List<List<Integer>>. And after you reset the code template, you’ll see this point.

1. i,j,k分别指向三个数组的开头，即i=j=k=0，相当于在[4,0,5]中找最大值和最小值，构成区间[0,5]，长度为5。
2. 最小值为j所在数组，所以++j，在新的数组[4,9,5]中找最大值和最小值，构成区间[4,9]，长度为5。
3. 最小值为i所在数组，所以++i，在新的数组[10,9,5]中找最大值和最小值，构成区间[5,10]，长度为5。
4. ++k，新数组[10,9,18]，区间[9,18]，长度为9。
5. ++j，新数组[10,12,18]，区间[10,18]，长度为8。
6. ++i，新数组[15,12,18]，区间[12,18]，长度为6。
7. ++j，新数组[15,20,18]，区间[15,20]，长度为5。
8. ++i，新数组[24,20,18]，区间[18,24]，长度为6。
9. ++k，新数组[24,20,22]，区间[20,24]，长度为4。
10. ++j，第二个数组遍历完毕，结束，遍历过程中，得到的长度最短的区间是[20,24]。

LeetCode Minimum Size Subarray Sum

209. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Example:

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up:If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums)
{
int n = nums.size(), left = 0, right = 0, sum = 0, ans = INT_MAX;
while (right < n) {
while (right < n && sum < s)
sum += nums[right++];
while (left <= right && sum >= s) {
ans = min(ans, right – left);
sum -= nums[left++];
}
}
return ans == INT_MAX ? 0 : ans;
}
};

class Solution {
private:
int searchRight(vector<int>& accuSum, int l, int r, int target)
{
while (l <= r) {
int m = l + (r – l) / 2;
if (accuSum[m] == target)
return m;
else if (accuSum[m] > target)
r = m – 1;
else
l = m + 1;
}
return l;
}
public:
int minSubArrayLen(int s, vector<int>& nums)
{
int n = nums.size(), ans = INT_MAX;
vector<int> accuSum(n + 1, 0);
for (int i = 1; i <= n; ++i)
accuSum[i] = accuSum[i – 1] + nums[i – 1];
for (int left = 0; left < n; ++left) {
int right = searchRight(accuSum, left, accuSum.size() – 1, accuSum[left] + s);
if (right == n + 1)
break;
ans = min(ans, right – left);
}
return ans == INT_MAX ? 0 : ans;
}
};

LeetCode Longest Word in Dictionary through Deleting

LeetCode Longest Word in Dictionary through Deleting Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string. Example 1:

Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
Output:
"apple"

Example 2:
Input:
s = "abpcplea", d = ["a","b","c"]
Output:
"a"

Note:
1. All the strings in the input will only contain lower-case letters.
2. The size of the dictionary won’t exceed 1,000.
3. The length of all the strings in the input won’t exceed 1,000.

LeetCode Move Zeroes

283. Move Zeroes

Given an array nums, write a function to move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

class Solution {
public:
void moveZeroes(vector<int>& nums)
{
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == 0) {
for (int j = i + 1; j < nums.size(); j++) {
if (nums[j] != 0) {
swap(nums[i], nums[j]);
break;
}
}
}
}
}
};

class Solution {
public:
void moveZeroes(vector<int>& nums)
{
for (int i = 0, j = 0; i < nums.size(); i++) {
if (nums[i] != 0) {
swap(nums[i], nums[j++]);
}
}
}
};

class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = nums.size(), num_zeors = 0;
int i = 0;
for (int j = 0; j < n; ++j) {
if (nums[j] != 0)nums[i++] = nums[j];
}
for (int j = i; j < n; ++j)nums[j] = 0;
}
};