美团 笔试 9.10 除了第四题的答案
题目链接：https://www.nowcoder.com/discuss/1047568
1、简单的比大小。
选择1：规规矩矩的除，然后根据差值小于一个很小的数认为相等，可以过，或者把除法换成乘法
package mt.笔试;
import java.math.BigInteger;
import java.util.Scanner;
/*
*/
public class t1 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
for(int i = 0; i < T; i++){
int n = in.nextInt(), x = in.nextInt(), y = in.nextInt(), k = in.nextInt();
BigInteger p1 = BigInteger.valueOf(k).multiply( BigInteger.valueOf( y));
BigInteger p2 = BigInteger.valueOf((n-k+1)).multiply(BigInteger.valueOf(x));
if(p1.equals(p2)){
System.out.println("Tie");
}else if(p1.compareTo(p2) > 0){
System.out.println("Lose");
}else{
System.out.println("Win");
}
}
}
}
2、神经网络
乘积不等于0，贪心，把所有为0的 一律加个1
只需要满足 和不等于0的条件就可以了。 相当于你只需要在一个位置变化就可以，尝试每一个位置
package mt.笔试;
import java.util.Scanner;
/*
神经网络
时间限制： 3000MS
内存限制： 589824KB
题目描述：
某天，小美在调试她的神经网络模型，这个模型共有n个参数，目前这些参数分别为a1、a2、…、an，
为了让参数看起来更加随机而且增加训练效果，她需要调节参数使所有参数满足a1+a2+…+an≠0且a1*a2*…*an≠0，她每次可以选择一个参数ai并将其变为ai+1，小美请你帮她计算一下，最少需要几次操作才能使参数达到她的要求。
输入描述
第一行一个正整数n，表示参数个数。
第二行为n个正整数a1, a2,...... an，其中ai表示第i个参数初始值。
1 ≤ n ≤ 30000，-1000 ≤ ai ≤ 1000。
输出描述
输出一个正整数，表示最少需要的操作次数。
*/
public class t2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
//1] 所有为0 的必须处理
//2 不是0的 枚举每一个位置 最少变化多少？
int n = in.nextInt();
int count = 0;
int[] arr = new int[n];
int sum = 0;
for(int i = 0; i < n; i++){
arr[i] = in.nextInt();
if(arr[i] == 0){
count++;
arr[i] += 1;
}
sum += arr[i];
}
if(sum != 0){
System.out.println(count);
return;
}
//sum = 0 改变任何一个都可以
int preCost = Integer.MAX_VALUE;
for(int i = 0; i < n; i++){
int cost = 0;
if(arr[i] < 0){
cost = arr[i] == -1 ? 2 : 1;
}else{
cost = 1;
}
preCost = Math.min(preCost, cost);
}
System.out.println(preCost+count);
}
}
3、迷宫
就是一颗二叉树上的进行
因为求最大价值，我的枚举是，必须获得这个宝藏情况下，得到的最大价值是多少。
注意可能，一个位置多个宝藏
package mt.笔试;
/*
时间限制： 3000MS
内存限制： 589824KB
题目描述：
某天小美进入了一个迷宫探险，根据地图所示，这个迷宫里有无数个房间，序号分别为1、2、3、…、∞，入口房间的序号为1，任意序号为正整数x的房间都与序号2*x和2*x+1的房间之间各有一条路径，但是这些路径是单向的，即只能从序号为x的房间去到序号为2*x或2*x+1的房间，而不能从序号为2*x或2*x+1的房间去到序号为x的房间。在任何时刻小美都可以选择结束探险并离开迷宫，但是离开之后将无法再次进入迷宫。小美还提前了解了迷宫中宝藏的信息，已知宝藏共有n个，其中第 i 个宝藏在序号为pi的房间，价值为wi，且一个房间中可能有多个宝藏。小美为了得到更多的宝藏，需要精心规划路线，她找到你帮忙，想请你帮她计算一下，能获得的宝藏价值和最大值为多少。
输入描述
第一行一个正整数n，表示宝藏数量。
第二行为n个正整数p1, p2,...... pn，其中pi表示第 i 个宝藏在序号为pi的房间。
第三行为n个正整数w1, w2,...... wn，其中wi表示第i个宝藏的价值为wi。
数字间两两有空格隔开
1 ≤ n ≤ 40000, 1 ≤ pi ＜230, 1 ≤ wi ≤ 106。
输出描述
输出一个正整数表示能获得的宝藏价值之和的最大值。
*/
import java.math.BigInteger;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;
public class t3 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
//必须获得宝藏i情况下 最大价值是多少？
int n = in.nextInt();
long[] space = new long[n];
long[] val = new long[n];
for(int i = 0; i < n; i++){
space[i] = in.nextLong();
}
HashMap<Long, Long> map = new HashMap<>();
for(int i = 0; i < n; i++){
val[i] = in.nextInt();
if(map.containsKey(space[i])){
map.put(space[i], map.get(space[i])+val[i]);
}else{
map.put(space[i], val[i]);
}
}
BigInteger[] dp = new BigInteger[n];
BigInteger ans = BigInteger.valueOf(0);
//dp[i] 必须到space[i] 的情况下 收获的价值是多少
for(int i = 0; i < n; i++){
dp[i] = process(space[i], map);
ans = dp[i].compareTo(ans) > 0 ? dp[i] : ans;
}
System.out.println(ans);
}
//从cur位置出发 必须到达aim 物资·信息为map
//最大价值是多少
public static BigInteger process( long aim, HashMap<Long, Long> map){
LinkedList<Long> list = new LinkedList<>();
while(aim != 1){
list.add(aim);
aim = aim / 2;
}
list.add(1L);
BigInteger count = BigInteger.valueOf(0);
for(long i : list){
if(map.containsKey(i)){
count = count.add(BigInteger.valueOf(map.get(i)));
}
}
return count;
}
}
4 没过，bfs总是超时，怎么优化都没好
5、最后一个位置为i的子串，最长长度是多少。动态规划
package mt.笔试;
import java.util.Scanner;
/*
777
时间限制： 3000MS
内存限制： 589824KB
题目描述：
小美有一串项链，项链共由n颗宝石组成，每个宝石上都有一个数字。但是有一天项链不小心被弄断了
，变成了一长串，此时可以看成一个只包含数字的字符串，于是她准备将项链从某些地方切开后再重新分成多段（
每段都是原来字符串的连续子串，且不能再重新组合），
因为小美特别喜欢7这个数字，所以她希望切开后每段的数字和都尽可能被7整除。
例如，假设项链表示为12457，可以切分为124|5|7，第一段和第三段的和能被7整除。她想请你帮她算一算 ，切开后最多能有多少段的数字和能被7整除。
输入描述
一行，一个字符串s，s的每位都是数字。
1 ≤ |s| ≤ 100000，|s| 表示s的长度。
输出描述
输出一个整数，表示切开后最多能有多少段的数字和是7的倍数。
*/
public class t5 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
char[] arr = in.nextLine().toCharArray();
int n = arr.length;
int[] dp = new int[n];
dp[0] = arr[0] == '7' || arr[0] == '0'? 1 : 0;
int preMax = dp[0];
for(int i = 1; i < n; i++){
//i结尾 一定是7的倍数
int p1 = 0;
int sum = arr[i] - '0';
if(sum == 7 || sum == 0){
dp[i] = preMax + 1;
preMax = preMax+1;
continue;
}
boolean has7 = false;
int j = i-1;
for(; j >= 0; j--){
sum += arr[j] - '0';
if(sum % 7 == 0){
has7 = true;
break;
}
}
if(has7){
//j...i 是倍数
if(j == 0){
p1 = 1;
}else{
p1 = dp[j-1] + 1;
}
}
dp[i] = Math.max(p1, preMax);
preMax = Math.max(preMax, dp[i]);
}
System.out.println(dp[n-1]);
}
}
#美团笔试##美团##23届秋招笔面经#
