字节客户端开发笔试10.20
记录第一次笔试AK
第一题思路:数学题,等差数列求和公式
第二题思路:先排序,然后在相邻数对的差值中找最大公因数
第三题思路:从终点出发做BFS,记录所有步长的频率求期望,用gcd得到不可约分形式
第四题思路:用TreeSet保存每行每列的机器人位置,利用TreeSet的lower和higher快速确定是走到边界还是另一个机器人的旁边。
第一题思路:数学题,等差数列求和公式
第二题思路:先排序,然后在相邻数对的差值中找最大公因数
第三题思路:从终点出发做BFS,记录所有步长的频率求期望,用gcd得到不可约分形式
第四题思路:用TreeSet保存每行每列的机器人位置,利用TreeSet的lower和higher快速确定是走到边界还是另一个机器人的旁边。
全部评论
第三个题我bfs完后,用gcd求完过了33,不用gcd过了44,难绷
第三题核心代码:
// 从终点开始BFS
// 记录每个步数的频率
Map<Integer, Integer> t = new HashMap<>();
int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
boolean[][] visit = new boolean[n][m];
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{ex, ey, 0});
visit[ex][ey] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
int x = cur[0], y = cur[1], dis = cur[2];
// 访问当前节点并更新频率
t.put(dis, t.getOrDefault(dis, 0) + 1);
// 四个方向探查
for (int[] dir : dirs) {
int nx = x + dir[0], ny = y + dir[1];
if (0 <= nx && nx < n && 0 <= ny && ny < m && !visit[nx][ny] && map[nx][ny] != '1') { // 可以前进
q.offer(new int[]{nx, ny, dis + 1});
visit[nx][ny] = true;
}
}
}
牛哇佬
哥们没有曼哈顿距离那道题嘛
可以分享下bfs吗 做的乱七八糟的
bfs那题不知道为啥只过了40%
相关推荐