力扣1-99
1.两数之和(哈希表)
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
// new Map() 遍历数组用声明式
// map中键是数字,值是index
// 如果map中有target-x,用get拿到target-x的index,和当前i作为[i,index]return出去
// 不管怎样本次循环用set设一下当前nums[i],i
// 循环结束return []
let map = new Map();
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
if (map.has(target - x)) {
return [i, map.get(target - x)];
}
map.set(x, i);
}
return [];
};
// O(n)
2.两数相加(链表)
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
const addTwoNumbers = function (l1, l2) {
let dummy = new ListNode(0);
let p = dummy;
let carry = 0; //该位和,在下一次的进位
while (l1 || l2) {
let sum = 0; //该位的和为0,每次循环会刷新
if (l1) {
sum += l1.val;
l1 = l1.next;
}
if (l2) {
sum += l2.val;
l2 = l2.next;
}
sum += carry;
p.next = new ListNode(sum % 10);
carry = Math.floor(sum / 10);
p = p.next;
}
// 最后全加完了,发现carry还有,如6+6=12
// carry必为1
if (carry === 1) {
p.next = new ListNode(carry);
}
return dummy.next;
};
3.无重复字符的最长子串(滑动窗口)
// 集合l在-1位外循环追逐遍历,第二次删除,内循环往后扩展,l走动,挑战最大值
var lengthOfLongestSubstring = function (s) {
let l = -1;
let r = 0;
let max = 0;
let set = new Set();
while (l < r && r < s.length) {
// 到第二次循环(l!==-1),重复已经被破坏
if (l !== -1) {
set.delete(s[l]);
}
//l在任何情况都要自增
l++;
// set中有记录过的,破坏
while (r < s.length && !set.has(s[r])) {
set.add(s[r++]);
}
max = Math.max(max, r - l);
}
return max;
};
4.*寻找两个正序数组的中位数(二分)
https://leetcode.cn/problems/median-of-two-sorted-arrays/description/
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
有两个数组A[7,8,9]和B[1,2,3,4,5,6],两个数组的总长度 len=9 中位数的位置 k=5 比较两个数组第 k/2 项,如果 A[k/2] > B[k/2] 即 B[1],B[2]...B[k/2] 为这两个数组的最小前 k/2 项,则可以直接排除掉,排除掉之后长度和k同步缩小,然后进行下一轮的比较,直到 k=1 的时候,只需要找到两个正序数组第一个元素最小值即可,其中有两 个地方需要特殊处理:
1、一个数组为空的情况,直接取另一个数组的第 k 项即可
2、一个数组的长度小于 k/2 的时候,取数组的最后一项
var findMedianSortedArrays = function (nums1, nums2) {
const len1 = nums1.length;
const len2 = nums2.length;
const mid = (len1 + len2 + 1) >> 1;
const left = getK(nums1, nums2, 0, 0, mid);
// 判断总长度奇偶
if ((len1 + len2) % 2) {
return left;
} else {
const right = getK(nums1, nums2, 0, 0, mid + 1);
return (left + right) / 2;
}
};
// 取第k小的数
function getK(nums1, nums2, start1, start2, k) {
const len1 = nums1.length;
const len2 = nums2.length;
/* 特例 */
// nums1 数组的元素排除完
if (len1 === start1) return nums2[start2 + k - 1];
if (len2 === start2) return nums1[start1 + k - 1];
// 排除到只剩两个元素取最小 即剩余 元素的最小值
if (k === 1) return Math.min(nums1[start1], nums2[start2]);
/* 通常情况 */
// 取k的一半 同时注意可能会超出数组长度 最多取数组最后一个元素
const i = start1 + Math.min(len1, k >> 1) - 1;
const j = start2 + Math.min(len2, k >> 1) - 1;
// j 前面的所有元素被排除了 同时缩减k的值
if (nums1[i] > nums2[j]) {
return getK(nums1, nums2, start1, j + 1, k - (j - start2 + 1));
} else {
return getK(nums1, nums2, i + 1, start2, k - (i - start1 + 1));
}
}
let n = nums1.length + nums2.length;
let nums = nums1.concat(nums2).sort((a, b) => a - b);
let result =
n % 2 == 0 ? (nums[n / 2] + nums[n / 2 - 1]) / 2 : nums[Math.floor(n / 2)];
return result;
5.最长回文子串(中心开花)
// 特殊s.length<=1 return s
// target = ''
// 设置求回文函数(left,right)
// 循环当left和right不越界且left值等于right值时
// left right向外走动
// 循环结束,挑战最大值,用s.substring(left+1,right).length和target.length
// 比较,更新target为新字符串
// 启动函数,通过一个遍历循环,启动函数(i,i)和(i,i+1)
const longestPalindrome = function (s) {
if (s.length <= 1) {
return s;
}
let target = "";
//从哪个字符开始向两边找?
for (let i = 0; i < s.length; i++) {
fun(i, i);
fun(i, i + 1);
}
//怎么求回文?
function fun(left, right) {
// 这里第一次就会执行,比如ab答案是0
while (left >= 0 && right <= s.length - 1 && s[left] == s[right]) {
--left;
right++;
}
//substring:从第一个参数开始,到第二个参数的前一个(包含第一个,不包含第二个)
// 例: 'asdfg'.substring(1,3)=>'sd'
if (right - left > target.length) {
target = s.substring(left + 1, right);
}
}
return target;
};
6.Z 字形变换
将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下:
P A H N
A P L S I I G
Y I R
之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数:
string convert(string s, int numRows);
var convert = function (s, numRows) {
const m = numRows;
const res = new Array(m).fill().map(() => new Array());
let current = 0;
let column = 0;
while (current < s.length) {
let i = 0;
for (; i < m && s[current]; i++) {
res[i][column] = s[current++];
}
i = m - 1;
while (s[current] && i > 1) {
res[--i][++column] = s[current++];
}
column++;
//一遍循环读了PAYP
// 第二遍读了ALIS
}
const sres = [];
// 一行行读取模拟的结果即可
for (let i = 0; i < res.length; i++) {
for (let j = 0; j < res[i].length; j++) {
if (res[i][j]) {
sres.push(res[i][j]);
}
}
}
return sres.join("");
};
7.整数反转
var reverse = function (x) {
let rev = 0;
while (x !== 0) {
const digit = x % 10;
x = ~~(x / 10);
rev = rev * 10 + digit;
if (rev < Math.pow(-2, 31) || rev > Math.pow(2, 31) - 1) {
return 0;
}
}
return rev;
};
8. 字符串转整数
/**
* @param {string} s
* @return {number}
*/
var myAtoi = function (s) {
let res = 0,
// 正负号,默认正号
negativeSymbol = 1;
// 把首尾的空格都去掉
s = s.trim();
for (let i = 0; i < s.length; i++) {
// 负数
if (i == 0 && s[i] == "-") {
negativeSymbol = -1;
continue;
// 正数
} else if (i == 0 && s[i] == "+") continue;
// 因为空格会被转成0,所以要排除空格的情况,也就是说在数字范围内就加上
if (s[i] >= 0 && s[i] <= 9 && s[i] != " ") {
res = res * 10 + (s[i] - 0);
// 为什么在这里就判断呢,因为这里如果就溢出的话,就直接跳出,不需要再后面无意义的计算了
if (res * negativeSymbol <= -2147483648) return -2147483648;
else if (res * negativeSymbol >= 2147483647) return 2147483647;
} else break; // 如123fffe
}
return res * negativeSymbol;
};
9. 回文数
/**
* @param {number} x
* @return {boolean}
*/
// 小于0不是回文数,
// 满足最后一位是0,且是0才是回文数
// 设回文数为0,循环当前数大于回文数。回文数*10+当前数最后位(%10)
// 当前数去掉最后位(Math.floor(x/10))
// 返回x与回文数相等或x与Floor回文数/10相等(x有奇数位)
var isPalindrome = function (x) {
// // 特殊情况:
if (x < 0 || (x % 10 === 0 && x !== 0)) return false;
return (x + "").split("").reverse().join("") === x + "";
// // 如上所述,当 x < 0 时,x 不是回文数。
// // 同样地,如果数字的最后一位是 0,为了使该数字为回文,
// // 则其第一位数字也应该是 0
// // 只有 0 满足这一属性
// if (x < 0 || (x % 10 === 0 && x !== 0)) {
// return false;
// }
let revertedNumber = 0;
while (x > revertedNumber) {
revertedNumber = revertedNumber * 10 + (x % 10);
x = Math.floor(x / 10);
}
// 当数字长度为奇数时,我们可以通过 revertedNumber/10 去除处于中位的数字。
// 例如,当输入为 12321 时,在 while 循环的末尾我们可以得到 x = 12,revertedNumber = 123,
// 由于处于中位的数字不影响回文(它总是与自己相等),所以我们可以简单地将其去除。
return x === revertedNumber || x === Math.floor(revertedNumber / 10);
};
10. *正则匹配
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 所谓匹配,是要涵盖 整个 字符串 s 的,而不是部分字符串
const isMatch = (s, p) => {
if (s == null || p == null) return false;
const sLen = s.length,
pLen = p.length;
const dp = new Array(sLen + 1);
for (let i = 0; i < dp.length; i++) {
dp[i] = new Array(pLen + 1).fill(false); // 将项默认为false
}
// base case,
dp[0][0] = true;
// aaaa和a*必匹配,但是和b*不匹配
for (let j = 1; j < pLen + 1; j++) {
if (p[j - 1] == "*") dp[0][j] = dp[0][j - 2];
}
// 迭代
for (let i = 1; i < sLen + 1; i++) {
for (let j = 1; j < pLen + 1; j++) {
// a 和 .
// a 和 a
if (s[i - 1] == p[j - 1] || p[j - 1] == ".") {
// 如果上一个匹配则匹配,否则就不匹配
dp[i][j] = dp[i - 1][j - 1];
} else if (p[j - 1] == "*") {
// a 和 a*
// a 和 .*
if (s[i - 1] == p[j - 2] || p[j - 2] == ".") {
//把*看作0试试 (ab->abb*
//把a*跟a换掉试试
// (abbbb-> ab*)
dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];
} else {
// 把*看作0试试
dp[i][j] = dp[i][j - 2];
}
}
}
}
return dp[sLen][pLen]; // 长sLen的s串 是否匹配 长pLen的p串
};
11.盛最多水的容器
https://leetcode.cn/problems/container-with-most-water/description/
双指针,向中遍历
若向内 移动长板 ,水槽的短板min(h[i],h[j])min(h[i], h[j])min(h[i],h[j])
不变或变小,因此下个水槽的面积 一定变小
向内移动长板,面积不变或变大
/**
* @param {number[]} height
* @return {number}
*/
Area = function (height) {
//两根主子间的最大面积
let max = 0;
//使用双指针求面积
for (let i = 0, j = height.length - 1; i < j; ) {
//求两根柱子之间高度低的哪一个
let minHeight = height[i] < height[j] ? height[i++] : height[j--];
//两个柱子之间的宽度
let leng = j - i + 1;
//求面积
let area = leng * minHeight;
//取最大值
max = Math.max(max, area);
}
return max;
};
12.整数转罗马数字
https://leetcode.cn/problems/integer-to-roman/description/
/**
* @param {number} num
* @return {string}
*/
var intToRoman = function (num) {
// 从大到小排列,准备好400 900的特殊情况
const valueSymbols = [
[1000, "M"],
[900, "CM"],
[500, "D"],
[400, "CD"],
[100, "C"],
[90, "XC"],
[50, "L"],
[40, "XL"],
[10, "X"],
[9, "IX"],
[5, "V"],
[4, "IV"],
[1, "I"],
];
const res = [];
for (let [val, roma] of valueSymbols) {
while (num >= val) {
num -= val;
res.push(roma);
}
}
return res.join("");
};
13.罗马数字转整数
https://leetcode.cn/problems/roman-to-integer/description/
/**
* @param {string} s
* @return {number}
*/
var romanToInt = function (s) {
const symbolValues = new Map();
// 从小到大排
symbolValues.set("I", 1);
symbolValues.set("V", 5);
symbolValues.set("X", 10);
symbolValues.set("L", 50);
symbolValues.set("C", 100);
symbolValues.set("D", 500);
symbolValues.set("M", 1000);
let ans = 0;
const n = s.length;
for (let i = 0; i < n; ++i) {
const value = symbolValues.get(s[i]);
// 如果遇到IV,则-1+5
if (i < n - 1 && value < symbolValues.get(s[i + 1])) {
ans -= value;
} else {
ans += value;
}
}
return ans;
};
14.最长公共前缀
/**
* @param {string[]} strs
* @return {string}
*/
// 特殊strs.length==0,return ""
// 假设ans为strs[0]
// 从第二个开始遍历strs
// 设j为0
// 当j<ans.length&&j<strs[i].length时
// 如果ans[j]!=strs[i][j] break
// j++
// 跳出循环。ans = ans.substr(0,j)
var longestCommonPrefix = function (strs) {
if (strs.length == 0) return "";
let ans = strs[0];
for (let i = 1; i < strs.length; i++) {
let j = 0;
while (j < ans.length) {
if (ans[j] != strs[i][j]) {
//第i个单词的第j个字母
break;
}
j++;
}
ans = ans.substr(0, j); //ans截取前j个字母
}
return ans;
};
15.三数之和(三指针)
给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,
同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
/**
* @param {number[]} nums
* @return {number[][]}
*/
// 特殊nums.len<3
// 将数组升序排列
// 循环遍历
// 1.如果当前值大于0,break
// 2.如果当前位不为0且与上一位值相等,continue去重
// 3.l=i+1三指针第二个,r=len-1三指针第三
// 4.while l<r
// 计算sum
// 41如果sum=0,三值加入res,内部while l<r l值<l+1 l++去重;r同理
// 内循环结束,注意让lr走动
// 42如果sum<0 l++
// 43同理
// 时间复杂度:O(n^2)
// n 为数组长度
var threeSum = function (nums) {
let ans = [];
let len = nums.length;
nums.sort((a, b) => a - b);
for (let i = 0; i < len - 2; i++) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] === nums[i - 1]) continue;
// 最大情况
if (nums[i] + nums[len - 2] + nums[len - 1] < 0) continue;
let l = i + 1;
let r = len - 1;
while (l < r) {
sum = nums[i] + nums[l] + nums[r];
if (sum === 0) {
ans.push([nums[i], nums[l], nums[r]]);
while (l < r && nums[l] === nums[l + 1]) l++;
while (l < r && nums[r] === nums[r - 1]) r--;
l++;
r--;
}
if (sum < 0) l++;
if (sum > 0) r--;
}
}
return ans;
};
16.最接近的三数之和
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。
返回这三个数的和。
// 只存在一个解
var threeSumClosest = function (nums, target) {
let N = nums.length;
let res = Infinity;
// 也是升序
nums.sort((a, b) => a - b);
for (let i = 0; i < N; i++) {
let left = i + 1;
let right = N - 1;
while (left < right) {
let sum = nums[i] + nums[left] + nums[right];
if (sum === target) return sum;
//每次收缩得到一个相对最接近target的解
// 类似记录max,反正最后也是输出max
if (Math.abs(sum - target) < Math.abs(res - target)) {
res = sum;
}
if (sum < target) left++;
if (sum > target) right--;
}
}
return res;
};
17.电话号码的字母组合
给定一个仅包 含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母
输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function (digits) {
const k = digits.length;
const map = [
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz",
];
if (!k) return [];
if (k === 1) return map[digits].split("");
const res = [],
path = [];
backtracking(0);
return res;
function backtracking(a) {
if (path.length === k) {
res.push(path.join(""));
return;
}
for (const v of map[digits[a]]) {
path.push(v);
backtracking(a + 1);
path.pop();
}
}
};
18.四数之和
**注意四数之和有 target 而不是像三数之和为 0
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
// 先升序
// 三层循环,第一层确定第一位~length-4,第二层确定第二位~length-3
// 还是三种剪枝
// 第三层确定left right窗口
var fourSum = function (nums, target) {
const quadruplets = [];
if (nums.length < 4) {
return quadruplets;
}
nums.sort((x, y) => x - y);
const length = nums.length;
for (let i = 0; i < length - 3; i++) {
// --- 外层和内层都能剪三次
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break;
}
if (
nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] <
target
) {
continue;
}
// ===
// ** * *
// ij固定,left,right动
for (let j = i + 1; j < length - 2; j++) {
// ---
if (j > i + 1 && nums[j] === nums[j - 1]) {
continue;
}
if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
break;
}
if (nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
continue;
}
//---
let left = j + 1,
right = length - 1;
while (left < right) {
const sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum === target) {
quadruplets.push([nums[i], nums[j], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left + 1]) {
left++;
}
left++;
while (left < right && nums[right] === nums[right - 1]) {
right--;
}
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return quadruplets;
};
19.删除链表的倒数第 N 个结点
var removeNthFromEnd = function (head, n) {
// ret为虚拟头节点
// 有虚拟头节点,可以不判断是不是直接删掉第一个节点
let hair = new ListNode(0, head),
slow = (fast = hair);
while (n--) fast = fast.next;
while (fast.next !== null) {
fast = fast.next;
slow = slow.next;
}
// 拿到的是被删除的节点的前一个!因此八倒三,要拿5号
slow.next = slow.next.next;
return hair.next;
};
20.有效的 括号(栈)
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function (str) {
// 对象键名左值右,准备栈,let of遍历,如果是键(左)(map[i]存在),加入栈,如果不是键是值且
// 栈顶不是对应键map[stk.pop()]!==i,return false
// 循环结束,栈空返回true否则false
let map = {
"{": "}",
"(": ")",
"[": "]",
};
let stk = [];
for (let i of str) {
// 如果是左括号
if (map[i]) {
stk.push(i);
//如果是右括号,但对不上栈顶
} else if (map[stk.pop()] !== i) {
return false;
}
}
return stk.length === 0;
};
21.合并有序链表(递归)
将两个升序链表合并为一个新的 升序 链表并返回。
// 递归函数(l1,l2),如果!l1 returnl2 如果!l2 return l1
// 如果l1值小于l2,l1.next = 递归函数(l1.next,l2) return l1
// else情况对称
var mergeTwoLists = function (l1, l2) {
if (l1 === null) {
return l2;
}
if (l2 === null) {
return l1;
}
if (l1.val > l2.val) {
l2.next = mergeTwoLists(l1, l2.next);
//这种情况,最小的是l2开头,因此返回l2
return l2;
} else {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
//通过(l1,l2.next)将问题转为更小的问题
//return返回符合条件的(偏大的)
//lx.next赋值能将return的接到链表后面,且lx肯定是前面同一位置较小的一方(因为在if里
};
迭代法(双指针)
const merge = (head1, head2) => {
let dummy = new ListNode(0);
let cur = dummy;
// 新链表,新的值小就先接谁
while (head1 && head2) {
if (head1.val < head2.val) {
cur.next = head1;
head1 = head1.next;
} else {
cur.next = head2;
head2 = head2.next;
}
cur = cur.next;
}
// 如果后面还有剩余的就把剩余的接上
cur.next = head1 == null ? head2 : head1;
return dummy.next;
};
22.括号生成
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
var generateParenthesis = function (n) {
const res = [];
const track = [];
function trackCracket(left, right) {
if (left < 0 || right < 0) return;
if (left > right) return;
if (left == 0 && right == 0) {
res.push(track.join(""));
return;
}
track.push("(");
trackCracket(left - 1, right);
track.pop();
track.push(")");
trackCracket(left, right - 1);
track.pop();
}
trackCracket(n, n);
return res;
};
23.合并 K 个升序链表(归并)
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表
输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function (lists) {
// 当是空数组的情况下
if (!lists.length) {
return null;
}
// 合并两个排序链表
const merge = (head1, head2) => {
let dummy = new ListNode(0);
let cur = dummy;
// 新链表,新的值小就先接谁
while (head1 && head2) {
if (head1.val < head2.val) {
cur.next = head1;
head1 = head1.next;
} else {
cur.next = head2;
head2 = head2.next;
}
cur = cur.next;
}
// 如果后面还有剩余的就把剩余的接上
cur.next = head1 == null ? head2 : head1;
return dummy.next;
};
const mergeLists = (lists, start, end) => {
// base case 只有一个链接的情况
if (start + 1 === end) {
return lists[start];
}
// 输入的k个排序链表,可以分成两部分,前k/2个链表和后k/2个链表
// 如果将这前k/2个链表和后k/2个链表分别合并成两个排序的链表,再将两个排序的链表合并,那么所有链表都合并了
let mid = start + ((end - start) >> 1);
let head1 = mergeLists(lists, start, mid);
let head2 = mergeLists(lists, mid, end);
return merge(head1, head2);
};
// 前闭后开
return mergeLists(lists, 0, lists.length);
};
24.两两交换链表中的节点
1,2,3,4->2,1,4,3
var swapPairs = function (head) {
if (head === null || head.next === null) {
return head;
}
const newHead = head.next;
head.next = swapPairs(newHead.next);
newHead.next = head;
return newHead;
};
25.K 个一组翻转链表
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
// 先实现反转函数(head,tail),return [tail,head]
// prev初始值为4,curr初始值为1
// [1,2,3] 4, 1连上4,prev变为1,curr变为[2,3]
// 主函数(head,k)
// 在head节点的前面加一个hair节点0
// [0,1,2,3,4]
// pre初始值是0,当head存在时,
// 设tail为pre,遍历k次,tail一直next,找到这一group的尾部
// 如果越界了,return hair.next,即哑节点后面的一个,直接结束
// 跳出循环,先用next记录tail.next,
// [head,tail] = myReverse(head,tail),反转这一group
// 把这一group接到pre的后面,把新tail(let出来的可为新)的后面接上
// next,更新pre为新tail,head为tail.next
// 最终返回hair.next,即哑节点后面的一个
const myReverse = (head, tail) => {
let prev = null;
let curr = head;
// 由于本题tail的下一个不是null,所以终止条件是 prev 已经到头了
while (prev !== tail) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return [tail, head];
};
const reverseKGroup = function (head, k) {
const hair = new ListNode(0);
hair.next = head;
let originPre = hair;
while (head) {
let oneGroupTail = pre;
// 查看剩余部分长度是否大于等于 k,如果小于,直接return hair.next
for (let i = 0; i < k; ++i) {
oneGroupTail = oneGroupTail.next;
if (!oneGroupTail) {
// 已经是最后一个group,把最终链表返回出去
return hair.next;
}
}
//
const orginNext = oneGroupTail.next;
[head, oneGroupTail] = myReverse(head, oneGroupTail);
// 把子链表重新接回原链表
originPre.next = head;
oneGroupTail.next = originNext;
originPre = oneGroupTail;
head = oneGroupTail.next;
}
return hair.next;
};
26.有序数组去重
更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。 返回 k 。 并返回 nums 中唯一元素的个数
/**
* @param {number[]} nums
* @return {number}
*/
// 双指针都从1开始,fast负责扩展,一旦出现不连续,就将当前的fast赋给slow位(去重),slow才进
// 只需要一遍遍历
// 最后要求返回个数,就是slow的值,当然slice()
var removeDuplicates = function (nums) {
const n = nums.length;
if (n === 0) {
return 0;
}
let fast = 1,
slow = 1;
while (fast < n) {
if (nums[fast] !== nums[fast - 1]) {
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return slow;
};
28.找出 字符串中第一个匹配项的下标*
const strStr = (haystack, needle) => {
// 注意空串和无法匹配的结果不一样
if (needle === "") return 0;
const haystackLen = haystack.length;
const needleLen = needle.length;
for (let i = 0; i < haystackLen; i++) {
if (haystack.substring(i, i + needleLen) === needle) return i;
}
return -1;
};
29.两数相除 *
给你两个整数,被除数 dividend 和除数 divisor。将两数相除,要求 不使用 乘法、除法和取余运算。
整数除法应该向零截断,也就是截去(truncate)其小数部分。例如,8.345 将被截断为 8 ,-2.7335 将被截断至 -2 。
返回被除数 dividend 除以除数 divisor 得到的 商 。
注意:假设我们的环境只能存储 32 位 有符号整数,其数值范围是 [-2147483648, 2147483648 − 1] 。本题中,如果商 严格大于 2**31 − 1 ,则返回 2**31 − 1 ;如果商 严格小于 -2**31 ,则返回 -2**31 。
var divide = function (dividend, divisor) {
if (divisor === 0) return Infinity;
if (dividend === 0) return 0;
if (dividend === -2147483648 && divisor === -1) return 2147483647;
let res = 0;
let flag = "";
if ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)) {
flag = "-";
}
dividend = Math.abs(dividend);
divisor = Math.abs(divisor);
while (dividend >= divisor) {
let temp = divisor,
m = 1;
while (temp <= dividend >> 1) {
// 位运算模拟乘法,撑到最大。防止溢出
temp <<= 1;
m <<= 1;
}
dividend -= temp;
res += m;
}
return parseInt(flag + res);
};
31.下一个排列(倒遍历 17831,n-2,n-1)
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ,因为 [3,2,1] 不存在一个字典序更大的排列。
必须 原地 修改,只允许使用额外常数空间。
function nextPermutation(nums) {
let i = nums.length - 2; // 向左遍历,i从倒数第二开始是为了nums[i+1]要存在
while (i >= 0 && nums[i] >= nums[i + 1]) {
// 从右往左,寻找第一个小于右邻居的数
i--;
}
if (i >= 0) {
// 这个数在数组中存在,从它身后挑一个数,和它换
let j = nums.length - 1; // 从最后一项,向左遍历
while (j >= 0 && nums[j] <= nums[i]) {
// 寻找第一个大于 nums[i] 的数
// 17831 18731
j--;
}
[nums[i], nums[j]] = [nums[j], nums[i]]; // 两数交换,实现变大
} else {
// 如果 i = -1,说明是递减排列,如 3 2 1,没有下一排列,直接翻转为最小排列:1 2 3
// 注意从i+1开始
let l = i + 1;
let r = nums.length - 1;
while (l < r) {
[nums[l], nums[r]] = [nums[r], nums[l]];
l++;
r--;
}
}
}
32.最长有效括号(栈,初始-1)
/**
* @param {string} s
* @return {number}
*/
const longestValidParentheses = (str) => {
// 初始有-1
let stk = [-1];
let max = 0;
for (let i in str) {
// 若为右,则弹出栈顶,如果还有栈顶则计算max
// 没有栈顶则把右压入作为新栈顶
if (str[i] === "(") {
stk.push(i);
} else if (str[i] === ")") {
stk.pop();
if (stk[stk.length - 1]) {
max = Math.max(max, i - stk[stk.length - 1]);
} else {
stk.push(i);
}
// 若为左直接压入
}
}
return max;
};
33.搜索旋转排序数组(改造二分)
[0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
const search = function(nums, target) {
let start = 0,end = nums.length - 1
let mid
while(start <= end){
mid = Math.floor((end-start)/2) + start
if(nums[mid] === target){
return mid
}
console.log(nums[mid])
// 由start<=mid得出
// s到mid包括部分左升序(严格),注意是小于等于,只有一个数的情况下,应该在这一个数以左比较,右为空
if(nums[start]<=nums[mid]){
//因为是部分左升序,满足这个可以缩小范围,但是不一定收敛成普通二分
if(target>=nums[start]&&target<nums[mid]){
end = mid - 1
}else{
//不满足,太好了,可以直接收敛成普通二分
start = mid + 1
}
// s到mid为完整左升序加部分右升序,那就去看右部分,因为是完整右升序(严格),容易判断
}else{
// 总会有某次循环收敛成正常二分
if(target>nums[mid]&&target<=nums[end]){
start = mid + 1
}else{
end = mid - 1
}
}
}
return -1
};
34.在排序数组中查找元素的第一个和最后一个位置(二分)
给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题
var searchRange = function (nums, target) {
// 特殊情况
if (nums.length === 0) return [-1, -1];
// 左二分尽量往左,(数组,目标)
// 右二分尽量往右
// 但是注意右二分可能到左边区间中,一开始是在整个数组找,和左右无关
// 只是两种限制条件类型的二分,在target找到情况下一个进行r = m - 1
// 一个进行l = m + 1
return [leftSearch(nums, target), rightSearch(nums, target)];
};
function leftSearch(nums, target) {
let l = 0,
r = nums.length - 1;
while (l <= r) {
let m = Math.floor((l + r) / 2);
if (nums[m] > target) {
r = m - 1;
} else if (nums[m] < target) {
l = m + 1;
} else {
// 如果等于,尽量往左继续找
// 就算左边没有,下一次l=m+1也会退出循环并找回来
r = m - 1;
}
}
// l 只会右溢出(在左侧找不到),或者找到第0位,却不是target
if (l >= nums.length || nums[l] !== target) {
return -1;
}
//等于
return l;
}
function rightSearch(nums, target) {
let l = 0,
r = nums.length - 1;
while (l <= r) {
let m = Math.floor((l + r) / 2);
if (nums[m] > target) {
r = m - 1;
} else if (nums[m] < target) {
l = m + 1;
} else {
l = m + 1;
}
}
// r只会左溢出,或者找到末位但不等于目标
if (r < 0 || nums[r] !== target) {
return -1;
}
return r;
}
35.搜索插入位置
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
// 二分,如果<=设置ans为mid
var searchInsert = function (nums, target) {
const n = nums.length;
let left = 0,
right = n - 1,
ans = n;
while (left <= right) {
let mid = ((right - left) >> 1) + left;
if (target <= nums[mid]) {
ans = mid;
// 尽量往左找,能记到target的前一个
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
};
38.外观数列
var countAndSay = function (n) {
let str = "1";
// 第一项为1个1,第二项则为11,第三项则为2个1(21)
for (let i = 2; i <= n; ++i) {
const sb = [];
// 每一项都双指针跑一次
let start = 0;
let pos = 0;
while (pos < str.length) {
// 内扩展 1211
while (pos < str.length && str[pos] === str[start]) {
pos++;
}
sb.push("" + (pos - start) + str[start]);
start = pos;
}
str = sb.join("");
}
return str;
};
39.组合总和(可以无限选,如果选了小于 0 就不选了,记得有跳过情况)
输入: (candidates = [2, 3, 5]), (target = 8);
输出: [
[2, 2, 2, 2],
[2, 3, 3],
[3, 5],
];
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function(candidates, target) {
const ans = [];
// idx当前遍历到数组哪一位
const dfs = (target, combine, idx) => {
if (idx > candidates.length - 1) {
return;
}
if (target === 0) {
ans.push(combine);
return;
}
// 直接跳过
dfs(target, combine, idx + 1);
// 选择当前数,可以反复选择多次,但是一旦target-x>=0就不选了
if (target - candidates[idx] >= 0) {
dfs(target - candidates[idx], [...combine, candidates[idx]], idx);
}
}
dfs(target, [], 0);
return ans;
};
40.组合总和 II
给定一个候选人编号的集合 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意:解集不能包含重复的组合。
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
const combinationSum2 = (candidates, target) => {
candidates.sort((a, b) => a - b); // 升序排序,因为排序了可以一路顺着到底
const res = [];
const temp = [];
const dfs = (start, sum) => {
// start是索引 当前选择范围的第一个
if (sum > target) {
// 爆掉了,不用继续选了
return; // 结束当前递归
}
if (sum == target) {
// 满足条件,加入解集
res.push([...temp]); // temp是引用,所指向的内存后续还要操作,所以拷贝一份
}
for (let i = start; i < candidates.length; i++) {
// 枚举出当前的选择
if (i - 1 >= start && candidates[i - 1] == candidates[i]) {
// 当前选项和左邻选项一样,跳过
continue;
}
temp.push(candidates[i]); // 作出选择
dfs(i + 1, sum + candidates[i]); // 基于该选择,继续选择,递归
temp.pop(); // 上面的递归结束,撤销选择,回到选择前的状态,切入另一分支
}
};
dfs(0, 0);
return res;
};
41.缺失的第一个正数(-1,-1,-1,-1)(1,2,3,4)
/**
* @param {number[]} nums
* @return {number}
*/
// 第一次遍历将nums中负数位替换成len+1
var firstMissingPositive = function (nums) {
const n = nums.length;
// [3,4,-1,1]
for (let i = 0; i < n; i++) {
if (nums[i] <= 0) {
nums[i] = n + 1;
}
}
console.log(nums);
// [3,4,5,1]
// 第二次遍历,将nums中值<=len的位对应的数取反
// 大于 len不管了
for (let i = 0; i < n; i++) {
let num = Math.abs(nums[i]);
if (num <= n) {
nums[num - 1] = -Math.abs(nums[num - 1]);
}
}
// [-3,4,-5,-1]
for (let i = 0; i < n; i++) {
// 常数级别空间,所以只能数组原地记录
// 负数位好歹也是有一个大于len的,正好就是缺失的整数
// 抽屉思想
if (nums[i] > 0) {
return i + 1;
}
}
// -1,-1,-1,-1
// 5,5,5,5
// 1
// 1,2,3,4
// -1,-2,-3,-4
//5
return n + 1;
};
42.接雨水(双指针)
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
/**
* @param {number[]} height
* @return {number}
*/
const trap = function (height) {
let ans = 0;
let left = 0,
right = height.length - 1;
let leftMax = 0,
rightMax = 0;
while (left <= right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
//*
//*234*
// 每次到这里一次,都能保证是从较低的一边来的
// 4-》3-》2
if (height[left] < height[right]) {
ans += leftMax - height[left];
++left;
} else {
ans += rightMax - height[right];
--right;
}
}
return ans;
};
43.字符串相乘
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
var multiply = function (num1, num2) {
if (num1 === "0" || num2 === "0") return "0";
let len1 = num1.length,
len2 = num2.length,
res = new Array(len1 + len2).fill(0);
//用11*11举例
// 结果最多为 m + n 位数
for (let i = len1 - 1; i >= 0; i--) {
for (let j = len2 - 1; j >= 0; j--) {
// 从个位数开始,逐步相乘
const mul = num1[i] * num2[j];
// 乘积在结果数组中对应的位置
const p1 = i + j,
p2 = i + j + 1;
// 对结果进行累加,加上结果的第p2位(为上一次进过位的地方
const sum = mul + res[p2];
// 结果的第p1位,加上进位的数字
res[p1] += Math.floor(sum / 10);
// 结果的第p2位,如果相加后大于10,则变成个位(已经进过位了
res[p2] = sum % 10;
}
}
if (res[0] === 0) res.shift();
return res.join("");
};
45.跳跃游戏 II
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
首先不管怎样都能跳到终点
其次刚开始必须走,每一步都计算从这能走的最大步数 直到把开始每次机会都用完
必须要走了,那就按之前最大步数走,count++
同时获得了新拓展的机会,继续每一步都计算能走的最大步数
var jump = function (nums) {
let end = 0,
longest = 0,
count = 0;
for (let i = 0; i < nums.length - 1; i++) {
// 注意此处设定为i<length-1
// 根据题目要求,假定每一个组合都能够跳到最终位置,因此最后一个位置不需要计算在内
longest = Math.max(longest, nums[i] + i);
if (end === i) {
count++;
end = longest;
}
}
return count;
};
46.全排列
给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function (nums) {
// 递归函数(left,right),如果左长度等于nums长度,进res,return剪枝
// forEach遍历右,...浅拷贝然后过滤掉i,递归函数(左加i,右)
// 空右启动
let len = nums.length;
let res = [];
const order = (l, r) => {
if (l.length === len) {
res.push(l);
return;
}
r.forEach((i) => {
// 返回true保留,返回false过滤掉
let tem = [...r].filter((j) => j !== i);
order([...l, i], tem);
});
};
order([], nums);
return res;
};
47.全排列 II *
给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permuteUnique = function (nums) {
const ans = [];
const arr = [];
const vis = new Array(nums.length).fill(false);
// **************聚拢数字相同的
nums.sort((x, y) => x - y);
const backtrack = (idx) => {
if (idx === nums.length) {
ans.push([...arr]);
return;
}
// 为什么不必再放?
// 因为如果上次1没被用过,这次用1相当于重复刷新,类似闭包
// 如果上次1被用过了,才能真正起到减少1的次数,这样一共
// 有3个1,也只会用3次
// 如果在第2个1开始递归,那会重复执行2个1开始的递归
//向idx位塞入nums每一位,继续递归
for (let i = 0; i < nums.length; ++i) {
// 剪枝,idx位塞1已经在第一次塞1递归完了,第二次用到1不用递归啦(!vis[i - 1]),否则重复了很多操作
if (vis[i] || (i > 0 && nums[i] === nums[i - 1] && !vis[i - 1])) {
continue;
}
arr.push(nums[i]);
vis[i] = true;
backtrack(idx + 1);
vis[i] = false;
arr.pop();
}
};
backtrack(0);
return ans;
};
48.旋转图像
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
//12
//34
//56
//135
//246
//531
//642
// 设一个swap函数(矩阵,[x1.y1],[x2,y2])
// 遍历矩阵,交换ij和ji
// 对矩阵中每一行逆序 matrix[i].reverse()
let rotate = function (matrix) {
function swap(matrix, [x1, y1], [x2, y2]) {
const tem = matrix[x1][y1];
matrix[x1][y1] = matrix[x2][y2];
matrix[x2][y2] = tem;
}
const n = matrix.length;
// 对角线反转
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
swap(matrix, [i, j], [j, i]);
}
}
// 挨个逆序
for (let i = 0; i < n; i++) {
matrix[i].reverse();
}
};
50.Pow(x,n)
实现 pow(x, n) ,即计算 x 的整数 n 次幂函数
dp
var myPow = function (x, n) {
if (n == 0) return 1;
if (n < 0) return 1 / myPow(x, -n);
// 如果是奇数,手动算一次,即乘x
if (n % 2) return x * myPow(x, n - 1);
// 如果不是,继续快速幂
return myPow(x * x, n / 2);
};
53.最大子数组和(连续子数组的最大和,最大连续和)(dp)
这种连续子数组,之前的状态不符合条件,都应该直接清空成新的 通过挑战最大值记录结果
/**
* @param {number[]} nums
* @return {number}
*/
// dp空数组max-10000,遍历数组,dp[i]设为dp[i-1]+nums[i]和num[i]较大一方
// 用dp[i]挑战最大值
// 注意判断dp[i-1]是否存在
function maxSubArray(nums) {
let dp = [];
let max = -10000;
for (let i = 0; i < nums.length; i++) {
dp[i] = Math.max(nums[i] + (dp[i - 1] ? dp[i - 1] : 0), nums[i]);
max = Math.max(dp[i], max);
}
return max;
}
54.螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ,请按照 顺时针螺旋顺序 ,返回矩阵中的所有元素。
/**
* @param {number[][]} matrix
* @return {number[]}
*/
const spiralOrder = function (matrix) {
if (!matrix.length || !matrix[0].length) {
return [];
}
const rows = matrix.length,
columns = matrix[0].length;
const order = [];
let left = 0,
right = columns - 1,
top = 0,
bottom = rows - 1;
while (left <= right && top <= bottom) {
for (let j = left; j <= right; j++) {
order.push(matrix[top][j]);
}
for (let i = top + 1; i <= bottom; i++) {
order.push(matrix[i][right]);
}
//如果只有一行是不能走回头路的,所以要同时满足且情况
if (left < right && top < bottom) {
for (let j = right - 1; j > left; j--) {
order.push(matrix[bottom][j]);
}
for (let i = bottom; i > top; i--) {
order.push(matrix[i][left]);
}
}
// 关键是这里一致的拆分了一个更小的问题
[left, right, top, bottom] = [left + 1, right - 1, top + 1, bottom - 1];
}
return order;
};
55.跳跃游戏
给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。
// 设当前位能往右跳到的最远位置初始为0
// 遍历数组,如果当前位小于最远位置,挑战最远位置i+nums[i]
var canJump = function (nums) {
let len = nums.length;
let end = 0;
for (let i = 0; i < len; i++) {
if (i <= end) {
end = Math.max(end, i + nums[i]);
let jump = i + nums[i];
if (jump >= len - 1) return true;
}
}
//[0,0,0,1]
return false;
};
56.合并区间(排序+标记 0+cur 指针)
输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
// 特殊,intervals.length===1 return intervals
// 按照第一个数字大小排序return a[0] - b[0]
// intervals.push(0)标记
// cur = intervals[0]
// 外遍历intervals
// 内循环如果intervals[i]!==0不为标记,且cur[1]>=intervals[i][0]{cur = [cur[0],cur[1]>int[i][1]则为cur[1]否则替换为int[i][1]],i++
// 这个i++会影响外层循环的i!
// 跳出内循环说明合并完成,res.push(curr) curr= int[i]
var merge = function (ins) {
if (ins.length === 1) return ins;
ins.sort(function (arr1, arr2) {
return arr1[0] - arr2[0];
});
const res = [];
let cur = ins[0];
ins.push(0); // 退出标志位,因为外循环后面还要做
for (let i = 0; i < ins.length; i++) {
// 注意大于等于
while (ins[i] !== 0 && cur[1] >= ins[i][0]) {
const temp = [cur[0], cur[1] > ins[i][1] ? cur[1] : ins[i][1]];
cur = temp;
i++;
}
res.push(cur);
cur = ins[i];
}
return res;
};
61.旋转链表
var rotateRight = function (head, k) {
if (k === 0 || !head || !head.next) {
return head;
}
let n = 1;
let cur = head;
while (cur.next) {
cur = cur.next;
n++;
}
cur.next = head;
// 5 - 2%5 = 3
let add = n - (k % n);
let newcur = head;
while (add !== 1) {
newcur = newcur.next;
add--;
}
//先保留要返回的指针
const ret = newcur.next;
newcur.next = null;
return ret;
};
62.不同路径(dp,上和左的和)
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
// 生成m*n的0填满数组,new Array(m).fill(0).map(()=>new Array(n).fill(0))
// 遍历第一行0~m-1和第一列的0~n-1,设为1
// 双循环遍历,f[i][j] = f[i-1][j] + f[i][j-1]
// 返回f[m-1][n-1]
// 111111
// 123456
// 136000
var uniquePaths = function (m, n) {
const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
for (let i = 0; i < m; i++) {
f[i][0] = 1;
}
for (let j = 0; j < n; j++) {
f[0][j] = 1;
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
return f[m - 1][n - 1];
};
63.不同路径 II
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1 和 0 来表示
/**
* @param {number[][]} obstacleGrid
* @return {number}
*/
// 初始点为障碍,和初始化时如果遇到障碍,就停止继续初始化
const uniquePathsWithObstacles = (obstacleGrid) => {
if (obstacleGrid[0][0] == 1) return 0; // 出发点就被障碍堵住
const m = obstacleGrid.length;
const n = obstacleGrid[0].length;
// dp数组初始化
const dp = new Array(m).fill().map(() => new Array(n).fill(0));
// base case
dp[0][0] = 1; // 终点就是出发点
for (let i = 1; i < m; i++) {
// 第一列其余的case
if (obstacleGrid[i][0] == 1) break;
dp[i][0] = 1;
}
for (let i = 1; i < n; i++) {
// 第一行其余的case
if (obstacleGrid[0][i] == 1) break;
dp[0][i] = 1;
}
// 迭代
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
// 落脚点为1,则到这里的方法为0
dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1]; // 到达(m-1,n-1)的路径数
};
64.最小路径和(dp,min 上和左)
给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
/**
* @param {number[][]} grid
* @return {number}
*/
// dp矩阵直接用原地grid就行,因为不回头,
// dp矩阵第一行依次求和
// 第一列一次求和
// 然后双循环从1,1开始遍历,grid[i][j]+=上面的和左边的最小
var minPathSum = function (grid) {
let row = grid.length,
col = grid[0].length;
for (let i = 1; i < row; i++) {
grid[i][0] += grid[i - 1][0];
}
for (let j = 1; j < col; j++) {
grid[0][j] += grid[0][j - 1];
}
for (let i = 1; i < row; i++) {
for (let j = 1; j < col; j++) {
grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
}
}
return grid[row - 1][col - 1];
};
67.二进制求和
给你两个二进制字符串 a 和 b ,以二进制字符串的形式返回它们的和。
/**
* @param {string} a
* @param {string} b
* @return {string}
*/
var addBinary = function (a, b) {
let add = 0;
let sum = [];
for (let i = a.length - 1, j = b.length - 1; i >= 0 || j >= 0; i--, j--) {
// 位数不够,默认为 0, 但是全都是0就算完了
let num1 = +a[i] || 0;
let num2 = +b[j] || 0;
// 两数相同异或为0,0与任意数字异或为数字本身
sum.unshift(num1 ^ num2 ^ add);
add = num1 + num2 + add > 1 ? 1 : 0;
}
if (add === 1) sum.unshift(1);
return sum.join("");
};
69.x 的平方根
给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function (x) {
if (x < 2) return x;
let left = 1;
// >=2
let right = Math.floor(x / 2);
while (left <= right) {
let mid = Math.floor(left + (right - left) / 2);
if (mid * mid === x) return mid;
if (mid * mid < x) left = mid + 1;
else right = mid - 1;
}
//** 返回right能保证结果是向下取整的,left则是向上
return right;
};
70.爬楼梯
/**
* @param {number} n
* @return {number}
*/
// dp[0]和dp[1]都是1
// 从2开始,累加,最后return dp[n]
var climbStairs = function (n) {
let p = 0;
let q = 0;
let m = 1;
for (let i = 1; i <= n; i++) {
p = q;
q = m;
m = p + q;
}
return m;
};
71.简化路径(栈)
/**
* @param {string} path
* @return {string}
*/
var simplifyPath = function (path) {
const names = path.split("/");
const stack = [];
for (const name of names) {
if (name === "..") {
if (stack.length) {
stack.pop();
}
} else if (name.length && name !== ".") {
stack.push(name);
}
}
return "/" + stack.join("/");
};
72.编辑距离(dp)
给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
插入一个字符 删除一个字符 替换一个字符
dp 求最小值的核心在于 Math.min(不同的策略)
/**
* @param {string} word1
* @param {string} word2
* @return {number}
*/
// 抛弃第0行和第0列,一律从1开始到word.length
// word1
// w000000
//
//
const minDistance = (word1, word2) => {
let dp = Array.from(Array(word1.length + 1), () =>
Array(word2.length + 1).fill(0)
);
//初始化数组,word1前i个字符最少需要i次操作,比如i次删除变成word2(长度为0
for (let i = 1; i <= word1.length; i++) {
dp[i][0] = i;
}
//初始 化数组,word1最少需要j次操作,比如j次插入变成word2(从0变成长度为j
for (let j = 1; j <= word2.length; j++) {
dp[0][j] = j;
}
for (let i = 1; i <= word1.length; i++) {
//循环word1和word2
for (let j = 1; j <= word2.length; j++) {
if (word1[i - 1] === word2[j - 1]) {
//如果word1[i-1] === word2[j-1],说明不用操作。
// 任何已经存在的字符,即便位置不同,都可以通过以后的操作,对应到正确位置上
dp[i][j] = dp[i - 1][j - 1];
} else {
//dp[i-1][j] + 1:对应删除
//dp[i][j-1] + 1:对应新增
//dp[i-1][j-1] + 1:对应替换操作
dp[i][j] = Math.min(
dp[i - 1][j] + 1,
dp[i][j - 1] + 1,
dp[i - 1][j - 1] + 1
);
}
}
}
return dp[word1.length][word2.length];
};
76.最小覆盖子串(滑动窗口)
预处理一个 map needType 计数,只要不为 0,窗口就不满足要求
双重循环 类似 003
var minWindow = function (s, t) {
let l = 0;
let r = 0;
const need = new Map();
for (let c of t) {
need.set(c, need.has(c) ? need.get(c) + 1 : 1);
}
let needType = need.size;
let res = "";
while (r < s.length) {
let c = s[r];
if (need.has(c)) {
need.set(c, need.get(c) - 1);
if (need.get(c) === 0) needType -= 1;
}
while (needType === 0) {
const newRes = s.substring(l, r + 1);
// !res,第一次要算上
if (!res || newRes.length < res.length) res = newRes;
const c2 = s[l];
if (need.has(c2)) {
need.set(c2, need.get(c2) + 1);
if (need.get(c2) === 1) needType += 1;
}
l += 1;
}
r += 1;
}
return res;
};
77.组合
给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合
/**
* @param {number} n
* @param {number} k
* @return {number[][]}
*/
var combine = function (n, k) {
const res = [];
// 1,2,3,4
const helper = (x, y, temp) => {
if (y === k) {
res.push(temp);
return;
}
for (let i = x; i <= n; i++) {
helper(i + 1, y + 1, [...temp, i]);
}
};
// k为
helper(1, 0, []);
return res;
};
78.子集
// temp,res,
// 递归函数(当前遍历到哪一位)
// 如果长度够,push temp的拷贝
// push当前位,当前位加1,递归
// 弹出当前位,
var subsets = function (nums) {
const t = [];
const ans = [];
const dfs = (cur) => {
if (cur === nums.length) {
ans.push(t.slice());
return;
}
t.push(nums[cur]);
dfs(cur + 1);
t.pop();
dfs(cur + 1);
};
dfs(0);
return ans;
};
// var subsets = function(nums) {
// const ans = [];
// const n = nums.length;
// for (let mask = 0; mask < (1 << n); ++mask) {
// const t = [];
// for (let i = 0; i < n; ++i) {
// mask的二进制右数第i位是否为1
// if (mask & (1 << i)) {
// t.push(nums[i]);
// }
// }
// ans.push(t);
// }
// return ans;
// };
79.单词搜索(dfs)
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
function exist(board, word) {
if (word.length === 0) return true;
if (board.length === 0) return false;
let rowRange = board.length;
let colRange = board[0].length;
const backtrack = (i, j, curInx) => {
// 剪枝:索引越界
if (i < 0 || j < 0 || i >= rowRange || j >= colRange) return false;
// 剪枝:当前元素 !== 指定字符
if (board[i][j] !== word[curInx]) return false;
// 结果:全部 匹配,返回 true
if (curInx === word.length - 1) return true;
board[i][j] = null; // 当前字母匹配后, 将当前位置置空,避免之后被重复往回找
// 向上下左右寻找下一个字母
const res =
backtrack(i + 1, j, curInx + 1) ||
backtrack(i - 1, j, curInx + 1) ||
backtrack(i, j + 1, curInx + 1) ||
backtrack(i, j - 1, curInx + 1);
// 回撤, 类似于Pop
board[i][j] = word[curInx];
return res;
};
for (let i = 0; i < rowRange; i++) {
for (let j = 0; j < colRange; j++) {
if (backtrack(i, j, 0)) return true;
}
}
return false;
}
82.删除排序链表中的重复元素 II
给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。
输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]
var deleteDuplicates = function (head) {
// 2个数字相同则去除2个数字,1个也不保留
// 0,1,1,1,2,3
if (!head) return head;
let dummy = new ListNode(0, head);
let cur = dummy;
while (cur.next && cur.next.next) {
if (cur.next.val == cur.next.next.val) {
let x = cur.next.next;
while (x.next && cur.next.val == x.next.val) {
x = x.next;
}
cur.next = x.next;
} else {
cur = cur.next;
}
}
return dummy.next;
};
83.删除排序链表中的重复元素
输入:head = [1,1,2] 输出:[1,2]
var deleteDuplicates = function (head) {
if (!head) {
return head;
}
let cur = head;
while (cur.next) {
if (cur.val === cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
};
88.合并两个有序数组(三指针)
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列。
// nums1上原地修改,三指针m尾n尾总尾,外循环n尾还有,如果m读完(<0)则n全拷continue,否则比较行事,跳出循环m已经在正确位置直接退出
// 原理是提前弄了m+n-1逆向不可能会修改不该修改的
// 而且某一方遍历完了,剩下的一定是给另一方的
const merge = function (nums1, m, nums2, n) {
let tailm = m - 1;
let tailn = n - 1;
let tail = m + n - 1;
while (tailn >= 0) {
if (tailm < 0) {
nums1[tail--] = nums2[tailn--];
continue;
}
nums1[tail--] =
nums1[tailm] > nums2[tailn] ? nums1[tailm--] : nums2[tailn--];
}
};
92.反转链表 II
给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right
。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表
const reverseLinkedList = (head) => {
let pre = null;
let cur = head;
while (cur) {
const next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
};
var reverseBetween = function (head, left, right) {
const dummyNode = new ListNode(-1);
dummyNode.next = head; //虚拟头节点
let pre = dummyNode;
for (let i = 0; i < left - 1; i++) {
//pre遍历到left的前一个节点
pre = pre.next;
}
let rightNode = pre;
for (let i = 0; i < right - left + 1; i++) {
//rightNode遍历到right的位置
rightNode = rightNode.next;
}
let leftNode = pre.next; //保存leftNode
let curr = rightNode.next; //保存rightNode.next
//切断left到right的子链
pre.next = null;
rightNode.next = null;
//206题的逻辑 反转left到right的子链
reverseLinkedList(leftNode);
// 重新连接开头
pre.next = rightNode;
leftNode.next = curr;
return dummyNode.next;
};
93.复原 IP 地址(dfs)
/**
* @param {string} s
* @return {string[]}
*/
const restoreIpAddresses = (s) => {
const res = [];
// 复原从start开始的子串,start表示当前在字符串的哪一位
// subRes里收集了[111],[255],[255],[0]
const dfs = (subRes, start) => {
if (subRes.length === 4) {
// 1.片段满4段
res.push(subRes.join(".")); // 拼成字符串,加入解集
return;
}
for (let len = 1; len <= 3; len++) {
// 枚举出选择,三种切割长度; 这里因为如果不满足,下一个肯定也不满足,所以用return就行
// 不需要continue
if (start + len - 1 >= s.length) return; // 3.加上要切的长度就越界,不能切这个长度
if (len != 1 && s[start] === "0") return; // 4.不能切出'0x'、'0xx'
const str = s.substring(start, start + len); // 5.当前选择切出的片段
if (+str > 255) return; // 不能超过255
subRes.push(str); // 作出选择,将片段加入subRes
dfs(subRes, start + len); // *基于当前选择,继续选择,注意更新指针
subRes.pop(); //** */ 上面一句的递归分支结束,撤销最后的选择,进入下一轮迭代,考察下一个切割长度,因为会回退,所以只需要维护一个数组就行,不重不漏
}
};
dfs([], 0); // dfs入口
return res;
};
94.二叉树的中序遍历(双循环,栈)
/**
* 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[]}
*/
// 递归法递归函数(root),如果!root 剪,递归(root.left) res.push(root.val) 递归(root.right)
// 启动
// 迭代法,特殊!root,外循环(root||stk.length)
// 内循环root,栈入root,root=root.left
// 跳出循环,从stk弹出一个node,res里push结果,root=node.right
const inorderTraversal = function (root) {
const res = [];
const stk = [];
while (root || stk.length) {
while (root) {
stk.push(root);
root = root.left;
}
let node = stk.pop();
res.push(node.val);
root = node.right;
}
return res;
};
98.验证二叉搜索树
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左子树 只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。
const isValidBST = (root) => {
return helper(root, -Infinity, Infinity);
};
const helper = (root, left, right) => {
//最底层条件
if (!root) return true;
// 一般条件
if (root.val <= left || root.val >= right) return false;
// 递归化条件
return (
// 注意right变成了root.val,表示上界;下界用不上!
helper(root.left, left, root.val) && helper(root.right, root.val, right)
);
};