【2024-02-02】华为秋招笔试三道编程题解

恭喜发现宝藏！搜索公众号【TechGuide】回复公司名，解锁更多新鲜好文和互联网大厂的笔经面经。
作者@TechGuide【全网同名】

订阅专栏： 【专享版】2024最新大厂笔试真题解析，错过必后悔的宝藏资源！

第一题：找出最可疑的嫌疑人

题目描述

​民警侦办某商场店面盗窃率时，通过人脸识别针对嫌疑人进行编号1-100000。现在民警在监控记录中发现某个嫌疑人在被盗店面出现的次数超过了所有嫌疑人总出现次数的一半，请帮助民警尽可能高效​地找到该嫌疑人的编号。

输入描述

给定一个嫌疑人的标号数组men，其中1<length(men)<1000，嫌疑人编号满足1<=men[i]<=100000

输出描述

返回出现次数超过一半的嫌疑人的编号。

如果总次数是偶数，例如4，则需要超过2次即最少3次，如果总次数是奇数，例如5，则需要超过2.5，满足条件最少是3次。若没有嫌疑人满足该条件，返回0。

样例

输入

1,1,2,2,3,3

输出

0

样例说明

第一行是嫌疑人出现记录，代表1号、2号和3号嫌疑人各出现2次因为各个嫌疑人均只出现2次，未超过6次的一半，因此没有嫌疑人满足要求，输出0。

思路

简单遍历即可。统计每个嫌疑人编号出现的次数，然后遍历次数，找到出现次数超过总次数一半的编号。

代码

Java版本

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String[] input = scanner.nextLine().split(",");int[] nums = new int[input.length];for (int i = 0; i < input.length; i++) {nums[i] = Integer.parseInt(input[i]);}Map<Integer, Integer> counter = new HashMap<>();for (int num : nums) {counter.put(num, counter.getOrDefault(num, 0) + 1);}for (int k : counter.keySet()) {if (counter.get(k) > nums.length / 2) {System.out.println(k);return;}}System.out.println(0);}
}
// vx公众号关注TechGuide，专业生产offer收割机。

CPP版本

#include <iostream>
#include <vector>
#include <unordered_map>using namespace std;int main() {string input;getline(cin, input);vector<int> nums;size_t pos = 0;while ((pos = input.find(',')) != string::npos) {nums.push_back(stoi(input.substr(0, pos)));input.erase(0, pos + 1);}nums.push_back(stoi(input));unordered_map<int, int> counter;for (int num : nums) {counter[num]++;}for (const auto& entry : counter) {if (entry.second > nums.size() / 2) {cout << entry.first << endl;return 0;}}cout << 0 << endl;return 0;
}
// vx公众号关注TechGuide，专业生产offer收割机。

第二题：登录赢金币

题目描述

某公司日对新用户推出大礼包，从任意一天注册开始，连续登录x天，每天可以领取一定的金币，领取金币的数量与该公司新设计的虚假世界的日历相关，该日历一年有n个月，第i个月有di天，每一年都一样。在每个月第1天会得到1个金币，第2天会得到2个金币，第3天会得到3个金币，后面依次类推。 请计算新用户注册后连续登陆x天，最多可以获取多少金币。 请注意，连续登陆可能会跨年。

输入描述

第一行包含两个整数n和x，分别表示一年中的月数和连续登陆的天数。第二行包含n个整数d1,d2,…,dn ，di表示第i个月的天数。

输出描述

打印新用户连续登录x天最多可以获取的金币数量。

样例

输入

3 2
1 3 1

输出

5

样例说明

一年中每天获取的金币数是1，1，2，3，1(对应每个月中的天数)。如果在一年中的第3天开始注册陆，最多可以获取 2+3=5 个金币。

思路

用滑动窗口。计算每个月的金币总数和连续登陆的区间内金币总数，通过滑动窗口来更新最大值。注意开始复制了一份，覆盖跨年的情况。

代码

Java版本

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int x = scanner.nextInt();int[] d = new int[n * 2];for (int i = 0; i < n; i++) {d[i] = scanner.nextInt();d[i + n] = d[i];}int ans = 0;int curSum = 0;int cur = 0;int l = 0;for (int i = 0; i < n * 2; i++) {curSum += d[i];cur += d[i] * (d[i] + 1) / 2;while (curSum > x) {curSum -= d[l];cur -= d[l] * (d[l] + 1) / 2;l++;}int curAns = cur;int cnt = x - curSum;if (l > 0) {curAns += sumup(d[l - 1] - cnt + 1, d[l - 1]);ans = Math.max(ans, curAns);}}System.out.println(ans);}private static int sumup(int l, int r) {return r * (r + 1) / 2 - l * (l - 1) / 2;}
}// vx公众号关注TechGuide，专业生产offer收割机。

CPP版本

#include <iostream>
#include <vector>using namespace std;int sumup(int l, int r) {return r * (r + 1) / 2 - l * (l - 1) / 2;
}int main() {int n, x;cin >> n >> x;vector<int> d(n * 2);for (int i = 0; i < n; i++) {cin >> d[i];d[i + n] = d[i];}int ans = 0;int curSum = 0;int cur = 0;int l = 0;for (int i = 0; i < n * 2; i++) {curSum += d[i];cur += d[i] * (d[i] + 1) / 2;while (curSum > x) {curSum -= d[l];cur -= d[l] * (d[l] + 1) / 2;l++;}int curAns = cur;int cnt = x - curSum;if (l > 0) {curAns += sumup(d[l - 1] - cnt + 1, d[l - 1]);ans = max(ans, curAns);}}cout << ans << endl;return 0;
}// vx公众号关注TechGuide，专业生产offer收割机。

第三题：整数分解

题目描述

给你一个整数N(1 < N < 256)，它的一个分解是N = a1 x a2 x a3 x…x ax,其中1 <ai ≤ aj(i≤ j)

对于整数N,请依次输出每一个分解(按照字典序)

例如,给定整数24,输出是

24=2*2*2*3
24=2*2*6
24=2*3*4
24=2*12
24=3*8
24=4*6
24=24

输入描述

输入只有一个整数N

输出描述

按照字典序，依次输出整数N的每一个分解.

样例

输入

11

输出

11=11

思路

递归生成整数N的所有分解，然后按照字典序输出就行了。

代码

Java版本

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();List<List<Integer>> ans = fac(n, 2);for (List<Integer> v : ans) {System.out.print(n + "=");for (int i = 0; i < v.size(); i++) {System.out.print(v.get(i));if (i < v.size() - 1) {System.out.print("*");}}System.out.println();}}private static List<List<Integer>> fac(int n, int p) {List<List<Integer>> result = new ArrayList<>();if (n == 1) {result.add(new ArrayList<>());return result;}for (int i = p; i <= n; i++) {if (n % i == 0) {for (List<Integer> v : fac(n / i, i)) {List<Integer> temp = new ArrayList<>();temp.add(i);temp.addAll(v);result.add(temp);}}}return result;}
}// vx公众号关注TechGuide，专业生产offer收割机。

CPP版本

#include <iostream>
#include <vector>using namespace std;void printResult(int n, vector<int>& vec) {cout << n << "=";for (int i = 0; i < vec.size(); i++) {cout << vec[i];if (i < vec.size() - 1) {cout << "*";}}cout << endl;
}void fac(int n, int p, vector<int>& temp) {if (n == 1) {printResult(n, temp);return;}for (int i = p; i <= n; i++) {if (n % i == 0) {temp.push_back(i);fac(n / i, i, temp);temp.pop_back();}}
}int main() {int n;cin >> n;vector<int> temp;fac(n, 2, temp);return 0;
}// vx公众号关注TechGuide，专业生产offer收割机。