校招编程真题总结

输入模板

比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]);
        }
    }
}

动态规划-回文字符串

想到回文字符串立马要想到最常用的解题思路：

1. 中心扩散法
2. 动态规划
3. 马拉车算法（？不会）
   回文子串

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];
    }

病毒传播