美团 笔试 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]);
    }
}