前端基础

整理一些基础的知识点及面试题，遇到感觉有兴趣的算法题也会记录下来。

一、js相关

1. 运行结果，原因

  运行结果为
  map() 函数创建一个新数组，其结果是该数组中的每个元素都调用一个提供的函数后返回的结果，第一个参数callball。

1
2
3
4
5
6
var arr = [1, 2, 3];
var ary = arr.map(function callback(currentValue, index, array) {
    return currentValue;
}, thisArg);
console.log(ary); // [1,2,3]
console.log(ary === arr); // false

  parseInt() 函数可解析一个字符串，并返回一个使字符串成为指定基数整数。
  parseInt(string, radix) 接收两个参数，第一个表示被处理的值，第二个表示为解析时的基数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
parseInt(0, 1) // NaN
parseInt(0, 2) // 0
parseInt(0, 36) // 0
parseInt(0, 37) // NaN
// 第二个参数有效范围为2至36，小于2或大于36的均无法处理，返回NaN。

parseInt(1, 2) // 1
parseInt(1, 3) // 1
parseInt(1, 4) // 1
parseInt(2, 2) // NaN
parseInt(3, 2) // NaN
parseInt(4, 2) // NaN
parseInt(9, 8) // NaN
parseInt(9, 9) // NaN
parseInt(10, 9) // 9
parseInt(11, 9) // 10
// parseInt(a,b)可以理解为将b进制中a转化为10进制的数字。

这样就不难理解[1, 2, 3].map(parseInt)

2. 0.1+0.2为什么不等于0.3

  对于计算机而言，四则运算时是二进制进行计算，最终结果展示为十进制。基本上所有的编程语言都会出现浮点数计算精度误差的情况，只不过其他语言内部对此有所处理，而js做为弱类型的语言，没有明确的浮点数数据类型，突出了问题情况。

产生问题的原因
　　JS中的数字是用IEEE 754 双精度 64 位浮点数来存储的，由64位组成，双精度浮点数小数位支持最多52位。运算过程如下

1
2
3
4
5
6
7
8
9
// 0.1 转换为二进制
0.0001 1001 1001 1001…(0011 无限循环) < br >
    // 0.2 转换为二进制
    0.0011 0011 0011 0011…(0011 无限循环) < br >

    // 0.1 + 0.2 
    0.0100110011001100110011001100110011001100110011001100(52 位)
// 结果转换为十进制
0.30000000000000004

解决方法
　　先将要计算的浮点数转为整数去计算，得到结果后再转为浮点数。

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
/**
 * 加法函数
 * 返回 num1 + num2 的精确计算结果
 */
function addition(num1, num2) {
    let len1 = num1.toString().split('.')[1].length;
    let len2 = num2.toString().split('.')[1].length;
    let int1 = Number(num1.toString().replace('.', ''));
    let int2 = Number(num2.toString().replace('.', ''));
    // 处理num1,num2 位数不一致情况
    if (len1 !== len2) {
        if (len1 > len2) {
            int2 = int2 * Math.pow(10, Math.abs(len1 - len2));
        } else {
            int1 = int1 * Math.pow(10, Math.abs(len1 - len2));
        }
    }
    let max = Math.max(len1, len2);
    let total = (int1 + int2) / Math.pow(10, max);
    return total;
}
// 减法同加法函数

/**
 * 乘法函数 
 * 返回 num1 * num2 的精确计算结果
 */
function multiplication(num1, num2) {
    let len = num1.toString().split(".")[1].length + num2.toString().split(".")[1].length;
    let int1 = Number(num1.toString().replace('.', ''));
    let int2 = Number(num2.toString().replace('.', ''));
    let total = (int1 * int2) / Math.pow(10, len);
    return total;
}

/**
 * 除法函数
 * 返回 num1 / num2 的精确计算结果
 */
function division(num1, num2) {
    let len = num2.toString().split(".")[1].length - num1.toString().split(".")[1].length;
    let int1 = Number(num1.toString().replace('.', ''));
    let int2 = Number(num2.toString().replace('.', ''));
    let total = (int1 / int2) * Math.pow(10, len);
    return total;
}

3. 3.toString()，3…toString()，3…toString()的结果

1
2
3
3. toString() // Uncaught SyntaxError: Invalid or unexpected token
3..toString() // '3'
3..toString() // Uncaught SyntaxError: Invalid or unexpected token

  为什么会这样呢，我个人觉着在处理3. 的时候，将3. 解析成了3.0，以上的可以转化成下边的写法。也就是3后边的. 并不是函数调用，而是将当作数值去处理，3. => 3.0，然后在调用toString()方法。3.001.toString()可以正常执行，是因为3.001已经是小数，后边的. 不会再将3.001做转换，而是当函数去调用方法，因此不会报错。

1
2
3
4
3. toString() => 3.0 toString()
3..toString() => 3.0.toString()
3...toString() => 3.0..toString()
// 只有3.0.toString()正常可以执行

4. 涉及async/await、Promise执行问题

  1. 代码运行后会输出什么结果？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
async function async1() {
    console.log('async1 start')
    await async2()
    console.log('async1 end')
}
async function async2() {
    console.log('async2')
}
console.log('script start')
setTimeout(function() {
    console.log('setTimeout')
}, 0)
async1();
new Promise(function(resolve) {
    console.log('promise1')
    resolve();
}).then(function() {
    console.log('promise2')
})
console.log('script end')

结果：

1
2
3
4
5
6
7
8
script start
async1 start
async2
promise1
script end
async1 end
promise2
setTimeout

5. forEach中async/await不生效问题

  1. 代码运行后会输出什么结果？
  2. 如果希望每隔1s输出一个结果，应该怎么改？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const list = [1, 2, 3];
const square = num => {
    return new Promise((resolve, reject) => {
        setTimeout(() => {
            resolve(num * num);
        }, 1000);
    });
}

function test() {
    // 修改这里的代码
    list.forEach(async x => {
        const res = await square(x);
        console.log(res);
    });
}
test()

  1. 执行结果：1，4，9
  2. 将改为循环即可实现每隔1s输出一个结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const list = [1, 2, 3]
const square = num => {
    return new Promise((resolve, reject) => {
        setTimeout(() => {
            resolve(num * num)
        }, 1000)
    })
}
async function test() {
    for (var i = 0; i < list.length; i++) {
        const res = await square(list[i])
        console.log(res)
    }
}
test()

  为什么在中使用，却没有达到每隔1s输出结果呢，其实是只是执行了下回调函数，不会去处理异步的情况。因此不会等待每次循环的结果，内部代码如下。

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
// Production steps of ECMA-262, Edition 5, 15.4.4.18
// Reference: http://es5.github.io/#x15.4.4.18
if (!Array.prototype.forEach) {
    Array.prototype.forEach = function(callback, thisArg) {
        var T, k;
        if (this == null) {
            throw new TypeError(' this is null or not defined');
        }
        // 1. Let O be the result of calling toObject() passing the
        // |this| value as the argument.
        var O = Object(this);
        // 2. Let lenValue be the result of calling the Get() internal
        // method of O with the argument "length".
        // 3. Let len be toUint32(lenValue).
        var len = O.length >>> 0;
        // 4. If isCallable(callback) is false, throw a TypeError exception.
        // See: http://es5.github.com/#x9.11
        if (typeof callback !== "function") {
            throw new TypeError(callback + ' is not a function');
        }
        // 5. If thisArg was supplied, let T be thisArg; else let
        // T be undefined.
        if (arguments.length > 1) {
            T = thisArg;
        }
        // 6. Let k be 0
        k = 0;
        // 7. Repeat, while k < len
        while (k < len) {
            var kValue;
            // a. Let Pk be ToString(k).
            //    This is implicit for LHS operands of the in operator
            // b. Let kPresent be the result of calling the HasProperty
            //    internal method of O with argument Pk.
            //    This step can be combined with c
            // c. If kPresent is true, then
            if (k in O) {
                // i. Let kValue be the result of calling the Get internal
                // method of O with argument Pk.
                kValue = O[k];

                // ii. Call the Call internal method of callback with T as
                // the this value and argument list containing kValue, k, and O.
                callback.call(T, kValue, k, O);
            }
            // d. Increase k by 1.
            k++;
        }
        // 8. return undefined
    };
}

6. str[index]与str.charAt(index) 有什么区别

1.当前索引值不在字符串长度范围内时，返回值不同，str[index]返回undefined，charAt方法返回空字符串
2.str[index]不兼容ie6/ie7/ie8浏览器，charAt方法可以兼容

7.写一个函数，将驼峰字符串转为下划线拼接的字符串。例如’HelloWorldXaHaHa’，执行后显示hello_world_xa_ha_ha

函数：

1
2
3
4
5
function conversion(worlds) {
    return worlds.replace(/[A-Z]/g, (cur, index) => {
        return index === 0 ? cur.toLowerCase() : '_' + cur.toLowerCase()
    })
}

二、HTML、CSS

1. CSS盒模型

  盒模型包括元素的margin（外边距）、border（边框）、padding（内边距）、content（内容）。
  盒模型有两种，IE盒模型（怪异模式）和W3C盒模型（标准）。



CSS3属性box-sizing

值 说明
content-box 默认值，元素遵循的是W3C盒模型
border-box 元素遵循的是IE盒模型
inherit 从父元素继承

2. position定位，下列说法错误的是

A.fixed 元素，可定位于相对于浏览器窗口的指定坐标，它始终是以 body 为依据
B.relative 元素以它原来的位置为基准偏移，在其移动后，原来的位置不再占据空间
C.absolute 的元素，如果它的 父容器设置了 position 属性，并且 position 的属性值为 absolute 或者 relative，那么就会依据父容器进行偏移
D.fixed 属性的元素在标准流中不占位置

答案：AB

值 描述 是否脱离标准文档流
relative 相对定位元素，相对于正常（原来的）位置定位 否
absolute 绝对定位元素，相对于 static 定位以外的第一个父元素定位 是
fixed 固定定位元素，相对于浏览器窗口定位 是
static 默认值，没有定位 否
inherit 从父类继承 position 属性的值 —

三、网络相关

1. http请求跨域

  跨域，是由浏览器的同源策略造成的，只要协议、域名、端口有任何一个不同，都被当作是不同的域。同源策略是一种约定，它是浏览器最核心也最基本的安全功能，如果缺少了同源策略，浏览器很容易受到XSS、CSRF等攻击。
解决跨域的方案：

  • JSONP，通过动态创建script标签，通过script标签的src，向一个不同源的接口发送一个get请求。缺点只能使用get请求，需要后端配合返回指定格式的数据。
  • document.domain + iframe，只适用于基础域名相同、子域名不同的情况。
  • CORS，跨域资源共享，服务器设置Access-Control-Allow-Origin HTTP响应头之后，浏览器将会允许跨域请求，前端无需任何处理。
  • 代理，目前常用方式，通过服务器设置代理，用于转发请求（nginx，node）。
  • websocket，是HTML5的一个持久化的协议，实现了浏览器与服务器的全双工通信，同时也是跨域的一种解决方案。在建立连接之后，webSocket的服务器与客户端都能主动向对方发送或接收数据。
  • postMessage，允许来自不同源的脚本采用异步方式进行有限的通信，可以实现跨文本档、多窗口、跨域消息传递。

延伸：

  • XSS，跨站脚本攻击，是最普遍的Web应用安全漏洞。这类漏洞能够使得攻击者嵌入恶意脚本代码到正常用户会访问到的页面中，当正常用户访问该页面时，则可导致嵌入的恶意脚本代码的执行，从而达到恶意攻击用户的目的。

四、算法相关

1. 二分查找

  给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
示例 1:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：
  1. 你可以假设 nums 中的所有元素是不重复的。
  2.n 将在 [1, 10000]之间。
  3.nums 的每个元素都将在 [-9999, 9999]之间。

解法：

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
const nums = [-1, 0, 2, 3, 5, 12, 11],
    target = 2

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let left = 0,
        right = nums.length - 1,
        mid
    while (left <= right) {
        mid = Math.floor((right - left) / 2) + left
        if (nums[mid] == target) {
            return mid
        } else if (nums[mid] < target) {
            left = mid + 1
        } else if (nums[mid] > target) {
            right = mid - 1
        }
    }
    return -1
};

search(nums, target)

2. 盛最多水的容器

  给定一个长度为 的整数数组 。有  条垂线，第 条线的两个端点是  和 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

1
2
3
输入: [1,8,6,2,5,4,8,3,7]
输出: 49
解释: 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。容器容纳水（蓝色部分）最大值为 49

示例 2:

1
2
输入：height = [1,1]
输出：1

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let left = 0, right = height.length - 1, area = 0
    while (left < right) {
        let value = Math.min(height[left], height[right]) * (right - left)
        area = Math.max(area, value)

        if (height[left] <= height[right]) {
            ++left
        }else {
            --right
        }
    }
    return area
};

maxArea([1,8,6,2,5,4,8,3,7])

3. 整数转罗马数字

  给你一个整数，将其转为罗马数字。罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

1
2
3
4
5
6
7
8
字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

  例如，罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

  • I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

示例 1:

1
2
输入: num = 3
输出: "III"

示例 2:

1
2
输入: num = 4
输出: "IV"

示例 3:

1
2
输入: num = 9
输出: "IX"

示例 4:

1
2
3
输入: num = 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例 5:

1
2
3
输入: num = 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

  • 1 <= num <= 3999

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number} num
 * @return {string}
 */
var intToRoman = function (num) {
    const nums = ['1000', '900', '500', '400', '100', '90', '50', '40', '10', '9', '5', '4', '1']
    const value = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I']
    let str = ''
    for (let i = 0; i < nums.length; i++) {

        while (num >= nums[i]) {
            num = num - nums[i]
            str = str + value[i]
        }
        // 
        if (num === 0) break
    }
    return str
}

4. 三数之和

  给你一个包含n个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得 a + b + c = 0 。请你找出所有和为 0 且不重复的三元组。

说明：答案中不可以包含重复的三元组。

示例 1:

1
2
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2:

1
2
输入：nums = []
输出：[]

示例 3:

1
2
输入：nums = [0]
输出：[]

提示：

  • 0 <= nums.length <= 3000
  • <= nums[i] <=

解法：

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
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
    // 排序,
    nums.sort((a, b) => a - b)
    var result = []
    for (let i = 0; i < nums.length - 2; i++) {
        // 第一项不能大于0，不会存在三数之和为0
        if (nums[i] > 0) return result
        // 相邻两项重复，跳出循环
        if (i > 0 && nums[i] == nums[i - 1]) continue
        // 左右指针
        let left = i + 1, right = nums.length - 1

        while (left < right) {
            let total = nums[i] + nums[left] + nums[right]
            // 满足条件，添加三个数的值，指针移动
            if (total == 0) {
                result.push([nums[i], nums[left], nums[right]])
                left++
                right--
            } else {
                total > 0 ? right-- : left++
            }
            // 指针移动后，与移动前值一样，继续移动
            while (left > i + 1 && nums[left] == nums[left - 1]) left++;
            while (right < nums.length - 1 && nums[right] == nums[right + 1]) right--;
        }
    }
    return result
}

5. 有效的数独

  请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

  1.数字 1-9 在每一行只能出现一次。
  2.数字 1-9 在每一列只能出现一次。
  3.数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

  • 一个有效的数独（部分已被填充）不一定是可解的。
  • 只需要根据以上规则，验证已经填入的数字是否有效即可。
  • 空白格用 ‘.’ 表示。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：board = 
[
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]
]
输出：true

示例 2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入：board = 
[
    ["8","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]
]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字（1-9）或者 ‘.’

解法：

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
/**
 * @param {character[][]} board
 * @return {boolean}
 */
var isValidSudoku = function(board) {
    var obj = {}
    for (let i = 0; i < board.length; i++) {
        // 行数组
        obj.row = []
        // 3 * 3 为一组，数组
        if (i % 3 == 0) {
            obj.group0 = []
            obj.group1 = []
            obj.group2 = []
        }
        for (let j = 0; j < board[i].length; j++) {
            let val = board[i][j] * 1, groupIndex = Math.floor(j / 3), columns = `columns${j}`
            // 列数组
            if (!obj[columns]) obj[columns] = []
            if (isNaN(val)) continue
            // 行、列、组中已经有当前数据，直接返回false
            if (obj.row.includes(val)) return false
            if (obj[columns].includes(val)) return false
            if (obj[`group${groupIndex}`].includes(val)) return false
            // 行、列、组添加当前数值
            obj.row.push(val)
            obj[columns].push(val)
            obj[`group${groupIndex}`].push(val)
        }
    }
    obj = null
    return true
}

6. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

1
2
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

1
2
输入：nums = [1, 6, 8]
输出：[[ 1, 6, 8 ],[ 1, 8, 6 ],[ 6, 1, 8 ],[ 6, 8, 1 ],[ 8, 1, 6 ],[ 8, 6, 1 ]]

提示：

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

解法：

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
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
    let res = [], used = new Array(nums.length).fill(false)
    function backtrack(nums, index, track) {
        // 终止条件，结果里添加改排列
        if (track.length == nums.length) {
            res.push(track)
            return
        }
        // 循环处理
        for (let i = 0; i < nums.length; i++) {
            // used[i] 已经使用，跳过
            if (used[i]) continue
            // 做出选择
            track.push(nums[i])
            used[i] = true
            // 递归调用
            backtrack(nums, index + 1, [...track])
            // 撤销选择，回溯
            track.pop()
            used[i] = false
        }
    }

    backtrack(nums, 0, [])
    return res
}

7. 解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：
  1.数字 1-9 在每一行只能出现一次。
  2.数字 1-9 在每一列只能出现一次。
  3.数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
输入：board = 
[
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]
]
输出：[
    ["5","3","4","6","7","8","9","1","2"],
    ["6","7","2","1","9","5","3","4","8"],
    ["1","9","8","3","4","2","5","6","7"],
    ["8","5","9","7","6","1","4","2","3"],
    ["4","2","6","8","5","3","7","9","1"],
    ["7","1","3","9","2","4","8","5","6"],
    ["9","6","1","5","3","7","2","8","4"],
    ["2","8","7","4","1","9","6","3","5"],
    ["3","4","5","2","8","6","1","7","9"]
]

解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字（1-9）或者 ‘.’

解法：

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
/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
    // 回溯，依次遍历board
    // row, col 值范围 0-8
    function backtrack(board, row, col) {
        // 边界处理
        // 最后一列遍历结束，遍历下一列
        if (col == 9) return backtrack(board, row + 1, 0)
        // 最后一行遍历结束
        if (row == 9) return true
        // 非空值，直接跳过
        if (board[row][col] != '.') return backtrack(board, row, col + 1)
        // 循环填充值范围 1-9
        for (let v = 1; v < 10; v++) {
            let num = String(v)
            // 检查满足条件
            if (check(board, row, col, num)) {
                // 尝试填入当前数字
                board[row][col] = num
                // 递归调用，下一个填写值满足条件，返回
                if (backtrack(board, row, col + 1))  return true
                // 不满足条件，撤回已填数字
                board[row][col] = '.'
            }
        }
    }

    // 检查是否存在 行、列、3*3九宫格，已填写当前数字
    function check(board, row, col, num) {
        for (let i = 0; i < 9; i++) {
            if (board[row][i] == num) return false
            if (board[i][col] == num) return false
            var m = parseInt(row / 3) * 3 + parseInt(i / 3), n = parseInt(col / 3) * 3 + i % 3
            if (board[m][n] == num) return false
        }
        return true
    }

    backtrack(board, 0, 0)
}
JavaScript

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！