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

LCR 102. 目标和要点0.1背包f[i1][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 sumtarget/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[n1][target1]; f[0][0] 1; for(int i 0; i n; i){ for(int c 0; c target; c){ if(c nums[i] ){ f[i1][c] f[i][c]; }else{ f[i1][c] f[i][c] f[i][c-nums[i]]; } } } return f[n][target]; } }零钱兑换要点完全背包f[i1][c] Math.min(f[i][c], f[i1][c-coins[i]] 1);class Solution { public int coinChange(int[] coins, int amount) { int n coins.length; int[][] f new int[n1][amount1]; 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[i1][c] f[i][c]; }else{ f[i1][c] Math.min(f[i][c], f[i1][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。早期用SETNXEXPIRE两步操作但这两步不是原子的可能在执行完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/21 个节点即大多数比如 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天以后每天就按秋招项目【javaagent 】科研必做项目算法八股锻炼身体来总结。今天又没学习就晚上补了点算法。哎一放假自己就是不会在学习了。