/**
 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

 你可以假设数组是非空的，并且给定的数组总是存在多数元素。

 示例 1:

 输入: [3,2,3]
 输出: 3
 示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2
**/
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  return  nums.sort()[parseInt(nums.length/2)];
};

/**
 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
 示例:

 输入："23"
 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
 * */
/**
 * @param {string} digits
 * @return {string[]}
 */
export default (str) => {
    // 建立电话号码键盘映射
    let map = ['', 1, 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
    // 把输入字符串按单字字符分割变成数组 234 => [2, 3, 4]
    let num = str.split('');
    // 保存键盘映射后的字母内容，23 => ['abc', 'def']
    let code = [];
    num.forEach(item => {
        if (map[item]) {
            code.push(map[item])
        }
    });

    let comb = (arr) => {
        // 临时变量用来保存前两个组合的结果
        let temp = [];
        // 最外层的循环遍历的是一个元素，内侧的循环遍历的是第二个元素
        for (let i = 0; i < arr[0].length; i++) {
            for (let j = 0; j < arr[1].length; j++) {
                temp.push(`${arr[0][i]}${arr[1][j]}`)
            }
        }
        arr.splice(0, 2, temp);
        if (arr.length > 1) {
            comb(arr)
        } else {
            return temp;
        }
        return arr[0]
    };
    return comb(code)
}

/**
 * 给定一副牌，每张牌上都写着一个整数。

 此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：

 每组都有 X 张牌。
 组内所有的牌上都写着相同的整数。
 仅当你可选的 X >= 2 时返回 true。

 示例 1：

 输入：[1,2,3,4,4,3,2,1]
 输出：true
 解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]
 示例 2：

 输入：[1,1,1,2,2,2,3,3]
 输出：false
 解释：没有满足要求的分组。
 示例 3：

 输入：[1]
 输出：false
 解释：没有满足要求的分组。
 示例 4：

 输入：[1,1]
 输出：true
 解释：可行的分组是 [1,1]
 示例 5：

 输入：[1,1,2,2,2,2]
 输出：true
 解释：可行的分组是 [1,1]，[2,2]，[2,2]

 提示：

 1 <= deck.length <= 10000
 0 <= deck[i] < 10000
 * */

export default (arr) => {
    // 存储每张卡牌的总数
    // 修改排序的方式修改为直接统计每个相同字符的数量，思路不变（LeetCode测试用例）
    let group = [];
    let tmp = {};
    arr.forEach(item => {
        tmp[item] = tmp[item] ? tmp[item] + 1 : 1
    });
    for (let v of Object.values(tmp)) {
        group.push(v)
    }
    // 此时group已经存放的是每张牌的总数了（数组只遍历一遍，避免了排序和正则的耗时）
    // 求两个数的最大公约数
    let gcd = (a, b) => {
        if (b === 0) {
            return a
        } else {
            return gcd(b, a % b)
        }
    };
    while (group.length > 1) {
        let a = group.shift();
        let b = group.shift();
        let v = gcd(a, b);
        if (v === 1) {
            return false
        } else {
            group.unshift(v)
        }
    }
    return group.length ? group[0] > 1 : false
}

/**
 假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
 给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。

 示例 1:
 输入: flowerbed = [1,0,0,0,1], n = 1
 输出: True

 示例 2:
 输入: flowerbed = [1,0,0,0,1], n = 2
 输出: False
 注意:

 数组内已种好的花不会违反种植规则。
 输入的数组长度范围为 [1, 20000]。
 n 是非负整数，且不会超过输入数组的大小。
 **/
export default (arr, n) => {
    // 计数器
    let max = 0;
    // 右边界补充[0,0,0],最后一块地能不能种只取决于前面的是不是1，所以默认最后一块地的右侧是0（无须考虑右侧边界有阻碍）（LeetCode测试用例）
    arr.push(0);
    for (let i = 0, len = arr.length - 1; i < len; i++) {
        if (arr[i] === 0) {
            if (i === 0 && arr[1] === 0) {
                max++;
                i++
            } else if (arr[i - 1] === 0 && arr[i + 1] === 0) {
                max++;
                i++
            }
        }
    }
    return max >= n
}

/**
 * 格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。

 给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。

 示例 1:

 输入: 2
 输出: [0,1,3,2]
 解释:
 00 - 0
 01 - 1
 11 - 3
 10 - 2

 对于给定的 n，其格雷编码序列并不唯一。
 例如，[0,2,3,1] 也是一个有效的格雷编码序列。

 00 - 0
 10 - 2
 11 - 3
 01 - 1
 示例 2:

 输入: 0
 输出: [0]
 解释: 我们定义格雷编码序列必须以 0 开头。
      给定编码总位数为 n 的格雷编码序列，其长度为 2n。当 n = 0 时，长度为 20 = 1。
      因此，当 n = 0 时，其格雷编码序列为 [0]。
 **/
// 递归函数，用来算输入为n的格雷编码序列

export default (n) => {
    let make = (n) => {
        if (n === 1) {
            return [0, 1]
        } else {
            let prev = make(n - 1);
            let result = [];
            let max = Math.pow(2, n) - 1;
            for (let i = 0; i < prev.length; i++) {
                result[i] = `0${prev[i]}`;
                result[max - i] = `1${prev[i]}`
            }
            return result.map(v => {
                return parseInt(v, 2)
            });
        }
    };
    return make(n)
}