当前位置： 首页 > news >正文

2024年美团春招技术岗第一批笔试

news 2025/7/6 14:57:53

链接：2024年美团春招技术岗第一批笔试

1.小美的平衡矩阵

题目：

思路：

1.分析题目：求[1~n]的完美矩阵个数

2.二维前缀和：

基础算法总结-xuan

3.枚举完美矩阵（d * d）矩阵终点，判断是不是完美矩阵

代码： 

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[][] nums = new int[n + 1][n + 1];for (int i = 1; i <= n; i ++) {String s = sc.next();for (int j = 0; j < n; j ++) {char c = s.charAt(j);nums[i][j + 1] = c - '0';}}// 求二维前缀和int[][] s = new int[n + 1][n + 1];for (int i = 1; i <= n; i ++) {for (int j = 1; j <= n; j ++) {s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + nums[i][j];}}for (int d = 1; d <= n; d ++) {// 算出 d * d 的完美矩阵数量int sum = d * d;int count = 0;// 枚举终点for (int i = d; i <= n; i ++) {       for (int j = d; j <= n; j ++) {// 得到起点int x = i - d + 1, y = j - d + 1;// 当前矩阵的和int t = s[i][j] - s[x - 1][j] - s[i][y - 1] + s[x - 1][y - 1];if (sum - t == t) {count ++;}}}System.out.println(count);}}
}

2.小美的数组询问

题目：

思路：

1.分析一下数据范围:(10^9) * (10^5 ) + (10^9) * (10^5) = 2 * (10^14)

2.long是64位的数据范围最大可到  9,223,372,036,854,775,807（即 2^63 - 1)

(所以long可以存下结果)

代码： 

import java.util.Scanner;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int q = sc.nextInt();int[] a = new int[n + 1];int count = 0;long sum = 0;for (int i = 1; i <= n; i ++) {a[i] = sc.nextInt();if (a[i] == 0) count ++;sum += a[i];}// q个询问while (q -- > 0) {int l = sc.nextInt();int r = sc.nextInt();long x = (long)l * count + sum;long y = (long)r * count + sum;System.out.println(x + " " + y);}}
}

补充：

高精度计算：

 这一题让我想到了高精度计算那一块的知识点，用高精度计算写了一下

import java.util.Scanner;
import java.util.ArrayList;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int q = sc.nextInt();int[] a = new int[n + 1];int count = 0;long sum = 0;for (int i = 1; i <= n; i ++) {a[i] = sc.nextInt();if (a[i] == 0) count ++;sum += a[i];}// q个询问while (q -- > 0) {int l = sc.nextInt();int r = sc.nextInt();StringBuilder minv = calculate(l, count, sum);StringBuilder maxv = calculate(r, count, sum);System.out.println(minv + " " + maxv);}}/** 高精度计算 num * count + sum*/public static StringBuilder calculate(long num, long count, long sum) {// 以字符串的形式返回结果StringBuilder str = new StringBuilder();ArrayList<Long> list = new ArrayList<Long>();long a = num * count;// 整理一下 a 和 sum 的值// a + sum = maxv + minvlong maxv = Math.max(a, sum);long minv = Math.min(a, sum);// maxv + minvlong p = 0; // 进位while (maxv > 0) {// 取出个位数long i = maxv % 10; long j = minv % 10;maxv /= 10;minv /= 10;long x = i + j + p;// 添加到结果中str.append(x % 10);p = x / 10; }while (p > 0) {str.append(p % 10);p /= 10;}return str.reverse();}
}

当然，Java中有封装好的高精度计算的类BigDecimal和BigInteger：

import java.util.Scanner;
import java.math.BigDecimal;
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int q = sc.nextInt();int[] a = new int[n + 1];int count = 0;long sum = 0;for (int i = 1; i <= n; i ++) {a[i] = sc.nextInt();if (a[i] == 0) count ++;sum += a[i];}// q个询问while (q -- > 0) {// num * count + sumBigDecimal l = new BigDecimal(sc.nextInt()).multiply(new BigDecimal(count)).add(new BigDecimal(sum));BigDecimal r = new BigDecimal(sc.nextInt()).multiply(new BigDecimal(count)).add(new BigDecimal(sum));System.out.println(l + " " + r);}}
}

 3.小美的MT

题目：

思路：

当这个字符串出现全部都是M或者T的情况时，剩下的修改次数没什么意义了，因为可以把M改成T，把T改成M，所以说它们内部消化了，并不会影响结果

代码： 

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int k = sc.nextInt();char[] c = sc.next().toCharArray();int count = 0;for (char x : c) {if (x == 'M' || x == 'T') count ++;}if (n - count >= k) {System.out.println(count + k);}else {System.out.println(n);}}
}

4.小美的朋友关系

题目：

思路：

1.存储朋友关系（pair<u, v>）：Set<Pair> st

2.存储事件(按顺序存储):List<Event> events

3.处理淡忘朋友的这个事件:

  1. 判断当前是不是朋友 isValid : true是朋友 false 不是朋友
  2. 是朋友：从st集合中移除当前主角的朋友关系

4.创建并查集（这个并查集是坚定的好朋友集合，不存在淡忘的）：

  1. 遍历st集合：并查集 + 路径压缩 [find(x)]

5.逆序处理事件

  • 因为事件的发生是有先后顺序的，淡忘是后面发生的事情，不影响前面，所以从后往前处理事件把这些短暂朋友关系插入到并查集中（此时的并查集有坚定的好朋友也有不坚定的短暂朋友）

6.理解一下：

顺序事件发生时间线：

  • 2025年5月14号 A和B是朋友（不坚定的短暂朋友）
  • 2025年5月15号 问A和B是不是朋友
  • 2025年5月16号 A和B淡忘了

逆序时间处理逻辑：

  • 首先A和B真的曾经是朋友，但是淡忘了，所以在16号以前他们是朋友，所以在16号之前询问他两的关系，回答的都是A和B是朋友

这里的输入输出如果用普通的，会超时，ε=(´ο｀*)))唉~

用StreamTokenizer和StringBuilder优化

代码： 

import java.io.*;
import java.util.*;public class Main {static class Pair {final int u, v;Pair(int u, int v) {this.u = Math.min(u, v);this.v = Math.max(u, v);}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Pair pair = (Pair) o;return u == pair.u && v == pair.v;}@Overridepublic int hashCode() {return Objects.hash(u, v);}}static class Event {int op;Pair pair;boolean isValid;Event(int op, Pair pair, boolean isValid) {this.op = op;this.pair = pair;this.isValid = isValid;}}private static Map<Integer, Integer> parent = new HashMap<>();private static Set<Pair> st = new HashSet<>();private static int find(int x) {if (!parent.containsKey(x)) {parent.put(x, x);return x;}if (parent.get(x) != x) {parent.put(x, find(parent.get(x)));}return parent.get(x);}private static void union(int x, int y) {int fx = find(x);int fy = find(y);if (fx != fy) {parent.put(fx, fy);}}public static void main(String[] args) throws IOException {// 使用StreamTokenizer优化输入StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));in.nextToken(); int n = (int)in.nval;in.nextToken(); int m = (int)in.nval;in.nextToken(); int q = (int)in.nval;// 读取初始关系for (int i = 0; i < m; i++) {in.nextToken(); int u = (int)in.nval;in.nextToken(); int v = (int)in.nval;st.add(new Pair(u, v));}// 处理事件List<Event> events = new ArrayList<>(q);for (int i = 0; i < q; i++) {in.nextToken(); int op = (int)in.nval;in.nextToken(); int u = (int)in.nval;in.nextToken(); int v = (int)in.nval;Pair pair = new Pair(u, v);if (op == 1) {boolean isValid = st.remove(pair);events.add(new Event(op, pair, isValid));} else {events.add(new Event(op, pair, false));}}// 构建初始并查集for (Pair p : st) {union(p.u, p.v);}// 处理查询List<String> res = new ArrayList<>();for (int i = events.size() - 1; i >= 0; i--) {Event e = events.get(i);if (e.op == 1 && e.isValid) {union(e.pair.u, e.pair.v);} else if (e.op == 2) {int fu = find(e.pair.u);int fv = find(e.pair.v);res.add(fu == fv ? "Yes" : "No");}}// 使用StringBuilder优化输出StringBuilder sb = new StringBuilder();for (int i = res.size() - 1; i >= 0; i--) {sb.append(res.get(i)).append('\n');}// 使用PrintWriter输出结果try (PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out))) {out.print(sb);}}
}

5.小美的区间删除 

题目：

思路：

1.分析规律：

  • 什么样的数相乘末尾能出现0？也就是出现10
  • 将10分解质因数：2和5
  • 也就是说当含有2或5因子的数就可能出现10

2.把数组中每个数都求出其含2和5的个数并求出对应前缀和

3.维护一个滑动窗口，要保证窗口外数字相乘末尾的0不小于k， 当前窗口维护的2和5的个数不能超过p = count-k

4.枚举窗口终点，当窗口不满足条件时（即窗口维护的2和5的个数不能超过p = count-k），窗口移动，直到满足需求

5.窗口左端点为靠近终点的那一个，窗口内的任一数删除都能保证条件成立

代码： 

import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;
import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {private static int[] a, two, five, ten;private static int[] sum2, sum5;private static int count2 = 0, count5 = 0;public static int calculate(int x, int t) {int count = 0;while (x % t == 0) {x /= t;count ++;}if (t == 2) count2 += count;else count5 += count;return count;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int k = sc.nextInt();a = new int[n + 1];two = new int[n + 1];five = new int[n + 1];sum2= new int[n + 1];sum5 = new int[n + 1];for (int i = 1; i <= n; i ++) {a[i] = sc.nextInt();two[i] = calculate(a[i], 2);five[i] = calculate(a[i], 5);sum2[i] = sum2[i - 1] + two[i];sum5[i] = sum5[i - 1] + five[i];}long res = 0;if (Math.min(count2, count5) < k) {res = 0;}else {// 枚举终点 // 维护到当前终点的最小起点int p2 = count2 - k; int p5 = count5 - k; // 区间内的2和5不能超过p2和p5// 始终要保持区间外的2和5个数是大于等于k的int l2 = 0, l5 = 0;// r在向右移动的过程中 一定是2和5增加的过程// 所以维护的左端点整体上也是越来越靠近右边// for (int r = 1; r <= n; r ++) {while (sum2[r] - sum2[l2] > p2) l2 ++;while (sum5[r] - sum5[l5] > p5) l5 ++;// 找到最小的区间 最靠终点 减去0最少的区间int l = Math.max(l2, l5);// 删除该区间任一数剩下的数组都满足k个0res += Math.max(0, r - l);}}System.out.println(res);}
}

http://www.xdnf.cn/news/484237.html

相关文章：

  • 23、电网数据管理与智能分析 - 负载预测模拟 - /能源管理组件/grid-data-smart-analysis
  • nfs网络文件系统
  • 网站推荐（第四期）
  • 【C++ 基础数论】质数判断
  • Pageassist安装（ollama+deepseek-r1）
  • AI 赋能 Copula 建模：大语言模型驱动的相关性分析革新
  • 每周资讯 | 腾讯Q1财报：国内游戏业务收入同比增长24%；Tripledot 8亿美元收购AppLovin游戏业务
  • 十一、Hive JOIN 连接查询
  • IDEA中git对于指定文件进行版本控制
  • 架构与UML4+1视图
  • 基于PXIE 总线架构的Kintex UltraScale 系列FPGA 高性能数据预处理板卡
  • leetcode2749. 得到整数零需要执行的最少操作数-medium
  • ai agent(智能体)开发 python高级应用5：crawl4ai 如何建立一个全面的知识库 第一步找分类
  • Redis 五种类型基础操作(redis-cli + Spring Data Redis)
  • STM32F407VET6的HAL库使用CRC校验的思路
  • React文件上传组件封装全攻略
  • WEB安全--Java安全--shiro550反序列化漏洞
  • Linux——UDP/TCP协议理论
  • 利用Python高效整理猫狗数据集训练集与验证集（附源码讲解）
  • 技术书籍推荐(001)
  • 硬件中的OID是什么？SNMP如何通过OID获取信息？——用“图书馆”比喻彻底讲清底层原理-优雅草卓伊凡|小无
  • makefile细节说明
  • 在 VSCode 中运行 Vue.js 项目
  • 抛物线运动路径动画实现
  • Android framework 中间件开发(三)
  • 高效管理嵌套Git仓库：三合一脚本解决方案
  • 【AI】CUDA 是如何成功的？（AI 计算的民主化，第 3 部分）
  • MOS管、三极管与IGBT管的原理与应用全面对比
  • 如何解决Move to iOS 不起作用的问题?
  • Yocto Project 快速构建