刷了四百道算法题，我在项目里用过哪几道呢？ 1版本比较：比

大家好，我是老三，今天和大家聊一个话题：项目中用到的力扣算法。

不知道从什么时候起，算法已经成为了互联网面试的标配，在十年前，哪怕如日中天的百度，面试也最多考个冒泡排序。后来，互联网越来越热，涌进来的人越来越多，整个行业越来越内卷的，算法也慢慢成了大小互联网公司面试的标配，力扣现在已经超过3000题了，那么这些题目有多少进入了面试的考察呢？

以最爱考算法的字节跳动为例，看看力扣的企业题库，发现考过的题目已经有1850道——按照平均每道题花20分钟来算，刷完字节题库的算法题需要37000分钟，616.66小时，按每天刷满8小时算，需要77.08天，一周刷五天，需要15.41周，按一个月四周，需要3.85个月。也就是说，在脱产，最理想的状态下，刷完力扣的字节题库，需要差不多4个月时间。

那么，我在项目里用过，包括在项目中见过哪些力扣上的算法呢？我目前刷了400多道题，翻来覆去盘点了一下，发现，也就这么几道。

1.版本比较：比较客户端版本

场景

在日常的开发中，我们很多时候可能面临这样的情况，兼容客户端的版本，尤其是Android和iPhone，有些功能是低版本不支持的，或者说有些功能到了高版本就废弃掉。

这时候就需要进行客户端的版本比较，客户端版本号通常是这种格式6.3.40，这是一个字符串，那就肯定不能用数字类型的比较方法，需要自己定义一个比较的工具方法。

题目

165. 比较版本号

这个场景对应LeetCode： 165. 比较版本号。

• 题目：165. 比较版本号 (leetcode.cn/problems/co…)
• 难度：中等
• 标签：双指针 字符串
• 描述：

给你两个版本号 version1 和 version2 ，请你比较它们。

版本号由一个或多个修订号组成，各修订号由一个 '.' 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。

比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1 ，0 < 1 。

返回规则如下：

+ 如果 `*version1* > *version2*` 返回 `1`，
+ 如果 `*version1* < *version2*` 返回 `-1`，
+ 除此之外返回 `0`。**示例 1：**

arduino复制代码输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：忽略前导零，"01" 和 "001" 都表示相同的整数 "1"

示例 2：

ini复制代码输入：version1 = "1.0", version2 = "1.0.0"
输出：0
解释：version1 没有指定下标为 2 的修订号，即视为 "0"

示例 3：

arduino复制代码输入：version1 = "0.1", version2 = "1.1"
输出：-1
解释：version1 中下标为 0 的修订号是 "0"，version2 中下标为 0 的修订号是 "1" 。0 < 1，所以 version1 < version2

提示：

+ `1 <= version1.length, version2.length <= 500`
+ `version1` 和 `version2` 仅包含数字和 `'.'`
+ `version1` 和 `version2` 都是 **有效版本号**
+ `version1` 和 `version2` 的所有修订号都可以存储在 **32 位整数** 中

解法

那么这道题怎么解呢？这道题其实是一道字符串模拟题，就像标签里给出了了双指针，这道题我们可以用双指针+累加来解决。

• 两个指针遍历version1和version2
• 将. 作为分隔符，通过累加获取每个区间代表的数字
• 比较数字的大小，这种方式正好可以忽略前导0

来看看代码:

arduino复制代码class Solution {
    public int compareVersion(String version1, String version2) {
        int m = version1.length();
        int n = version2.length();

        //两个指针
        int p = 0, q = 0;

        while (p < m || q < n) {
            //累加version1区间的数字
            int x = 0;
            while (p < m && version1.charAt(p) != '.') {
                x += x * 10 + (version1.charAt(p) - '0');
                p++;
            }

            //累加version2区间的数字
            int y = 0;
            while (q < n && version2.charAt(q) != '.') {
                y += y * 10 + (version2.charAt(q) - '0');
                q++;
            }

            //判断
            if (x > y) {
                return 1;
            }
            if (x < y) {
                return -1;
            }

            //跳过.
            p++;
            q++;
        }
        //version1等于version2
        return 0;
    }
}

应用

这段代码，直接CV过来，就可以直接当做一个工具类的工具方法来使用：

arduino复制代码public class VersionUtil {

    public static Integer compareVersion(String version1, String version2) {
        int m = version1.length();
        int n = version2.length();

        //两个指针
        int p = 0, q = 0;

        while (p < m || q < n) {
            //累加version1区间的数字
            int x = 0;
            while (p < m && version1.charAt(p) != '.') {
                x += x * 10 + (version1.charAt(p) - '0');
                p++;
            }

            //累加version2区间的数字
            int y = 0;
            while (q < n && version2.charAt(q) != '.') {
                y += y * 10 + (version2.charAt(q) - '0');
                q++;
            }

            //判断
            if (x > y) {
                return 1;
            }
            if (x < y) {
                return -1;
            }

            //跳过.
            p++;
            q++;
        }
        //version1等于version2
        return 0;
    }
}

前面老三分享过一个规则引擎：这款轻量级规则引擎，真香！

比较版本号的方法，还可以结合规则引擎来使用：

• 自定义函数：利用AviatorScript的自定义函数特性，自定义一个版本比较函数

typescript复制代码    /**
     * 自定义版本比较函数
     */
    class VersionFunction extends AbstractFunction {
        @Override
        public String getName() {
            return "compareVersion";
        }

        @Override
        public AviatorObject call(Map<String, Object> env, AviatorObject arg1, AviatorObject arg2) {
            // 获取版本
            String version1 = FunctionUtils.getStringValue(arg1, env);
            String version2 = FunctionUtils.getStringValue(arg2, env);
            return new AviatorBigInt(VersionUtil.compareVersion(version1, version2));
        }
    }

• 注册函数：将自定义的函数注册到AviatorEvaluatorInstance中

csharp复制代码    /**
     * 注册自定义函数
     */
    @Bean
    public AviatorEvaluatorInstance aviatorEvaluatorInstance() {
        AviatorEvaluatorInstance instance = AviatorEvaluator.getInstance();
        // 默认开启缓存
        instance.setCachedExpressionByDefault(true);
        // 使用LRU缓存，最大值为100个。
        instance.useLRUExpressionCache(100);
        // 注册内置函数，版本比较函数。
        instance.addFunction(new VersionFunction());
        return instance;
    }

• 代码传递上下文：在业务代码里传入客户端、客户端版本的上下文

typescript复制代码    /**
     * @param device  设备
     * @param version 版本
     * @param rule    规则脚本
     * @return 是否过滤
     */
    public boolean filter(String device, String version, String rule) {
        // 执行参数
        Map<String, Object> env = new HashMap<>();
        env.put("device", device);
        env.put("version", version);
        //编译脚本
        Expression expression = aviatorEvaluatorInstance.compile(DigestUtils.md5DigestAsHex(rule.getBytes()), rule, true);
        //执行脚本
        boolean isMatch = (boolean) expression.execute(env);
        return isMatch;
    }

• 编写脚本：接下来我们就可以编写规则脚本，规则脚本可以放在数据库，也可以放在配置中心，这样就可以灵活改动客户端的版本控制规则

kotlin复制代码if(device==bil){
    return false;
}

## 控制Android的版本
if (device=="Android" && compareVersion(version,"1.38.1")<0){
    return false;
}

return true;

2.N叉数层序遍历：翻译商品类型

场景

一个跨境电商网站，现在有这么一个需求：把商品的类型进行国际化翻译。

商品的类型是什么结构呢？一级类型下面还有子类型，字类型下面还有子类型，我们把结构一画，发现这就是一个N叉树的结构嘛。

翻译商品类型，要做的事情，就是遍历这棵树，翻译节点上的类型，这不妥妥的BFS或者DFS！

题目

429. N 叉树的层序遍历

这个场景对应LeetCode：429. N 叉树的层序遍历。

• 题目：429. N 叉树的层序遍历(leetcode.cn/problems/n-…)
• 难度：中等
• 标签：树 广度优先搜索
• 描述：

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例 1：

ini复制代码输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]

示例 2：

csharp复制代码输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：[[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]

提示：

+ 树的高度不会超过 `1000`
+ 树的节点总数在 `[0, 10^4]` 之间

解法

BFS想必很多同学都很熟悉了，DFS的秘诀是栈，BFS的秘诀是队列。

层序遍历的思路是什么呢？

使用队列，把每一层的节点存储进去，一层存储结束之后，我们把队列中的节点再取出来，孩子节点不为空，就把孩子节点放进去队列里，循环往复。

代码如下：

ini复制代码class Solution {
   public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        //创建队列并存储根节点
        Deque<Node> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            //存储每层结果
            List<Integer> level = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node current = queue.poll();
                level.add(current.val);
                //添加孩子
                if (current.children != null) {
                    for (Node child : current.children) {
                        queue.offer(child);
                    }
                }
            }
            //每层遍历结束，添加结果
            result.add(level);
        }
        return result;
    }
}

应用

商品类型翻译这个场景下，基本上和这道题目大差不差，不过是两点小区别：

• 商品类型是一个属性多一些的树节点
• 翻译过程直接替换类型名称即可，不需要返回值

来看下代码：

• ProductCategory：商品分类实体

arduino复制代码public class ProductCategory {
    /**
     * 分类id
     */
    private String id;
    /**
     * 分类名称
     */
    private String name;
    /**
     * 分类描述
     */
    private String description;
    /**
     * 子分类
     */
    private List<ProductCategory> children;
  
    //省略getter、setter
  
}

• translateProductCategory：翻译商品类型方法

arduino复制代码   public void translateProductCategory(ProductCategory root) {
        if (root == null) {
            return;
        }

        Deque<ProductCategory> queue = new LinkedList<>();
        queue.offer(root);

        //遍历商品类型，翻译
        while (!queue.isEmpty()) {
            int size = queue.size();
            //遍历当前层
            for (int i = 0; i < size; i++) {
                ProductCategory current = queue.poll();
                //翻译
                String translation = translate(current.getName());
                current.setName(translation);
                //添加孩子
                if (current.getChildren() != null && !current.getChildren().isEmpty()) {
                    for (ProductCategory child : current.getChildren()) {
                        queue.offer(child);
                    }
                }
            }
        }
    }

3.前缀和+二分查找：渠道选择

场景

在电商的交易支付中，我们可以选择一些支付方式，来进行支付，当然，这只是交易的表象。

在支付的背后，一种支付方式，可能会有很多种支付渠道，比如Stripe、Adyen、Alipay，涉及到多个渠道，那么就涉及到决策，用户的这笔交易，到底交给哪个渠道呢？

这其实是个路由问题，答案是加权随机，每个渠道有一定的权重，随机落到某个渠道，加权随机有很多种实现方式，其中一种就是前缀和+二分查找。简单说，就是先累积所有元素权重，再使用二分查找来快速查找。

题目

先来看看对应的LeetCode的题目，这里用到了两个算法：前缀和和二分查找。

704. 二分查找

• 题目：704. 二分查找(leetcode.cn/problems/bi…)
• 难度：简单
• 标签：数组 二分查找
• 描述：

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

makefile复制代码输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

makefile复制代码输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

1. 你可以假设 `nums` 中的所有元素是不重复的。
2. `n` 将在 `[1, 10000]`之间。
3. `nums` 的每个元素都将在 `[-9999, 9999]`之间。

解法

二分查找可以说我们都很熟了。

数组是有序的，定义三个指针，left、right、mid，其中mid是left、right的中间指针，每次中间指针指向的元素nums[mid]比较和target比较:

• 如果nums[mid]等于target，找到目标
• 如果nums[mid]小于target，目标元素在(mid,right]区间；
• 如果nums[mid]大于target，目标元素在[left,mid)区间

代码：

sql复制代码class Solution {
    public int search(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;

        while(left<=right){
            int mid=left+((right-left)>>1);
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]<target){
                //target在(mid,right]区间，右移
                left=mid+1;
            }else{
                //target在[left,mid)区间，左移
                right=mid-1;
            }
        }
        return -1;
    }
}

二分查找，有一个需要注意的细节，计算mid的时候：int mid = left + ((right - left) >> 1);，为什么要这么写呢？

因为这种写法int mid = (left + right) / 2;，可能会因为left和right数值太大导致内存溢出。同时，使用位运算，也是除以2最高效的写法。

——这里有个彩蛋，后面再说。

303. 区域和检索 - 数组不可变

不像二分查找，在LeetCode上，前缀和没有直接的题目，因为本身前缀和更多是一种思路，一种工具，其中303. 区域和检索 - 数组不可变 是一道典型的前缀和题目。

• 题目：303. 区域和检索 - 数组不可变(leetcode.cn/problems/ra…)
• 难度：简单
• 标签：设计 数组 前缀和
• 描述：

给定一个整数数组 nums，处理以下类型的多个查询:

1. 计算索引 `left` 和 `right` （包含 `left` 和 `right`）之间的 `nums` 元素的 **和** ，其中 `left <= right`实现 `NumArray` 类：


+ `NumArray(int[] nums)` 使用数组 `nums` 初始化对象
+ `int sumRange(int i, int j)` 返回数组 `nums` 中索引 `left` 和 `right` 之间的元素的 **总和** ，包含 `left` 和 `right` 两点（也就是 `nums[left] + nums[left + 1] + ... + nums[right]` )**示例 1：**

scss复制代码输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

提示：

+ `1 <= nums.length <= 104`
+ `-105 <= nums[i] <= 105`
+ `0 <= i <= j < nums.length`
+ 最多调用 `104` 次 `sumRange` 方法

解法

这道题，我们如果不用前缀和的话，写起来也很简单：

arduino复制代码class NumArray {
    private int[] nums;

    public NumArray(int[] nums) {
        this.nums=nums;
    }
    
    public int sumRange(int left, int right) {
        int res=0;
        for(int i=left;i<=right;i++){
            res+=nums[i];
        }
        return res;
    }
}

当然时间复杂度偏高，O(n)，那么怎么使用前缀和呢？

• 构建一个前缀和数组，用来累积 (0……i-1)的和，这样一来，我们就可以直接计算[left,right]之间的累加和

代码如下：

ini复制代码class NumArray {
    private int[] preSum;

    public NumArray(int[] nums) {
        int n=nums.length;
        preSum=new int[n+1];
        //计算nums的前缀和
        for(int i=0;i<n;i++){
            preSum[i+1]=preSum[i]+nums[i];
        }
    }
    
    //直接算出区间[left,right]的累加和
    public int sumRange(int left, int right) {
        return preSum[right+1]-preSum[left];
    }
}

可以看到，通过前缀和数组，可以直接算出区间[left,right]的累加和，时间复杂度O(1)，可以说非常高效了。

应用

了解了前缀和和二分查找之后，回归我们之前的场景，使用前缀和+二分查找来实现加权随机，从而实现对渠道的分流选择。

• 需要根据渠道和权重的配置，生成一个前缀和数组，来累积权重的值，渠道也通过一个数组进行分配映射
• 用户的支付请求进来的时候，生成一个随机数，二分查找找到随机数载前缀和数组的位置，映射到渠道数组
• 最后通过渠道数组的映射，找到选中的渠道

代码如下：

ini复制代码/**
 * 支付渠道分配器
 */
public class PaymentChannelAllocator {
    //渠道数组
    private String[] channels;
    //前缀和数组
    private int[] preSum;
    private ThreadLocalRandom random;

    /**
     * 构造方法
     *
     * @param channelWeights 渠道分流权重
     */
    public PaymentChannelAllocator(HashMap<String, Integer> channelWeights) {
        this.random = ThreadLocalRandom.current();
        // 初始化channels和preSum数组
        channels = new String[channelWeights.size()];
        preSum = new int[channelWeights.size()];

        // 计算前缀和
        int index = 0;
        int sum = 0;
        for (String channel : channelWeights.keySet()) {
            sum += channelWeights.get(channel);
            channels[index] = channel;
            preSum[index++] = sum;
        }
    }

    /**
     * 渠道选择
     */
    public String allocate() {
        // 生成一个随机数
        int rand = random.nextInt(preSum[preSum.length - 1]) + 1;

        // 通过二分查找在前缀和数组查找随机数所在的区间
        int channelIndex = binarySearch(preSum, rand);
        return channels[channelIndex];
    }

    /**
     * 二分查找
     */
    private int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + ((right - left) >> 2);
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 当找不到确切匹配时返回大于随机数的最小前缀和的索引
        return left;
    }
}

测试一下：

ini复制代码    @Test
    void allocate() {
        HashMap<String, Integer> channels = new HashMap<>();
        channels.put("Adyen", 50);
        channels.put("Stripe", 30);
        channels.put("Alipay", 20);

        PaymentChannelAllocator allocator = new PaymentChannelAllocator(channels);

        // 模拟100次交易分配
        for (int i = 0; i < 100; i++) {
            String allocatedChannel = allocator.allocate();
            System.out.println("Transaction " + (i + 1) + " allocated to: " + allocatedChannel);
        }
    }

彩蛋

在这个渠道选择的场景里，还有两个小彩蛋。

二分查找翻车

我前面提到了一个二分查找求mid的写法：

sql复制代码int mid=left+((right-left)>>1);

这个写法机能防止内存溢出，用了位移运算也很高效，但是，这个简单的二分查找写出过问题，直接导致线上cpu飙升，差点给老三吓尿了。

sql复制代码int mid = (right - left) >> 2 + left;

就是这行代码，看出什么问题来了吗？

——它会导致循环结束不了！

为什么呢？因为>>运算的优先级是要低于+的，所以这个运算实际上等于：

sql复制代码int mid = (right - left) >> (2 + left);

在只有两个渠道的时候没有问题，三个的时候就寄了。

当然，最主要原因还是没有充分测试，所以大家知道我在上面为什么特意写了单测吧。

加权随机其它写法

这里用了前缀和+二分查找来实现加权随机，其实加权随机还有一些其它的实现方法，包括别名方法、树状数组、线段树 、 随机列表扩展 、 权重累积等等方法，大家感兴趣可以了解一下。

印象比较深刻的是，有场面试被问到了怎么实现加权随机，我回答了权重累积、前缀和+二分查找，面试官还是不太满意，最后面试官给出了他的答案——随机列表扩展。

什么是随机列表扩展呢？简单说，就是创建一个足够大的列表，根据权重，在相应的区间，放入对应的渠道，生成随机数的时候，就可以直接获取对应位置的渠道。

arduino复制代码public class WeightedRandomList {
    private final List<String> expandedList = new ArrayList<>();
    private final Random random = new Random();

    public WeightedRandomList(HashMap<String, Integer> weightMap) {
        // 填充 expandedList，根据权重重复元素
        for (String item : weightMap.keySet()) {
            int weight = weightMap.get(item);
            for (int i = 0; i < weight; i++) {
                expandedList.add(item);
            }
        }
    }

    public String getRandomItem() {
        // 生成随机索引并返回对应元素
        int index = random.nextInt(expandedList.size());
        return expandedList.get(index);
    }

    public static void main(String[] args) {
        HashMap<String, Integer> items = new HashMap<>();
        items.put("Alipay", 60);
        items.put("Adyen", 20);
        items.put("Stripe", 10);

        WeightedRandomList wrl = new WeightedRandomList(items);

        // 演示随机选择
        for (int i = 0; i < 10; i++) {
            System.out.println(wrl.getRandomItem());
        }
    }
}

这种实现方式就是典型的空间换时间，空间复杂度O(n)，时间复杂度O(1)。优点是时间复杂度低，缺点是空间复杂度高，如果权重总和特别大的时候，就需要一个特别大的列表来存储元素。

当然这种写法还是很巧妙的，适合元素少、权重总和小的场景。

刷题随想

上面就是我在项目里用到过或者见到过的LeetCode算法应用，416:4，不足1%的使用率，还搞出过严重的线上问题。

……

在力扣社区里关于算法有什么的贴子里，有这样的回复：

“最好的结构是数组，最好的算法是遍历”。

“最好的算法思路是暴力。”

……

坦白说，如果不是为了面试，我是绝对不会去刷算法的，上百个小时，用在其他地方，绝对收益会高很多。

从实际应用去找刷LeetCode算法的意义，本身没有太大意义，算法题的最大意义就是面试。

刷了能过，不刷就挂，仅此而已。

这些年互联网行业红利消失，越来越多的算法题，只是内卷的产物而已。

当然，从另外一个角度来看，考察算法，对于普通的打工人，可能是个更公平的方式——学历、背景都很难卷出来，但是算法可以。

我去年面试的真实感受，“没机会”比“面试难”更令人绝望。

写到这，有点难受，刷几道题缓一下！

---

参考：

[1].leetcode.cn/circle/disc…

[2].36kr.com/p/121243626…

[3].leetcode.cn/circle/disc…

[4].leetcode.cn/circle/disc…

---

备注：涉及敏感信息，文中的代码都不是真实的投产代码，作者进行了一定的脱敏和演绎。

---

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有