Jacky's blog
wangjiasheng
2020-12-23
目录

基础算法篇

# 1.两数之和 (opens new window)

题解：

  • nums = [2, 7, 11, 15], target = 9
    1

  • 可以发现，2与7是一对，可以先将2存入key中，当循环到7时，找字典中是否存在7的对子【2】即可一遍循环就可以完成，否则按照传统两层for循环。

  • 核心：从2找7难，从7找2可通过字典实现

伪代码：

dict = new map
for(一层数组遍历){
	从7找2，所以先保存各个位置上的补数(7的补数是2)
    if(补数是否存在字典中){
       	存在：找到，直接return
    }else{
        不存在，将当前数存入字典
    }
}
1
2
3
4
5
6
7
8
9
点击查看

参考代码：

var twoSum = function(nums, target) {
    const map = new Map();
    for( let i=0;i<nums.length;i++){
        const complement = target - nums[i];
        if(map.has(complement)){
            return [map.get(complement),i]
        }else{
            map.set(nums[i], i)
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11

两层嵌套：

var twoSum = function(nums, target) {
    const result = [];
    for(let i=0;i<nums.length-1;i++){
        var end = i + 1;
        while(end<nums.length){
            console.log(nums[i] + nums[end])
            if(target == nums[i] + nums[end]){
                result.push(i,end);
                return  result;
            }
            end++;
        }
    }
    return []
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 20.有效括号 (opens new window)

知识点：堆栈

伪代码：

1. 将'{''}','['']','{''}'成对写入字典
2. for(循环字符串组，如"([)]")
      if(如果是'['，则压入']',其余同理){}
	  else{
       	  if(错误条件1 ){return false}
      }
	if( 错误条件2 ){ return false}
	错误都被排除完了，所以最后直接 return true

3. return false 的条件
	1. 首先弹出的字符一定要是先弹出的字符串，否则则错误（这个可以在循环内判断）
    2. 结束后一定是stack内需要为空（这个必须循环结束后判断）
1
2
3
4
5
6
7
8
9
10
11
12

参考代码：

点击查看 
var isValid = function(s) {
    let charMap = new Map();
    charMap.set('{','}');
    charMap.set('(',')');
    charMap.set('[',']');

    const stack = [];
    for(let i=0;i<s.length;i++){
        if(charMap.has(s[i])){
            stack.push(charMap.get(s[i]))
        }else{
            if(s[i] !== stack.pop()){
                return false;
            }
        }
    }

    if(stack.length !=0){
        return false;
    }
    return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 49.字母异位词分组 (opens new window)

示例：

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
1
2
3
4
5
6
7

题解1：

  • 使用Hash矩阵来表示str

    只要将矩阵中的字符串表示为hash矩阵，将相同hash矩阵输出即可。

题解2：

  • 使用排序后的str作为字典的key

    str.split("").sort().join("");

伪代码：

for( const str of strs){
    const map = new Map;
    for(循环读取字母){
        //创建一个新的空矩阵，用于存26个字母: charasters = Array(26).fill(0);
        1. 将字母转坏为ascii码，-97后可获得对应的索引
        2. 将charasters对应位置上++1
    }
    // 将charasters数组合并为str字符串===>.join(",");
    // 下一步，填充字典，key=charasters，val=str
    if(字典中不存在str){
        将当前str压入字典
    }else{
        存在，先get(key)，再添加【相同key的添加方式】
    }
}

const result = [];
for(循环读取map中的【key-value结构】){
    result.push(【key-value结构】[1]);
}
return result;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
点击查看

参考代码

var groupAnagrams = function(strs) {
    
    const map = new Map;
    // 解法2：自定义一个hash矩阵来表示key
    // 1. 生成hash矩阵
    for(const str of strs){
        // str = "abc"
        var charasters = Array(26).fill(0);
        for(let i=0;i<str.length;i++){
            // str[i] -- "a";
            const ascii = str[i].charCodeAt() - 97;
            charasters[ascii]++ ;
        }
        console.log(charasters);
        var key = charasters.join(",");
        console.log(key)
        if(map.has(key)){
            map.set(key, [...map.get(key),str]);
        }else{
            //  第一次添加
            map.set(key,[str])
        }
    }
    // 准备result数组
    const result = [];
    for (const array of map){
        // 取map中的值为map: array[0]--key array[1]--value
        result.push(array[1]);
    }
    return result;
};
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

排序写法

var groupAnagrams = function(strs) {
    // 准备result数组
    const map = new Map;
    // 解法1：排序
    for(let str of strs){
        // str.sort()作为key值
        var key = str.split("").sort().join("");
        // console.log(key);
        if(map.has(key)){
            // map.set(key, map.get(key).push(str));
            map.set(key, [...map.get(key),str]);
            // console.log(map.get(key));
        }else{
            map.set(key,[str]);
        }
    }
    const result = []
    for(const arry of map ){
        result.push(arry[1]);
    }
    return result;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 54.螺旋矩阵 (opens new window)

解题思路：

  • 核心：掌握for循环边界left,right,top,bottom，以及定义四个direction以及对应的操作。

参考答案：

点击查看 
var spiralOrder = function(matrix) {
    // 定义方向
    var direction = "right";
    // 定义边界
    var left = 0;
    var top = 0;
    var right = matrix[0].length - 1;
    var bottom = matrix.length - 1;
    // 定义结果
    const result = [];
    
//   [1, 2, 3, 4],
//   [5, 6, 7, 8],
//   [9,10,11,12]
    while(left<=right && top<=bottom){
        if(direction === "right"){
            for(let i=left;i<=right;i++){
                result.push(matrix[top][i]);
            }
            top++;
            direction = "down";
        }else if(direction === "down"){
            for(let i=top;i<=bottom;i++){
                result.push(matrix[i][right]);
            }
            right--; 
            direction = "left";
        }else if(direction === "left"){
            for(let i=right;i>=left;i--){
                result.push(matrix[bottom][i]);
            }
            bottom--;
            direction = "up";
        }else if(direction === "up"){
            for(let i=bottom;i>=top;i--){
                result.push(matrix[i][left]);
            }
            left++;
            direction = "right";
        }      
    }
    return result
};
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
37
38
39
40
41
42
43

# 56.合并区间 (opens new window)

题解：

  • 我认为这道题目记忆的方式：临时工作区 + result.push

伪代码：

// 1. 排序
intervals.sort(function(a,b){})
// 2. 建立临时工作区
let workspaceTemp = intervals[0];
// 3. 循环大列表，根据条件走步骤
for(let interval of intervals){
    if(当前区间的首<=临时工作区的末){
        则，合并
    }else{
        否则，
        1.需先将当前临时工作区直接压入result 
        2.再将当前interval放入临时工作区
    }
}

// 最后临时工作区可能还有内容，故
if(临时工作区不为空){
    如果还有值，则将剩余的一部分压入result中
}
// 最后，return 结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
点击查看

参考代码:

var merge = function(intervals) {
    // 极端情况判断：数据源的问题：空，或者只有一个数组
    if(intervals.length<2){
        return intervals;
    }
    // 首先是排序
    intervals.sort(function(a,b){
        return a[0] - b[0];
    });

    // 缓存一个工作区，将符合要求的压入 result
    let cur = intervals[0];
    let result = [];
    
    for(let interval of intervals){
        if( cur[1] >= interval[0] ){
            // 合并
            cur[1] = Math.max(cur[1],interval[1]);
        }else{
            // 压入result
            result.push(cur);
            cur = interval;
        }
    }
    // 最后清空工作区，因为最后没有比较对象了
    if(cur.length !== 0 ){
        result.push(cur);
    }
    return result
};
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

# 66.加一 (opens new window)

题解：

  • 这道题秒就妙在，可以不考虑进位变量carry

    具体操作：+1后直接return即可。

伪代码：

for(从后往前遍历数组digits){
    // +1 操作后直接return即可
    if(考虑当前位置是否为9){}
}
例外：考虑999的情况
// 合并矩阵的操作
Es6写法：1. result = [1,...digits]
传统写法：[1].concat(digits)
1
2
3
4
5
6
7
8
点击查看

参考代码：

var plusOne = function(digits) {
    // 核心：只有两种情况
    // 1. 只要当前位数不为9，就++1（不局限与个位，包括十位）
    // 2. 如果当前位数为9,则置零即可。
    for(let i=digits.length-1;i>=0;i--){
        if(digits[i] !== 9 ){
            digits[i]++;
            return digits;
        }else{
            digits[i] = 0;
        }
    }
    const result = [1,...digits];
    [1].concat(digits);
    return result;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 73.矩阵置零 (opens new window)

题解：

  • 难点在于要求不能新开矩阵，必须在当前给定的矩阵完成检测和置零操作。
  • 利用第1列和第1行作为标记位，则此时需要用额外的变量标记第1行和第1列是否存在0的情况。
点击查看

参考代码：

var setZeroes = function(matrix) {
    let firstRowHasZero = false;
    let firstColHasZero = false;
    // 标记第一列和第一行为0的情况
    for(let i = 0;i<matrix[0].length;i++){
        if(matrix[0][i] === 0){
            firstRowHasZero = true;
            break;
        }
    }
    for(let i = 0;i<matrix.length;i++){
        if(matrix[i][0] === 0){
            firstColHasZero = true;
            break;
        }
    }
    // 使用第1列和第1行记录矩阵其余位置含0的情况
    for(let row=1;row<matrix.length;row++){
        for(let col=1;col<matrix[0].length;col++){
            if(matrix[row][col] ===0){
                matrix[row][0] = 0;
                matrix[0][col] = 0;
            }        
        }
    }
    // 使用第1列和第1行的零去给矩阵其余位置置0
    for(let row=1;row<matrix.length;row++){
        if(matrix[row][0] === 0){
            for(let col=1;col<matrix[0].length;col++){
                matrix[row][col] = 0;
            }
        }
    }
    for(let col=1;col<matrix[0].length;col++){
        if(matrix[0][col] === 0){
            for(let row=1;row<matrix.length;row++){
                matrix[row][col] = 0;
            }
        }
    }
    // 最后解决第1列和第1行
    if(firstRowHasZero == true){
        for (let col=0;col<matrix[0].length;col++ ){
            matrix[0][col] = 0;
        }
    }
    if(firstColHasZero == true){
        for (let row=0;row<matrix.length;row++ ){
            matrix[row][0] = 0;
        }
    }
    return matrix
};
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

# 242.有效的字母异位词 (opens new window)

题解：

  • 知识点：子符串相关+哈希表+ new Map()

  • 核心：统计词频

    • 第一次存入Map中，词频+1
    • 第二此存入Map中，词频-1
点击查看

参考代码：

var isAnagram = function(s, t) {
    let map = new Map();
    for(let i=0;i<s.length;i++){
        if(!map.has(s[i])){
            map.set(s[i],1);
        }else{
            map.set(s[i],map.get(s[i])+1);
        }
    }
    for(let i=0;i<t.length;i++){
        if(!map.has(t[i])){
            map.set(t[i],1);
        }else{
            map.set(t[i],map.get(t[i])-1);
        }
    }
    for(const imap of map){
        if(imap[1] !== 0 ){
            return false
        }
    }
    return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 125.验证回文串 (opens new window)

题解：

  • 知识点：子符串相关

  • 只考虑字符和数字，且忽略字母的大小写【正则表达式处理】

伪代码：

//0.考虑只有一个字符的情况，因为下面采用双指针，默认子符串内存在两个字符
if(s.length<2){}

// 正则处理子符串
s = s.toLowerCase().repalce(/[]/g,'');

// 15.类似回文子串的写法
let left,right = ...;
while(left<right){
    if(只要不相等){return false}
    移动指针
}
否则，则return true
1
2
3
4
5
6
7
8
9
10
11
12
13
点击查看 
var isPalindrome = function(s) {
    if(s.length<2){
        return true;
    }
    s = s.toLowerCase().replace(/[\W_]/g,"");
    left = 0;
    right = s.length -1 ;
    while (left < right){
        if(s[left] !== s[right]){
            return false
        }
        left++;
        right--;       
    }
    return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 217.存在重复元素 (opens new window)

题解：

  • 知识点：new Set()
点击查看

参考代码：

var containsDuplicate = function(nums) {
    let map = new Set();
    for(let i=0;i<nums.length;i++){
        if(!map.has(nums[i])){
            map.add(nums[i]);
        }else{
            return true;
        }
    }
    return false;
};
1
2
3
4
5
6
7
8
9
10
11

# 219.存在重复元素 II (opens new window)

题解：

  • 知识点：new Map()的使用
点击查看

参考答案：

var containsNearbyDuplicate = function(nums, k) {
    const map = new Map();
    for(let i=0;i<nums.length;i++){
        if(map.has(nums[i]) && i - map.get(nums[i]) <= k){
            return true;
        }else{
            map.set(nums[i],i);
        }
    }
    return false;
};
1
2
3
4
5
6
7
8
9
10
11

# 349.两个数组的交集 (opens new window)

题解：

  • 数组检索：nums.inclueds(num)

  • set检索：set.has(num)

    根据 数组 转化为 set类型

    // 直接转化
let set = new Set(nums2);
// 间接转化
for(num of nums2){
    set.add(num);
}
    1
    2
    3
    4
    5
    6

    根据 set类型 转化回 数组

    Array.from(set);
    1
点击查看

参考代码：

  • set中搜索值 vs 数组中搜索值
var intersection = function(nums1, nums2) {
    let result = new Set();
    let set = new Set(nums2);
    for(num of nums1){
        // 数组中搜索值，复杂度是O(n)
        if(nums2.includes(num)){
            result.add(num);
        }     
        // set中搜索值，复杂度是O(1)
        if(set.has(num)){
            result.add(num);
        }
    }
    // 将set类型转化为[]
    return Array.from(result);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 200.岛屿数量 (opens new window)

题解：

  • 知识点：深度优先搜索、广度优先搜索
  • 深度优先：优先往下处理，碰头了就往回走
  • 广度搜索：本题中，只处理当前点的上下左右四个点

伪代码：

// 全局变量
let count = 0;
// 准备dfs函数，让岛屿沉没[置0]
function dfs(row,col){
    if(1.越界 2.当前字符为0){
        跳过；
    }else{
        否则：让当前位置的岛屿沉没[置0]
        深度优先：调用四次dfs函数
        dfs(向上);dfs(向左);dfs(向下);dfs(向右);    
    }
}

// 两层循环
for(行遍历){
    for(列遍历){
        if(当前位置 === “1”){
            直接 + 1；
            调用dfs(row,col)让其余的位置沉没
        }
    }
}
// 直接return count
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
点击查看

参考代码：

var numIslands = function(grid) {
let count = 0;
function dfs(row,col){
    // 越界 和 “0” 就无需置零，跳过即可
    if(row<0 || row>=grid.length || col<0 || col>=grid[0].length || grid[row][col] ==="0"){
        return ;
    }
    grid[row][col] = "0";
    dfs(row-1,col);
    dfs(row+1,col);
    dfs(row,col-1);
    dfs(row,col+1);

}
for(let row=0;row<grid.length;row++){
    for(let col=0;col<grid[0].length;col++){
        if(grid[row][col] === "1"){
            //第1次检索到"1"时，count++，再调用广度搜索使所有其余区域为0
            count++;
            dfs(row,col);
        }
    }
}
return count;
};
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

# 695.岛屿的最大面积 (opens new window)

题解：

  • 只需要在第200题的题上稍作修改
  • 稍作修改：在置零时，面积 +1
点击查看

参考代码：

var maxAreaOfIsland = function(grid) {

let result = 0;
function dfs(row,col){
    if(row<0 || row>=grid.length || col<0 || col>=grid[0].length || grid[row][col] === 0){
        return 0;
    }
    grid[row][col] = 0;
    let count = 1;
    count += dfs(row-1,col);
    count += dfs(row+1,col);
    count += dfs(row,col-1);
    count += dfs(row,col+1);
    return count;
}

for(let row=0;row<grid.length;row++){
    for(let col=0;col<grid[0].length;col++){
        if(grid[row][col] === 1){
            const count = dfs(row,col);
            result = Math.max(result, count)
        }
    }
}
return result;
};
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

# 836.矩形重叠 (opens new window)

题解：

  • 不能正向思考，逆向思考更简单。固定rec1不动，写rec2绝对不可能存在的位置。
点击查看

官方python[未通过]：

class Solution(object):
    def isRectangleOverlap(self, rec1, rec2):
        return not (rec1[2] <= rec2[0] or  # left
                    rec1[3] <= rec2[1] or  # bottom
                    rec1[0] >= rec2[2] or  # right
                    rec1[1] >= rec2[3])    # top
1
2
3
4
5
6
编辑 (opens new window)
#刷题
上次更新: 2022/04/06, 15:04:00
链表题

链表题→

最近更新
01
如何理解浏览器的 user agent 用户代理的含义?
11-05
02
浏览器事件循环机制
10-31
03
浏览器页面渲染机制【2023】
10-15
更多文章>
Theme by Vdoing | Copyright © 2020-2023