校招编程真题总结
输入模板
比Scanner快不少，具体原理需要看一下。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
//注意
public static void main (String[] args) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bf.readLine());
}
}动态规划-01背包问题
每个货物都可以无限使用，但是要求背包必须装满，而且要求背包中的物品数目最少。
由于货物是无限的，那么假设dp[n]表示背包容量为n的能够装满的最少货物个数。
如果选择3, 5, 7任意的一种货物重量，那么dp[n-3]、dp[n-5]、dp[n-7]就会是背包容量为n的一种选择，
所以问题就转化为了求dp[n-x]，dp[i] = min(min(dp[i-3],dp[i-5]),dp[i-7])+1。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main (String[] args) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(bf.readLine());
if (n < 8) {
if (n == 3 || n == 5 || n == 7)
System.out.println(1);
else if (n ==6)
System.out.println(2);
else
System.out.println(-1);
} else {
int[] dp = new int[n+1];
dp[1] = Integer.MAX_VALUE; dp[2] = Integer.MAX_VALUE; dp[4] = Integer.MAX_VALUE;
dp[3] = 1; dp[5] = 1; dp[7] = 1;
dp[6] = 2;
for (int i = 8; i <= n; i++) {
int temp = Math.min(dp[i-3], Math.min(dp[i-5], dp[i-7]));
if (temp == Integer.MAX_VALUE)
dp[i] = Integer.MAX_VALUE;
else
dp[i] = temp + 1;
}
if (dp[n] == Integer.MAX_VALUE)
System.out.println(-1);
else
System.out.println(dp[n]);
}
}
}动态规划-回文字符串
想到回文字符串立马要想到最常用的解题思路：
- 中心扩散法
- 动态规划
- 马拉车算法（？不会）
回文子串
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main (String[] args) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String str = bf.readLine();
int n = str.length();
int count = n;
int[][] dp = new int[n][n];
dp[0][0] = 1;
for (int i = 1; i < n; i++) {
dp[i][i] = 1;
for (int j = i-1; j >= 0; j--) {
if (str.charAt(i) == str.charAt(j) && (j+1 > i-1 || dp[j+1][i-1] == 1)) {
dp[j][i] = 1;
count++;
}
}
}
System.out.println(count);
}
}动态规划-机器人问题变种
拜访 -美团2016年面试题
(x1,y1),(x2,y2)两点任意指定，需要先进行交换，令x1是左面的点，令x2是右面的点。
int x1 = 0; int y1 = 0;
int x2 = 0; int y2 = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] == 1) {
x1 = i;
y1 = j;
} else if (map[i][j] == 2) {
x2 = i;
y2 = j;
}
}
}
if (x1 == x2 && y1 == y2) {
return 1;
}
if (x1 > x2) {
int temp = x1; x1 = x2; x2 = temp;
temp = y1; y1 = y2; y2 = temp;
}然后在进行按照机器人路径那么写就可以了。
网格走法数目
注意走的是格点不是格子就能做对了。
import java.util.*;
import java.math.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main (String[] args) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String[] s = bf.readLine().split(" ");
int x = Integer.parseInt(s[0]);
int y = Integer.parseInt(s[1]);
int[][] dp = new int[x+1][y+1];
dp[0][0] = 1;
for (int i = 1; i <= x; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= y; i++) {
dp[0][i] = 1;
}
for (int i = 1; i <= x; i++) {
for (int j = 1; j <= y; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
System.out.println(dp[x][y]);
}
}图
创建图
static ArrayList<Integer>[] graph;
graph = new ArrayList[n+1];
graph = new ArrayList[n+1];
for (int i = 0; i <= n; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
s = bf.readLine().split(" ");
int u = Integer.parseInt(s[0]);
int v = Integer.parseInt(s[1]);
graph[u].add(v);
graph[v].add(u);
}bfs
private static int bfs(int x, int n, int m) {
int[] dist = new int[n + m + 1];
LinkedList<Integer> queue = new LinkedList<>();
dist[x] = 1;
queue.offer(x);
while (!queue.isEmpty()) {
int cur = queue.poll();
for (Integer e : graph[cur]) {
if (dist[e] == 0) {
dist[e] = dist[cur] + 1;
queue.offer(e);
}
}
}
return dist[n];
} 
