寒假力扣周赛
第300场周赛
3-通过最少操作次数使数组的和相等：双指针+贪心
大意：给定两个数组a,b，里面的元素都是1-6之间的数，每次操作可以对任意数组中的任意元素修改为1-6之间的数，问最少操作数使得两数组的元素和相等。
思路：假设a的和比b的和大，那先对a从大到小排序，对b从小到大排序，求出差值ca，l指向a中未修改且最靠前的元素，r指向b中未修改且最靠前的元素，贪心策略为把a中的元素尽量修改为1，b中的元素尽量修改为6，前提条件是先比较a[l]-1，6-a[r]的大小。
class Solution {
public:
bool cmp(int a,int b)
{
return a > b;
}
vector<int>a,b;
int minOperations(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
int m = nums2.size();
int tmp1 = 0,tmp2 = 0;
if(n > m){
if(n > m*6) return -1;
}
if(n < m){
if(m > 6*n) return -1;
}
for(int i = 0; i < n; i++){
tmp1 += nums1[i];
}
for(int i = 0; i < m; i++){
tmp2 += nums2[i];
}
int ans = 0;
int ca;
if(tmp1 > tmp2){
a = nums1;
b = nums2;
}
else{
a = nums2;
b = nums1;
}
sort(a.begin(),a.end());
sort(b.begin(),b.end());
reverse(a.begin(),a.end());
ca = abs(tmp1 - tmp2);
int l = 0,r = 0,x,y;
n = a.size();
m = b.size();
while(l < n && r < m){
x = a[l]-1;
y = 6-b[r];
if(x < y){
if(ca <= 0) return ans;
ca -= y;
r++;
ans++;
}
else if(x > y){
if(ca <= 0) return ans;
ca -= x;
l++;
ans++;
}
else {
if(ca <= 0) return ans;
ca -= x;
l++;
ans++;
}
if(ca <= 0) return ans;
}
while(l < n){
x = a[l]-1;
if(ca <= 0) return ans;
ca -= x;
l++;
ans++;
}
while(r < m){
y = 6-b[r];
if(ca <= 0) return ans;
ca -= y;
r++;
ans++;
}
return ans;
}
}; 第229场周赛
3-执行乘法运算的最大分数：动态规划
大意：给定一个数组nums和另一个数组multipliers，第i次可以从nums中的左端或右端取一个数和multipliers中的第i个数相乘，问最后所有结果相加和最大是多少。
思路：要么从左取要么从右取，两种选择，数据范围不大，考虑动态规划做。
找状态：dp[i][j] 表示选第k个数是有i个左端点，j个右端点。假设i+j=k
状态转移：如果i=0，也就是全取的是右端点，当前只能取右端点，那么dp[i][k-j] = dp[i][k-j-1]+a[m-k+i]*b[k-1];
如果i=k，也就是全是做端点，当前只能取左端点，那么dp[i][k-i] = dp[i-1][k-i]+a[i-1]*b[k-1];
其它情况dp[i][k-i] = max(dp[i][k-i-1]+a[m-k+i]*b[k-1], dp[i-1][k-i]+a[i-1]*b[k-1]);两者取最大中的一个。
class Solution {
public:
int a[100005],b[100005];
int dp[2005][2005];
int maximumScore(vector<int>& nums, vector<int>& multipliers) {
int n = multipliers.size();
int m = nums.size();
for(int i = 0; i < nums.size(); i++) a[i] = nums[i];
for(int i = 0; i < multipliers.size(); i++) b[i] = multipliers[i];
int ans = -1e9;
memset(dp,0,sizeof(dp));
for(int k = 1; k <= n; k++){
for(int i = 0; i <= k; i++){
if(i == 0) dp[i][k-i] = dp[i][k-i-1]+a[m-k+i]*b[k-1];
else if(i == k) dp[i][k-i] = dp[i-1][k-i]+a[i-1]*b[k-1];
else{
dp[i][k-i] = max(dp[i][k-i-1]+a[m-k+i]*b[k-1], dp[i-1][k-i]+a[i-1]*b[k-1]);
}
if(k == n) ans = max(dp[i][k-i],ans);
}
}
return ans;
}
}; 4-由子序列构造的最长回文串的长度：动态规划
大意：给定两个字符串s1,s2，从s1中取出一个非空子序列，再从s2中取出一个非空子序列，问连接后的字符串是回文串吗？最长是多少。
思路：直接将s1和s2先连起来，再求回文子序列的最长长度，注意一端要在s1内，另一端要在s2内。
class Solution {
public:
int dp[2005][2005];
int longestPalindrome(string word1, string word2) {
string s = word1+word2;
int n = s.size();
int n1 = word1.size()-1;
int n2 = word2.size()-1;
int ans = 0;
for(int i = n-1; i >= 0; i--){//由小区间扩展到大区间，所以倒过来。
dp[i][i] = 1;
for(int j = i+1; j < n; j++){
if(s[i] == s[j]){
dp[i][j] = dp[i+1][j-1]+2;
if(i <= n1 && j > n1) ans = max(dp[i][j],ans);
}
else dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
}
}
return ans;
}
}; 第227场周赛
1-检查数组是否经排序和轮转得到
大意：问是否存在k使得所有数循环移动(i+k)%nums.size()后，使得数组有序。
思路：暴力枚举原数组中的每个数，看看是否存在以某个数为起点使得数组有序。
class Solution {
public:
bool check(vector<int>& nums) {
int a[105];
vector<int>num = nums;
int t = nums[0],xb = 0;
for(int i = 1; i < nums.size(); i++){
if(nums[i] < t){
xb = i;
t = nums[i];
}
}
// cout << xb;
for(int k = 0; k < num.size(); k++){
int q = 0;
for(int i = k; i < num.size(); i++){
a[q++] = num[i];
}
for(int i = 0; i < k; i++){
a[q++] = num[i];
}
int flag = 0;
sort(nums.begin(),nums.end());
for(int i = 0; i < nums.size(); i++){
// cout << a[i] << " ";
if(a[i] != nums[i]) {
flag = 1;
break;
}
}
if(!flag) return true;
}
return false;
}
}; 2-移除石子的最大得分
大意：给出三堆石子，每次从不同的两堆中个取走一个石子，并加一分，问最大得分是多少。
class Solution {
public:
int maximumScore(int a, int b, int c) {
int num[10];
num[0] = a;
num[1] = b;
num[2] = c;
sort(num,num+3);
if(num[0]+num[1] < num[2]) return num[0]+num[1];
if(num[0]+num[1] == num[2]) return num[2];
return (num[0]+num[1]-num[2])/2+num[2];
}
}; 3-构造字典序最大的合并字符串
大意：给定两个字符串s1,s2，有两种操作，第一种是取s1的第一个字符加入merge尾部并从s1中删去，第二种是取s2的第一个字符加入merge尾部并从s2中删去，求merge最大字典序的字符串是多少。
思路：弄两个指针l1,l2分别指向s1,s2的第一个字符，判断s1[l1],s2[l2]大小,取最大的那个，如果相同，那么继续判断后面的字符，谁大就取谁。(注意边界如s1="ababa",s2="ababa",答案merge="ababababa")
class Solution {
public:
string largestMerge(string word1, string word2) {
int l1,l2,r1,r2;
string ans;
l1 = l2 = 0;
int n1,n2;
n1 = word1.size();
n2 = word2.size();
ans = "";
while(l1 < n1 && l2 < n2){
if(word1[l1] < word2[l2]){
ans += word2[l2];
l2++;
continue;
}
if(word1[l1] > word2[l2]){
ans += word1[l1];
l1++;
continue;
}
int t1,t2;
// cout << l1 << " " << l2 << endl;
t1 = l1;
t2 = l2;
while(word1[t1] == word2[t2] && t1 < n1 && t2 < n2){
// cout << word1[t1] << " " << word2[t2] << "\n";
t1++;
t2++;
}
if(t1 == n1 && t2 == n2){
ans += word1[l1];
l1++;
}
if(t1 == n1) word1 += "A";
if(t2 == n2) word2 += "A";
if(word1[t1] < word2[t2]){
ans += word2[l2];
l2++;
continue;
}
if(word1[t1] > word2[t2]){
ans += word1[l1];
l1++;
}
}
if(l1 < n1){
for(int i = l1; i < n1; i++) ans += word1[i];
}
if(l2 < n2){
for(int i = l2; i < n2; i++) ans += word2[i];
}
return ans;
}
}; 4-最接近目标值的子序列和：dfs+二分
大意：给定一组数，从中取若干个数，使得这些数的和和goal最接近。
思路：看到数据范围是40，又是取若干个数，首先想到的是dfs+剪枝，可是还是TLE，那就试着把范围缩小，将数组对半分成两个数组，对这两个数组dfs暴搜出所有和的情况，然后对其中一个数组排序，枚举另一个数组中的每一个数，因为要尽可能让lsum+rsum>=goal，所以在排好序的数组中查找第一个大于等于goal-rsum，还有可能在这个位置的前一个。
class Solution {
public:
int n,g,xb;
long long ans = 1e15;
vector<int>num;
vector<int>num1[5];
void dfs(int cur,int en,int res,int bh)
{
if(cur > en) return ;
num1[bh].push_back(res);
for(int i = cur+1; i <= en; i++){
dfs(i,en,res+num[i],bh);
}
}
int minAbsDifference(vector<int>& nums, int goal) {
n = nums.size();
num = nums;
for(int i = 0; i <= n/2-1; i++){
dfs(i,n/2-1,nums[i],1);
}
for(int i = n/2; i <= n-1; i++){
dfs(i,n-1,nums[i],2);
}
sort(num1[2].begin(),num1[2].end());
int ans = 1e9+7;
for(int i = 0; i < num1[1].size(); i++){
// cout << num1[1][i] << "\n";
int temp = goal-num1[1][i];
int xb = lower_bound(num1[2].begin(),num1[2].end(),temp)-num1[2].begin();
// cout << xb << endl;
ans = min(ans,abs(num1[1][i]-goal));
ans = min(ans,abs(num1[2][xb]+num1[1][i]-goal));
if(xb >= 1){
ans = min(ans,abs(num1[2][xb-1]+num1[1][i]-goal));
}
}
for(int i = 0; i < num1[2].size(); i++){
ans = min(ans,abs(num1[2][i]-goal));
}
return min(ans,abs(goal));
}
}; 第45场双周赛
https://leetcode-cn.com/contest/biweekly-contest-45/2-任意子数组和的绝对值的最大值
大意：给定一组数，问子数组中和的绝对值的最大值是多少。
思路：先求出nums的前缀和pre，然后对pre排序，如果pre中全是负数，那么取pre中最小数的绝对值，如果全是正数，那么取pre中最大的数，如果即有正又有负，取pre中最大值减去最小值作为答案。
class Solution {
public:
int pre[100005];
int maxAbsoluteSum(vector<int>& nums) {
pre[0] = nums[0];
for(int i = 1; i < nums.size(); i++){
pre[i] = nums[i]+pre[i-1];
}
sort(pre,pre+nums.size());
if(nums.size() == 1) return abs(nums[0]);
if(pre[0] >= 0) return pre[nums.size()-1];
if(pre[nums.size()-1] < 0) return abs(pre[0]);
return max(abs(pre[nums.size()-1]-pre[0]),abs(pre[nums.size()-1]));
}
}; 3-删除字符串两端相同字符后的最短长度
class Solution {
public:
int minimumLength(string s) {
int l = 0,r = s.length()-1;
// if(r == 0) return 1;
while(l <= r){
if(l == r){
if(s[r] == s[r+1]) return 0;
return 1;
}
if(s[l] == s[r]){
l++;
r--;
}
else{
if(l == 0 || r == s.length()-1) return s.length();
if(s[l-1] == s[l]){
l++;
}
else if(s[r+1] == s[r]){
r--;
}
else{
break;
}
}
}
return r-l+1;
}
}; 4：最多可以参加的会议数目 II：动态规划+二分
思路：一看这种考虑选或不选，数据范围也不小的题，可以考虑用dp来解决。
先将会议按结束时间从小到大排序。
状态：dp[i][j]表示前i个会议中参加了j个的最大价值和。
状态转移：
1）第i个会议不参加，那么dp[i][j] = dp[i-1][j]。
3）参加第i个会议，从前i个会议中二分找到会议结束时间首先小于第i个会议开始时间的会议l，dp[i][j] = dp[l][j-1],为什么不是dp[i][j] = dp[i-1][j-1]呢，因为如果第i-1个会议和第i个会议冲突的话，答案会错误，也就是前面的状态对后面的状态有影响。
class Solution {
public:
struct Node{
int s,e,v;
bool operator<(const Node &x)const{
return x.e > e;
}
}node[1000005];
int s[1000005],e[1000005],v[1000005];
int maxValue(vector<vector<int>>& events, int k) {
vector<int>dp[1000005];
for(int i = 0; i < events.size(); i++)
for(int j = 0; j <= k; j++) dp[i].push_back(0);
for(int i = 0; i < events.size(); i++){
node[i].s = events[i][0];
node[i].e = events[i][1];
node[i].v = events[i][2];
}
sort(node,node+events.size());
dp[0][0] = 0;
dp[0][1] = node[0].v;
//cout <<node[2].e << endl;
for(int i = 1; i < events.size(); i++){
for(int j = 1; j <= k; j++){//不选
dp[i][j] = max(dp[i][j],dp[i-1][j]);
}
int l = 0,r = i,ans = -1;
while(l <= r){
int mid = (l+r)>>1;
if(node[mid].e < node[i].s){
ans = mid;
l = mid+1;
}
else r = mid-1;
}
if(ans == -1){
dp[i][1] = max(dp[i][1],node[i].v);
continue;
}
for(int j = 1; j <= k; j++){
dp[i][j] = max(dp[i][j],dp[ans][j-1]+node[i].v);
}
}
int ans = 0;
for(int j = 0; j <= k; j++){
ans = max(ans,dp[events.size()-1][j]);
}
return ans;
}
}; 
