Leetcode-20

不想动了，慢慢动吧，代码随想录算是二刷完了吧，后面没怎么写了，都是看一遍过了，不想动，真的好累，每天花在算法上的时间真不少了，就看命吧。

offer II 057 值和下标之差都在给定的范围内

时间：2022-04-13

甚至可以无脑先暴力一遍，至少能过

var containsNearbyAlmostDuplicate = function (nums, k, t) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j <= i + k && j < nums.length; j++) {
            if (Math.abs(nums[j] - nums[i]) <= t) return true;
        }
    }
    return false;
};

这个太抽象了兄弟，桶排序，一共有t+1个桶，第一个桶存的是0-t的数字，第二个桶存的是t+1-2t数字，依次类推，如果获取的ID在同一个桶中，那么就是找到了，要不然去找ID+1的桶和ID-1的桶，判断距离是是不是小于t，这什么神仙想法。

var containsNearbyAlmostDuplicate = function (nums, k, t) {
    const n = nums.length;
    const map = new Map();
    const getID = (x, w = t + 1) => {
        return x < 0 ? Math.floor((x + 1) / w) - 1 : Math.floor(x / w);
    };
    for (let i = 0; i < n; ++i) {
        const x = nums[i];
        const id = getID(x);
        if (map.has(id)) return true;
        if (map.has(id - 1) && Math.abs(x - map.get(id - 1)) <= t) return true;
        if (map.has(id + 1) && Math.abs(x - map.get(id + 1)) <= t) return true;
        map.set(id, x);
        if (i >= k) map.delete(getID(nums[i - k]));
    }
    return false;
};

offer II 058 日程表

时间：2022-04-13

暴力法，居然都做不出来，我真的拉了

var MyCalendar = function () {
    this.arr = [];
};

/**
 * @param {number} start
 * @param {number} end
 * @return {boolean}
 */
MyCalendar.prototype.book = function (start, end) {
    for (let [s, e] of this.arr) {
        if (!(start >= e || end <= s)) return false;
    }
    this.arr.push([start, end]);
    return true;
};

不是吧，看都看不懂，抄的那个太迷惑了，直接去掉了，就是用start来找到已有区间的开始值的左边，反正就是二分查找吧，找到比他小的那个

var MyCalendar = function () {
    this.arr = [];
};
MyCalendar.prototype.findInsertIndex = function (start) {
    let left = 0;
    let right = this.arr.length - 1;
    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        if (this.arr[mid][0] < start) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left;
};

MyCalendar.prototype.book = function (start, end) {
    const arr = this.arr;
    let t = this.findInsertIndex(start);
    if ((arr.length && t > 0 && start < this.arr[t - 1][1]) || (this.arr[t] && end > this.arr[t][0])) {
        return false;
    }
    this.arr.splice(t, 0, [start, end]);
    return true;
};

1672 最富有客户的资产总量

时间：2022-04-14

什么简单模拟题

var maximumWealth = function (accounts) {
    let res = -Infinity;
    let max;
    for (let acc of accounts) {
        max = acc.reduce((p, v) => p + v, 0);
        if (max > res) res = max;
    }
    return res;
};

offer II 059 数据流的第 K 大数值

时间：2022-04-14

这里用到了小根堆，在总集合里面提到了，这里就不重复出现了。

用小根堆排序前K个大的，加入的val大于第k个大的，就弹出顶部，然后添加进去。

var KthLargest = function (k, nums) {
    // 堆大小
    this.size = k;
    this.minHeap = new MinHeap();
    // 把数据都添加到堆中
    for (const x of nums) {
        this.add(x);
    }
};

/**
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function (val) {
    if (this.minHeap.size() < this.size) {
        this.minHeap.offer(val);
    } else if (val > this.minHeap.peek()) {
        this.minHeap.poll();
        this.minHeap.offer(val);
    }
    return this.minHeap.peek();
};

这种题目为了以防万一，还需要做一下C++写法。

class KthLargest {
   public:
    // 从小排到大，（默认是从大排到小）
    priority_queue<int, vector<int>, greater<int>> q;
    int k;
    KthLargest(int k, vector<int>& nums) {
        this->k = k; // 这个指向我还不知道，js用多了，cpp全忘了
        for (int i : nums) {
            add(i); // 这个也不需要用this指向
        }
    }

    int add(int val) {
        q.push(val);
        if (q.size() > k) {
            q.pop();
        }
        return q.top();
    }
};

offer II 061 和最小的 k 个数对

时间：2022-04-14

烦死了，根本写不出来，什么垃圾最大堆，是我能写出来的？写了tm快两个小时，一直在找错，佛了

var kSmallestPairs = function (nums1, nums2, k) {
    const n = nums1.length;
    const m = nums2.length;
    // 求和最小的k 个数对 ： 最大堆
    // 由于数组升序，那么前k 大值 肯定在 nums1 和 nums2 的前k个数据中
    let sum;
    let maxHeap = new MaxHeap(k);
    // 添加一个数组 [sum,num1,num2]
    for (let i = 0; i < k && i < n; i++) {
        for (let j = 0; j < k && j < m; j++) {
            sum = nums1[i] + nums2[j];
            // 插入 arr 通过 sum 进行堆排序
            maxHeap.insert([sum, nums1[i], nums2[j]]);
        }
    }
    const result = [];
    for (let i = maxHeap.size; i >= 1; i--) {
        result.push([maxHeap.data[i][1], maxHeap.data[i][2]]);
    }
    result.sort((a, b) => {
        if (a[0] + a[1] == b[0] + b[1]) {
            if (a[0] == b[0]) return a[1] - b[1];
            else return a[0] - b[0]
        } else return a[0] + a[1] - b[0] - b[1]
    })
    return result;
};

class MaxHeap {
    constructor(maxSize) {
        this.data = [0];
        this.maxSize = maxSize;
        this.size = 0;
    }
    insert(arr) {
        if (this.size == this.maxSize && arr[0] >= this.data[1][0]) return;
        let index = ++this.size;
        while (index > 1) {
            const parentIndex = index >> 1;
            if (arr[0] > this.data[parentIndex][0]) {
                this.data[index] = this.data[parentIndex];
                index = parentIndex;
            } else break;
        }
        this.data[index] = arr;
        if (this.size > this.maxSize) this.delete();

    }
    delete() {
        const temp = this.data.pop();
        let index = 1;
        this.data[1] = temp;
        const size = --this.size;
        while (true) {
            const leftIndex = index * 2;
            const rightIndex = index * 2 + 1;
            let findIndex = index;
            if (leftIndex <= size && this.data[leftIndex][0] > this.data[findIndex][0]) findIndex = leftIndex;
            if (rightIndex <= size && this.data[rightIndex][0] > this.data[findIndex][0]) findIndex = rightIndex;
            // 则要交换
            if (index !== findIndex) {
                [this.data[index], this.data[findIndex]] = [this.data[findIndex], this.data[index]]
                index = findIndex;
            } else {
                break;
            }
        }
    }
}

offer II 064 神奇的字典

时间：2022-04-16

简朴的模拟法，反而是最快的。

var MagicDictionary = function () {
    this.dict = [];
};

/**
 * @param {string[]} dictionary
 * @return {void}
 */
MagicDictionary.prototype.buildDict = function (dictionary) {
    this.dict = dictionary;
};

/**
 * @param {string} searchWord
 * @return {boolean}
 */
MagicDictionary.prototype.search = function (searchWord) {
    for (let i = 0; i < this.dict.length; i++) {
        if (searchWord.length !== this.dict[i].length) continue;

        let diff = 0;
        for (let j = 0; j < searchWord.length; j++) {
            if (diff > 1) break;
            if (searchWord[j] !== this.dict[i][j]) diff++;
        }

        if (diff === 1) return true;
    }
    return false;
};

前缀树的感觉都非常的慢，我感觉不是很推荐写。

offer II 065 最短的单词编码

时间：2022-04-16

前缀树，但是这里用的其实是单词反向的前缀树，相当于后缀树了？

var minimumLengthEncoding = function (words) {
    const trie = {};
    for (let word of words) {
        let node = trie;
        for (let i = word.length - 1; i >= 0; i--) {
            const w = word[i];
            if (!node[w]) {
                node[w] = {};
            }
            node = node[w];
        }
    }
    let res = 0;
    const dfs = (root, depth) => {
        const values = Object.values(root)
        if (values.length==0) {
            res += depth;
            return;
        }
        for (let i of values) {
            dfs(i, depth + 1);
        }
    };
    dfs(trie, 1);
    return res;
};

老规矩，哈希，又快又好，又快又好啊！

var minimumLengthEncoding = function (words) {
    const set = new Set(words);
    for (let word of set) {
        for (let i = word.length - 1; i > 0; i--) {
            const subword =word.substring(i, word.length);
            if (set.has(subword)) {
                set.delete(subword);
            }
        }
    }
    let res = 0;
    for (let s of set) res += s.length + 1;
    return res;
};

offer II 067 最大的异或

时间：2022-04-16

当然是朴素想法先来一发了，可惜过不了，超时了。

var findMaximumXOR = function (nums) {
    let res = 0;
    for (let i = 0; i < nums.length - 1; i++) {
        for (let j = i; j < nums.length; j++) {
            res = Math.max(res, nums[i] ^ nums[j]);
        }
    }
    return res;
};

前缀树，很聪明的办法，但是也非常的费时间。就是用二进制从高位到低位建立前缀树，然后再重新遍历给定的nums，然后看二进制，如果是1，那么就去前缀树找0，如果是0，就去前缀树找1，这样子才能够最大。

var findMaximumXOR = function (nums) {
    const trie = {};
    // 建立前缀树
    for (let i of nums) {
        let node = trie;
        for (let j = 30; j >= 0; j--) {
            let attr = (i >> j) & 1;
            if (!node[attr]) {
                node[attr] = {};
            }
            node = node[attr];
        }
    }
    let res = 0;
    for (let i of nums) {
        let node = trie;
        let result = 0;
        for (let j = 30; j >= 0; j--) {
            let bit = (i >> j) & 1;
            let index = bit ^ 1;
            if (node[index]) {
                result |= 1 << j;
                node = node[index];
            } else {
                node = node[bit];
            }
        }
        res = Math.max(res, result);
    }
    return res;
};

821 字符的最短距离

时间：2022-04-19

简单题不简单的水平，错了好几次才试出来的水平

var shortestToChar = function (s, c) {
    const arr = [];
    for (let i = 0; i < s.length; i++) if (s[i] === c) arr.push(i);
    let i = 0;
    const res = new Array(arr.length);
    const len = arr.length;
    for (let j = 0; j < s.length; j++) {
        if (i < len - 1 && arr[i + 1] < j) i++;
        res[j] = Math.abs(j - arr[i]);
        if (len > 1 && i < len - 1) res[j] = Math.min(res[j], Math.abs(j - arr[i + 1]));
    }
    return res;
};

386 字典序排数

时间：2022-04-19

相当于又是找规律的题目，找的是字典序的排序方法，用递归是最好想的，虽然我是抄别人的，但是这个空间容易炸。

var lexicalOrder = function (n) {
    const res = [];
    const dfs = (start, end) => {
        for (let i = start; i <= n && i <= end; ++i) {
            res.push(i);
            dfs(10 * i, 10 * (i + 1) - 1);
        }
    };
    dfs(1, 9);
    return res;
};

这个迭代可是相当的难啊，稍微强行想了明白，我肯定是做不出来的，太难了这个，一般人估计写不出来吧

var lexicalOrder = function (n) {
    const res = [];
    let j = 1;
    for (let i = 0; i < n; i++) {
        res.push(j);
        if (j * 10 <= n) {
            j = j * 10;
        } else {
            while (j % 10 == 9 || j + 1 > n) j = Math.floor(j / 10);
            j++;
        }
    }
    return res;
};

819 最常见的单词

时间：2022-04-19

抄的，这个分词很妙，不用搞来搞去，先用正则替换成空格，然后用filter去过滤值为空格和在禁用词里面的，这个过滤空格的操作很重要，要不然可能过不去。放在这里在时间和空间上面都有提升，非常的不错。

var mostCommonWord = function (paragraph, banned) {
    const set = new Set(banned);
    const map = new Map();
    paragraph = paragraph.toLowerCase().replace(/[!?',;.]/g, ' ');
    const words = paragraph.split(' ').filter(word => word && !set.has(word));
    let res = 0;
    let max = 0;
    for (let w of words) {
            const val = (map.get(w) || 0) + 1;
            map.set(w, val);
            if (val > max) {
                max = val;
                res = w;
            }
    }
    return res;
};

offer II 069 山峰数组的顶部

时间：2022-04-19

听我说，谢谢你，因为有你，温暖了四季

var peakIndexInMountainArray = function (arr) {
    let l = 1,
        r = arr.length - 2;
    while (l <= r) {
        const mid = ((r - l) >> 1) + l;
        if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) return mid;
        else if (arr[mid] > arr[mid - 1]) l = mid + 1;
        else r = mid - 1;
    }
    return l;
};

offer II 070 按权重生成随机数

时间：2022-04-19

这种生成随机概率的题目没有一次是做出来的，都是tmd抄的，我也是佛了。

/**
 * @param {number[]} w
 */
var Solution = function (w) {
    pre = new Array(w.length).fill(0);
    pre[0] = w[0];
    for (let i = 1; i < w.length; ++i) {
        pre[i] = pre[i - 1] + w[i];
    }
    this.total = pre[w.length - 1];
};

/**
 * @return {number}
 */
Solution.prototype.pickIndex = function () {
    const x = Math.floor(Math.random() * this.total) + 1;
    const binarySearch = (x) => {
        let low = 0,
            high = pre.length - 1;
        while (low < high) {
            const mid = Math.floor((high - low) / 2) + low;
            if (pre[mid] < x) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    };
    return binarySearch(x);
};

offer II 073 狒狒吃香蕉

时间：2022-04-19

二分查找，范围是0到piles的最大值，用上Math.ceil，又快又好，又快又好啊

var minEatingSpeed = function (piles, h) {
    let l = 0,
        r = Math.max(...piles);
    while (l <= r) {
        const mid = l + ((r - l) >> 1);
        if (canFinish(piles, mid, h)) {
            r = mid - 1;
        } else l = mid + 1;
    }
    return l;
};
function canFinish(piles, speed, h) {
    let time = 0;
    for (let a of piles) {
        time +=  Math.ceil(a / speed)
    }
    return time <= h;
}

388 文件的最长绝对路径

时间：2022-04-20

抄的，然后改良了一下，变成栈的思想

var lengthLongestPath = function (input) {
    let res = 0,
        st = [];
    const arr = input.split('\n').map((a) => a.split('\t'));
    arr.forEach((a) => {
        while (a.length <= st.length) st.pop();
        const word = a[a.length - 1];
        st.push(word);
        if (word.indexOf('.') >= 0) res = Math.max(res, st.join('/').length);
    });
    return res;
};

824 山羊拉丁文

时间：2022-04-21

邪恶的山羊，邪恶的你我。好！

var toGoatLatin = function (sentence) {
    const arr = sentence.split(' ');
    let tmp = '';
    return arr.map((v, i) => {
        tmp += 'a';
        const first = v[0].toLocaleLowerCase();
        if (!(first === 'a' || first === 'e' || first === 'i' || first === 'o' || first === 'u')) {
            v = v.substring(1) + v[0];
        }
        return v + 'ma' + tmp;
    }).join(' ');
};

offer II 075 数组相对排序

时间：2022-04-21

简单题简单写，但也没感觉这么简单吧

var relativeSortArray = function (arr1, arr2) {
    const map = new Map();
    for (let i of arr1) map.set(i, (map.get(i) || 0) + 1);
    const res = [];
    for (let i of arr2) {
        if (map.has(i)) {
            for (let j = map.get(i); j > 0; j--) {
                res.push(i);
            }
            map.delete(i)
        }
    }
    const last = [];
    for (let m of map) {
        for (let j = m[1]; j > 0; j--) {
            last.push(m[0])
        }
    }
    return res.concat(last.sort((a, b) => a - b));
};

offer II 076 数组中的第 k 大的数字

时间：2022-04-21

先简单api排序来一发

var findKthLargest = function (nums, k) {
    nums.sort((a, b) => b - a);
    return nums[k - 1];
};

用堆排序，然后只用k次堆排就行了，又快又好，又快又好！

// 堆排序？
var findKthLargest = function (nums, k) {
    // 先初始化，建立大顶堆
    let len = nums.length;
    for (let i = Math.floor(len / 2); i >= 0; i--) {
        heapify(nums, i, len);
    }
    const n = nums.length;
    for (let i = n - 1; i >= n - k; i--) {
        // 交换根节点和末尾节点
        swap(nums, 0, i);
        len--;
        heapify(nums, 0, len);
    }
    return nums[n - k];
};

function heapify(arr, i, len) {
    // 堆调整
    // 2i+1是左节点，2i+2是右节点，最大值的下标为当前节点
    const left = 2 * i + 1,
        right = 2 * i + 2;
    let largest = i;

    // 判断子节点是否存在，并找出最大的那个
    if (left < len && arr[left] > arr[largest]) largest = left;
    if (right < len && arr[right] > arr[largest]) largest = right;

    // 如果最大值不等于父节点（就是子节点比父节点大），那么就进行交换，并进行
    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest, len);
    }
}

function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

offer II 077 链表排序

时间：2022-04-21

当然先用数组来摸一遍了，O(nlogn)时间复杂度，空间是O(n)

var sortList = function (head) {
    const arr = [];
    let cur = head;
    while (cur) {
        arr.push(cur.val);
        cur = cur.next;
    }
    arr.sort((a, b) => a - b);
    cur = head;
    let i = 0;
    while (cur) {
        cur.val = arr[i++];
        cur = cur.next;
    }
    return head;
};

归并排序，递归的版本，拉中拉了，空间

var sortList = function (head) {
    if (!head || head.next === null) return head;
    // 使用快慢指针找到中间节点
    let slow = head,
        fast = head.next;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // 分成前后两个链表
    let newList = slow.next;
    slow.next = null;
    // 对前后两个链表进行排序
    let left = sortList(head);
    let right = sortList(newList);
    // 将排序好的两个有序链表合并为一个链表
    let res = new ListNode(-1);
    let nHead = res;
    while (left !== null && right !== null) {
        if (left.val < right.val) {
            nHead.next = left;
            left = left.next;
        } else {
            nHead.next = right;
            right = right.next;
        }
        nHead = nHead.next;
    }
    nHead.next = left === null ? right : left;
    return res.next;
};

offer II 078 合并排序链表

时间：2022-04-21

这道题算不上难吧，就直接遍历合并就行了，分组合并有必要吗，可能快点吧。

var mergeKLists = function (lists) {
    if (lists.length == 0) return null;
    let res = lists[0];
    for (let i = 1; i < lists.length; i++) {
        res = merge(res, lists[i]);
    }
    return res;
};

function merge(left, right) {
    const prev = new ListNode(-1);
    let cur = prev;
    while (left && right) {
        if (left.val < right.val) {
            cur.next = left;
            left = left.next;
        } else {
            cur.next = right;
            right = right.next;
        }
        cur = cur.next
    }
    cur.next = left ? left : right;
    return prev.next;
}

好吧，快了不止一点，估计是数据量的长度都是差不多的，这样子分治的归并排序是能快很多的

/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
    if (lists.length == 0) return null;
    return mergeSort(lists, 0, lists.length - 1)
};

const mergeSort = (nums, left, right) => {
    if (left == right) return nums[left];
    const mid = Math.floor((left + right) / 2);
    const head1 = mergeSort(nums, left, mid);
    const head2 = mergeSort(nums, mid + 1, right);
    return merge(head1, head2)
}


function merge(left, right) {
    const prev = new ListNode(-1);
    let cur = prev;
    while (left && right) {
        if (left.val < right.val) {
            cur.next = left;
            left = left.next;
        } else {
            cur.next = right;
            right = right.next;
        }
        cur = cur.next
    }
    cur.next = left ? left : right;
    return prev.next;
}

396 旋转函数

时间：2022-04-22

直接一波模板带走，虽然是抄的，但是用上了reduce就很牛逼的样子

var maxRotateFunction = function (nums) {
    let f = nums.reduce((a, b, i) => a + b * i, 0),
        n = nums.length,
        sum = nums.reduce((a, b) => a + b);
    let res = f;
    for (let i = n - 1; i > 0; i--) {
        f += sum - n * nums[i];
        res = Math.max(res, f);
    }
    return res;
};

offer II 091 粉刷房子

时间：2022-04-22

这个思路倒是挺简单的，不过空间还能再优化一下

var minCost = function (costs) {
    const n = costs.length;
    const dp = new Array(n + 1).fill(0).map(() => new Array(3).fill(0));
    for (let i = 0; i < n; i++) {
        const num = costs[i];
        dp[i + 1][0] = Math.min(dp[i][1], dp[i][2]) + num[0];
        dp[i + 1][1] = Math.min(dp[i][0], dp[i][2]) + num[1];
        dp[i + 1][2] = Math.min(dp[i][0], dp[i][1]) + num[2];
    }
    return Math.min(...dp[n]);
};

省空间，速度反而又下降了

var minCost = function (costs) {
    const n = costs.length;
    let dp0 = 0,dp1 = 0,dp2 = 0,tmp0,tmp1,tmp2;
    for (let i = 0; i < n; i++) {
        const num = costs[i];
        tmp0 = Math.min(dp1, dp2) + num[0];
        tmp1 = Math.min(dp0, dp2) + num[1];
        tmp2 = Math.min(dp0, dp1) + num[2];
        dp0 = tmp0;
        dp1 = tmp1;
        dp2 = tmp2;
    }
    return Math.min(tmp0, Math.min(tmp1, tmp2));
};

offer II 092 翻转字符

时间：2022-04-22

抄的，还挺难想通的，dp应该就是代表最小的次数，如果是0，那么就可以把当前转化成1，或者把之前所有的数字1都转换成0，反正有点怪。

var minFlipsMonoIncr = function (s) {
    const n = s.length, dp = new Array(n + 1).fill(0);
    let cnt1 = 0;
    for (let i = 0; i < n; i++) {
        if (s[i] === '0') {
            dp[i + 1] = Math.min(dp[i] + 1, cnt1);
        } else {
            cnt1++;
            dp[i + 1] = dp[i];
        }
    }
    return dp[n];
};

还有个神仙写法，正则表达式的写法

字符串中的 10 打乱了递增顺序，要保证递增性只需要将其替换成 00、01、11 中任意一种，至于替换成哪一种不重要，因为总有一个合适的，重要的是每出现1个 10 翻转次数需要加 1。

因此要求最小翻转次数，只需要循环地把所有 10 全部剔除，并累加翻转次数即可

var minFlipsMonoIncr = function (s) {
    let c = 0;
    while (s.indexOf('10') > -1) s = s.replace(/10/g, () => (c++, ''));
    return c;
};

offer II 093 最长斐波那契数列

时间：2022-04-22

用暴力解法，就是无限循环找下一个，不过这个有点过于暴力了，有些浪费后面的东西了。

var lenLongestFibSubseq = function (arr) {
    const n = arr.length;
    let set = new Set(arr),
        count = 2,
        max = 0;
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            count = 2;
            let f1 = arr[i];
            let f2 = arr[j];
            let f3 = f1 + f2;
            while (set.has(f3)) {
                count++;
                if (count > max) max = count;
                f1 = f2;
                f2 = f3;
                f3 = f1 + f2;
            }
        }
    }
    return max;
};

有个动态规划的，其实整体上思路和上面的差不多，只不过利用起来了以往的经验值，k一定是小于i

解题思路 转移方程 dp[i][j]=dp[k][i]+1

var lenLongestFibSubseq = function (arr) {
    const n = arr.length,
        map = new Map();
    arr.forEach((v, i) => {
        map.set(v, i);
    });
    let max = 0,
        dp = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(2));
    for (let i = 0; i < arr.length - 1; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            let f2 = arr[i];
            let f3 = arr[j];
            let f1 = f3 - f2;
            if (f1 < f2 && map.has(f1)) {
                dp[i][j] = dp[map.get(f1)][i] + 1;
                max = Math.max(max, dp[i][j]);
            }
        }
    }
    return max;
};

offer II 094 最少回文分割

时间：2022-04-22

这道题还是比较难的，首先预处理回文字符串，先处理字符串中哪些是回文，注意这里的遍历顺序，i+1和j-1是在左下角，所以遍历顺序应该是从下往上，从左往右，这样子才有关联。然后就是动态规划了，dp表示当前最少分割的次数，如果当前回文字符串本身就是回文，那么就是0次切割。如果不是回文，则去前面找到回文，dp[i]=Math.min(dp[i],dp[j]+1)，0<j<i

var minCut = function (s) {
    const n = s.length,
        pre = new Array(n).fill(0).map(() => new Array(n).fill(true));
    for (let i = n - 1; i >= 0; i--) {
        for (let j = i + 1; j < n; ++j) {
            pre[i][j] = s[i] == s[j] && pre[i + 1][j - 1];
        }
    }
    const dp = new Array(n).fill(Number.MAX_SAFE_INTEGER);
    for (let i = 0; i < n; ++i) {
        if (pre[0][i]) {
            dp[i] = 0;
        } else {
            for (let j = 0; j < i; ++j) {
                if (pre[j + 1][i]) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
    }
    return dp[n - 1];
};

417 太平洋大西洋水流问题

时间：2022-04-27

经典岛屿问题，需要反向思维一下，水往高处流，就是要求两次，其他基本也没差。

var pacificAtlantic = function (heights) {
    const dirs = [
        [-1, 0],
        [1, 0],
        [0, -1],
        [0, 1]
    ];
    const m = heights.length;
    const n = heights[0].length;
    const pacific = new Array(m).fill(false).map(() => new Array(n).fill(false));
    const atlantic = new Array(m).fill(false).map(() => new Array(n).fill(false));
    const dfs = (row, col, ocean) => {
        if (ocean[row][col]) return;
        ocean[row][col] = true;
        for (const dir of dirs) {
            const newRow = row + dir[0],
                newCol = col + dir[1];
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] >= heights[row][col]) {
                dfs(newRow, newCol, ocean);
            }
        }
    };
    for (let i = 0; i < m; i++) {
        dfs(i, 0, pacific);
        dfs(i, n - 1, atlantic);
    }
    for (let j = 0; j < n; j++) {
        dfs(0, j, pacific);
        dfs(m - 1, j, atlantic);
    }
    const res = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (pacific[i][j] && atlantic[i][j]) {
                res.push([i, j]);
            }
        }
    }
    return res;
};

883 三维形体投影面积

时间：2022-04-27

简单题还是错了两次，有点拉胯

var projectionArea = function (grid) {
    const n = grid.length;
    let res1 = 0,
        res2 = 0,
        res = 0;
    for (let i = 0; i < n; i++) {
        res1 = 0, res2 = 0;
        for (let j = 0; j < n; j++) {
            res1 = Math.max(res1, grid[i][j]);
            res2 = Math.max(res2, grid[j][i]);
            if (grid[i][j] != 0) res++;
        }
        res += res1 + res2;
    }
    return res;
};

398 随机数索引

时间：2022-04-27

正常思路，用的哈希表，速度有点慢。

var Solution = function (nums) {
    const map = new Map();
    for (let [key, value] of nums.entries()) {
        if (!map.has(value)) {
            map.set(value, []);
        }
        map.get(value).push(key);
    }
    this.map = map;
};

/**
 * @param {number} target
 * @return {number}
 */
Solution.prototype.pick = function (target) {
    const arr = this.map.get(target);
    const index = Math.floor(Math.random() * arr.length);
    return arr[index];
};

什么水塘抽样法，这样子抽样之后返回的概率就是1/k，具体数学咱也不懂，相当于时间换空间了，速度还挺快，大概是哈希表建立和查询都费点时间，样本测试用例不多

var Solution = function(nums) {
    this.nums = nums;
};

Solution.prototype.pick = function(target) {
    let ans = 0;
    for (let i = 0, cnt = 0; i < this.nums.length; ++i) {
        if (this.nums[i] == target) {
            ++cnt; // 第 cnt 次遇到 target
            if (Math.floor(Math.random() * cnt) === 0) {
                ans = i;
            }
        }
    }
    return ans;
};

868 二进制间距

时间：2022-04-27

简单题简单写

var binaryGap = function (n) {
    let index = -1,
        res = 0;
    for (let i = 0; i < 31; i++) {
        if (1 & (n >> i)) {
            if (index == -1) {
                index = i;
            } else {
                res = Math.max(res, i - index);
                index = i;
            }
        }
    }
    return res;
};

当然官解写的更简单了

var binaryGap = function (n) {
    let index = -1,
        res = 0;
    for (let i =0; n != 0; i++) {
        if (1 & n) {
            if (index != -1) res = Math.max(res, i - index);
            index = i;
        }
        n >>= 1;
    }
    return res;
};

905 按奇偶排序数组

时间：2022-04-28

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

offer II 096 字符串交织

时间：2022-04-28

写不出来，抄的。动态规划，dp[i][j]表示s1前i个和s2前j个是否能够组成s3的前i+j个元素，为什么m是i+j+1呢，不行，还是想不明白为什么。

var isInterleave = function (s1, s2, s3) {
    const len1 = s1.length,
        len2 = s2.length,
        len3 = s3.length;
    if (len1 + len2 !== len3) return false;
    const dp = new Array(len1 + 1).fill(false).map(() => new Array(len2 + 1).fill(false));
    dp[0][0] = true
    for (let i = 0; i < len1; i++) dp[i + 1][0] = dp[i][0] && s3[i] == s1[i];
    for (let j = 0; j < len2; j++) dp[0][j + 1] = dp[0][j] && s3[j] == s2[j];
    for (let i = 0; i < len1; i++) {
        for (let j = 0; j < len2; j++) {
            const m = i + j + 1;
            dp[i + 1][j + 1] = dp[i][j + 1] && s1[i] == s3[m] || dp[i + 1][j] && s2[j] == s3[m];
        }
    }
    return dp[len1][len2];
};