1. 最长上传前缀

难度

• Easy
• Medium
• Hard

完成情况

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

思路

第一次遇到数据结构的题。初看确实懵了。但打个草稿之后理解了题意。这里说“视频流”，其实用一个数组就行了。如果当前下标的视频被上传，就标记为1，否则为0。

我最初把 longest() 函数用遍历数组来实现，但是超时了。然后想到，可以用一个 front 来保存当前的最长前缀下标，在每次添加视频进流的时候，由 front+1 这个位置为起始，向后遍历，遇1则 front++ ，遇0就停止。这样节省了重复查找的事件。 longest() 直接返回 front 即可。

代码

class LUPrefix {
private:
    vector<int> stream;
    int front;
public:
    LUPrefix(int n) {
        vector<int> vec(n+2,0);
        stream=vec;
        front=0;
    }

    void upload(int video) {
        ++stream;
        for (int i=front+1;front<stream.size();++i) {
            if (stream[i]==1) ++front;
            else break;
        }
    }

    int longest() {
        return front;
    }
};

2. 所有数对的异或和

难度

• Easy
• Medium
• Hard

完成情况

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

思路

打个草稿不难发现，最后要求的值，其实是所有数对异或的结果。要知道异或的性质，即0异或任何数都等于原来的数，相同的数异或得0。那么思路就很清晰了。统计下每种数字出现频率，模2为1的则参与异或，最后返回结果。统计数字出现频率，也不用遍历m*n，因为只要知道另一个数组的长度，那么当前数组中元素都要出现它的常数次。为了防止溢出，也对数组长度模2。于是统计数组长度用了m+n 的复杂度，最后异或在最坏条件下的复杂度是 m+n ，总体亦同。但有点奇怪，时间复杂度超过5%……

代码

class Solution {
public:
    int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
        int ans=0;
        int m=nums1.size();
        int n=nums2.size();
        map<long long,int> mp;
        for (auto elem:nums1) mp[elem]+=n%2;
        for (auto elem:nums2) mp[elem]+=m%2;
        for (auto elem:mp) {
            if (elem.second%2==1) ans^=elem.first;
        }
        return ans;
    }
};

3. 满足不等式的数对数目

难度

• Easy
• Medium
• Hard

完成情况

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

思路

暴力法不出意外超时了。看这篇 。理解了如何用归并排序解这道题， 然后自己凭理解完整写了一遍，顺利通过。

本质上是要求解数组中大于左侧元素值+diff的元素数目，如果用暴力法，显然是n的平方复杂度。而利用归并排序，可以降到nlogn。

代码其实跟正常归并排序代码差不多，只不过多了五行用于计算答案。因为对比元素时，左半边和右半边已经分别有序，而两边的元素相对对方而言，相对位置其实并未改变，故只需较少的比较次数，便能算出局部答案，累加即可。

通过这道题，对归并排序有了一定理解。

代码

class Solution {
private:
    long long ans=0;
    void mergeSort(vector<int>& nums,vector<int>& temp,int diff,int left,int right) {
        if (left>=right) return;
        int mid=left+(right-left>>1);
        mergeSort(nums,temp,diff,left,mid);
        mergeSort(nums,temp,diff,mid+1,right);

        for (int i=left,j=mid+1;j<=right;++j) {
            while (i<=mid&&nums[i]<=nums[j]+diff) ++i;
            ans+=(i-left);
        }

        for (int i=left,j=mid+1,k=left;i<=mid||j<=right;++k) {
            if (i>mid) temp[k]=nums[j++];
            else if (j>right) temp[k]=nums[i++];
            else if (nums[i]<nums[j]) temp[k]=nums[i++];
            else temp[k]=nums[j++];
        }
        for (int i=left;i<=right;++i) nums[i]=temp[i];
    }
public:
    long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int diff) {
        ans=0;
        int n=nums1.size();
        vector<int> nums(n);
        vector<int> temp(n);
        for (int i=0;i<n;++i) nums[i]=nums1[i]-nums2[i];
        mergeSort(nums,temp,diff,0,n-1);
        return ans;
    }
};

4. 按身高排序

难度

• Easy
• Medium
• Hard

完成情况

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

思路

建立一个由身高到姓名的映射，由于身高和姓名都唯一，所以可行。

降序排列身高数组，然后按对应关系依次填入names数组即可。

代码

class Solution {
public:
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        int n=names.size();
        map<int,string> mp;
        for (int i=0;i<n;++i) mp[heights[i]]=names[i];
        sort(heights.rbegin(),heights.rend());
        for (int i=0;i<n;++i) names[i]=mp[heights[i]];
        return names;
    }
};

5. 按位与最大的最长子数组

难度

• Easy
• Medium
• Hard

完成情况

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

思路

完全是脑筋急转弯。看到这题的时候，特意去搜了下按位与的性质，但没有什么突破性发现，还想着用DP做。看了下题解的思路，原来就是找最大值的连续长度！因为两个数字按位与，结果一定小于他们俩中的任何一个！所以只要找到最大值，然后计算这个元素在数组中的最大连续长度，就做出来了。

代码

class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        int n=nums.size();
        int maxNum=INT_MIN;
        for (int i=0;i<n;++i) maxNum=nums[i]>maxNum?nums[i]:maxNum;
        int maxLen=1;
        int len=0;
        if (nums[0]==maxNum) len=1;
        for (int i=1;i<n;++i) {
            if (nums[i]==maxNum) {
                ++len;
                maxLen=max(len,maxLen);
            } else len=0;
        }
        return maxLen;
    }
};

6. 找到所有好下标

难度

• Easy
• Medium
• Hard

完成情况

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

思路

n平方的写法超时了，逻辑本身没问题。

题解做到了n的复杂度。巧妙的地方在于，不是每次确定一个i，再去判断它的左右是否满足条件。而是先正向遍历一遍，判断每个元素左侧的最长连续非递增序列长度，再反向遍历一遍，计算每个元素右侧的最长连续非递减子序列长度。最后再遍历一遍，如果当前坐标在两个数组的左右最长序列长度都大于等于k，则将其加入答案。

这题考虑得不太够。

代码

class Solution {
public:
    vector<int> goodIndices(vector<int>& nums, int k) {
        int n=nums.size();
        vector<int> res;
        vector<int> back(n,1);
        vector<int> forward(n,1);
        int pre=INT_MIN;
        for (int i=n-2;i>=k;--i) {
            if (nums[i+1]<=pre) back[i]=back[i+1]+1;
            pre=nums[i+1];
        }
        pre=INT_MIN;
        for (int i=1;i<n-k;++i) {
            if (nums[i-1]<=pre) forward[i]=forward[i-1]+1;
            pre=nums[i-1];
        }
        for (int i=k;i<n-k;++i) {
            if (back[i]>=k&&forward[i]>=k) res.push_back(i);
        }
        return res;
    }
};

7. 好路径的数目

• TODO: 写个图的数据结构，dfs完成。

难度

• Easy
• Medium
• Hard

完成情况

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

思路

代码

8. 最小偶倍数

难度

• Easy
• Medium
• Hard

完成情况

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

思路

两分钟写完。首先写个欧几里得算法计算最大公因数。再写个函数用于计算最小公倍数。最小公倍数等于a和b的积除以两者的最大公因数。

代码

class Solution {
private:
    int gcd(int a,int b) {
        if (a<b) {
            a=a^b;
            b=a^b;
            a=a^b;
        }
        if (b==0) return a;
        else return gcd(b,a%b);
    }
    int lcm(int a,int b) {
        return (a*b)/gcd(a,b);
    }
public:
    int smallestEvenMultiple(int n) {
        return lcm(n,2);
    }
};

9. 最长的字母序连续子字符串的长度

难度

• Easy
• Medium
• Hard

完成情况

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

思路

实际感觉要归到Easy里。

遍历一遍，如果当前字符跟上一个字符刚好差1，就加一，否则计数归一。

代码

class Solution {
public:
    int longestContinuousSubstring(string s) {
        int n=s.size();
        int ans=1;
        int cnt=1;
        for (int i=1;i<n;++i) {
            if (s[i]-s[i-1]==1) {
                cnt++;
                ans=cnt>ans?cnt:ans;
            }
            else cnt=1;
        }
        return ans;
    }
};

10. 反转二叉树的奇数层

难度

• Easy
• Medium
• Hard

完成情况

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

思路

之前有类似的，需要对树的整层元素进行操作的题目。这次用到了那会儿学的方法。

dfs附加一个深度参数，用二维数组存储结点，同层结点在一个一维数组内。结点全部放进数组里之后，再操作奇数层的元素。

判断层数是否为奇数用按位与运算，交换元素用三次异或，改善效率。

代码

class Solution {
private:
    vector<vector<TreeNode*>> tree;
    void dfs(TreeNode* root, int depth) {
        if (root==nullptr) return;
        if (tree.size()<depth+1) tree.push_back(vector<TreeNode*>());
        tree[depth].push_back(root);
        dfs(root->left,depth+1);
        dfs(root->right,depth+1);
    }
public:
    TreeNode* reverseOddLevels(TreeNode* root) {
        tree.clear();
        dfs(root,0);
        int n=tree.size();
        for (int i=0;i<n;++i) {
            if (i&1==1) {
                int m=tree[i].size();
                int k=m>>1;
                for (int j=0;j<k;++j) {
                    tree[i][j]->val=tree[i][j]->val^tree[i][m-1-j]->val;
                    tree[i][m-1-j]->val=tree[i][j]->val^tree[i][m-1-j]->val;
                    tree[i][j]->val=tree[i][j]->val^tree[i][m-1-j]->val;
                }
            }
        }
        return tree[0][0];
    }
};