Lucas Liao's Blog

leetcode刷题记录

动态规划

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

链接：https://leetcode-cn.com/problems/climbing-stairs/
思路：https://leetcode-cn.com/problems/climbing-stairs/solution/hua-jie-suan-fa-70-pa-lou-ti-by-guanpengchn/

1
2
3
4
5
6
7
8
9
10
11
var climbStairs = function(n) {
    const dp = [];
    dp[0] = 1;
    dp[1] = 1;

    for (let i = 2; i <= n; i ++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n]
};

买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var maxProfit = function(prices) {
    let l = prices.length;
    let min = prices[0];
    let profit = 0;
    for(let i = 1; i < l; i ++) {
        if (prices[i] < min) {
            min = prices[i]
        }
        if ((prices[i] - min) > profit ) {
            profit = prices[i] - min;
        }
    }
    return profit
};

不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var uniquePaths = function(m, n) {
  let dp = Array.from(new Array(m+1),() => new Array(n+1).fill(0))
   for (let i = 0; i < m; i++) {
     dp[i][0] = 1
   }
   for (let j = 0; j < n; j++) {
     dp[0][j] = 1
   }
    for(let i = 1;i<m;i++){
      for(let j= 1;j<n;j++){
        dp[i][j] = dp[i-1][j]+dp[i][j-1]
      }
    }
    return dp[m-1][n-1]
};

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

剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m] 。请问 k[0]k[1]…*k[m] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof

1
2
3
4
5
6
7
8
9
10
var cuttingRope(n) = function {
    let dp = new Array(n + 1).fill(1)
    for (let i = 3; i <= n; i++) {
        for (let j = 1; j < n; j++) {
            dp[i] = Math.max(dp[i], j * (i -j), j * dp[i - j])
        }
    }
    return dp[n]
}

Array

combination-sum

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合.candidates 中的数字可以无限制重复被选取。

链接：https://leetcode-cn.com/problems/combination-sum
思路: https://leetcode-cn.com/problems/combination-sum/solution/39-zu-he-zong-he-by-alexer-660/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    let n = candidates.length;
    let temp = [];
    let res = [];

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

    const backtrack = (temp, target, start) => {
        if (target === 0) {
            res.push(temp);
            return;
        };
        for (let i = start; i < n; i++) {
            if (target < candidates[i]) break;
            temp.push(candidates[i]);
            backtrack(temp.slice(), target - candidates[i], i);
            temp.pop();
        };
    }
    backtrack(temp, target, 0);
    return res;
};

其他解法：https://leetcode-cn.com/problems/combination-sum/solution/javascript-jie-fa-cong-da-dao-xiao-shi-zhi-84ms-98/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 * 64ms 100.00%
 * 36.3mb 83.33%
 * 极致简化版
 */
var combinationSum = function (candidates, target) {
  // 由大到小排序
  candidates.sort((a, b) => b - a);

  let res = [], path = [];
  let len = candidates.length, minNum = candidates[len - 1]; // 缓存长度

  get_combin(candidates, target, 0, path);

  function get_combin(candidates, target, start, path) {
    if (target == 0) {
      return res.push(path.slice());
    }

    // 这里不用小于 0，小于最小的数就可以返回了
    if (target < minNum) return;

    for (let i = start; i < len; i++) {
      path.push(candidates[i]);
      get_combin(candidates, target - candidates[i], i, path);
      path.pop();
    }
  }

  return res;
};

有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    let stack = [];
    let array = s.split('');

    for(let e of array) {
        if (isLeft(e)) {
            stack.push(e)
        }else {
            let last = stack[stack.length - 1];
            if (isMatch(last+e)) {
                stack.pop();
            }else {
                return false;
            }
        }
    }

    return stack.length === 0 ? true : false;

};

function isLeft (s) {
    return ['(', '{', '['].includes(s);
}

function isMatch (s) {
    return ['()', '{}', '[]'].includes(s);
}

整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    let res = 0;

    x = parseInt(x)


    while(x) {
       res = res * 10 + x % 10;
       x = parseInt(x/10)
    }


    if (res > 2147483647 || res < -2147483648) return 0;

    return res;
};

两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

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

1
2
3
4
5
6
7
8
9
10
11
12
var twoSum = function(nums, target) {
    let map = {};

    for (let i = 0; i < nums.length; i++) {

         if (map[target - nums[i]] >= 0) {
            return [map[target - nums[i]], i];
        }

        map[nums[i]] = i;
    }
};

回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    if (x < 0) return false;

    let a = x;
    let r;

    for (r = 0; a !== 0; a = a/10 >>0) {
        r = r * 10 + a % 10;
    }

    return r === x
};

分糖果

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？

链接：https://leetcode-cn.com/problems/candy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function(ratings) {
    let length = ratings.length;
    let left = new Array(length).fill(1);
    let right = new Array(length).fill(1);

    for (let i = 1; i < length; i ++) {
        if (ratings[i] > ratings[i - 1]) {
            left[i] = left[i - 1] + 1;
        }
    }

    let count = left[length - 1];

    for (let k = length - 2; k >= 0;  k--) {
        if (ratings[k] > ratings[k + 1]) {
            right[k] = right[k + 1] + 1
        }
        count += Math.max(left[k], right[k])
    }
    return count;
};

两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

链接：https://leetcode-cn.com/problems/intersection-of-two-arrays/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    let mark1 = new Set(nums1);
    let mark2 = new Set();

    for (let i = 0, l = nums2.length; i < l; i ++) {
        if (mark1.has(nums2[i])) mark2.add(nums2[i])
    }

    return [...mark2]

};

给定一个字符串，请你找出其中不含有重复字符的 最长子串的长度。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let length = s.length;
    let res = 0;
    
    let map = new Map();
    
    for (let i = 0, j = 0; i < length; i++) {
        if (map.has(s[i])) {
            j = Math.max(map.get(s[i]), j)
        }
        res = Math.max(res, i - j + 1);
        map.set(s[i], i+1);
    }

    return res
};

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :

数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

链接：https://leetcode-cn.com/problems/subarray-sum-equals-k

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    const map = new Map();
    map.set(0, 1);
    let pre = 0;
    let count = 0;

    for (const x of nums) {
        pre += x;
        if (map.has(pre - k)) count += map.get(pre - k);
        if (map.has(pre)) {
            map.set(pre, map.get(pre) + 1)
        }else {
            map.set(pre, 1);
        }
    }
    return count;

}