巴彦淖尔网站制作,一键开发小程序,石家庄在线制作网站,网站运营推广的方法有哪些字典序
在刷题和计算机科学领域#xff0c;字典序#xff08;Lexicographical order#xff09;也称为词典序、字典顺序、字母序#xff0c;是一种对序列元素进行排序的方式#xff0c;它模仿了字典中单词的排序规则。下面从不同的数据类型来详细解释字典序#xff1a; …字典序
在刷题和计算机科学领域字典序Lexicographical order也称为词典序、字典顺序、字母序是一种对序列元素进行排序的方式它模仿了字典中单词的排序规则。下面从不同的数据类型来详细解释字典序
字符串的字典序
在字典中单词是按照字母的先后顺序排列的。对于两个字符串字典序的比较规则如下 比较过程从两个字符串的第一个字符开始逐个比较如果对应位置的字符不同则字符 ASCII 码值小的字符串排在前面如果对应位置字符相同则继续比较下一个位置的字符直到出现不同字符或者其中一个字符串结束。 示例 比较 apple 和 banana因为第一个字符 a 的 ASCII 码值小于 b所以 apple 在字典序中排在 banana 前面。 比较 apple 和 app前三个字符都相同但 app 先结束所以 app 在字典序中排在 apple 前面。
整数序列的字典序
对于整数序列同样可以按照字典序进行比较 比较过程将整数序列看作由数字组成的字符串从序列的第一个元素开始逐个比较元素的大小如果对应位置的元素不同则元素值小的序列排在前面如果对应位置元素相同则继续比较下一个位置的元素直到出现不同元素或者其中一个序列结束。 示例 比较序列 [1, 2, 3] 和 [2, 1, 3]第一个元素 1 小于 2所以 [1, 2, 3] 在字典序中排在 [2, 1, 3] 前面。 比较序列 [1, 2, 3] 和 [1, 2]前两个元素都相同但 [1, 2] 先结束所以 [1, 2] 在字典序中排在 [1, 2, 3] 前面。
在刷题中的应用
在很多算法题中字典序常常作为排序的依据或者要求输出的结果满足字典序的要求例如 全排列问题要求输出给定序列的所有全排列并且按照字典序输出。例如对于序列 [1, 2, 3]其全排列按照字典序输出为 [1, 2, 3]、[1, 3, 2]、[2, 1, 3]、[2, 3, 1]、[3, 1, 2]、[3, 2, 1]。 子集问题可能要求输出所有子集并且按照字典序排列。
代码示例C 实现全排列并按字典序输出
#include iostream
#include vector
#include algorithmint main() {std::vectorint nums {1, 2, 3};do {for (int num : nums) {std::cout num ;}std::cout std::endl;} while (std::next_permutation(nums.begin(), nums.end()));return 0;
}
这些代码示例展示了如何生成全排列并按字典序输出在刷题中可以根据具体需求对代码进行调整。
92.递归实现指数型枚举 #include cstdio#include cstring#include iostream#include algorithmusing namespace std;const int N 16; // 最大数据范围int statu[N]; // 状态数组 0表示未考虑 1表示选 2表示不选int n; // 标准输入void dfs(int u) // d{if(u n) // 考虑到了最后一个位置 -- 递归出口{// 打印所有的数for(int i 0; i n; i){if(statu[i] 1)printf(%d , i);}printf(\n);// 打印换行表示这一次枚举完毕return;// 返回上一层}// 不选的情况statu[u] 2;dfs(u1);statu[u] 0;// 恢复现场// 选的情况statu[u] 1;dfs(u1);statu[u] 0; }int main(){cin n;dfs(1); //对第1个数进行考虑return 0;} 94.递归实现排列型枚举 #include iostream
#include cstdio
#include cstring
#include algorithmusing namespace std;// 数组定义成全局变量初始值一定是0如果定义成局部变量初始值随机
const int N 10;
int status[N]; // 0表示未填入 1—n表示填入的数
bool used[N];// 标记这个数有没有被用过 true用过 false没有用过
int n;void dfs(int u)
{// 递归出口if(u n){for(int i 1; i n; i) printf(%d , status[i]);puts();return;}// 依此枚举每个分支即当前位置可以填哪些数for(int i 1; i n; i){if(!used[i]) // 当前的数没有用{status[u] i; // 填入这个数used[i] true; // 标记已使用dfs(u 1);// 恢复现场used[i] false;status[u] 0;}}}int main()
{scanf(%d, n);dfs(1);return 0;
} 93.递归实现组合型枚举 #include iostream
#include cstdio
#include cstring
#include algorithmusing namespace std;
int n, m;
const int N 30;
int status[N];void dfs(int u, int start)
{// u-1 n - start 1 mif(u n - start m) return; // 剪枝 -- start后面的数加起来都不够凑m个数// 递归出口if(u m){for(int i 1; i m; i) printf(%d , status[i]);puts();return;}for(int i start; i n; i){status[u] i;dfs(u1, i1);// 恢复现场status[u] 0;}
}int main()
{scanf(%d %d, n, m);dfs(1, 1);return 0;
} 1209.带分数 #include iostream
#include cstdio
#include cstring
#include algorithmusing namespace std;
const int N 10;
int ans 0;int n;
bool status[N]; // 判重数组
bool backup[N];bool check(int a, int c)
{long long b n * (long long)c - a * c;// a b c 不能为0if(!a || !b || !c) return false;memcpy(backup, status, sizeof(status));while(b){int x b % 10;b b / 10;// x在ac中不能出现, x不能为0if(!x || backup[x]) return false;backup[x] true; }// 看看每个数字是否出现过 -- 必须全部出现for(int i 1; i 9; i){if(!backup[i]) return false;}return true;
}void dfs_c(int u, int a, int c)
{if(u n) return;if(check(a, c)) ans;for(int i 1; i 9; i){if(!status[i]){status[i] true;dfs_c(u1, a, c * 10 i);status[i] false;}}}void dfs_a(int u, int a)
{if(a n) return; if(a) dfs_c(u, a, 0); // 只要a小于n每种情况下都有dfs_cfor(int i 1; i 9; i){if(!status[i]){status[i] true;dfs_a(u1, a * 10 i);status[i] false; }}
}int main()
{cin n;dfs_a(0, 0); // 当前已经用了多少个数字 最开始a是0 cout ans endl;return 0;
} 717.简单斐波那契 #include iostream
#include cstdio
#include cstring
#include algorithmusing namespace std;int main()
{int n 0;cin n;int F[47];F[0] 0, F[1] 1, F[2] 1;for(int i 3; i n; i){F[i] F[i-1] F[i-2];}for(int i 0; i n; i){cout F[i] ;}return 0;
} 优化
#include iostream
#include cstdio
#include cstring
#include algorithmusing namespace std;int main()
{int n; cin n;int a 0, b 1;for(int i 1; i n; i){cout a ;int fn a b;a b; b fn;}return 0;
}
1208.翻硬币 #include iostream
#include cstring
#include algorithm
#include cstdiousing namespace std;const int N 110;
char start[N], aim[N];void turn(int i)
{if(start[i] *) start[i] o;else start[i] *;
}int main()
{cin start aim;int n strlen(start);// 计算输入长度int ret 0;for(int i 0; i n - 1; i){if(start[i] ! aim[i]){turn(i), turn(i1);ret;}}cout ret endl;return 0;
} 116.飞行员兄弟 #include iostream
#include cstring
#include cstdio
#include algorithm
#include vectorusing namespace std;
const int N 5;
char g[N][N], backup[N][N];
typedef pairint, int PII;// 映射函数
int get(int i, int j)
{return i * 4 j;
}void turn_one(int x, int y)
{if(g[x][y] -) g[x][y] ;else g[x][y] -;
}void turn_all(int x, int y)
{for(int i 0; i 4; i){turn_one(x, i);turn_one(i, y);}turn_one(x, y); // xy在循环中被按了两次现在调回去
}int main()
{vectorPII res;// 输入for(int i 0; i 4; i)for(int j 0; j 4; j)cin g[i][j];// 枚举所有方案for(int op 0; op (1 16); op){vectorPII temp; // 存储方案memcpy(backup, g, sizeof(g)); // 备份方案// 枚举16个位置for(int i 0; i 4; i)for(int j 0; j 4; j){if(op get(i, j) 1) // 判断是不是要按开关{temp.push_back({i, j});turn_all(i, j);}}bool hash_close false;// 判断是否全部灯泡已经亮了for(int i 0; i 4; i)for(int j 0; j 4; j)if(g[i][j] )hash_close true;if(!hash_close){if(res.empty() || res.size() temp.size() ) res temp;}memcpy(g, backup, sizeof(backup)); // 恢复方案}cout res.size() endl;for (auto op : res) cout op.first 1 op.second 1 endl;return 0;
}
