5418. Pseudo-Palindromic Paths in a Binary Tree

Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

Example 1:

Input: root = [2,3,1,3,1,null,1]
Output: 2 
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 2:

Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1 
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome).

Example 3:

Input: root = [9]
Output: 1

Constraints:

• The given binary tree will have between 1 and 10^5 nodes.
• Node values are digits from 1 to 9.

---

给定一棵二叉树，问树中从根到叶子的路径构成的一个数组，能调整成回文数组串的个数。

简单题，直接DFS，记录每条路径中包含1~9的个数，如果该数组中包含的奇数的个数不超过1个，则能调整成回文串，否则不能。

回文串有两种形式，一种是123321，即串中每个数字都对称出现偶数次，另一种是1234321，中间的4只出现1次，其他数字都出现偶数次。

完整代码如下：

class Solution {
private:
	void DFS(TreeNode* root, vector<int> &hash, int &ans) {
		if (root == NULL)return;
		++hash[root->val];

		if (root->left == NULL && root->right == NULL) {
			int odd = 0;
			for (int i = 1; i <= 9; ++i) {
				if (hash[i] % 2 == 1) {
					++odd;
					if (odd > 1) {
						break;
					}
				}
			}
			if (odd <= 1) {
				++ans;
			}
			--hash[root->val];
			return;
		}

		DFS(root->left, hash, ans);
		DFS(root->right, hash, ans);
		--hash[root->val];
	}
public:
	int pseudoPalindromicPaths(TreeNode* root) {
		vector<int> hash(10, 0);
		int ans = 0;
		DFS(root, hash, ans);
		return ans;
	}
};

本代码提交AC。

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

---

给定字符串s和长度k，问s中长度为k的子串中，包含最多元音字母的个数。

简单题，直接滑动窗口+双指针计数即可：

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;
	}
};

本代码提交AC。

5416. Check If a Word Occurs As a Prefix of Any Word in a Sentence

Given a sentence that consists of some words separated by a single space, and a searchWord.

You have to check if searchWord is a prefix of any word in sentence.

Return the index of the word in sentence where searchWord is a prefix of this word (1-indexed).

If searchWord is a prefix of more than one word, return the index of the first word (minimum index). If there is no such word return -1.

A prefix of a string S is any leading contiguous substring of S.

Example 1:

Input: sentence = "i love eating burger", searchWord = "burg"
Output: 4
Explanation: "burg" is prefix of "burger" which is the 4th word in the sentence.

Example 2:

Input: sentence = "this problem is an easy problem", searchWord = "pro"
Output: 2
Explanation: "pro" is prefix of "problem" which is the 2nd and the 6th word in the sentence, but we return 2 as it's the minimal index.

Example 3:

Input: sentence = "i am tired", searchWord = "you"
Output: -1
Explanation: "you" is not a prefix of any word in the sentence.

Example 4:

Input: sentence = "i use triple pillow", searchWord = "pill"
Output: 4

Example 5:

Input: sentence = "hello from the other side", searchWord = "they"
Output: -1

Constraints:

• 1 <= sentence.length <= 100
• 1 <= searchWord.length <= 10
• sentence consists of lowercase English letters and spaces.
• searchWord consists of lowercase English letters.

---

给定一个句子和一个待搜索词，问该搜索词是否可能是这个句子中某个词的前缀。

直接暴力搜索即可，因为指定必须是前缀，所以其实直接截取相同长度的前缀判断相等即可。

class Solution {
public:
	int isPrefixOfWord(string sentence, string searchWord) {
		int idx = 1, i = 0, j = 0, n = sentence.size();
		while (i < n) {
			j = i + 1;
			while (j < n&&sentence[j] != ' ')++j;
			string cur = sentence.substr(i, j - i);
			size_t pos = cur.find(searchWord);
			if (pos != string::npos&&pos == 0) {
				return idx;
			}
			++idx;
			i = j + 1;
		}
		return -1;
	}
};

本代码提交AC。

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

---

给定一个数组，问数组中一个连续的子数组内的最大值和最小值的差不超过limit的最长连续子数组的长度。

常规解法。使用DP求出任何一个子区间dp[i,j]的最大值和最小值，dp[i,j+1]的最大值和最小值只需要用nums[j]和dp[i,j]的最大值和最小值比较即可。完整代码如下：

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;
	}
};

很不幸，该代码的时间复杂度达到了O(n^2)，在最后两个测试样例上TLE了。

比O(n^2)低的复杂度有O(nlgn)和O(n)。O(nlgn)排序好像无法求解，那么只有O(n)的方法了。此题本质上是一个滑动窗口的问题，可以用两个指针i和j，标记区间的起止位置。那么问题的关键就是如何快速求解到区间[i,j]的最大值和最小值。

我之前的方法是用DP提前算出来，但是DP的过程费时。使用优先队列priority_queue（最大堆、最小堆）可以得到当前区域的最大值和最小值，但是一旦差的绝对值超过limit，需要从优先队列中删除i所指元素时，priority_queue没有提供erase或者remove之类的接口，所以使用priority_queue无法达成目标。

提示使用multiset，我之前知道multiset内部使用红黑树结构，内部存储是有序的，而且提供了erase接口以供删除元素。但是我一直不确定如何获得multiset内部的最大值和最小值元素，虽然它内部是有序的，但我不确定程序员能否得到其有序列表。

后来看了multiset的API，里面明确说明了multiset默认是从小到大排序，而且其begin()指向最小值，rbegin()指向最后一个元素，即最大值。所以multiset是一个功能很强大的容器，它不但可以实现堆的功能，还能查找、删除某个元素，比 priority_queue 更强大。

使用multiset的完整代码如下：

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;
    }
};

本代码提交AC，用时368MS。

另外，我们还可以指定multiset内部的排序规则，让其表现为最大堆或最小堆。

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

---

给定一个0/1数组，问数组中所有1的间隔是否超过某个阈值。

简单题，一遍扫描数组，使用双指针记录相邻两个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;
	}
};

本代码提交AC，用时140MS。