Monthly Archives: May 2020

LeetCode Max Dot Product of Two Subsequences

1458. Max Dot Product of Two Subsequences

Given two arrays nums1 and nums2.

Return the maximum dot product between non-empty subsequences of nums1 and nums2 with the same length.

A subsequence of a array is a new array which is formed from the original array by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, [2,3,5] is a subsequence of [1,2,3,4,5] while [1,5,3] is not).

Example 1:

Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6]
Output: 18
Explanation: Take subsequence [2,-2] from nums1 and subsequence [3,-6] from nums2.
Their dot product is (2*3 + (-2)*(-6)) = 18.

Example 2:

Input: nums1 = [3,-2], nums2 = [2,-6,7]
Output: 21
Explanation: Take subsequence [3] from nums1 and subsequence [7] from nums2.
Their dot product is (3*7) = 21.

Example 3:

Input: nums1 = [-1,-1], nums2 = [1,1]
Output: -1
Explanation: Take subsequence [-1] from nums1 and subsequence [1] from nums2.
Their dot product is -1.

Constraints:

  • 1 <= nums1.length, nums2.length <= 500
  • -1000 <= nums1[i], nums2[i] <= 1000

给定两个数组,问从这两个数组中选出两个长度相同的子序列,使得子序列的向量点积最大,求这个最大值。

难题,参考讨论区解法: https://leetcode.com/problems/max-dot-product-of-two-subsequences/discuss/648261/C++Python-Simple-DP

假设dp[i][j]表示nums1[0:i]和nums2[0:j]的最大点积。则在求解dp[i][j]时,有以下四种情况:

  • 不选nums1第i个数,dp[i][j]=dp[i-1][j]
  • 不选nums2第j个数,dp[i][j]=dp[i][j-1]
  • 既不选nums1第i个数,也不选nums2第j个数,dp[i][j]=dp[i-1][j-1]
  • 既选nums1第i个数,也选nums2第j个数,dp[i][j]=dp[i-1][j-1]+nums1[i]*nums2[j]

在最后一个情况中,如果dp[i-1][j-1]<0的话,就把前面的点积都扔掉,相当于max(dp[i-1][j-1],0),完整代码如下:

class Solution {
public:
	int maxDotProduct(vector<int>& nums1, vector<int>& nums2) {
		int m = nums1.size(), n = nums2.size();
		vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MIN));
		for (int i = 1; i <= m; ++i) {
			for (int j = 1; j <= n; ++j) {
				dp[i][j] = max(dp[i][j], dp[i - 1][j]);
				dp[i][j] = max(dp[i][j], dp[i][j - 1]);
				dp[i][j] = max(dp[i][j], dp[i - 1][j - 1]);
				dp[i][j] = max(dp[i][j], max(dp[i - 1][j - 1], 0) + nums1[i - 1] * nums2[j - 1]);
			}
		}
		return dp[m][n];
	}
};

本代码提交AC,用时96MS。

LeetCode Pseudo-Palindromic Paths in a Binary Tree

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。

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

给定字符串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。

LeetCode Check If a Word Occurs As a Prefix of Any Word in a Sentence

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.

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。

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

给定一个数组,问数组中一个连续的子数组内的最大值和最小值的差不超过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内部的排序规则,让其表现为最大堆或最小堆。

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

给定一个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。

LeetCode Destination City

5400. Destination City

You are given the array paths, where paths[i] = [cityAi, cityBi] means there exists a direct path going from cityAi to cityBiReturn the destination city, that is, the city without any path outgoing to another city.

It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city.

Example 1:

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo" 
Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo".

Example 2:

Input: paths = [["B","C"],["D","B"],["C","A"]]
Output: "A"
Explanation: All possible trips are: 
"D" -> "B" -> "C" -> "A". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
Clearly the destination city is "A".

Example 3:

Input: paths = [["A","Z"]]
Output: "Z"

Constraints:

  • 1 <= paths.length <= 100
  • paths[i].length == 2
  • 1 <= cityAi.length, cityBi.length <= 10
  • cityA!= cityBi
  • All strings consist of lowercase and uppercase English letters and the space character.

给定一个路径数组,每条路径标明了出发城市和到达城市,问所有路径最终会到达哪个城市,最终到达的城市是只有进路,没有出路的城市。

简单题,统计下所有城市的入度和出度,出度为0的城市即为最终城市。

class Solution {
public:
	string destCity(vector<vector<string>>& paths) {
		map<string, pair<int,int>> count;
		for (int i = 0; i < paths.size(); ++i) {
			string src = paths[i][0], dest = paths[i][1];
			++count[src].first; // 出度
			++count[dest].second; // 入度
		}
		for (map<string, pair<int, int>>::iterator it = count.begin(); it != count.end(); ++it) {
			if (it->second.first == 0) {
				return it->first;
			}
		}
		return "";
	}
};

本代码提交AC,用时56MS。

LeetCode Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree

LeetCode Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree

Given a binary tree where each path going from the root to any leaf form a valid sequence, check if a given string is a valid sequence in such binary tree. 

We get the given string from the concatenation of an array of integers arr and the concatenation of all values of the nodes along a path results in a sequence in the given binary tree.

Example 1:

Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,0,1]
Output: true
Explanation: 
The path 0 -> 1 -> 0 -> 1 is a valid sequence (green color in the figure). 
Other valid sequences are: 
0 -> 1 -> 1 -> 0 
0 -> 0 -> 0

Example 2:

Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,0,1]
Output: false 
Explanation: The path 0 -> 0 -> 1 does not exist, therefore it is not even a sequence.

Example 3:

Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,1]
Output: false
Explanation: The path 0 -> 1 -> 1 is a sequence, but it is not a valid sequence.

Constraints:

  • 1 <= arr.length <= 5000
  • 0 <= arr[i] <= 9
  • Each node’s value is between [0 – 9].

给定一棵二叉树,和一个数组,问树中从根节点到叶子节点能否组成给定数组。

简单题,本质就是Trie树,直接DFS查找即可,代码如下:

class Solution {
public:
	bool dfs(TreeNode* root, vector<int>& arr, int idx) {
		int n = arr.size();
		if (idx >= n)return false;
		if (root->val == arr[idx] && root->left == NULL && root->right == NULL && idx == n - 1)return true;
		if (root->val != arr[idx])return false;
		bool left = false, right = false;
		if (root->left != NULL)left = dfs(root->left, arr, idx + 1);
		if (root->right != NULL)right = dfs(root->right, arr, idx + 1);
		return left || right;
	}
	bool isValidSequence(TreeNode* root, vector<int>& arr) {
		if (root == NULL)return false;
		return dfs(root, arr, 0);
	}
};

本代码提交AC,用时104MS。