笔试复盘|网易传媒0807
网易传媒
投递时间：2021年8月7日 21点26分
校招；base：杭州；内推
0821-笔试
100·20%+100·30%+70·30%+66.67·20%=84
给一个数组，给一个整数M，需要找出数组中的两数和小于等于M的个数。
我的思路：双层循环遍历数组，复杂度
O(n^2)卡住的点：键盘输入的数组是一行，M在第二行，没有告诉数组的大小，所以无法用n循环读取
sc.nextInt，也无法通过while(sc.hasNextInt())循环读取，不会停的！！后来用了sc.nextLine()把数组读到String字符串里，然后split切分字符串，通过Integer.valueOf(c)转为数字，存到数组中。粗心的点：没有看到是==小于等于==，起初代码只写了小于，导致通过40%
import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.Scanner; public class Solution1 { public static void main(String[] args) { Scanner in = new Scanner(System.in); List<Integer> list = new ArrayList<>(); String line = in.nextLine(); for (String s : line.split(" ")) { list.add(Integer.valueOf(s)); } int M = in.nextInt(); // 对list排序 list.sort(new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o1 - o2; } }); if (list.get(0) > M) { System.out.println("0"); return; } int res = 0; for (int i = 0; i < list.size() - 1; i++) { for (int j = i + 1; j < list.size(); j++) { if (list.get(j) < M - list.get(i)) { res++; } } } System.out.println(res); } }给定一种创造字符串的方式，递归的，给出一个n和k，需要输出第n个字符串的第k个字符。
生成字符串的规则：
，
，
。翻转字符串包括两个内容：逆序+字母翻转，按照L逆序的方式对应，如”abz“reverse之后的结果是"ayz"
如n=3时的第k=1个字符是
a，这里的计数都是从1开始的。import java.util.*; public class Solution2 { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * <p> * 返回Sn的第k位字符 * * @param n int整型 Sn的n * @param k int整型 需要返回的字符下标位 * @return char字符型 */ public static char findKthBit(int n, int k) { Map<Character, Character> LR = new HashMap<>(); for (int i = 0; i < 26; i++) { LR.put((char) ('a' + i), (char) ('z' - i)); } if (n == 1 && k == 1) return 'a'; String res = recur(n, LR); return res.charAt(k - 1); } public static String recur(int n, Map<Character, Character> LR) { if (n == 1) { return "a"; } else { String s = recur(n - 1, LR); return s + (char) ('a' + n - 1) + reverse(s, LR); } } public static String reverse(String s, Map<Character, Character> LR) { StringBuilder sb = new StringBuilder(); for (int i = s.length() - 1; i >= 0; i--) { sb.append(LR.get(s.charAt(i))); } return sb.toString(); } public static void main(String[] args) { System.out.println(findKthBit(4, 11)); } }小朋友分纸，按照年龄分，每人最少分一张，旁边小朋友年龄大的要多分，年龄相同的可以小于等于，问最少的分纸数。
如：
- 1 2 3 4 需要 10 张
- 1 1 1 1 需要 4 张
我的思路：
- 不能排序，题目中涉及到旁边小朋友，因此要考虑左右邻居，有顺序性。
- 给小朋友的纸数用per表示，初始为1，第一个小朋友无论年龄大小，给他1张，临时变量存储第一个小朋友年龄；
- 从左遍历数组，当下一个小朋友年龄大于前一个小朋友，per+1，维护临时变量；【仅此条可以通过60%】
- 当下一个小朋友年龄小于当前小朋友，per-1，维护临时变量；【增加此条通过70%】
- 当下一个小朋友年龄等于当前小朋友，per=1，维护临时变量。【此条不太正确：如果连续几个相同年龄小朋友后面没有比他小的人，可以直接将后续的同年龄小朋友定1，如 2 2 2 2 ；否则，如2 2 2 1时，1至少需要1个，当给2置1时没啦】
这个思路通过70%样例，其实显然是不全面的，当小朋友顺序是4 3 2 1时，还按照初始为1，按照上述思路，会编程负数。因此，既然题目中说了”旁边“，就需要左右两个方向考虑，且不能初始为1，或者即使初始为1，后来也需要维护总纸数。
关于单调递增/递减的数组，完全可以找到最小年龄的位置给他1，然后随着年龄增长纸数增加。
当遇到相同年龄时，如果其左右没有比他小的，就可以给该位置只给1个。
4 3 2 1 1 2 2 2 3 4 【小朋友】
4 3 2 1 1 2 1 1 2 3 【纸数】
import java.util.*;
public class Solution3 {
public static void main(String[] args) {
// 按照年龄大小分配纸，年龄最小的分配1张，年龄大的多加1张
Scanner in = new Scanner(System.in);
List<Integer> list = new ArrayList<>();
String line = in.nextLine();
for (String s : line.split(" ")) {
list.add(Integer.valueOf(s));
}
// 只有一个小朋友
if (list.size() == 1) {
System.out.println("1");
return;
}
// 遍历list
int tmp = list.get(0);
int num = 1;
int per = 1;
for (int i = 1; i < list.size(); i++) {
int age = list.get(i);
if (age > tmp) { // 后面小朋友年纪大，per+1
per++;
} else if (age < tmp) { // 同岁/小
per--;
} else
per = 1;
tmp = list.get(i);
num += per;
}
System.out.println(num);
}
} 最短路径问题
package NETEASE;
public class Solution4 {
/**
* 计算最小航行费用
*
* @param input int整型二维数组 二维网格
* @return int整型
* <p>
* 1 代价 1
* 0 代价 2
* 2 无法行走
*/
public static int minSailCost(int[][] input) {
int m = input.length, n = input[0].length;
int[][] res = new int[m][n];
res[0][0] = 0;
// 初始化第一列
for (int i = 1; i < m; i++) {
if (input[i][0] == 0)
res[i][0] += (res[i - 1][0] + 2);
if (input[i][0] == 1)
res[i][0] += (res[i - 1][0] + 1);
if (input[i][0] == 2)
res[i][0] = 999999;
}
// 初始化第一行
for (int j = 1; j < n; j++) {
if (input[0][j] == 0)
res[0][j] += (res[0][j - 1] + 2);
if (input[0][j] == 1)
res[0][j] += (res[0][j - 1] + 1);
if (input[0][j] == 2)
res[0][j] = 999999;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (res[i - 1][j] == 9999999 && res[i][j - 1] == 9999999) {
return -1;
}
if (input[i][j] == 0)
res[i][j] = Math.min(res[i - 1][j], res[i][j - 1]) + 2;
if (input[i][j] == 1)
res[i][j] = Math.min(res[i - 1][j], res[i][j - 1]) + 1;
if (input[i][j] == 2)
res[i][j] = 9999999;
}
}
print(res);
return res[m - 1][n - 1];
}
public static void print(int[][] nums) {
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums[0].length; j++) {
System.out.print(nums[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
public static void main(String[] args) {
int res = minSailCost(new int[][]{{1, 1, 1, 1, 0}, {0, 1, 0, 1, 0}, {1, 1, 2, 1, 1}, {0, 2, 0, 0, 1}});
System.out.println(res);
}}
#网易##笔经#
查看31道真题和解析