Step

掘金前端

作者烛阴

2025年5月17日 23:06

## Task > Write a shader that splits the screen

掘金前端
# Vue 中 provide/inject 与 props/emit 的对比与选择拉不动的猪
2025年5月17日 21:05

# Vue 中 provide/inject 与 props/emit 的对比与选择

掘金前端

作者拉不动的猪

2025年5月17日 21:05

一、核心设计理念差异 1. 数据流向的明确性 ‌props/emit‌ 遵循严格的单向数据流： ‌provide/inject‌ 则是隐式的跨层级通信：二、必须使用 props/emit 的场景 1

Vue 中 provide/inject 与传统状态管理的深度对比

掘金前端

作者拉不动的猪

2025年5月17日 21:00

一、provide/inject 基础原理 1. 基本用法 2. 响应式数据传递二、provide/inject 的优势 1. 组件树穿透能力 ‌场景‌：多层嵌套组件共享配置 2. 减少 props

LeetCode 每日一题题解
O(n) 插入排序，简洁写法（Python/Java/C++/C/Go/JS/Rust）endlesscheng
2025年5月17日 08:57

O(n) 插入排序，简洁写法（Python/Java/C++/C/Go/JS/Rust）

LeetCode 每日一题题解

作者 endlesscheng

2025年5月17日 08:57

不让用 $\texttt{sort}$ 吗？有意思……

技巧：O(1) 插入元素

假设现在有一个有序数组 $a=[0,0,1,1,2,2]$。在 $a$ 中插入一个 $0$，同时保证 $a$ 是有序的，你会怎么做？

最暴力的想法是，把 $0$ 插在数组的最左边，原来的元素全体右移一位，得到 $[0,0,0,1,1,2,2]$。这样做是 $\mathcal{O}(n)$ 的。

实际上，我们可以「狸猫换太子」：不是插入元素，而是修改元素！

对比一下插入前后：

插入前 $[0,0,1,1,2,2]$。
插入后 $[0,0,0,1,1,2,2]$。

竖着看，其实只有 $3$ 个位置变了：

原来的 $a[2]$ 变成 $0$。
原来的 $a[4]$ 变成 $1$。
末尾新增一个 $2$，相当于 $a[6]=2$。

怎么知道要修改的位置（下标）？

维护 $0$ 的个数，即为改成 $0$ 的位置，记作 $p_0$。上例中 $p_0=2$。把 $a[p_0]$ 改成 $0$。
维护 $0$ 和 $1$ 的个数，即为改成 $1$ 的位置，记作 $p_1$。上例中 $p_1=4$。把 $a[p_1]$ 改成 $1$。
末尾新增的位置记作 $i$，把 $a[i]$ 改成 $2$。

细节

如果 $a$ 中没有 $2$ 呢？上面第三步就错了。

比如现在 $a=[1]$，插入一个 $0$，变成 $[0,1]$。

如果按照上面三步走，最后把 $a[1]$ 改成 $2$，得到的是 $[0,2]$，这就错了。

要写很多 $\texttt{if-else}$，特判这些特殊情况吗？

不需要，我们可以倒过来算：先把 $a[1]$ 改成 $2$，再把 $a[1]$ 改成 $1$（覆盖），最后 $a[0]$ 改成 $0$，得到 $[0,1]$。这种「覆盖」等价于「没有 $2$ 的时候不改成 $2$」。

如果插入的是 $1$ 呢？

跳过「把 $a[p_0]$ 改成 $0$」这一步。

如果插入的是 $2$ 呢？

只需要把 $a[i]$ 改成 $2$ 即可。

本题思路

对 $\textit{nums}$ 执行插入排序，也就是对 $i=0,1,2,\ldots,n-1$ 依次执行如下过程：

现在前缀 $\textit{nums}[0]$ 到 $\textit{nums}[i-1]$ 是有序的，我们把 $\textit{nums}[i]$ 插入到这个有序前缀中，从而把前缀 $\textit{nums}[0]$ 到 $\textit{nums}[i]$ 变成有序的。
算法执行完后，$\textit{nums}$ 就是一个有序数组了。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        p0 = p1 = 0
        for i, x in enumerate(nums):
            nums[i] = 2
            if x <= 1:
                nums[p1] = 1
                p1 += 1
            if x == 0:
                nums[p0] = 0
                p0 += 1

class Solution {
    public void sortColors(int[] nums) {
        int p0 = 0;
        int p1 = 0;
        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            nums[i] = 2;
            if (x <= 1) {
                nums[p1++] = 1;
            }
            if (x == 0) {
                nums[p0++] = 0;
            }
        }
    }
}

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int p0 = 0, p1 = 0;
        for (int i = 0; i < nums.size(); i++) {
            int x = nums[i];
            nums[i] = 2;
            if (x <= 1) {
                nums[p1++] = 1;
            }
            if (x == 0) {
                nums[p0++] = 0;
            }
        }
    }
};

void sortColors(int* nums, int numsSize) {
    int p0 = 0, p1 = 0;
    for (int i = 0; i < numsSize; i++) {
        int x = nums[i];
        nums[i] = 2;
        if (x <= 1) {
            nums[p1++] = 1;
        }
        if (x == 0) {
            nums[p0++] = 0;
        }
    }
}

func sortColors(nums []int) {
    p0, p1 := 0, 0
    for i, x := range nums {
        nums[i] = 2
        if x <= 1 {
            nums[p1] = 1
            p1++
        }
        if x == 0 {
            nums[p0] = 0
            p0++
        }
    }
}

var sortColors = function(nums) {
    let p0 = 0, p1 = 0;
    for (let i = 0; i < nums.length; i++) {
        const x = nums[i];
        nums[i] = 2;
        if (x <= 1) {
            nums[p1++] = 1;
        }
        if (x === 0) {
            nums[p0++] = 0;
        }
    }
};

impl Solution {
    pub fn sort_colors(nums: &mut Vec<i32>) {
        let mut p0 = 0;
        let mut p1 = 0;
        for i in 0..nums.len() {
            let x = nums[i];
            nums[i] = 2;
            if x <= 1 {
                nums[p1] = 1;
                p1 += 1;
            }
            if x == 0 {
                nums[p0] = 0;
                p0 += 1;
            }
        }
    }
}