classSolution{public:intminCount(vector<int>& coins){int i, sum =0;for(i =0; i < coins.size();++i)sum +=ceil(coins[i]/2.0);return sum;}};
執行用時：4 ms 內存消耗：8.4 MB
2.2 傳遞信息 Esay
題目鏈接 小朋友 A 在和 ta 的小伙伴們玩傳信息游戲，游戲規則如下：
有 n 名玩家，所有玩家編號分別為 0 ～ n-1，其中小朋友 A 的編號為 0
每個玩家都有固定的若干個可傳信息的其他玩家（也可能沒有）。
傳信息的關系是單向的（比如 A 可以向 B 傳信息，但 B 不能向 A 傳信息）。
每輪信息必須需要傳遞給另一個人，且信息可重復經過同一個人
給定總玩家數 n，以及按 [玩家編號,對應可傳遞玩家編號] 關系組成的二維數組 relation。 返回信息從小 A (編號 0 ) 經過 k 輪傳遞到編號為 n-1 的小伙伴處的方案數；若不能到達，返回 0。
示例 1：
輸入：n =5, relation =[[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k =3
輸出：3
解釋：信息從小 A 編號 0 處開始，經 3 輪傳遞，到達編號 4。
共有 3 種方案，分別是 0->2->0->4， 0->2->1->4， 0->2->3->4。示例 2：
輸入：n =3, relation =[[0,2],[2,1]], k =2
輸出：0
解釋：信息不能從小 A 處經過 2 輪傳遞到編號 2限制：
2<= n <=101<= k <=51<= relation.length <=90, 且 relation[i].length ==20<= relation[i][0],relation[i][1]< n
且 relation[i][0]!= relation[i][1]
解答：
把路徑的邊插入set，方便后面快速查找
dp[i][j] 表示第i次傳遞到j的方案數
classSolution{public:intnumWays(int n, vector<vector<int>>& relation,int k){set<vector<int>> s;for(auto re : relation)s.insert(re);vector<vector<int>>dp(k+1,vector<int>(n,0));dp[0][0]=1;//初始狀態for(int i =1; i <= k;++i)//k次傳遞{for(int j =0; j < n;++j){//n個人，如果存在傳遞到這的情況if(dp[i-1][j]!=0){for(int k =0; k < n;++k){//傳給下一個人，可以傳給跟自己有關系的if(s.count({j,k}))//有關系dp[i][k]+= dp[i-1][j];}}}}return dp[k][n-1];}};
執行用時：8 ms 內存消耗：7.6 MB
classSolution{//更簡潔的版本public:intnumWays(int n, vector<vector<int>>& relation,int k){int dp[6][10]={0};dp[0][0]=1;for(int i=0;i<k;i++)for(auto ss:relation)dp[i+1][ss[1]]+= dp[i][ss[0]];return dp[k][n-1];}//參看作者：xunh};
classSolution{public:intminJump(vector<int>& jump){int i, j, n = jump.size(), t =0, size,tp;set<int> set;for(i =0; i < n;++i)set.insert(i);queue<int> q;q.push(0);set.erase(0);while(!q.empty()){size = q.size();t++;while(size--){tp = q.front();q.pop();if(tp+jump[tp]>= n)return t;if(set.count(tp+jump[tp])){q.push(tp+jump[tp]);set.erase(tp+jump[tp]);}auto end = set.upper_bound(tp);//這個地方多了lgn的查找，用數組降到O(1)for(auto it = set.begin(); it != end;++it){q.push(*it);set.erase(*it);}}}return t;}};
改進的BFS
classSolution{public:intminJump(vector<int>& jump){int i, n = jump.size(), t =0, size, tp, prevPos =0;vector<bool>vis(n,false);vis[0]=true;queue<int> q;q.push(0);while(!q.empty()){size = q.size();t++;while(size--){tp = q.front();q.pop();if(tp+jump[tp]>= n)return t;if(!vis[tp+jump[tp]]){//向右跳過來q.push(tp+jump[tp]);vis[tp+jump[tp]]=true;}for(i = prevPos+1; tp >0&& i < tp;++i){//向左位置跳if(!vis[i]){q.push(i);vis[i]=true;}}prevPos =max(prevPos,tp);//沒有這句會超時//避免重復檢查某些位置}}return t;}};
