西山居校招笔试编程题

题 1

import java.util.Scanner;

public class Fibonacci {
    // 方法：计算斐波那契数列的第n项
    public static int fibonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        }
        
        // 从2开始，利用两个变量存储前两项
        int a = 0, b = 1, result = 0;
        for (int i = 2; i <= n; i++) {
            result = a + b;
            a = b;
            b = result;
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入n: ");
        int n = scanner.nextInt();
        System.out.println("斐波那契数列的第" + n + "项是: " + fibonacci(n));
        scanner.close();
    }
}

题 2

题目描述

现有一个由 0（海洋）、1（陆地）、2（有敌军的陆地）构成的二维网格，请计算没有敌军驻扎的岛屿数量。岛屿总是被水包围，每座岛屿只能由水平方向或垂直方向上相邻的陆地连接而成。二维网格的四条边均被水包围。

函数定义：

输入：一个二维数组 grid，表示地图。
输出：返回没有敌军驻扎的岛屿数量。

规则：

数组中的 0 代表海洋，1 代表没有敌军的陆地，2 代表有敌军的陆地。
只能统计没有敌军的岛屿，数值为 1 的连续区域构成的岛屿。
数组没有覆盖到的地方认为是海水。

示例

示例 1：

输入：

[
  [1, 1, 1, 0],
  [1, 0, 1, 0],
  [0, 1, 0, 1],
  [0, 1, 0, 0]
]

输出：`3```

解释：输入二维数组，计算出没有敌军岛屿数量，数组没有覆盖到的地方认为是海水。

示例 2：

输入：

[
  [0, 1, 1, 0],
  [2, 1, 1, 0],
  [1, 0, 0, 1],
  [0, 1, 1, 1]
]

输出：`1```

解释：计算二维数组中没有敌军的岛屿数量，敌军驻扎的地方（值为 2）不能计入岛屿。

思路分析

可以使用 深度优先搜索（DFS） 或 广度优先搜索（BFS） 来查找岛屿的数量。
每当遇到 1 时，启动 DFS 或 BFS，递归遍历所有与之相邻的 1，并标记为已经访问过，统计岛屿的个数。

public class IslandCounter {
    private boolean[][] visited;
    private int rows;
    private int cols;
    private int count = 0;
    private boolean enemyFound;

    public int countIslands(int[][] grid) {
        if (grid == null || grid.length == 0) return 0;

        rows = grid.length;
        cols = grid[0].length;
        visited = new boolean[rows][cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++)
                if (!visited[i][j] && grid[i][j] != 0) {
                    enemyFound = false;
                    dfs(grid, i, j);
                    if (!enemyFound) {
                        count++;
                    }
                }
        }
        return count;
    }

    private void dfs(int[][] grid, int i, int j) {
        // 边界条件
        if (i < 0 || i >= rows || j < 0 || j >= cols) return;
        if (visited[i][j] || grid[i][j] == 0) return;

        // 标记为已访问
        visited[i][j] = true;

        // 检查是否有敌军
        if (grid[i][j] == 2) {
            enemyFound = true;
        }

        // 递归访问相邻单元格
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }

    // 测试函数，可以使用示例输入来测试
    public static void main(String[] args) {
        IslandCounter ic = new IslandCounter();

        int[][] grid1 = {
            {1, 1, 1, 0},
            {1, 0, 1, 0},
            {0, 1, 0, 1},
            {0, 1, 0, 0}
        };
        System.out.println(ic.countIslands(grid1)); // 输出：3

        // 重置计数器和访问数组以供下一次测试
        ic = new IslandCounter();
        int[][] grid2 = {
            {0, 1, 1, 0},
            {2, 1, 1, 0},
            {1, 0, 0, 1},
            {0, 1, 1, 1}
        };
        System.out.println(ic.countIslands(grid2)); // 输出：1
    }
}

题 3

题目描述

实现一个简单的网络协议编解码器，从标准输入中得到模拟的网络字节流，对其进行解码并输出解析后的内容。协议规范如下：

字节流前两字节为常量，我们设置为 "SS"。
接下来的 2 个字节为协议的长度（unsigned short）。
接着是 2 个字节为协议号（unsigned short）。
最后为消息体的长度。为了便于输出，这里我们使用的是不带结束符的字符串表示消息体。

例子：

如图所示：

字节流的前两个字节为常量，我们设置为“SS”。
接下来的 2 个字节为协议的长度（unsigned short）。
接着是 2 个字节为协议号（unsigned short）。
最后为消息体的长度。为了便于输出，我们这里使用的是不带结束符的字符串表示消息体。

示例

输入示例：

16 进制表示的字节流，16 进制的字母使用小写表示，如：

53530e00420048656c6c6f2053656153756e

输出示例：

解码后的消息体内容，输出协议号和消息体，协议号和消息体用空格隔开，如上所示的例子输出为：

66 Hello SeaSun

解析：

输入字节流：53530e00420048656c6c6f2053656153756e
- 前 2 字节：5353（常量 "SS"）
- 长度：0e00（协议总长度 14）
- 协议号：4200（协议号为 66）
- 消息体：Hello SeaSun

示例

输入示例：

16 进制表示的字节流，16 进制的字母使用小写表示，如：

53530e00420048656c6c6f2053656153756e53531300580057656c636f6d6520746f205a6875486169

输出示例：

解码后的消息体内容，输出协议号和消息体，协议号和消息体用空格隔开，如上所示的例子输出为：

66 Hello SeaSun
88 Welcome to ZhuHai

示例

输入示例：

16 进制表示的字节流，16 进制的字母使用小写表示，如：

53530e00420048656c6c6f2053656153756e53531300580057656c636f6d6520746f205a687548616953530b007b00476f6f64206c75636b53530f00

输出示例：

解码后的消息体内容，输出协议号和消息体，协议号和消息体用空格隔开，如上所示的例子输出为：

66 Hello SeaSun
88 Welcome to ZhuHai
123 Good luck

import java.util.*;

public class Mainxs3 {
    public static void main(String[] args) {
        // 读取输入的十六进制字符串
        Scanner scanner = new Scanner(System.in);
        String hexString = scanner.nextLine();
        // 将十六进制字符串转换为字节数组
        byte[] bytes = hexStringToByteArray(hexString);

        int index = 0;
        while (index + 5 < bytes.length) { // 至少需要 6 个字节才能解析一个包
            // 检查前两个字节是否为常量 "SS"
            if (bytes[index] != 0x53 || bytes[index + 1] != 0x53) {
                // 非法包，跳过或结束
                break;
            }
            index += 2;
            // 读取长度字段（2 字节，little-endian）
            if (index + 1 >= bytes.length) break; // 防止越界
            int length = (bytes[index] & 0xFF) | ((bytes[index + 1] & 0xFF) << 8);
            index += 2;
            // 检查剩余数据是否足够
            if (index + length > bytes.length) break;
            // 读取协议号（2 字节，little-endian）
            int protocolNumber = (bytes[index] & 0xFF) | ((bytes[index + 1] & 0xFF) << 8);
            index += 2;
            // 计算消息体长度
            int messageLength = length - 2; // 减去协议号占用的 2 字节
            // 读取消息体
            byte[] messageBytes = Arrays.copyOfRange(bytes, index, index + messageLength);
            index += messageLength;
            // 将消息体转换为字符串
            String message = new String(messageBytes);
            // 输出协议号和消息体
            System.out.println(protocolNumber + " " + message);
        }
    }

    // 将十六进制字符串转换为字节数组的辅助方法
    private static byte[] hexStringToByteArray(String s) {
        int len = s.length();
        byte[] data = new byte[len / 2];
        // 每两个十六进制字符转换为一个字节
        for (int i = 0; i < len; i += 2) {
            // 将十六进制字符转换为字节
            data[i / 2] = (byte) ((Character.digit(s.charAt(i), 16) << 4)
                                 + Character.digit(s.charAt(i+1), 16));
        }
        return data;
    }
}