题解 | #环形链表的约瑟夫问题#
环形链表的约瑟夫问题
http://www.nowcoder.com/practice/41c399fdb6004b31a6cbb047c641ed8a
题意：
编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。
下一个人继续从 1 开始报数。
n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？
方法：
模拟
思路：模拟。
首先，初始化 vis[ ] 数组表示每个人的状态；
遍历环形数组，报到m的人修改vis[ ] 数组的状态；一直循环遍历，直到只剩一个人。最后，返回最后留下的人编号。
class Solution {
public:
int vis[10005]={0};//判断是否离开
int ysf(int n, int m) {
int cnt=n,num=0;
for(int i=1;i<=n;i++){//循环
if(vis[i]==0){
num++;
if(num==m){//报到m的人离开
vis[i]=1;
cnt--;
if(cnt==1)
break;
num=0;
}
}
if(i==n){//保证环形
i=0;
}
}
for(int i=1;i<=n;i++){//返回最后留下的人编号
if(vis[i]==0){
return i;
}
}
return 0;
}
};
时间复杂度：%2C%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6%3D%E5%9C%88%E6%95%B0*%E6%95%B0%E7%BB%84%E9%95%BF%E5%BA%A6%E3%80%82)
空间复杂度:%2Cvis%5B%20%5C%20%5D%E6%95%B0%E7%BB%84%E5%AD%98%E5%82%A8%E6%AF%8F%E4%B8%AA%E4%BA%BA%E7%9A%84%E7%8A%B6%E6%80%81%E3%80%82)
OPPO公司福利 1225人发布
「端到端耗时缩减30-40%」要给出确切数字和绝对值。从1000ms降到600ms是降了40%，从100ms降到60ms也是降了40%，但这两个含义完全不一样。其他也是，涉及到数据，准备好证据，口径统一，面试会问
「熟练」「熟悉」「了解」混在一起用，读起来很乱。而且「了解前端需求」最好改成「具备前后端协作经验」