LeetCode冲刺：Day8

发布于 2022-11-15  1051 次阅读

继续刷往期周赛。目前Medium题独立解出占比大概7成。

1. 使数组相等的最小开销

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

主要问题在于，应该让所有元素变成哪个数字？这题完全是数学问题。参考这篇。

代码

class Solution {
public:
    long long sumCost(const vector<int>& nums, const vector<int>& cost, int mid) {
        const int n = nums.size();
        long long ans = 0;
        for (int i = 0;i < n;++i)
            ans += 1ll * cost[i] * abs(nums[i] - mid);
        return ans;
    }

    long long minCost(const vector<int>& nums, const vector<int>& cost) {
        const auto [minit, maxit] = minmax_element(nums.begin(), nums.end());
        long long lo = *minit, hi = *maxit;
        while (lo < hi) {
            const int mi = (lo + hi) / 2;
            if (sumCost(nums, cost, mi) > sumCost(nums, cost, mi + 1))
                lo = mi + 1;
            else hi = mi;
        }
        return sumCost(nums, cost, lo);
    }
};

2. 使数组相似的最少操作次数

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

考虑到偶数和奇数并存，我选择了排序后再遍历，每次判断奇偶对应关系，但用例验证失败。

看到答案的标题是“按奇偶性分类贪心”，我忽然明白了，直接把奇偶分开处理就好了！且数字按次序对应，局部最优推出全局最优。

代码

class Solution {
public:
    long long makeSimilar(vector<int>& nums, vector<int>& target) {
        vector<int> oddNums;
        vector<int> pairNums;
        vector<int> oddTarget;
        vector<int> pairTarget;
        sort(nums.begin(),nums.end());
        sort(target.begin(),target.end());
        for (auto elem:nums) {
            if (elem%2==1) oddNums.push_back(elem);
            else pairNums.push_back(elem);
        }

        for (auto elem:target) {
            if (elem%2==1) oddTarget.push_back(elem);
            else pairTarget.push_back(elem);
        }

        long long oddOps=0,pairOps=0;
        int m=oddNums.size();
        int n=pairNums.size();
        for (int i=0;i<m;++i) {
            oddOps+=abs(oddNums[i]-oddTarget[i])/2;
        }
        for (int i=0;i<n;++i) {
            pairOps+=abs(pairNums[i]-pairTarget[i])/2;
        }
        return (oddOps+pairOps)/2;
    }
};

3. 与对应负数同时存在的最大正整数

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

双指针法。先排序，然后i指向首元素，j指向尾元素。如果元素i的负等于元素j，那么返回元素j，如果大于，让i++，如果小于，让j--。最后如果i指向了正数，或j指向了负数，跳出循环返回-1。

代码

class Solution {
public:
    int findMaxK(vector<int>& nums) {
        if (nums.size()==1) return -1;
        sort(nums.begin(),nums.end());
        int i=0,j=nums.size()-1;
        while (nums[i]<0&&nums[j]>0) {
            if (nums[i]==-nums[j]) return nums[j];
            else if (-nums[i]>nums[j]) ++i;
            else --j;
        }
        return -1;
    }
};

4. 反转之后不同整数的数目

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

先写辅助函数 int revert() ，输入int，输出反转后的int。将数组大小数量的正数反转并添加到末尾后，排序，并计算数字的种数。顺利通过，性能略差。

代码

class Solution {
private:
    int revert(const int& x) {
        vector<short> pos;
        int y=x;
        while (y!=0) {
            pos.push_back(y%10);
            y/=10;
        }
        for (int i=0;i<pos.size();++i) y+=pos[i]*pow(10,pos.size()-i-1);
        return y;
    }
public:
    int countDistinctIntegers(vector<int>& nums) {
        int n=nums.size();
        for (int i=0;i<n;++i) nums.push_back(revert(nums[i]));
        sort(nums.begin(),nums.end());
        int ans=1;
        for (int i=1;i<nums.size();++i) if (nums[i]!=nums[i-1]) ++ans;
        return ans;
    }
};

5. 反转之后的数字和

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

暴力法。但我自己想的反转算法效率不佳，换用更好的算法后，暴力法也能超过90%了

代码

class Solution {
private:
    int revert(int x) {
        int y=0;
        while(x) {
            y=y*10+x%10;
            x/=10;
        }
        return y;
    }
public:
    bool sumOfNumberAndReverse(int num) {
        for (int start=num/2;start<=num;++start) if (start+revert(start)==num) return true;
        return false;
    }
};

6. 统计定界子数组的数目

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

参考这篇

实际上我们关心的是minK、maxK和越界数的位置。因为只要求子数组元素在范围内即可，所以数组数目是可以直接根据位置得出的。还需要加深理解。

代码

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int minK, int maxK) {
        long long ans=0;
        int n=nums.size(),min_i=-1,max_i=-1,i0=-1;
        for (int i=0;i<n;++i) {
            int x=nums[i];
            if (x==minK) min_i=i;
            if (x==maxK) max_i=i;
            if (x>maxK||x<minK) i0=i;
            ans+=max(0,min(min_i,max_i)-i0);
        }
        return ans;
    }
};

7.

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

情况有限，直接枚举即可。

代码

class Solution {
public:
    int countTime(string time) {
        int ans=1;
        if (time[0]=='?'&&time[1]=='?') {
            ans*=24;
        } else if (time[0]=='?'&&int(time[1])-48<=3) ans*=3;
        else if (time[0]=='?'&&int(time[1])-48>3) ans*=2;
        else if (time[0]=='2'&&time[1]=='?') ans*=4;
        else if ((time[0]=='0'||time[0]=='1')&&time[1]=='?') ans*=10;

        if (time[3]=='?') ans*=6;
        if (time[4]=='?') ans*=10;
        return ans;
    }
};

8. 二的幂数组中查询范围内的乘积

难度

  • Easy
  • Medium
  • Hard

完成情况

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

思路

不算太难，按部就班即可。

首先计算powers数组，按照我的想法，每次找到一个最大的，小于n的2的幂，加到数组首部，然后n减掉这个数，继续计算，直到n=0。从运行情况看这个算法没有问题。

然后按描述计算每次查询的结果即可。为了防止溢出，需要直到模运算的性质，即两数相乘取模，等于两数分别取模后相乘再取模。所以每次乘上一个数前先对其取模，乘完再取个模。但即便这样，每次的临时变量用int还是溢出，改成long long后正常通过。

代码

class Solution {
private:
    int maxMi(int x) {
        int y=1;
        while (y<=x) {
            y*=2;
        }
        return y/2;
    }
public:
    vector<int> productQueries(int n, vector<vector<int>>& queries) {
        vector<int> powersReverse;
        while (n!=0) {
            int x=maxMi(n);
            powersReverse.push_back(x);
            n-=x;
        }
        vector<int> powers(powersReverse.rbegin(),powersReverse.rend());
        vector<int> ans(queries.size());
        for (int i=0;i<queries.size();++i) {
            long long res=1;
            for (int j=queries[i][0];j<=queries[i][1];++j) {
                res*=powers[j]%(1000000007LL);
                res%=(1000000007LL);
            }
            ans[i]=res;
        }
        return ans;
    }
};