全排列

要点：dfs（i，ans，path， onpath【boolean标记】，nums）

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        //i，ans，path ， onpath， nums
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean[] onPath = new boolean[n];

        dfs(0,ans, path, onPath, nums);

        return ans;        
    }

    public void dfs(int i, List<List<Integer>> ans, List<Integer> path, boolean[] onPath, int[] nums){
        if(i == nums.length){
            ans.add(new ArrayList<>(path));
            return;
        }


        for(int j = 0; j<nums.length; j++){
            if(!onPath[j]){
                onPath[j] = true;
                path.add(nums[j]);
                dfs(i+1,ans, path, onPath,nums);
                path.removeLast();
                onPath[j] = false;
            }

        }
    } 
}

N 皇后

要点：就是排列的基础上+三个判断条件，int path【】，就是表示path的第i行path【i】 = j列的位置放皇后，就是0到n-1，选不同排序

class Solution {
    public List<List<String>> solveNQueens(int n) {
        //i,ans,path,col,duijiao1, duijiao2,n

        List<List<String>> 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,List<List<String>> anss, int[] path, boolean[] lie, boolean[] duijiao1, 
    boolean[] duijiao2, int n){

        if(hang == n){
            List<String> 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[hang+j] && !duijiao2[duijiao2ans] ){
                path[hang] = j;
                lie[j]=duijiao1[hang+j]=duijiao2[duijiao2ans] = true;
                dfs(hang+1,anss, path, lie, duijiao1, duijiao2,n);
                lie[j]=duijiao1[hang+j]=duijiao2[duijiao2ans] = false;

            
            }
        }
    }
}

打家劫舍

要点：的动态规划公式，dp【i】 = max（dp【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 淘汰最近最少使用的 key；lfu 淘汰最近最少访问频率的 key；random 随机淘汰；ttl 淘汰剩余过期时间最短的 key；noeviction 默认策略，不淘汰，直接返回写入失败。

对于缓存场景，最常用的是 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天！以后每天就按，秋招项目【java+agent】，科研，必做项目，算法，八股，锻炼身体来总结。

今天休息，玩了一天，就晚上补了点算法。2h学习