简单斐波那契
以下数列 0 1 1 2 3 5 8 13 21 … 被称为斐波纳契数列。
这个数列从第 3 项开始，每一项都等于前两项之和。
输入一个整数 N，请你输出这个序列的前 N 项。
输入格式
一个整数 N。
输出格式
在一行中输出斐波那契数列的前 N 项，数字之间用空格隔开。
数据范围
0<N<46
输入样例：
5
输出样例：
0 1 1 2 3
提交代码：
import java.util.*; public class Main { static int n; static int [] f = new int [50]; static int fc(int n) { if (f[n] != 0) return f[n]; if (n == 0) f[n] = 0; if (n == 1) f[n] = 1; if (n > 1) f[n] = fc(n - 1) + fc(n - 2); return f[n]; } public static void main(String [] args) { Scanner in = new Scanner (System.in); n = in.nextInt(); int f1 = 0, f2 = 1; fc(n); for (int i = 0; i < n; ++ i) { System.out.print(f[i] + " "); } } }
滑动窗口
给定一个大小为 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(); } }
