前言

题目难度比较低，模拟题也很简单，dp也是很常见的类型，所以这种难度就要争取全A了。

第一题

假设有一种可以在人与人之间进行快速传播的新型病毒 (记为V)，如果有人(记为A)感染了这种病毒，并在某个时刻t和另一个人 B 接触，那么B 也会立刻感染病毒 V.

现有如下条件:

1、给定一个正整数n，代表n 个人，这些人的编号从0到n-1;

2、给定一个下标从0开始的二维数组 meetings，其中 meetings[i]=[xi,yi,ti] 表示人员xi和yi在时刻ti 有过接触;在 meetings 代表的所有接触发生期间，感染者会一直处于感染状态;

3、同一个人A可以在某一时刻同时和多个人接触，且如果A感染了病毒V，那么和A接触的所有人都会立刻感染该病毒;即:假设人员xi和yi在时刻ti有过接触，如果 xi 感染了病毒 V，那么yi 也会感染该病毒，反之亦然;

4、病毒V的感染是瞬间发生的，也就是说，如果人员A在时刻t 感染了病毒，那么A马上就可以把病毒V 传染给接触到的其他人;

5、给定一个整数 firstPerson，代表某个人，且 0 < firstPerson< n;

6、人员 0 感染了病毒V，并在时刻 0与 firstPerson 有过接触。

在meetings代表的所有接触都发生之后，请返回感染病毒V的所有感染者的编号列表，并按照从小到大的顺序记录人员编号。

示例1

输入

6,[[1 2,5][2 3 8],[1 5 101],1

输出

[0,1,2,3,5]

说明

时刻0，人员0与人员1接触，人员1 感染病毒
时刻5，人员1与人员2 接触，人员2 感染病毒
时刻8，人员2与人员3 接触，人员3 感染病毒,
时刻 10，人员1与人员 5接触，人员5感染病毒。
因此，在所有接触发生后，人员0、1、2、3、5都是感染者。

思路和代码

将二维数组转为list，根据时间进行排序，判断是否和病源接触过，注意结果先放在set中进行去重再转为list

import java.util.*;
    
public ArrayList<Integer> findAllPerson(int n, int[][] meetings, int firstPerson) {
        List<Spread> list = new ArrayList<>();
        Set<Integer> set = new HashSet<>(); //进行去重
        int len = meetings.length; //有几条Spread
        for (int i = 0; i < len; i++) {
            Spread spread = new Spread(meetings[i][0], meetings[i][1], meetings[i][2]);
            list.add(spread);
        }
        //第0号人进行传播给firstPerson
        set.add(0);
        set.add(firstPerson);
        //按照时间进行排序
        Collections.sort(list, new Comparator<Spread>() {
            @Override
            public int compare(Spread o1, Spread o2) {
                return o1.time - o2.time;
            }
        });
        //判断传播途径
        for (Spread spread : list) {
            if (set.contains(spread.p1) || set.contains(spread.p2)) {
                //都被感染
                set.add(spread.p1);
                set.add(spread.p2);
            }
        }
        //转为list
        ArrayList<Integer> ans = new ArrayList<>();
        for (int person : set) {
            ans.add(person);
        }
        //排序
        Collections.sort(ans);
        return ans;
    }
}
class Spread{
    int p1;
    int p2;
    int time;
    public Spread(int p1,int p2,int time){
        this.p1 = p1;
        this.p2 = p2;
        this.time = time;
    }
}

第二题

一个长方形的棋盘一个棋子要从棋盘的左下角行走到棋盘的右上角棋子落点为两条线相交处.

现在规定棋子一次只能走一步方向只能向右或者向上走；

现将棋盘的起点做为平面直角坐标系的(0,0)终点为(m,n)

请用动态规划思想计算棋子从起点到终点一共有多少种走法

输入描述

int m,int n,表示棋盘的总格数为m*n

输出描述

输出值为int型表示棋子从棋盘的左下角(0,0)行走到棋盘的右上角(m,n)的总路线数.

示例1

输入

1 1

输出

2

说明

对于一个1*1的棋盘，从左下角走到右上角有两种走法
1. 右->上
2. 上->右

思路和代码

常规动态规划，初始化第一行第一列为1

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt()+1;
        int n = sc.nextInt()+1;

        int[][] dp = new int[m][n];
        //初始化
        for(int i=0;i<m;i++){
            dp[i][0] = 1;
        }
        for(int j=0;j<n;j++){
            dp[0][j] = 1;
        }
        //动态规划
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(j-1>=0 && i-1>=0)
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        System.out.println(dp[m-1][n-1]);
    }
}

第三题

给定两个长度都是 n(n>0)的整数数组 nums1和nums2，在给定一个整数k。

你可以对数组 nums2 进行以下操作：

选择两个下标和i和j，满足：0<=i< n

nums2[i] = nums2[i] + k,目 nums2[j]= nums2[j]-k;

如果对于所有整数i(0<=1<n)，都有num1[i]==nums2[i]，那人称nums1 等于nums2。

计算使 nums1 等于nums2 所需的 最少操作数量。如果没办法让它们相等，直接返回-1。

示例1

输入

[1,3,7,1],[4,3,1,4,],3

输出

2

说明

可以通过2个操作将nums2变成nums1:
第1个操作: i=2，j=0;操作后得到nums2 =[1,3,4,4]
第2个操作:i=2，j=3;操作后得到 nums2 =[1,3,7,1]
无法用更少操作使两个数组相等。

思路和代码

遍历nums2的每个元素，与对应的nums1 比较，差值能否整除，不能整除返回-1

public long minOperations(int[] nums1,int[] nums2, int k){
            int zs = 0;
            int fs =0;
            for(int i=0;i< nums1.length;i++){
                int diff = nums2[i] - nums1[i];
                if(diff%k !=0){
                    System.out.println(-1);
                    break;
                }else{
                    if(diff>0){
                        zs += diff/k;
                    }else if(diff<0){
                        fs += -diff/k;
                    }
                }
            }
            if(zs == fs){
                System.out.println(zs);
            }
            else {
                System.out.println(-1);
            }
        }