Appearance
第二部分
常见经典算法题。
三十三、爬楼梯 简单
题目
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1 阶 + 1 阶
2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
2 阶 + 1 阶
题解
一、动态规划(一)
存储爬到每一格的方法。
js
var climbStairs = function (n) {
const dp = new Array(n);
dp[0] = 1;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
};二、动态规划(二)
走一步算两步
js
var climbStairs = function (n) {
let result = 1, prior = 0, pre = 0;
for (let i = 1; i <= n; i++) {
result = pre + prior;
prior = pre;
pre = result;
}
return result;
};三十四、杨辉三角 简单
题目
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1
输出: [[1]]
题解
数学
js
var generate = function (numRows) {
const ans = [];
for (let row = 0; row < numRows; row++) {
let arr = [], count = row + 1;
for (let i = 0; i < count; i++) {
if (i === 0 || i === count - 1) {
arr.push(1);
} else {
arr.push(ans[row - 1][i] + ans[row - 1][i - 1])
}
}
ans.push(arr)
}
return ans;
};三十五、打家劫舍 中等
题目
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
题解
动态规划
js
var rob = function (nums) {
if (nums.length === 1) {
return nums[0];
}
const dp = new Array(nums.length).fill(0);
dp[0] = nums[0];
dp[1] = Math.max(nums[1], nums[0]);
dp[2] = Math.max(nums[1], nums[2] + nums[0]);
for (let i = 2; i < nums.length; i++) {
dp[i] = Math.max(nums[i] + dp[i - 2], dp[i - 1]);
}
return dp[nums.length - 1];
};三十六、完全平方数 中等
题目
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
题解
动态规划
dp[i] 表示数字 i 最少可以由多少个完全平方数相加组成
首先将 min 初始化为 JavaScript 能表示的最大数值（Number.MAX_VALUE），它用于记录当前数字 i 减去某个完全平方数后，剩下数字所对应的最少完全平方数个数中的最小值。
在内层循环结束后，找到了对于当前数字 i 减去某个完全平方数后剩余部分所对应的最少完全平方数个数的最小值 min，由于我们还需要加上刚刚减掉的那个完全平方数（也就是 1 个），所以 dp[i] 的值就是 min + 1
js
var numSquares = function (n) {
const dp = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
let min = Number.MAX_VALUE;
for (let j = 1; j * j <= i; j++) {
min = Math.min(min, dp[i - j * j])
}
dp[i] = min + 1;
}
return dp[n];
};三十七、字符串解码 中等
题目
给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"
示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"
示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
示例 4：
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"
题解
栈操作
js
function decodeString(s) {
let stack = [];
for (let i = 0; i < s.length; i++) {
let char = s[i];
// 如果当前字符不是右括号，都入栈（数字、字母、左括号都入栈）
if (char !== ']') {
stack.push(char);
} else {
// 当遇到右括号时，开始处理括号内的内容以及重复次数
let str = '';
while (stack[stack.length - 1] !== '[') {
// 从栈顶依次取出字符，拼接成当前括号内的字符串
str = stack.pop() + str;
}
stack.pop(); // 把 '[' 弹出栈
let num = '';
while (stack.length > 0 && /\d/.test(stack[stack.length - 1])) {
// 从栈顶依次取出数字字符，拼接成重复次数的数字字符串
num = stack.pop() + num;
}
let repeatNum = parseInt(num);
// 将当前括号内的字符串重复相应次数后，再重新入栈
stack.push(str.repeat(repeatNum));
}
}
return stack.join('');
}三十八、颜色分类 中等
题目
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
题解
一、单指针
我们可以考虑对数组进行两次遍历。在第一次遍历中，我们将数组中所有的 0 交换到数组的头部。在第二次遍历中，我们将数组中所有的 1 交换到头部的 0 之后。此时，所有的 2 都出现在数组的尾部，这样我们就完成了排序。
js
var sortColors = function (nums) {
function swap(i, j) {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
let slow = 0;
for (let fast = 0; fast < nums.length; fast++) {
if (nums[fast] === 0) {
swap(slow, fast);
slow++;
}
}
for (let fast = slow; fast < nums.length; fast++) {
if (nums[fast] === 1) {
swap(slow, fast);
slow++;
}
}
};二、双指针
js
var sortColors = function (nums) {
function swap(i, j) {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
let p0 = 0, p2 = nums.length - 1;
for (let index = 0; index < nums.length; index++) {
while (nums[index] === 2 && index < p2) {
swap(index, p2);
p2--;
}
if (nums[index] === 0) {
swap(p0, index);
p0++;
}
}
};三十九、零钱兑换 中等
题目
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
题解
动态规划
定义dp[i]为组成面值i所需最少的硬币数量。
js
var coinChange = function(coins, amount) {
const dp = new Array(amount + 1).fill(amount + 1);
dp[0] = 0;
for(let i = 0; i <= amount; i++) {
for(let j = 0; j < coins.length; j++) {
if(i >= coins[j]) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
};四十、单词拆分 中等
题目
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意，你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
题解
动态规划
js
var wordBreak = function(s, wordDict) {
const n = s.length;
const dp = new Array(n + 1).fill(false);
const wordSet = new Set(wordDict);
dp[0] = true;
for(let i = 1; i <= n; i++) {
for(let j = 0; j < i; j++) {
if(dp[j] && wordSet.has(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
};四十一、最长递增子序列 中等
题目
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列 。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
题解
一、动态规划
定义一个数组（设为 dp），dp[i] 表示以数组中第 i 个元素为结尾的最长严格递增子序列的长度
js
var lengthOfLIS = function(nums) {
const dp = new Array(nums.length).fill(1);
let max = 1;
for(let i = 1; i < nums.length; i++) {
for(let j = 0; j < i; j++) {
if(nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
max = Math.max(max, dp[i]);
}
}
}
return max;
};四十二、乘积最大子数组 中等
题目
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组 （该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
题解
一、动态规划
js
var maxProduct = function (nums) {
let ans = nums[0];
let maxProduct = nums[0]; // 最大正乘积
let minProduct = nums[0]; // 最小负乘积
for (let i = 1; i < nums.length; i++) {
let maxProductHere = maxProduct;
let minProductHere = minProduct;
if(nums[i] > 0) {
maxProduct = Math.max(nums[i], maxProductHere * nums[i]);
minProduct = Math.min(nums[i], minProductHere * nums[i]);
} else if(nums[i] < 0) {
minProduct = Math.min(nums[i], maxProductHere * nums[i]);
maxProduct = Math.max(nums[i], minProductHere * nums[i]);
} else {
maxProduct = 0;
minProduct = 0;
}
ans = Math.max(maxProduct, ans);
}
return ans;
};二、双遍历分区间乘积法
js
var maxProduct = function (nums) {
let product = 1;
let ans = nums[0];
for(let i = 0; i < nums.length; i++) {
product *= nums[i];
ans = Math.max(ans, product);
if(nums[i] === 0 || i === nums.length - 1) {
product = 1;
}
}
for(let i = nums.length - 1; i >= 0; i--) {
product *= nums[i];
ans = Math.max(ans, product);
if(nums[i] === 0) {
product = 1;
}
}
return ans;
};四十三、最长公共子序列 中等
题目
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。
示例 2：
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。
示例 3：
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。
题解
动态规划
可以使用一个二维数组 dp[i][j] 来表示状态，其中 i 表示 text1 字符串中前 i 个字符（索引从 0 到 i - 1 ），j 表示 text2 字符串中前 j 个字符（索引从 0 到 j - 1 ）。dp[i][j] 的值代表 text1 的前 i 个字符和 text2 的前 j 个字符构成的最长公共子序列的长度。
js
var longestCommonSubsequence = function(text1, text2) {
const m = text1.length, n = text2.length;
const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
const c1 = text1[i - 1];
for (let j = 1; j <= n; j++) {
const c2 = text2[j - 1];
if (c1 === c2) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
};四十四、最长等差数列 中等
题目
给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。
回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。
示例 1：
输入：nums = [3,6,9,12]
输出：4
解释：
整个数组是公差为 3 的等差数列。
示例 2：
输入：nums = [9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。
示例 3：
输入：nums = [20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]。
题解
一、动态规划(一)
状态定义：dp[i][d]表示以nums[i]结尾且公差为d的数列长度。
状态转移：对于nums[i]，可以枚举它的前一项nums[j]，0<= j < i，有了前一项nums[j]，其实公差就确定了d=nums[i]-nums[j]。
如果nums[j]可以是某个公差为d的数列的最后一项，nums[i]就可以接在后面形成更长的等差数列，状态转移方程为dp[i][d]=dp[j][d]+1
否则它两就形成公差为d的等差数列前两项，状态转移方程为dp[i][d]=2。
对于任意的d，当i = 0时有dp[i][d] = 1，表示第一项可以属于任意公差的等差数列。
js
var longestArithSeqLength = function (nums) {
const dp = new Array(nums.length + 1).fill(0).map(() => []);
let ans = 1;
for(let i = 1; i < nums.length; i++) {
for(let j = 0; j < i; j++) {
const d = nums[i] - nums[j];
if(j === 0) {
dp[j][d] = 1;
}
if(dp[j][d]) {
dp[i][d] = dp[j][d] + 1;
} else {
dp[i][d] = 2;
}
ans = Math.max(ans, dp[i][d]);
}
}
return ans;
};二、动态规划(二)
超时了
js
var longestArithSeqLength = function (nums) {
let max = 1;
const map = new Map();
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
const diff = nums[i] - nums[j];
const preKey = [j, diff].toString();
const preLength = map.get(preKey) || 1;
const curKey = [i, diff].toString();
map.set(curKey, preLength + 1);
max = Math.max(max, preLength + 1);
}
}
return max;
};