【2020】百度校招Java研发工程师笔试卷（第二批）算法题

本文主要是介绍【2020】百度校招Java研发工程师笔试卷（第二批）算法题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

贴一下我去年9月份写的博客

三道编程题，一道数学题，两道图论，哎嘿嘿，我就是不会做，哎嘿嘿，哭了。。。

一.最小值

牛牛给度度熊出了一个数学题，牛牛给定数字n,m,k，希望度度熊能找到一组非负整数a,b满足(n−a)(m−b)≤k且a+b尽量小。

度度熊把这个问题交给了你，希望你能帮他解决。

那么做这种题目，一看就是数学题，当时我直接看了几眼没思路就跳了。没想到是线性规划方程
其实要把这个方程拆开看
k>=(n-a)(m-b)=nm-ma-nb+ab

=m(n-a)+b(a-n)

=m(n-a-b)+b(a-n+m) // 这一步是关键，如果没有想到这一步，那么后面的就更想不到了

=m(n-(a+b)) + b ((m-n) + a)

$>= m (n - (a + b))$
是不是很像初高中做的不等式。。。呵呵呵
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);long n = in.nextLong();long m = in.nextLong();long k = in.nextLong(); /**(n - k / m) >= a+ b,我们要让两数更小那个降低更快,那么其实让n更小，降低得会更快点,这个也是一个关键点*/if(n > m) { long temp       n = m;m = temp;}// 所以经过上面分析，列式子可以得System.out.print(n - k / m);}
}

二.返回公司

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int T = in.nextInt();while(T > 0) {T--;int n =in.nextInt();int m = in.nextInt();ArrayList<Integer>[] graph = new ArrayList[n + 1];for(int i = 1 ;i <= n; i++) {graph[i] = new ArrayList<>();}for(int i = 0; i < m;i ++) {int a = in.nextInt();int b = in.nextInt();graph[a].add(b);graph[b].add(a);}List<Integer> now = graph[1];boolean flag = false;for(int i : now) { List<Integer> next = graph[i];if(next.contains(n) || i == n) {flag = true;break;}}if(flag) { // 这个输出一定要放外面，放里面的话如果第一个不符合就会跳出来，// 就检测不到后面的了，相当于每次都检测第一个System.out.println("POSSIBLE");} else {System.out.println("IMPOSSIBLE");}}}
}