明天是第二次周赛了，紧张。预计下周二后找老师考核。不过要是明天周赛还发挥不好的话，就不太好意思了。

今天才知道，C++ &的优先级低于 ==，难怪之前有些代码的异常很奇怪……

1. 最长优雅子数组

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

看到连续子数组，就应该联想到滑动窗口法。还要注意到，与组内每一个元素与等于0，相当于对应每个1为0，所以把之前的元素都异或和起来再对比即可，窗口滑出元素时也用异或。

但这里有用例过不了，迷惑。

更新，把while的判断改为无不等号就行了，更迷惑了。

代码

class Solution {
public:
    int longestNiceSubarray(vector<int>& nums) {
        int ans=1;
        int n=nums.size();
        if (n==1) return 1; 
        int sum=0;
        int left=0;
        for (int i=0;i<n;++i) {
            while((sum&nums[i])>0) { //括号不能省
                sum^=nums[left++];
            }
            sum^=nums[i];
            ans=i-left+1>ans?i-left+1:ans;
        }
        return ans;
    }
};

2. 和相等的子数组

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

遍历一遍即可。

代码

class Solution {
public:
    bool findSubarrays(vector<int>& nums) {
        int n=nums.size();
        map<int,int> mp;
        for (int i=1;i<n;++i) {
            if (mp[nums[i]+nums[i-1]]==1) return true;
            else mp[nums[i]+nums[i-1]]=1;
        }
        return false;
    }
};

3. 严格回文的数字

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

针对每个数字，转换成对应进制的字符串，然后对比取反字符串即可。

代码

class Solution {
public:
    bool isStrictlyPalindromic(int n) {
        for (int i=2;i<=n-2;++i) {
            int num=n;
            string s1="";
            while(num) {
                s1+=to_string(num%i);
                num/=i;
            }
            string s2(s1.rbegin(),s1.rend());
            if (s1!=s2) return false;
        }
        return true;
    }
};

4. 被列覆盖的最多行数

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

参考这篇 下的评论。

又学到一个新操作，用内建函数 __builtin_popcount() 来统计一个数字的二进制形式包含多少0。将每行的01序列转换为二进制数字，将选定序列的也转换为二进制形式，当该数字含有的1的数量等于numsSelect，则检查覆盖情况。如果两者相与还等于原数字，则说明该行已经被覆盖，可以++计数。最后取最大计数即可。

代码

class Solution {
public:
    int maximumRows(vector<vector<int>>& matrix, int numSelect) {
        int n=matrix.size();
        int m=matrix[0].size();
        vector<int> rowNum(n);
        for (int i=0;i<n;++i) {
            int num=0;
            for (int j=0;j<m;++j) {
                num*=2;
                num+=matrix[i][j];
            }
            rowNum[i]=num;
        }

        int ans=0;
        for (int now=1;now<(1<<m);++now) {
            if ((__builtin_popcount(now))==numSelect) {
                int cnt=0;
                for (int i=0;i<n;++i) {
                    if ((now&rowNum[i])==rowNum[i]) {
                        ++cnt;
                        ans=cnt>ans?cnt:ans;
                    }
                }
            }
        }
        return ans;
    }
};

5. 和有限的最长子序列

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

虽然背包超时了，但还是趁机回顾下背包问题。对于本题，可以看作若干个01背包问题。

这题同时标了独立完成和参考思路。独立完成是因为能够无辅助直接流畅写出背包代码。参考思路是看了评论区题解的标题“排序+二分”，根据这个写出了代码。

虽然题目描述说的是子序列，但实际上答案是顺序无关的，所以可以给nums数组排序，计算前缀和，二分搜索即可。另外，在前缀和数组末尾增加一个INT_MAX值，以解决目标值超出前缀和数组最大值引发的问题。

代码

// 01背包
class Solution {
public:
    vector<int> answerQueries(vector<int>& nums, vector<int>& queries) {
        int capacity=*max_element(queries.begin(),queries.end());
        int m=queries.size();
        int n=nums.size();
        vector<vector<int>> dp(capacity+1,vector<int>(n+1,0));

        for (int j=1;j<=capacity;++j) {
            for (int i=1;i<=n;++i) {
                if (j>=nums[i-1]) dp[j][i]=max(dp[j-nums[i-1]][i-1]+1,dp[j][i-1]);
                else dp[j][i]=dp[j][i-1];
            }
        }
        vector<int> ans(m);
        for (int i=0;i<m;++i) ans[i]=dp[queries[i]][n];
        return ans;

        // 排序+二分
        sort(nums.begin(),nums.end());
        int n=nums.size();
        vector<int> vec(n+1);
        vec[0]=nums[0];
        for (int i=1;i<n;++i) {
            vec[i]=vec[i-1]+nums[i];
        }
        vec[n]=INT_MAX;
        int m=queries.size();
        vector<int> ans(m);
        for (int i=0;i<m;++i) {
            int target=queries[i];
            int left=0,right=n;
            while (left<right) {
                int mid=left+((right-left)>>1);
                if (vec[mid]>target) {
                    right=mid;
                } else left=mid+1;
            }
            ans[i]=left;
        }
        return ans;
    }
};

6. 从字符串中移除星号

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

前后两题难度标反了吧……

在字符串上删除中间元素不好操作，直接构造一个新字符串。遍历给定字符串，如果遇到非星号字符，直接加到新字符串末尾；如果遇到星号，把新字符串的末尾字符弹出。最后返回新字符串。

代码

class Solution {
public:
    string removeStars(string s) {
        string ans="";
        int n=s.size();
        for (int i=0;i<n;++i) {
            if (s[i]!='*') ans+=s[i];
            else ans.pop_back();
        }
        return ans;
    }
};

7. 收集垃圾的最少总时间

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

首先计算每个房子里每种垃圾的数量，显然，总时间必定包含总数量（一比一）。然后记录每个车要到达的最远位置，加上对应时间即可。总的时间即求出来了。

初始版本虽然能过，但效率惨不忍睹，时间内存都超过5%提交者。优化一下之后时间超过96%，空间超过38%。

这次周赛两道M都比E简单……

代码（未优化）

class Solution {
public:
    int garbageCollection(vector<string>& garbage, vector<int>& travel) {
        int n=garbage.size();
        vector<map<char,int>> center(n);
        for (int i=0;i<n;++i) {
            for (auto ch:garbage[i]) center[i][ch]++;
        }
        int timeM=0,timeP=0,timeG=0;
        int farM=0,farP=0,farG=0;
        for (int i=0;i<n;++i) {
            if (center[i]['M']!=0) {
                timeM+=center[i]['M'];
                farM=i;
            }
            if (center[i]['P']!=0) {
                timeP+=center[i]['P'];
                farP=i;
            }
            if (center[i]['G']!=0) {
                timeG+=center[i]['G'];
                farG=i;
            }
        }
        int m=travel.size();
        vector<int> totalTime(m+1,0);
        totalTime[1]=travel[0];
        for (int i=2;i<=m;++i) totalTime[i]=totalTime[i-1]+travel[i-1];
        timeM+=totalTime[farM];
        timeP+=totalTime[farP];
        timeG+=totalTime[farG];
        return timeM+timeP+timeG;
    }
};

代码（优化后）

class Solution {
public:
    int garbageCollection(vector<string>& garbage, vector<int>& travel) {
        int n=garbage.size();
        int farM=0,farP=0,farG=0;
        int totalTime=0;
        for (int i=0;i<n;++i) {
            for (auto ch:garbage[i]) {
                ++totalTime;
                if (ch=='M') farM=i;
                if (ch=='P') farP=i;
                if (ch=='G') farG=i;
            }
        }
        int m=travel.size();
        vector<int> driveTime(m+1,0);
        driveTime[1]=travel[0];
        for (int i=2;i<=m;++i) driveTime[i]=driveTime[i-1]+travel[i-1];
        totalTime+=driveTime[farM]+driveTime[farP]+driveTime[farG];
        return totalTime;
    }
};

8. 赢得比赛需要的最少训练时长

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

本身不难，但要注意细节。即初始状态已经足够过关的时候，中间变量可能为负，这个时候不能直接加到返回值上，而要判负为0。

代码

class Solution {
public:
    int minNumberOfHours(int initialEnergy, int initialExperience, vector<int>& energy, vector<int>& experience) {
        int ans=0;
        int totalEn=0;
        for (int elem:energy) totalEn+=elem;
        ans+=max(totalEn+1-initialEnergy,0);
        int maxGap=INT_MIN;
        int totalEx=initialExperience;
        for (int elem:experience) {
            int newGap=max(elem+1-totalEx,0);
            maxGap=max(maxGap,newGap);
            totalEx+=elem;
        }
        ans+=maxGap;
        return ans;
    }
};

9. 最大回文数字

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

本身难度不高，但细节比较多，如果在竞赛时，看不到特殊用例，有很多细节会做不出来。

代码

class Solution {
public:
    string largestPalindromic(string num) {
        sort(num.begin(),num.end());
        string mid="";
        string preHalf="";
        int n=num.size();
        if (n==1) return num;
        bool flag=false;
        for (int i=n-2;i>=0;--i) {
            if (num[i]!=num[i+1]) {
                if (mid=="") mid=num[i+1];
            }
            else {
                if (num[i]=='0') {
                    if (flag) preHalf+=num[i];
                } else {
                    flag=true;
                    preHalf+=num[i];
                }
                --i;
                if (i==0&&mid=="") mid=num[0];
            }
        }
        string backHalf(preHalf.rbegin(),preHalf.rend());
        if (preHalf==""&&mid=="") mid="0";
        preHalf+=mid+backHalf;
        return preHalf;
    }
};

10. 最大回文数字

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

我的思路是分情况。如果起始结点是根节点，那么返回最大深度；如果起始结点在较深的子树上，返回其感染自己的子树或到根节点再感染另一棵子树时间的较大值；如果起始结点在较浅的子树上，返回其与根节点的距离加上较深子树的深度和。

但到用例69通不过，我意识到分类是有问题的。

答案的分类是基于起始结点当前位置作为相对位置来讨论，而不是我那样基于绝对位置讨论，因而会更全面和清晰。

参考这篇

代码

class Solution {
public:
    int ans=0;
    int depth=-1;
    int dfs (TreeNode* root,int level,int start) {
        if (root==nullptr) return 0;
        if (root->val==start) depth=level;
        int l=dfs(root->left,level+1,start);
        bool inLeft=depth!=-1;
        int r=dfs(root->right,level+1,start);
        if (root->val==start) ans=max(ans,max(l,r));
        if (inLeft) ans=max(ans,depth-level+r);
        else ans=max(ans,depth-level+l);
        return max(l,r)+1;
    }
    int amountOfTime(TreeNode* root, int start) {
        dfs(root,0,start);
        return ans;
    }
};