力扣 300-599
300.最长递增子序列（双重 00，dp）
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的 子序列 。
var lengthOfLIS = function (nums) {
let max = 1;
// 初始化全为1
let dp = new Array(nums.length).fill(1);
for (let i = 0; i < nums.length; i++) {
//往前找，更新；利用已经自增的子序列，加上个1
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
// 因为严格递增 12222最长只是2，第二次遍历到2时不能再增了
dp[i] = dp[j] + 1;
max = Math.max(dp[i], max);
}
}
}
console.log(dp);
return max;
};
301.删除无效的括号（dfs+预处理）
输入：s = "()())()"
输出：["(())()","()()()"]
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
/**
* @param {string} s
* @return {string[]}
*/
var removeInvalidParentheses = function (s) {
const n = s.length;
// 记录最大有效括号数量
let count = 0;
let i = 0;
// 存在重复字符形式
const set = new Set();
// ")()" count:1; 最多的有效括号对为1；则此时l和r都为1
for (let c of s) {
if (c == "(") {
i++;
} else if (c == ")" && i > 0) {
i--;
//
count++;
}
}
const dfs = (i, l, r, str) => {
// 数量关系，剪枝
if (l < r || l > count || r > count) return;
// 遍历结束
if (i == n) {
// n走完，且l和r都等于最多的有效括号对数，则说明删了最少个
if (l == count && r == count) {
set.add(str);
}
return;
}
const cur = s[i];
if (cur == "(") {
// 括号，选或不选
dfs(i + 1, l + 1, r, str + "(");
dfs(i + 1, l, r, str);
} else if (cur == ")") {
dfs(i + 1, l, r + 1, str + ")");
dfs(i + 1, l, r, str);
} else {
// 字符（如a)直接加入
dfs(i + 1, l, r, str + cur);
}
};
dfs(0, 0, 0, "");
return [...set];
};
322.零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
/**
* @param {number[]} coins
* @param {number} amount
* @return {number}
*/
var coinChange = function (coins, amount) {
// amount为总金额，1000块钱最多是1000个1块钱，所以设置amount + 1，即不可能发生的情况，这样在最后return时如果还是amount + 1,则返回-1
// [1: 4,2:4,3:4]，剩三块钱的时候需要最多能用三个币，最坏情况也是3：3，不可能是3：4（除非硬币里没有1
//
let dp = new Array(amount + 1).fill(amount + 1); //arr[i]用来存储金额为i时需要的最少硬币个数
dp[0] = 0; //金额为0时需要0个硬币
for (let i = 1; i <= amount; i++) {
//已经确定金额为0时的最少硬币数，要得到arr[amount]就要得到arr[0]~arr[amount -1]的硬币数
for (let j = 0; j < coins.length; j++) {
//遍历可能的硬币情况
if (coins[j] <= i) {
// 则可用上这枚硬币，试试看此时硬币数会不会是最少的
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1); //求arr[i]最少硬币数
}
}
}
return dp[amount] > amount ? -1 : dp[amount]; //如果没有组成的可能，结果是初始值amount + 1，只要有可能，最坏情况是都为1元硬币，个数至多为amount个
// 而如果硬币面值大于总面值的情况, arr[amount]
};
344.反转字符串
使用 O(1) 的额外空间解决这一问题。
/**
* @param {character[]} s
* @return {void} Do not return anything, modify s in-place instead.
*/
var reverseString = function (s) {
const n = s.length;
for (let left = 0, right = n - 1; left < right; ++left, --right) {
[s[left], s[right]] = [s[right], s[left]];
}
};
349.两个数组的交集
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersection = function (nums1, nums2) {
let a = new Set(nums1);
let b = new Set(nums2);
let intersect = [...a].filter((ina) => b.has(ina));
return intersect;
};
509.斐波那契数
var fib = function (n) {
if (n < 2) {
return n;
}
let p = 0,
q = 0,
r = 1;
for (let i = 2; i <= n; i++) {
p = q;
q = r;
r = p + q;
}
return r;
};
384.打乱数组
给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。
实现 Solution class:
Solution(int[] nums) 使用整数数组 nums 初始化对象
int[] reset() 重设数组到它的初始状态并返回
int[] shuffle() 返回数组随机打乱后的结果
var Solution = function (nums) {
this.originNums = nums;
this.shuffleNums = nums;
this.len = nums.length;
};
Solution.prototype.reset = function () {
return this.originNums;
};
Solution.prototype.shuffle = function () {
const nums = [...this.originNums];
let n = nums.length;
// 产生的结果有 n! 种可能
for (let i = 0; i < n; i++) {
// 从 i 到 n-1 随机选一个
const rand = randOne(i, n - 1);
// 交换nums数组i和rand下标的两个元素
[nums[i], nums[rand]] = [nums[rand], nums[i]];
}
return nums;
};
// 获取闭区间 [n, m] 内的一个随机整数
function randOne(n, m) {
return Math.floor(Math.random() * (m - n + 1)) + n;
}
387.字符串的第一个唯一字符
给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。
/**
* @param {string} s
* @return {number}
*/
var firstUniqChar = function (s) {
// 创建一个哈希表对象
let map = new Map();
// 统计次数
for (let i = 0; i < s.length; i++) {
let word = s.charAt(i);
let val = map.get(word);
if (map.has(word)) {
map.set(word, val + 1);
} else {
map.set(word, 1);
}
}
// 找到第一个只出现一次的字母
for (let i = 0; i < s.length; i++) {
if (map.get(s.charAt(i)) === 1) {
return i;
}
}
return -1;
};
392.判断子序列(原地双指针)
输入：s = "abc", t = "ahbgdc" 输出：true
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isSubsequence = function (s, t) {
var sLen = s.length;
var tLen = t.length;
if (sLen > tLen) {
return false;
}
if (sLen === 0) {
return true;
}
var step = 0;
for (var i = 0; i < sLen; i++) {
while (step < tLen) {
if (t[step] === s[i]) {
step++;
if (i === sLen - 1) {
return true;
}
break;
}
step++;
}
}
return false;
};
394.字符串解码（双栈，str.repeat）
输入：s = "3[a]2[bc]"
输出："aaabcbc"
/**
* @param {string} s
* @return {string}
*/
// 创建倍数数组
// 待拼接str所在的栈
// 创建num,和res
// 循环遍历字符串，如果是数字，num乘10进当前位（要parseInt
// 否则如果是[ ，往str栈入当前res,当前res更新位空，将当前重复次数num栈入num栈，更新num为0
// 否则如果]，num栈出重复次数，res=str栈出之前的总字符串，加上当前res重复num次
// 否则res+当前位字母
// 返回res
var decodeString = function (s) {
let numStack = []; // 倍数 num 的等待栈
let strStack = []; // 待拼接 str 的等待栈
let num = 0,
result = "";
for (let item of s) {
if (!isNaN(item)) {
// 判断是数字时，'30'是30
num = num * 10 + parseInt(item);
} else if (item === "[") {
// 此时result可以确定一个保底了
strStack.push(result);
result = "";
numStack.push(num);
num = 0;
} else if (item === "]") {
const repeatTimes = numStack.pop(); // 从栈中获取次数
// 保底result可以继续变长，只把状态可以确定的部分和上去，这个result会越来越长
result = strStack.pop() + result.repeat(repeatTimes); // 把之前已经拼接好的str再次弹出和当前res结合
} else {
result += item;
}
}
return result;
};
402. 移掉 K 位数字
12364
遍历到4 发现栈顶6大 换成1234
var removeKdigits = function(num, k) {
const stk = [];
for (const digit of num) {
while (stk.length > 0 && stk[stk.length - 1] > digit && k) {
stk.pop();
k -= 1;
}
stk.push(digit);
}
for (; k > 0; --k) {
stk.pop();
}
let ans = "";
let isLeadingZero = true;
for (const digit of stk) {
if (isLeadingZero && digit === '0') {
continue;
}
isLeadingZero = false;
ans += digit;
}
return ans === "" ? "0" : ans;
};
470.用 Rand7() 实现 Rand10()
给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。
你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。
每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。
首先获取等概率的 1,2,3,4,5 (如果 rand7()结果>5 则抛弃重新来一次 根据对称性原理 1,2,3,4,5 等概率)
再以 50%的概率是否加上 5 这样可以得到等概率的 1-10
var rand10 = function () {
// 等概率1-5
let result = rand7();
while (result > 5) result = rand7();
// 等概率1-6
let temp = rand7();
while (temp === 7) temp = rand7();
// rand() 1 2 3 4 5 6 <=3为50%
return temp <= 3 ? result : result + 5;
};
543.二叉树直径
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
var diameterOfBinaryTree = function (root) {
let height = 0;
function helper(node) {
if (!node) return 0;
let left = helper(node.left);
let right = helper(node.right);
height = Math.max(left + right, height); //左子树深度 + 右子树深度
return Math.max(left, right) + 1; //以该节点为根节点的最大深度
}
helper(root);
return height;
};
560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列
输入：nums = [1,3,1], k = 2 输出：0
输入：nums = [1,2,3], k = 3 输出：2
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var subarraySum = function (nums, k) {
let len = nums.length,
map = new Map(),
prefixSum = 0,
result = 0;
map.set(0, 1); // 前缀和为 0 的出现次数初始化为 1
for (let i = 0; i < len; i++) {
// 1, 4, 5
prefixSum += nums[i];
// 例如 k = 6，如果遍历到前缀和为 8 时，如果前面出现过 2，说明满足前缀和
if (map.get(prefixSum - k)) {
result += map.get(prefixSum - k);
}
// 如果 prefixSum 这个前缀和第一次出现的，那就初始化为 1，否则 map.get(prefixSum) 的基础上 + 1
map.set(prefixSum, (map.get(prefixSum) || 0) + 1);
}
return result;
};