本文主要是介绍LeetCode第 20 场双周赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.根据数字二进制下 1 的数目排序
/*** Note: The returned array must be malloced, assume caller calls free().*/int cal(int num){int sum=0;while(num){sum+=num%2;num/=2;}return sum;}
int* sortByBits(int* arr, int arrSize, int* returnSize){int i,tmp,j;int *onenum=(int*)malloc(sizeof(int)*(arrSize+1));for(i=0;i<arrSize;i++){onenum[i]=cal(arr[i]);}for(i=0;i<arrSize-1;i++){for(j=i+1;j<arrSize;j++){if(onenum[i]>onenum[j]||(onenum[i]==onenum[j]&&arr[i]>arr[j])){tmp=onenum[i];onenum[i]=onenum[j];onenum[j]=tmp;tmp=arr[i];arr[i]=arr[j];arr[j]=tmp;}}}*returnSize=arrSize;return arr;
}2.每隔 n 个顾客打折
typedef struct {int n;int now;int discount;int* products;int productsSize;int* prices;int pricesSize;
} Cashier;Cashier* cashierCreate(int n, int discount, int* products, int productsSize, int* prices, int pricesSize) {Cashier* t=(Cashier*)malloc(sizeof(Cashier));t->n=n;t->now=0;t->discount=discount;t->products=products;t->productsSize=productsSize;t->prices=prices;t->pricesSize=pricesSize;return t;
}double cashierGetBill(Cashier* obj, int* product, int productSize, int* amount, int amountSize) {obj->now++;double sum=0;for(int i=0;i<productSize;i++){for(int j=0;j<obj->productsSize;j++){if(obj->products[j]==product[i]){sum=sum+obj->prices[j]*amount[i];break;}}}if(obj->now==obj->n){sum=sum-(obj->discount*sum)/100;obj->now=0;}return sum;
}void cashierFree(Cashier* obj) {
free(obj);
}/*** Your Cashier struct will be instantiated and called as such:* Cashier* obj = cashierCreate(n, discount, products, productsSize, prices, pricesSize);* double param_1 = cashierGetBill(obj, product, productSize, amount, amountSize);* cashierFree(obj);
*/3.包含所有三种字符的子字符串数目
【思路】考虑子串是否包含abc，且重复的子串也算。我们每次从i开始遍历，计算i开始的字符串中有多少个符合要求的子串。如果采用双循环，会超时。在这里需要优化一下，其实遍历i开始的字符串我们只需要保存上一次遍历的末尾 j，而j前面遍历的结果已经存在数组d中。
我们用一个数组d[3]来存放出现的abc的次数。如果d[0],d[1],d[2]都不为0，表示当前子串已经出现了abc字母，那么接下来j后面的字符无需遍历，因为再加入任何一个字符，都可以组成符合要求的字符串。
int numberOfSubstrings(char * s){int i,j=0,len,sum=0,tmp;int d[3]={0};len=strlen(s);if(len<3)return 0;for(i=0;i<len;i++){while(j<len&&(d[0]==0||d[1]==0||d[2]==0)){d[s[j]-'a']++;j++;}if(!(d[0]==0||d[1]==0||d[2]==0)){sum+=len-j+1;}d[s[i]-'a']--;}return sum;
}4.有效的快递序列数目
【思路】用dp[i][j]表示当前收件为i件，发件为j件。当前的操作分为收件和发件。
对于收件：dp[i][j]+=dp[i-1][j]*(n-(i-1));其中，收件可以是剩下包裹n-(i-1)中的任意一件
对于发件：dp[i][j]+=dp[i][j-1]*(i-(j-1));其中，发件可以是当前收件i除去已发的j-1，剩余i-(j-1)中任意一件
int countOrders(int n){long long i,j,dp[n+1][n+1];memset(dp,0,sizeof(dp));long long mod=1000000007;dp[0][0]=1;//已发0件，已收0件，方案为1for(i=1;i<=n;i++){for(j=0;j<=i;j++){
//如果当前是收件，那么收件可以是剩下包裹n-(i-1)中的任意一件dp[i][j]+=dp[i-1][j]*(n-(i-1));dp[i][j]%=mod;
//如果当前是发件，那么发件可以是当前收件i除去已发的j-1，剩余i-(j-1)中任意一件if(j>0)dp[i][j]+=dp[i][j-1]*(i-(j-1));dp[i][j]%=mod;}}return (int)dp[n][n];
}
这篇关于LeetCode第 20 场双周赛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
