全排列要点dfsianspath onpath【boolean标记】numsclass Solution { public ListListInteger permute(int[] nums) { //ianspath onpath nums int n nums.length; ListListInteger ans new ArrayList(); ListInteger path new ArrayList(); boolean[] onPath new boolean[n]; dfs(0,ans, path, onPath, nums); return ans; } public void dfs(int i, ListListInteger ans, ListInteger path, boolean[] onPath, int[] nums){ if(i nums.length){ ans.add(new ArrayList(path)); return; } for(int j 0; jnums.length; j){ if(!onPath[j]){ onPath[j] true; path.add(nums[j]); dfs(i1,ans, path, onPath,nums); path.removeLast(); onPath[j] false; } } } }N 皇后要点就是排列的基础上三个判断条件int path【】就是表示path的第i行path【i】 j列的位置放皇后就是0到n-1选不同排序class Solution { public ListListString solveNQueens(int n) { //i,ans,path,col,duijiao1, duijiao2,n ListListString anss new ArrayList(); int[] path new int[n];//皇后放在r,path[r] boolean[] lie new boolean[n]; boolean[] duijiao1 new boolean[2*n -1]; boolean[] duijiao2 new boolean[2*n -1]; dfs(0,anss,path,lie,duijiao1, duijiao2,n); return anss; } public void dfs(int hang,ListListString anss, int[] path, boolean[] lie, boolean[] duijiao1, boolean[] duijiao2, int n){ if(hang n){ ListString ans new ArrayList(n); for(int c : path){ char[] ans_hang new char[n]; Arrays.fill(ans_hang,.); ans_hang[c] Q; ans.add(new String(ans_hang)); } anss.add(ans); return; } for(int j 0; j n; j){ int duijiao2ans hang - j n-1;//[行数-列数 【n-1】不能负数] if(!lie[j] !duijiao1[hangj] !duijiao2[duijiao2ans] ){ path[hang] j; lie[j]duijiao1[hangj]duijiao2[duijiao2ans] true; dfs(hang1,anss, path, lie, duijiao1, duijiao2,n); lie[j]duijiao1[hangj]duijiao2[duijiao2ans] false; } } } }打家劫舍要点的动态规划公式dp【i】 maxdp【i-1】 dp【i-2】nums【i】class Solution { public int rob(int[] nums) { int n nums.length; if(n 1){ return nums[0]; } if(n 2){ return Math.max(nums[0],nums[1]); } int[] dp new int[n]; dp[0] nums[0]; dp[1] Math.max(nums[0],nums[1]); int max Math.max(dp[0], dp[1]); for(int i 2; i n; i){ dp[i] Math.max(dp[i-1], dp[i-2]nums[i]); max Math.max(dp[i], max); } return max; } }随机知识四、过期策略与内存淘汰中高频Redis 怎么清理过期的 key内存满了怎么办面试官为什么这么问这道题考的是你对 Redis 内存管理的理解线上 OOM 排查时很关键。你可能要说出惰性删除和定期删除两种策略的配合。希望听到怎样的回答过期键清除策略惰性删除访问 key 时才检查是否过期过期就删。优点对 CPU 友好。缺点内存不友好过期键可能不被访问而一直占内存。定期删除Redis 周期性扫描一批 key随机采样删除其中过期的。平衡 CPU 和内存。内存淘汰策略maxmemory 满时noeviction默认不淘汰写请求报错。allkeys-lru所有 key 里淘汰最近最少用的常用。volatile-lru过期键里淘汰最近最少用的。allkeys-random、volatile-ttl等。结合项目“我们用allkeys-lru因为希望热点题目缓存常驻内存淘汰冷门题目的缓存。”候选人好的。这两个问题分别对应 Redis 内存管理的两个层面过期键的删除方式和内存达到上限时的淘汰策略。它们组合在一起构成了 Redis 内存管理的核心。第一过期键的删除方式。Redis 给 key 设置了 TTL 过期时间到期后 key 逻辑上已经“失效”了但物理上它可能还在内存里。Redis 用两种策略配合来删除它们惰性删除和定期删除。惰性删除当客户端访问某个 key 时Redis 先检查这个 key 是否过期。如果过期了立刻删除然后返回空。这个策略对 CPU 最友好——只在访问时才检查不浪费额外算力。但问题是如果某个 key 过期后没人访问它它就永远占着内存变成“僵尸 key”。定期删除Redis 默认每秒执行 10 次定期删除任务。每次从设置了过期时间的 key 里随机抽取 20 个检查是否过期删掉过期的。如果抽到的 key 中超过 25% 都过期了说明过期 key 的密度较高就继续重复抽取清理直到过期比例低于 25% 或达到时间上限25 毫秒。这个上限非常重要防止定期删除占用 CPU 太长时间、阻塞正常命令处理。这两种策略互补配合定期删除批量清理已经过期但没人访问的 key防止它们无限堆积惰性删除拦截正在被访问的过期 key保证客户端不会读到脏数据。两种策略都不能保证过期 key 立刻被清理Redis 对 CPU 和内存的平衡就在这里。第二内存满了怎么办——内存淘汰策略。当 Redis 内存使用达到maxmemory上限时再写入数据会触发内存淘汰。Redis 提供了多种淘汰策略核心区别是“从哪些 key 里淘汰”和“按什么规则淘汰”。从淘汰范围看策略分两档volatile-*只从设置了过期时间的 key 里淘汰allkeys-*从所有 key 里淘汰。从淘汰规则看lru淘汰最近最少使用的 keylfu淘汰最近最少访问频率的 keyrandom随机淘汰ttl淘汰剩余过期时间最短的 keynoeviction默认策略不淘汰直接返回写入失败。对于缓存场景最常用的是allkeys-lru和allkeys-lfu。它们的区别在于LRU 只看 key 最近被访问的时间如果一个冷门 key 昨天被访问了一次今天可能被 LRU 标记为“最近被访问过”继续保留LFU 则统计 key 在一段时间内的被访问频率一次性的冷门访问不会让 key 赖在内存里。LFU 比 LRU 更“聪明”更适合有明显热点和冷门数据的场景。第三项目中的配置选择。项目里 Redis 使用的是allkeys-lfu。我们的面试题库的缓存中只有真正高频被考察的题目才值得一直占着内存偶尔被查一次的冷门题目就让它被 LFU 自然淘汰掉避免低频数据挤占高频热点内容。内存的利用更偏向于真正有价值的热点数据。同时实际部署中需要做好内存监控通过INFO memory查看内存使用率配置接近上限的告警。如果大量 key 同时过期导致瞬间淘汰压力过大可以在配置里禁止lazyfree-lazy-eviction开启异步淘汰——被淘汰的 key 可能会触发UNLINK而不是DEL释放内存的操作放在后台线程执行避免主线程在淘汰大 key 时阻塞。总结一句话过期 key 靠惰性删除和定期删除互补清理惰性删除保 CPU定期删除保内存内存满了靠maxmemory-policy淘汰缓存场景推荐用allkeys-lfu让热点数据常驻而冷门数据优先淘汰。碎碎念后续会更新每天学习的八股和算法 题开始准备秋招的第27天。努力连续更新100天以后每天就按秋招项目【javaagent】科研必做项目算法八股锻炼身体来总结。今天休息玩了一天就晚上补了点算法。2h学习