Vermoshの探索日志

分类导航

LeetCode 30 ~ ? 水题(并非)

作者：

Vermosh

在

25 – 09 – 30 (补于 25 – 10 – 06)

今日份题面

超市正在促销，你可以用 numExchange 个空水瓶从超市兑换一瓶水。最开始，你一共购入了 numBottles 瓶水。

如果喝掉了水瓶中的水，那么水瓶就会变成空的。

给你两个整数 numBottles 和 numExchange ，返回你 最多 可以喝到多少瓶水。

我能借一个吗(

模拟就行

class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        int res = 0;
        while(numBottles >= numExchange){
            res += numBottles / numExchange * numExchange;
            numBottles = numBottles / numExchange + numBottles % numExchange;
        }
        res += numBottles;
        return res;
    }
}

或者组合数学推导一下

class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        return numBottles + (numBottles - 1) / (numExchange - 1);
    }
}

25 – 10 – 01 (补于 25 – 10 – 07)

今日份题面

给你两个整数 numBottles 和 numExchange 。

numBottles 代表你最初拥有的满水瓶数量。在一次操作中，你可以执行以下操作之一：

  • 喝掉任意数量的满水瓶，使它们变成空水瓶。
  • 用 numExchange 个空水瓶交换一个满水瓶。然后，将 numExchange 的值增加 1 。

注意，你不能使用相同的 numExchange 值交换多批空水瓶。例如，如果 numBottles == 3 并且 numExchange == 1 ，则不能用 3 个空水瓶交换成 3 个满水瓶。

返回你 最多 可以喝到多少瓶水。

其实和昨天的差不多，模拟就行，注意每次换水后要求数 +1

class Solution {
    public int maxBottlesDrunk(int numBottles, int numExchange) {
        int res = numBottles;
        while(numBottles >= numExchange){
            numBottles -= numExchange;
            ++res;
            ++numBottles;
            ++numExchange;
        }
        return res;
    }
}

25 – 10 – 02

来了个大的，拉了托大的…

今日份题面

给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

有一说一我第一反应出栈入栈接雨水，仔细一看好嘛二维的

二维就不是用栈的思想了，因为栈顾得了前后顾不了左右。

考虑最小堆队列，当前排出的是低洼地，那么他周围如果都比他高就能存个差量。存在比他矮的就刷新到矮的上再重复当前判断。

注意初始化是有技巧的，我们需要从外围逐层向内扫。

class Solution {
    private static final int [][] DIRS = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
        
    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length, n = heightMap[0].length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(i ==0 || j == 0 || i == m - 1 || j == n - 1){
                    pq.add(new int []{heightMap[i][j], i, j});
                    heightMap[i][j] = -1;
                }
            }
        }

        int ans = 0;
        while(!pq.isEmpty()){
            int [] t = pq.poll();
            int minHeight = t[0], i = t[1], j = t[2];
            for(int [] d : DIRS){
                int x = i + d[0], y = j + d[1];
                    if (0 <= x && x < m && 0 <= y && y < n && heightMap[x][y] >= 0) { 
                    ans += Math.max(minHeight - heightMap[x][y], 0);
                    pq.add(new int[]{Math.max(minHeight, heightMap[x][y]), x, y});
                    heightMap[x][y] = -1;
                }
            }
        }     
        return ans;
    }
}

25 – 10 – 03

今日份题面

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

稀里糊涂做出了的属于是

class Solution {
    public int maxArea(int[] height) {
    int res = 0;
    int i = 0;
    int j = height.length - 1;
    while (i < j) {
        int area = (j - i) * Math.min(height[i], height[j]);
        res = Math.max(res, area);
        if (height[i] < height[j]) {
            i++;
        } else {
            j--;
        }
    }
    return res;
    }
}

看题解说是双指针，理解起来还是要一点思路的

此处双指针的意义在于：指针每一次移动，都意味着排除掉了一个柱子

我们需要看移动当前柱子的收益，具体来说，如果移动当前柱子后新的水面只会比当前还要低，那么移动显然是不明智的(因为宽度必然减小)，那么此时换侧考虑

如果都无法移动或者两个指针相遇，那么算法结束，此时储存的结果就是过程中的最大值吗，也就是全局最大值。

25 – 10 -04

啊，大海，你水真多(

今日份题面

有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r] 表示坐标 (r, c) 上单元格 高于海平面的高度 。

岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。

很很明显的一个搜索问题，从边界开始一路往中间走，走不通为止，最后扫一遍统计标记

遍历方式有两种：DFS 和 BFS

// BFS
class Solution {
    private static final int[][] DIRS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    private int m, n; // 网格的行数和列数

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        m = heights.length;
        n = heights[0].length;
        
        // 初始化两个布尔数组，分别记录能到达太平洋和大西洋的单元格
        boolean[][] pacificReachable = new boolean[m][n];
        boolean[][] atlanticReachable = new boolean[m][n];
        
        // 创建两个队列，分别用于太平洋和大西洋的BFS
        Queue<int[]> pacificQueue = new LinkedList<>();
        Queue<int[]> atlanticQueue = new LinkedList<>();
        
        // 将太平洋边界单元格加入队列并标记
        for (int i = 0; i < m; i++) {
            pacificQueue.offer(new int[]{i, 0});
            pacificReachable[i][0] = true;
        }
        for (int j = 0; j < n; j++) {
            pacificQueue.offer(new int[]{0, j});
            pacificReachable[0][j] = true;
        }
        
        // 将大西洋边界单元格加入队列并标记
        for (int i = 0; i < m; i++) {
            atlanticQueue.offer(new int[]{i, n - 1});
            atlanticReachable[i][n - 1] = true;
        }
        for (int j = 0; j < n; j++) {
            atlanticQueue.offer(new int[]{m - 1, j});
            atlanticReachable[m - 1][j] = true;
        }
        
        bfs(heights, pacificQueue, pacificReachable);
        
        bfs(heights, atlanticQueue, atlanticReachable);
        
        // 收集结果：同时能到达太平洋和大西洋的单元格
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacificReachable[i][j] && atlanticReachable[i][j]) {
                    res.add(Arrays.asList(i, j));
                }
            }
        }
        return res;
    }

    /**
     * BFS：从队列中的单元格开始，标记所有可以流向海洋的单元格
     * @param heights 高度矩阵
     * @param queue BFS队列
     * @param visited 访问标记数组（记录能到达的单元格）
     */
    private void bfs(int[][] heights, Queue<int[]> queue, boolean[][] visited) {
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int i = cell[0], j = cell[1];
            
            // 遍历四个方向
            for (int[] dir : DIRS) {
                int x = i + dir[0];
                int y = j + dir[1];
                
                // 检查新坐标是否在网格内、未被访问、且高度满足条件
                if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y] && heights[x][y] >= heights[i][j]) {
                    visited[x][y] = true;
                    queue.offer(new int[]{x, y});
                }
            }
        }
    }
}


// DFS
class Solution {
    private static final int[][] DIRS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    private int m, n; // 网格的行数和列数

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        m = heights.length;
        n = heights[0].length;
        
        // 初始化两个布尔数组，分别记录能到达太平洋和大西洋的单元格
        boolean[][] pacificReachable = new boolean[m][n];
        boolean[][] atlanticReachable = new boolean[m][n];
        
        // 从太平洋边界开始DFS：第一行和第一列
        for (int i = 0; i < m; i++) {
            dfs(heights, pacificReachable, i, 0); // 第一列
        }
        for (int j = 0; j < n; j++) {
            dfs(heights, pacificReachable, 0, j); // 第一行
        }
        
        // 从大西洋边界开始DFS：最后一行和最后一列
        for (int i = 0; i < m; i++) {
            dfs(heights, atlanticReachable, i, n - 1); // 最后一列
        }
        for (int j = 0; j < n; j++) {
            dfs(heights, atlanticReachable, m - 1, j); // 最后一行
        }
        
        // 收集结果：同时能到达太平洋和大西洋的单元格
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacificReachable[i][j] && atlanticReachable[i][j]) {
                    res.add(Arrays.asList(i, j)); // 使用Arrays.asList创建列表
                }
            }
        }
        return res;
    }

    /**
     * DFS辅助函数：从当前单元格开始，标记所有可以流向海洋的单元格
     * @param heights 高度矩阵
     * @param visited 访问标记数组（记录能到达的单元格）
     * @param i 当前行索引
     * @param j 当前列索引
     */
    private void dfs(int[][] heights, boolean[][] visited, int i, int j) {
        // 标记当前单元格为已访问（可到达）
        visited[i][j] = true;
        
        // 遍历四个方向
        for (int[] dir : DIRS) {
            int x = i + dir[0];
            int y = j + dir[1];
            
            // 检查新坐标是否在网格内、未被访问、且高度满足条件（水流可以从新坐标流向当前坐标）
            if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y] && heights[x][y] >= heights[i][j]) {
                dfs(heights, visited, x, y);
            }
        }
    }
}

25 – 10 – 05

今日份题面

在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。

当开始下雨时，在时间为 t 时，水池中的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。

你从坐标方格的左上平台 (0，0) 出发。返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间

一眼广搜，然后过程中优先往当前最小方向(最小堆)出发，取过程最大值即可

class Solution {
    private final int [][] DIRS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    private PriorityQueue <int []>curVisited = new PriorityQueue<>((a, b) -> (a[2] - b[2]));
    private boolean [][] visited;
    public int swimInWater(int[][] grid) {
        int reachTime = Integer.MIN_VALUE, m = grid.length, n = grid[0].length;
        visited = new boolean [m][n];
        curVisited.offer(new int []{0, 0, grid[0][0]});
        visited[0][0] = true;
        while(!curVisited.isEmpty()){
            int [] curPoint = curVisited.poll();
            reachTime = Math.max(reachTime, curPoint[2]);
            if(curPoint[0] == m - 1 && curPoint[1] == n - 1){
                break;
            }
            for(int [] dir:DIRS){
                int newi = curPoint[0] + dir[0];
                int newj = curPoint[1] + dir[1];
                if(newi < 0 || newi > m - 1 || newj < 0 || newj > n - 1 || visited[newi][newj]){
                    continue;
                }
                curVisited.add(new int []{newi, newj, grid[newi][newj]});
                visited[newi][newj] = true;
            }
        }
        return reachTime;
    }
}

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

更多文章