LeetCode-11

二叉树还剩几题，接下来以回溯为主要的学习。回溯法可是我的心头大恨。

OK，回溯法学完了，确实长进非常多，接下来学习贪心，贪心的题量说实话也不少。

1078 Bigram 分词

刷题时间：2021-12-26

var findOcurrences = function (text, first, second) {
    const words = text.split(" ");
    const list = [];
    for (let i = 2; i < words.length; i++) {
        if (words[i - 2] === first && words[i - 1] === second) {
            list.push(words[i]);
        }
    }
    return list
};

669 修剪二叉搜索树

刷题时间：2021-12-26

这个有点难，估计我是写不出来的。

var trimBST = function (root, low, high) {
    if (!root) return null;
    if (root.val < low) return trimBST(root.right, low, high);
    if (root.val > high) return trimBST(root.left, low, high);
    root.left = trimBST(root.left, low, high);
    root.right = trimBST(root.right, low, high);
    return root;
};

108 将有序数组转换为二叉搜索树

刷题时间：2021-12-26

简单题，简单写

var sortedArrayToBST = function (nums) {
    const dfs = (left, right) => {
        if (left == right) {
            return new TreeNode(nums[left]);;
        }
        if(left>right){
            return null;
        }
        const mid = Math.floor((left + right) / 2);
        const root = new TreeNode(nums[mid]);
        root.left = dfs(left, mid - 1);
        root.right = dfs(mid + 1, right);
        return root;
    };
    return dfs(0, nums.length - 1);
};

538 把二叉搜索树转换为累加树

刷题时间：2021-12-26

这个思路转换成数组就能够想明白。

var convertBST = function (root) {
    let pre = 0;
    const ReverseInOrder = (cur) => {
        if (cur) {
            ReverseInOrder(cur.right);
            cur.val += pre;
            pre = cur.val;
            ReverseInOrder(cur.left);
        }
    };
    ReverseInOrder(root);
    return root;
};

825 适龄的朋友

刷题时间：2021-12-27

垃圾时间O(n^2)

var numFriendRequests = function (ages) {
    ages.sort((a, b) => b - a);
    const len = ages.length;
    let res = 0;
    for (let i = 0; i < len; i++) {
        const x = ages[i];
        for (let j = i + 1; j < len; j++) {
            const y = ages[j];
            if (y <= 0.5 * x + 7) {
                continue;
            }
            if (y <= 14) break;
            if (x == y) {
                res++;
            }
            res++;
        }
    }
    return res;
};

双指针，O(nlogn)

var numFriendRequests = function (ages) {
    const n = ages.length;
    ages.sort((a, b) => a - b);
    let left = 0,
        right = 0,
        ans = 0;
    for (const age of ages) {
        if (age < 15) {
            continue;
        }
        while (ages[left] <= 0.5 * age + 7) {
            ++left;
        }
        while (right + 1 < n && ages[right + 1] <= age) {
            ++right;
        }
        ans += right - left;
    }
    return ans;
};

216 组合总和 III

刷题时间：2021-12-27

在组合的基础上改的，还不错，空间和速度基本上都是顶格的。

var combinationSum3 = function (k, n) {
    const res = [];
    const backtrack = (arr, index, sum) => {
        if (sum > n || arr.length > k) {
            return;
        }
        if (sum == n && arr.length == k) {
            res.push(arr.slice());
            return;
        }
        for (let i = index; i <= 9 - (k - arr.length) + 1; i++) {
            arr.push(i);
            backtrack(arr, i + 1, sum + i);
            arr.pop();
        }
    };
    backtrack([], 1, 0);
    return res;
};

131 分割回文串

刷题时间：2021-12-27

回溯的模板确实都差不多，这个是不是回文串的时候需要在横向的时候直接比较。

var partition = function (s) {
    const res = [];
    const len = s.length;
    const backtrack = (path, index) => {
        if (index >= len) {
            res.push(path.slice());
            return;
        }
        for (let i = index; i < len; i++) {
            if (!isPalindrome(s, index, i)) continue;
            path.push(s.substring(index, i + 1));
            backtrack(path, i + 1);
            path.pop();
        }
    };

    const isPalindrome = (s, start, end) => {
        for (let i = start, j = end; i < j; i++, j--) {
            if (s[i] != s[j]) {
                return false;
            }
        }
        return true;
    };
    backtrack([], 0);
    return res;
};

93 复原 IP 地址

刷题时间：2021-12-28

这个题目和上面那个确实很像，分割问题确实可以看成组合问题嗷，不知道还能不能再优化一下

var restoreIpAddresses = function (s) {
    const res = [];
    const len = s.length;
    const backtrack = (path, index) => {
        if (path.length >= 4) return;
        if (index >= len && path.length == 4) {
            res.push(path.join('.'));
            return;
        }

        for (let i = index; i < len; i++) {
            if (i - index >= 3 || !isLegal(s, index, i)) continue;

            path.push(s.substring(index, i + 1));
            backtrack(path, i + 1);
            path.pop();
        }
    };
    const isLegal = (s, l, r) => {
        if (r - l > 0 && s[l] == '0') {
            return false;
        }
        for (let i = l; i <= r; i++) {
            if (!(s[i] >= '0' && s[i] <= '9')) {
                return false;
            }
        }
        const num = parseInt(s.substring(l, r + 1));
        if (num > 255 || num < 0) {
            return false;
        }
        return true;
    };
    backtrack([], 0);
    return res;
};

看到一个新的活，这活也太好了吧，有个+str的操作，就会变成数字，太牛了，如果里面有其他的数字，那么就会变成false，不知道哪里来的骚想法。

var restoreIpAddresses = function(s) {
    const res = [], path = [];
    backtracking(0, 0)
    return res;
    function backtracking(i) {
        const len = path.length;
        if(len > 4) return;
        if(len === 4 && i === s.length) {
            res.push(path.join("."));
            return;
        }
        for(let j = i; j < s.length; j++) {
            const str = s.substr(i, j - i + 1);
            if(str.length > 3 || +str > 255) break;
            if(str.length > 1 && str[0] === "0") break;
            path.push(str);
            backtracking(j + 1);
            path.pop()
        }
    }
};

191 递增子序列

刷题时间：2021-12-28

这题不能用上面那些重复的子集II这种来写，因为不能排序，所以序列不是按序的，可以用set来判断之前横向的是否用过了。

使用slice比array.from要快

var findSubsequences = function (nums) {
    const res = [];
    const len = nums.length;
    const path = [];
    const backtrack = (index) => {
        if (path.length >1) {
            res.push(path.slice());
        }
        let arr = [];
        for (let i = index; i < len; i++) {
            if ((path.length && nums[i] < path[path.length - 1]) || arr[nums[i] + 100]) continue;
            path.push(nums[i]);
            arr[nums[i] + 100] = 1;
            backtrack(i + 1);
            path.pop();
        }
    };
    backtrack(0);
    return res;
};

1995 统计特殊四元组

刷题时间：2021-12-29

这个实在是秒，估计我只能想到O(n3)这种方法，这种应该是想不到的。

var countQuadruplets = function (nums) {
    let n = nums.length;
    let ans = 0;
    const cnt = new Map();
    // 这个逆序反倒是关键的部分，这样子只有遍历一遍就行了
    for (let b = n - 3; b >= 1; --b) {
        for (let d = b + 2; d < n; ++d) {
            cnt.set(nums[d] - nums[b + 1], (cnt.get(nums[d] - nums[b + 1]) || 0) + 1);
        }
        for (let a = 0; a < b; ++a) {
            let sum = nums[a] + nums[b];
            if (cnt.has(sum)) {
                ans += cnt.get(sum);
            }
        }
    }
    return ans;
};

332 重新安排行程

刷题时间：2021-12-29

直接复制粘贴抄袭，困难题睡大觉了

var findItinerary = function (tickets) {
    let result = ['JFK'];
    let map = {};

    for (const tickt of tickets) {
        const [from, to] = tickt;
        if (!map[from]) {
            map[from] = [];
        }
        map[from].push(to);
    }
    for (const city in map) {
        // 对到达城市列表排序
        map[city].sort();
    }

    const backtracing = () => {
        if (result.length === tickets.length + 1) {
            return true;
        }
        const lastCityTickets = map[result[result.length - 1]];

        if (!lastCityTickets || !lastCityTickets.length) {
            return false;
        }
        for (let i = 0; i < lastCityTickets.length; i++) {
            let city = lastCityTickets[i];
            // 删除已走过航线，防止死循环
            lastCityTickets.splice(i, 1);
            result.push(city);
            if (backtracing()) {
                return true;
            }
            result.pop();
            lastCityTickets.splice(i, 0, city);
        }
    };
    backtracing();
    return result;
};

846 一手顺子

刷题时间：2021-12-30、

没看懂题目，直接抄了解析

var isNStraightHand = function (hand, groupSize) {
    const n = hand.length;
    if (n % groupSize !== 0) {
        return false;
    }
    hand.sort((a, b) => a - b);
    const cnt = new Map();
    for (const x of hand) {
        cnt.set(x, (cnt.get(x) || 0) + 1);
    }
    for (const x of hand) {
        if (!cnt.has(x)) {
            continue;
        }
        for (let j = 0; j < groupSize; j++) {
            const num = x + j;
            if (!cnt.has(num)) {
                return false;
            }
            cnt.set(num, cnt.get(num) - 1);
            if (cnt.get(num) == 0) {
                cnt.delete(num);
            }
        }
    }
    return true;
};

51 N 皇后

刷题时间：2021-12-30

经典回溯问题，就是判断稍微费点劲，问题不是很大。

var solveNQueens = function (n) {
    const res = [];
    const backtrack = (path, row) => {
        if (row == n) {
            let arr = [];
            path.forEach((row) => {
                arr.push(row.join(''));
            });
            res.push(arr.slice());
            return;
        }
        for (let col = 0; col < n; col++) {
            if (!isValid(path, row, col)) continue;
            path[row][col] = 'Q';
            backtrack(path, row + 1);
            path[row][col] = '.';
        }
    };
    const isValid = (path, row, col) => {
        for (let i = 0; i < row; i++) {
            if (path[i][col] == 'Q') {
                return false;
            }
        }
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (path[i][j] == 'Q') {
                return false;
            }
        }
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (path[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    };
    backtrack(
        new Array(n).fill('.').map(() => new Array(n).fill('.')),
        0
    );
    return res;
};

37 解数独

刷题时间：2021-12-30

抄的，多重回溯，感觉非常的爆炸，但看起来还行。

var solveSudoku = function (board) {
    function isValid(row, col, val, board) {
        let len = 9;
        // 行不能重复
        for (let i = 0; i < len; i++) {
            if (board[row][i] === val) {
                return false;
            }
        }
        // 列不能重复
        for (let i = 0; i < len; i++) {
            if (board[i][col] === val) {
                return false;
            }
        }
        let startRow = Math.floor(row / 3) * 3;
        let startCol = Math.floor(col / 3) * 3;

        for (let i = startRow; i < startRow + 3; i++) {
            for (let j = startCol; j < startCol + 3; j++) {
                if (board[i][j] === val) {
                    return false;
                }
            }
        }
        return true;
    }

    function backTracking() {
        for (let i = 0; i < 9; i++) {
            for (let j = 0; j < 9; j++) {
                if (board[i][j] !== '.') continue;
                for (let val = 1; val <= 9; val++) {
                    if (isValid(i, j, `${val}`, board)) {
                        board[i][j] = `${val}`;
                        if (backTracking()) {
                            return true;
                        }
                        board[i][j] = `.`;
                    }
                }
                return false;
            }
        }
        return true;
    }
    backTracking(board);
    return board;
};

507 完美数

刷题时间：2021-12-31

var checkPerfectNumber = function (num) {
    if (num == 1) return false;
    const size = Math.floor(Math.sqrt(num));
    const arr = [1];
    for (let i = 2; i <= size; i++) {
        if (num % i == 0) {
            arr.push(i);
            arr.push(num / i);
        }
    }
    const sum = arr.reduce((prev, curr) => prev + curr, 0);
    if (sum == num) return true;
    return false;
};

455 分发饼干

刷题时间：2021-12-31

居然没做出来，贪心我还是太菜了，思想是小饼干喂胃口小的，也就是要遍历小饼干

var findContentChildren = function (g, s) {
    g.sort((a, b) => a - b);
    s.sort((a, b) => a - b);
    let index = 0;
    for (let i = 0; i < s.length; i++) {
        if (index < g.length && g[index] <= s[i]) {
            index++;
        }
    }
    return index;
};

376 摆动序列

刷题时间：2021-12-31

不是这个也太难了吧，我一开始觉得这种子序列只能通过动态规划来完成，居然考虑峰值就行了。有点难

var wiggleMaxLength = function (nums) {
    if (nums.length == 1) return 1;
    let curDiff = 0; // 当前一对差值
    let preDiff = 0; // 前一对差值
    let result = 1; // 记录峰值个数，序列默认序列最右边有一个峰值
    for (let i = 0; i < nums.length - 1; i++) {
        curDiff = nums[i + 1] - nums[i];
        // 出现峰值
        if ((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0)) {
            result++;
            preDiff = curDiff;
        }
    }
    return result;
};

2022 将一维数组转变成二维数组

刷题时间：2022-01-01

元旦快乐题，新年快乐

var construct2DArray = function (original, m, n) {
    const len = original.length;
    if (len != m * n) {
        return [];
    }
    const res = [];
    for (let i = 0; i < m; i++) {
        let tmp = [];
        for (let j = 0; j < n; j++) {
            tmp.push(original[i * n + j]);
        }
        res.push(tmp.slice());
    }
    return res;
};

390 消除游戏

刷题时间：2022-01-02

抽象数学，搞不来。

var lastRemaining = function(n) {
    let a1 = 1, an = n;
    let k = 0, cnt = n, step = 1;
    while (cnt > 1) {
        if (k % 2 === 0) { // 正向
            a1 = a1 + step;
            an = (cnt % 2 === 0) ? an : an - step;
        } else { // 反向
            a1 = (cnt % 2 === 0) ? a1 : a1 + step;
            an = an - step;
        }
        k++;
        cnt = cnt >> 1;
        step = step << 1;
    }
    return a1;
};

134 加油站

刷题时间：2022-01-04

瞎摸摸出来的，看规律的，应该是贪心算法

var canCompleteCircuit = function (gas, cost) {
    const length = gas.length;
    let cnt = 0;
    let max = -Infinity;
    let res = -1;
    for (let i = 0; i < length; i++) {
        if (max < -cnt) {
            res = i;
            max = -cnt;
        }
        cnt += gas[i] - cost[i];
    }
    if (cnt < 0) return -1;
    return res;
};

135 分发糖果

刷题时间：2022-01-04

直接抄袭，不会写，困难贪心，这居然要从左到右，再从右到左两次贪心，双重贪心

var candy = function (ratings) {
    const len = ratings.length;
    const res = new Array(len).fill(1);
    for (let i = 1; i < len; i++) {
        if (ratings[i] > ratings[i - 1]) res[i] = res[i - 1] + 1;
    }
    for (let i = len - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) res[i] = Math.max(res[i], res[i + 1] + 1);
    }
    return res.reduce((prev, curr) => prev + curr);
};

860 柠檬水找零

刷题时间：2022-01-04

简单题简单逻辑。

var lemonadeChange = function (bills) {
    let five = 0,
        ten = 0;
    for (let i = 0; i < bills.length; i++) {
        if (bills[i] == 5) five++;
        else if (bills[i] == 10) {
            ten++;

            if (five > 0) five--;
            else return false;
        } else if (bills[i] == 20) {
            if (ten) {
                ten--;
                if (five) {
                    five--;
                } else return false;
            } else if (five >= 3) five -= 3;
            else return false;
        }
    }
    return true;
};

1576 替换所有的问号

刷题时间：2022-01-05

U1S1，今天这道简单题可不简单啊，难得很。

var modifyString = function (s) {
    const n = s.length;
    const arr = [...s];
    for (let i = 0; i < n; ++i) {
        if (arr[i] === '?') {
            for (let j = 0; j < 3; ++j) {
                if ((i > 0 && arr[i - 1] === String.fromCharCode('a'.charCodeAt() + j)) || (i < n - 1 && arr[i + 1] === String.fromCharCode('a'.charCodeAt() + j))) {
                    continue;
                }
                arr[i] = String.fromCharCode('a'.charCodeAt() + j);
                break;
            }
        }
    }
    return arr.join('');
};

406 根据身高重建队列

刷题时间：2022-01-05

这种二维的贪心，需要先确定一个维度进行考量，然后再从另一个维度上考量。第一个考量的维度是按照身高从高到矮的排序，身高相同按照k小的在前面。排完之后遍历，按照k值大小进行插入，因为不会影响其他的。

var reconstructQueue = function (people) {
    people.sort((a, b) => {
        if (b[0] != a[0]) {
            return b[0] - a[0];
        } else {
            return a[1] - b[1];
        }
    });
    const queue = [];
    for(let i = 0; i < people.length; i++) {
        queue.splice(people[i][1], 0, people[i])
    }
    return queue
};

452 用最少数量的箭引爆气球

刷题时间：2022-01-05

这个方法最取巧的地方就是直接修改原数组的【1】，这样子就比较方便，不需要另外再定义变量和新增判断，巴适的很。

var findMinArrowShots = function (points) {
    points.sort((a, b) => a[0] - b[0]);
    let res = 1;
    for (let i = 1; i < points.length; i++) {
        if (points[i][0] > points[i - 1][1]) {
            res++;
        } else {
            points[i][1] = Math.min(points[i][1], points[i - 1][1]);
        }
    }
    return res;
};