A. 来自瑞思拜龙的善意 (参照”工具人”的解答)

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int i = sc.nextInt();
        int[] arr=new int[i];
        int[] ret=new int[i];
        int idx=0;
        while(i>0){
            int i1 = sc.nextInt();
            arr[idx]=i1;
            idx++;
            i--;
        }
        idx=0;
        for (int i1 : arr) {
            if(isPrime(i1+1)){
                ret[idx]=i1+1;
            }else ret[idx]=-1;
            idx++;
        }
        for (int i1 : ret) {
            System.out.println(i1);
        }
    }
    public static boolean isPrime(int x){
        if(x==2) return true;
        if(x==1) return false;
        for(int i=2;i<=Math.sqrt(x);i++){
            if(x%i==0) return false;
        }
        return true;
    }
}

C. CUIT_WIFI咋又断啦！！！

二分+双指针

思路：为什么可以二分？
首先，一定存在一个x，使得如果路由器的覆盖范围小于x，那么就不能够覆盖所有机房，
如果大于x，能够覆盖所有的机房
综上，具有二段性，所以可以二分。
check()函数：双指针，路由器能够覆盖一个机房的条件为:

该路由器的位置+x>=机房的位置
该路由器的位置-x<=机房的位置

有了这两个条件值后，接下来

先遍历机房，如果当前路由器能覆盖该机房，遍历下一个机房
如果当前的路由器不能覆盖该机房，遍历下一个路由器

如果所有的路由器遍历完之后，但凡有一个机房都不能被覆盖，说明该距离x不成立。重新改变二分的区间。

import java.util.Arrays;
import java.util.Scanner;
public class questionC {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 机房的数量
        int n = sc.nextInt();
        // 路由器的数量
        int m = sc.nextInt();
        int[] houses=new int[n];
        int[] routers=new int[n];
        int idx=0;
        while(n>0){
            houses[idx]=sc.nextInt();
            n--;
            idx++;
        }
        idx=0;
        while(m>0){
            routers[idx]=sc.nextInt();
            m--;
            idx++;
        }
        Arrays.sort(routers);
        Arrays.sort(houses);
        // 1. 划分二分区间
        int l = 0, r = (int) 1e9;
        
        while(l<r){
            int mid=(l+r)/2;
            if(check(houses,routers,mid)) r=mid;
            else l=mid+1;
        }
        System.out.println(l);
    }
    // 查看当前的距离x能否满足要求
    public static boolean check(int[] houses,int[] routers,int x){
        int n = houses.length;
        int m = routers.length;
        for(int i=0,j=0;i<n && j<m;i++){
            while(j<m&&routers[j]+x<houses[i]) j++;
            if(j<m&&routers[j]+x>=houses[i] &&routers[j]-x<=houses[i]) continue;
            return false;
        }
        return true;
    }
}

捎上二分查找的板子

public class binarySearch {
    // 查找第一个大于等于元素的下标
    public void bsForFirstGT(int[] arr,int find){
        int l=0,r=arr.length-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(l==r) break;
            else if(arr[mid]<find) l=mid+1;
            else if(arr[mid]>=find) r=mid;
        }
        if(arr[l]>find) System.out.println("找不到该元素,但是第一个大于等于该元素的下表为 "+l);
        else if(arr[l]==find) System.out.println("该元素的下标"+l);
        else System.out.println("数组中的所有元素全部小于find");
    }

    // 找第一个大于元素的下标
    public void bsForFirstG(int[] arr,int find){
        int l=0,r=arr.length-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(l==r) break;
            else if(arr[mid]<=find) l=mid+1;
            else if(arr[mid]>find) r=mid;
        }
        if(arr[l]<=find) System.out.println("找不到第一个大于该元素的值");
        else System.out.println(l);
    }
    // 查找第一个小于等于元素的下标
    public void bsForLast(int[] arr,int find){
        int l=0,r=arr.length-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(l==r || l==r-1) break;
            else if(arr[mid]<=find) l=mid;
            else if(arr[mid]>find) r=mid-1;
        }
        if(arr[r]<=find) System.out.println(r);
        else System.out.println(l);
    }
}

G. 忙碌的大学生活

这里提供三种解法
1.哈希表+记忆化递归

如果使用暴力递归会超时
这里的话，我是用哈希表HashMap<Integer,Integer>存每个节点的最短路径，防止节点重复访问。其次，还要建立一个逆向的邻接表,例如，题干给的是从2到5的捷径，如果直接利用题干给的数组去构建邻接表，求出来的就是每个节点到最后一个节点的最短路径，但是此题求的是从起始节点0到其余各点的最短路径，所以要建立一个逆向邻接表,这里我采用ArrayList<Integer>[]进行存储.
如图，假如捷径为0到2，2到4。根据学过的，递归其实是从栈顶往栈底走，走到4，然后返回。

这里举个例子。如图,假如从0开始递归，先递归这样一条路径，0->2->4.当从栈顶4开始返回时，返回到2，因为2还有另外一条路径,也就是2->3->4,所以此时的思路也就是dfs这个函数里面的for循环，step=Math.min(dfs()).这个意思就是说会得到两条路径中的最小值，也就是比较2->3->4和2->4这两条路的最小值。毫无疑问，肯定是1.所以一旦遍历完了两条路径，就将2这个节点和它对应的路径放入哈希表，之后再访问到2时，就不用再去走这两条老路了.比如之后还有一条路径是0->1->2.当这条路径走到2时，直接返回1. 对应于代码中的 if(map.contains()) return;
参考图

import java.util.*;
public class Main {
public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int n = sc.nextInt();
    int idx=0;
    int[] arr=new int[n];
    // 初始化
    while(n>0){
        arr[idx]=sc.nextInt();
        idx++;
        n--;
    }
    n=arr.length;
    ArrayList<Integer>[] lists=new ArrayList[n+1];
    for(int i=0;i<=n;i++){
        lists[i]=new ArrayList<>();
    }
    // i+1代表当前节点
    for(int i=n-1;i>=0;i--){
        if(i+1==arr[i]||arr[i]==i+2){
            lists[i+1].add(i);
            continue;
        }
        lists[i+1].add(i);
        lists[arr[i]].add(i+1);
    }
    int[] dp=new int[n+1];
    // 递归
    dfs(n, lists);
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        Integer node = entry.getKey();
        Integer dist = entry.getValue();
        dp[node]=dist;
    }
    for(int i=1;i<n;i++){
        System.out.print(dp[i]+" ");
    }
    System.out.print(dp[n]);
}
public static int dfs(int curNode, ArrayList<Integer>[] lists) {
    // 遍历到最后一个节点
    if (curNode == 0){
        return 0;
    }
    // 如果之前的哈希表已经
    if(map.containsKey(curNode)) return map.get(curNode);
    int step=lists.length+1;
    for (Integer neigh : lists[curNode]) {
        step = Math.min(step, dfs(neigh, lists) + 1);
    }
    map.put(curNode,step);
    return step;
}
}

2. 区间dp

dp[i][j]的定义:从i到j的最短距离
思路:仿照Dijtsra算法(这里感谢”工具人”给我提供的帮助),外层len从2到n，len的意思如下,当len=2,求dp[0][2],dp[1][3]，当len=3,求dp[0][3],dp[1][4]以此类推。

状态转移方程，这里先附上我之前写错的转移方程dp[i][j]=Math.min(Math.min(dp[i+1][j]+1,dp[i][j-1]+1),dp[i][j]),这里其实还少了一层for循环，因为dp[i][j]不单单只能由dp[i+1][j],dp[i][j-1]转移得来.还可能由dp[i][k]+dp[k][j]以及dp[i][m]+dp[m][j]等等转移得来，所以还需要加一层for循环.

import java.util.*;
public class Main {
    static HashMap<Integer, Integer> map = new HashMap<>();   // k:节点 v:到达n的最短步数
    static HashMap<Integer, List<Integer>> distan = new HashMap<>();
    // 区间dp
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int idx = 1;
        int[] arr = new int[n + 1];
        while (n > 0) {
            arr[idx] = sc.nextInt();
            idx++;
            n--;
        }
        n = arr.length;
        int[][] dp = new int[n][n];
        for (int i = 1; i < n; i++) {
            int dest = arr[i];
            dp[i][dest] = 1;
        }
        for (int i = 0; i < n - 1; i++) {
            dp[i][i + 1] = 1;
        }
        for (int len = 2; len < n; len++) {
            for (int l = 0; l + len < n; l++) {
                int r = l + len;
                if (dp[l][r] == 1) continue;
                dp[l][r] = n + 1;
                for (int x = l + 1; x < r; x++) {
                    dp[l][r] = Math.min(dp[l][x] + dp[x][r], dp[l][r]);
                }
            }
        }
        for(int i=1;i<n-1;i++){
            System.out.print(dp[0][i] + " ");
        }
        System.out.print(dp[0][n-1]);
    }
}

3. 一维dp (参照”工具人”的解答)

import java.util.*;
public class Main {
     //dp
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        int idx=1;
        int[] arr = new int[n+1];
        while(n>0){
            arr[idx]=sc.nextInt();
            idx++;
            n--;
        }
        n = arr.length;
        int[] dp=new int[n];
        Arrays.fill(dp,n+1);
        dp[0]=0;
        for(int i=1;i<n;i++){
            dp[i] = Math.min(dp[i - 1] + 1, dp[i]);
            dp[arr[i]]=Math.min(dp[i]+1,dp[arr[i]]);
        }
        for(int i=1;i<n;i++){
            System.out.println(dp[i]);
        }
    }
}
}

leetcode上与G题相似的题目

375题猜数字大小
526题优美的排列
494题目标和