leetcode周赛 226

A：模拟题，枚举每一个数，然后求出他应该放在哪一个盒子里面，时间复杂度为n*lgn

 1 class Solution {
 2 public:
 3     int countBalls(int l, int r) {
 4         vector<int> cnt(50,0);
 5         int res=0;
 6         for(int i=l;i<=r;i++){
 7             int t=i;
 8             int sum=0;
 9             while(t){
10                 sum+=t%10,t/=10;
11             }
12             cnt[sum]++;
13             res=max(res,cnt[sum]);
14         }
15         return res;
16     }
17 };

B：给定相邻元素，求可行的原数组。

可以直接应用树模型（个人理解有点像拓扑序），根节点是度为1的点。

 1 class Solution {
 2 public:
 3     unordered_map<int,vector<int>> e;
 4     vector<int> path;
 5     unordered_map<int,int> cnt;
 6     void dfs(int root,int father){
 7         path.push_back(root);
 8         for(auto x:e[root]){
 9             if(x!=father){
10                 dfs(x,root);
11             }
12         }
13     }
14     vector<int> restoreArray(vector<vector<int>>& ad) {
15         for(auto x:ad){
16             int a=x[0],b=x[1];
17             e[a].push_back(b);
18             e[b].push_back(a);
19             cnt[a]++,cnt[b]++;
20         }
21         int root=-1;
22         for(auto x:cnt){
23             if(x.second==1){
24                 root=x.first;
25                 break;
26             }
27         }
28         dfs(root,-1);
29         return path;
30     }
31 };

C：题意很绕，加一或者不加的问题给我整吐了。

给定n种糖果及其数量，只能够按照顺序吃，问能否在每天吃糖果数量1<=s<=c情况下，在第d天吃到第t种糖果。

假设将糖果一个一个的摊开摆放，编号从1开始。

首先因为每天只能吃1<=s<=c个糖果，而且天数是从0开始编号的，所以d天吃的糖果的编号为[ d+1 , (d+1)*c ]。

如此一来只需要知道第t种糖果的编号范围，再求两个区间是否有交，就可以判断答案是否为真了。

 1 typedef long long LL;
 2 class Solution {
 3 public:
 4     int check(LL a,LL b,LL c,LL d){
 5         if(c>b||a>d){
 6             return false;
 7         }
 8         return true;
 9     }
10     vector<bool> canEat(vector<int>& w, vector<vector<int>>& queries) {
11         int n=w.size();
12         vector<LL> pre(n+1);
13         for(int i=1;i<=n;i++){
14             pre[i]=pre[i-1]+w[i-1];
15         }
16         vector<bool> res;
17         for(auto x:queries){
18             int t=x[0],d=x[1],c=x[2];
19             if(check(d+1,LL(d+1)*c,pre[t]+1,pre[t]+w[t]))
20                 res.push_back(true);
21             else
22                 res.push_back(false);
23         }
24         return res;
25     }
26 };

D：分割回文串，问能否将一个字符串分割成三份，每一份都是回文串。

首先dp，初始化出来一个f数组，f( i , j )表示i~j是否是一个回文串。

之后直接枚举分割点就可以了。

 1 class Solution {
 2 public:
 3     bool checkPartitioning(string s) {
 4         int n=s.size();
 5         vector<vector<int>> f(n,vector<int>(n));
 6         for(int i=n-1;i>=0;i--){
 7             for(int j=i;j<n;j++){
 8                 if(i==j) f[i][j]=true;
 9                 else if(i+1==j) f[i][j]=s[i]==s[j];
10                 else f[i][j]=(s[i]==s[j]&&f[i+1][j-1]);
11             }
12         }
13         for(int i=1;i<n;i++){
14             for(int j=i+1;j<n;j++){
15                 if(f[0][i-1]&&f[i][j-1]&&f[j][n-1]){
16                     return true;
17                 }
18             }
19         }
20         return false;
21     }
22 };