LeetCode第291场周赛题解

比赛地址:https://leetcode-cn.com/contest/weekly-contest-291/

一、移除指定数字得到的最大结果

题解:暴力

比赛时想复杂了,代码又丑又长,还wa了两发…,这里便不给出比赛的思路了。

需要计算删除指定字符后,字符串表示的数字结果最大化。

直接遍历字符串,若当前字符等于需要删除的字符时,则记录若删除当前字符后,所能得到的数字,只要维护这个数字的最大值即可,具体见代码。

C++代码:

class Solution {
public:
    string removeDigit(string number, char digit) {
        int n=number.size();
        string ans="",res;
        for(int i=0;i<n;i++){
            if(number[i]==digit){
                res=number.substr(0,i)+number.substr(i+1,n-i);
                if(res>ans){
                    ans=res;
                }
            }
        }
        return ans;
    }
};

二、必须拿起的最小连续卡牌数

题解:哈希

计算必须最小拿起的连续卡牌数,使得拿起卡牌数中有一对相同数字的卡牌。

只需要记录每个数字第一次出现的下标,若当前遍历的数字为x:

  • 如果前面已经出现过,则直接记录当前需要拿起的连续卡牌数量,并维护最小值。

  • 如果前面没有出现过,则将当前数字以及下标存入到哈希表中。

具体见代码。

C++代码:

class Solution {
public:
    int minimumCardPickup(vector<int>& cards) {
        int n=cards.size();
        map<int,int> mp;
        int ans=0x3f3f3f3f;
        for(int i=0;i<n;i++){
            if(mp.count(cards[i])){
                ans=min(ans,i-mp[cards[i]]+1);
            }
            mp[cards[i]]=i;
        }
        if(ans==0x3f3f3f3f) ans=-1;
        return ans;
    }
};

三、含最多 K 个可整除元素的子数组

题解:哈希

由于数组长度最大为200,所有子数组个数最大为:(其中n为数组长度)

需要判断没有重复的子数组,可以将数字转化为字符,于是便将子数组转化为了字符串,存入到哈希表中判重。

假设当前遍历的下标为i,则直接判断以下边i开头的子数组有多少个满足题意:

  • 如果超过k个可整除的元素,则直接结束循环
  • 如果不超过k个,则判断当前子数组是否出现过,若没出现过则结果加1,同时存到到哈希表中

具体见代码。

C++代码:

class Solution {
public:
    set<string> st;
    int countDistinct(vector<int>& nums, int k, int p) {
        int n=nums.size();
        int ans=0;
        for(int i=0;i<n;i++){
            string s="";int cnt=0;
            for(int j=i;j<n;j++){
                s+=nums[j]+'0';
                if(nums[j]%p==0) ++cnt;
                if(cnt>k) break;
                if(st.count(s)) continue;
                st.insert(s);++ans;
            }
        }
        return ans;
    }
};

四、字符串的总引力

题解:dp

需要计算所有子字符串的引力和。字符串的引力表示为:字符串中出现不同字符的个数。

由于字符串长度最大为$1e^5$,显然按照题三一样两重循环遍历所有子字符串显然不行,考虑dp

dp[i]表示以s[i]结尾的子字符串的所有引力之和。

于是最终结果ans为所有dp[i]的和。

状态转移方程为:

  • 如果前面出现过s[i],则:$dp[i]=dp[i-1]+(i-j-1)+1$,其中j表示s[i]在前面出现的下标,
  • 如果没有出现过s[i],则:$dp[i]=dp[i-1]+i+1$

具体见代码。

C++代码:

class Solution {
public:
    typedef long long ll;
    ll dp[100010];
    long long appealSum(string s) {
        ll ans=1;
        int n=s.size();
        //记录每个字母出现的索引
        int pos[26];
        for(int i=0;i<26;i++) pos[i]=-1;
        pos[s[0]-'a']=0;dp[0]=1;
        for(int i=1;i<n;i++){
            if(pos[s[i]-'a']==-1){
                //没有出现过
                dp[i]=dp[i-1]+i+1;
            }else{
                //前面出现过
                dp[i]=dp[i-1]+(i-pos[s[i]-'a']);
            }
            //更新s[i]最新的下标
            pos[s[i]-'a']=i;
            ans+=dp[i];
        }
        return ans;
    }
};

当然,可以对空间进行优化,对于dp数组,只需要用一个变量sum存储即可。

class Solution {
public:
    typedef long long ll;
    vector<int> ve;
    long long appealSum(string s) {
        int n=s.length();
        int pos[26];
        for(int i=0;i<26;i++) pos[i]=-1;
        ll ans=0,sum=0;
        for(int i=0;i<n;i++){
            if(pos[s[i]-'a']!=-1){
                //前面已经出现过s[i]
                int pre_pos=pos[s[i]-'a'];
                sum+=(i-pre_pos);
            }else{
                //前面没有出现过s[i]
                sum+=(i+1);
            }
            //更新s[i]最新的下标
            pos[s[i]-'a']=i;
            //ans累加
            ans+=sum;
        }
        return ans;
    }
};