2024.4.27 美团笔试
和携程差不多，签到题速通，后续疯狂折磨人，过不了一点。感觉题目难度差的好大，要么我秒杀它，要么它秒杀我
第三题
回溯写了半天，结果只能过20%。看别人是用前缀和+dp，那就是和腾讯第四题类似了，当时学会了现在又忘了，真难崩。
小美拿到了一个数组，她每次操作可以将两个相邻元素合并为一个元素，合并后的元素为原来两个元素之和。小美希望最终数组的最小值不小于 k。她想知道有多少种不同的合并结果?
输入描述：第一行输入两个正整数n,k，代表数组大小和数组的最大值。第二行输入几个正整数q:，代表小美拿到的数组。1 ≤ n,k,ai < 200
输出描述：输出一个整数，代表小美可以得到多少种不同的结果。由于结果可能很大，输出对10^9+7取模的结果。
eg：
输出 4
回溯解法，只过20%（加了dp保存过程值也没用）
class Solution_3 {
int[] dp;
int[] a;
int k;
void solve(int[] a, int k) {
this.dp = new int[a.length];
this.a = a;
this.k = k;
Arrays.fill(dp, -1);
System.out.println(backtrack(0, 0));
}
int backtrack(int sum, int index) {
if (index==a.length) return 1;
if (sum==0 && dp[index]!=-1)
return dp[index];
int cnt=0;
boolean isBegin = sum==0;
for (int i=index; i<a.length; i++) {
sum += a[i];
if (sum>=k) {
cnt += backtrack(0, i+1);
}
}
if (isBegin) dp[index] = cnt;
return cnt;
}
}
class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), k = in.nextInt();
int[] a = new int[n];
for (int i=0; i<n; i++) {
a[i] = in.nextInt();
}
new Solution_3().solve(a, k);
}
}
|
自己试试写前缀和+dp（思路重要真的很重要，二十分钟就写出来了）
dp[i] 表示数字 0-i 的方案数[0, i) 的字串可以拆分的种类，状态转移方程为$dp[i] = \sum dp[j]$（j-i 大于等于 k 的数量总和，用前缀和求出）
class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), k = in.nextInt();
int[] sum = new int[n+1];
sum[1] = in.nextInt();
for (int i=2; i<=n; i++) {
sum[i] += sum[i-1] + in.nextInt();
}
int[] dp = new int[n+1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (sum[i] - sum[j] >= k) {
dp[i] += dp[j];
}
}
}
System.out.println(dp[n]);
}
}
|
Q1：前缀和算法初始化时为什么都要设置 [0, 0] = 1 呢？ 如: dp[0] = 1 or map.put(0,1)
A1：想不明白呢，需要对状态转移数组 dp[] 的理解非常正确才行
第四题
小美拿到了一棵树，其中有一些节点被染成红色。
大佬的思路：预打表小质数，然后dfs遍历连通块，统计块内每个红点的质因子，得到结点编号的乘积的质因子分解形式，根据质因子数量计算因子个数。对于我来说，需要背一下并查集的模板。
小美定义一个红色连通块的权值为:所有节点编号乘积的因子数量。小美想知道，所有红色连通块的权值之和是多少?由于答案过大，请对10^9+ 7取模。
输入描述：
第一行输入一个正整数n，代表节点数量。第二行输入一个长度为几的、仅由’R"和"W组成的字符串，第i个字符为’R’代表;号节点被染成红色，"W代表未被染色。保证至少有一个节点被染成红色。
接下来的n - 1行，每行输入2个正整数4,U，代表u号节点和u号节点有一条边连接。1 ≤n ≤ 10^5, 1 ≤u,v≤n
输出描述：
一个整数，代表所有红色连通块的权值之和。
2024.4.25 华为测评
华子免笔试，只有测评了。看网上好多人测评挂了我都惊呆了，还好没和其他的厂一样直接做测评而是上我搜了下，其他的厂可以不去但华子我必然拿下（小心谨慎哈哈哈）
华子要什么样性格的人？（前后回答要一致）
- 不需要凸显自己的能力、表达自己的个性，更多的是团队合作
- 遇到挫折要坚持，遇到问题会咨询
- 热爱工作，吃苦耐劳，积极向上
（准备了又好像没准备，就这样吧，希望能过！阿弥陀佛财神爷保佑！）
复盘：有些过于没有压力了，前面每一题都认真思考结果 40min 过完才做了一半，人家都是 40min 就做完了，实在是有些拖拉（但这个要认真选真的很难啊，得回忆自己平常的所思所想所做才然后选个答案，后续时间紧张直接主观臆断速度还是很快的）。只要时间不紧张就慢慢做，一旦时间紧张了才开始全神贯注做，这可真的是一个坏毛病，得改。
后续学习工作中都应该有这个意识，主动养成专注的习惯，要做就认真仔细专注的做事情！
2024.4.16 携程笔试
前两道签到题，后面一个半小时纯折磨
第三题
游游拿到了一个数组，她每次操作可以将相邻的两个素数元素进山314行合并，合并后的新数为原来的两个数之和，并删除原来两个数。游游希望最终数组的元素数量尽可能少，你能帮帮她吗?
第一行输入一个正整数n，代表数组的大小。第二行输入几个正整数a_i，代表数组的元素
1 ≤ n < 10^5
1 ≤ a_i < 10^6
返回合并结束后的元素的数量
题目分析：素数是只能被1和自身整除的数。针对这道题可以用到，它的一大特性：除了 2 之外两个素数之和一定是偶数（即，一定不是素数）
因此只要先把所有 2 和素数合并，后续只需要判断还有多少相邻的素数即可。
做题的时候没有考虑到 7 2 2 3 这种情况，即素数和 2 合并完的结果如果是素数，还需要和判断他的左边还有没有 2，有的话还要合并，即代码中的 i-- 部分。
class PrimeMerge {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
List<Integer> numbers = new ArrayList<>();
for (int i = 0; i < n; i++) {
numbers.add(scanner.nextInt());
}
mergePrimesWithPriorityToTwo(numbers);
for (int num : numbers) {
System.out.print(num + " ");
}
}
static boolean isPrime(int num) {
if (num <= 1) return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
private static void mergePrimesWithPriorityToTwo(List<Integer> numbers) {
for (int i = 0; i < numbers.size(); ) {
if (numbers.get(i) == 2) {
if (i > 0 && isPrime(numbers.get(i - 1)) && isPrime(numbers.get(i - 1) + 2)) {
numbers.set(i - 1, numbers.get(i - 1) + 2);
numbers.remove(i);
i--;
} else if (i < numbers.size() - 1 && isPrime(numbers.get(i + 1)) && isPrime(numbers.get(i + 1) + 2)) {
numbers.set(i, numbers.get(i) + numbers.get(i + 1));
numbers.remove(i + 1);
i--;
} else {
i++;
}
} else {
i++;
}
}
for (int i = 0; i < numbers.size() - 1; ) {
if (isPrime(numbers.get(i)) && isPrime(numbers.get(i + 1))) {
numbers.set(i, numbers.get(i) + numbers.get(i + 1));
numbers.remove(i + 1);
} else {
i++;
}
}
}
}
|
第四题
定义一棵树的直径为：任意两个节点的距离的最大值。现在定义f(i)：对i号节点上再连接一个新的子叶节点后，树的直径长度。现在要求f(1)到f(n)的值。
输入描述：第一行输入一个正整数n，代表树的节点数量。
接下来的n-1行，每行输入两个正整数u和v，代表u号节点和v号节点之间有一条长度为1的边连接。
变量的范围：1≤n≤10的五次方，1≤u，v≤n。
题目分析： 树的直径引出树形 dp 算法
class TreeNode {
int val;
List<TreeNode> children;
public TreeNode(int val) {
this.val = val;
children = new ArrayList<>();
}
}
public class TreeDiameter {
public static int[] f;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
f = new int[n + 1];
TreeNode[] nodes = new TreeNode[n + 1];
for (int i = 1; i <= n; i++) {
nodes[i] = new TreeNode(i);
}
for (int i = 0; i < n - 1; i++) {
int u = scanner.nextInt();
int v = scanner.nextInt();
nodes[u].children.add(nodes[v]);
nodes[v].children.add(nodes[u]);
}
for (int i = 1; i <= n; i++) {
nodes[i].children.add(new TreeNode(-1));
dfs(nodes[i], null, i);
nodes[i].children.remove(nodes[i].children.size()-1);
}
for (int i = 1; i <= n; i++) {
System.out.print(f[i] + " ");
}
}
public static int dfs(TreeNode node, TreeNode parent, int i) {
int maxDepth1 = 0;
int maxDepth2 = 0;
for (TreeNode child : node.children) {
if (child == parent) continue;
int childDepth = dfs(child, node, i) + 1;
if (childDepth > maxDepth1) {
maxDepth2 = maxDepth1;
maxDepth1 = childDepth;
} else if (childDepth > maxDepth2) {
maxDepth2 = childDepth;
}
}
f[i] = Math.max(f[i], maxDepth1 + maxDepth2);
return maxDepth1;
}
}
|
2024.4.9 恒生笔试
- 下列代码的返回值
int count() {
try {
return 5/0;
} catch (Exception e) {
return 2*3;
} finally {
return 3;
}
}
|
根据Java语言规范文档规定。在 try-catch-finally 语句块中，finally 语句块中的 return/抛出异常（立即结束语句）的优先级最高，程序会优先返回 finally 语句块中的立即结束语句的结果，此时 try-catch 语句块中的 return/抛出异常（立即结束语句）的结果就会被丢弃掉。
- SQL 语句
联结语法、INNER JOIN 语法
- 初始资金 M，N 天价格信息，K 次交易后，能赚多少钱？（动态规划）
public double get_max_profit (double M, int N, double[] historyPrices, int K) {
double[][] dp = new double[K+1][N];
for (int j=1; j<N; j++) {
dp[0][j] = M;
}
for (int i=0; i<=K; i++) {
dp[i][0] = M;
}
for (int i=1; i<=K; i++) {
for (int j=1; j<N; j++) {
double max = dp[i][j-1];
for (int t=0; t<j; t++) {
double rest = dp[i-1][t]%historyPrices[t], buy = (dp[i-1][t]-rest)/historyPrices[t];
max = Math.max(max, buy*historyPrices[j]+rest);
}
dp[i][j] = max;
}
}
return dp[K][N-1]-dp[0][0];
}
|
2024.3.31 腾讯笔试
没做好记录，只记了没做出来的第四题，其他四道题 AC 了三道，还有一道通过 97% 我怀疑是样例有问题[手动狗头]
- 给你 n 个数，这 n 个数要被拆成 k 份，对每份中的数字求异或，求各份异或总和的最大值（和恒生第二题的思路基本一样）
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int k = in.nextInt();
long[][] dp = new long[k + 1][n + 1];
for (int i = 0; i < n; i++) {
dp[1][i + 1] = in.nextInt() ^ dp[1][i];
}
long[] prefix = dp[1];
for (int i = 2; i <= k; i++) {
for (int j = i; j <= n; j++) {
long max = 0;
for (int s = j - 1; s >= i - 1; s--) {
max = Math.max(max, dp[i - 1][s] + (prefix[j] ^ prefix[s]));
}
dp[i][j] = max;
}
}
System.out.println(dp[k][n]);
}
|