莉莉丝笔试题

5道填空一脸懵逼

编程题考了两个

第一题通过率没过50

public class MinOperationsToUnify {
    public static int minOperationsToUnify(String s) {
        int n = s.length();
        int count0 = 0;
        int count1 = 0;

        // 计算将所有字符变为0所需的最小次数
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) != s.charAt(i - 1)) {
                count0++;
            }
        }

        // 计算将所有字符变为1所需的最小次数
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                count1++;
            }
        }

        return Math.min(count0, count1);
    }

    public static void main(String[] args) {
        String s = "010101";
        System.out.println(minOperationsToUnify(s));  // 输出: 3
    }
}

1. 广度优先搜索（BFS）:我们使用广度优先搜索（BFS）来遍历二维字符数组。BFS 是一种图搜索算法，适用于寻找最短路径。我们使用一个队列来存储当前的搜索状态，包括当前位置、已经花费的时间以及是否有车。
2. 初始化:首先，我们找到起点 S 并将其加入队列，同时标记为已访问。初始化方向数组 dx 和 dy，用于表示四个可能的移动方向（上、下、左、右）。
3. 搜索过程:从队列中取出当前点，检查是否到达安全区 X。如果到达，则返回 true 和当前时间。否则，遍历四个可能的移动方向，计算新的位置和新的时间。如果新的位置在边界内且未被访问且不是阻塞区 O，则将其加入队列。如果当前点有车，则移动时间为 1 秒，否则为 2 秒。如果新的时间小于等于给定时间 t，则继续搜索。
4. 终止条件:如果队列为空且未找到安全区 X，则返回 false 和 -1。

/**
 * 功能描述
 * <p>
 * 成略在胸，良计速出
 *
 * @author SUN
 * @date 2024/08/22  0:36
 */
import java.util.*;

import java.util.*;

public class SafetyZone {
    static class Point {
        int x, y, time;
        boolean hasCar;

        Point(int x, int y, int time, boolean hasCar) {
            this.x = x;
            this.y = y;
            this.time = time;
            this.hasCar = hasCar;
        }
    }

    static class Result {
        boolean canReach;
        int time;

        Result(boolean canReach, int time) {
            this.canReach = canReach;
            this.time = time;
        }

        @Override
        public String toString() {
            return "Result{" +
                    "canReach=" + canReach +
                    ", time=" + time +
                    '}';
        }
    }

    public static Result canReachSafety(char[][] grid, int t) {
        int n = grid.length;
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        Queue<Point> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][n];

        // Find the starting point S
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'S') {
                    queue.add(new Point(i, j, 0, false));
                    visited[i][j] = true;
                    break;
                }
            }
        }

        while (!queue.isEmpty()) {
            Point p = queue.poll();

            // Check if we reached the safety zone X
            if (grid[p.x][p.y] == 'X') {
                return new Result(true, p.time);
            }

            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && !visited[nx][ny] && grid[nx][ny] != 'O') {
                    int newTime = p.time + (p.hasCar ? 1 : 2);
                    if (newTime <= t) {
                        visited[nx][ny] = true;
                        queue.add(new Point(nx, ny, newTime, p.hasCar || grid[nx][ny] == 'C'));
                    }
                }
            }
        }

        return new Result(false, -1);
    }

    public static void main(String[] args) {
        char[][] grid1 = {{'X', 'O'}, {'S', '.'}};
        char[][] grid2 = {{'O', 'X'}, {'S', '.'}};
        char[][] grid3 = {{'O', 'X'}, {'S', 'C'}};

        System.out.println(canReachSafety(grid1, 3));  // 输出: Result{canReach=true, time=2}
        System.out.println(canReachSafety(grid2, 3));  // 输出: Result{canReach=false, time=-1}
        System.out.println(canReachSafety(grid3, 3));  // 输出: Result{canReach=true, time=3}
    }
}