LeetCode-18

剑指Offer继续刷，代码随想录已经到动态规划了

172 阶乘后的零

时间：2022-03-25

没话说，直接CV

var trailingZeroes = function(n) {
    let ans = 0;
    while (n !== 0) {
        n = Math.floor(n / 5);
        ans += n;
    }
    return ans;
};

offer 43 1-n整数中1出现的次数

时间：2022-03-25

困难题，我直接抄袭，唯一能够看懂的解法，讲的非常的清楚。

var countDigitOne = function (n) {
    let digit = 1; // digit 需为 long 型，因为比如 n 是 INT_MAX，digit 会在最后一次循环越界
    let high = Math.floor(n / 10),
        cur = n % 10,
        low = 0;
    let res = 0;

    while (high != 0 || cur != 0) {
        if (cur == 0) {
            res += high * digit;
        } else if (cur == 1) {
            res += high * digit + low + 1;
        } else {
            res += (high + 1) * digit;
        }

        low += cur * digit;
        cur = high % 10;
        high = Math.floor(high/10);
        digit *= 10;
    }

    return res;
};

offer 44 数字序列中某一位的数字

时间：2022-03-25

非常的难，史诗级难度，虽然之前做过了，但是这次还是不会，以后估计还是不会，问题不大。

var findNthDigit = function (n) {
    let digit = 1,
        start = 1,
        count = 9;
    while (n > count) {
        n -= count;
        start *= 10;
        digit += 1;
        count = 9 * start * digit;
    }
    num = start + Math.floor((n - 1) / digit);
    num = num.toString();
    return num[(n - 1) % digit];
};

offer 45 把数组排成最小的数

时间：2022-03-25

直接排序，牛逼

var minNumber = function (nums) {
    nums.sort((a, b) => Number(a.toString() + b.toString()) - Number(b.toString() + a.toString()));
    return nums.join('');
};

682 棒球比赛

时间：2022-03-26

什么简单题。

var calPoints = function (ops) {
    const st = [];
    for (let i of ops) {
        if (i === '+') {
            st.push(st[st.length - 1] + st[st.length - 2]);
        } else if (i === 'D') {
            st.push(st[st.length - 1] * 2);
        } else if (i === 'C') {
            st.pop();
        } else {
            st.push(Number(i));
        }
    }
    return st.reduce((a, b) => a + b, 0);
};

offer 46 把数字翻译成字符串

时间：2022-03-26

梭哈，简单问题简单解。

var translateNum = function (num) {
    num = num.toString();
    const n = num.length;
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        if ((num[i - 1] <= '5' && num[i - 1] >= '0' && num[i - 2] == '2') || num[i - 2] == '1') {
            dp[i] = dp[i - 2] + dp[i - 1];
        } else {
            dp[i] = dp[i - 1];
        }
    }
    return dp[n];
};

offer 49 丑数

时间：2022-03-26

看题解，这个还是挺好理解的动态规划，但是是三指针+动态规划，三个指针分别指向2和3和5的位置，每次取最小

var nthUglyNumber = function (n) {
    const dp = new Array(n).fill(0);
    dp[0] = 1;
    let p2 = 0,
        p3 = 0,
        p5 = 0;
    for (let i = 1; i < n; i++) {
        const num1 = dp[p2] * 2;
        const num2 = dp[p3] * 3;
        const num3 = dp[p5] * 5;

        dp[i] = Math.min(num1, Math.min(num2, num3));
        if (dp[i] == num1) p2++;
        if (dp[i] == num2) p3++;
        if (dp[i] == num3) p5++;
    }
    return dp[n - 1];
};

offer 50 第一个只出现一次的字符

时间：2022-03-26

var firstUniqChar = function (s) {
    const map = new Map();
    for (let i of s) {
        map.set(i, (map.get(i) || 0) + 1);
    }
    for (let [index, value] of map) {
        if (value == 1) return index;
    }
    return ' '
};

offer 51 数组中的逆序对

时间：2022-03-26

过不去的O(n^2)，还得再想想

var reversePairs = function (nums) {
    const n = nums.length;
    let res = 0;
    for (let i = 0; i < n - 1; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] > nums[j]) res++;
        }
    }
    return res;
};

排序归并，就只需要加一行，在排序好的左右序列，只要左边有个大于右边，那么左边剩下的都比右边大，所以加上剩下的那些就行了

var reversePairs = function (nums) {
    let res = 0;
    const n = nums.length;
    const arr = new Array(n).fill(0);
    const mergeSort = (nums, left, right) => {
        if (left >= right) return;
        const mid = Math.floor((left + right) / 2);
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        let i = left;
        let j = mid+1;
        let k = 0;
        while (i <= mid && j <= right) {
            if (nums[i] <= nums[j]) arr[k++] = nums[i++];
            else {
                arr[k++] = nums[j++];
                res += mid-i+1;	//就只需要加一行
            }
        }
        while (i <= mid) arr[k++] = nums[i++];
        while (j <= right) arr[k++] = nums[j++];
        for (let i = left; i <= right; i++) nums[i] = arr[i - left];
    };
    mergeSort(nums, 0, n-1);
    return res;
};

offer 53 I 在排序数组中查找数字 I

时间：2022-03-27

var search = function (nums, target) {
    let res = 0;
    for (let i of nums) if (i == target) res++;
    return res;
};

二分法，找到左边界和右边界

var search = function (nums, target) {
    let i = 0,
        j = nums.length - 1;
    let mid;
    while (i <= j) {
        mid = Math.floor((i + j) / 2);
        if (nums[mid] >= target) {
            j = mid - 1;
        } else {
            i = mid + 1;
        }
    }
    const start = i;
    j = nums.length - 1;
    while (i <= j) {
        mid = Math.floor((i + j) / 2);
        if (nums[mid] > target) {
            j = mid - 1;
        } else {
            i = mid + 1;
        }
    }
    return i - start;
};

offer 53 II 0-n-1中缺失的数字

时间：2022-03-27

继续二分法，判断条件是下标+1不等于数字

var missingNumber = function (nums) {
    let i = 0,
        j = nums.length - 1,
        mid;
    while (i <= j) {
        mid = Math.floor((i + j) / 2);
        if (nums[mid] == mid + 1) {
            j = mid - 1;
        } else {
            i = mid + 1;
        }
    }
    return i;
};

offer 54 二叉搜索树的第k大节点

时间：2022-03-27

简单，右中左遍历

var kthLargest = function (root, k) {
    if (!root) return 0;
    let res = 0;
    const dfs = (root) => {
        root.right && dfs(root.right);
        k--;
        if (k == 0) {
            res = root.val;
            return;
        }
        root.left && dfs(root.left);
    };
    dfs(root, k);
    return res;
};

693 交替位二进制数

时间：2022-03-28

var hasAlternatingBits = function (n) {
    const num = n.toString(2);
    for (let i = 1; i < num.length; i++) {
        if (num[i] ^ (num[i - 1] == 0)) return false;
    }
    return true;
};

妙蛙种子版本

var hasAlternatingBits = function (n) {
    const a = n ^ (n >> 1);
    return (a & (a + 1)) === 0;
};

offer 56 I 数组中数字出现的次数

时间：2022-03-28

什么妙蛙种子的方案，太妙了8，先找到两个数字的异或，然后找到最低位的1，然后根据这个最低位的1进行分组，有1的分一组，没1的分一组，这样子就是两个数字了。

var singleNumbers = function (nums) {
    let res = 0;
    for (let i of nums) res ^= i;
    let div = 1;
    while ((div & res) == 0) div <<= 1;
    let a = 0,
        b = 0;
    for (let i of nums) {
        if (div & i) {
            a ^= i;
        } else {
            b ^= i;
        }
    }
    return [a, b];
};

offer 56 II 数组中数字出现的次数 II

又是神仙解法，位运算，如果一个数字的出现了三次，那么二进制的位就会出现三次，所以统计每个二进制位上面的数量，然后取模3，这样子就是只出现一次的那个数字对应的二进制位

var singleNumber = function (nums) {
    let res = 0,
        bit = 0;
    for (let i = 30; i >= 0; i--) {
        for (let n of nums) {
            bit += (n >> i) & 1;
        }
        res <<= 1;
        res += bit % 3;
        bit = 0;
    }
    return res;
};

offer 57 和为s的两个数字

时间：2022-03-28

var twoSum = function (nums, target) {
    let i = 0;
    j = nums.length - 1;
    while (i < j) {
        const num = nums[i] + nums[j];
        if (num == target) return [nums[i], nums[j]];
        else if (num > target) j--;
        else i++;
    }
    return [];
};

offer 57 II 和为s的连续正数序列

时间：2022-03-28

什么神仙方法，自己写的，快的一批

var findContinuousSequence = function (target) {
    const mid = Math.round(target / 2);
    const res = [];
    let i = 1;
    let sum = 1;
    for (let j = 2; j <= mid; j++) {
        sum += j;
        while (sum > target) {
            sum -= i;
            i++;
        }
        if (sum == target) res.push(new Array(j - i + 1).fill(0).map((_, index) => index + i));
    }
    return res;
};

offer 59 II 队列的最大值

时间：2022-03-28

直接抄的别人的，舒服。

var MaxQueue = function () {
    this.queue = []; // 用一个正常数组存取每次 push 进来的元素
    this.maxQueue = []; // 该队列专门为了简化 max_value 这个 API，称它为单调递减队列
};

/**
 * @return {number}
 */
MaxQueue.prototype.max_value = function () {
    return this.maxQueue.length ? this.maxQueue[0] : -1;
};

/**
 * @param {number} value
 * @return {void}
 */
MaxQueue.prototype.push_back = function (value) {
    this.queue.push(value); // 正常压入该队列，然后下面维护另一个单调递减队列
    // 队尾开始遍历，遇到值比 value 小的就弹出，维护单调递减队列
    while (this.maxQueue.length && this.maxQueue[this.maxQueue.length - 1] < value) {
        this.maxQueue.pop();
    }
    this.maxQueue.push(value);
};

/**
 * @return {number}
 */
MaxQueue.prototype.pop_front = function () {
    if (!this.queue.length) return -1;

    const val = this.queue.shift(); // 该队列由于是正常存放所有压入数组的队列，正常弹出即可
    // 如果弹出的元素正好是单调队列中的队头，那也要弹出，如果弹出的元素不是单调队列头部，那不用管了hh，因为 max_value 的API 只跟队头有关，只要队头元素不要在已经被移出原队列的基础上，还存在单调队列里就行
    if (this.maxQueue[0] === val) {
        this.maxQueue.shift();
    }

    return val;
};

1004 最大连续1的个数 III

时间：2022-03-29

直接抄的别人滑动窗口模板

var longestOnes = function (nums, k) {
    let res = 0,
        left = 0,
        numZero = 0;
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] == 0) numZero++;
        while (numZero > k) {
            if (nums[left] == 0) numZero--;
            left++;
        }
        res = Math.max(res, right - left + 1);
    }
    return res;
};

2024 考试的最大困扰度

时间：2022-03-29

直接使用上一题的模板，一条龙直接冲过去，芜湖

var maxConsecutiveAnswers = function (answerKey, k) {
    return Math.max(findSubArray(answerKey, k, 'T'), findSubArray(answerKey, k, 'F'));
};

const findSubArray = (nums, k, ch) => {
    let res = 0,
        left = 0,
        sums = 0;
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] == ch) sums++;
        while (sums > k) {
            if (nums[left] == ch) sums--;
            left++;
        }
        res = Math.max(res, right - left + 1);
    }
    return res;
};

offer 60 n个骰子的点数

时间：2022-03-29

直接抄袭，这道题有困难的水平，非常的困难，理解起来比较困难。

var dicesProbability = function (n) {
    // 第一次的骰子概率都为 1/6
    let dp = new Array(6).fill(1 / 6);

    // 遍历有多少个骰子
    for (let i = 2; i <= n; i++) {
        // n个骰子对应5n+1个和
        // temp[0] 是每个骰子都是 1 的概率，i 个骰子对应和为 i
        let temp = new Array(5 * i + 1).fill(0);
        // 遍历上一次的骰子每一个和对应的概率
        for (let j = 0; j < dp.length; j++) {
            // 这一次分别摇到 1 - 6，每一次的概率都是 1/6
            for (let k = 0; k < 6; k++) {
                // 相当于上一次的骰子点数之和再加上这次摇到对应的点数的新和的概率
                // 当 j=0，k=0 时，dp[0] 是上一次 n - 1 个骰子都是摇到 1 的概率
                // temp[0] = dp[0] / 6 相当于这一次又摇到 1 的概率
                temp[j + k] += dp[j] / 6;
            }
        }
        // i 个骰子的点数之和转移到 dp
        dp = temp;
    }
    return dp;
};

offer 61 扑克牌中的顺子

时间：2022-03-29

k神，我永远滴神

var isStraight = function (nums) {
    nums.sort((a, b) => a - b);
    let zero = 0;
    for (let i = 0; i < 4; i++) {
        if (nums[i] == 0) zero++;
        else if (nums[i] == nums[i + 1]) return false;
    }
    return nums[4] - nums[zero] < 5;
};

offer 62 圆圈中最后剩下的数字

时间：2022-03-29

妈的，还是不会，这个真的很难，递归也想不明白了属于是。

var lastRemaining = function (n, m) {
    if (n == 1) return 0;
    return (lastRemaining(n - 1, m) + m) % n;
};

迭代，不行，真的掌握不住，太考验脑子了。

var lastRemaining = function (n, m) {
    let f = 0; //最后剩下一个人的情况时胜利者的下标是0
    //开始逆推
    for (let i = 2; i <= n; ++i) {
        f = (f + m) % i; //循环右移m位
    }
    return f;
};

offer 64 求1加到n

时间：2022-03-29

就是神仙递归法，把if变成了&&

var sumNums = function (n) {
    n && (n += sumNums(n - 1));
    return n;
};

offer 65 不用加减乘除做加法

时间：2022-03-29

太难了，这个真的太难了，一开始我就老老实实一位一位弄，结果碰到负数炸了。看了一下官解，看不懂，其实有点递归在里面，就是一个数字相加可以拆分成本位和进位，然后把这两个相加，但是相加又不能用，只能继续套娃递归，直到进位为0，那就返回本位。

var add = function (a, b) {
    if (b == 0) return a;
    return add(a ^ b, (a & b) << 1);
};

迭代相当于拆分了递归而已。

var add = function (a, b) {
    while (b) {
        let carry = a & b; // 计算 进位
        a = a ^ b; // 计算 本位
        b = carry << 1;
    }
    return a;
};

offer 66 构建乘积数组

时间：2022-03-29

看的别人的解法，然后自己写出来的。大概就是这样子了。两遍循环，从前到后，然后再相乘

var constructArr = function (a) {
    const n = a.length;
    const res = new Array(n).fill(1);
    for (let i = 0; i < n - 1; i++) {
        res[i + 1] = a[i] * res[i];
    }
    // res[1,a,ab,abc,abcd]
    console.log(res);
    const tmp = new Array(n).fill(1);
    for (let i = n - 1; i >= 1; i--) {
        tmp[i - 1] = a[i] * tmp[i];
        // tmp[bcde,cde,de,e,1]
        res[i - 1] *= tmp[i - 1];
    }
    // res[bcde,acde,abde,abce,abcd]
    return res;
};

1606 找到处理最多请求的服务器

时间：2022-03-30

直接抄袭一题，没用上优先队列，虽然时间很长，但是能过就行了，什么优先不优先的队列，别折腾了。

var busiestServers = function (k, arrival, load) {
    // 统计服务器执行任务数量
    const taskCounts = Array(k).fill(0);
    // 记录服务器当前任务执行到哪一个时间点
    const serversTimestamp = Array(k).fill(0);
    // 记录当前执行了任务最多的服务器的任务次数
    // 搜索当前哪台服务器空闲函数
    const findFreeServer = (time, i) => {
        // 如果第 (i % k) 个服务器空闲，那么对应服务器会处理该请求
        let j = i % k;
        if (serversTimestamp[j] <= time) return j;
        // 找一圈
        for (let l = j + 1; l < j + k + 1; l++) {
            if (serversTimestamp[l % k] <= time) return l % k;
        }
        return -1;
    };
    arrival.forEach((time, i) => {
        // 找到空闲服务器
        let serverIndex = findFreeServer(time, i);
        // 全都没空，任务抛弃
        if (serverIndex === -1) return;
        // 对应服务器执行任务次数累加并判断是不是最多的记录到max字段
        taskCounts[serverIndex]++;
        // 记录当前服务器的时间戳
        serversTimestamp[serverIndex] = time + load[i];
    });
    // 找到处理任务最多的服务器
    let max = Math.max(...taskCounts);
    let res = [];
    for (let i = 0; i < k; ++i) {
        if (taskCounts[i] === max) res.push(i);
    }
    return res;
};

offer II 001 整数除法

时间：2022-03-30

太难了，最朴素的方法先来一个，用解法来解决，就是非常费时，万幸能够通过。

var divide = function (a, b) {
    const INT_MIN = -Math.pow(2, 31);
    const INT_MAX = Math.pow(2, 31) - 1;

    if (a == INT_MIN && b == -1) return INT_MAX;

    let res = 0;
    let flag = true;
    if (a < 0) {
        a = -a;
        flag = !flag;
    }
    if (b < 0) {
        b = -b;
        flag = !flag;
    }
    if (a < b) return 0;
    while (a >= b) {
        a -= b;
        res++;
    }
    return flag ? res : -res;
};

又好又快，又好又快啊，倍增乘法，其实就是每次乘以2呗

var divide = function (a, b) {
    const INT_MIN = -Math.pow(2, 31);
    const INT_MAX = Math.pow(2, 31) - 1;
    if (a == INT_MIN && b == -1) return INT_MAX;

    let res = 0;
    let flag = true;
    if (a < 0) {
        a = -a;
        flag = !flag;
    }
    if (b < 0) {
        b = -b;
        flag = !flag;
    }
    if (a < b) return 0;
    while (a >= b) {
        let value = b;
        let k = 1;
        while (value > 0 && a >= value + value) {
            value += value;
            k += k;
        }
        a -= value;
        res += k;
    }
    return flag ? res : -res;
};

二进制的不看了，看不懂，烦得很，这才剑指Offer II的第一题呢，还是简单题，淦！

offer II 002 二进制加法

时间：2022-03-30

都在这儿比笨是吧，当然也可以看字符串相加leetcode-15-415

var addBinary = function (a, b) {
    let flag = 0;
    if (a.length < b.length) [a, b] = [b, a];
    let i = a.length - 1,
        j = b.length - 1;
    const res = [];
    while (j >= 0) {
        const c = +a[i];
        const d = +b[j];
        if (c ^ d) {
            if (flag) res.push(0);
            else res.push(1);
        } else {
            if (flag) res.push(1);
            else res.push(0);
            flag = c && d;
        }
        i--;
        j--;
    }
    while (i >= 0) {
        const c = +a[i];
        if (flag) {
            if (c) {
                res.push(0);
            } else {
                res.push(1);
                flag = 0;
            }
        } else {
            res.push(c);
        }
        i--;
    }
    if (flag) res.push(1);
    return res.reverse().join('');
};

offer II 003 前 n 个数字二进制中 1 的个数

时间：2022-03-30

我就想不起来了x&x-1到底是干嘛的了，原来是获得消去最低位的1，反复就能获得1的个数，这就是最朴素的

O(nlogn)

var countBits = function (n) {
    const bits = new Array(n + 1).fill(0);
    for (let i = 0; i <= n; i++) {
        bits[i] = countOnes(i);
    }
    return bits;
};

const countOnes = (x) => {
    let ones = 0;
    while (x > 0) {
        x &= x - 1;
        ones++;
    }
    return ones;
};

动态规划我也感觉出来了，就是递推公式找不出来，一看题解，就这？简单题罢了。

var countBits = function (n) {
    const dp = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        dp[i] = dp[i >> 1] + (i & 1);
    }
    return dp;
};

offer II 004 只出现一次的数字

时间：2022-03-30

如果是正数的情况，就是这种情况leetcode-18-offer-56-II。

这里需要考虑一下负数的情况，那么就是i从31开始嘛。

var singleNumber = function (nums) {
    let res = 0,
        bit = 0;
    for (let i = 31; i >= 0; i--) {
        for (let n of nums) {
            bit += (n >> i) & 1;
        }
        res <<= 1;
        res += bit % 3;
        bit = 0;
    }
    return res;
};

还有数电的方法，直接抄袭好吧，就不用了解了。

var singleNumber = function(nums) {
    let a = 0, b = 0;
    for (const num of nums) {
        b = ~a & (b ^ num);
        a = ~b & (a ^ num);
    }
    return b;
};

728 自除数

时间：2022-03-31

var selfDividingNumbers = function (left, right) {
    let res = [];
    for (let i = left; i <= right; i++) {
        let j = i;
        while (j > 0) {
            if (i % (j % 10) != 0) break;
            j = Math.floor(j / 10);
        }
        if (j == 0) res.push(i);
    }
    return res;
};

offer II 005 单词长度的最大乘积

时间：2022-03-31

直接抄袭之前的做法，虽然之前的做法也是抄袭的，用的位运算，做掩码，用字母来做掩码，两个掩码一与，如果为0，那么就是不包含相同字符。

var maxProduct = function (words) {
    const mask = new Array(words.length).fill(0);
    for (let i = 0; i < words.length; i++) {
        for (let w of words[i]) {
            mask[i] |= 1 << (w.charCodeAt() - 97);
        }
    }
    let res = 0;
    for (let i = 0; i < words.length - 1; i++) {
        for (let j = i + 1; j < words.length; j++) {
            if ((mask[i] & mask[j]) == 0) {
                res = Math.max(res, words[i].length * words[j].length);
            }
        }
    }
    return res;
};

offer II 006 排序数组中两个数字之和

时间：2022-03-31

感觉之前剑指offer就写过了。

var twoSum = function (numbers, target) {
    let i = 0,
        j = numbers.length - 1;
    while (i < j) {
        if (numbers[i] + numbers[j] == target) return [i, j];
        else if (numbers[i] + numbers[j] < target) i++;
        else j--;
    }
    return [];
};

offer II 010 和为k的子数组

时间：2022-03-31

居然不是滑动窗口了，因为有负数的问题，需要用到前缀和以及哈希表，用哈希表去查看之前已经记录的前缀和，如果存在pre-k这个前缀记录，那么就直接加上这个前缀记录出现的次数即可。

var subarraySum = function (nums, k) {
    let pre = 0,
        res = 0;
    const map = new Map([[0, 1]]);
    for (let i = 0; i < nums.length; i++) {
        pre += nums[i];
        if (map.has(pre - k)) res += map.get(pre - k);
        map.set(pre, (map.get(pre) || 0) + 1);
    }
    return res;
};

offer II 013 二维子矩阵的和

时间：2022-03-31

一维的前缀和，每次计算的时候需要叠加前缀和。

var NumMatrix = function(matrix) {
    const m = matrix.length;
    if (m > 0) {
        const n = matrix[0].length;
        this.sums = new Array(m).fill(0).map(() => new Array(n + 1).fill(0));
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                this.sums[i][j + 1] = this.sums[i][j] + matrix[i][j];
            }
        }
    }
};

NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
    let sum = 0;
    for (let i = row1; i <= row2; i++) {
        sum += this.sums[i][col2 + 1] - this.sums[i][col1];
    }
    return sum;
};

二维前缀和，没写出来，不应该啊，这我感觉好像想到了啊，实现的时候没有理清楚吧，但这个已经很清晰明了。

var NumMatrix = function (matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    this.sums = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            this.sums[i + 1][j + 1] = this.sums[i][j + 1] + this.sums[i + 1][j] - this.sums[i][j] + matrix[i][j];
        }
    }
};

NumMatrix.prototype.sumRegion = function (row1, col1, row2, col2) {
    return this.sums[row2 + 1][col2 + 1] - this.sums[row1][col2 + 1] - this.sums[row2 + 1][col1] + this.sums[row1][col1];
};

41 缺失的第一个正数

时间：2022-03-31

困难题，直接摆烂，用的什么置换，就是下标0对应1，下标1对应2，找数字进行置换

const firstMissingPositive = (nums) => {
    const len = nums.length;
    for (let i = 0; i < len; i++) {
        // 将nums[i]放到对应的位置
        while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] !== nums[i]) {
            [nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]];
        }
    }
    // 遍历是否是对应位置
    for (let i = 0; i < len; i++) {
        if (nums[i] !== i + 1) return i + 1;
    }
    return len + 1;
};