今日学习记录
1. 生成赛程leetcode.3680
关键词：数学 模拟
问题分析：
- 就是 n 个队,两两相比较,分主场和副场,但是每队不能在相邻天比赛
核心思路
- 就是先安排 i 为奇数和偶数时的比赛,取 1 和 n-1,微调这两个比赛,当 n 为偶数的时候,首尾会出现冲突,i 为 n 的时候会余成 0,而第二个数开始遍历的时候,会从 0 开始,所以会冲突,安排奇偶数的方法
vector<vector<int>> generateSchedule(int n) {
//0,1,2,3,4
//1,0,2,3,4
//2,0,1,3,4
//3,0,1,2,4
//4,0,1,2,3
//0,1;2,3;4,0;1,2;3,4;
//可以简单枚举,4及4以下是不符合的
if(n<=4) return {};
//可以看出来,这里,先直接单独的枚举,每个组的数据都隔了一个数,直接在原来基础上加上2
//二的间隔跳跃要首项的两个数
//1,3,5,7,9;2,4,6,8,10;
int d = 1;
vector<vector<int>> arr;
for(int i = 0;i<n;i+=2){
arr.push_back({i,(i+d)%n});
}
//0,1;2,3;4,0;1,2;3,4;4,1;
for(int i = 1;i<n;i+=2){
arr.push_back({i,(i+d)%n});
}
//若n为偶数,在首尾时会出现意外,单独处理尾数偶数的情况
//5,0与0,2冲突
if(n%2==0) swap(arr.back(),arr[arr.size()-2]);
//处理1~n-1的所有情况
for(d = 2;d<n-1;d++){
for(int i = 0;i<n;i++){
arr.push_back({i,(i+d)%n});
}
}
//再但单独处理n-1的情况
d = n-1;
for(int i = 1;i<n;i+=2){
arr.push_back({i,(i+d)%n});
}
//0,1;2,3;4,0;1,2;3,4;4,1;
if(n%2==0) swap(arr.back(),arr[arr.size()-2]);
for(int i = 0;i<n;i+=2){
arr.push_back({i,(i+d)%n});
}
return arr;
}- 那么我想到的是交叉放入,因为我只要保证间隔为 2 的数先放完,再去随机放就行,但是在实现的时候肯定先随机放中间间隔大于 2 的数,再单独去处理 1 和 n-1
vector<vector<int>> generateSchedule(int n) {
if(n<=4) return {};
vector<vector<int>> arr;
for(int d = 2;d<n-1;d++){
for(int i = 0;i<n;i++){
arr.push_back({i,(i+d)%n});
}
}
//单独处理1和n-1;
for(int i = 0;i<n;i++){
arr.push_back({i,(i+1)%n});
arr.push_back({(i+n-1)%n,(i+n-2)%n});
}
return arr;
}- 还有一种解法,就是真正意义上的随机化,随机生成一种序列然后检查是否符合条件,这种方法太复杂,而且最坏情况时间复杂度高,不建议 **最终代码：
vector<vector<int>> generateSchedule(int n) {
//0,1,2,3,4
//1,0,2,3,4
//2,0,1,3,4
//3,0,1,2,4
//4,0,1,2,3
//0,1;2,3;4,0;1,2;3,4;
//可以简单枚举,4及4以下是不符合的
if(n<=4) return {};
//可以看出来,这里,先直接单独的枚举,每个组的数据都隔了一个数,直接在原来基础上加上2
//二的间隔跳跃要首项的两个数
//1,3,5,7,9;2,4,6,8,10;
int d = 1;
vector<vector<int>> arr;
for(int i = 0;i<n;i+=2){
arr.push_back({i,(i+d)%n});
}
//0,1;2,3;4,0;1,2;3,4;4,1;
for(int i = 1;i<n;i+=2){
arr.push_back({i,(i+d)%n});
}
//若n为偶数,在首尾时会出现意外,单独处理尾数偶数的情况
//5,0与0,2冲突
if(n%2==0) swap(arr.back(),arr[arr.size()-2]);
//处理1~n-1的所有情况
for(d = 2;d<n-1;d++){
for(int i = 0;i<n;i++){
arr.push_back({i,(i+d)%n});
}
}
//再但单独处理n-1的情况
d = n-1;
for(int i = 1;i<n;i+=2){
arr.push_back({i,(i+d)%n});
}
//0,1;2,3;4,0;1,2;3,4;4,1;
if(n%2==0) swap(arr.back(),arr[arr.size()-2]);
for(int i = 0;i<n;i+=2){
arr.push_back({i,(i+d)%n});
}
return arr;
}学到的点：
- 模拟