1.两数之和

题目链接https://leetcode-cn.com/problems/two-sum/

思路:从前向后遍历数组,每次查找map中是否有目标数值,如果没有,则将当前数值加入到Map中,知道某一时刻满足条件,返回结果。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const mp = new Map();

    for (let i = 0; i < nums.length; ++ i) {
        let j = mp.get(target - nums[i]);
        
        // 判断当前集合中是否有目标数值
        if (typeof j === "undefined") {
            mp.set(nums[i], i);
        } else {
            return [i, j];
        }
    }
};

2. 两数相加

题目链接https://leetcode-cn.com/problems/add-two-numbers/

思路:给定的两个数是以链表的形式,最低位是链表的头结点。模拟每个结点相加和进位操作。我们可以先创建一个头结点 head,这样对于头节点就不需要单独处理了。接下来 while 循环处理。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {

    const head = new ListNode(-1, null);
    let p = head;

    let jw = 0;
    while(l1 != null || l2 != null) {
		
        const v1 = l1 ? l1.val : 0;
        const v2 = l2 ? l2.val : 0;
        
        const sum = v1 + v2 + jw;
        jw = Math.floor(sum / 10);
        if (l1) {
            l1.val = sum % 10;
            p.next = l1;
        } else {
            l2.val = sum % 10;
            p.next = l2;
        }
        p = p.next;
        l1 = l1 ? l1.next : null;
        l2 = l2 ? l2.next : null;
    }
    // 剩余进位
    if (jw) {
        p.next = new ListNode(jw, null);
    }
    return head.next;
};

3. 无重复字符的最长子串

题目链接https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

思路:要找到最长连续无重复字符组成的长度。可以通过使用 滑动窗口,使用 i 表示窗口的左边界, j 表示窗口的右边界。

  • 边界扩展:当 s[i~j] 中无重复字符时,右边界一直向右扩展
  • 边界收缩:当新加入的字符,出现了重复,那么开始收缩左边界,直到该字符在滑动窗口中的数量小于等于 1.
  • 边界扩展和收缩的同时计算最大长度。
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    
    const n = s.length;
    if (!n) 
        return 0;
    const charCountMap = new Map();
    let len = 0;
    for (let i = -1, j = 0; j < n; ++ j) {
        // 边界扩张
        addPyToMap(s[j], 1);
		
        // 边界收缩
        while(i < j && getCount(s[j]) > 1) 
            addPyToMap(s[++ i], -1);
            
        len = Math.max(len, j - i);
    }
	
    // 获取 key 字符的数量
    function getCount (key) {
        const value = charCountMap.get(key);

        return typeof value !== "undefined" ? value : 0;
    }
	// key 字符数量 加上 py 
    function addPyToMap (key, py) {
        const value = getCount(key);
        charCountMap.set(key, value + py);
    }

    return len;
};

4. 寻找两个正序数组的中位数

题目链接https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

思路:因为题目要求是 O(log(m + n)), 很容易想到 二分法。因为,两个数组都是有序的。找中位数,我们可以转换为:找到两个数中第 k 大的数。设两个数组是 a, b。如果 a[k / 2 - 1] < a[k/2 - 1], 说明了至少 有 k/2 个数小于 第k个数。所以,每次都将 数组折半然后进行排除 数值,最后就可以得到答案。

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {

    let len1 = nums1.length, len2 = nums2.length;
    const n = len1 + len2;
    if (n % 2) {
        let k = Math.floor(n / 2);
        return getKElement(nums1, nums2, k-1);
    } else {
        let k1 = Math.floor(n / 2);
        let k2 = k1 + 1 ;

        return (getKElement(nums1, nums2, k1) + getKElement(nums1, nums2, k2)) / 2;
    }

    

};


function getKElement(num1, num2, k) {
    
    let len1 = num1.length, len2 = num2.length;
    let index1 = 0, index2 = 0;

    while(true) {
        if (index1 === len1) {
            return num2[index2 + k - 1];
        }
        if (index2 === len2) {
            return num1[index1 + k - 1];
        }
        if (k === 1) {
            return Math.max(num1[index1], num2[index2]);
        }

        let half = Math.floor( k / 2);
        let newIndex1 = Math.min(index1 + half, len1) - 1;
        let newIndex2 = Math.min(index2 + half, len2) - 1;

        let p1 = num1[newIndex1], p2 = num2[newIndex2];
        if (p1 >= p2) {
            k -= (newIndex1 - index1 + 1);
            index1 = newIndex1 + 1;
        } else {
            k -= (newIndex2 - index2 + 1);
            index2 = newIndex2 + 1;
        }
    }

}

5. 最长回文子串

题目链接https://leetcode-cn.com/problems/longest-palindromic-substring/

思路:判断回文字符串,可以枚举回文字符串的中轴,然后依次向两侧匹配字符,直到字符不匹配或越界。

  • 分两种情况
    • 回文字符串长度是奇数:中轴就是 当前字符
    • 回文字符串长度是偶数:中轴就两个字符中间的虚拟轴对称
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    

    const n = s.length;
    let len = 0, left = 0, right = 0;
    for (let center = 0; center < n; ++ center) {
        // 处理奇数情况
        let i = center - 1;
        let j = center + 1;

        while(i >= 0 && j < n && s[i] === s[j]) {
            -- i;
            ++ j;
        }
        if (len < j - i + 1) {
            len = j - i + 1;
            left = i + 1;
            right = j - 1;
        }

        // 处理偶数情况
        i = center;
        j = center + 1;
        while(i >= 0 && j < n && s[i] === s[j]) {
            -- i;
            ++ j;
        }

        if (len < j - i + 1) {
            len = j - i + 1;
            left = i + 1;
            right = j - 1;
        }
    }

    return s.slice(left, right + 1);
};

6. Z 字形变换

题目链接https://leetcode-cn.com/problems/zigzag-conversion/

思路:模拟这个过程,控制 ij, 的方向。根据题例直到在 横轴方向 j 始终 递增, i 会递增递减的改变方向。模拟过程注意控制 i 的方向即可。

/**
 * @param {string} s
 * @param {number} numRows
 * @return {string}
 */
var convert = function(s, numRows) {
    const n = s.length;
    if (numRows === 1)
        return s;
	// 构建二维数组
    const mp = new Array(numRows).fill(0).map(()=>new Array(n).fill(""));
    let i = 0, j = 0;
    let flag = true;
    for (let k = 0; k < n; ++ k) {

        mp[i][j] = s[k];

        if (flag) {
            ++ i;
        } else {
            -- i;
            ++ j;
        }

        if (flag) {
            if (i === numRows) {
                flag = false;
                i -= 2;
                ++ j;
            }
        } else {
            if (i === -1) {
                i += 2;
                flag = true;
            }
        }
    }
    let ss = "";
    // 得到
    for (const arr of mp) {
        for (const c of arr) {
            if (c !== "")
                ss += c;
        }
    }

    return ss;
};

7. 整数反转

题目链接https://leetcode-cn.com/problems/reverse-integer/

思路:将数值反转,然后判断是否越界。注意正负数的处理就好了。

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function (x) {
  let maxNumber = 2 ** 31 - 1;
  let minNumber = -1 * 2 ** 31;

  let number = 0;

  while (x !== 0) {
    number = number * 10 + (x % 10);
    // 整除
    x = ~~(x / 10);

    if (number > maxNumber || number < minNumber)
        return 0;
  }

  return number;
};

8. 字符串转换整数 (atoi)

题目链接https://leetcode-cn.com/problems/string-to-integer-atoi/

思路:模拟整个算法过程,注意处理 负数前导零情况 和 超出数据范围情况。

/**
 * @param {string} s
 * @return {number}
 */
var myAtoi = function(ss) {
    const maxValue = 2 ** 31 - 1;
    const minValue = 2 ** 31 * (-1);
    let s = ss.trimLeft();
    let i = 0;
    let len = s.length;
    let res = 0;
    // 前导零处理 和 负数前导零情况处理
    while(s[i] === "0" && i < len) {
        if (i + 1 < len && s[i + 1] === '-')
            return 0;
        ++ i;
    }
        
    // 正负判断
    let flag = true;
    if (s[i] === '-') {
        flag = false;
        ++ i;
    } else if (s[i] === '+')
        ++ i;


    while(s[i] >= "0" && s[i] <= "9" && i < len) {
        res = res * 10 + (s[i].charCodeAt() - "0".charCodeAt());

        // 处理超过数据范围的结果
        if (flag) {
            if (res >= maxValue)
                return maxValue;
        } else {
            if (-res <= minValue) 
                return minValue;
        }
        ++ i;
    }


    return flag? res : -res;

};

9. 回文数

题目链接https://leetcode-cn.com/problems/palindrome-number/

思路: 把整数倒过来判断是否相等,负数不是回文数。

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    if (x < 0)
        return false;
    // 将数导过来判断是否相等即可
    let t = x;
    let revserX = 0;
    while (t > 0) {
        revserX = revserX * 10 + t % 10;
        t = Math.floor(t/ 10); 
    }

    return revserX === x;
};

10. 正则表达式匹配

题目链接https://leetcode-cn.com/problems/regular-expression-matching/

思路:动态规划,对于 a* 这样的组合 看成一个整体,那么这个组合有两种情况。第一种:a* 不匹配任何字符;第二种:a* 匹配了字符并留下来继续匹配。

  • 状态表示:f(i, j) 表示 p[0 ~ j - 1] 是否匹配 s[0 ~ i - 1]

  • 边界:f(0, 0) = true

  • 状态转移方程:

    • p[j - 1] == ‘*’

      • f(i, j) = f(i, j - 2); // 不匹配任何字符
      • f(i, j) = f(i, j - 2) || f(i - 1, j); s[i - 1] = p[j - 2] // (丢弃当前能匹配的字符,并将组合留下来继续匹配)
    • p[j - 1] != ‘*’

      • f(i, j) = f(i - 1, j - 1); // s[i - 1] = p[j - 1];
    • 不满足上述条件皆为 false

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {
    s = s;
    p = p;
    const [n, m] = [s.length, p.length];

    const f = new Array(n + 1).fill(true).map(() => new Array(m + 1).fill(false));

    f[0][0] = true;

    for (let i = 0; i <= n; ++ i) {
        for (let j = 1; j <= m; ++ j) {
            if (p[j - 1] === '*') {
                // 丢弃组合
                f[i][j] = f[i][j - 2];

                if (match(i, j - 1)) {
                    // 匹配一个字符,并将该字符丢弃,留下组合继续匹配
                    f[i][j] = f[i][j] || f[i - 1][j];
                }
            } else {
                if (match(i, j))
                    f[i][j] = f[i - 1][j - 1];
            }
            
        }
    }

    return f[n][m];

    function match(i, j) {
        if (i === 0)
            return false;
        if (p[j - 1] === '.')
            return true;
        
        return s[i - 1] === p[j - 1];
    }
};




11. 盛最多水的容器

题目链接https://leetcode-cn.com/problems/container-with-most-water/

思路:设两个 变量,分别从数组的前后开始遍历,相遇就结束。每次移动 值最小的指针就能得到最优解。

  • 证明:

    • 设变量 L(左边的高度),R(右边的高度),W(容器的宽度),L > R, S(面积) = R*W

    • 假设向右移动 L, 会出现两种情况

      • L > R, 则 S1 = R*(W - 1)
      • L < R, 则 S2 = L*(W-1)
      • S > S1 >= S2
    • 假设向左移动 R, 会出现两种情况

      • L < R, 则 S3 = L * (W - 1)
      • L > R, 则 S4 = R * (W - 1)
      • S3 >= S > S3
    • 根据上面两种假设,第一种,始终移动最大的值,显然没有变大的可能。第二种,移动最小值有变大的可能

    • 结论:每次移动较小的值,就能够得到最优解

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let [i, j] = [0, height.length - 1];

    let res = 0;
    while(i < j){
        let currRes = Math.min(height[i], height[j]) * (j - i);
        res = Math.max(res, currRes);
        if (height[i] <= height[j])
            ++ i;
        else 
            -- j;
    }
    return res;
};

12. 整数转罗马数字

题目链接https://leetcode-cn.com/problems/integer-to-roman/

思路:此题使用贪心来做,优先使用最大的值来表示数值。就像找零钱一样,会尽量按最少的张数来配对。这个问题就可以转换成,有 13 种面额的钱,怎么找出指定的零钱,并使得张数更少。

/**
 * @param {number} num
 * @return {string}
 */
var intToRoman = function(num) {
    let values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1];
    let reps = ["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]


    let res = "";
    for (let i = 0; i < 13; ++ i) {
        while (num >= values[i]) {
            num -= values[i];
            res += reps[i];
        }
    }
    return res;
};

13. 罗马数字转整数

题目链接https://leetcode-cn.com/problems/roman-to-integer/

思路:从后往前遍历,并用一个lastInt 变量保存上一个转换的数值,通过比较 当前数是否大于上一个数来处理 IV 这样类型的数。例如IV,之前加过5 那么, 发现5 > 1 所以应该减去 1。

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    const mp = new Map();
    mp.set('I', 1);
    mp.set('IV', 4);
    mp.set('V', 5);
    mp.set("IX", 9);
    mp.set('X', 10);
    mp.set("XL", 40);
    mp.set('L', 50);
    mp.set("XC", 90);
    mp.set('C', 100);
    mp.set("CD", 400);
    mp.set('D', 500);
    mp.set("CM", 900);
    mp.set('M', 1000);

    let res = 0;
    let lastInt = 0;
    for (let i = s.length - 1; i >= 0; -- i) {
        let number = mp.get(s[i]);
        if (number < lastInt) {
            res -= number;
        } else {
            res = res + number;
        }
        lastInt = number;
    }
    return res;
};

14. 最长公共前缀

题目链接https://leetcode-cn.com/problems/longest-common-prefix/

思路:求出 传入字符串中最小的字符串长度,然后再一个个字符判断所有字符串当前指定的位置字符是否相同。

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {

    let prefixLen = 0;
    // 获得最小长度
    let minLen = Math.min.apply(Math, strs.map((item) => item.length));

    for (let i = 0; i < minLen; ++ i) {
        let char = strs[0][i];
        let flag = true;
        for (let j = 0; j < strs.length; ++ j) {
            if (strs[j][i] !== char) {
                flag = false;
                break;
            }
        }

        if (!flag) {
            break;
        }

        prefixLen ++;
    }

    return prefixLen ? strs[0].slice(0, prefixLen): "";
};

15. 三数之和

题目链接https://leetcode-cn.com/problems/3sum/

思路:将数组从小到大排序,枚举三个数的组合。重点是去重操作。

  • 第一个数循环 i 来说,当 i 不等于 0,且 nums[i] === nums[i - 1] 时,说明nums[i-1] 已经将所有能包含nums[i]的结果都枚举了,再次枚举会得到重复的结果。
  • 第二个数循环 j 来说,当 j 不等于i + 1, 且 nums[j] === nums[j - 1]时, 说明 nums[j - 1], 已经将 包含 nums[i] 和 nums[j] 的结果枚举过了。
  • 第三个数,如果前两个数固定,那么第三个数能得满足条件的结果就是固定的。
    • 这里有一种优化, nums[i] + nums[j] + nums[k] > 0, nums[j] 是递增的,显然 nums[k] 包括k之后的数必然不会满足目标条件。
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {

    nums.sort((a, b) => a-b);
    const n = nums.length;
    let ans = [];
    
    for (let i = 0; i < n; ++ i) {
        if (i && nums[i] === nums[i - 1])
            continue;
        let k = n - 1;
        let target = -nums[i];

        for (let j = i + 1; j < n; ++ j) {
            if (j !== i + 1 && nums[j] === nums[j - 1])
                continue;
            while (j < k && nums[j] + nums[k] > target) {
                k --;
            }
            if (j === k)
                break;
            if (j !== k && nums[j] + nums[k] === target)
                ans.push([nums[i],nums[j],nums[k]]);
        }
        
    }
    return ans;
};

16. 最接近的三数之和

题目链接https://leetcode-cn.com/problems/3sum-closest/

思路:先将数组从小到大排序,然后依次枚举每个可能的组合。当 sum > target 时,下标k及k之后不会是最优解。记住去重来剪枝。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    
    nums.sort((a, b) => a-b);
    const n = nums.length;
    let diff = 0x3f3f3f3f, res = 0;


    for (let i = 0; i < n - 2; ++ i) {
        if (i && nums[i] === nums[i - 1])
            continue;

        let j = i + 1;
        let k = n - 1;
        while (j < k) {
            let sum = nums[i] + nums[j] + nums[k];
            if (Math.abs(sum - target) < diff) {
                [res, diff] = [sum, Math.abs(sum - target)];
            }

            if (sum === target)
                return res;
            else if (sum > target)
                -- k;
            else 
                ++ j;
        }
    }
    
    return res;
};

17. 电话号码的字母组合

题目链接https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

思路:暴力枚举所有组合即可,递归枚举也行。这里采用暴力。

// 写法一
/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  let numberToStr = [
    "",
    "",
    "abc",
    "def",
    "ghi",
    "jkl",
    "mno",
    "pqrs",
    "tuv",
    "wxyz",
  ];

  let res = [];
  for (const c of digits) {
    let number = c.charCodeAt() - "0".charCodeAt();

    if (!res.length) {
      res.push(...numberToStr[number]);
    } else {
      let curRes = [];
      let s = numberToStr[number];
      for (let i = 0; i < s.length; ++i) {
        for (let j = 0; j < res.length; ++j) {
          curRes.push(res[j] + s[i]);
        }
      }
      res = curRes;
    }
  }
  return res;
};


// 写法二
/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {

    if (!digits.length)
        return [];
    let mp = new Map();
    mp.set('2', ['a', 'b', 'c']);
    mp.set('3', ['d', 'e', 'f']);
    mp.set('4', ['g', 'h', 'i']);
    mp.set('5', ['j', 'k', 'l']);
    mp.set('6', ['m', 'n', 'o']);
    mp.set('7', ['p', 'q', 'r', 's']);
    mp.set('8', ['t', 'u', 'v']);
    mp.set('9', ['w', 'x', 'y', 'z']);

    let arr = [];
    for (let i of digits) {
        arr.push(mp.get(i));
    }

    let ans = arr.reduce((r, item)=>{
        let nextR = [];
        for (let s1 of r) {
            for (let s2 of item) {
                nextR.push(s1 + s2);
            }
        }
        return nextR;
    });

    return ans;


};

18. 四数之和

题目链接https://leetcode-cn.com/problems/4sum/

思路:思路和第15题三数之和一样,排序去重,优化

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const res = [];
    for (let i = 0; i < n - 3; ++ i) {
        if (i && nums[i] === nums[i - 1])
            continue;
        
        for (let j = i + 1; j < n - 2; ++ j) {
            if (j !== i + 1 && nums[j] === nums[j - 1])
                continue;
            
            for (let k = j + 1; k < n - 1; ++ k) {
                if (k !== j + 1 && nums[k] === nums[k - 1]) 
                    continue;
                let currSum = nums[i] + nums[j] + nums[k];
                let p = n - 1;
                while (k < p &&  currSum + nums[p] > target)
                    -- p;
                
                if (k === p)
                    break;
                
                if (nums[i] + nums[j] + nums[k] + nums[p] === target) {
                    res.push([nums[i],nums[j], nums[k], nums[p]]);
                }
            }
        }
    }



    return res;
};

19. 删除链表的倒数第 N 个结点

题目链接https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

思路:设置快慢指针,first second, 令first先走到第n+1个位置,此时 second 距离 first 距离为 n。然后在一起往后遍历,当first.next === null 的时候,first到达尾部,此时 second 就距离 first n, 所以,他是倒数第n个点前面的一个点。

image20220427224207085.png

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {

    let k = 0, first = head, second = head;

    while (k < n) {
        ++ k;
        first = first.next;
    }

    // 如果等于空就等于删除第一个结点
    if (first === null)
        return head.next;

    while(first.next !== null) {
        first = first.next;
        second = second.next;
    }

    second.next = second.next.next;


    return head;

};

20. 有效的括号

题目链接https://leetcode-cn.com/problems/valid-parentheses/

思路:这个题是栈的简单应用。遇到左括号就将其压入栈中,遇到右括号就与栈顶元素进行匹配。如果遇到右括号且栈为空,则此括号组合无效。当循环结束,栈不为空,则说明有多余的左括号未匹配。

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {

    const stack = [];
    let mp = {
        "(": 1,
        "{": 2,
        "[": 3,
        "]": 4,
        "}": 5,
        ")": 6
    };

    for (const c of s) {
        if (mp[c] <= 3) {
            stack.push(c);
        } else {
            if (stack.length === 0)
                return false;
            let top = stack[stack.length - 1];
            if ((mp[top] === 1 && mp[c] === 6) || (mp[top] === 2 && mp[c] === 5) || (mp[top] === 3 && mp[c] === 4)) {
                stack.pop();
            } else {
                return false;
            }
        }
    }

    return stack.length? false:true;

};

21. 合并两个有序链

题目链接https://leetcode-cn.com/problems/merge-two-sorted-lists/

思路:按照题意合并即可,注意头节点的处理

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
    
    // 声明头结点,将头结点处理统一
    let head = new ListNode();
    let p = head;

    while(list1 || list2) {
        
        let num1 = list1 ? list1.val : 0x3f3f3f3f;
        let num2 = list2 ? list2.val : 0x3f3f3f3f;

        if (num1 < num2) {
            p.next = list1;
            list1 = list1.next;
        } else {
            p.next = list2;
            list2 = list2.next;
        }
        p = p.next;
    }

    return head.next;
    
};

22. 括号生成

题目链接https://leetcode-cn.com/problems/generate-parentheses/

思路:直接深度优先遍历枚举所有可能的组合即可。

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  let res = [];

  // l 表示左括号待使用的个数
  // r 表示右括号待使用的个数
  // s 表示已使用括号组成的正确的括号字符串
  const generateDfs = function (l, r, s) {
    if (s.length === n * 2) {
      res.push(s);
      return;
    }

    // 还有左括号
    if (l > 0) {
      generateDfs(l - 1, r, s + "(");
    }

    // 有左括号待匹配
    if (r > l) {
      generateDfs(l, r - 1, s + ")");
    }
  };

  generateDfs(n, n, "");
  return res;
};

23. 合并K个升序链表

题目链接https://leetcode-cn.com/problems/merge-k-sorted-lists/

思路:分治法,将多个链表的合并,分解成两两合并,然后递归处理。第21题的加强版

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    if (lists.length === 0) 
        return null;
    return dfs(0, lists.length);


    function dfs(l, r) {
        if (l === r) return lists[l];
        let mid = Math.floor((l + r) / 2 );
        let list1 = dfs(l, mid);
        let list2 = dfs(mid + 1, r);
        
        return mergeTwo(list1, list2);
    }

    function mergeTwo(list1, list2) {
        let head = new ListNode();
        let p = head;
        while(list1 || list2) {
            const num1 = list1 ? list1.val : 0x3f3f3f3f;
            const num2 = list2 ? list2.val : 0x3f3f3f3f;

            if (num1 < num2) {
                p.next = list1;
                list1 = list1.next;
            } else {
                p.next = list2;
                list2 = list2.next;
            }

            p = p.next;
        }

        return head.next;
    }  

};

24. 两两交换链表中的节点

题目链接https://leetcode-cn.com/problems/swap-nodes-in-pairs/

思路:创建一个头节点,dummy.next = head。令p=dummy, 每次需要交换的是 p.next 和 p.next.next, 也就是 p-> node1 ->node2 => p->node2->node1

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    
    let dummy = new ListNode();
    dummy.next = head;

    let p = dummy;
    
    while(p !== null && p.next !== null && p.next.next !== null) {
        let node1 = p.next;
        let node2 = p.next.next;

        p.next = node2;
        node1.next = node2.next;
        node2.next = node1;

        p = node1;
    }

    return dummy.next;


};

25. K 个一组翻转链表

题目链接https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

思路:将链表每k个结点分成一个子链表,分别对子链表进行反转。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function(head, k) {
   let node = head;
   for (let i = 0; i < k; ++ i) {
       if (node === null) {
           return head;
       }

       node = node.next;
   }

   let newHead = reverseList(head, node);
   // head 始终指向 原始链表的第一个结点,翻转过后就是最后一个结点了
   head.next = reverseKGroup(node, k);
   return newHead;
};
// last 是下一个链表的开头
function reverseList(first, last) {
    let prev = last;
    while(first != last) {
        let tmp = first.next;
        first.next = prev;
        prev = first;
        first = tmp;
    }

    return prev;
}

26. 删除有序数组中的重复项

题目链接https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

思路:双指针算法

image20220429212128046.png

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let i, j;
    for (i = 0, j = 0; j < nums.length; ++ j) {
        if (nums[i] !== nums[j]) {
            nums[++ i] = nums[j];
        }
    }
    return i + 1;
};

27. 移除元素

题目链接https://leetcode-cn.com/problems/remove-element/

思路:26题差不多,按照题意做即可

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {

    let i, j;
    for (i = 0, j = 0; j < nums.length; ++ j) {
        if (nums[j] !== val) {
            console.log(nums[i], nums[j]);
            nums[i] = nums[j];
            ++ i;
        }
    }
    return i;
};

28. 实现 strStr()

题目链接https://leetcode-cn.com/problems/implement-strstr/

思路:使用kmp字符串匹配。模板题

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function(haystack, needle) {
    if (needle.length === 0)
        return 0;

    let s = new String(" " + haystack);
    let p = new String(" " + needle);
    const n = haystack.length;
    const m = needle.length;

    let next = new Array(m + 1).fill(0);

    // p 字符串进行自匹配 得到 next[i] :1~i 这段的最长公共前后缀。
    for (let i = 2, j = 0; i <= m; ++ i) {
        while(j !== 0 && p[i] !== p[j + 1])
            j = next[j];
        if (p[i] === p[j + 1])
            ++ j;
        next[i] = j;
    }

    for (let i = 1, j = 0; i <= n; ++ i) {
        while(j !== 0 && s[i] !== p[j + 1])
            j = next[j];
        if (s[i] === p[j + 1])
            ++ j;
        if (j === m) {
            return i - m;
        }
    }
    return -1;
};

29. 两数相除

题目链接https://leetcode-cn.com/problems/divide-two-integers/

思路:设X是被除数,Y是除数,Z为商。当 X,Y 都为正数的时候存在表达式 (Z + 1) * Y > X >= Z * Y。 所以,我们只需要求出 Z*Y <= X 中 满足条件时 Z 的最大值。因为,题目要求不能乘除法mod等。我们直到 任何一个整数都可以表示成 多个2的幂次累加。Z = 2^c1 + 2^c2 + 2^c3 + …。将上面表达式转换一下。

X - Z*Y >= 0 , X - (2^c1 + 2^c2 + 2^c3+ …) * Y >= 0. 依次枚举每个 ci 即可求出答案。

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function (dividend, divisor) {
  const [INT_MIN, INT_MAX] = [-1 * 2 ** 31, 2 ** 31 - 1];
  if (dividend === INT_MIN) {
      if (divisor === -1)
        return INT_MAX;
      if (divisor === 1)
        return INT_MIN;
  }

  let [dvd, dvs] = [Math.abs(dividend), Math.abs(divisor)];
  let res = 0;
  for (let i = 30; i >= 0; -- i) {
   
      if ((dvd >>> i) >= dvs) {  
        dvd -= (dvs << i);
        res += (1 << i);     
      }
  }


  return (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0) ? -res: res;
};

30. 串联所有单词的子串

题目链接https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/

思路:用一个map统计words中单词的次数,然后使用滑动窗口,start为窗口头部,i为窗口尾部。枚举 窗口头部 start 以字符串 s 的每个字符开头。在 i 扩展大小的时候,同时,将map中对应字符串的次数减去。当map中所有字符串的次数为0时,则这是一个成功的匹配。

/**
 * @param {string} s
 * @param {string[]} words
 * @return {number[]}
 */
var findSubstring = function(s, words) {
    if (words.length === 0)
        return [];
    
    
    let counter = new Map();
    let noChangeCounter = null;
    let wordLen = words[0].length;  // 单词长度
    let totalLen = wordLen * words.length;  // 总长度

    for (let i = 0; i < words.length; ++ i) {
        incrementCount(counter, words[i], 1);
    }
    noChangeCounter = copyMap(counter);
    let res = [];
    // start 是窗口开始位置,i 向远处扩展, i + wordLen - start + 1 最大长度为 totalLen
    for (let i = 0, start = 0; i < s.length - wordLen + 1 && start  < s.length - totalLen + 1;  ++ i) {
        let str = s.slice(i, i + wordLen);

        if (getCount(counter, str) > 0) {
            incrementCount(counter, str, -1);

            // 判断是否全部匹配完成
            if (checkCount(counter)) {
                res.push(start);
                continue;
            }

            // 跳转到下一个单词的前面一个字符,循环会执行 ++ i, 所以此处 -1
            i = i + wordLen - 1;
        } else {
            // 以下一个字符开头继续匹配
            start ++;
            i = start - 1;
            counter = copyMap(noChangeCounter);
        }
    }

    return res;

    // 获取map 中的值,返回一个整数
    function getCount(counter, key) {
        return counter.has(key)? counter.get(key) : 0;
    }

    // key的值添加d值
    function incrementCount(counter, key, d) {
        let c = getCount(counter, key);
        counter.set(key, c + d);
    }
    // 检测当前map中所有值是否为 0
    function checkCount(counter) {
        for (const value of counter.values()) {
            if (value > 0) 
                return false;
        }

        return true;
    }
    // copy
    function copyMap(counter) {
        let newMap = new Map();
        for (const [key,value] of counter.entries()) {
            newMap.set(key, value);
        }

        return newMap;
    }
};

31. 下一个排列

题目链接https://leetcode-cn.com/problems/next-permutation/

思路:要求出大于当前排序的字典序,且变化幅度最小。那么只能将较小的数和一个较大的数进行交换。且 较小的数尽量靠右,较大的数尽可能的小。交换完后将将 较大的数的右边进行升序排序即可。

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {

    let i;
    for (i = nums.length - 2; i >= 0; -- i) {
        if (nums[i] < nums[i + 1])
            break;
    }
	// -1 表示 此数组已经是最大字典序了,也就是降序排列了,直接从小到大排序即可
    if (i === -1) {
        // nums.sort((a, b) => a-b);
        nums.reverse();
        return nums;
    }
	
    // 找到较大的数,i存在j必然存在
    let j;
    for (j = nums.length - 1; j > i; -- j) {
        if (nums[j] > nums[i])
            break;
    }
	
    // 交换
    [nums[i], nums[j]] = [nums[j], nums[i]];

    // 排序,此时i之后的数必然是升序。因为查找的i的时候就确认了。
    let l = i + 1, r = nums.length - 1;
    while (l < r) {
        [nums[l], nums[r]] = [nums[r], nums[l]];
        l ++;
        r --;
    }

    return nums;
};

32. 最长有效括号

题目链接https://leetcode-cn.com/problems/longest-valid-parentheses/

思路:用栈来维护左括号下标和未匹配右括号下标,每个未匹配的右括号就是每个连续的括号段的分割符。每次匹配成功后,可以通过该分割符计算连续匹配长度。注意开始的时候,没有右括号。栈的初始栈顶 为 -1

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
    let stack = [-1];
    let res = 0;
    for (let i = 0; i < s.length; ++ i) {
        if (s[i] === "(")
            stack.push(i);
        else {
            stack.pop();
            // 将 未匹配的右括号加入栈中
            if (stack.length === 0)
                stack.push(i);
            else 
                // 匹配成功,计算当前连续匹配长度
                res = Math.max(res, i - stack[stack.length - 1]);
        }
    }
    return res;
};

33. 搜索旋转排序数组

题目链接https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

思路:由于数组本身是有序的。经过翻转必然会形成两段升序序列。大概像下图一样。我们依然可以进行二分,每次二分判断有序的那一段。也就是判断mid落在那较大或较小的升序序列,然后在进行范围缩小。具体下图分析的两种情况,1.落在较大大升序序列中,2. 落在较小的升序序列中

image20220501225024503.pngimage-20220501225024503

// 解题代码一:
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    if (nums.length === 0) 
        return -1;
    
    if (nums.length === 1) 
        return nums[0] === target? 0 : -1;
    
    let l = 0, r = nums.length - 1;

    while (l <= r) {
        let mid = Math.floor((l + r) / 2);
        if (nums[mid] === target)
            return mid;
        

        if (nums[mid] >= nums[l]) {
            if (nums[mid] < target)
                l = mid + 1;
            else if (nums[mid] > target){
                if (nums[l] <= target)
                    r = mid - 1;
                else if (nums[l] > target)
                    l = mid + 1;
            }
        } else if (nums[mid] <= nums[r]) {
            if (nums[mid] > target)
                r = mid - 1;
            else if (nums[mid] < target) {
                if (nums[r] >= target)
                    l = mid + 1;
                else if (nums[r] < target) 
                    r = mid - 1;
            }
        }
    }
    
    return -1;
};


// 解题代码二
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    const n = nums.length;
    if (n === 0) 
        return -1;
    
    if (n === 1) 
        return nums[0] === target? 0 : -1;
    
    let l = 0, r = n - 1;

    while (l <= r) {
        let mid = Math.floor((l + r) / 2);
        if (nums[mid] === target)
            return mid;
        

        if (nums[mid] >= nums[0]) {
            if (nums[0] <= target && nums[mid] > target)
                r = mid - 1;
            else 
                l = mid + 1;
        } else {
            if (nums[n - 1] >= target && nums[mid] < target)
                l = mid + 1;
            else 
                r = mid - 1;
        }
    }
    
    return -1;
};

34. 在排序数组中查找元素的第一个和最后一个位置

题目链接https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

思路:题目要求O(log n) 必然想到二分,这里涉及到,

  • 二分查找第一个小于或等于 target 的数
  • 二分查找最后一个大于或等于target的数
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    const n = nums.length;
    let l = b1(0, n - 1, target, nums);
    if (nums[l] !== target)
        return [-1, -1];
    
    let r = b2(0, n - 1, target, nums);

    return [l, r];
    

    // 查找第一个小于或等于 target的数
    function b1(l, r, target, nums) {
        while(l < r) {
            let mid = Math.floor((l + r) / 2);
            if (nums[mid] >= target)
                r = mid;
            else
                l = mid + 1;
        }

        return l;
    }

    // 查找最后一个大于或等于 target的数
    function b2(l, r, target, nums) {
        while(l < r) {
            let mid = Math.floor((l + r + 1) / 2);
            if (nums[mid] <= target)
                l = mid;
            else 
                r = mid - 1;
        }

        return l;
    }
};

35. 搜索插入位置

题目链接https://leetcode-cn.com/problems/search-insert-position/

思路:二分查找第一个大于或等于 target的数即可,当 pos == len - 1 时 需要特判,当前 数是大于还是小于target

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    const n = nums.length;
    let pos = b1(0, n - 1, target, nums);

    if (nums[pos] === target)
        return pos;
    

    if (pos === n - 1) {
        if (target > nums[pos])
            return pos + 1;
        
        if (nums[pos] < target)
            return pos - 1;
    }

    return pos;

    // 查找数组中第一个大于等于它的数
    function b1(l, r, target, nums) {
        while (l < r) {
            let mid = Math.floor((l + r) / 2);

            if (nums[mid] < target)
                l = mid + 1;
            else 
                r = mid;
        } 

        return l;
    }
};

36. 有效的数独

题目链接https://leetcode-cn.com/problems/valid-sudoku/

思路:判断每一行、每一列和每一个块是否满足要求,块的判断,先计算出块的起始坐标 startX = x / 3 * 3, startY = y / 3 * 3,然后遍历该块即可。判断是否满足数度的要求即可。

/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {
    const n = board.length;
    const m = board[0].length;

    for (let i = 0; i < n; ++ i) {
        for (let j = 0; j < m; ++ j) {
            if (board[i][j] !== '.') {
                if (!checkBlock(i, j) || !checkColumn(i, j) || !checkRow(i, j))
                    return false;
            }
        }
    }

    return true;

    // 检测block 块
    function checkBlock(x, y) {
        // (5, 5)  => (1, 1) => (1 * 3 + 1) 
        let startX = Math.floor(x / 3) * 3, startY = Math.floor(y / 3) * 3;
        for (let i = startX; i < startX + 3; ++ i){
            for (let j = startY; j < startY + 3; ++ j) {
                if (i === x && j === y) 
                    continue;
                if (board[i][j] === board[x][y])
                    return false;
            }
        }

        return true;   
    }
    // 检测行
    function checkRow(x, y) {
        for(let i = x - 1; i >= 0; -- i) {
            if (board[i][y] === board[x][y])
                return false;
        }

        for (let i = x + 1; i < 9; ++ i) {
            if (board[i][y] === board[x][y])
                return false;
        }

        return true;
    } 
    // 检测列
    function checkColumn(x, y) {
        for (let i = y - 1; i >= 0; -- i) {
            if (board[x][i] === board[x][y])
                return false;
        }
        for (let i = y + 1; i < 9; ++ i) {
            if (board[x][i] === board[x][y])
                return false;
        }

        return true;
    } 
};

37. 解数独

题目链接https://leetcode-cn.com/problems/sudoku-solver/

思路:暴力dfs, 枚举每一列中的每个空格中填入的数字,并判断是否满足要求。

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
    
    dfs(0, 0);
    return board;


    function dfs(x, y) {
        // 枚举下一列
        if (y >= 9) {
            return dfs(x + 1, 0);
        }
        // 所有列枚举完,说都满足条件了
        if (x >= 9) {
            return true;
        }
        // 不为空则枚举下一个空格
        if (board[x][y] !== '.')
            return dfs(x, y + 1);
        
        // 尝试在该空填入数字
        for (let i = 1; i <= 9; ++ i) {
            if (check(x, y, String.fromCharCode('0'.charCodeAt() + i))) {
                board[x][y] = String.fromCharCode('0'.charCodeAt() + i);
                if (dfs(x, y + 1)) {
                    return true;
                } else {
                    // 回溯
                    board[x][y] = '.';
                }
            }
        }

        return false;
    }

    // 检测填入当前数字是否满足条件
    function check(x, y, target) {
        // 检测block 块
        function checkBlock(x, y, target) {
            // (5, 5)  => (1, 1) => (1 * 3 + 1) 
            let startX = Math.floor(x / 3) * 3, startY = Math.floor(y / 3) * 3;
            for (let i = startX; i < startX + 3; ++ i){
                for (let j = startY; j < startY + 3; ++ j) {
                    if (i === x && j === y) 
                        continue;
                    if (board[i][j] === target)
                        return false;
                }
            }

            return true;   
        }
        // 检测行
        function checkRow(x, y, target) {
            for(let i = x - 1; i >= 0; -- i) {
                if (board[i][y] === target)
                    return false;
            }

            for (let i = x + 1; i < 9; ++ i) {
                if (board[i][y] === target)
                    return false;
            }

            return true;
        } 
        // 检测列
        function checkColumn(x, y, target) {
            for (let i = y - 1; i >= 0; -- i) {
                if (board[x][i] === target)
                    return false;
            }
            for (let i = y + 1; i < 9; ++ i) {
                if (board[x][i] === target)
                    return false;
            }

            return true;
        } 

        return checkBlock(x, y, target) && checkColumn(x, y, target) && checkRow(x, y, target);
    }
    
    
};

38. 外观数列

题目链接https://leetcode-cn.com/problems/count-and-say/

思路:先dfs从,n = 1 开始处理字符串,然后获取前一个返回的结果,遍历该结果在进行描述,然后将结果返回。

/**
 * @param {number} n
 * @return {string}
 */
var countAndSay = function(n) {
    if (n === 1)
        return "1";
    let res = countAndSay(n - 1);

    let curFuncRes = "";
    let curCharCnt = 0;
    let i, j;
    for(i = 0, j = 0; j < res.length; ++ j) {
        
        if (res[i] === res[j])
            curCharCnt ++;
        if (res[i] !== res[j]) {
            // console.log(curCharCnt, res[i]);
            curFuncRes += String(curCharCnt) + res[i];
            curCharCnt = 0;
            i = j;
            j --;
        }
    }
    // console.log(curCharCnt, res[i]);
    // 处理最后连续的一段
    curFuncRes += String(curCharCnt) + res[i];

    return curFuncRes;
};

39. 组合总和

题目链接https://leetcode-cn.com/problems/combination-sum/

思路:直接dfs搜索即可,对于数组中的每个数右两种情况,1:一直选当前这个数,2:选了k次后,停止选该数。同时,对数组排序可优化搜索时间

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    let n = candidates.length;
    candidates.sort();
    let ans = [];
    let ds = [];

    dfs(0, ds, target);
    
    return ans;
    function dfs(k, ds, target) {
        if (target < 0 || k >= n) {
            return;
        }

        if (target == 0) {
            ans.push(Array.from(ds));
            return;
        }

        ds.push(candidates[k]);
        dfs(k, ds, target - candidates[k]);
        ds.pop();

        dfs(k + 1, ds, target);
    }

   
    
};

40. 组合总和 II

题目链接https://leetcode-cn.com/problems/combination-sum-ii/

思路:这个题时 39 题的变形,每个数只能枚举一次,存在重复的数字(也就是说,每个数的适用次数是有限的)。为了避免,重复的答案出现,我们必须把重复的数字统一处理。先枚举存重复数字 = 1次的所有情况组合,然后再枚举 重复数字 = 2 所有情况组合…

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {

    let n = candidates.length;
    
    candidates.sort((a, b) => a - b);

    const res = [];
    const curArr = [];
    dfs(0, target);
    return res;
    function dfs(start, target) {
        if (target === 0) {
            res.push([...curArr]);
            return;
        }

        for (let i = start; i < n; ++ i) {
            // 去重, 这里去重,下一次循环可选择重复数字。
            // 不会出现  [1, 2, 5], [1, 2, 5] 这样类似的情况
            // 出现的时 [1, 2, 5] / [1, 1, 2, 4] / [1, 1, 2, 3] ....
            if (i > start && candidates[i] === candidates[i - 1]) {
                continue;
            }

            if (target >= candidates[i]) {
                curArr.push(candidates[i]);
                dfs(i + 1, target - candidates[i]);
                curArr.pop();
            }
        }
    }

};

41. 缺失的第一个正数

题目链接https://leetcode-cn.com/problems/first-missing-positive/

思路

  • 答案显然只会再 [1, N + 1]的范围内,N 为 数组长度,N+1 是 1~N 的数全部存在,则最小的正整数 N + 1

  • 我们可以利用当前的数组来做hash,因为,只有nums[i] 在 N 的范围内才会影响结果。所以,如果 nums[i] <= n, 则我们可以打上标记,令 nums[nums[i]] = -nums[nums[i]], 在该位置上打上负数标记。表示该下标指定的数出现过。

  • 算法流程

    • 将所有 小于等于 0 的数设置为 N + 1, 因为负数和零不在取值范围中。此时,数组中全正数

    • 接下来判断nums[i] 是否在[1, N]这个范围中,如果在则将nums[nums[i]]标记(如果已经是负数则说明前面有重复的标记了次,则必须在进行标记)。注意:有可能未枚举到的数已经被标记成负数,所以得取数的绝对值来进行比较。

    • 最后,遍历数组,遇到第一个正数,则它的下标 + 1 就是答案。若全为整数,N + 1 就是答案。

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {

    const n = nums.length;
    for (let i = 0; i < n; ++ i) {
        if (nums[i] <= 0)
            nums[i] = n + 1;
    }

    for (let i = 0; i < n; ++ i) {
        // 当 i = 1 nums[1] = 3 此时标记  nums[3] = -nums[3] = -2, 2 也需要去标记nums[2] = nums[Math.abs(nums[3])] -nums[2]
        if (Math.abs(nums[i]) <= n) {
            // 已经标记过就不不能再标记了
            if (nums[Math.abs(nums[i]) - 1] > 0)
                nums[Math.abs(nums[i]) - 1] = -nums[Math.abs(nums[i]) - 1];
        }
            
    }
    for (let i = 0; i < n; ++ i) {
        if (nums[i] > 0) {
            return i + 1;
        }
    }

    return n + 1;
};

42. 接雨水

题目链接https://leetcode-cn.com/problems/trapping-rain-water/

思路

  • 解法一:通过dp,计算出求出每个柱子左右两边最高的柱子,可以得到,当前位置能接雨水的量是 Math.min(leftMax[i], rightMax[i]) - height[i],然后把每个位置的结果累加起来即可。

    • dp 状态转义

      • 求左边最大值
        • leftMax[i] = Math.max(leftMax[i - 1], height[i - 1]) 1 <= i < n
      • 求右边最大值
        • rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]) 0 <= i < n - 1;
      • 边界
        • leftMax[0] = 0;
        • rightMax[n - 1] = 0;
    • 图解

      • image-20220504214458470
    • 代码:

      • /**
         * @param {number[]} height
         * @return {number}
         */
        var trap = function(height) {
            
            const n = height.length;
        
            // 这里已经处理了边界
            let leftMax = new Array(n).fill(0);
            let rightMax = new Array(n).fill(0);
        
            // 1. 求出每个数左边的最大值
        
            for (let i = 1; i < n; ++ i) {
                leftMax[i] = Math.max(leftMax[i - 1], height[i - 1]);
            }
        
            // 2. 求出每个数右边的最大值
            for (let i = n - 2; i >= 0; -- i) {
                rightMax[i] = Math.max(rightMax[i + 1], height[i + 1]);
            }
        
            // 3. 计算每个位置能接的水量
            let sum = 0;
            for (let i = 0; i < n; ++ i) {
                if (leftMax[i] > height[i] && rightMax[i] > height[i]) {
                    let h = Math.min(leftMax[i], rightMax[i]);
                    sum += h - height[i];
                }
            }
        
            return sum;
            
        };
        
  • 解法二:通过单调栈,维护一个递减的序列。当遍历的元素大于当前栈顶元素,那么当前栈顶能够被,当前遍历的元素和上一个栈顶 围成一个桶来接收雨水。不过此时只能计算出,最小的值。后面通过其他值来计算

    • 图解

      • image20220504214458470.png
    • 代码

      • /**
         * @param {number[]} height
         * @return {number}
         */
        var trap = function(height) {
            
            const n = height.length;
            const stack = new Array();
            // 单调栈写法
            let sum = 0;
            for (let i = 0; i < n; ++ i) {
                
                // 当前袁术和栈顶对比
                while(stack.length !== 0 && height[i] > height[stack[stack.length - 1]]) {
                    let top = stack.pop();
                    if (stack.length === 0)
                        break;
                    
                    let rainHeight = Math.min(height[i], height[stack[stack.length - 1]]) - height[top];
                    let rainArea = (i - stack[stack.length - 1] - 1) * rainHeight;
                    sum += rainArea;
                }
        
                stack.push(i);
            }
            
            return sum;
            
        };
        

43. 字符串相乘

题目链接https://leetcode-cn.com/problems/multiply-strings/

思路:我的思路是模拟乘法过程,将num2 每一位 和 num1 相乘,然后在将这些结果累加。不过有一个更好的解法,因为num1[i] * num2[j] 值必然是在 i + j 位,通过此特性即可计算出结果。

// 方法一
/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function(num1, num2) {
    if (num1 === "0" || num2 === "0")
        return "0";
    num1 = num1 + '';
    num2 = num2 + '';
    const len1 = num1.length;
    const len2 = num2.length;

    const store = new Array(len1 + len2 - 1).fill(0);

    for (let i = 0; i < len2; ++ i) {
        for (let j = 0; j < len1; ++ j) {
            store[i + j] += (+num2[i] * +num1[j]);
        }
    }

    let k = store.length;
    let t = 0;
    let res = "";
    while (k --) {
        t += store[k];
        res = t % 10 + res;
        t = Math.floor(t / 10);
    }

    return t > 0 ? (t + res) : res;
};


// 方法二
/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function(num1, num2) {
    if (num1 === "0" || num2 === "0")
        return "0";
    
    return bigMul(num1, num2);

    function mergeMulValue(l, r, bitMull) {
        if (l === r) return bitMull[l];
        let mid = Math.floor((l + r)/2);
        let num1 = mergeMulValue(l, mid, bitMull);
        let num2 = mergeMulValue(mid + 1, r, bitMull);
        return bigIncrement(num1, num2);
    }

    function bigIncrement(num1, num2) {
        if (num1.length < num2.length) {
            [num1, num2] = [num2, num1];
        }

        const len1 = num1.length;
        const len2 = num2.length;

        let res = "";
        let jw = 0;
        let t;
        for (let i = 0; i < len1; ++ i) {
            let a = num1[i].charCodeAt() - "0".charCodeAt();
            let b = 0;
            if (i < len2) {
                b = num2[i].charCodeAt() - "0".charCodeAt();
            }
            t = a + b + jw;
            jw = Math.floor(t / 10);
            t = t % 10;
            res += String(t);
        }

        if (jw) {
            res += String(jw);
        }
        

        
        return res;
    }

    function bigMul(num1, num2) {
        if (num1.length < num2.length) {
            [num1, num2] = [num2, num1];
        }

        num1 = num1.split("").reverse().join("");
        num2 = num2.split("").reverse().join("");

        const len1 = num1.length;
        const len2 = num2.length;

        let bitMull = [];

        for (let i = 0; i < len2; ++ i) {

            let a = num2[i].charCodeAt() - '0'.charCodeAt();

            if (a === 0)
                continue;

            let res = "";
            let jw = 0;
            let t;
            for (let j = 0; j < len1; ++ j) {
                let b = num1[j].charCodeAt() - '0'.charCodeAt();
                t  = a * b + jw;

                jw = Math.floor(t / 10);
                t = t % 10;

                res += String(t);

            }

            if (jw) 
                res += String(jw);

            for (let j = 0; j < i; ++ j)
                res = "0" + res;
            
            bitMull.push(res);
        }
        return mergeMulValue(0, bitMull.length - 1, bitMull).split("").reverse().join("");


    }
};

44. 通配符匹配

题目链接https://leetcode-cn.com/problems/wildcard-matching/

思路:动态规划

  • 状态表示:dp[i][j] 表示 s的前i个字符能否被,p 前j个字符匹配

  • 状态转义

    • p[j] = ‘*’
      • dp[i][j] = d[i - 1][j] || dp[i][j-1]
    • “?” 和字母
      • dp[i][j] = dp[i-1][j-1]
  • 边界判断

  • dp(0, 0) = false

  • dp(i, 0) = false

  • dp(0, j) = true 前j个字符全为 ‘*’

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function(s, p) {

    const n = s.length, m = p.length;
    const dp = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(false));
    dp[0][0] = true;

    for(let i = 1; i <= m; ++ i) {
        if (p[i - 1] !== '*')
            break;
        
        dp[0][i] = true;
    }

    for (let i = 1; i <= n; ++ i) {
        for (let j = 1; j <= m; ++ j) {
            if (p[j - 1] === '*') {
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            } 
            if (p[j - 1] === '?' || s[i - 1] === p[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }

    return dp[n][m];
};

45. 跳跃游戏 II

题目链接https://leetcode-cn.com/problems/jump-game-ii/

思路

  • dp解法

    • 状态表示 dp[i] 表示到达 i 的最小步数

    • 状态转移

      • dp[i] = dp[j] + nums[j] 0<= j < i, j + nums[j] >= i
    • 边界

      • dp[0] = 0;
      • dp[i] = INF; i > 0
    • 代码

      • /**
         * @param {number[]} nums
         * @return {number}
         */
        var jump = function(nums) {
            const n = nums.length;
            const dp = new Array(n).fill(Number.MAX_VALUE);
            dp[0] = 0;
        
            for (let i = 1; i < n; ++ i) {
        
                for (let j = i - 1; j >= 0; -- j) {
                    if (nums[j] + j >= i) {
                        dp[i] = Math.min(dp[i], dp[j] + 1);
                    }
                }
            }
        
            return dp[n - 1];
        };
        
  • 贪心

    • 将上一个最远距离范围内的位置遍历完,也就求出了下一个所能到达的最远距离,然后跟新下一个起跳点end为最远距离也就是跳一步

    • /**
       * @param {number[]} nums
       * @return {number}
       */
      var jump = function(nums) {
          
          let maxPos = 0;
          let end = 0;
          let res = 0;
          
          for (let i = 0; i < nums.length - 1; ++ i) {
              maxPos = Math.max(maxPos, i + nums[i]);
              if (i === end) {
                  end = maxPos;
                  res ++;
              }
          }
      
          return res;
      
      };
      

46. 全排列

题目链接:https://leetcode-cn.com/problems/permutations/

思路:dfs 枚举每个当前位置能够填写的所有值。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {


    const n = nums.length;
    const st = new Array(n).fill(false);

    let res = [];
    let cur = [];
    dfs(0);

    return res;
    function dfs(u) {
        if (u === n) {
            res.push([...cur]);
            return;
        }

        for (let i = 0; i < n; ++ i) {
            if (!st[i]) {
                st[i] = true;
                cur.push(nums[i]);
                dfs(u + 1);
                cur.pop();
                st[i] = false;
            }
        }
    }
    

};

47. 全排列 II

题目链接https://leetcode-cn.com/problems/permutations-ii/

思路:求所有的组合,也就是枚举组合中的每一个位置上能够填的数。出现重复的情况就是,在同一个位置上填过之前相同的数。只要避免这个过程就能得出答案。所以我们将数组排序,通过判断当前位置是否填过同一个数,来进行去重。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
    const n = nums.length;
    const st = new Array(n).fill(false);
    
    // 排序
    nums.sort((a, b) => a - b);
    let res = [];
    let cur = [];
    dfs(0);

    return res;
    function dfs(u) {
        if (u === n) {
            res.push([...cur]);
            return;
        }

        for (let i = 0; i < n; ++ i) {
            // st[i - 1] === false , 表示之前这个位置已经枚举过 nums[i - 1] 了, 如果放相同的数将会产生相同的结果
            if (i > 0 && nums[i] === nums[i - 1] && !st[i - 1])
                continue;
            if (!st[i]) {
                st[i] = true;
                cur.push(nums[i]);
                dfs(u + 1);
                cur.pop();
                st[i] = false;
            }
            
        }
    }
};

48. 旋转图像

题目链接https://leetcode-cn.com/problems/rotate-image/

思路:将矩阵先沿着中线互换上下元素,然后就可以发现,转换后的矩阵沿着角线翻转, 就是原始矩阵顺时针反转90度的结果。

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function(matrix) {
    const n = matrix.length;
    
    for (let i = 0; i < Math.floor(n / 2); ++ i) {
        for (let j = 0; j < n; ++ j) {
            [matrix[i][j],matrix[n - 1 - i][j]] = [matrix[n - 1 - i][j], matrix[i][j]];
        }
    }


    for (let i = 0; i < n; ++ i) {
        for (let j = 0; j < i; ++ j) {
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
        }
    }


    return matrix;

};

49. 字母异位词分组

题目链接https://leetcode-cn.com/problems/group-anagrams/

思路:统计每个字符串的字符数,然后将统计的字符数组转换成字符串当成key,如果key一样说明是字母异位词。则将其加入到对应的数组中。

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {

    const n = strs.length;
    const mp = new Map();

    for (let i = 0; i < n; ++ i) {
        const count = new Array(26).fill(0);
        for (let c of strs[i]) {
            let num = c.charCodeAt() - "a".charCodeAt();
            count[num] ++;
        }
        let key = count.toString();
        let arr = mp.has(key) ? mp.get(key): new Array();
        if (arr.length === 0)
            mp.set(key, arr);
        arr.push(strs[i]);
    }

    const res = [];
    for (const values of mp.values()) {
        res.push(values);
    }

    return res;
};

50. Pow(x, n)

题目链接https://leetcode-cn.com/problems/powx-n/

思路:适用快速幂计算,注意处理 最小值转换成整数越界问题

/**
 * @param {number} x
 * @param {number} n
 * @return {number}
 */
var myPow = function(x, n) {
    return quickM(x, n);


    function quickM(a, b) {
        if (b < 0)  {
            b = -b;
            a = 1 / a;
        }
            
        let res = 1;
        while(b) {
            if (b & 1)
                res *= a;
            a = a * a;
            b >>>= 1;
        }

        return res;
    }
};

51. N 皇后

题目连接:https://leetcode-cn.com/problems/n-queens/

思路:根全排列样,只是每一行每一列和每条对角线上都只能有一个皇后。所以我们可以枚举每一行,判断当前行的皇后放在哪个列上。就可以得出答案了,

  • 对角线如何判断: 用截距表示
/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {

    // 1. 构造数组
    const mp = new Array(n).fill('.'.repeat(n));
    const col = new Array(n).fill(false), lg = new Array(n * 2).fill(false), dlg = new Array(n * 2).fill(false);
    const res = [];
    dfs(0);
    return res;

    function dfs(u) {
        if (u === n) {
            res.push([...mp]);
            return;
        }

        for (let i = 0; i < n; ++ i) {
            if (!col[i] && !lg[u + i] && !dlg[n + u - i]) {
                col[i] = lg[u + i] = dlg[n + u - i] = true;
                const copyString = mp[u];
                mp[u] = mp[u].slice(0, i) + 'Q' + mp[u].slice(i + 1);
                dfs(u + 1);
                mp[u] = copyString;
                col[i] = lg[u + i] = dlg[n + u - i] = false;
            }
        }

    }
};

52. N皇后 II

题目链接https://leetcode-cn.com/problems/n-queens-ii/

思路:和51题思路一样

/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function(n) {

    const col = new Array(n).fill(false),
          lg = new Array(n * 2 - 1).fill(false),
          dlg = new Array(n * 2 - 1).fill(false);
        
    let res = 0;
    dfs(0);
    return res;
    function dfs(u) {
        if (u === n) {
            res ++;
            return;
        }

        for (let i = 0; i < n; ++ i) {
            if (!col[i] && !lg[u + i] && !dlg[n + u - i]) {
                col[i] = lg[u + i] = dlg[n + u - i] = true;
                dfs(u + 1);
                col[i] = lg[u + i] = dlg[n + u - i] = false;
            }
        }
    }
};

53. 最大子数组和

题目链接https://leetcode-cn.com/problems/maximum-subarray/

思路:动态规划

  • 状态表示:dp[i] 表示当前第 i 结尾的数的最大连续子序列和。
  • 状态转移:dp[i] = max(dp[i - 1] + nums[i], nums[i]);
  • 边界条件:dp[0] = 0;
  • 因为状态转移只和前 i - 1 的 数有关,可将省略数组
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {

    
    let res = -Number.MAX_VALUE;
    let pre = 0;

    /*
        1. dp[i] 表示以 i 结尾的连续子序列最大和
        2. 状态转移  dp[i] = max(dp[i - 1] + nums[i], nums[i]);
    */
    for (let i = 0; i < nums.length; ++ i) {
        pre = Math.max(pre + nums[i], nums[i]);
        res = Math.max(res, pre);
    }

    return res;
};

54. 螺旋矩阵

题目链接https://leetcode-cn.com/problems/spiral-matrix/

思路:用四个指针维护上下左右四个边界,然后动态的缩小边界即可。模拟整个过程

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {

    let res = [];
    const n = matrix.length, m = matrix[0].length;

    let left = 0, right = m - 1, top = 0, bottom = n - 1;

    while (true) {
        for (let i = left; i <= right; ++ i)
            res.push(matrix[top][i]);
        top ++;
        if (top > bottom) break;
        for (let i = top; i <= bottom; ++ i) 
            res.push(matrix[i][right]);
        right --;
        if (left > right) break;
        for (let i = right; i >= left; -- i)
            res.push(matrix[bottom][i]);
        bottom --;
        if (top > bottom) break;
        for (let i = bottom; i >= top; -- i)
            res.push(matrix[i][left])
        left ++;
        if (left > right) break;
    }
    
    return res;
};

55. 跳跃游戏

题目链接https://leetcode-cn.com/problems/jump-game/)

思路

  • 动态维护当前可达范围内能够到达的最远距离。在最远距离内的点是可达的,可以可达点为新的起点寻找可达最远距离。
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function(nums) {

   let maxDis = 0;

   for (let i = 0; i < nums.length; ++ i) {
        if (maxDis >= i)
            maxDis = Math.max(maxDis, i + nums[i]);
        if (maxDis >= nums.length - 1)
            return true;
   }

   return false;

};

56. 合并区间

题目链接https://leetcode-cn.com/problems/merge-intervals/

思路:贪心,将数组按区间右边界进行排序。然后,再模拟合并的过程。不过需要注意,会出现前面都不能合并,但是到最后来了一个超级大范围的数据,将前面不能合并的数据合并了。解决这种情况,我们只需要从 右边界最大的开始从后向前进行合并即可。

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {

    // 1. 按范围排序
    intervals.sort((a, b) => a[1] - b[1]);

    let lastLeft = intervals[intervals.length - 1][0], lastRight = intervals[intervals.length - 1][1];
    const res = [];
    for (let i = intervals.length - 1; i >= 0; -- i) {
        let [left, right] = intervals[i];   
        if (lastLeft <= right && lastLeft >= left) {
            lastLeft = left;
        } else if (lastLeft > right) {
            res.push([lastLeft, lastRight]);
            lastLeft = left;
            lastRight = right;
        }
    }

    res.push([lastLeft, lastRight]);


    return res;
};

57. 插入区间

**题目链接:**https://leetcode-cn.com/problems/insert-interval/

思路

  • 可使用二分优化,找出待插入区间的位置,然后合并周围区间,省略

  • 直接和 56 题做法一样

    • /**
       * @param {number[][]} intervals
       * @param {number[]} newInterval
       * @return {number[][]}
       */
      var insert = function(intervals, newInterval) {
        let newarr = [...intervals,newInterval];
        
        newarr.sort((a,b)=>a[1] - b[1]);
      
        let res = [];
        let lastleft = newarr[newarr.length - 1][0];
        let lastright = newarr[newarr.length - 1][1];
        
        for(let i=newarr.length-1; i >= 0; -- i)                 {
            let [left, right] = newarr[i];
            if (lastleft <= right && lastleft >= left) {
                lastleft = left;
            } else if (lastleft > right) {
                res.push([lastleft, lastright]);
                lastleft = left;
                lastright = right;
            }
        }
      
        res.push([lastleft, lastright]);
      
        return res.sort((a, b) => a[0] - b[0]);
      };
      

58. 最后一个单词的长度

题目链接https://leetcode-cn.com/problems/length-of-last-word/

思路:水题水题

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLastWord = function(s) {
    let newString = s.trim();

    return newString.slice(newString.lastIndexOf(" ") + 1).length;

};

59. 螺旋矩阵 II

题目链接https://leetcode-cn.com/problems/spiral-matrix-ii/

思路:和54题思路一样

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function(n) {
    let res = new Array(n).fill(0).map(() => new Array(n).fill(0));

    let left = 0, right = n - 1, top = 0, bottom = n - 1;
    let k = 1;
    while(true) {
        for (let i = left; i <= right; ++ i) {
            res[top][i] = k ++;
        }
            
        top ++;
        if (top > bottom)
            break;
        for (let i = top; i <= bottom; ++ i) {
            res[i][right] = k ++;
        }
        right --;
        if (left > right)
            break;
        for (let i = right; i >= left; -- i) {
            res[bottom][i] = k ++;
        }
        bottom --;
        if (top > bottom)
            break;
        for (let i = bottom; i >= top; -- i) {
            res[i][left] = k ++;
        }
        left ++;
        if (left > right)
            break;
    }

    
    return res;
};

60. 排列序列

题目链接https://leetcode-cn.com/problems/permutation-sequence/

思路:直接正常全排列即可,用一个变量统计当前排列数量,当数量 为 k 时就时答案,水题水题。

/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getPermutation = function(n, k) {


    let st  = new Array(n + 1).fill(false);
    let ans = "";
    
    let flag = false;
    let cnt = 0;
    const dfs = (s) => {
        if (flag)
            return;
        if (s.length === n) {
            cnt ++;
            if (cnt === k) {
                ans = s;
                flag = true;
            }
            return;
        }

        for (let i = 1; i <= n; ++ i) {
            if (!st[i]) {
                st[i] = true;
                dfs(s + i);
                st[i] = false;
            }
        }


    } 

    dfs("");
    return ans;
};

61. 旋转链表

题目链接https://leetcode-cn.com/problems/rotate-list/

思路:注意处理k的有效值,具体看代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
    if (head === null) {
        return null;
    }
    let n = 0;
    let p = head;
    // 计算链表长度
    while(p.next !== null) {
        n ++;
        p = p.next;
    }
    n ++;
    // 将链表变成循环链表
    p.next = head;

    // 计算有效移动次数,当为 k = n 的时候相当于没转。k表示head逆时针移动k位,我们改成顺时针移动 n - k
    let c = n - k % n;
    p = head;
    while(c) {
        c --;
        p = head;
        head = head.next;
    }

    // 将首尾断开
    p.next = null;
    return head;
};

62. 不同路径

题目链接https://leetcode-cn.com/problems/unique-paths/

思路: 动态规划

  • 状态表示:dp(i, j) 表示到达 (i, j) 这个点的不同路径数
  • 状态转移:dp(i, j) = dp(i - 1, j) + dp(i, j - 1)
  • 边界条件:dp(1, 1) = 1;
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {

    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    dp[1][1] = 1;

    for (let i = 1; i <= m; ++ i) {
        for (let j = 1; j <= n; ++ j)
            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j] + dp[i][j - 1]);
    }


    return dp[m][n];
};

63. 不同路径 II

题目链接https://leetcode-cn.com/problems/unique-paths-ii/

思路:和 62 题思路一摸一样,加个特判即可

/**
 * @param {number[][]} obstacleGrid
 * @return {number}
 */
var uniquePathsWithObstacles = function(obstacleGrid) {

    const n = obstacleGrid.length;
    const m = obstacleGrid[0].length;

    let dp = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));
    dp[1][1] = 1;
    for (let i = 1; i <= n; ++ i) {
        for (let j = 1; j <= m; ++ j) {
            dp[i][j] = Math.max(dp[i][j], dp[i - 1][j] + dp[i][j - 1]);
            if (obstacleGrid[i - 1][j - 1] === 1)
                dp[i][j] = 0;
        }
    }

    return dp[n][m];
};

64. 最小路径和

题目链接https://leetcode-cn.com/problems/minimum-path-sum/

思路:动态规划

  • 状态表示:dp(i, j) 表示到 (i, j) 点的最小数值。
  • 状态转移:dp(i, j) = min(dp(i, j - 1), dp(i - 1, j)) + grid(i, j);
  • 边界条件:dp(i, j) = +INF, dp(0, 1) = 0;
/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {

    const n = grid.length;
    const m = grid[0].length;

    const dp = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(Number.MAX_VALUE));
    dp[0][1] = 0;
    for (let i = 1; i <= n; ++ i) {
        for (let j = 1; j <= m; ++ j) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
        }
    }
   
   return dp[n][m];
};

65. 有效数字

题目链接https://leetcode-cn.com/problems/valid-number/

思路:使用三个变量分别保存,数字,‘.', ‘e/E’ 是否出现过。依次枚举字符串每个元素。

  • s[i] 是数值,这标识numflag = true
  • s[i] 是 ‘.’, 则必须要求,dotflag = false && eflag = false, 因为e后面必须是整数
  • s[i] 是 e/E, 要求eFlag = false, numflag = true, 因为 e 前面必须有数值才合法
  • s[i] 是 + / -, 要么 是字符串第一个元素,要么是 e/E 后面的第一个元素
  • 其他情况直接不成立
  • 最后,要求必须有数值
/**
 * @param {string} s
 * @return {boolean}
 */
var isNumber = function(s) {
   let [numFlag, dotFlag, eFlag] = [false, false, false];

   for (let i = 0; i < s.length; ++ i) {
       if (s[i] >= '0' && s[i] <= '9') {
           numFlag = true;
       } else if (s[i] === '.' && !dotFlag && !eFlag) {
           dotFlag = true;
       } else if ((s[i] === 'e' || s[i] === 'E') && !eFlag && numFlag) {
           numFlag = false;
           eFlag = true;
       } else if ((s[i] == '+' || s[i] == '-') && (i == 0 || s[i - 1] === 'e' || s[i - 1] === 'E')) {
           continue;
       } else {
           return false;
       }
   }

   return numFlag;
};

66. 加一

题目链接https://leetcode.cn/problems/plus-one/

思路:模拟即可,注意进位

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {

    const n = digits.length;
    let jw = 0;
    digits[n - 1] += 1;

    for (let i = digits.length - 1; i >= 0; -- i) {
        digits[i] = jw + digits[i]; 
        jw = Math.floor(digits[i] / 10);
        digits[i] = digits[i] % 10;
        if (jw === 0)
            break;
    }

    if (jw)
        digits.unshift(jw);
    
    return digits;
};

67. 二进制求和

题目链接https://leetcode.cn/problems/add-binary/

思路:将两个二进制长度补到相同,不够补零。然后模拟相加,遇2进位

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function(a, b) {
    if (a.length < b.length)
        [a, b] = [b, a];
    
    b = "0".repeat(a.length - b.length) + b;

    let jw = 0;
    let res = "";

    for (let i = a.length - 1; i >= 0; -- i) {
        const n1 = Number(a[i]);
        const n2 = Number(b[i]);

        let sum = n1 + n2 + jw;
        jw = Math.floor(sum / 2);
        sum %= 2;

        res = sum + res;
    }

    if (jw) 
        res = jw + res;
    
    return res;
};

68. 文本左右对齐

题目链接https://leetcode.cn/problems/text-justification/

思路:因为是单词,所以潜在条件是,每行相邻单词间至少有一个空白。所以,我们尽可能在每一行多放单词。

  • 特殊情况
    • 当前行是最后一行,单词左对其,并在后面填充空格
    • 当前行只有一个单词,单词左对其,并在后面填充空格
  • 一般情况
    • 该行有多个单词,每个单词间的空白,应该是 剩余可填空白数 / (空白数-1)。
    • 如果不能整数,剩余空白应该 填充在该行前几个单词之间
/**
 * @param {string[]} words
 * @param {number} maxWidth
 * @return {string[]}
 */
var fullJustify = function(words, maxWidth) {
    const ans = [];
    let right = 0, n = words.length;

    while (true) {
        const left = right;
        let sumLen = 0; // 每行最大放的单词数
        while(right < n && sumLen + words[right].length + right - left <= maxWidth) {
            sumLen += words[right].length;
            right ++;
        }

        // 如果当前是最后一行:单词左对其,且单词间只有一个空格,在行末填充空格
        if (right === n) {
            const s = words.slice(left).join(' ');
            ans.push(s + " ".repeat(maxWidth - s.length));
            break;
        }

        const numWords = right - left;
        const numSpace = maxWidth - sumLen;

        // 当前行只有一个单词:左对齐,后面补空格
        if (numWords === 1) {
            ans.push(words[left] + " ".repeat(numSpace));
            continue;
        }

        // 当前不只有一个单词
        const avgSpaces = Math.floor(numSpace / (numWords - 1));
        const extraSpace = numSpace % (numWords - 1);
        const s1 = words.slice(left, left + extraSpace + 1).join(" ".repeat(avgSpaces + 1));
        const s2 = words.slice(left + extraSpace + 1, right).join(" ".repeat(avgSpaces));
        ans.push(s1 + " ".repeat(avgSpaces) + s2);
    }

    return ans;
};

69. x 的平方根

题目链接https://leetcode.cn/problems/sqrtx/

思路:浮点数二分,二分100次机会无限接近于答案,然后在取整数部分。

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {

    let left = 0, right = x;

    for (let i = 0; i < 100; ++ i) {
        let mid = (left + right) / 2;
        if (mid * mid > x)
            right = mid;
        else 
            left = mid;
    }

    return parseInt(left);
};

70. 爬楼梯

题目链接https://leetcode.cn/problems/climbing-stairs/

思路:动态规划

  • 状态表示:dp[i] 表示 到达 i 层的路径数
  • 状态转移:dp[i] = dp[i - 1] + dp[i - 2] , i >=2
  • 边界条件:dp[0] = 1, dp[1] = 1;
  • 空间优化:因为下一个答案只和前两个数有关,所以通过滚动数组可优化空间复杂度
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {

    let a = 1, b = 1, c = 1;

    for (let i = 2; i <= n; ++ i) {
        c = a + b;
        a = b;
        b = c;
    }

    return c;
};

71. 简化路径

题目链接https://leetcode.cn/problems/simplify-path/

思路:先将path以 / 分割成数组,空白表示当前为两个斜杠间组成,用栈来维护路径上的每个文件名,当遇到 ‘…’ 就弹出当前栈顶。遇到 ‘.’ 就直接不处理即可。

/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function(path) {
    let paths = path.split('/');
    // console.log(paths);
    let res = [];
    for (let i = 0; i < paths.length; ++ i) {
        if (paths[i] === '' || paths[i] === '.') {
            continue;
        }

        if (paths[i] === "..") {
            if (res.length !== 0) {
                res.pop();
            }
            continue;
        }
        res.push(paths[i]);
    }

    // console.log(res);
    let s = res.join("/");
    s = "/" + s;
    
    return s;
};

72. 编辑距离

题目链接https://leetcode.cn/problems/edit-distance/

思路:动态规划,两个字符串的操作数未6,但是其中有等价的。最终可以得出如下操作

  • 操作
    • A 字符串中插入一个字符(等价B中删除一个字符)
    • B 字符串中插入一个字符 (同上)
    • A 字符串中修改一个字符
  • 状态表示:dp(i, j) 表示字符串word1(0 ~i) 要转换到 word2(0 ~ j) 的最小编辑距离
  • 状态转移:dp(i, j) = 1 + min(dp(i, j - 1), dp(i - 1, j), dp(i - 1, j - 1) + (word1(i - 1) !== word2(j - 1)));
  • 边界:dp(0, i) = i; dp(j, 0) = j;
/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    const n = word1.length;
    const m = word2.length;

    const dp = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(Number.MAX_VALUE));
    dp[0][0] = 0;
    for (let i = 1; i <= n; ++ i)
        dp[i][0] = i;

    for (let j = 1; j <= m; ++ j)
        dp[0][j] = j;

    for (let i = 1; i <= n; ++ i) {
        for (let j = 1; j <= m; ++ j) {
            if (word1[i - 1] === word2[j - 1])
                dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] - 1);
            else 
                dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
        }
    }

    return dp[n][m];
};

73. 矩阵置零

题目链接https://leetcode.cn/problems/set-matrix-zeroes/

思路

  • 思路一:使用两个标记数组,标记每行和每列是否出现0,先遍历一次矩阵,然后再进行置零

    • /**
       * @param {number[][]} matrix
       * @return {void} Do not return anything, modify matrix in-place instead.
       */
      var setZeroes = function(matrix) {
          const n = matrix.length;
          const m = matrix[0].length;
      
          const col = new Array(m).fill(false);
          const row = new Array(n).fill(false);
      
          for (let i = 0; i < n; ++ i) {
              for (let j = 0; j < m; ++ j) {
                  if (matrix[i][j] === 0) {
                      row[i] = true;
                      col[j] = true;
                  }
              }
          }
      
          for (let i = 0; i < n; ++ i) {
              for (let j = 0; j < m; ++ j) {
                  if (row[i] || col[j])
                      matrix[i][j] = 0;
              }
          }
          
      
          return matrix;
      };
      
  • 思路二:在思路一的基础上,优化空间复杂度。使用矩阵中的 第 一 行 和 第 一 列

74. 搜索二维矩阵

题目链接https://leetcode.cn/problems/search-a-2d-matrix/

思路:同分,注意下标的转换,和循环结束

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
  const n = matrix.length;
  const m = matrix[0].length;

  let l = 0,
    r = n * m - 1;
  while (l < r) {
    let mid = (l + r + 1) >> 1;
    let x = Math.trunc(mid / m);
    let y = mid % m;
    // break;
    if (matrix[x][y] > target) r = mid - 1;
    else l = mid;
  }

  let x = Math.trunc(l / m);
  let y = l % m;

  return matrix[x][y] === target;
};

77. 组合

题目链接https://leetcode.cn/problems/combinations/

思路

  • 思路一:二进制枚举,每个数是否可选, 官方有更精巧的解法

    • /**
       * @param {number} n
       * @param {number} k
       * @return {number[][]}
       */
      var combine = function(n, k) {
      
          const res = [];
      
          for(let i = 0; i < 1 << n; ++ i) {
              let ans = [];
      
              for (let j = 0; j < n; ++ j) {
                  if (ans.length > k)
                      break;
                  if ((i >> j) & 1) {
                      ans.push(j + 1);
                  }
              }
      
              if (ans.length === k) {
                  res.push(ans);
              }
          }
      
          return res;
      };
      
  • 思路二:深度优先遍历+减枝

    • /**
       * @param {number} n
       * @param {number} k
       * @return {number[][]}
       */
      // 有 k 个位置,来放置 n 个数中的 k 个,就模拟当前数是否放置即可
      var combine = function(n, k) {
      
          const res = [];
          const st = new Array(n + 1).fill(false);
          const currArr = [];
          const dfs = (u) => {
              // 剩余的数加上已经选的数不能满足 k, 就直接返回 减枝叶
              if (currArr.length + n - u + 1 < k) {
                  return;
              }
      
              if (currArr.length === k) {
                  res.push([...currArr]);
                  return;
              }
      
              currArr.push(u);
              dfs(u + 1);
              currArr.pop();
      
              dfs(u + 1);
          }
      
          dfs(1);
          return res;
      };
      
      
      /**
       * @param {number} n
       * @param {number} k
       * @return {number[][]}
       */
      var combine = function(n, k) {
      
          const res = [];
          const st = new Array(n + 1).fill(false);
          const currArr = [];
          const dfs = (index) => {
              if (currArr.length === k) {
                  res.push([...currArr]);
                  return;
              }
      
              for (let i = index; i <= n; ++ i) {
                  if (!st[i]) {
                      st[i] = true;
                      currArr.push(i);
                      dfs(i + 1);
                      currArr.pop();
                      st[i] = false;
                  }
              }
          }
      
          dfs(1);
          return res;
      };
      

78. 子集

题目链接https://leetcode.cn/problems/subsets/

思路:二进制枚举,DFS

// 二进制
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    let res = [];
    for (let i = 0; i < 1 << nums.length; ++ i) {
        let currArr = [];

        for (let j = 0; j < nums.length; ++ j) {
            if ((i >> j) & 1)
                currArr.push(nums[j]);
        }

        res.push(currArr);
    }

    return res;
};


// dfs

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    const n = nums.length;
    let ans = [];
    let a = []; // 子集

    dfs(0);

    return ans;

    function dfs(u) {
        if (u === n) {
            ans.push(Array.from(a));
            return;
        }

        // 1. 不选第 u 个数
        arguments.callee(u + 1);
        // 2. 选第u个数
        a.push(nums[u]);
        
        arguments.callee(u + 1);
        
        a.pop();
        

    }
};

79. 单词搜索

题目链接https://leetcode.cn/problems/word-search/

思路:dfs 搜索,每次搜索符合条件的坐标周围的数。先遍历数组,如果当前字符board(i, j) === word(0), 就开始搜索

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    const n = board.length;
    const m = board[0].length;
    const dx = [1, -1, 0, 0];
    const dy = [0, 0, 1, -1];
    let st;


    for (let i = 0; i < n; ++ i) {
        for (let j = 0; j < m; ++ j) {
            if (board[i][j] === word[0]) {
                st = new Array(n).fill(0).map(() => new Array(m).fill(false));
                st[i][j] = true;
                if (dfs(i, j, 1)) {
                    return true;
                }
            }
        }
    }

   

    
    return false;
    function dfs(x, y, u) {
        // console.log(`X:${x} Y:${y} char:${board[x][y]}`);
        if (u >= word.length) {
            return true;
        }
        
        for (let i = 0; i < 4; ++ i) {
            const nx = x + dx[i];
            const ny = y + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m || st[nx][ny])
                continue;
            
            if (word[u] !== board[nx][ny])
                continue;
            st[nx][ny] = true;
            if (dfs(nx, ny, u + 1)) {
                return true;
            }
            st[nx][ny] = false;
        }

        return false;
    };

    

};

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

题目链接https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/

思路

  • 处理连续个数大于2的问题:
    • 我们用 i 表示当前已经去重的数组末尾元素位置。
    • 当 nums(i) === nums(j) 时,我们需要判断 nums(i - 1) 是否等于 nums(i)。如果不等于则说明该重复数未满两个,如果等于则表示该重复数已经两个了。
  • 处理不同的数
    • 如果当前的数是一般 nums(i) 不相同则,直接添加 nums(i + 1) 的位置。
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let i = 0, j = 0;
    for (j = 1; j < nums.length; ++ j) {
        if (nums[i] === nums[j] && (i === 0 || nums[i - 1] !== nums[i])) {
            nums[++ i] = nums[j];
        } else if (nums[i] !== nums[j]){
            nums[++ i] = nums[j];
        }
    }

    return i + 1;
};

// 一种更妙的写法,当 i < 2 时不需要判断是否大于2,当 i>=2 时,通过 判断当前数 与前两个数是否相等
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let i = 0;

    for (let x of nums) {
        if (i < 2 || x > nums[i - 2])
            nums[i ++] = x;
    }

    return i;
};


81. 搜索旋转排序数组 II

题目链接https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/

思路:数组以k点旋转过后,会形成两个升序序列。我们可以通过判断mid在哪个升序序列中,进而进行收缩范围。不过当有重复元素的时候。可能无法判断mid在哪个升序序列中,所以需要打破这个情况。令r–或l++

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {boolean}
 */
var search = function(nums, target) {

    const n = nums.length;

    let l = 0, r = n - 1;
    while (l <= r) {
        let mid = Math.trunc((l + r) / 2);

        if (nums[mid] === target)
            return true;
        // [1,0,1,1,1] 0
        // nums[l] = 1, nums[mid] = 1, nums[r] = 1, 无法判断当前的mid在哪个区间,那么直接让l,r向中间收缩即可 ,只要能打破这个情况即可
        if (nums[l] === nums[mid] && nums[mid] === nums[r]) {
            // l ++;
            r --;
        }
        else if (nums[l] <= nums[mid]) {
            if (nums[l] <= target && nums[mid] > target)
                r = mid - 1;
            else
                l = mid + 1;
        } else {
            if (nums[r] >= target && nums[mid] < target)
                l = mid + 1;
            else 
                r = mid - 1;

        }
    }

    return false;
};

82. 删除排序链表中的重复元素 II

题目链接https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/

思路:用一个指针 p 维护当前没有重复结点链表的尾结点。然后使用另一个指针q来遍历链表,如果 q.val == q.next.val 那么就找到重复这段最后一个元素,然后令p.next = q.next。如果不存在 q.val == q.next.val 的情况,相当于 q 指向的结点是不重复的值。直接加入p结点的尾部亦可。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    const newHead = new ListNode(-101, head);
    let p = newHead;
    let q = newHead.next;

    while(q != null) {
        
        let flag = false;
        while(q.next != null && q.val === q.next.val) {
            q = q.next;
            flag = true;
        }
        if (flag)
            p.next = q.next;
        else 
            p = p.next;

        q = q.next;
    }

    return newHead.next;
};

83. 删除排序链表中的重复元素

题目链接https://leetcode.cn/problems/remove-duplicates-from-sorted-list/

思路:用 p 指针维护去重后链表的尾结点,q指针遍历链表,发现重复段就找到当前重复段紧挨着的不同结点。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {

    const newHead = new ListNode(-101, head);

    let p = newHead;
    let q = newHead.next;

    while (q != null) {
        if (p.val === q.val) {
            while(q != null && p.val === q.val)
                q = q.next;
            
            p.next = q;
        }

        if (q === null)
            break;
        
        q = q.next;
        p = p.next;
    }

    return newHead.next;
};

84. 柱状图中最大的矩形

题目链接https://leetcode.cn/problems/largest-rectangle-in-histogram/

思路:利用单调递增栈,当遇到的高度小于等于当前栈顶时,弹出栈中元素并同时计算弹出元素能够组成的最大面积,使得当前栈插入当前元素依旧满足单调性,并同时维护一个宽度,表示比当前高度大的组成的宽度,也就是因为当前元素弹出的元素。

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
    
    heights.push(0);
    const n = heights.length;
    let stack = new Int32Array(n), w = new Int32Array(n);
    let tt = -1;
    let ans = 0;
    for (let i = 0; i < n; ++ i) {
        if (tt === -1 || stack[tt] < heights[i]) {
            stack[++ tt] = heights[i];
            w[tt] = 1;
        } else {
            let width = 0;
            while(tt !== -1 && stack[tt] >= heights[i]) {
                width += w[tt];
                ans = Math.max(ans, width * stack[tt]);
                tt --;
            }

            stack[++ tt] = heights[i];
            w[tt] = width + 1;
        }

    }

    return ans;
};

89. 格雷编码

题目链接:https://leetcode.cn/problems/gray-code/

思路:不理解啊,背了公式 (i >> 1)^ i

/**
 * @param {number} n
 * @return {number[]}
 */
var grayCode = function(n) {
    const res = [];

    for (let i = 0; i < 1 << n; ++ i) {
        res.push(i ^ (i >> 1));
    }
    
    return res;
};

90. 子集 II

题目链接https://leetcode.cn/problems/subsets-ii/

思路:通过去重,枚举子集的时候判断当前这个位置是否枚举过相同的数。如果枚举过直接跳过,因为相同的数的组合已经枚举过了。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {

    const n = nums.length;
    const res = [];
    const currArr = [];
    nums.sort((a, b) => a-b);
    const st = new Array(n).fill(false);

    const dfs = function (index) {
        // 添加到子集
        res.push([...currArr]);
        if (index >= n)
            return;
        for(let i = index; i < n; ++ i) {
            if (i > index && nums[i] === nums[i - 1])
                continue;
            currArr.push(nums[i]);
            dfs(i + 1);
            currArr.pop();
        }
    };

    dfs(0);
    return res;
};

91. 解码方法

题目链接https://leetcode.cn/problems/decode-ways/

思路:动态规划

  • 首先我们考虑,字符串开头是 0 的情况,必然不存在解码方式。
  • 动态规划
    • 状态表示:f(i) 表示前 i 个字符的不同解码方法数
    • 状态转义:
      • f(i) += f(i - 1) , s[i] !== ‘0’
      • f(i) += f(i - 2), s[i - 1] !== ‘0’ && Number(s[i - 1] + s[i]) <= 26
/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function(s) {

    if (s[0] === '0')
        return 0;

    const n = s.length;
    s = " " + s;

    const f = new Array(n + 1).fill(0);
    f[0] = 1;
    for (let i = 1; i <= n; ++ i) {
        if (s[i] !== '0') {
            f[i] = f[i - 1];
        }
        // console.log(s[i - 1] + s[i], checkIsZM(Number(s[i - 1] + s[i])));
        if (i > 1 && s[i - 1] !== "0" && checkIsZM(Number(s[i - 1] + s[i]))) {
            f[i] += f[i - 2];
        }
    }

    return f[n];
    
};

function checkIsZM(num) {
    let c = String.fromCharCode((num + "A".charCodeAt() - 1));
    if (c >= "A" && c <= "Z") {
        return true;
    }

    return false;
}

92. 反转链表 II

题目链接https://leetcode.cn/problems/reverse-linked-list-ii/

思路

  • 当left == right 是直接返回head
  • 然后,使用 p 维护这段反转链表的前一个结点,使用 tail 维护 当前已经反转链表的尾部结点。用 v 来遍历 left + 1 ~ right 的结点。让 tail.next 指向 v.next, 然后 把 v 结点插入到 p 结点后面。让v 指向下一个结点,v = tail.next, 因为 tail.next 保存的是 当前遍历 v 的 v.next.
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function(head, left, right) {
    if (left === right)
        return head;
    
    const newHead = new ListNode(undefined, head);
    let p = newHead;
    let v = newHead.next;
    let tail = null;
    let currOrder = 0;

    while (v !== null) {
        ++ currOrder;
        if (currOrder > right) {
            break;
        }
        if (currOrder === left) {
            tail = v;
        } else if (currOrder > left && currOrder <= right) {
            // console.log(p.val, v.val, tail.val);
            let c = v.next;
            v.next = p.next;
            p.next = v;
            tail.next = c;
        }

        if (tail === null) {
            p = p.next;
            v = v.next;
        } else {
            v = tail.next;
        }
    }

    return newHead.next;
};

93. 复原 IP 地址

题目链接https://leetcode.cn/problems/restore-ip-addresses/

思路:全排列,相当于 有 四个 位置待填。然后我们枚举字符串每个位置的长度。判断该长度字串是否满足条件ip地址的条件。

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function(s) {
    // 如果当前的长度大于,12 位那必然不是一个正确的ip地址
    if (s.length > 12) {
        return [];
    }
    const n = s.length;
    const res = [];
    const currArr = [];
    const dfs = function (u, i) {
        // 如果当前4个位置枚举完了,字符串未到末尾 或 字符串到末尾了,4 个位置未枚举完成 都剪去
        if ((u >= 4 && i < n) || (u < 4 && i >= n))
            return;
        // 满足条件
        if (u === 4 && i === n) {
            res.push(currArr.join("."));
            return;
        }

        // 枚举长度,每一位的长度 是 1,2,3
        for (let len = 1; len <= 3 && i + len <= n; len ++) {

            if (len !== 1 && s[i] === "0") {
                break;
            }
            if (len === 3 && Number(s.slice(i, i + len)) > 255) {
                break;
            }

            currArr.push(s.slice(i, i + len));
            dfs(u + 1, i + len);
            currArr.pop();

            // if (len === 1) {
            //     currArr.push(s[i]);
            //     dfs(u + 1, i + len);
            //     currArr.pop();
            // } else if (len === 2) {
            //     if (s[i] !== "0") {
            //         currArr.push(s[i] + s[i + 1]);
            //         dfs(u + 1, i + len);
            //         currArr.pop();
            //     }

            // } else {
            //     if (s[i] !== "0" && Number(s[i] + s[i + 1] + s[i + 2]) <= 255) {
            //         currArr.push(s[i] + s[i + 1] + s[i + 2]);
            //         dfs(u + 1, i + len);
            //         currArr.pop();
            //     }
            // }
        }
    }

    dfs(0, 0);

    return res;
};

94. 二叉树的中序遍历

题目链接https://leetcode.cn/problems/binary-tree-inorder-traversal/

思路:中序遍历:左结点 + 根 + 右结点

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    if(root === null) {
        return [];
    }
    let res = [];


    const dfs = function (root) {
        if (root.left) 
            dfs(root.left);

        res.push(root.val);

        if (root.right) 
            dfs(root.right);
    };

    dfs(root);

    return res;

};

95. 不同的二叉搜索树 II

题目链接https://leetcode.cn/problems/unique-binary-search-trees-ii/

思路:二叉搜索树的关键性质:根结点的所有左子树的结点都小于右子树的结点。每个子树都必须满足这个条件。所以,我们可以通过分治来解决。假设我们的根结点 是 i ,那么左子树的集合 [1~i-1], 右子树的集合 [i + 1, n]。对于子树递归枚举当前根结点选择方式。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function(n) {
    
    const dfs = function (start, end) {
        const allTree = [];
        if (start > end) {
            allTree.push(null);
            return allTree;
        }
		
        // 枚举这一段 [start, end] 以 i 为根的时候的子树的组合方式
        for(let i = start; i <= end; ++ i) {
			// 获得左子树所有组合
            const leftTree = dfs(start, i - 1);
            // 右子树所有组合
            const rightTree = dfs(i + 1, end);
			// 随便从两个子树分别取一个组成 树。并存储
            for (const leftRoot of leftTree) {
                for (const rightRoot of rightTree) {
                    const root = new TreeNode(i, leftRoot, rightRoot);
                    allTree.push(root);
                }
            }
        }

        return allTree;

    };

    return dfs(1, n);
};

96. 不同的二叉搜索树

题目链接https://leetcode.cn/problems/unique-binary-search-trees/

思路:如果 根结点 是 i ,那么不同的二叉平衡树等于 左子树 [1, i -1] 的所有不同的二叉平衡树 * 右子树 [i + 1, n]。同样左子树 也可以是这个过程,右子树同理。所以,不同的二叉平衡树,需要我们枚举不同的根结点,让后将结果累加起来。

  • 动态规划
    • 状态表示:f(i) 表示长度为 i 的集合能够组成的不同二叉平衡树的数量
    • 状态计算:f(i) += f(j - 1) * f(i - j); j <= i;
    • 边界条件:f(0) = 1, f(1) = 1;
  • 卡特兰数直接计算:百度百度
/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
    const f = new Array(n + 1).fill(0);
    f[0] = 1;
    f[1] = 1;

    // 枚举不同长度
    for(let i = 2; i <= n; ++ i) {
        // 枚举根结点
        for (let j = 1; j <= i; ++ j) {
            f[i] += f[j - 1] * f[i - j];
        }
    }

    return f[n];
};

97. 交错字符串

题目链接https://leetcode.cn/problems/interleaving-string/

思路:动态规划

  • 状态表示:f(i, j) 表示 s1 的前 i 个字符 和 s2的前j个字符,能否表示出 s3 的前i + j 个字符
  • 状态计算:f(i, j) = f(i - 1, j) && (s1[i] == s3[i + j]) or f(i, j - 1) && (s2[i] == s3[i + j]).
  • 边界条件: f(0,0) = true;
/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
var isInterleave = function(s1, s2, s3) {
    if (s1.length + s2.length !== s3.length)
        return false;
    
    const [n, m] = [s1.length, s2.length];
    const f = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(false));
    f[0][0] = true;

    for(let i = 0; i <= n; ++ i) {
        for (let j = 0; j <= m; ++ j) {
            let p = i + j - 1;
            if (i > 0 && s1[i - 1] === s3[p])
                f[i][j] = f[i][j] || f[i - 1][j];
            if (j > 0 && s2[j - 1] === s3[p])
                f[i][j] = f[i][j] || f[i][j - 1];
        }
    }

    return f[n][m];
};

// 滚动数组优化,因为下一次状态的表示只和上一次计算有关
/**
 * @param {string} s1
 * @param {string} s2
 * @param {string} s3
 * @return {boolean}
 */
var isInterleave = function(s1, s2, s3) {
    if (s1.length + s2.length !== s3.length)
        return false;
    
    const [n, m] = [s1.length, s2.length];
    const f = new Array(m + 1).fill(false);
    f[0] = true;
    for(let i = 0; i <= n; ++ i) {
        for (let j = 0; j <= m; ++ j) {
            let p = i + j - 1;
            if (i > 0)
                f[j] = f[j] && (s1[i - 1] === s3[p]);
            if (j > 0 )
                f[j] = f[j] || (f[j - 1] && s2[j - 1] === s3[p]);
        }
    }

    return f[m];
};

98. 验证二叉搜索树

题目链接https://leetcode.cn/problems/validate-binary-search-tree/

思路:二叉搜索树的性质是,左子树的所有结点的值小于根结点,右子树的所有值大于根结点。所有,递归判断每个子树是否满足条件即可。

  • 另一种解法:因为只要满足每个结点,left < root.val < right 即可。只要每个结点满足这个表达式即可,对于子结点,替换left 或 right即可
  • 中序遍历:如果该树是二叉搜索树,那么必然满足 中序遍历出来的序列是递增的。
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    
    let flag = true;
    const dfs = function(root) {

        let minmax = [];
        // 是叶子结点的时候
        if (root.left === null && root.right === null) {
            minmax.push(root.val, root.val);
            return minmax;
        }

        let leftMinMax = [root.val, -Number.MAX_VALUE];
        if (root.left) {
            leftMinMax = dfs(root.left);
        }
        let rightMinMax = [Number.MAX_VALUE, root.val];
        if (root.right) {
            rightMinMax = dfs(root.right);
        }

        if (leftMinMax[1] >= root.val) {
            flag = false;
        }

        if (rightMinMax[0] <= root.val) {
            flag = false;
        }
        

        let min = Math.min(leftMinMax[0], rightMinMax[0], root.val);
        let max = Math.max(leftMinMax[1], rightMinMax[1], root.val);
        
        minmax.push(min, max);
        return minmax;
    }   

    dfs(root);
    return flag;
};


// 解法二:满足表达式

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    
    const dfs = function(root, left, right) {
        if (root === null)
            return true;

        if (root.val > left && root.val < right) {
            return dfs(root.left, left, root.val) && dfs(root.right, root.val, right);
        } else {
            return false;
        }
    }   

    
    return dfs(root, -Number.MAX_VALUE, Number.MAX_VALUE);
};

// 解法三:中序遍历
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    
    const stack = [];
    let inorder = -Infinity;

    while(stack.length || root !== null) {
        // 先将所有左结点加入
        while(root) {
            stack.push(root);
            root = root.left;
        }
		// 拿出一个结点
        root = stack.pop();
        // 判断和上一个结点值相比是否满足递增条件
        if (root.val <= inorder) {
            return false;
        }
        inorder = root.val;
        root = root.right;
    }
    
    return true;;
};

99. 恢复二叉搜索树

题目链接https://leetcode.cn/problems/recover-binary-search-tree/

思路:因为二叉搜索树的性质,导致该树中序遍历必定是升序的。题目说有两个点是错误的,那么必然是中序遍历相邻的点中 满足 pre.val > root.val 的两个点。所以我们可以通过中序遍历找到这两个特殊点,然后交换它们的值。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function(root) {
    const stack = [];
    let x = null, y = null, pred = null;
    while(stack.length > 0|| root !== null) {
        while(root !== null) {
            stack.push(root);
            root = root.left;
        }

        root = stack.pop();
        if (pred !== null && root.val < pred.val) {
            y = root;
            if (x === null) {
                x = pred;
            } else {
                break;
            }
        }

        pred = root;
        root = root.right;
    }
    let temp = x.val;
    x.val = y.val;
    y.val = temp;

};

100. 相同的树

题目链接https://leetcode.cn/problems/same-tree/

思路:递归比较每个结点

// 写法一:有剪枝
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    let flag = true;

    const dfs = function (root1, root2) {
        if (!flag)
            return;
        
        if (root1 === null && root2 === null)
            return ;

        if ((root1 !== null && root2 === null) || (root1 === null && root2 !== null)) {
            flag = false;
            return;
        }
        if (root1.val !== root2.val) {
            flag = false;
            return;
        }
        
        dfs(root1.left, root2.left);
        dfs(root1.right, root2.right);
    };

    dfs(p, q);

    return flag;
};

// 方法二: 更优美
var isSameTree = function(p, q) {
    let flag = true;

    const dfs = function (root1, root2) {
        if (root1 === null)
            return root2 === null;
        
        return root2 !== null && root1.val === root2.val && dfs(root1.left, root2.left) && dfs(root1.right, root2.right);
    };

    

    return dfs(p, q);
};

101. 对称二叉树

题目链接https://leetcode.cn/problems/symmetric-tree/

思路:直接递归遍历判断,左子树的结点是否是右子树结点的镜像。也可以栈来实现

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {

    if (root === null)
        return true;

    const dfs = function (node1, node2) {
        if (node1 === null && node2 === null) {
            return true;
        }

        if (node1 === null || node2 === null) {
            return false;
        }

        return node1.val === node2.val && dfs(node1.left, node2.right) && dfs(node1.right, node2.left);
    }

    return dfs(root.left, root.right);
};

// 解法二:使用栈来实现

var isSymmetric = function(root) {

    if (root === null)
        return true;
    
    const stack = [];
    let root1 = root.left;
    let root2 = root.right;
    let flag = true;
    
    while(stack.length > 0 || (root1 !== null || root2 !== null)) {
        while(root1 !== null && root2 !== null) {
            stack.push(root1);
            stack.push(root2);
            root1 = root1.left;
            root2 = root2.right;
        }

        if ((root1 === null && root2 !== null) || (root1 !== null && root2 === null) ) {
            flag = false;
            break;
        }

        root2 = stack.pop();
        root1 = stack.pop();

        if (root1.val !== root2.val) {
            flag = false;
            break;
        }

        root2 = root2.left;
        root1 = root1.right;
    }

    return flag;
};





102. 二叉树的层序遍历

题目链接:https://leetcode.cn/problems/binary-tree-level-order-traversal/

思路:使用广度优先搜索,当一层搜索完成后,队列中剩余的结点就是下一层的所有结点。所以,我们可以通过变量维护当前层还剩多少个结点没有枚举。如果为 0 则加入当前层的结果。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if (root === null)
        return [];
    const queue = [];
    const res = [];

    queue.push(root);
    let cnt = 1;
    let curArr = [];

    while(queue.length !== 0) {
        const p = queue.shift();
        
        if (p.left !== null)
            queue.push(p.left);
        if (p.right !== null)
            queue.push(p.right);

        cnt --;
        curArr.push(p.val);
        // 如果cnt为零 表示当前层已经遍历完成了
        if (cnt === 0) {
            cnt = queue.length;
            res.push([...curArr]);
            curArr = [];
        }
    }

    return res;
};

103. 二叉树的锯齿形层序遍历

题目链接https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/

思路:令根结点为第 0 层。当是偶数的时候从左到右输出值,计数从右向左输出值。使用双端队列,来维护层的遍历方式。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
    if (root === null) {
        return [];
    }
    const res = [];
    const queue = [];
    let cnt = 1;
    let curArr = [];
    let flag = true;
    queue.push(root);
    while(queue.length !== 0) {
        let p;
        if (flag) {
            p = queue.shift();
        } else {
            p = queue.pop();
        }

        if (flag) {
            p.left && queue.push(p.left);
            p.right && queue.push(p.right);
        } else {
            p.right && queue.unshift(p.right);
            p.left && queue.unshift(p.left);
        }

        cnt --;
        curArr.push(p.val);

        if (cnt === 0) {
            cnt = queue.length;
            flag = !flag;
            res.push([...curArr]);
            curArr = [];
        }
    }

    return res;
};

104. 二叉树的最大深度

题目链接https://leetcode.cn/problems/maximum-depth-of-binary-tree/

思路:直接深度优先遍历,广度优先遍历,没有这个最优。因为它的空间复杂度,最多 O(height) height 为 二叉树的高度

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (root === null)
        return 0;

    let res = 0;

    const dfs = function (u, root) {
        res = Math.max(u, res);
        root.left && dfs(u + 1, root.left);
        root.right && dfs(u + 1, root.right);
    };

    dfs(1, root);

    return res;
};


// 更优雅的代码

var maxDepth = function(root) {
    
    const dfs = function (root) {
        if (root === null)
            return 0;
        return Math.max(dfs(root.left), dfs(root.right)) + 1;
    };

    
    return dfs(root);
};

105. 从前序与中序遍历序列构造二叉树

题目链接https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

思路:二叉树的先序遍历中,我们很容易得到数的根结点。二叉树的中序遍历中,我们很容易得到,二叉树的左右子树的长度和值。所以我们通过先序遍历找到根结点,通过中序遍历确定左右子树。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    const n = preorder.length;
    const myBuildTree = function(l1, r1, l2, r2) {

        if (l2 > r2)
            return null;

        const root = new TreeNode();
        root.val = preorder[l1];

        let rootIdx = l1;
        for (let i = l2; i <= r2; ++ i)
            if (inorder[i] === root.val) {
                rootIdx = i;
                break;
            }
        // 获取 左子树的先序遍历开始下标
        let leftTreeStartIndex = l1 + 1; 
        // 获取 右子树先序遍历的开始下标
        let rightTreeStartIndex = l1 + 1 + rootIdx - l2;

        // 递归处理左右子树
        root.left = myBuildTree(leftTreeStartIndex, l1 + rootIdx - l2, l2, rootIdx - 1);
        root.right = myBuildTree(rightTreeStartIndex, r1, rootIdx + 1, r2);

        return root;
    }
    
    return myBuildTree(0, n - 1, 0, n - 1);
};

106. 从中序与后序遍历序列构造二叉树

题目链接https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

思路:二叉树的中序遍历可以得到左右子树结点集合,二叉树的后序遍历能够得到 根,根是后续遍历最后一个元素。

var buildTree = function(inorder, postorder) {
    const n = inorder.length;
    const myBuildTree = function (l1, r1, l2, r2) {
        if (l1 > r1)
            return null;
        
        const root = new TreeNode(postorder[r2]);

        let rootIndex = l1;
        while(rootIndex <= r1 && inorder[rootIndex] !== root.val) 
            rootIndex ++;


        root.left = myBuildTree(l1, rootIndex - 1, l2, l2 + rootIndex - l1 - 1);
        root.right = myBuildTree(rootIndex + 1, r1, l2 + rootIndex - l1, r2 - 1);
        
        return root;
    }

    return myBuildTree(0, n - 1, 0, n - 1);
};

107. 二叉树的层序遍历 II

题目链接https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/

思路

  • 先求出正向的层序遍历,然后将结果反转
  • 或使用广度优先遍历,将结果从头部插入答案。
// 只有解法一
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */

var levelOrderBottom = function(root) {
    const res = [];

    const dfs = function (u, root) {
        if (root === null)
            return;

        dfs(u + 1, root.left);
        dfs(u + 1, root.right);
        res[u] ??= [];
        res[u].push(root.val);
    };

    dfs(0, root);
    return res.reverse();
};

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

题目链接https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/

思路:因为题目中给的数组是从小到大排序的,所以我们取中间的点为根,那么左边的集合部分必然是小于根结点,右边集合部分必然是大于根结点。对于子树也这样做,必然能保证高度差最多为1.

var sortedArrayToBST = function(nums) {
    const n = nums.length;

    const buildTree = function (l, r) {
        if (l > r)
            return null;
        
        let rootIndex = Math.trunc((l + r + 1) / 2);

        const root = new TreeNode(nums[rootIndex]);

        root.left = buildTree(l, rootIndex - 1);
        root.right = buildTree(rootIndex + 1, r);

        return root;
    };

    return buildTree(0, n - 1);
};

109. 有序链表转换二叉搜索树

题目链接: https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/

思路

  • 可以直接将链表的值取出来,然后做法就和108题一样了
  • 因为链表是排序的,恰好属于二叉树搜索树的中序遍历。所以,我们可以模拟二叉搜索树的中序遍历,然后给对应的点填值。
// 解法二:模拟中序遍历
var sortedListToBST = function(head) {

    const getLength = function(head) {
        let len = 0;
        while(head !== null) {
            len ++;
            head = head.next;
        }

        return len;
    };

    const buildTree = function (l, r) {
        if (l > r)
            return null;
        let mid = Math.trunc((l + r + 1) / 2);
        const root = new TreeNode();
        
        root.left = buildTree(l, mid - 1);
        

        root.val = head.val;
        head = head.next;
        
        root.right = buildTree(mid + 1, r);

        return root;  
    };

    const len = getLength(head);
    return buildTree(0, len - 1);
};

110. 平衡二叉树

题目链接https://leetcode.cn/problems/balanced-binary-tree/

思路:从叶节点开始向上计算子树的深度。如果某一个结点的左右子树的深度差大于 1, 那么就不满足条件了。

var isBalanced = function(root) {

    let flag = true;
    const checkAVL = (root) => {
        if (!flag) 
            return 0;
        
        if (root === null)
            return 0;
        
        const leftDeep = checkAVL(root.left);
        const rightDeep = checkAVL(root.right);

        if (Math.abs(leftDeep - rightDeep) > 1) {
            flag = false;
            return 0;
        }

        return Math.max(leftDeep, rightDeep) + 1;
    };

    checkAVL(root);
    return flag;
};

111. 二叉树的最小深度

题目链接https://leetcode.cn/problems/minimum-depth-of-binary-tree/

思路

  • 使用递归求每个叶节点的深度,然后比较
  • 使用广度优先遍历,得到第一个叶子结点的深度(推荐)
// 解法一:深度优先遍历
var minDepth = function(root) {
    if (root === null)
        return 0;
    let res = Infinity;
    const getMinDeep = (u, root) => {
        if (root.left === null && root.right === null) {
            res = Math.min(res, u);
            return;
        }

        root.left && getMinDeep(u + 1, root.left);
        root.right && getMinDeep(u + 1, root.right);
    }

    getMinDeep(1, root);
    return res;
};


// 解法二:广度优先遍历(推荐)
var minDepth = function(root) {
    if (root === null)
        return 0;
    let queue = [root];
    let cen = 1;
    let cnt = 1;

    while(queue.length > 0) {
        const p = queue.shift();
        if (p.left === null && p.right === null) 
            break;
        
        p.left && queue.push(p.left);
        p.right && queue.push(p.right);

        cnt --;
        if (cnt === 0) {
            cen ++;
            cnt = queue.length;
        }
    }

    return cen;
};

112. 路径总和

题目链接https://leetcode.cn/problems/path-sum/

思路:枚举每条到叶子结点的路径,并计算路径之和,判断是否和targetsum相等。

// 写法一:
var hasPathSum = function(root, targetSum) {
    if (root ===  null) {
        return false;
    }

    let flag = false;
    const checkTagetSum = (sum, root) => {
        // console.log(sum, root);
        if (flag) {
            return;
        }
        if (root.left === null && root.right === null) {
            if (sum + root.val === targetSum)
                flag = true;
            return ;
        }
        
        (root.left && checkTagetSum(sum + root.val, root.left));
        (root.right && checkTagetSum(sum + root.val, root.right));
    };
    checkTagetSum(0, root);
    return flag;
};

// 写法二:
var hasPathSum = function(root, targetSum) {
    
    const checkTagetSum = (sum, root) => {
        if (root === null)
            return false;
        
        if (root.left === null && root.right === null) {
            return sum + root.val === targetSum;
        }
        
        return checkTagetSum(sum + root.val, root.left) ||
        checkTagetSum(sum + root.val, root.right);
    };
    
    return checkTagetSum(0, root);
};

113. 路径总和 II

题目链接https://leetcode.cn/problems/path-sum-ii/

思路:搜索加回溯,思路和 113 一样

var pathSum = function(root, targetSum) {
    const res = [];
    const curArr = [];
    const checkTargetPath = (sum, root) => {
        if (root === null)
            return;
        if (root.left === null && root.right === null) {
            if (root.val + sum === targetSum) {
                curArr.push(root.val);
                res.push([...curArr]);
                // 注意回溯
                curArr.pop();
            }

            return;
        }

        curArr.push(root.val);
        checkTargetPath(sum + root.val, root.left);
        
        checkTargetPath(sum + root.val, root.right);
        curArr.pop();
    };

    checkTargetPath(0, root);

    return res;
};

114. 二叉树展开为链表

题目链接: https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/

思路:我们必须先把整个树遍历完成后,将其结点插入到链表中,不然会影响递归的结果。所以,我们必须将操作放在最后,因为因为最后要求链表为先序遍历的顺序,因此,我们先遍历右节点在遍历左结点,然后使用链表的头插法来实现。

var flatten = function(root) {
    const newHead = new TreeNode();
    const preOrder = (root) => {
        if (root === null)
            return;
        
        
        preOrder(root.right);
        preOrder(root.left);

        root.right = newHead.right;
        newHead.right = root;
        root.left = null;
        
    };
    preOrder(root);
    return newHead.right;
};

115. 不同的子序列

题目链接https://leetcode.cn/problems/distinct-subsequences/

思路:动态规划

  • 状态表示:f(i, j) 表示 s(0~i) 中包含 t(0~j) 子序列的个数
  • 状态计算:f(i, j) = f(i - 1, j) + f(i - 1, j - 1) (s[i] === t[j])
  • 边界条件:f(i, 0) = 1 0 <= i <= n;
var numDistinct = function(s, t) {

    const n = s.length;
    const m = t.length;

    const f = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));

    for (let i = 0; i <= n; ++ i)
        f[i][0] = 1;
    
    for (let i = 1; i <= n; ++ i) {
        for (let j = 1; j <= m; ++ j) {
            f[i][j] = f[i - 1][j];

            if (s[i - 1] === t[j - 1]) {
                f[i][j] += f[i - 1][j - 1];
            }
                
        }
    }


    return f[n][m];
};

116. 填充每个节点的下一个右侧节点指针

题目链接https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/

思路:观察一下,链表链接的是每一层,所以可以通过层序遍历来连接每一层的结点。

/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * };
 */

/**
 * @param {Node} root
 * @return {Node}
 */
var connect = function(root) {
    if (root === null) {
        return null;
    }

    const queue = [root];
    let cnt = 1;
    let cenHead = null;
    while(queue.length > 0) {
        const p = queue.shift();

        p.left && queue.push(p.left);
        p.right && queue.push(p.right);

        if (cenHead === null) {
            cenHead = p;
        } else {
            cenHead.next = p;
            cenHead = cenHead.next;
        }

        
		
        cnt --;
        // 当前层遍历完成
        if (cnt === 0) {
            cnt = queue.length;
            cenHead = null;
        }
    }

    return root;
};

117. 填充每个节点的下一个右侧节点指针 II

题目连接https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/

思路:和上题思路一样,层序遍历。代码也是一样的。

118. 杨辉三角

题目链接https://leetcode.cn/problems/pascals-triangle/

思路:最基础的递推或说是dp, 模拟即可

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function(numRows) {
    const res = [[1]];
    const f = new Array(numRows + 1).fill(0).map(() => new Array(numRows + 1).fill(0));
    f[1][1] = 1;

    for (let i = 2; i <= numRows; ++ i) {
        for (let j = 1; j <= i; ++ j)
            f[i][j] = f[i - 1][j - 1] + f[i - 1][j];
        
        res.push(f[i].slice(1, i + 1));
    }

    return res;
};

119. 杨辉三角 II

题目链接https://leetcode.cn/problems/pascals-triangle-ii/

思路:dp + 滚动数组优化,因为下一行的状态只与上一行的状态有关。所以可以将空间优化成一维。为了避免当前层的计算的结果影响其他答案的计算。应该从后向前计算。

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
    const f = new Array(rowIndex + 2).fill(0);
    f[1] = 1;

    for (let i = 2; i <= rowIndex + 1; ++ i) {
        for (let j = i; j >= 1; -- j)
            f[j] = f[j - 1] + f[j];
    }

    return f.slice(1);
};

120. 三角形最小路径和

题目链接:(https://leetcode.cn/problems/triangle/

思路:动态规划,转换角度,找到从底部到根结点总和最少的路径。所以 f(i, j) += Math.min(f(i + 1, j), f(i + 1, j + 1));

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    const n = triangle.length;

    for (let i = n - 2; i >= 0; -- i) {
        for (let j = 0; j <= i; ++ j) {
            triangle[i][j] += Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]);
        }
    }

    return triangle[0][0];
};

121. 买卖股票的最佳时机

题目链接https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

思路:双指针 + 贪心

  • l 指向的是用户购买的股票,r 向后遍历股市价格,并同时结算最大收益。如果出现,某天的价格低于 当前购买的价格,就有可能会影响到最大值的结果。所以,我们将 l 指向 r 这天的股票价格,继续计算。
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    const n = prices.length;
    let res = 0;
    let l = 0, r = 0;

    while(r < n) {
        res = Math.max(res, prices[r] - prices[l]);

        if (prices[r] - prices[l] < 0)
            l = r;
        r ++;
    }

    return res;
};

122. 买卖股票的最佳时机 II

题目链接https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/

思路:买股票要想赚钱,必然是抄底。所以我们找到每一段连续上升的区间的第一个值买进,到最高点卖出就得到答案了。不想当韭菜,低买高卖

  • image20220518235532111.png
/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    const n = prices.length;
    let res = 0;
    let l = 0, r = 0;
    
    while(r < n - 1) {
        if (prices[r] > prices[r + 1]) {
            res += prices[r] - prices[l];
            r ++;
            l = r;
        } else {
            r ++;
        }
    }

    // 最后一段连续递增
    res += prices[r] - prices[l];
    return res;
};