一、递归与递推
递归实现指数型枚举
import java.util.*;
public class Main {
static int n;
static LinkedList<Integer> tmp = new LinkedList<>();
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
dfs(1);
}
static void dfs(int start) {
if (tmp.size() == 0) {
System.out.println();
}
if (tmp.size() >= 1) {
for (int i = 0; i < tmp.size(); i++) {
System.out.printf("%d ", tmp.get(i));
}
System.out.println();
}
if (tmp.size() > n) {
return;
}
for (int i = start; i <= n; i++) {
tmp.add(i);
dfs(i + 1);
tmp.removeLast();
}
}
}
递归实现排列型枚举
import java.util.*;
public class Main {
static int n;
static int[] vis = new int[10];
static LinkedList<Integer> tmp = new LinkedList<>();
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
dfs();
}
static void dfs() {
if (tmp.size() == n) {
for (int i = 0; i < tmp.size(); i++) {
System.out.printf("%d ", tmp.get(i));
}
System.out.println();
}
if (tmp.size() > n) {
return;
}
for (int i = 1; i <= n; i++) {
if (vis[i] == 1) {
continue;
}
vis[i] = 1;
tmp.add(i);
dfs();
vis[i] = 0;
tmp.removeLast();
}
}
}
用System.out.println会超时，改用BufferedWriter，比System.out.println快20倍。
package Chapter_5;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.*;
public class Main {
static int n;
static int[] vis = new int[10];
static LinkedList<Integer> tmp = new LinkedList<>();
// 加快打印速度
static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
dfs();
log.flush();
}
static void dfs() throws IOException {
if (tmp.size() == n) {
for (int i = 0; i < tmp.size(); i++) {
log.write(tmp.get(i) + " ");
}
log.write("\n");
}
if (tmp.size() > n) {
return;
}
for (int i = 1; i <= n; i++) {
if (vis[i] == 1) {
continue;
}
vis[i] = 1;
tmp.add(i);
dfs();
vis[i] = 0;
tmp.removeLast();
}
}
}
递归实现组合型枚举
import java.io.*;
import java.util.*;
public class Main {
static int n;
static int m;
static LinkedList<Integer> tmp = new LinkedList<>();
// 加快打印速度
static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
dfs(1);
log.flush();
}
static void dfs(int start) throws IOException {
if (tmp.size() == m) {
for (int i = 0; i < tmp.size(); i++) {
log.write(tmp.get(i) + " ");
}
log.write("\n");
}
if (tmp.size() > m) {
return;
}
for (int i = start; i <= n; i++) {
tmp.add(i);
dfs(i + 1);
tmp.removeLast();
}
}
}
飞行员兄弟
从左到右，从上往下，依次遍历每个开关，对某个开关有两种状态，可以change，也可以不change，所以就需要回溯。
import java.io.*;
import java.util.*;
class node {
int x, y;
node() {};
node(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static char[][] map = new char[4][4];
static LinkedList<node> nodes = new LinkedList<>();
static LinkedList<node> ans = new LinkedList<>();
// 加快打印速度
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
for (int i = 0; i < 4; i++) {
map[i] = scan.next().toCharArray();
}
// 从左到右、从上到下遍历每个开关，直到遍历完，整个过程中查看是否成功
dfs(0, 0);
System.out.println(ans.size());
for (int i = 0; i < ans.size(); i++) {
System.out.printf("%d %d\n", ans.get(i).x + 1, ans.get(i).y + 1);
}
}
static void openOneUp(int x, int y) {
if (map[x][y] == '+') map[x][y] = '-';
else map[x][y] = '+';
}
static void openAllUp(int x, int y) {
for (int i = 0; i < 4; i++) {
openOneUp(x, i);
openOneUp(i, y);
}
// 注意上面会把x,y重置（两次change = 不change）
// 还需要单独open(x,y)
openOneUp(x, y);
}
static void dfs(int x, int y) {
if (x == 3 && y == 4) {
// 所有开关都遍历完了，看当前冰箱能否打开
boolean flag = true;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (map[i][j] == '+') {
flag = false;
break;
}
}
if (flag == false) {
break;
}
}
if (flag) {
// 所需的最小切换把手次数
if (ans.isEmpty() || ans.size() > nodes.size()) {
// 必须要用clone，否则nodes的变化会导致ans的变化
ans = (LinkedList<node>) nodes.clone();
}
}
return;
}
// 当前行遍历完了，遍历下一行
if (y == 4) {
x++;
y = 0;
}
openAllUp(x, y);
node tmp = new node(x, y);
nodes.add(tmp);
// 遍历右边一个
dfs(x, y + 1);
// 回溯
nodes.removeLast();
// 回溯，之前的状态也要全部回溯
openAllUp(x, y);
dfs(x, y + 1);
}
}
二、二分
数的范围
一次二分找最开始位置，一次二分找第一个大于它的位置即可。
import java.io.*;
import java.util.*;
public class Main {
static int[] nums;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int q = scan.nextInt();
nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = scan.nextInt();
}
for (int i = 0; i < q; i++) {
int key = scan.nextInt();
int res = binarySearch(key);
if (res == -1) {
System.out.printf("-1 -1\n");
} else {
int res1 = binarySearch1(key);
System.out.printf("%d %d\n", res, res1 - 1);
}
}
}
static int binarySearch(int key) {
int res = -1;
int left = 0;
int right = nums.length - 1;
int mid;
while (left <= right) {
mid = left + (right - left) / 2;
if (nums[mid] == key) {
res = mid;
// 要找第一次出现的位置
right = mid - 1;
} else if (nums[mid] > key) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return res;
}
// 找第一个大于key的下标
static int binarySearch1(int key) {
int left = 0;
int right = nums.length;
int mid;
while (left < right) {
mid = left + (right - left) / 2;
if (nums[mid] > key) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
数的三次方根
从n的左右边界开始遍历
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
double key = scan.nextDouble();
// 注意x的范围可正可夫，所以左右边界要为边界
double left = -10000;
double right = 10000;
double eps = 0.00000001;
double mid;
while (right - left >= eps) {
mid = left + (right - left) / 2;
if (mid * mid * mid <= key) {
left = mid;
} else {
right = mid;
}
}
System.out.printf("%.6f", left);
}
}
能用二分的地方，都是存在单调性的地方！
三、模拟
注意不能斜向走，找到两个坐标，然后求曼哈顿距离。
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int w = scan.nextInt();
int m = scan.nextInt();
int n = scan.nextInt();
m--;n--;
int x1 = m / w;
int x2 = n / w;
int y1 = m % w;
if (x1 % 2 == 0) {
y1 = w - y1 - 1;
}
int y2 = n % w;
if (x2 % 2 == 0) {
y2 = w - y2 - 1;
}
System.out.println(Math.abs(x1 - x2) + Math.abs(y1 - y2));
}
}
四、搜索
正常的BFS，直接做就行。
import java.util.*;
class node {
int x, y, step;
node() {};
node(int x, int y, int step) {
this.x = x;
this.y = y;
this.step = step;
}
}
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int t = scan.nextInt();
char[][] map;
int[][] vis;
int[] xx = new int[] {-1,1,0,0};
int[] yy = new int[] {0,0,-1,1};
for (int i = 0; i < t; i++) {
int r = scan.nextInt();
int c = scan.nextInt();
vis = new int[201][201];
map = new char[201][201];
node b = new node();
for (int j = 0; j < r; j++) {
map[j] = scan.next().toCharArray();
for (int k = 0; k < c; k++) {
if (map[j][k] == 'S') {
b = new node(j, k, 0);
vis[j][k] = 1;
}
}
}
int ans = Integer.MAX_VALUE;
Queue<node> Q = new LinkedList<>();
Q.offer(b);
while (!Q.isEmpty()) {
node tmp = Q.poll();
if (map[tmp.x][tmp.y] == 'E') {
ans = tmp.step;
break;
}
for (int j = 0; j < 4; j++) {
// 注意这里不要直接temp = tmp!!!
node temp = new node();
temp.x = tmp.x + xx[j];
temp.y = tmp.y + yy[j];
if (temp.x < 0 || temp.y < 0 || temp.x >= r || temp.y >= c || map[temp.x][temp.y] == '#') {
continue;
}
if (vis[temp.x][temp.y] == 1) {
continue;
}
vis[temp.x][temp.y] = 1;
temp.step = tmp.step + 1;
Q.offer(temp);
}
}
if (ans == Integer.MAX_VALUE) {
System.out.println("oop!");
} else {
System.out.println(ans);
}
}
}
}
五、前缀和
普通的前缀和要超时，让女生=-1，男生=1，这样记录前缀和中每个和第一次出现的位置，后面再遇到同样的和时，减去第一次出现的位置即可。需要注意，可能有从头到某个位置只有1个零出现的情况，例如：1 1 -1 -1，前缀和为：1 2 1 0，只有1个0，所以需要在读入数据的时候单独求和判断一下。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
// 计算前缀和，比较当前区间和区间长度是否相等
int[] nums = new int[n];
int sum = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
nums[i] = scan.nextInt();
if (nums[i] == 0) {
nums[i] = -1;
}
sum += nums[i];
if (sum == 0) {
// 如果从头到某个位置的和为0，且只出现1次，要特殊判断一下
ans = i + 1;
}
}
// 计算前缀和
int[] preSum = new int[n + 1];
int[] pos = new int[2 * n + 1];
for (int i = 1; i <= n; i++) {
preSum[i] = preSum[i - 1] + nums[i - 1];
if (pos[preSum[i] + n] != 0) {
ans = Math.max(i - pos[preSum[i] + n], ans);
} else {
pos[preSum[i] + n] = i;
}
}
System.out.println(ans);
}
}
这道题滑动窗口做不了。