leetcode 286 周赛回顾

T1

传送门

比赛时代码，过于冗长

class Solution {
public:
    vector> findDifference(vector& nums1, vector& nums2) {
        vector aa, bb;
        
        for(int i = 0; i < nums1.size(); i ++){
            
            auto it = find(nums2.begin(), nums2.end(), nums1[i]);
            
            if(it == nums2.end()){
                
                auto qq = find(aa.begin(), aa.end(), nums1[i]);
                
                if(qq == aa.end()){
                   aa.push_back(nums1[i]);
                }

            }
        }
        
        for(int i = 0; i < nums2.size(); i ++){
            
            auto it = find(nums1.begin(), nums1.end(), nums2[i]);
            
            if(it == nums1.end()){
                
                auto qq = find(bb.begin(), bb.end(), nums2[i]);
                
                if(qq == bb.end()){
                   bb.push_back(nums2[i]);
                }
            }
        }
        
        vector> xx;
        
        xx.push_back(aa);
        xx.push_back(bb);
        
        return xx;
    }
};

这里我们可以用 set 来去重，简化步骤

class Solution
{
public:
    vector> findDifference(vector &nums1, vector &nums2)
    {
        set s1, s2;

        for (auto i : nums1)
            s1.insert(i);

        for (auto i : nums2)
            s2.insert(i);

        vector ans1, ans2;

        for (auto i : s1)
            if (s2.find(i) == s2.end())
                ans1.push_back(i);

        for (auto i : s2)
            if (s1.find(i) == s1.end())
                ans2.push_back(i);


        return vector>{ans1, ans2};
    }
};

 T2

传送门

看了题解后知道了可以利用栈来模拟

遍历一遍数组：

* 如果栈大小为偶数，可以随意加入元素；
* 如果栈大小为奇数，那么加入的元素不能和栈顶相同。
遍历结束后，若栈大小为奇数，则移除栈顶。

class Solution {
public:
    int minDeletion(vector& nums) {
        stack aa;
        int ans = 0;

        for(auto c : nums){
            if(aa.size() & 1 && aa.top() == c){
                ans ++;
            }else{
                aa.push(c);
            }
        }

        if(aa.size() & 1){
            ans ++;
        }

        return ans;
    }
};

还可以用贪心来做

如果当前数可以作为数对中的第二个数就保留（即前面的数与其不相等），它的下一个数直接作为下一个数对中的第一个数。 

class Solution {
public:
    int minDeletion(vector& nums) {
        int ans = 0;

        for(int i = 0; i < nums.size() - 1; i ++){
            if((i - ans) % 2 == 0 && nums[i] == nums[i + 1]){
                ans ++;
            } 
        }

        if((nums.size() - ans) % 2 == 1){
            ans ++;
        }

        return ans;
    }
};

（i - ans) 起到改变下标的作用，如果遍历的数不能作为数对的第二个元素，就忽略前一个，将该数作为数对的第一个

大佬对贪心做法的证明，如下：

显然最佳答案中同一个数不会连续出现三次及以上，因此我们先考虑同一个数连续出现不超过两次时，贪心算法是否正确。

在该简化问题中，如果同一个数 ai 和 ai+1 连续出现两次，而且这两个数都要保留，那么 i 必须是奇数（下标从 0 开始）。如果 i 是偶数，那么我们必须从小等于 (i + 1) 的下标里删掉一个。当删除下标 j 时，原下标大于 j 的数都会受影响（原本连续出现的两个数都能保留的，结果前面删了一下，下标的奇偶性改变了）。这个影响只会让答案不优，因此为了最小化影响，我们直接删除下标 (i + 1) 就好。我们的贪心算法在简化问题中就在做这个事。

回到原问题，如果出现同一个数 ai , ai+1 , ai+2 ,⋯ 连续出现超过两次，当 i 是奇数时，贪心算法会删掉下标大等于 (i + 2) 的部分；当 i 是偶数时，贪心算法会删掉下标大等于 (i + 1) 的部分。其实就是把连续出现的数减到两次，以及简化问题中的操作这两个步骤结合起来一起做。因此贪心算法正确。

T3

传送门

想不到，这题要用对称思想

解题步骤：

1、

2、 

3、 

图片取自这位大佬，很清晰 

了解到思想后自己敲了一遍

class Solution {
private:
   long long pai(long long querie, int intLength){
       long long shu = 1;
       int xx = (intLength + 1) >> 1; //长度取半（向上取整）

       while(-- xx){
            shu *= 10;
       } //前一半的初始数

       if(querie + shu > shu * 10){
           return -1;
       } //判断不存在的情况

       shu = shu + querie - 1; //确定回文数的前一半

       long long zhon; 
       if(intLength & 1){
           zhon = shu / 10; //如果是奇数，需要砍掉一位再复制
       }else{
           zhon = shu; //如果长度是偶数，后一半与前一半相同
       }

       while(zhon){
           shu *= 10;
           shu += zhon % 10;

           zhon /= 10;
       }

       return shu;
   }

public:
    vector kthPalindrome(vector& queries, int intLength) {
        int xx = (intLength + 1) >> 1;

        vector aa; 

        for(int i = 0; i < queries.size(); i ++){
            long long zz = pai(queries[i], intLength);

            aa.push_back(zz);
        }

        return aa;
    }
};