leecodecode【动态规划2】【2026.6.7打卡-java版本】

LCR 102. 目标和

要点：0.1背包

f[i+1][c] = f[i][c] + f[i][c-nums[i]];

class Solution { public int findTargetSumWays(int[] nums, int target) { //dp[n][target] //p //sum - p //p -(sum-p)=target // p = sum+target/2 for(int i = 0; i < nums.length; i++){ target += nums[i]; } if(target < 0 || target %2 == 1){ return 0; } target = target/2; int n = nums.length; int[][] f = new int[n+1][target+1]; f[0][0] =1; for(int i = 0; i < n; i++){ for(int c = 0; c <= target; c++){ if(c < nums[i] ){ f[i+1][c] = f[i][c]; }else{ f[i+1][c] = f[i][c] + f[i][c-nums[i]]; } } } return f[n][target]; } }

零钱兑换

要点：完全背包

f[i+1][c] = Math.min(f[i][c], f[i+1][c-coins[i]] +1);

class Solution { public int coinChange(int[] coins, int amount) { int n = coins.length; int[][] f = new int[n+1][amount+1]; Arrays.fill(f[0],Integer.MAX_VALUE/2); f[0][0] = 0; for(int i = 0; i < n; i++){ for(int c = 0; c <= amount; c++){ if(c < coins[i]){ f[i+1][c] = f[i][c]; }else{ f[i+1][c] = Math.min(f[i][c], f[i+1][c-coins[i]] +1); } } } int ans = f[n][amount]; return ans < Integer.MAX_VALUE/2 ? ans : -1; } }

随机知识

五、缓存与数据库一致性（高频）

更新数据时，先删缓存还是先更新数据库？如何保证最终一致性？

面试官为什么这么问？
这是工程上极易踩坑的地方。我要看你有没有考虑过并发下的操作顺序问题，以及是否知道经典的解决方案。

希望听到怎样的回答：

• 错误操作：先删缓存，再更新 DB。在并发时，删除后、DB 更新前，别的请求会把旧数据再写回缓存，导致脏数据。
• 推荐：先更新 DB，再删缓存。虽然可能短时不一致（更新后、删除前有请求读到旧缓存），但最终会被删除纠正。
• 最终一致性兜底：
  • 延时双删：先删缓存，更新 DB，休眠一小段时间，再删一次。
  • 订阅数据库 binlog（如阿里 Canal），解析 binlog 异步更新缓存。
  • 设置缓存过期时间，作为兜底，即使出现脏数据也会过期刷新。
• 记得说出：“我们项目对题目点赞数这类更新不频繁的数据，更新 DB 后主动删除缓存，并给缓存设置一个短的过期时间。”

候选人：
好的。这是工程上非常容易踩坑的地方，我按错误方案、推荐方案和最终一致性兜底方案三个层次来讲。

第一，错误方案：先删缓存，再更新数据库。

这个顺序在并发场景下会出严重问题。

假设缓存里原来存着 name = "张三"，现在要更新成 name = "李四"。先删缓存成功，然后去更新数据库。就在删除缓存之后、数据库更新完成之前这个空窗期，另一个读请求进来了。它发现缓存为空，去数据库查，此时数据库还没更新，读到的是旧值 name = "张三"。读请求把这个旧值写入缓存。

最终结果：数据库里是 "李四"（新值），但缓存里是 "张三"（旧值）。缓存一直保存着脏数据，直到下一次缓存过期或被手动删除才会纠正。这个不一致窗口可能非常长。

所以绝大多数场景下，先删缓存再更新数据库是不可取的。

第二，推荐方案：先更新数据库，再删除缓存。

正确的顺序是：先更新数据库，更新成功后，再删除 Redis 里的对应缓存。

这个方案仍然有一个短暂的不一致窗口：数据库更新完成但缓存还没来得及删的一瞬间，如果有请求来读，它会读到缓存里的旧数据。但这个窗口极短——删缓存操作通常只需要几毫秒，而且在业务层面影响很小。一旦缓存删除成功，后续所有读请求都拿不到缓存，去数据库查，拿到新值并回写到缓存，一致性得到恢复。

这个方案唯一的风险是删除缓存失败。数据库更新成功了，但 Redis 网络抖动、重启等原因导致删缓存命令没执行或失败了，那这个 key 就永远保存着旧值，除非被自然过期淘汰。

解决删除失败有两种方式：

一是重试机制。删除缓存失败后，把删除任务发送到消息队列，由消费者异步不断重试，直到删除成功。这需要额外的 MQ 组件，但对业务代码入侵性较强。

二是订阅数据库 binlog。使用阿里 Canal 这样的中间件，伪装成 MySQL 的从库，接收 binlog 同步数据。Canal 解析 binlog 发现某张表的数据发生变化，触发下游服务自动删除对应的 Redis 缓存。这个方案完全解耦，业务代码不需要做任何额外处理，是更优雅的做法。

第三，最终一致性兜底方案。

除了上面说的实时删除，还要考虑缓存重建过程和极端异常下的数据修复。

延时双删：这是一种补偿性做法。先删除缓存，再更新数据库，然后等待几百毫秒（通常 500 毫秒到 1 秒），再执行一次缓存删除。第二次删除的目的是清除并发读请求在更新数据库后、延时期间可能写入缓存的旧值。

这个方案的优点是实现简单，缺点是延迟时间不好设定：太短可能删不掉并发请求还没来得及写完的旧缓存，太长会导致不一致窗口拉大。而且第二次删除也可能失败，还需要结合重试机制。

设置缓存过期时间：这是最后兜底手段。无论使用哪种方案，缓存的 key 都一定要设置过期时间。即使前面的删除逻辑都失败了，缓存也会在 TTL 到期后自动失效，最差情况下数据不一致的时间最多就是这个过期时长。这是一道任何人都不用担心的最终防线。

定期对账：高要求的系统（如金融、订单）还可以加一层定期对账任务，把核心数据对比数据库和缓存的内容，发现不一致就强制修复。这是最耗资源的兜底手段。

强一致性场景的特殊做法：如果业务确实需要数据即时一致，上述方案（都是最终一致性）就不适用了。需要调整架构：读请求不再直接走缓存，而是开启一个异步线程持续将数据库更新同步到缓存中，保证缓存数据是数据库的最新状态。这种方案成本高、架构复杂，只用在极核心的数据场景。

第四，项目中的实际选型。

项目里采用了先更新数据库，再删除缓存作为主流程。

同时做了三重保障：

• 缓存删除失败时，异步重试队列补偿删除。
• 所有缓存 key 都设置了过期时间，作为最后的兜底。
• 对于极高一致性要求的场景（如面试记录、支付状态），我们直接读数据库，绕过缓存，让 Redis 只承担非关键数据的读取加速职责。

总结一句话：更新数据时最安全的顺序是先更新数据库再删除缓存，短暂的不一致窗口极短可容忍；删除失败通过重试或 binlog 订阅补偿；所有缓存都要设过期时间做最后兜底；极度一致性要求的数据就绕开缓存直接读数据库。

分布式锁（中高频）

Redis 怎么实现分布式锁？用SET NX PX有什么要注意的？

面试官为什么这么问？
分布式锁是 Redis 最重要的工程应用之一。问这个要看你是否知道上锁、释放锁的原子性，以及可能出的问题。

希望听到怎样的回答：

• 基本命令：SET key value NX PX 30000（原子性地设置锁，带上所有者标识和超时时间）。
• 关键注意点：
  • 必须设置过期时间，防止死锁。
  • value 用唯一标识（如 UUID），释放锁时必须判断是自己的锁，用Lua 脚本保证GET + DEL原子性。
  • 锁续期：如果业务执行时间超过锁过期时间，需要一个看门狗机制自动续期（Redisson 已实现）。
• Redlock 争议：多个独立 Redis 实例过半成功才视为加锁，但存在时钟跳跃、GC 停顿等安全问题，实际很少用。
• 结合项目：“我们面试 Agent 在生成Token 时段用 Redis 锁控制对同一用户面试记录的并发修改，用 UUID 作锁值，Lua 脚本安全释放

候选人：
好的。分布式锁是保证多实例服务下共享资源互斥访问的核心手段，Redis 实现分布式锁是最常见的方案。我从基础实现、关键注意事项、锁续期和项目实践几个层面来回答。

第一，基础实现：SET key value NX PX 30000。

早期用SETNX+EXPIRE两步操作，但这两步不是原子的，可能在执行完SETNX后 Redis 宕机，导致锁永远不释放。Redis 2.6.12 之后，SET命令支持了NX和PX选项，一条命令原子性地完成“设置 key + 加过期时间”。

NX表示只有当 key 不存在时才设置成功，这是互斥的核心。PX 30000表示这个 key 会在 30000 毫秒后自动过期，即使持有锁的客户端崩溃，锁也能被自动释放，防止死锁。

value 一般设置为一个唯一标识，比如UUID + 线程ID，用来识别锁的持有者。释放锁时需要检查是不是自己的锁，防止误删别人的锁。

第二，关键注意点：释放锁必须原子性。

释放锁不能简单用DEL命令，因为需要先验证锁是不是自己的，再删除。这两步分开执行会有并发问题：客户端 A 执行GET发现锁是自己的，然后因为网络延迟或 GC 停顿，锁恰好在此时过期被释放；客户端 B 拿到了锁，客户端 A 继续执行DEL，就会把 B 的锁误删。

解决方案是用 Lua 脚本保证 GET + DEL 的原子性。Lua 脚本在 Redis 执行时是单线程原语，整个脚本不会被中断。逻辑是：if redis.call("GET", key) == ARGV[1] then return redis.call("DEL", key) else return 0 end。如果当前锁的值等于传入的唯一标识才删除，否则不删除。这样释放锁就是原子操作，不会误删。

另外必须设置过期时间，防止业务崩溃后锁永不释放。过期时间要结合业务执行时间设置合理值，一般设成最大业务执行时间的 1.5~2 倍。

第三，锁续期：看门狗机制。

如果业务执行时间超过了锁的过期时间（比如 GC 停顿、下游依赖慢），锁会被自动释放，另一个线程就能拿到锁，造成并发执行问题。

Redisson 这样的库实现了看门狗（Watch Dog）机制。Redisson 的分布式锁默认租约时间是 30 秒，加锁后会启动一个后台定时任务，每 10 秒检查一下锁是不是还被当前线程持有，如果是就自动续约，把过期时间重置为 30 秒。业务执行完主动释放锁，看门狗也停止续期。这样彻底解决了业务执行时间不确定的问题。如果应用崩溃，看门狗停止续期，锁在 30 秒后自动释放，避免死锁。

第四，Redlock 争议。

Redis 单节点存在单点故障风险。主从架构下，主机挂掉后，如果从机还没同步到锁数据就切换成新主机，两个客户端可能同时获得同一把锁。

Redis 作者提出了Redlock 算法：在 N 个完全独立的 Redis 节点（通常是 5 个）上依次尝试加锁，各节点不互通且不使用主从复制。如果客户端在 N/2+1 个节点（即大多数，比如 5 个中的 3 个）上成功加锁，且总耗时小于锁的有效时间，才算加锁成功。释放锁时向所有节点广播释放。

但 Redlock 受到很多质疑。分布式专家 Martin Kleppmann 指出，GC 停顿可能导致锁过期后客户端仍然认为自己持有锁，造成安全性问题；时钟跳跃也可能让锁提前过期。Redis 作者 Antirez 也承认这些问题的存在，并指出全系统同步时钟的成本和复杂度远超其收益。

因此业界主流不推荐使用 Redlock。如果需要强一致的分布式锁，应该使用 ZooKeeper 或 etcd（基于 Raft 共识协议）来保证节点间强一致。如果只是需要高性能、可容忍极小概率锁失效的业务（如防重复点击、限制任务执行频率），用 Redis 单节点或哨兵 + 续期足够。

第五，项目中的实际使用。

项目里使用了 Redis 分布式锁控制同一用户面试记录的并发修改。用户在前端触发面试生成后，可能因为网络延迟重复点击，或者多个 Tab 同时发起请求。我们用SET userId-lock threadId NX EX 10加锁：如果加锁失败，说明已有请求在处理，直接返回“正在生成中，请稍后刷新”；加锁成功则执行生成逻辑，执行完后用 Lua 脚本原子性释放锁。10 秒过期足够完成生成，即使服务中断锁也自释放，不阻塞用户后续请求。对于需要执行较长时间的异步任务，我们使用了 Redisson 的 RLock 并启用了看门狗机制。

碎碎念：后续会更新每天学习的八股和算法 题，开始准备秋招的第28天。努力连续更新100天！以后每天就按，秋招项目【java+agent 】，科研，必做项目，算法，八股，锻炼身体来总结。

今天又没学习，就晚上补了点算法。哎，一放假自己就是不会在学习了。