排列数字
给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。
输入格式
共一行，包含一个整数 n。
输出格式
按字典序输出所有排列方案，每个方案占一行。
数据范围
1≤n≤7
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
思路讲解：
本题为dfs经典例题，也是算法比赛必出的题目类型，无法理解就背下来，每天看看，多思考几周就会豁然开朗了。
提交代码
C++
#include<iostream> using namespace std; const int N = 10; int n; int path[N]; bool st[N]; // 值为true表示这个数字被用过 void dfs(int u) { if (u == n) { for (int i = 0; i < n; ++i) printf("%d ", path[i]); // 如果 n == u 那么这个path存的就是我们要输出的数字 putchar('\n'); return; // 可写可不写 } for (int i = 1; i <= n; ++i) // 这里是1 ~ n每一位数字的穷举 { if (!st[i]) // 如果这个数字被标记过， 那么这个数字就存入 path { path[u] = i; st[i] = true; // 这个数组是用来标记1 ~ n的每一位数字是否出现 dfs(u + 1); // 举下一种情况 // path[u] = 0; 可写可不写 st[i] = false; // 再把出现过的数字回归初始化 代表没有出现过 } } } /* 这个题的是从第0层的根结点开始的 */ int main() { cin >> n; dfs(0); // 所以这里要是0 return 0; }
Java
import java.util.*; public class Main { static int N = 10; static int n; static boolean [] st = new boolean [N]; // 标记数字是否被使用过 static int []a = new int [N]; static Scanner in = new Scanner (System.in); static void dfs (int u) { if (u == n) // 可以输出的条件 { // 输出这组满足条件的结果 for (int i = 0; i < n; ++ i) System.out.print(a[i] + " "); System.out.println(); return; } // 遍历1到n之间的数字 for (int i = 1; i <= n; ++ i) { if (!st[i]) // 当数字i没有被使用过的时候 { a[u] = i; // 把第u个数字设置成i st[i] = true; // 然后标记第i个数字被使用过了 dfs (u + 1); // 进入下一层 st[i] = false; // 回溯，恢复现场 } } } public static void main(String[] args) { n = in.nextInt(); // 从第0层开始 dfs (0); } }
排列数字
给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。
输入格式
共一行，包含一个整数 n。
输出格式
按字典序输出所有排列方案，每个方案占一行。
数据范围
1≤n≤7
输入样例：
3
输出样例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
思路讲解：
本题为dfs经典例题，也是算法比赛必出的题目类型，无法理解就背下来，每天看看，多思考几周就会豁然开朗了。
提交代码
C++
#include<iostream> using namespace std; const int N = 10; int n; int path[N]; bool st[N]; // 值为true表示这个数字被用过 void dfs(int u) { if (u == n) { for (int i = 0; i < n; ++i) printf("%d ", path[i]); // 如果 n == u 那么这个path存的就是我们要输出的数字 putchar('\n'); return; // 可写可不写 } for (int i = 1; i <= n; ++i) // 这里是1 ~ n每一位数字的穷举 { if (!st[i]) // 如果这个数字被标记过， 那么这个数字就存入 path { path[u] = i; st[i] = true; // 这个数组是用来标记1 ~ n的每一位数字是否出现 dfs(u + 1); // 举下一种情况 // path[u] = 0; 可写可不写 st[i] = false; // 再把出现过的数字回归初始化 代表没有出现过 } } } /* 这个题的是从第0层的根结点开始的 */ int main() { cin >> n; dfs(0); // 所以这里要是0 return 0; }
Java
import java.util.*; public class Main { static int N = 10; static int n; static boolean [] st = new boolean [N]; // 标记数字是否被使用过 static int []a = new int [N]; static Scanner in = new Scanner (System.in); static void dfs (int u) { if (u == n) // 可以输出的条件 { // 输出这组满足条件的结果 for (int i = 0; i < n; ++ i) System.out.print(a[i] + " "); System.out.println(); return; } // 遍历1到n之间的数字 for (int i = 1; i <= n; ++ i) { if (!st[i]) // 当数字i没有被使用过的时候 { a[u] = i; // 把第u个数字设置成i st[i] = true; // 然后标记第i个数字被使用过了 dfs (u + 1); // 进入下一层 st[i] = false; // 回溯，恢复现场 } } } public static void main(String[] args) { n = in.nextInt(); // 从第0层开始 dfs (0); } }
滑动窗口
给定一个大小为 n≤106 的数组。
有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 k 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。
窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。
第二行有 n 个整数，代表数组的具体数值。
同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。
输入样例：
8 3
1 3 -1 -3 5 3 6 7
输出样例：
-1 -3 -3 -3 3 3
3 3 5 5 6 7
提交代码
C++
#include<iostream> using namespace std; const int N = 1000010; int a[N], q[N], hh, tt = -1; int main() { int n, k; cin >> n >> k; for (int i = 0; i < n; ++ i) // 这个题要注意的是 q队列里面存放的是位置 { scanf ("%d", &a[i]); // 先求的是最小值 if (i - k + 1 > q[hh]) ++hh; // 如果最小值的位置已经滑出窗口了 然后就 // ++ hh代表这个数已经没了 while (hh <= tt && a[i] <= a[q[tt]]) -- tt; // 先确保队列里面有数字 // 然后如果新来的数字要小于 队列里面的最小值 // 那么--tt 就代表当前队列的最小值去掉 q[++ tt] = i; // 把新来的数字放到队列中 if (i + 1 >= k) printf ("%d ", a[q[hh]]); // 当前队列的长度已经满足k了 // 就可以把对首的元素输出出来 } puts(""); int hh = 0, tt = -1; for (int i = 0; i < n; ++ i) { if (i - k + 1 > q[hh]) ++ hh; while (hh <= tt && a[i] >= a[q[tt]]) -- tt; q[++ tt] = i; if (i + 1 >= k) printf("%d ", a[q[hh]]); } return 0; }
Java
import java.io.*; public class Main { final static int N = 1000010; static int [] a = new int [N]; static int [] q = new int [N]; static int hh = 0, tt = -1; public static void main(String[] args) throws IOException { int n, k; BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); String [] str = reader.readLine().split(" "); n = Integer.parseInt(str[0]); k = Integer.parseInt(str[1]); str = reader.readLine().split(" "); for (int i = 0; i < n; ++ i) a[i] = Integer.parseInt(str[i]); // for (int i = 0; i < n; ++ i) // { // if (hh <= tt && i - k + 1 > q[hh]) ++ hh; // while (hh <= tt && a[i] <= a[q[hh]]) -- tt; // q[++ tt] = i; // if (i + 1 >= k) out.write(a[q[hh]]+" "); // } for(int i = 0; i < n; i ++) { if(hh <= tt && i - q[hh] + 1 > k) hh++;//判断队头是否已经滑出窗口 while(hh <= tt && a[q[tt]] >= a[i]) tt--;//出队 q[++tt] = i;//入队 if(i >= k - 1) out.write(a[q[hh]]+" "); } out.write("\n"); hh = 0; tt = -1; // for (int i = 0; i < n; ++ i) // { // if (hh <= tt && i - k + 1 > q[hh]) ++ hh; // while (hh <= tt && a[i] >= a[q[hh]]) -- tt; // q[++ tt] = i; // if (i + 1 >= k) out.write(a[q[hh]]+" "); // } for(int i = 0; i < n; i ++) { if(hh <= tt && i - q[hh] + 1 > k) hh++;//判断队头是否已经滑出窗口 while(hh <= tt && a[q[tt]] <= a[i]) tt--;//出队 q[++tt] = i;//入队 if(i >= k - 1) out.write(a[q[hh]]+" "); } out.flush(); out.close(); } }
