程序员进阶之算法练习（九十二）leetcode
题目1 最后一块石头的重量
题目链接
题目大意：
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
示例：
输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。
提示：
1 <= stones.length <= 30
1 <= stones[i] <= 1000
题目解析：
模拟题目操作，用优先队列，每次取出头部两个元素进行操作，如果元素不相同则把石头差放回队列。
代码比较简单：
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
priority_queue<int> q;
for (int i = 0; i < stones.size(); ++i) q.push(stones[i]);
while (q.size() >= 2) {
int first = q.top();
q.pop();
int second = q.top();
q.pop();
if (first - second) q.push(first - second);
}
return q.empty() ? 0 : q.top();
}
}ac;
题目2 两地调度
题目链接
题目大意：
公司计划面试 2n 人。给你一个数组 costs ，其中 costs[i] = [aCosti, bCosti] 。第 i 人飞往 a 市的费用为 aCosti ，飞往 b 市的费用为 bCosti 。
返回将每个人都飞到 a 、b 中某座城市的最低费用，要求每个城市都有 n 人抵达。
示例 1：
输入：costs = [[10,20],[30,200],[400,50],[30,20]]
输出：110
解释：
第一个人去 a 市，费用为 10。
第二个人去 a 市，费用为 30。
第三个人去 b 市，费用为 50。
第四个人去 b 市，费用为 20。
最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。
提示：
2 * n == costs.length
2 <= costs.length <= 100
costs.length 为偶数
1 <= aCosti, bCosti <= 1000
题目解析：
如果不考虑复杂度，可以直接使用搜索的方式，每个人有2个选择，总共会有2^2n种选择，这个复杂度明显超过题目限制；
注意到每个人有2个选择，那么用dp[i][j]来表示前i个人，有j个选择a城市的最小费用，对于第i个人：
如果第i个人选择a城市，那么有dp[i][j]=dp[i-1][j-1] + aCost[i]；
如果第i个人选择b城市，那么有dp[i][j]=dp[i-1][j] + bCost[i];
总的复杂度是O(N^2)；
class Solution {
int dp[110][110];
public:
int twoCitySchedCost(vector<vector<int>>& costs) {
int n = costs.size();
for (int i = 1; i <= n; ++i) {
dp[i][0] = dp[i - 1][0] + costs[i-1][1]; // bCost[i]
dp[i][i] = dp[i - 1][i - 1] + costs[i-1][0]; // aCost[i]
for (int j = 1; j < i; ++j) {
dp[i][j] = min(dp[i - 1][j - 1] + costs[i - 1][0], dp[i - 1][j] + costs[i - 1][1]);
}
}
return dp[n][n/2];
}
}ac;
题目3 两个非重叠子数组的最大和
题目链接
题目大意：
给出非负整数数组 A ，返回两个非重叠（连续）子数组中元素的最大和，子数组的长度分别为 L 和 M。（这里需要澄清的是，长为 L 的子数组可以出现在长为 M 的子数组之前或之后。）
从形式上看，返回最大的 V，而 V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) 并满足下列条件之一：
0 <= i < i + L - 1 < j < j + M - 1 < A.length, 或
0 <= j < j + M - 1 < i < i + L - 1 < A.length.
示例 1：
输入：A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2
输出：20
解释：子数组的一种选择中，[9] 长度为 1，[6,5] 长度为 2。
示例 2：
输入：A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2
输出：29
解释：子数组的一种选择中，[3,8,1] 长度为 3，[8,9] 长度为 2。
示例 3：
输入：A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3
输出：31
解释：子数组的一种选择中，[5,6,0,9] 长度为 4，[0,3,8] 长度为 3。
提示：
L >= 1
M >= 1
L + M <= A.length <= 1000
0 <= A[i] <= 1000
题目解析：
题目要求是找到两个子数组并且要求和最大，我们可以先简化题目要求；
假如只考虑找到一个最大子数组的情况，此时可以从左到右遍历数组，就可以得到每个位置结尾的最大子数组和left[i]；在这个过程中，可以持续计算得到该位置往左所有left[i]的最大值maxLeft[i]；
这样我们就可以O(N)的复杂度，在数组中找到某个长度的最大值。
同理，可以从右到左遍历，得到right[i]和maxRight[i]。
现在要寻找长度L和M的子数组，那么问题可以拆分为：
1、假设有位置k，那么[1, k]中会产生L数组，[k+1, n]会产生M数组；此时可以枚举k的位置；
2、LR的位置是反过来的，按照1的做法把L和R交换一下；
时间和空间复杂度都是O(N)；
class Solution {
int search(vector<int>& nums, int firstLen, int secondLen) {
int n = nums.size(), sum = 0;
vector<int> left(n), maxLeft(n);
for (int i = 0; i < n; ++i) {
sum += nums[i];
if (i >= firstLen) {
sum -= nums[i - firstLen];
}
left[i] = sum;
if (i > 0) maxLeft[i] = maxLeft[i - 1];
maxLeft[i] = max(maxLeft[i], left[i]);
}
vector<int> right(n), maxRight(n);
sum = 0;
for (int i = n - 1; i >= 0; --i) {
sum += nums[i];
if (i + secondLen <= n - 1) {
sum -= nums[i + secondLen];
}
right[i] = sum;
if (i < n - 1) maxRight[i] = maxRight[i + 1];
maxRight[i] = max(maxRight[i], right[i]);
}
int ret = 0;
for (int i = firstLen - 1; i + secondLen < n; ++i) {
ret = max(ret, maxLeft[i] + maxRight[i + 1]);
}
return ret;
}
public:
int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
return max(search(nums, firstLen, secondLen), search(nums, secondLen, firstLen));
}
}leetcode;
题目4 每个元音包含偶数次的最长子字符串
题目链接
题目大意：
给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。
示例 1：
输入：s = "eleetminicoworoep"
输出：13
解释：最长子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。
示例 2：
输入：s = "leetcodeisgreat"
输出：5
解释：最长子字符串是 "leetc" ，其中包含 2 个 e 。
示例 3：
输入：s = "bcbcbc"
输出：6
解释：这个示例中，字符串 "bcbcbc" 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 0 次。
提示：
1 <= s.length <= 5 x 10^5
s 只包含小写英文字母。
题目解析：
从简单的开始思考，假如要求只有一个字母a出现偶数次；
那么如果数组中字母a出现偶数次，则直接满足；如果a出现奇数次，那么去掉最左边的a及左边的部分，或者去掉最右边a及右边的部分；（复杂度O(N) )
由此我们知道，肯定是去掉最初出现的字母a，或者最后出现的字母a。
现在要求变成字母a、o出现偶数次，能否延续上面的思路：去掉最左边或者最右边的某一些部分，使得剩下部分满足要求？
理论上是可行的，左边去掉部分，可能是奇数或者偶数个a，有可能是奇数或者偶数个o，右边同理；剩下的部分要求a和o都是偶数。
对于左边来说，去掉的部分有4种可能：偶数a偶数o，偶数a奇数o，奇数a偶数o，奇数a奇数o；
为了方便描述我们用0表示偶数，1表示奇数，那么上面的状态可以表示为00、01、10、11，刚好可以用数字0、1、2、3来表示这4个状态。
假如原始字符串，最开始的状态是state；最终剩下的字符串，状态应该是00，假如左边去掉字符串的状态是leftState，右边去掉字符串的状态是rightState，那么就有 leftState ^ rightState ^ state = 0；（这里采用异或操作符，可以用实际操作例子感受下）
当字母扩展为a、e、i、o、u之后，同样可以用上面的方式。
class Solution {
public:
int findTheLongestSubstring(string s) {
char aoe[] = "aeiou";
int state = 0;
int left[33] = {0}, right[33] = {0};
for (int i = 0; i < s.length(); ++i) {
char c = s[i];
int k = -1;
for (int j = 0; j < 5; ++j) {
if (aoe[j] == c) {
k = j;
break;
}
}
if (k >= 0) {
state = state ^ (1 << k);
if (state && !left[state]) {
left[state] = i + 1;
// cout << "left " << state << " " << i + 1 << endl;
}
}
}
state = 0;
right[state] = s.length();
for (int i = s.length() - 1; i >= 0; --i) {
char c = s[i];
int k = -1;
for (int j = 0; j < 5; ++j) {
if (aoe[j] == c) {
k = j;
break;
}
}
if (k >= 0) {
state = state ^ (1 << k);
if (state && !right[state]) {
right[state] = i;
// cout << "right " << state << " " << i + 1 << endl;
}
}
}
// cout << "state " << state << endl;
int ans = 0;
for (int j = 0; j < 32; ++j) {
int leftState = j;
int rightState = j ^ state;
// cout << leftState << " " << rightState << " " << s.length() - (s.length() - right[rightState]) - left[leftState] << endl;
ans = max(ans, right[rightState] - left[leftState]);
}
return ans;
}
}leetcode;
题目5 删除子数组的最大得分
题目链接
题目大意：
给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。
返回 只删除一个 子数组可获得的 最大得分 。
如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。
示例 1：
输入：nums = [4,2,4,5,6]
输出：17
解释：最优子数组是 [2,4,5,6]
示例 2：
输入：nums = [5,2,1,2,5,2,1,2,5]
输出：8
解释：最优子数组是 [5,2,1] 或 [1,2,5]
提示：
1 <= nums.length <= 105
1 <= nums[i] <= 104
题目解析：
从数组中找到一个连续的区间，区间不能包括相同的数字，要求区间的数字和尽可能大。
从左到右遍历数组，维护一个区间[left, right]，区间没有相同元素，我们用map<int, int> 来记录数组中出现的数字，sum记录数组的和；
假设遍历到数字a[i]，如果map中没有数字a[i]，则直接添加到map中，右区间右移right=right+1，sum=sum+a[i]；
假设遍历到数字a[i]，如果map中存在数字a[i]，则左区间右移sum=sum-a[left]，left=left+1，直到发现数字a[i]，这样得到包括数字a[i]的区间[left, right]和区间和sum；
遍历过程中的最大和所在区间，就是答案。复杂度O(N)。
class Solution {
public:
int maximumUniqueSubarray(vector<int>& nums) {
int sum = 0, left = 0, right = 0;
int ans = 0;
unordered_map<int, int> mp;
for (int i = 0; i < nums.size(); ++i) {
if (mp[nums[i]]) {
while (mp[nums[i]]) {
sum -= nums[left];
mp[nums[left]]--;
++left;
}
}
right += 1;
sum += nums[i];
++mp[nums[i]];
ans = max(ans, sum);
}
return ans;
}
}leetcode;
