从班助那里得知了这个网站，据说做上面的题对找工作有好处。题挺简单的，可以划划水放松放松。

A. 根据数字二进制下 1 的数目排序

题目链接

题目描述

给你一个整数数组 $arr$ 。请你将数组中的元素按照其二进制表示中数字 $1$ 的数目升序排序。

如果存在多个数字二进制中 $1$ 的数目相同，则必须将它们按照数值大小升序排列。

请你返回排序后的数组。

思路

直接暴力求出每一个数的二进制下 $1$ 的个数，排序输出即可。
这题是简单难度。

代码

class Solution {
public:
    struct node
    {
        int x,val;
        bool operator &lt; (const node xx) const
        {
            if(xx.val==val) return x &lt; xx.x;
            return val &lt; xx.val;
        }
    } a[505];
    vector &lt;int&gt; sortByBits(vector &lt;int&gt; & arr) {
        int cnt=arr.size();
        for(int i=0;i &lt; arr.size();i++)
        {
            a[i].x=arr[i];
            a[i].val=0;
            for(int j=0;j &lt; 32;j++)
            {
                if(a[i].x&(1 &lt;&lt; j)) a[i].val++;
            }
        }
        sort(a,a+arr.size());
        arr.clear();
        for(int i=0;i &lt; cnt;i++) arr.push_back(a[i].x);
        return arr;
    }
};

B. 每隔 n 个顾客打折

题目链接

题目描述

超市里正在举行打折活动，每隔 n 个顾客会得到 discount 的折扣。

超市里有一些商品，第 i 种商品为 products[i] 且每件单品的价格为 prices[i] 。

结账系统会统计顾客的数目，每隔 n 个顾客结账时，该顾客的账单都会打折，折扣为 discount （也就是如果原本账单为 x ，那么实际金额会变成 x - (discount * x) / 100 ），然后系统会重新开始计数。

顾客会购买一些商品， product[i] 是顾客购买的第 i 种商品， amount[i] 是对应的购买该种商品的数目。

请你实现 Cashier 类：

Cashier(int n, int discount, int[] products, int[] prices) 初始化实例对象，参数分别为打折频率 n ，折扣大小 discount ，超市里的商品列表 products 和它们的价格 prices 。
double getBill(int[] product, int[] amount) 返回账单的实际金额（如果有打折，请返回打折后的结果）。返回结果与标准答案误差在 10^-5 以内都视为正确结果。

思路

直接模拟就好了，这题的难度是中等。

代码

class Cashier {
public:
    int qn=0,qd,cnt=0;
    double pri[10005];
    Cashier(int n, int discount, vector &lt; int>& products, vector &lt; int>& prices) {
        qn=n;
        qd=discount;
        for(int i=0;i &lt; products.size();i++)
        {
            int x=products[i];
            pri[x]=prices[i];
        }
    }
    
    double getBill(vector &lt; int> product, vector &lt; int> amount) {
        double ans=0;
        for(int i=0;i &lt; product.size();i++)
        {
            ans+=pri[product[i]]*amount[i];
        }
        cnt++;
        if(cnt==qn)
        {
            ans-=((double)qd*ans)/100.0;
            cnt=0;
        }
        return ans;
    }
};

/**
 * Your Cashier object will be instantiated and called as such:
 * Cashier* obj = new Cashier(n, discount, products, prices);
 * double param_1 = obj->getBill(product,amount);
 */

C. 包含所有三种字符的子字符串数目

题目链接

题目描述

给你一个字符串 s ，它只包含三种字符 a, b 和 c 。

请你返回 a，b 和 c 都至少出现过一次的子字符串数目。

思路

因为数据范围还是有 50,000 的，所以不能直接模拟，需要简单想一想。
因为要求出所有满足条件的子字符串的数量，考虑第 $i$ 位字符的贡献。假设另外两个字符在 $i+1$ - $n$ 的最早出现位置 $pos1$ , $pos2$ ，那么贡献就为 $n-max(pos1,pos2)+1$ ，因为从 $i$ 开始到 $max(pos1,pos2)$ 之后的所有子字符串一定都包含了三个字符，符合条件。

代码

class Solution {
public:
    int nxt[50005][5],last[5];
    int numberOfSubstrings(string s) {
        int n=s.length()-1;
        last[0]=last[1]=last[2]=0x7f7f7f7f;
        for(int i=n;~i;i--)
        {
            for(int j=0;j &lt; =2;j++) nxt[i][j]=last[j];
            last[s[i]-'a']=i;
        }
        int ans=0;
        for(int i=0;i &lt; =n;i++)
        {
            int a,b;
            if(s[i]=='a') a=1,b=2;
            else if(s[i]=='b') a=0,b=2;
            else if(s[i]=='c') a=0,b=1;
            int x=max(nxt[i][a],nxt[i][b]);
            if(x==0x7f7f7f7f) continue;
            ans+=(n-x+1);
        }
        return ans;
    }
};

D. 有效的快递序列数目

题目链接

题目描述

给你 n 笔订单，每笔订单都需要快递服务。

请你统计所有有效的收件/配送序列的数目，确保第 i 个物品的配送服务 delivery(i) 总是在其收件服务 pickup(i) 之后。

由于答案可能很大，请返回答案对 1e9 + 7 取余的结果。

思路

设f[i][j]表示已经收了i个快递，且配送了j个快递(j≤i)
那么状态转移方程为

f[i][j]+=f[i-1][j]*(n-i+1//从n-i+1个还没有收的快递中随机收一个快递
f[i][j]+=f[i][j-1]*(i-j+1)//从已经收了的但还没有配送的(i-j+1)个快递中随便选一个配送
最后我们是既收取完n个快递，又配送完n个快递，所以答案为f[n][n]

当然排列组合、插空法、一维dp等等都可以解决，这题是困难难度。

代码

class Solution {
public:
    long long f[505][505];
    long long mod=1e9+7;
    int countOrders(int n) {
        f[0][0]=1;
        for(int i=1;i &lt; =n;i++)
        {
            for(int j=0;j &lt; =n;j++)
            {
                f[i][j]+=f[i-1][j]*(n-i+1);
                if(j) f[i][j]+=f[i][j-1]*(i-j+1);
                f[i][j]%=mod;
            }
        }
        int ans=(int)f[n][n];
        return ans;
    }
};

biweekly-contest-20