LeetCode-16

继续二刷代码随想录和三道新题。可以打打周赛，选取周赛的题目也行。

2055 蜡烛之间的盘子

时间：2022-03-08

这题挺难的，甚至直接放弃去看题解。用上了前缀和和预处理，这个left和right的还需要反一下，真的是挺难的好吧。困难的中等题了。

var platesBetweenCandles = function (s, queries) {
    const n = s.length;
    const preSum = new Array(n).fill(0);
    let sum = 0;
    for (let i = 0; i < n; i++) {
        if (s[i] == '*') {
            sum++;
        }
        preSum[i] = sum;
    }
    let l = -1,
        r = -1;
    const left = new Array(n).fill(-1);
    const right = new Array(n).fill(-1);
    for (let i = 0; i < n; i++) {
        if (s[i] == '|') l = i;
        if (s[n - i - 1] == '|') r = n - i - 1;
        left[i] = l;
        right[n - i - 1] = r;
    }
    const m = queries.length;
    const res = new Array(m).fill(0);
    for (let i = 0; i < m; i++) {
        const x = right[queries[i][0]],
            y = left[queries[i][1]];
	        if (x == -1 || y == -1 || x > y) continue;
        res[i] = preSum[y] - preSum[x];
    }
    return res;
};

525 连续数组

时间：2022-03-08

这是一道前缀和 与哈希表联合的题目，可以理解为用到了前缀和，如果两个的前缀和相同，那么说明他们中间的数组加起来为0，在这道题里面就是0和1的数量相同。使用哈希表来记录最初的前缀和，如果没有这个前缀和，就添加进去，这肯定是最早的前缀和，如果有这个前缀和，那么就判断是不是最大的，非常巧妙的题目，又是我不会的。

var findMaxLength = function (nums) {
    const map = new Map();
    map.set(0, -1);
    let sum = 0;
    let res = 0;
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i] == 1 ? 1 : -1;
        if (map.has(sum)) {
            res = Math.max(i - map.get(sum), res);
        } else {
            map.set(sum, i);
        }
    }
    return res;
};

2177 找到和为给定整数的三个连续整数

时间：2022-03-08

var sumOfThree = function (num) {
    const n = num / 3;
    if (num%3 !== 0) return [];
    else return [n - 1, n, n + 1];
};

1754 构造字典序最大的合并字符串

时间：2022-03-08

真难啊这道题，居然只能打败一点点

var largestMerge = function (word1, word2) {
    let i = 0;
    let j = 0;
    const merge = [];
    while (i < word1.length && j < word2.length) {
        if (word1[i] > word2[j]) merge.push(word1[i++]);
        else if (word1[i] < word2[j]) merge.push(word2[j++]);
        else {
            merge.push(word1[i]);
            let m = i + 1;
            let n = j + 1;
            let flag = false;
            while (m < word1.length && n < word2.length) {
                if (word1[m] < word2[n]) {
                    j++;
                    flag = true;
                    break;
                } else if (word1[m] > word2[n]) {
                    i++;
                    flag = true;
                    break;
                }
                m++;
                n++;
            }
            if (flag == false) {
                if (m < word1.length) i++;
                else if (n < word2.length) j++;
                else i++;
            }
        }
    }
    if (i < word1.length) merge.push(word1.substring(i));
    if (j < word2.length) merge.push(word2.substring(j));
    return merge.join('');
};

或者直接用api库，这样子就快很多了。

var largestMerge = function (word1, word2) {
    let i = 0,
        j = 0;
    let res = '';
    while (i < word1.length && j < word2.length) {
        if (word1.substr(i) < word2.substr(j)) {
            res += word2[j];
            j += 1;
        } else {
            res += word1[i];
            i += 1;
        }
    }
    res += word1.substr(i) + word2.substr(j);
    return res;
};

743 网络延迟时间

时间：2022-03-09

直接击败百分之百的人，实属有点牛逼的。

Dijkstra，但是难也是真的难啊，怎么会这么难啊。下次我不一定能够写得出来，真的有点龙鸣的。

var networkDelayTime = function (times, n, k) {
    const INF = Number.MAX_SAFE_INTEGER;
    const g = new Array(n).fill(INF).map(() => new Array(n).fill(INF));
    for (let t of times) g[t[0] - 1][t[1] - 1] = t[2];
    // 从第k个节点（源点）到第i个节点的的距离
    const dist = Array.from(g[k - 1]);
    dist[k - 1] = 0;
    // 节点是否被用过的
    const used = new Array(n).fill(false);
    //共有n轮，每轮确定一个节点
    for (let i = 0; i < n; i++) {
        let pos = -1;
        let min = INF;
        // 找到该轮中未确定且距离k节点最小的节点位置pos
        for (let j = 0; j < n; j++) {
            if (!used[j] && dist[j] < min) {
                pos = j;
                min = dist[j];
            }
        }
        if (pos == -1) break;
        used[pos] = true;
        for (let j = 0; j < n; j++) {
            if (!used[j]) {
                dist[j] = Math.min(dist[j], dist[pos] + g[pos][j]);
            }
        }
    }
    let ans = Math.max(...dist);
    return ans == INF ? -1 : ans;
};

1588 所有奇数长度子数组的和

时间：2022-03-09

又是一道前缀和，真有你的，数学方法就不看了，这个前缀和能掌握就已经谢天谢地了

var sumOddLengthSubarrays = function (arr) {
    let sum = 0;
    const preSum = arr.map((v) => (sum += v));
    let res = 0;
    for (let i = 0; i < arr.length; i++) {
        for (let j = i; j < arr.length; j += 2) {
            res += preSum[j] - preSum[i] + arr[i];
        }
    }
    return res;
};

用上计数排序？或者桶排序的特性？计数，然后按照从小到大再遍历，如果不相同，就

var heightChecker = function (heights) {
    const cnt = new Array(101).fill(0);
    for (let h of heights) cnt[h]++;
    let res = 0;
    let j = 0;
    for (let i = 1; i < cnt.length; i++) {
        while (cnt[i]-- > 0) {
            if (heights[j++] != i) res++;
        }
    }
    return res;
};

152 乘积最大子数组

时间：2022-03-09

妈的，写了一个小时，还是在参考题解的情况下，但是写的和题解不一样，他那种太简单了，一般人根本写不出来，还是回归动态规划的一般解法好了。

var maxProduct = function (nums) {
    const n = nums.length;
    if (n == 1) return nums[0];
    // maxArr[i]最大连续正数，minArr最大连续负数
    const maxArr = new Array(n).fill(0);
    const minArr = new Array(n).fill(0);
    if (nums[0] > 0) maxArr[0] = nums[0];
    else minArr[0] = nums[0];
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > 0) {
            maxArr[i] = Math.max(maxArr[i - 1] * nums[i], nums[i]);
            minArr[i] = minArr[i - 1] * nums[i];
        } else if (nums[i] == 0) {
            maxArr[i] = 0;
            minArr[i] = 0;
        } else if (nums[i] < 0) {
            maxArr[i] = Math.max(minArr[i - 1] * nums[i], nums[i]);
            minArr[i] = Math.min(maxArr[i - 1] * nums[i], nums[i]);
        }
    }
    return Math.max(...maxArr);
};

空间O(n)降为O(1)，又好又快，又好又快啊！

var maxProduct = function (nums) {
    const n = nums.length;
    if (n == 1) return nums[0];
    // maxArr[i]最大连续正数，minArr最大连续负数
    let maxArr = 0;
    let minArr = 0;
    if (nums[0] > 0) maxArr = nums[0];
    else minArr = nums[0];
    let tmpmax, tmpmin;
    let res = maxArr;
    for (let i = 1; i < nums.length; i++) {
        tmpmax = maxArr;
        tmpmin = minArr;
        if (nums[i] > 0) {
            tmpmax = Math.max(maxArr * nums[i], nums[i]);
            tmpmin = Math.min(minArr * nums[i], nums[i]);
        } else if (nums[i] == 0) {
            tmpmax = 0;
            tmpmin = 0;
        } else {
            tmpmax = Math.max(minArr * nums[i], nums[i]);
            tmpmin = Math.min(maxArr * nums[i], nums[i]);
        }
        maxArr = tmpmax;
        minArr = tmpmin;
        res = Math.max(res, maxArr);
    }
    return res;
};

589 N 叉树的前序遍历

时间：2022-03-10

递归

var preorder = function (root) {
    if (!root) return [];
    const res = [];
    const dfs = (root) => {
        res.push(root.val);
        for (let i of root.children) {
            i && dfs(i);
        }
    };
    dfs(root);
    return res;
};

迭代，简单

var preorder = function (root) {
    if (!root) return [];
    const st = [root];
    const res = [];
    while (st.length) {
        root = st.pop()
        res.push(root.val);
        for (let i = root.children.length - 1; i >= 0; i--) {
            root.children[i] && st.push(root.children[i]);
        }
    }
    return res;
};

165 比较版本号

时间：2022-03-10

var compareVersion = function (version1, version2) {
    // 处理，去掉前导零
    const arr1 = version1.split('.');
    for (let i = 0; i < arr1.length; i++) arr1[i] = parseInt(arr1[i]);
    const arr2 = version2.split('.');
    for (let i = 0; i < arr2.length; i++) arr2[i] = parseInt(arr2[i]);
    let i = 0,
        j = 0;
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] > arr2[j]) return 1;
        else if (arr1[i] < arr2[j]) return -1;
        i++;
        j++;
    }
    while (i < arr1.length) {
        if (arr1[i] != 0) return 1;
        i++;
    }
    while (j < arr2.length) {
        if (arr2[j] != 0) return -1;
        j++;
    }
    return 0;
};

80 删除有序数组中的重复项 II

时间：2022-03-10

真的尿了，这个居然就只击败了5%的时间，也不至于这么慢吧，明明也是双指针啊

var removeDuplicates = function (nums) {
    let cnt = 1;
    let left = 1;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] == nums[i - 1]) {
            if (cnt >= 2) continue;
            cnt++;
        } else {
            cnt = 1;
        }
        nums[left++] = nums[i];
    }
    nums.length = left;
};

2049 统计最高分的节点数目

时间：2022-03-11

不会，抄的

var countHighestScoreNodes = function (parents) {
    const n = parents.length;
    const children = new Array(n).fill(0).map(() => []);
    let maxScore = 0;
    let cnt = 0;
    for (let i = 0; i < n; i++) {
        const p = parents[i];
        if (p !== -1) children[p].push(i);
    }

    const dfs = (node) => {
        let score = 1;
        let sum = 1;
        for (const c of children[node]) {
            let t = dfs(c);
            score *= t;
            sum += t;
        }
        // 根节点上面那一坨
        if (node !== 0) {
            score *= n - sum;
        }
        if (score === maxScore) {
            cnt++;
        } else if (score > maxScore) {
            maxScore = score;
            cnt = 1;
        }
        return sum;
    };

    dfs(0);
    return cnt;
};

590 N 叉树的后序遍历

时间：2022-03-12

递归

var postorder = function (root) {
    if (!root) return [];
    const res = [];
    const dfs = (root) => {
        for (let i of root.children) {
            i && dfs(i);
        }
        res.push(root.val);
    };
    dfs(root)
    return res;
};

翻转迭代

var postorder = function (root) {
    if (!root) return [];
    const st = [root];
    const res = [];
    while (st.length) {
        root = st.pop()
        res.push(root.val);
        for (let i of root.children) {
            i && st.push(i);
        }
    }
    return res.reverse();
};

正常迭代，还是写不出来，就很尿

var postorder = function (root) {
    if (!root) return [];
    const st = [root];
    const res = [];
    const visited = new Set();
    while (st.length) {
        const node = st[st.length - 1];
        if (node.children.length === 0 || visited.has(node)) {
            st.pop();
            res.push(node.val);
            continue;
        }
        for (let i = node.children.length - 1; i >= 0; i--) {
            st.push(node.children[i]);
        }
        visited.add(node);
    }
    return res;
};

128 最长连续序列

时间：2022-03-12

这道题很有趣，虽然我想到了要用哈希表，但是我没想到用set表，好，我用了set表，发现这个时间复杂度还是O(n2)，结果原来是检查有没有比当前数字小的，如果没有，才会去while比当前数字大的，就感觉很巧妙，就很牛逼。

var longestConsecutive = function (nums) {
    let res = 0;
    const set = new Set(nums);
    let cnt = 1;
    for (let i of set) {
        if (!set.has(i - 1)) {
            let j = i + 1;
            while (set.has(j++)) {
                cnt++;
            }
        }
        if (cnt > res) res = cnt;
        cnt = 1;
    }
    return res;
};

1155 掷骰子的N种方法

时间：2022-03-12

回溯，这道题过不去，回溯适合需要求出所有的解的情况，而这里不需要，只需要返回所有解的个数，所以这里回溯显然是不合适的。

var numRollsToTarget = function (n, k, target) {
    let res = 0;
    const backtrace = (sum, index, num) => {
        if (num > n || sum > target) return;
        if (sum == target) {
            res++;
            return;
        }
        for (let i = index; i <= k; i++) {
            backtrace(sum + i, index, num + 1);
        }
    };
    backtrace(0, 1, 0);
    return res;
};

动态规划，dp[i][j]表示投掷i个骰子，和为j的方法数量。

var numRollsToTarget = function (n, k, target) {
    const dp = new Array(n + 1).fill(0).map(() => new Array(target + 1).fill(0));
    for (let i = 1; i <= Math.min(target, k); i++) dp[1][i] = 1;
    for (let i = 2; i <= n; i++) {
        for (let j = i; j <= target; j++) {
            for (let m = 1; m < j && m <= k; m++) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j - m]) % (1e9 + 7);
            }
        }
    }
    return dp[n][target];
};

6031 找出数组中的所有 K 近邻下标

时间：2022-03-13

周赛第一题简单题，也是唯一一道做出来的，我还是太菜了嗷

var findKDistantIndices = function (nums, key, k) {
    const arr = [];
    for (let i = 0; i < nums.length; i++) {
        if (key == nums[i]) {
            arr.push(i);
        }
    }
    const res = [];
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            if (Math.abs(arr[j] - i) <= k) {
                res.push(i);
                break;
            }
        }
    }
    return res;
};

5203 统计可以提取的工件

时间：2022-03-13

周赛第二题，靠狗季的帮忙才做出来，主要坑是给的第一个参数tm没用，还害得我错了两次

var digArtifacts = function (n, artifacts, dig) {
    const cnt = new Array(artifacts.length).fill(0);
    const map = new Map();
    for (let i = 0; i < artifacts.length; i++) {
        const r1 = artifacts[i][0];
        const c1 = artifacts[i][1];
        const r2 = artifacts[i][2];
        const c2 = artifacts[i][3];
        for (let r = r1; r <= r2; r++) {
            for (let c = c1; c <= c2; c++) {
                map.set(r + '.' + c, i);
                cnt[i] += 1;
            }
        }
    }
    let res = 0;
    for (let di of dig) {
        const d = di[0] + '.' + di[1];
        if (!map.has(d)) continue;
        const idx = map.get(d);
        map.delete(d);
        cnt[idx] -= 1;
        if (cnt[idx] === 0) res += 1;
    }
    return res;
};

5227 K 次操作后最大化顶端元素

时间：2022-03-13

没有a出来，非常的可惜，瞎JB硬测试，就差最后一个例子，也算是满足了，问题不大。这个是抄别人的。

var maximumTop = function (nums, k) {
    const n = nums.length;
    if (k == 0) return nums[0];
    if (n == 1)
        if (k & 1) return -1;
        else return nums[0];
    let max = -1;
    for (let x of nums) max = Math.max(max, x);
    if (k > n) return max;
    max = -1;
    for (let i = 0; i < k - 1; i++) {
        max = Math.max(max, nums[i]);
    }
    if (k < n) max = Math.max(max, nums[k]);
    return max;
};

银联01 回文链表

时间：2022-03-13

也只会这种方法了，这也不能算简单题啊，挺难的。

var isPalindrome = function (head) {
    const vals = [];
    while (head !== null) {
        vals.push(head.val);
        head = head.next;
    }
    let flag = 0;
    for (let i = 0, j = vals.length - 1; i < j; ++i, --j) {
        if (vals[i] !== vals[j]) {
            if (flag == 0) {
                if (vals[i + 1] === vals[j]) {
                    flag = 1;
                    i++;
                    continue;
                }
                if (vals[i] === vals[j - 1]) {
                    flag = 1;
                    j--;
                    continue;
                }
                return false;
            }
            return false;
        }
    }
    return true;
};

银联03 理财产品

时间：2022-03-13

这辈子的命都搭进去了，累死，真的，我tm写这题目快花了三个小时了，一直是想错的，没有转过来，真有我的，妈的。

var maxInvestment = function (product, limit) {
    product.sort((a, b) => b - a);
    const mod = 1e9 + 7;
    product.push(0);
    const n = product.length;
    let start = 0;
    let len = 0;
    let res = 0;
    for (let i = 0; i < n - 1; i++) {
        if (product[i] == product[i + 1]) continue;
        len = i - start + 1 + len;
        for (let j = product[i]; j > product[i + 1]; j--) {
            const num = Math.min(len, limit);
            res = (res + j * num) % mod;
            limit -= num;
            if (limit == 0) return res;
        }
        start = i + 1;
    }
    return res;
};

599 两个列表的最小索引总和

时间：2022-03-14

谢邀，这个简单

var findRestaurant = function (list1, list2) {
    const map = new Map();
    for (let i = 0; i < list1.length; i++) {
        map.set(list1[i], i);
    }
    let res = [];
    let min = Infinity;
    for (let i = 0; i < list2.length; i++) {
        if (map.has(list2[i])) {
            const tmp = i + map.get(list2[i]);
            if (tmp < min) {
                min = tmp;
                res = [list2[i]];
            } else if (tmp == min) {
                res.push(list2[i]);
            }
        }
    }
    return res;
};

2044 统计按位或能得到最大值的子集数目

时间：2022-03-15

谢邀，子集问题，一把过

var countMaxOrSubsets = function (nums) {
    const n = nums.length;
    nums.sort((a, b) => b - a);
    let ans = 0;
    let max = -Infinity;
    const backtrace = (path, index, res) => {
        if (res > max) {
            max = res;
            ans = 1;
        } else if (res == max) {
            ans++;
        }
        for (let i = index; i < n; i++) {
            path.push(nums[i]);
            backtrace(path, i + 1, res | nums[i]);
            path.pop();
        }
    };
    backtrace([], 0, 0);
    return ans;
};

1712 将数组分成三个子数组的方案数

时间：2022-03-15

写了一个小时，真的搞，还是在参考题解的情况下，二分法，但是[0,0,0]这种情况特别恶心，要注意小心。

var waysToSplit = function (nums) {
    const n = nums.length;
    let sum = 0;
    const preSum = nums.map((value) => (sum += value));
    let res = 0;
    const mod = 1e9 + 7;
    const t = Math.floor(preSum[n - 1] / 3);
    let m = 1;
    for (let l = 0; l < n - 2 && preSum[l] <= t; l++) {
        const leftSum = preSum[l];
        m = Math.max(m, l + 1);
        while (m < n && preSum[m] - leftSum < leftSum) m++;
        if (m == n) break;
        let low = m,
            high = n - 2;
        while (low <= high) {
            const mid = Math.floor((low + high) / 2);
            if (preSum[n - 1] - preSum[mid] < preSum[mid] - leftSum) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        res += high - m + 1;
    }
    return res % mod;
};

三指针的方法，真的牛，这里r也需要记录，真的困难。

var waysToSplit = function (nums) {
    const n = nums.length;
    let sum = 0;
    const preSum = nums.map((value) => (sum += value));
    let res = 0;
    const mod = 1e9 + 7;
    const t = Math.floor(preSum[n - 1] / 3);
    let m = 1;
    let r = 1;
    for (let l = 0; l < n - 2 && preSum[l] <= t; l++) {
        const leftSum = preSum[l];
        m = Math.max(m, l + 1);
        while (m < n - 1 && preSum[m] - leftSum < leftSum) m++;
        r = Math.max(m, r);
        while (r < n - 1 && preSum[n - 1] - preSum[r] >= preSum[r] - leftSum) r++;
        res += r - m;
    }
    return res % mod;
};

405 数字转换为十六进制数

时间：2022-03-15

var toHex = function (num) {
    if (num === 0) {
        return '0';
    }
    const arr = [];
    for (let i = 7; i >= 0; i--) {
        const val = (num >> (4 * i)) & 0xf;
        if (arr.length > 0 || val > 0) {
            const digit = val < 10 ? String.fromCharCode('0'.charCodeAt() + val) : String.fromCharCode('a'.charCodeAt() + val - 10);
            arr.push(digit);
        }
    }
    return arr.join('');
};

offer 03 数组中重复的数字

时间：2022-03-16

开始刷剑指Offer的题目了

var findRepeatNumber = function (nums) {
    const set = new Set();
    for (let i of nums) {
        if (set.has(i)) return i;
        set.add(i);
    }
    return;
};

offer 04 二维数组中的查找

时间：2022-03-16

这道题写过，但是现在还是不会，尿了，方法就是从右上角搜索，这样子就能够判断大小怎么移动了。

var findNumberIn2DArray = function (matrix, target) {
    const m = matrix.length;
    if (m == 0) return false;
    const n = matrix[0].length;
    if (n == 0) return false;
    let x = 0,
        y = n - 1;
    while (x < m && y >= 0) {
        if (target == matrix[x][y]) return true;
        else if (target < matrix[x][y]) y--;
        else x++;
    }
    return false;
};

offer 06 从尾到头打印链表

时间：2022-03-16

啊这，官解居然不是这种方法，而是用栈的方法，这我没想到啊。

var reversePrint = function (head) {
    const res = [];
    while (head) {
        res.push(head.val);
        head = head.next;
    }
    return res.reverse();
};

用栈，不过对于js来说这种方法确实没啥用处

var reversePrint = function (head) {
    const res = [];
    const st = [];
    while (head) {
        st.push(head.val);
        head = head.next;
    }
    while (st.length) {
        res.push(st.pop());
    }
    return res;
};

offer 07 重建二叉树

时间：2022-03-16

谢邀，和105题目一模一样，又写了一遍

var buildTree = function (preorder, inorder) {
    if (!preorder.length) return null;
    const rootVal = preorder.shift();
    const root = new TreeNode(rootVal);
    const index = inorder.indexOf(rootVal);
    root.left = buildTree(preorder.slice(0, index), inorder.slice(0, index));
    root.right = buildTree(preorder.slice(index), inorder.slice(index + 1));
    return root;
};

720 词典中最长的单词

时间：2022-03-17

抄的官解，题目都看不懂，还有一种字典树的解法。

var longestWord = function (words) {
    words.sort((a, b) => {
        if (a.length !== b.length) {
            return a.length - b.length;
        } else {
            return b.localeCompare(a);
        }
    })
    console.log(words)
    let longest = '';
    let set = new Set();
    set.add('');
    const n = words.length;
    for (let i = 0; i < n; i++) {
        const word = words[i];
        if (set.has(word.slice(0, word.length - 1))) {
            set.add(word);
            longest = word;
        }
    }
    return longest;
};

我tm直接我tm抄袭

var longestWord = function(words) {
    const trie = new Trie();
    for (const word of words) {
        trie.insert(word);
    }
    let longest = "";
    for (const word of words) {
        if (trie.search(word)) {
            if (word.length > longest.length || (word.length === longest.length && word.localeCompare(longest) < 0)) {
                longest = word;
            }
        }
    }
    return longest;
};

class Node {
    constructor() {
        this.children = {};
        this.isEnd = false;
    }
}

class Trie {
    constructor() {
        this.children = new Node();
        this.isEnd = false;
    }

    insert(word) {
        let node = this;
        for (let i = 0; i < word.length; i++) {
            const ch = word[i];
            const index = ch.charCodeAt() - 'a'.charCodeAt();
            if (!node.children[index]) {
                node.children[index] = new Node();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    search(word) {
        let node = this;
        for (let i = 0; i < word.length; i++) {
            const ch = word[i];
            const index = ch.charCodeAt() - 'a'.charCodeAt();
            if (!node.children[index] || !node.children[index].isEnd) {
                return false;
            }
            node = node.children[index];
        }
        return node && node.isEnd;
    }
}

offer 09 用两个栈实现队列

时间：2022-03-17

做过一模一样的，所以这题轻轻松松

var CQueue = function () {
    this.input = [];
    this.out = [];
};

/**
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function (value) {
    this.input.push(value);
};

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function () {
    if (this.out.length) {
        return this.out.pop();
    }
    while (this.input.length) {
        this.out.push(this.input.pop());
    }
    return this.out.length == 0 ? -1 : this.out.pop();
};

offer 10 斐波那契数列

时间：2022-03-17

迭代，比递归方便，居然还有个logn的方法，什么快速矩阵幂？鬼才看

var fib = function (n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    let i = 1,
        j = 0;
    let tmp = 0;
    for (let x = 1; x < n; x++) {
        tmp = i;
        i += j;
        j = tmp;
        i %= 1e9 + 7;
    }
    return i;
};

offer 10 II 青蛙跳台阶问题

时间：2022-03-17

也是老题了，和70一样

var numWays = function (n) {
    if (n == 0) return 1;
    const dp = new Array(n + 1).fill(1);
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
        dp[i]%=(1e9 + 7);
    }
    return dp[n] ;
};

offer 11 旋转数组的最小数字

时间：2022-03-17

这个难中难了属于是。

var minArray = function (nums) {
    const n = nums.length;
    let l = 0,
        r = n - 1;
    while (l < r) {
        const mid = Math.floor((l + r) / 2);
        if (nums[mid] < nums[r]) {
            r = mid;
        } else if (nums[mid] == nums[r]) {
            r--;
        } else {
            l = mid + 1;
        }
    }
    return nums[l];
};