1. 两数之和
方法1 「暴力枚举」
直接嵌套两个for循环来解决：
var twoSum = function (nums, target) {for (let i = 0; i < nums.length - 1; i++) {for (let j = i + 1; j < nums.length; j++) {const item = nums[j];if (target === item + nums[i]) {return [i, j];}}}};
let j = i + 1- 注意，j 要从 i + 1 的位置开始遍历。
方法2 「静态哈希表」
var twoSum = function (nums, target) {
// 静态哈希表
const map = new Map();
// 初始化哈希表
for (let i = 0; i < nums.length; i++) {
map.set(nums[i], i);
}
// 查询哈希表
for (let i = 0; i < nums.length; i++) {
const anotherNum = target - nums[i];
if (map.has(anotherNum) && map.get(anotherNum) !== i) {
return [i, map.get(anotherNum)];
}
}
};
【思路】
- 初始化一个哈希表。
- 查询哈希表。
【思考：若数组中出现重复的成员，是否会影响结果？】
如果初始化过程中，重复出现的成员 nums[i]，映射表中只会记录一组映射关系，{nums[i], 最大下标}。
由于题目描述中说：每种输入仅对应一个解。由此可得知，如果数组 nums 中某个成员 a 重复出现，那么，该数组中必然不存在成员 b，实现 b + a === target。即：数组中重复出现的成员，并不会影响输出。
【查询哈希表的步骤】
- 遍历 nums
- 获取到符合条件的差值
anotherNum 到哈希表中查询该差值
- 由于题目描述中说：数组中同一个元素在答案里不能重复出现。所以还得确保当前遍历到的成员和映射表中记录的成员，它们在数组nums中，并不是同一个位置上的。
map.get(anotherNum) !== i
- 由于题目描述中说：数组中同一个元素在答案里不能重复出现。所以还得确保当前遍历到的成员和映射表中记录的成员，它们在数组nums中，并不是同一个位置上的。
返回结果
- 可以按任意顺序返回。
方法3 「动态哈希表」
var twoSum = function (nums, target) {
// 动态哈希表
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const item = nums[i];
const anotherNum = target - item;
if (map.has(anotherNum)) { // 查询
return [i, map.get(anotherNum)];
}
map.set(item, i); // 存入哈希表
}
};
| 动态哈希表 | 静态哈希表 |
|---|---|
| 创建和查询哈希表同时进行。 | 先创建好哈希表，再做查询。 |
【对比】
- 先查后存
- 先存后查
就一种特殊情况来说明它们之间的区别，比如示例3。
输入：nums = [3,3], target = 6
输出：[0,1]
实际输出：undefined
如果是先存后查，即：采用下面这种写法，那么会出问题，最终的返回结果会是 undefined。
var twoSum = function (nums, target) {
// 动态哈希表
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const item = nums[i];
map.set(item, i); // 存入哈希表
const anotherNum = target - item;
if (map.has(anotherNum) && map.get(anotherNum) !== i) { // 查询
return [i, map.get(anotherNum)];
}
}
};
由于哈希表中，对于重复的 key 值，后面的会覆盖前面的，所以如果是这种特殊情况的话，那么永远不会执行 return 语句。
但是，如果是先查后存的话，那么就会在覆盖先前存入的值之前，判断那个值是否满足要求。
输入：nums = [3,4,3], target = 6
输出：[0,2]
实际输出：undefined
再比如说这样的示例，得到的结果依旧是 undefined，因为第一次存入的 3 => 0 还没被查询，就被 3 => 2 给覆盖了。
测试
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSum([3, 2, 4], 6)); // [1, 2]
console.log(twoSum([3, 3], 6)); // [0, 1]
小结
测试结果：
- 内存消耗：1 < 2 ≈ 3
- 执行用时：2 ≈ 3 < 1
3. 无重复字符的最长子串
1. 暴力解法
var lengthOfLongestSubstring = function (s) {
let set = new Set(), // 准备一个 set
maxLen = 0, // 最大长度
curLen = 0; // 当前长度
const len = s.length;
for (let i = 0; i < len; i++) {
// 每一个成员都过一遍，直到重复成员出现，统计长度
let j = i;
while (j < len && !set.has(s[j])) {
set.add(s[j]);
curLen++;
j++;
}
maxLen = maxLen > curLen ? maxLen : curLen; // 记录最大值
// 重置
curLen = 0;
set.clear();
}
return maxLen;
};
解题思路：
示例：”pwwkew”
依次遍历每一个字符，记录下从当前字符开始，直到出现重复字符时的长度值。
- 第1个遍历到 p，得到的结果是
pw长度为 2 - 第2个遍历到 w，得到的结果是
w长度为 1 - 3 ==> w ==>
wke==> 3 - 4 ==> k ==>
kew==> 3 - 5 ==> e ==>
ew==> 2 - 6 ==> w ==>
w==> 1
这是最先想到的解题方法，原理很简单，就是遍历字符串 s 中的每一个字符，获取到 cur_len，cur_len 是指从当前字符所在的位置开始计算，直到出现重复字符时停止。每次遍历结束都将当前记录的长度值和历史最大长度 max_len 进行比较，把最大值保存到 max_len 中。最后返回 max_len 即可。
示例：s = "abcabcbb"
- 遍历第
1个字符a得到abc，所以cur_len为3，此时max_len所记录的历史最大值为3 2 ==> b ==> bca ==> cur_len: 3 ==> max_len: 33 ==> c ==> cab ==> cur_len: 3 ==> max_len: 34 ==> a ==> abc ==> cur_len: 3 ==> max_len: 35 ==> b ==> bc ==> cur_len: 2 ==> max_len: 36 ==> c ==> cb ==> cur_len: 2 ==> max_len: 37 ==> b ==> b ==> cur_len: 1 ==> max_len: 38 ==> b ==> b ==> cur_len: 1 ==> max_len: 3- 遍历结束。
return max_len;
7. 整数反转
方法1 「while 循环」
var reverse = function (x) {
const min = -Math.pow(2, 31);
const max = Math.pow(2, 31) - 1;
let result = 0;
while (x !== 0) {
result = result * 10 + x % 10;
x = parseInt(x / 10);
}
if (result < min || result > max) {
return 0;
} else {
return result;
}
};
幂：
Math.pow(2, 31)2 ** 31
整除：
parseInt(x / 10)~~(x / 10)
方法2 「转为字符串求解」
var reverse = function (x) {
let str = '';
if (x < 0) { // x 为负数
str = '-' + x.toString().substring(1).split('').reverse().join('');
} else { // x 为正数
str = x.toString().split('').reverse().join('');
}
const result = parseInt(str);
const max = (2 ** 31) - 1;
const min = -(2 ** 31);
if (result < min || result > max) {
return 0;
} else {
return result;
}
};
去掉字符串的首字符：
字符串.substring(1)
字符串 <=> 数组
字符串.split(指定字符)数组.join(指定字符)
测试
console.log(reverse(123)); // 321
console.log(reverse(-123)); // -321
console.log(reverse(120)); // 21
console.log(reverse(0)); // 0
小结
溢出的判断，还有更高效的方法，还可以进一步优化。
9. 回文数
方法1 「转为字符串来比较」
var isPalindrome = function (x) {
if (x < 0) {
return false;
}
const result = x.toString().split('').reverse().join(''); // 经过反转后的结果
return result === x.toString();
};
方法2 「先反转再比较」
var isPalindrome = function (x) {
if (x < 0) {
return false;
}
const originalNum = x; // 原始值
let resultNum = 0; // 经过反转后的结果
while(x !== 0) {
resultNum = resultNum * 10 + x % 10;
x = parseInt(x / 10);
}
return originalNum === resultNum;
};
方法3 「二分对比」
var isPalindrome = function (x) {
if (x < 0) {
return false;
}
const arr = x.toString().split(''); // 转化为数组
const len = arr.length;
let endIndex = len - 1; // 数组的最后一个下标
for (let i = 0; i <= len / 2; i++) {
if (arr[i] !== arr[endIndex - i]) {
return false;
}
}
return true;
};
小结
和 整数反转 那题类似
13. 罗马数字转整数
方法1 「暴力哈希」
准备好转换库，直接从转换库中匹配。将正常情况和特殊情况都存储起来。
- 使用对象来存储
const map = {
I: 1,
V: 5,
X: 10,
L: 50,
C: 100,
D: 500,
M: 1000,
}
// 特殊值
const mapCombine = {
IV: 4,
IX: 9,
XL: 40,
XC: 90,
CD: 400,
CM: 900
}
- 使用map来存储
const map = new Map();
map.set('I', 1);
map.set('V', 5);
map.set('X', 10);
map.set('L', 50);
map.set('C', 100);
map.set('D', 500);
map.set('M', 1000);
// 特殊值
map.set('IV', 4);
map.set('IX', 9);
map.set('XL', 40);
map.set('XC', 90);
map.set('CD', 400);
map.set('CM', 900);
var romanToInt = function (s) {
const map = new Map();
map.set('I', 1);
map.set('V', 5);
map.set('X', 10);
map.set('L', 50);
map.set('C', 100);
map.set('D', 500);
map.set('M', 1000);
// 特殊值
map.set('IV', 4);
map.set('IX', 9);
map.set('XL', 40);
map.set('XC', 90);
map.set('CD', 400);
map.set('CM', 900);
let result = 0;
for (let i = 0; i < s.length; i++) {
// 先判断特殊情况
if (map.has(`${s[i]}${s[i + 1]}`)) {
result += map.get(`${s[i]}${s[i + 1]}`);
i++;
} else {
result += map.get(s[i]);
}
}
return result;
};
方法2 「哈希表」
只要存储正常情况即可。
规律：
- 正常情况，连续字符中，左侧的字符所表示的数字是比右侧的字符所表示的数字大的（或相等），此时只要以此识别，累加即可；
- 特殊情况，连续字符中，左侧的字符所表示的数字比右侧小，那么左侧的字符表示的是一个负数，即：在累加时，需要对左侧的字符取反，再相加；
var romanToInt = function (s) {
const map = new Map();
map.set('I', 1);
map.set('V', 5);
map.set('X', 10);
map.set('L', 50);
map.set('C', 100);
map.set('D', 500);
map.set('M', 1000);
let result = 0;
for (let i = 0; i < s.length; i++) {
if (map.get(s[i]) < map.get(s[i + 1])) { // 特殊情况
result += (map.get(s[i + 1]) - map.get(s[i]));
i++;
} else { // 正常情况
result += map.get(s[i]);
}
}
return result;
};
测试
console.log(romanToInt("III")); // 3
console.log(romanToInt("IV")); // 4
console.log(romanToInt("IX")); // 9
console.log(romanToInt("LVIII")); // 58
console.log(romanToInt("MCMXCIV")); // 1994
小结
这是一道字符串转换问题，对于这类问题，解题的关键在于：转换规则。
14. 最长公共前缀
方法1 「纵向扫描法」
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function (strs) {
// 1. 先判断传递的 strs 具有多少项（两种特殊情况）
if (strs.length === 0) {
return "";
} else if (strs.length === 1) {
return strs[0];
}
// 2. 获取到字符串数组 strs 中最短的字符串
let minStr = strs[0];
for (let i = 1; i < strs.length; i++) {
const str = strs[i];
if (str.length < minStr.length) {
minStr = str;
}
}
let result = '';
// 3. 获取最长公共前缀
for (let i = 0; i < minStr.length; i++) { // 遍历字符串的第n位
for (let j = 0; j < strs.length; j++) { // 遍历字符串数组的每一项
const str = strs[j];
if (str[i] !== minStr[i]) {
return result;
} else {
if (j !== strs.length - 1) {
continue;
}
result += str[i];
}
}
}
return result;
};
console.log(longestCommonPrefix(["flower", "flow", "flight"]));
console.log(longestCommonPrefix(["dog", "racecar", "car"]));
先判断传递的 strs 具有多少项（两种特殊情况）
如果strs的长度为0
- 直接返回空字符串 “” 即可
如果strs的长度为1
- 直接将该项返回即可
获取到字符串数组 strs 中最短的字符串
- 防止后续遍历的时候越界
获取最长公共前缀
- 两层for循环，依次比较公共前缀，直到出现第一个不满足或者遍历到最短字符串的最后一位，将结果返回即可。
时间复杂度：O(S)，S为所有字符串的综合，空间复杂度O(1)。
方法2 「横向扫描」
可能会用到的 api：
-
- The
substring()method returns the part of thestringbetween the start and end indexes, or to the end of the string. - substring() 方法返回起始索引和结束索引之间的字符串部分，或返回到字符串末尾的部分。
- The
-
- The
indexOf()method returns the index within the calling String object of the first occurrence of the specified value, starting the search atfromIndex. Returns-1if the value is not found. - indexOf() 方法返回调用 String 对象中第一次出现指定值的索引，从 fromIndex 开始搜索。如果未找到该值，则返回 -1。
- The
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function (strs) {
let str = strs[0];
for (let i = 1; i < strs.length; i++) {
while(strs[i].indexOf(str) !== 0){
str = str.substring(0, str.length - 1); // 可能是因为 str 太长了，去掉结尾的字符再试试
if(str === "") return str;
continue;
}
// console.log(str);
}
return str;
};
console.log(longestCommonPrefix(["flower", "flow", "flight"]));
console.log(longestCommonPrefix(["dog", "racecar", "car"]));
注解：
strs[i].indexOf(str) === 0要求strs[i]中存在子串str，并且是从strs[i]的第一个字符开始匹配的。- while循环执行完第一轮，意味着已确定 strs 中的第一项和第二项的最长公共前缀
flow； - while循环执行完第二轮，意味着已确定前一次 while循环得到的结果
flow与 strs 中的第三项的最长公共前缀fl； - 。。。以此类推，直到strs遍历结束；
基本操作：
- 去掉字符串的最后一个字符：
str = str.substring(0, str.length - 1);
测试
console.log(longestCommonPrefix(["flower", "flow", "flight"])); // "fl"
console.log(longestCommonPrefix(["dog", "racecar", "car"])); // ""
小结
null
19. 删除链表的倒数第 N 个结点
1. 暴力解法
var removeNthFromEnd = function(head, n) {
let root = cur1 = cur2 = new ListNode(-1, head);
// cur1 指针，负责探路，获取链表的总长度
let length = 0; // 当前链表的总长度
while (cur1.next) {
cur1 = cur1.next;
length ++;
}
// cur2 指针，负责删除指定节点
let start = length - n; // 从哪个节点开始截
while (start--) {
cur2 = cur2.next
}
cur2.next = cur2.next.next; // 删除第 start 个节点
return root.next; // 返回表头
};
解题思路：
核心步骤共两步
- 获取链表的总长度
- 删除指定成员
在获取到链表的总长度之后，结合已知的需要被删除的倒数第 n 个成员，就可以获取到需要被删除的那个成员是第几个成员；然后再正向的遍历链表，找到指定成员，并将其删除即可。
20. 有效的括号
方法1 「栈」
需要用到的数据结构：栈。
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function (s) {
const len = s.length;
if (len % 2 !== 0) {
return false;
}
const stack = [];
for (let i = 0; i < len; i++) {
const str = s[i];
if (str === '(') {
stack.push(')');
} else if (str === '[') {
stack.push(']');
} else if (str === '{') {
stack.push('}');
} else {
if (str !== stack.pop()) return false;
}
}
return stack.length === 0;
};
先判断传入的字符数量
- 单数
return false; - 双数 继续后续操作
- 单数
遍历传入的字符串，判断当前字符
如果是左括号
- 令对应的右括号入栈，push
如果是右括号
如果此时栈不为空，那么，pop 出栈，比较从栈中取出的字符是否和当前的右括号相同
- 相同 -> 继续遍历
- 不同 ->
return false;
- 如果此时栈为空，那么直接
return false;
遍历结束
- 如果栈中还存在成员，那么直接
return false; - 如果栈为空，说明在遍历过程中，配对过程没有出现问题。直接
return true;即可。
- 如果栈中还存在成员，那么直接
测试
console.log(isValid("()")); // true
console.log(isValid("()[]{}")); // true
console.log(isValid("(]")); // false
console.log(isValid("([)]")); // false
console.log(isValid("{[]}")); // true
21. 合并两个有序链表
方法1 「暴力循环」
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var mergeTwoLists = function (l1, l2) {
const newList = new ListNode(-1);
let cur = newList;
while(l1 && l2){
if(l1.val < l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 ? l1 : l2;
return newList.next;
};
- 变量 newList 始终指向新链表的表头的前一个节点；
- 变量 cur 不断地偏移，辅助新链表的生成；
方法2 「递归」
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var mergeTwoLists = function (l1, l2) {
if (l1 === null) {
return l2;
}
if (l2 === null) {
return l1;
}
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
};
会破坏传入的两个链表 l1 和 l2。
测试
function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
遍历链表：
function traverseLinkedList(root) {
let temp = root;
while(true) {
if(temp !== null){
console.log(temp.val);
}else{
break;
}
temp = temp.next;
}
}
官方提供的三个示例：
function ListNode(val, next) {
this.val = (val === undefined ? 0 : val);
this.next = (next === undefined ? null : next);
}
function traverseLinkedList(root) {
let temp = root;
while (true) {
if (temp !== null) {
console.log(temp.val);
} else {
break;
}
temp = temp.next;
}
}
// 示例1
const l1_node1 = new ListNode(1);
const l1_node2 = new ListNode(2);
const l1_node4 = new ListNode(4);
l1_node1.next = l1_node2;
l1_node2.next = l1_node4;
const l2_node1 = new ListNode(1);
const l2_node3 = new ListNode(3);
const l2_node4 = new ListNode(4);
l2_node1.next = l2_node3;
l2_node3.next = l2_node4;
const newList1 = mergeTwoLists(l1_node1, l2_node1);
traverseLinkedList(newList1); // 1 1 2 3 4 4
// 示例2
const newList2 = mergeTwoLists(new ListNode(null), new ListNode(null));
traverseLinkedList(newList2); // null null
// 示例3
const newList3 = mergeTwoLists(new ListNode(null), new ListNode(0));
traverseLinkedList(newList3); // 0 null
22. 括号生成
方法1 「回溯算法」
var generateParenthesis = function (n) {
const ans = [];
const dfs = (lRemain, rRemain, str) => {
if (str.length === n * 2) {
ans.push(str);
return;
}
if (lRemain > 0) dfs(lRemain - 1, rRemain, str + '(');
if (rRemain > lRemain) dfs(lRemain, rRemain - 1, str + ')');
}
dfs(n, n, "");
return ans;
};
注解
参考题解：「手画图解」从 22. 括号生成 看回溯算法的三个要点
该图片来自参考题解，图片中标注的顺序，是 dfs 依次入栈的次序。
- 已选：
str - 可选：由
lRemain和rRemain决定 - 结束：
str.length === n * 2
回溯的套路中，难点通常在于确定「可选」是什么，「已选」、「结束」往往都很容易明确。
27. 移除元素
方法1：双指针 - 1
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function (nums, val) {
let len = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] === val) {
// 找后续不为 val 的成员与之交换位置
for (let j = i + 1; j < nums.length; j++) {
if (nums[j] !== val) {
nums[i] = nums[j];
nums[j] = val;
len++;
break;
}
}
} else {
len++;
}
};
return len;
};
【解题思路】
外层循环找 val
- 若当前项不等于 val，说明该项不需要移除，那么，满足条件的成员加 1，len++；
若当前项等于 val，那么开启内层循环，从当前项的下一项开始找第一个不为 val 的成员，找到后将它们位置交换，同时，满足条件的成员加 1，len++；
- 内层循环只要找到第一个不为 val 的成员即可，之后直接 break; 跳出内层循环；
【注意点】
内层循环始终是从外层循环的当前项的下一项开始查找，一旦找到满足条件的成员，意味着数组长度需要加 1。
并非只有在发生交换时，数组长度才需要加 1；若外层循环遍历到的当前项本身就不等于 val，那么也意味着该项是不需要删除的，此时，数组的长度也需要加 1。
方法2：双指针 - 2
var removeElement = function (nums, val) {
if (nums.length === 0) return 0;
let l = 0,
r = nums.length - 1;
while (l < r) {
while (nums[l] !== val && l < r) {
l++;
}
while (nums[r] === val && l < r) {
r--;
}
let temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
}
return nums[l] === val ? l : l + 1;
};
【解题思路】
爱学习的饲养员 Leetcode力扣 1-300题视频讲解合集｜手画图解版+代码【持续更新ing】
【踩坑】
- 内层两个 while 循环的限制条件
l < r不能少，防止两指针相撞之后继续运动，导致相撞点两侧的数据出现问题。 由于循环结束分两种情况，所以最终返回的新数组长度也分两种情况：
左指针撞向右指针；
- 直接返回 l
右指针撞向左指针；
- 返回 l + 1
方法3：调用系统函数
调用原生 api，splice。（不符合题目要求）
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function (nums, val) {
if (!nums.length) return 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] === val) {
nums.splice(i, 1);
i--;
}
}
return nums.length;
};
【解题思路】
很简单，遍历数组，一旦找到不满足条件的，直接将其从原数组中删除即可。
splice 这个 api，会改变原数组，所以，最后只要将修改后的原数组 nums 返回即可。
测试示例
const nums = [3, 2, 2, 3];
const val = 3;
const len = removeElement(nums, val);
console.log(nums, len); // [2, 2, 3, 3] 2
const nums = [0, 1, 2, 2, 3, 0, 4, 2];
const val = 2;
const len = removeElement(nums, val);
console.log(nums, len); // [0, 1, 3, 0, 4, 2, 2, 2]
28. 实现 strStr()
调用原生 js 等价 api：indexOf
/**
* @param {string} haystack
* @param {string} needle
* @return {number}
*/
var strStr = function(haystack, needle) {
return haystack.indexOf(needle);
};
35. 搜索插入位置
方法1 「二分查找」
var searchInsert = function (nums, target) {
const len = nums.length;
// 特殊情况处理
if (target > nums[len - 1]) return len;
// 二分
let l = 0, r = len - 1, mid = (r - l >> 1) + l;
while (l < r) {
if (target === nums[mid]) return mid;
else if (target > nums[mid]) l = mid + 1;
else r = mid;
mid = (r - l >> 1) + l;
}
return mid;
};
描述
- 特殊情况
当 target 比 nums 中每一个成员都大时，返回 nums.length。由于在这种情况下，插入位置并不在 [L, R] 区间内，所以要单独处理。
- 二分
若不是特殊情况，那么进行二分查找，不断细分区间。细分区间的逻辑：
- 看拿目标值 target 与当前区间 [L, R] 的中间成员 nums[mid] 比较，若相等，则直接返回 mid 即可；
- 若目标值 target > nums[mid]，则插入位置不可能位于左区间，包括当前 mid 所在位置也不可能是插入位置，所以将 l 赋值为 mid + 1，舍弃掉左侧区间，将查找的区间进一步细分；
- 若目标值 target < nums[mid]，则插入位置不可能位于右区间，但是，当前 mid 所在的位置有可能是插入位置，所以将 r 赋值为 mid，舍弃掉右侧区间，将查找的区间进一步细分；
- 循环以上 3 步，直到循环结束「区间不能再细分了，即
l === r === mid」，此时区间所指的位置，就是要找的插入位置。
方法2 「暴力解法」
var searchInsert = function (nums, target) {
for (let i = 0; i < nums.length; i++) {
if (nums[i] >= target) return i;
}
return nums.length;
};
描述
直接用 704 题解的图，思路完全几乎是一样的。
类似例题
46. 全排列
方法1 「回溯」
var permute = function(nums) {
const ans = [];
const dfs = (path) => {
if (path.length === nums.length) {
ans.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (path.includes(nums[i])) continue;
path.push(nums[i]);
dfs(path);
path.pop();
}
}
dfs([]);
return ans;
};
53. 最大子序和
方法1 「暴力解法」
var maxSubArray = function(nums) {
const len = nums.length;
if(len === 1) return nums[0];
let ans = Math.min(...nums); // 有可能 nums 都是负数
for (let i = 0; i < len; i++) {
let count = 0;
for (let j = i; j < len; j++) {
count += nums[j];
ans = Math.max(count, ans);
}
}
return ans;
};
描述
思想很简单，就是两层循环，将所有可能的子数组都判断一遍，取最值。
Attention
回看提交记录时，发现当时是通过的，但是目前运行提示超时。
方法2 「动态规划」
var maxSubArray = function(nums) {
let sum = 0, ans = nums[0];
for (let i = 0; i < nums.length; i++) {
sum = Math.max(sum + nums[i], nums[i]);
ans = Math.max(ans, sum);
}
return ans;
};
概念
在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线．这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划方法。
描述
若一个连续子序列的最后一个元素，比这个序列的和还要大。这意味着，最大的连续子序列不可能包含前面部分，直接将其舍弃即可。
58. 最后一个单词的长度
split、filter
调用原生的api，split、filter
/**
* @param {string} s
* @return {number}
*/
var lengthOfLastWord = function(s) {
const strs = s.split(' ').filter(str => str !== '');
if(strs.length === 0) return 0;
return strs[strs.length - 1].length;
};
66. 加一
逆序循环
/**
* @param {number[]} digits
* @return {number[]}
*/
var plusOne = function (digits) {
const len = digits.length;
for (let i = len - 1; i >= 0; i--) {
digits[i]++;
digits[i] %= 10;
if (digits[i] !== 0) return digits;
}
const result = Array(len + 1).fill(0);
result[0] = 1;
return result;
};
74. 搜索二维矩阵
方法1 「flat」
var searchMatrix = function(matrix, target) {
return matrix.flat().includes(target);
};
注解
将二维数组转换为一维。
[0, 1, 2, [3, 4]].flat(); // => [0, 1, 2, 3, 4]
[0, 1, 2, [[[3, 4]]]].flat(2); // => [0, 1, 2, [3, 4]]
// flat() 参数默认值为 1
方法2 「循环二维数组」
var searchMatrix = function(matrix, target) {
const rows = matrix.length, cols = matrix[0].length;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
const item = matrix[r][c];
if (item === target) return true;
}
}
return false;
};
注解
两个 for 循环，暴力循环二维数组的每一项。
一旦发现与目标值 target 相等的项，则返回 true，表示在该二维数组 matrix 中找到了目标值。
若找完所有项都没找到与目标值相等的值，则返回 false，表明该二维数组 matrix 中不存在目标值。
方法3 「二分查找」
var searchMatrix = function(matrix, target) {
const rows = matrix.length,
cols = matrix[0].length;
let start = 0,
end = rows * cols - 1;
while (start <= end) {
const mid = start + ((end - start) >> 1),
r = parseInt(mid / cols),
c = mid % cols,
item = matrix[r][c];
if (item === target) return true;
else if (item < target) start = mid + 1;
else end = mid - 1;
}
return false;
};
注解
将二维数组视作一维数组来做，并且题目明确该二维数组是有序的。
类似题目
77. 组合
方法1 「回溯」
var combine = function(n, k) {
// 初始化选择列表
const nums = [];
for (let i = 1; i <= n; i++) {
nums.push(i);
}
const ans = [];
const backtracking = (path, startIndex) => {
// console.log('已选', path, '选择列表', nums.slice(startIndex));
if (path.length === k) {
ans.push(path.slice());
return;
}
for (let i = startIndex; i < nums.length; i++) {
path.push(nums[i]); // 做选择
// console.log('选择', nums[i]);
backtracking(path, i + 1);
path.pop(); // 撤销选择
// console.log('撤销', nums[i]);
}
}
backtracking([], 0);
return ans;
};
注解
下面是图解的流程，可结合打印结果来分析回溯的过程。
已选 [] 选择列表 [ 1, 2, 3, 4 ]
选择 1
已选 [ 1 ] 选择列表 [ 2, 3, 4 ]
选择 2
已选 [ 1, 2 ] 选择列表 [ 3, 4 ]
撤销 2
选择 3
已选 [ 1, 3 ] 选择列表 [ 4 ]
撤销 3
选择 4
已选 [ 1, 4 ] 选择列表 []
撤销 4
撤销 1
选择 2
已选 [ 2 ] 选择列表 [ 3, 4 ]
选择 3
已选 [ 2, 3 ] 选择列表 [ 4 ]
撤销 3
选择 4
已选 [ 2, 4 ] 选择列表 []
撤销 4
撤销 2
选择 3
已选 [ 3 ] 选择列表 [ 4 ]
选择 4
已选 [ 3, 4 ] 选择列表 []
撤销 4
撤销 3
选择 4
已选 [ 4 ] 选择列表 []
撤销 4
回溯的其他写法
var combine = function(n, k) {
const ans = [];
const backtracking = (path, startIndex, endIndex) => {
if (path.length === k) {
ans.push([...path]);
return;
}
for (let i = startIndex; i <= endIndex; i++) {
path.push(i); // 做选择
backtracking(path, i + 1, endIndex);
path.pop(); // 撤销选择
}
}
backtracking([], 1, n);
return ans;
};
// 由于 n 它是一个整数，选择列表就是 1~n，其实没有必要再去初始化一个选择列表。
var combine = function(n, k) {
const ans = [];
const backtracking = (path, startIndex, endIndex) => {
if (path.length + (endIndex - startIndex + 1) < k) return; // 剪枝优化
if (path.length === k) {
ans.push([...path]);
return;
}
for (let i = startIndex; i <= endIndex; i++) {
path.push(i); // 做选择
backtracking(path, i + 1, endIndex);
path.pop(); // 撤销选择
}
}
backtracking([], 1, n);
return ans;
};
// 剪枝优化，就是去掉没有必要遍历的分支。
// 在这个组合问题中，若已选项加可选项小于目标长度，那么就可以剪枝。
var combine = function(n, k) {
const ans = [];
const backtracking = (path, startIndex, endIndex) => {
if (path.length + (endIndex - startIndex + 1) < k) return;
if (path.length === k) {
ans.push([...path]);
return;
}
path.push(startIndex); // 选择
backtracking(path, startIndex + 1, endIndex);
path.pop(); // 撤销
backtracking(path, startIndex + 1, endIndex);
}
backtracking([], 1, n);
return ans;
};
// 结合上述的「循环」+「递归」来看，会发现每次撤销选择后，再次进入下次循环时，发生变化的仅有 startIndex，直接在撤销时，再次调用 backtracking 也同样能实现循环的效果。
var combine = function(n, k) {
const ans = [];
const backtracking = (path, startIndex, endIndex) => {
if (path.length + (endIndex - startIndex + 1) < k) return;
if (path.length === k) {
ans.push(path);
return;
}
backtracking([...path, startIndex], startIndex + 1, endIndex);
backtracking([...path], startIndex + 1, endIndex);
}
backtracking([], 1, n);
return ans;
};
// 写法上还可以简化为上面这种形式，将「选择」「撤销」操作合并到递归函数的参数中。
// 若采用上面这种写法，那么我们在记录结果 ans.push(path) 时，就不用再去 path.slice() 拷贝 path 了，因为每次传入的 path 都是一个全新的 path，和之前的 path 没有关系。
78. 子集
方法1 - 循环遍历
var subsets = function(nums) {
let ans = [[]];
for(let i = 0; i < nums.length; i++) {
const temps = [];
for(let k = 0; k < ans.length; k++) {
temps.push(ans[k].slice());
}
// const temps = [...ans]; // 由于 js 中引用类型的值在赋值时，赋的值是地址，所以这么写不行。
for(let j = 0; j < temps.length; j++) {
temps[j].push(nums[i]);
}
ans = [...ans, ...temps];
}
return ans;
};
方法2 - 回溯
var subsets = function(nums) {
const t = [];
const ans = [];
const dfs = (deep) => {
if (deep === nums.length) {
// console.log(t);
ans.push([...t]);
return;
}
t.push(nums[deep]);
dfs(deep + 1);
t.pop();
dfs(deep + 1);
}
dfs(0);
return ans;
};
注解
对于当前值，只有两种选择：「选」 | 「不选」。所以，如果 nums 的长度为 3，那么结果有 2^3，也就是 8 个。
绿线：选；红线：不选；
- 第一个 dfs 走绿线；
- 第二个 dfs 走红线；
- 回溯：撤销选择；
- 结束条件：到底层，即 deep 等于 nums.length，此时记录结果；
套路
回溯算法需要关注的核心有 3 个点：
- 路径：已做的选择；
t - 选择列表：可选项；
nums[deep] - 结束条件：到底层，不用继续做选择；
deep === nums.length
回溯的意思就是指撤销我们做的选择，让我们重新选。
详细内容，见文章：知乎 回溯算法套路详解。
若有收获，就点个赞吧
0 人点赞
