北京博乐科技有限公司2025届程序技术类笔试题

1.划船

某人逆着水流的方向向岸边划船，每次行进前进x米后需要休息一下，休息期间船会自行倒退y米，每次休息后再次行进，前进距离缩短1/5，若起始距离岸边为m米，问：能否到达岸上，需要行进多少次才能上岸。

如果可以返回次数，如果不能返回-1。

补充说明

x、y、m均为大于0的浮点数

输入

8,2,13

输出

3

题解

import java.util.Scanner;public class Main {public static void main(String[] args) {// 读取输入（格式：x,y,m，均为浮点数）Scanner scanner = new Scanner(System.in);String input = scanner.nextLine();scanner.close();// 分割输入字符串，转换为浮点数String[] parts = input.split(",");double x = Double.parseDouble(parts[0]); // 初始前进距离double y = Double.parseDouble(parts[1]); // 每次休息倒退距离double m = Double.parseDouble(parts[2]); // 起始距离岸边的距离// 调用计算方法，输出结果int result = calculateBoatTimes(x, y, m);System.out.println(result);}/*** 计算划船上岸所需的行进次数* @param initialX 初始前进距离（第一次行进的距离）* @param y 每次休息后的倒退距离* @param m 起始距离岸边的距离* @return 成功上岸返回次数，无法上岸返回-1*/private static int calculateBoatTimes(double initialX, double y, double m) {double remainingDistance = m; // 当前剩余距离岸边的距离double currentX = initialX;   // 当前次行进的前进距离int count = 0;                // 行进次数计数器// 循环模拟每次行进-休息的过程while (true) {// 1. 第count+1次行进，前进currentX米count++;remainingDistance -= currentX;// 2. 判断行进后是否已到达岸边（剩余距离≤0）if (remainingDistance <= 1e-9) { // 浮点数比较，避免精度误差return count;}// 3. 未到达，休息并倒退y米（倒退后剩余距离不小于0）remainingDistance = Math.max(remainingDistance + y, 0.0);// 4. 更新下一次的前进距离（缩短1/5，即变为原来的4/5）currentX *= 0.8; // 1 - 1/5 = 4/5 = 0.8// 5. 若下一次前进距离≤0，后续无法再前进，返回-1if (currentX <= 1e-9) { // 浮点数精度判断return -1;}}}
}

2.希尔排序

直接插入排序的原理是将第i个元素插入前面i-1个已排好序的记录中，将比第i个元素大的记录依次向后移动一个位置，将第i个元素插入空位。

希尔排序在直接插入排序的基础上进行了改进，它通过比较相距一定间隔的元素来进行，各轮比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一轮排序为止。所以希尔排序又称缩小增量排序，它能减少元素的移动次数。

输入一个无序数组和增量因子序列（表示每次比较的位置间隔），输出进行希尔排序过程中元素向后移动的次数。

示例1

输入

[5, 6, 1, 4], [2, 1]

输出

2

说明

第一轮5和1比较，6和4比较，后移2次;

第二轮已有序，移动0次

示例2

输入

[1, 4, 3, 7, 5], [3, 1]
**
输出**

2

说明

第一轮1和7,4和5比较，后移0次;

第二轮相邻比较，后移2次。

题解：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取输入的数组和增量序列String arrayInput = scanner.nextLine();String gapsInput = scanner.nextLine();// 解析输入为整数数组int[] array = parseInput(arrayInput);int[] gaps = parseInput(gapsInput);// 计算并输出移动次数System.out.println(countMoves(array, gaps));scanner.close();}// 解析输入字符串为整数数组private static int[] parseInput(String input) {// 去除方括号并分割元素String content = input.substring(1, input.length() - 1);String[] elements = content.split(",\\s*");int[] result = new int[elements.length];for (int i = 0; i < elements.length; i++) {result[i] = Integer.parseInt(elements[i]);}return result;}// 统计希尔排序过程中元素向后移动的次数private static int countMoves(int[] array, int[] gaps) {// 创建数组副本，避免修改原数组int[] arr = array.clone();int moveCount = 0;// 遍历每个增量for (int gap : gaps) {// 对每个子序列执行插入排序for (int i = gap; i < arr.length; i++) {int temp = arr[i]; // 保存当前待插入元素int j = i;// 将比temp大的元素向后移动while (j >= gap && arr[j - gap] > temp) {arr[j] = arr[j - gap]; // 元素后移一个位置moveCount++; // 移动次数加1j -= gap;}// 将temp插入到正确位置arr[j] = temp;}}return moveCount;}
}

3.数字计数

给定一个正整数n，求在[1, n]中的所有整数中，每个数字字符(digit)各出现了多少次。

数值范围：1<n<2^31

补充说明

输出顺序为0到9，中间用空格分隔。

输入

20

**输出
**
“2 12 3 2 2 2 2 2 2 2”

题解：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();scanner.close();// 存储0-9每个数字出现的次数long[] counts = new long[10];// 按位处理，base表示当前处理的位数（个位、十位、百位等）for (long base = 1; base <= n; base *= 10) {long divisor = base * 10; // 用于提取高位的除数long higher = n / divisor; // 当前位左边的高位数字long current = (n / base) % 10; // 当前位的数字long lower = n % base; // 当前位右边的低位数字// 计算每个数字在当前位出现的次数for (int d = 0; d < 10; d++) {if (d == 0) {// 处理0的特殊情况（避免计算前导0）if (higher == 0) {continue; // 高位为0时，当前位的0属于前导0，不计数}if (current > d) {counts[d] += higher * base;} else {counts[d] += (higher - 1) * base + lower + 1;}} else {// 处理1-9的情况if (d < current) {counts[d] += (higher + 1) * base;} else if (d == current) {counts[d] += higher * base + lower + 1;} else {counts[d] += higher * base;}}}}// 拼接结果并输出StringBuilder result = new StringBuilder();for (int i = 0; i < 10; i++) {if (i > 0) {result.append(" ");}result.append(counts[i]);}System.out.println(result);}
}

4.单词搜索

给定一个二维数组(map)和给出多个字符串(strArr)，判断哪些字符串可以一个字母出发，通过向上下左右移动，使走过的路径构成这个符串，要求一次出发每个位置的字母不能够走第二次。

补充说明

1. map行列数均小于10

2. strArr长度小于10

演示：

map:[
[‘a’, ‘b’, ‘c’],
[‘f’, ‘e’, ‘d’],
['g, ‘n’, ‘m’],
],
strArr: [‘fed’, ‘fam’, ‘bca’]

返回值:

[true, false, false]

输入

[[“a”, “b”, “c”], [“f”, “e”, “d”], [“g”, “n”, “m”]],
[“fed”, “fam”, “bca”]

输出

[true, false, false]

题解

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);// 读取输入并解析为二维数组和字符串数组List<String> inputLines = new ArrayList<>();while (scanner.hasNextLine()) {String line = scanner.nextLine().trim();if (!line.isEmpty()) {inputLines.add(line);}}scanner.close();// 解析二维数组int gridLines = inputLines.size() - 1;char[][] grid = new char[gridLines][];for (int i = 0; i < gridLines; i++) {String line = inputLines.get(i);// 提取字符并去除引号和逗号String[] elements = line.replaceAll("[\\[\\]\"]", "").split(",\\s*");grid[i] = new char[elements.length];for (int j = 0; j < elements.length; j++) {grid[i][j] = elements[j].charAt(0);}}// 解析字符串数组String lastLine = inputLines.get(inputLines.size() - 1);String[] strArr = lastLine.replaceAll("[\\[\\]\"]", "").split(",\\s*");// 处理每个字符串并输出结果boolean[] results = solveWordSearch(grid, strArr);System.out.print("[");for (int i = 0; i < results.length; i++) {System.out.print(results[i]);if (i < results.length - 1) {System.out.print(", ");}}System.out.println("]");}/*** 处理单词搜索问题* @param grid 二维字符数组* @param strArr 待搜索的字符串数组* @return 每个字符串是否能被找到的布尔数组*/private static boolean[] solveWordSearch(char[][] grid, String[] strArr) {boolean[] results = new boolean[strArr.length];if (grid == null || grid.length == 0 || grid[0].length == 0) {return results;}int rows = grid.length;int cols = grid[0].length;for (int i = 0; i < strArr.length; i++) {String word = strArr[i];boolean found = false;// 尝试从每个位置开始搜索for (int row = 0; row < rows && !found; row++) {for (int col = 0; col < cols && !found; col++) {// 如果找到匹配的第一个字符，开始深度优先搜索if (grid[row][col] == word.charAt(0)) {boolean[][] visited = new boolean[rows][cols];if (dfs(grid, word, 0, row, col, visited)) {found = true;}}}}results[i] = found;}return results;}/*** 深度优先搜索* @param grid 二维字符数组* @param word 要搜索的单词* @param index 当前搜索到的单词索引* @param row 当前所在行* @param col 当前所在列* @param visited 记录已访问位置的数组* @return 是否找到匹配的路径*/private static boolean dfs(char[][] grid, String word, int index,int row, int col, boolean[][] visited) {// 如果已经匹配到单词的最后一个字符，返回trueif (index == word.length()) {return true;}int rows = grid.length;int cols = grid[0].length;// 检查当前位置是否越界、已访问或不匹配if (row < 0 || row >= rows || col < 0 || col >= cols ||visited[row][col] || grid[row][col] != word.charAt(index)) {return false;}// 标记当前位置为已访问visited[row][col] = true;// 尝试上下左右四个方向int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};for (int[] dir : directions) {int newRow = row + dir[0];int newCol = col + dir[1];if (dfs(grid, word, index + 1, newRow, newCol, visited)) {return true;}}// 回溯：如果所有方向都找不到匹配，取消当前位置的访问标记visited[row][col] = false;return false;}
}