topcode【随机算法题】【2026.5.19打卡-java版本】

m0_56136663

487人浏览 · 2026-05-20 01:25:46

m0_56136663 · 2026-05-20 01:25:46 发布

编辑距离

要点：二维dp

class Solution {
    public int minDistance(String word1, String word2) {

        //二维数组
        int n = word1.length();
        int m = word2.length();

        int[][] dp = new int[n+1][m+1];

        for(int i = 0; i <= n; i++){
            dp[i][0] = i;
        }

        for(int j = 0; j <=m; j++){
            dp[0][j] = j;
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){

                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    int inser = dp[i-1][j] +1;
                    int replsce = dp[i][j-1] +1;
                    int delete = dp[i-1][j-1] +1;

                    dp[i][j] = Math.min(delete, Math.min(inser, replsce));
                }
            }
        }

        return dp[n][m];
        
    }
}

两两交换链表中的节点

要点：dummy + 临时空两个节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        //头节点
        ListNode dummy = new ListNode(0,head);

        ListNode curr = dummy;

        //while的循环条件不一样的
        while(curr.next != null && curr.next.next != null){

            ListNode list1 = curr.next;
            ListNode list2 = curr.next.next;

            curr.next = list2;
            list1.next = list2.next;
            list2.next = list1;
            curr = list1;
        }

        return dummy.next;

        
    }
}

最长公共子序列

要点：二维dp

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        //二维数组
        int n = text1.length();
        int m = text2.length();

        int[][] dp = new int[n+1][m+1];

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){

                if(text1.charAt(i-1) == text2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }

        return dp[n][m];
        
    }
}

路径总和

要点：用层次遍历，两个队列

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        //队列

        if(root == null){
            return false;
        }


        Deque<TreeNode> stack = new LinkedList<>();
        Deque<Integer> instack = new LinkedList<>();

        stack.offer(root);
        instack.offer(root.val);

        while(!stack.isEmpty()){
            int size = stack.size();


            for(int i = 0; i < size; i++){

                TreeNode temp = stack.poll();
                int intemp = instack.poll();

                if(temp.left ==null && temp.right == null){
                    if(intemp == targetSum){
                        return true;
                    }

                    continue;
                }

                if(temp.left != null){
                    stack.offer(temp.left);
                    instack.offer(temp.left.val +intemp);
                }

                if(temp.right != null){
                    stack.offer(temp.right);
                    instack.offer(temp.right.val + intemp);
                }
            }
        }

        return false;
    }
}

随机知识

一、基础数据结构（必问）

Redis 有哪几种基础数据类型？你分别用在什么场景？

面试官为什么这么问？
这题看似简单，但我要看你能不能用一句话概括每种类型的底层结构，并且用你的项目来举例。只会说“String 是 K-V，List 是列表”的，和能说出“用 ZSet 的跳表结构做排行榜”的，差距很大。

希望听到怎样的回答：

5 种基本类型 + 3 种扩展：
- String：底层简单动态字符串（SDS），二进制安全，可存数字、JSON 等。用于缓存、分布式锁、计数器。
- List：底层是双向链表或 ziplist，支持两端操作。用于消息队列、最新动态列表。
- Hash：底层是哈希表或 ziplist，存对象。用于存储对象属性（如用户信息）。
- Set：底层是哈希表，无序不重复。用于标签、共同好友、去重。
- ZSet：底层是跳表 + 哈希表，按分值排序。用于排行榜（这是亮点）。
- 高级：Bitmap（签到）、HyperLogLog（UV 统计）、Geospatial（附近的人）。
一定要关联自己的项目：比如“面经 Agent 里我们用 String 类型存储生成的面试脚本 JSON，用 ZSet 做高频考题排行榜，用 Hash 存用户的面试偏好配置”。

候选人：
好的。Redis 有五种基础数据类型和三种常用的高级类型。我从底层结构和项目中的实际使用场景两个角度来分别说清楚。

一、String

String 是 Redis 最基本也是最通用的类型。底层是 SDS（简单动态字符串），设计上比 C 语言的字符数组更安全高效：获取长度 O(1) 直接读字段而不是遍历；一次扩容留足空间，不需要每次拼接都重新分配；二进制安全，存什么字节都能完整存取原样返回。

使用场景非常多：

缓存 JSON：把查出来的 Java 对象序列化成 JSON 字符串存进去，下次直接返回，不走数据库。
分布式锁：SET key value NX EX 30，用 NX 保证只有一个线程能 set 成功，EX 设过期防止死锁。
计数器：INCR 原子自增，统计点赞数、阅读量、文章访问次数。

在我项目里，用 String 缓存生成的面试脚本 JSON。面试 Agent 生成反馈报告后，把报告 JSON 存到 Redis，用户刷新页面直接从缓存拿。还用它做简单的分布锁，防止同一个用户并发触发多个面试流程。

二、List

List 是双向链表结构，Redis 3.2 之后底层统一用 QuickList——一个双向链表，每个节点又是一个小的压缩列表，兼顾性能和内存。两端插入删除极快，中间访问慢。适合做先进先出或最新列表。

项目里用它记录用户的最近搜索关键词，LPUSH 压入新关键词，LTRIM 只保留最近 10 个，用户点击搜索框就自动展示历史记录，体验流畅。

三、Hash

Hash 的底层是压缩列表或哈希表，元素少时用压缩列表省内存，多了自动升级成哈希表。Key 是集合名字，Field 是成员名，Value 是成员值。最适合存储对象，而且每个字段可以单独读写，更新名字不用整体序列化。

项目里用它存用户面试偏好配置：难度、题量、方向分别存在一个 Hash 的不同字段里。修改难度只改对应 Field，不整体覆盖，比 String 灵活很多。

四、Set

Set 是无序不重复的集合，底层也是哈希表类型。自动去重，支持交并差集运算。

项目里用 Set 存面试题目的多维度标签——比如某道题既属于“Java 基础”又属于“高并发”。通过标签关联题目，前端选了某一标签后，用集合运算快速找出同时包含对应标签的所有题目，并且天然去重，比数据库 LIKE 或多个条件 OR 都高效。

五、ZSet

ZSet 是 Redis 里最特殊也最有用的数据结构。它是有序集合，每个元素关联一个 Score 分数，元素按 Score 自动排序。底层是跳表加哈希表双结构，跳表保证按分数的范围查询高效，哈希表保证按元素查分数的等值查询高效。

跳表是一种多层索引链表，底层是全量数据，上层以概率抽取节点做索引以跳过大量节点。范围查询时从高层索引快速定位边界，再下沉到实际数据区间遍历，查询效率接近二分查找。

项目里用 ZSet 做面试高频考题排行榜。用题目 ID 作为 member，被考察次数作为 score，每次考到就用 ZINCRBY 自增。查询前十热门考题用 ZREVRANGE 倒序秒级返回，性能远超数据库。还通过 ZADD 的 NX 选项实现首次收录时的初始化。

补充一个实际场景的细节：排行榜的权重不是简单地依赖于考察次数的。如果多类题目参与排行榜比较，不同分类的题目可能本身就有知识点难度差距，经常被考到不一定代表它“好”。所以在实际设计中，会加入时间衰减因素——某个题目很久没被抽中考到，权重就要慢慢降下来，用定时任务周期性拉取考察记录对 ZSet 做一次重新排序，或者直接用分数加权，把最近更新时间作为副权重结合进 Score 计算。这种方式让排行榜既体现热度，又能防止旧题目长期霸榜。

六、高级类型补充。

三种不太常被归类为“数据类型”，但在特定场景下性能极优：

Bitmap 是用位图存布尔值，适合签到、打卡、当天活跃用户标记。用 Bitmap 存用户签到记录，只占极少量内存。

HyperLogLog 是基数统计算法，统计不重复的元素个数，占恒定 12KB 内存，不分数据量大小。误差约 0.81%，适合 UV 统计、独立访客量，极大规模下非常省内存。

GEO 是地理位置类型，底层是 ZSet，存经纬度，计算两点距离、找附近的人、周边商家这些功能直接用 GEOADD、GEORADIUS 就行。

总结：Redis 的数据类型选型就是“什么模样选什么结构”。对象存 Hash，列表用 List，去重用 Set，排序用 ZSet，字符串缓存用 String，布尔标记用 Bitmap。按业务场景选，才能把 Redis 的快发挥到极致。

碎碎念：后续会更新每天学习的八股和算法题，暑假实习找不到了，开始准备秋招的第9天。努力连续更新100天！又vibecoding了一天，把项目理清楚了算是？反正写了一篇设计报告，明天争取测试跑起来。ai的项目复刻复刻！！！两眼一睁开就干！！但是就是感觉实际没积累多少东西，ai真是越用越虚，还是要好好先把基础打牢。先整理八股。