模拟计数即可
class Solution { public: vector<int> mostVisited(int n, vector<int>& rounds) { vector<int> cnt(n+1); vector<int>v; int m = rounds.size(); if(!m) return v; cnt[rounds[0]]=1; for(int i=1;i<m;++i) { int k = rounds[i-1]; do { if(++k==n+1) k=1; cnt[k]++; }while(k!=rounds[i]); } int ans = 1; for(int i=2;i<=n;++i) { if(cnt[i]>cnt[ans]) ans = i; } for(int i=1;i<=n;++i) { if(cnt[i]==cnt[ans]) v.push_back(i); } return v; } };有 3n 堆数目不一的硬币，你和你的朋友们打算按以下方式分硬币：
每一轮中，你将会选出 任意 3 堆硬币（不一定连续）。 Alice 将会取走硬币数量最多的那一堆。 你将会取走硬币数量第二多的那一堆。 Bob 将会取走最后一堆。 重复这个过程，直到没有更多硬币。 给你一个整数数组 piles ，其中 piles[i] 是第 i 堆中硬币的数目。
返回你可以获得的最大硬币数目。
每次让Bob取最小的，Alice取第二大的，取n/3次。贪心。排序之后依次选a[n-2],a[n-4]… 选n/3个
class Solution { public: int maxCoins(vector<int>& piles) { int n = piles.size(); if(!n) return 0; int ans = 0; sort(piles.begin(),piles.end()); int id = n-2; int t = n/3; for(int i=1;i<=t;++i) { ans += piles[id]; id -= 2; } return ans; } };给你一个数组 arr ，该数组表示一个从 1 到 n 的数字排列。有一个长度为 n 的二进制字符串，该字符串上的所有位最初都设置为 0 。
在从 1 到 n 的每个步骤 i 中（假设二进制字符串和 arr 都是从 1 开始索引的情况下），二进制字符串上位于位置 arr[i] 的位将会设为 1 。
给你一个整数 m ，请你找出二进制字符串上存在长度为 m 的一组 1 的最后步骤。一组 1 是一个连续的、由 1 组成的子串，且左右两边不再有可以延伸的 1 。
返回存在长度 恰好 为 m 的 一组 1 的最后步骤。如果不存在这样的步骤，请返回 -1 。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-latest-group-of-size-m 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
用L[x]表示位置x最左边连续的1的位置，用R[x]表示位置x最右边连续的1的位置。开始初始化都为-1插入一个结点后，先修改L[x] = R[x] = x，然后看是否可以和左边合并，如果可以，更新L[x]=L[x-1], 看是否可以和右边合并，如果可以，更新R[x] = R[x+1], 然后我们更新左边连通块的值和右边连通块的值。如果左边有1，那么我们让R[L[x-1]] = R[x-1] = R[x], 如果右边也有1，那么让L[x+1] = L[R[x+1]] = L[x]我们只需要更新连通块左右端点的L[i]和R[i]即可，中间的可以不管。因为我们在进行区间合并的时候，只要知道区间端点就可以知道是否要合并。我们可以维护一个cnt，表示当前长度为m的连续1的个数。用last记录最后的出现m的轮数。在插入的时候，插入a[x]=1, 我们计算出R[x]和L[x]之后，如果R[x]-L[x]+1==m，那么说明新增一个，cnt++, 如果左边a[x-1]所在连通块本来长度为m，加入a[x]后边长，那么cnt–, 右边同理。 #include <bits/stdc++.h> using namespace std; class Solution { public: int findLatestStep(vector<int>& arr, int m) { int n = arr.size(); vector<int> v(n+1,0),L(n+1,-1),R(n+1,-1); int cnt = 0; //长度为m的最长子串的个数 int last = -1; for(int i=0;i<n;++i) { int x = arr[i]; v[x] = 1; L[x] = R[x] = x; if(x!=1&&v[x-1]==1) { L[x] = L[x-1]; } if(x!=n&&v[x+1]==1) { R[x] = R[x+1]; } if(R[x]-L[x]+1==m) { ++cnt; } if(x!=1&&v[x-1]==1) { if(R[x-1]-L[x-1]+1==m) --cnt; R[x-1] = R[x]; R[L[x-1]] = R[x]; } if(x!=n&&v[x+1]==1) { if(R[x+1]-L[x+1]+1==m) --cnt; L[x+1] = L[x]; L[R[x+1]] = L[x]; } if(cnt>0) last = i+1; } return last; } }; int main(void) { Solution * sol = new Solution(); vector<int> v = {3,2,5,6,10,8,9,4,1,7}; cout<<sol->findLatestStep(v,3)<<endl; return 0; }几块石子 排成一行 ，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。
游戏中的每一轮：Alice 会将这行石子分成两个 非空行（即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。
只 剩下一块石子 时，游戏结束。Alice 的分数最初为 0 。
返回 Alice 能够获得的最大分数 。
开始想的是贪心，每次二分出左边stoneValue的和不超过一半的最长序列，向下递归，二分出右边stoneValue的和不超过一般的最长序列，向下递归。后来发现，这样贪心可能有问题[98,77,24,49,6,12,2,44,51,96]这个数据输出应该是330，贪心的输出是307。 所以发现还得遍历每一个不超过一半的序列，都递归。但是这样O(n^3)会超时，所以加一个记忆化即可。
贪心二分+递归代码如下
class Solution { public: void dfs(int st,int ed,int presum,int& ans,vector<int>& s,vector<pair<int,int> >&r) { if(ed<=st) { ans = max(ans,presum); // for(auto x:r) printf("[%d,%d],",x.first,x.second); // cout<<" presum = "<<presum<<endl; return; } int sum = s[ed]-s[st-1]; int left = st-1, right = ed+1; while(right-left>1) { int mid = (left+right)>>1; if((s[mid]-s[st-1])*2<=sum) left = mid; else right = mid; } r.push_back(make_pair(st,left)); dfs(st,left,presum+s[left]-s[st-1],ans,s,r); r.pop_back(); left = st-1,right = ed+1; while(right-left>1) { int mid = (right+left)>>1; if((s[ed]-s[mid-1])*2<=sum) right = mid; else left = mid; } r.push_back(make_pair(right,ed)); dfs(right,ed,presum+s[ed]-s[right-1],ans,s,r); r.pop_back(); } int stoneGameV(vector<int>& stoneValue) { int n = stoneValue.size(); if(!n) return 0; vector<int> s(n+1,0); for(int i=1;i<=n;++i) s[i] = s[i-1]+stoneValue[i-1]; int ans = 0; vector<pair<int,int>> r; dfs(1,n,0,ans,s,r); return ans; } };记忆化搜索代码如下：
#include <bits/stdc++.h> using namespace std; class Solution { public: int dfs(int st,int ed,vector<int>& s,vector<vector<int>>& dp) { if(dp[st][ed]!=-1) return dp[st][ed]; if(st>=ed) { return dp[st][ed] = 0; } int & ans = dp[st][ed] = 0; for(int mid=st;mid<ed;++mid) { int sumL = s[mid]-s[st-1], sumR = s[ed]-s[mid]; if(sumL<=sumR) ans = max(ans,sumL+dfs(st,mid,s,dp)); if(sumL>=sumR) ans = max(ans,sumR+dfs(mid+1,ed,s,dp)); } return ans; } int stoneGameV(vector<int>& stoneValue) { int n = stoneValue.size(); if(!n) return 0; vector<int> s(n+1,0); vector<vector<int> > dp(n+1,vector<int>(n+1,-1)); for(int i=1;i<=n;++i) s[i] = s[i-1]+stoneValue[i-1]; return dfs(1,n,s,dp); } }; int main(void) { Solution * sol = new Solution(); vector<int> v = {98,77,24,49,6,12,2,44,51,96}; cout<<sol-> stoneGameV(v)<<endl; return 0; }2020.9.4 13:31
