5.8 贝壳笔试 AC

1、用map存count和price,直接做就可以了
static void beike1() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        Map<String, Integer> countMap = new HashMap<>(), priceMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String s = scanner.next();
            int price = scanner.nextInt(), count = scanner.nextInt();
            countMap.put(s, count);
            priceMap.put(s, price);
        }
        int ans = 0;
        for (int i = 0; i < m; i++) {
            String s = scanner.next();
            int count = scanner.nextInt();
            ans += count * priceMap.get(s);
            count = countMap.get(s) - count;
            if (count < 0) {
                ans = -(i + 1);
                break;
            }
            countMap.put(s, count);
        }
        System.out.println(ans);
    }
2、排序+贪心+TreeMap,如果有更大的烧饼就叠加上去,没有就新开一堆
static void beike2() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] f = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = scanner.nextInt();
        }
        Arrays.sort(f);
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int ans = 0;
        for (int i = n - 1; i > -1; i--) {
            Integer key = map.higherKey(f[i]);
            if (key == null) {
                ans++;
                map.put(f[i], map.getOrDefault(f[i], 0) + 1);
                continue;
            }
            int val = map.get(key) - 1;
            if (val == 0) {
                map.remove(key);
            } else {
                map.put(key, val);
            }
            map.put(f[i], map.getOrDefault(f[i], 0) + 1);
        }
        System.out.println(ans);
    }

3、看数据规模感觉 暴力过不了,结果还是过了。。。
   static void beike3() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), k = scanner.nextInt();
        int[] f = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = scanner.nextInt();
        }

        int ans = 0;
        int cur = 0, l = 0;
        for (int i = 0; i < n; i++) {
            cur = 0;
            for (int j = i; j < n; j++) {
                cur += f[j] > k ? 1 : -1;
                ans = Math.max(ans, cur > 0 ? j - i + 1 : 0);
            }
        }
        System.out.println(ans);
    }

4、模拟+二分+前缀和,通过前缀和快速求sum,计算avg后二分,通过map记忆化防止重复计算(不过感觉不会重复计算)
  !(有个点是,苹果重量ai是10e9,求和可能会溢出,所以用了long)
    static void beike4() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), q = scanner.nextInt();
        long[] f = new long[n], pre = new long[n];
        Map<Integer, Map<Integer, Integer>> memo = new HashMap<>();
        for (int i = 0; i < n; i++) {
            f[i] = scanner.nextInt();
            memo.put(i, new HashMap<>());
        }

        Arrays.sort(f);
        for (int i = 0; i < n; i++) {
            pre[i] += f[i];
            pre[i] += i - 1 >= 0 ? pre[i - 1] : 0;

        }
//        SegmentTree segmentTree = new SegmentTree(f);
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{0, f.length - 1});
        Set<Long> set = new HashSet<>();
        set.add(0L);
        while (queue.size() > 0) {
            int[] a = queue.poll();
            int l = a[0], r = a[1];
            long sum = getSum(pre, l, r);
            set.add(sum);

            long avg = sum / (r - l + 1);
            if (f[l] == avg && f[r] == avg) {
                continue;
            }
            int idx = upperBound(f, avg, l, r);
            if (memo.get(l).get(idx) == null) {
                queue.add(new int[]{l, idx});
                memo.get(l).put(idx, 0);
            }
            if (memo.get(idx + 1).get(r) == null) {
//                queue.add(new int[]{l,
                queue.add(new int[]{idx + 1, r});
                memo.get(idx + 1).put(r, 0);

            }
        }

//        System.out.println(set.size());

        for (int i = 0; i < q; i++) {
            long num = scanner.nextInt();
            System.out.println(set.contains(num) ? "YES" : "NO");
        }
    }

    static long getSum(long[] f, int l, int r) {
        return l == 0 ? f[r] : f[r] - f[l-1];
    }


    static int upperBound(long[] f, long num, int l, int r) {
//        int l = 0, r = f.length - 1;
        while (l < r - 1) {
            int mid = (l + r) / 2;
            if (f[mid] <= num) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        if (f[l+1] <= num) {
            l++;
        }
        return l;
    }




#贝壳找房##笔经##java工程师#
全部评论
第二个直接输出一个数的最多数量就可以了
9 回复
分享
发布于 2021-05-08 22:04
怪不得,第四题我用递归,直接超出时间限制,哭鸟
4 回复
分享
发布于 2021-05-08 22:05
百信银行
校招火热招聘中
官网直投
感觉人均3道题
2 回复
分享
发布于 2021-05-08 22:10
第四题思路都想出来了,代码也写出来了,结果最后十几分钟调试太慢没调出来,哭了T﹏T
1 回复
分享
发布于 2021-05-08 22:07
前端题好像不一样?
1 回复
分享
发布于 2021-05-08 22:56
3ac能过吗
1 回复
分享
发布于 2021-05-08 23:36
大哥牛批  我才是2.9AC
点赞 回复
分享
发布于 2021-05-08 22:03
不知道为啥第一题总是百分之80 一共 2.73 AC😅
点赞 回复
分享
发布于 2021-05-08 22:05
大佬最后一题能讲细一点吗。。递归加二分还是0
点赞 回复
分享
发布于 2021-05-08 22:05
0.8 0.6 0.93 0.05有机会面试吗
点赞 回复
分享
发布于 2021-05-08 22:06
第二题只需要算重复次数最多的那个数的数量就行,计数就得到结果了 第四题同样的思路,不过不知道是哪里有问题,只AC了30%
点赞 回复
分享
发布于 2021-05-08 22:07
第四个本来会做的,结果数组排序的方法被我给忘了,直接GG😭
点赞 回复
分享
发布于 2021-05-08 22:08
2.3AC,估计没了😓
点赞 回复
分享
发布于 2021-05-08 22:09
第四题疯狂超时
点赞 回复
分享
发布于 2021-05-08 22:09
第四题不知道为啥总是差5%
点赞 回复
分享
发布于 2021-05-08 22:12
第三题python暴力只过50%
点赞 回复
分享
发布于 2021-05-08 22:31
做了前三个就交了🤣
点赞 回复
分享
发布于 2021-05-08 22:43
第二题咋写啊,题目都忘了🤣
点赞 回复
分享
发布于 2021-05-08 22:47
前三题感觉暴力就OK,本来打算优化一下,没想到暴力救过了。第四题一直超出内存限制,我用的递归,mmp
点赞 回复
分享
发布于 2021-05-09 12:08

相关推荐

8 37 评论
分享
牛客网
牛客企业服务