盘点那些一行js代码搞定的算法题

1.各位数相加

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果。

示例 1:

输入: num = 38
输出: 2 
解释: 各位相加的过程为 ： 38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2
由于 2 是一位数，所以返回 2。

示例 2:

输入: num = 0
输出: 0

进阶： 你可以不使用循环或者递归，在 O(1) 时间复杂度内解决这个问题吗？

// 常规写法
var addDigits = function(num) {
    if(!num){ return num; }
    let sum = [...String(num)].reduce((acc, curr) => {
        return Number(acc) + Number(curr);
    }, 0);
    return sum >= 10 ? addDigits(sum) : sum;
};

// 一行代码
var addDigits = function(num) {
    return (num-1) %9 +1;
}

聪明的你可能会问，为什么要 模9 ? 举个例子：

• 比如 num=678，计算过程为 678⟶6+7+8=21⟶2+1=3
• 想一想，从 678 到 21，减少了多少？
• 减少了：
• 678−21
• = (600+70+8)−(6+7+8)
• = (600−6)+(70−7)+(8−8)
• = 6×(100−1)+7×(10−1)
• = 6×99+7×9
• 由于 99 和 9 都是 9 的倍数，所以减少量一定是 9 的倍数。
• 从 21 到 3 也同理，减少量也是 9 的倍数。
• 由于减少量总是 9 的倍数，只看结果的话，相当于从 678 开始，不断地减 9，直到减成个位数（小于 10 的数）。
• 这和「余数」的概念是类似的：
• 从 num 开始，不断地减 9，直到小于 9，所得到的结果叫做 num 除以 9 的余数，即 num % 9。
• 特殊情况：如果 num>0 且是 9 的倍数，那么最终 num 会减成 9，而不是 0。因为 9 已经是个位数了。
• 这可以整合成一个公式：
• (num−1)%9+1

2.有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

// 常规解法
var isAnagram = function(s, t) {
    let sArr = s.split("").sort();
    let tArr = t.split("").sort();
    let flag = true;
    if(sArr.length !== tArr.length){ return false; }
    for(let i = 0 ; i < sArr.length; i++){
        if(tArr[i] !== sArr[i]){
            flag = false;
        }
    }
    return flag;
};


// 一行代码
var isAnagram = function(s, t) {
    return s.length == t.length && [...s].sort().join('') === [...t].sort().join('')
};

没想到吧，字符串还能用...扩展语法，是不是挺骚的，总的来说一句话，把字符串拆分后排序再组合，判断两个字符串是否一致就好；

3.检查棋盘相同颜色方格

给你两个字符串 coordinate1 和 coordinate2，代表 8 x 8 国际象棋棋盘上的两个方格的坐标。

以下是棋盘的参考图。

如果这两个方格颜色相同，返回 true，否则返回 false。

坐标总是表示有效的棋盘方格。坐标的格式总是先字母（表示列），再数字（表示行）。

示例 1：

输入：  coordinate1 = "a1", coordinate2 = "c3"
输出： true

示例 2：

输入： coordinate1 = "a1", coordinate2 = "h3"
输出： false

解释：

// 枚举写法
var checkTwoChessboards = function(coordinate1, coordinate2) {
    let coordinateMap = {};
    let letterArr = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'];
    for(let i = 0;i <=8; i++){
        for(let j = 0; j <=8; j++){
            coordinateMap[`${letterArr[j]}${i+1}`] = (i+j)%2 === 0;
        } 
    }
    return coordinateMap[coordinate1] === coordinateMap[coordinate2];
};

// 一行代码
var checkTwoChessboards = function(coordinate1, coordinate2) {
    // 行列差值之间的和为偶数，说明颜色相同;
    return ((coordinate1.charCodeAt(0) - coordinate2.charCodeAt(0)) + (coordinate1.charCodeAt(1) - coordinate2.charCodeAt(1))) % 2 === 0;
};

这里用到了 charCodeAt方法，返回一个整数，表示给定索引处的 UTF-16 码元，把整个棋盘行对应字母，列对应数字，行和列基数位颜色相同，如果 行列差值之间的和为偶数，说明颜色相同。

字母拆解：

// 行差值 a1, h3 两个棋盘字母a, h UTF-16码元相减
let rowDiff = coordinate1.charCodeAt(0) - coordinate2.charCodeAt(0)

数字拆解：

// 列差值 a1, h3 两个棋盘数字1,3 UTF-16码元相减
let columnsDiff = coordinate1.charCodeAt(1) - coordinate2.charCodeAt(1)

如果行列差之和为偶数，则说明颜色相同

var checkTwoChessboards = function(coordinate1, coordinate2) {
    let rowDiff = coordinate1.charCodeAt(0) - coordinate2.charCodeAt(0);
    let columnsDiff = coordinate1.charCodeAt(1) - coordinate2.charCodeAt(1);
    return ((rowDiff + columnsDiff) % 2) === 0;
}

4.2的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

示例 1：

输入： n = 1
输出： true
解释： 20 = 1

示例 2：

输入： n = 16
输出： true
解释： 24 = 16

示例 3：

输入： n = 3
输出： false

// 一行代码
var isPowerOfTwo = function(n) {
    return n >0 && (n & (n-1))===0;
};

解释： 来自力扣官方

这里用到了位运算，一个数 n 是 2 的幂，当且仅当 n 是正整数，并且 n 的二进制表示中仅包含 1 个 1。

因此我们可以考虑使用位运算，将 n 的二进制表示中最低位的那个 1 提取出来，再判断剩余的数值是否为 0 即可。下面介绍两种常见的与「二进制表示中最低位」相关的位运算技巧。

第一个技巧是 n & (n - 1)

其中 & 表示按位与运算。该位运算技巧可以直接将 n 二进制表示的最低位 1 移除，它的原理如下：

• 假设 n 的二进制表示为 (a10⋯0)2，其中 a 表示若干个高位，1 表示最低位的那个 1，0⋯0 表示后面的若干个 0，那么 n−1 的二进制表示为： (a10⋯0)2

• 我们将 (a10⋯0)2 与 (a01⋯1)2 进行按位与运算，高位 a 不变，在这之后的所有位都会变为 0，这样我们就将最低位的那个 1 移除了。

进行按位与运算，高位 a 不变，在这之后的所有位都会变为 0，这样我们就将最低位的那个 1 移除了。

5. 3 的幂

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x

示例 1：

输入： n = 27
输出： true

示例 2：

输入： n = 0
输出： false

示例 3：

输入： n = 9
输出： true

示例 4：

输入： n = 45
输出： false

// 一行代码
var isPowerOfThree = function(n) {
    return n && 1162261467 % n === 0;
};

你可能会问，1162261467 是啥？其实这是用了一种较为取巧的做法。

在题目给定的 32 位有符号整数的范围内，最大的 3 的幂为 3^19 =1162261467。我们只需要判断 n 是否是 3^19 的约数即可。 与方法一不同的是，这里需要特殊判断 n 是负数或 0 的情况。

6. 4的幂

var isPowerOfFour = function(n) {
    // 检查是否是正数和2的幂
    // 由于4的幂在二进制中'1'必须在偶数位上，
    // 我们可以利用掩码 0x55555555 (1010101010101010101010101010101)
    // 来确保'1'只出现在偶数位上
    return n > 0 && (n & (n - 1)) === 0 && (n & 0x55555555) !== 0;
};

• 后面遇到N的幂求解，可以套用这段暴力破解代码： 不管是4的幂，还是N的幂，通用暴力解法

// 这里是4的幂求解，如果是求5的幂就模5除5
var isPowerOfFour = function(n) {
    while(n && n % 4 == 0){
        n = Math.floor(n/4);
    }
    return n === 1;
};

7. Nim 游戏

你和你的朋友，两个人一起玩 Nim 游戏：

• 桌子上有一堆石头。
• 你们轮流进行自己的回合， 你作为先手 。
• 每一回合，轮到的人拿掉 1 - 3 块石头。
• 拿掉最后一块石头的人就是获胜者。

假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。  

示例 1：

输入： n = 4
输出： false 
解释： 以下是可能的结果:
1. 移除1颗石头。你的朋友移走了3块石头，包括最后一块。你的朋友赢了。
2. 移除2个石子。你的朋友移走2块石头，包括最后一块。你的朋友赢了。
3.你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。
在所有结果中，你的朋友是赢家。

示例 2：

输入： n = 1
输出： true

示例 3：

输入： n = 2
输出： true

var canWinNim = function(n) {
    return n % 4 !== 0;
};

让我们考虑一些小例子。显而易见的是，如果石头堆中只有一块、两块、或是三块石头，那么在你的回合，你就可以把全部石子拿走，从而在游戏中取胜；如果堆中恰好有四块石头，你就会失败。因为在这种情况下不管你取走多少石头，总会为你的对手留下几块，他可以将剩余的石头全部取完，从而他可以在游戏中打败你。因此，要想获胜，在你的回合中，必须避免石头堆中的石子数为 4 的情况。

我们继续推理，假设当前堆里只剩下五块、六块、或是七块石头，你可以控制自己拿取的石头数，总是恰好给你的对手留下四块石头，使他输掉这场比赛。但是如果石头堆里有八块石头，你就不可避免地会输掉，因为不管你从一堆石头中挑出一块、两块还是三块，你的对手都可以选择三块、两块或一块，以确保在再一次轮到你的时候，你会面对四块石头。显然我们继续推理，可以看到它会以相同的模式不断重复 n=4,8,12,16,…，基本可以看出如果堆里的石头数目为 4 的倍数时，你一定会输掉游戏。

如果总的石头数目为 4 的倍数时，因为无论你取多少石头，对方总有对应的取法，让剩余的石头的数目继续为 4 的倍数。对于你或者你的对手取石头时，显然最优的选择是当前己方取完石头后，让剩余的石头的数目为 4 的倍数。假设当前的石头数目为 x，如果 x 为 4 的倍数时，则此时你必然会输掉游戏；如果 x 不为 4 的倍数时，则此时你只需要取走 xmod4 个石头时，则剩余的石头数目必然为 4 的倍数，从而对手会输掉游戏。

8.柯里化

function curry(fn, ...args) {
    return fn.length <= args.length ? fn(...args) : curry.bind(null, fn, ...args);
}

9.有效的完全平方数

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如  sqrt 。  

示例 1：

输入： num = 16
输出： true
解释： 返回 true ，因为 4 * 4 = 16 且 4 是一个整数。

示例 2：

输入： num = 14
输出： false
解释： 返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

var isPerfectSquare = function(num) {
    return Number.isInteger(Math.sqrt(num));
};

number.isInteger  静态方法判断传入值是否为整数；Math.sqrt 函数返回一个数的平方根，两者结合搞定。

10.两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的 交集，输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

  示例 1：

输入： nums1 = [1,2,2,1], nums2 = [2,2]
输出： [2]

示例 2：

输入： nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出： [9,4]
解释： [4,9] 也是可通过的

// 常规解法
var intersection = function(nums1, nums2) {
    let res = [];
    for(let i = 0; i < nums1.length; i++){
        if(!res.includes(nums1[i]) && nums2.includes(nums1[i])){
            res.push(nums1[i]);
        }
    }
    return res;
};

// 一行代码
var intersection = function(nums1, nums2) {
    return [...new Set(nums1)].filter(n => nums2.includes(n));
};

首先利用Set()构造函数 给num1解构后去重，再使用filter去过滤nums2里面的每一项，搞定，下课！