百度笔试
百度-正式批
笔试-0907
选择题占60分，编程题占40分
选择题
基本是Java、计算机网络、操作系统、数据结构类的题目，考研408，emmmm
list.stream().map(d->1).reduce(0,(a,b)->a+b)：本题关于Java1.8的新特性stream的功能进行考察，stream是用来管理集合数据的，可以看作高级的迭代器；map用来归类；reduce用来计算值。本句代码表示计算流中元素个数，换成count()也可计数。- 计网：GBN协议，发送0-10帧，计时器超时，发送方只收到0、2、4，问现在需要重发第几帧？
- OS：分页存储系统，一次访存120ns，一次访问快表TLB30ns，命中率70%，计算有效访问时间？
本题需要明白，查询的流程，先去快表查（耗时30ns），如果命中，访存得到数据；否则查页表得到存储的地址（访存一次，耗时120ns），更新快表，去相应地址拿数据（访存一次，耗时120ns）；否则，如果内存中没有，就需要IO中断，访问外存。 - OS：三个进程ABC，分别需要执行计算操作、IO操作、计算操作，三个阶段需要的时间：A：60-50-10，B：100-60-30，C：80-10-40，问并行执行快了多少时间？
- Huffman编码的带权路径长度MPL的计算，给了一个序列{4，2，1，9，7，10}。参考
- JVM：Eden的垃圾占新生区的75%，好像是问新生区的分区比例？8：1：1
- 二分查找的次数
- Java：深拷贝和浅拷贝的知识考察。参考
- 数据结构：平衡二叉树的深度是4，最少多少节点？7个节点
代码题
送分题：给定一个二维矩阵，然后每一个位置需要横向纵向复制K份，输出扩大之后的新矩阵。
package baidu; import java.util.Scanner; /** * 给定图像的所有像素点0/1，现在要放大图像 */ public class solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(), k = sc.nextInt(); int[][] rawMap = new int[n][n]; int[][] retMap = new int[n * k][n * k]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { rawMap[i][j] = sc.nextInt(); } } for (int i = 0; i < n * k; i++) { for (int j = 0; j < n * k; j++) { retMap[i][j] = rawMap[i / k][j / k]; System.out.print(retMap[i][j] + " "); } System.out.println(); } } }3 2 1 2 3 4 5 6 7 8 9
1 1 2 2 3 3 1 1 2 2 3 3 4 4 5 5 6 6 4 4 5 5 6 6 7 7 8 8 9 9 7 7 8 8 9 9
数字规整问题，定义了一个“完美数”的概念，完美数中每一位都属于{1，2，3}，需要输出最大的不大于n的完美数。需要考虑的问题是大整数问题，题目给定的n的范围上限是10^18。
思路：可以通过字符串来接收键盘输入的内容，然后根据数字的长度选择用int型还是BigInteger类型，思路一致。用一个新数字存储修改后的结果，从个位数开始判断，如果当前数字大于3，那么将该数字直接置为3，存入新数字，num/=10；如果当前数字小于1，即0，那么将整个数字减1，进入下一层循环；如果当前数字在{1，2，3}之间，存入新数字，num/=10。【该思路超时】
package baidu; import java.math.BigInteger; import java.util.HashMap; import java.util.Scanner; /** * 十进制正整数的每一个数字都是1 2 3，则为完美数。 * 需要得到最大的，小于等于n的完美数 */ public class solution1 { public static BigInteger func(BigInteger n) { BigInteger newNum = BigInteger.valueOf(0); BigInteger pos = BigInteger.valueOf(1); while (n.bitLength() > 0) { // System.out.println("+" + n); // int lastNum = n % 10; int lastNum = n.divideAndRemainder(BigInteger.valueOf(10))[1].intValue(); if (lastNum < 1) { // 0，需要将该数-1，然后进入下一层循环 // n--; n = n.subtract(BigInteger.valueOf(1)); } else { if (lastNum > 3) { // 大于3，可以直接将原数中该位置替换为3 lastNum = 3; } newNum = newNum.add(pos.multiply(BigInteger.valueOf((long) lastNum))); n = n.divide(BigInteger.valueOf(10)); pos = pos.multiply(BigInteger.valueOf(10)); } } return newNum; } public static int func(int n) { int newNum = 0, pos = 1; while (n != 0) { int lastNum = n % 10; if (lastNum < 1) { // 0，需要将该数-1，然后进入下一层循环 n--; } else { if (lastNum > 3) { // 大于3，可以直接将原数中该位置替换为3 lastNum = 3; } newNum += lastNum * pos; n = n / 10; pos *= 10; } } return newNum; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int i = 0; i < T; i++) { String tmp = sc.next(); int a; BigInteger b; if (tmp.length() < 10) { a = Integer.parseInt(tmp); System.out.println(func(a)); // 10^18 } else { b = new BigInteger(tmp); System.out.println(func(b)); // 10^18 } } } }11 213 3244 22 646201396803243732 1209 1109 1120323 1110323 1111423 11113231 1102
213 3233 22 333131333333233332 1133 333 1113333 333333 1111333 11113231 333
设计测试用例：
- 完全符合条件：123-->123
- 包含大于3的数字：1267-->1233【增加条件，如果该位置数字大于3，将其置为3，pos--】
- 包含0： 2089 --> 1333【增加标志位mark=0，如果当前数字为0，mark=1，将该位置置为3，pos--，下一位数字需要减去mark】【发现2->1没有生效，原来是计算出来的结果需要覆盖掉原值】
- 包含0的特例：100000-->33333【存在连续的两个0，前一位数字-mark之后等于-1，也意味着当前位置曾是0，保持mark=1】
- 1102->333：该样例，用以下代码仍有遗漏【如果第一位数字为0了，直接返回所有位都是3的数字】
- 15102->13333：根据5、6样例分析，如果当前数字比3大，那么该位之后的低位数字都可以提高至3.
新解法：
public static String func(String n) { char[] newNum = n.toCharArray(); // 从个位开始判断 int mark = 0; // 标记是否需要向前一位借位 int pos = n.length() - 1; while (pos >= 0) { int curNum = n.charAt(pos) - 48 - mark; if (pos == 0 && curNum == 0) { // 第一位的数字是0的话，无法借位，用空格代替咯 newNum[pos] = ' '; break; } if (curNum >= 1 && curNum <= 3) { newNum[pos] = (char) (curNum + 48); // 后一位有借位的话，需要更新当前数字 mark = 0; // 1209检查出来的bug，此时没有借位，但是mark仍保留着原来的1，因此恢复mark pos--; continue; } else { mark = curNum == 0 || curNum == -1 ? 1 : 0; // 如果当前位置超过3，或者需要借位，都需要将该位置置为3， // 说明从该位开始的低位数，即使取到最大也比原数小，因此那么之后低位数字要改为3才能取到最大 if (curNum > 3 || mark == 1) { int tmpPos = pos; while (tmpPos<len){ newNum[tmpPos] = (char) (3 + 48); tmpPos++; } } newNum[pos] = (char) (3 + 48); } pos--; } return new String(newNum).trim(); // trim来去除最前面的空格 } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int i = 0; i < T; i++) { String tmp = sc.next(); System.out.println(func(tmp)); } }包含k种字母的子序列个数：给定字符串的长度和k，以及一个字符串。
题目描述
在数学中，某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置而形成的新序列，如对于字符"abc"，“ab” 和 "ac” 都是其子序列，而"cb"和"ca"不是。牛牛有一个长度为n的仅由小写字母组成的字符串s，牛牛想知道 s有多少子序列恰好包含k种字母?
输入描述
第一行输入两个正整数n和k。
第二行输入一个长度为n的仅包含小写字母的字符串s。(1≤n<105,1<k≤26)6 5 eecbad
3
package baidu;
// 参考：https://www.nowcoder.com/discuss/735052?type=post&order=create&pos=&page=0&ncTraceId=&channel=-1&source_id=search_post_nctrack
import java.util.HashMap;
import java.util.Scanner;
public class solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
String s = sc.next();
HashMap<Character, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
int cnt = map.getOrDefault(s.charAt(i), 0);
cnt++;
map.put(s.charAt(i), cnt);
}
int[] v = new int[26];
int[] w = new int[26];
int[] dp = new int[26];
for (char i = 'a'; i < 'z'; i++) {
v[i - 'a'] = (int) (Math.pow(2, map.getOrDefault(i,0)) - 1); // 2^n-1
w[i - 'a'] = 1;
}
dp[0] = 1;
for (int i = 0; i < 26; i++) {
for (int j = k; j > 0; j--) {
if (j >= w[i]) {
int mod = (int) (1e9 + 7);
dp[j] = (dp[j] + dp[j - w[i]] * v[i]) % mod; // dp转移式子
}
}
}
System.out.println(dp[k]);
}
} package baidu;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
// DFS解法
public class solution2 {
public static int cnt = 0;
static void dfs(String s, int cur, StringBuilder sb, int k) {
System.out.println("cur=" + cur + " " + sb.toString());
if (cur == s.length()) {
Set<Character> set = new HashSet<>();
String s1 = sb.toString();
for (int i = 0; i < s1.length(); i++) {
set.add(s1.charAt(i));
}
if (set.size() == k) {
cnt++;
}
return;
}
sb.append(s.charAt(cur));
dfs(s, cur + 1, sb, k);
sb.deleteCharAt(sb.length() - 1);
dfs(s, cur + 1, sb, k);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int k = sc.nextInt();
String s = sc.next();
dfs(s, 0, new StringBuilder(), k);
System.out.println(cnt);
}
} #面试复盘##百度##笔经#
理想汽车工作强度 71人发布
查看5道真题和解析
