YY's blog

从海洋到陆地：如何找到流向两大洋的雨水路径？🌊🌧️问题背景：当雨水遇见两大洋想象这样一个场景：一个美丽的矩形岛屿被太平洋和大西洋环绕。太平洋守护在岛屿的左边界和上边界，而大西洋则拥抱岛屿的右边界和下边界。岛上的雨水会从高处流向低处，最终汇入海洋。 现在，我们需要找出岛上哪些位置的雨水能够同时流向太平洋和大西洋。这不仅是一个有趣的现实问题，更是一个经典的算法挑战！ 问题形式化给定一个 m × n 的网格 heights，其中： heights[r][c] 表示坐标 (r, c) 处的高度 雨水可以从一个单元格流向相邻的四个方向（上、下、左、右） 流动条件：相邻单元格的高度 ≤ 当前单元格的高度 靠近海洋的单元格可以直接流入海洋 我们需要返回所有既能流向太平洋又能流向大西洋的单元格坐标。 解决思路：逆向思维的力量 💡最直观的想法可能是对每个单元格检查是否能同时到达两个海洋，但这样效率太低。我们采用更聪明的逆向思维： 与其从山顶找海洋，不如从海洋找山顶！ 标记太平洋可达区域：从所有太平洋边界点出发，逆向寻找所有能流入太平洋的单元格 标记大西洋可达区域：从所有大西洋边界点出发，逆向 ...

🌊 问题描述给定一个 m x n 的二维矩阵 heightMap，其中每个元素表示该位置的高度。计算下雨后这个地形能够捕获多少雨水。 示例： 1234567输入：heightMap = [ [1,4,3,1,3,2], [3,2,1,3,2,4], [2,3,3,2,3,1]]输出：4解释：下雨后，雨水被捕获在两个低洼区域，总容量为4。 🔑 核心思路：从边界向内收缩的木桶原理直观理解想象这个二维矩阵是一个盆地，雨水会从四周边界流出。只有当四周有足够高的”围墙”时，雨水才能被积攒在内部。 这就像是一个二维的木桶效应：一个位置的积水高度取决于它到边界的所有路径中，路径上最高点的最小值。 关键洞察 边界决定论：只有边界上的单元格不会积水（水会流出） 最小最大值原理：内部单元格的积水高度由从边界到该单元格的所有路径中，路径上最大高度的最小值决定 🧠 算法详解：优先队列+BFS📊 初始化阶段12345678910// 处理特殊情况if (heightMap.length <= 2 || heightMap[0].length <= 2) { retu ...

方法思路本题可以通过动态规划来解决，其思路类似于背包问题中的选择与不选择当前物品的决策。每个问题可以选择解决或不解决，解决当前问题会获得分数，但必须跳过后续若干个问题。我们需要通过动态规划来记录每个位置的最大分数，从而得到最终结果。 类比背包问题在背包问题中，每个物品可以选择拿或不拿，拿的话会占用一定容量并获得价值。这里的问题类似，每个问题可以选择解决或不解决，解决的话会获得分数，但必须跳过后续若干个问题，相当于占用了后续的位置。因此，我们可以将每个问题视为一个物品，其价值为对应的分数，而选择该物品会影响后续物品的选择。 解决思路 状态定义：定义 f[i] 表示处理到第 i 个问题时的最大分数。 状态转移： 不解决当前问题：此时最大分数直接传递到下一个问题，即 f[i+1] = max(f[i+1], f[i])。 解决当前问题：获得当前问题的分数，并跳过后续若干个问题，更新对应位置的最大分数。具体来说，解决第 i 个问题后，下一个可处理的问题位置为 j = i + brainpower + 1，这里需要确保 j 不超过总问题数 n。然后更新 f[j] = max(f[j], f[i] ...

字符串匹配命中率计算题目链接2278.字母在字符串中的百分比 思路 将字符串转换为字符数组进行逐个匹配 统计命中次数，最终计算命中率（命中次数 / 总长度） 解题过程 使用String类型接收输入字符串 转换为字符数组进行遍历匹配 涉及包：java.lang（自动导入，无需显式声明） 复杂度分析 时间复杂度：$O(n)$线性遍历字符串一次 空间复杂度：$O(n)$需要创建字符数组存储空间 优化方案空间复杂度优化 使用charAt()方法替代字符数组转换 优化后空间复杂度：$O(1)$直接访问字符串中的字符，无需额外存储空间 代码实现1234567891011class Solution { public int percentageLetter(String s, char letter) { int count = 0; for (char a : s.toCharArray()) { if (a == letter) { count++; ...

分布式数据库

省流：读了两天代码+理解/制作需求

省流：社恐+看内部工具晕头转向的一天

SQL 关键字:JOINS进行多表联合查询

SQL 关键字:SELECT WHERE ORDER LIMIT LIKE IN