JavaScript数据结构与算法-Array

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

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

输入: [4,1,2,1,2]
输出: 4

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    // 这个方法可以找出存在奇数次的数字，不一定只有一次
    for(let i = 1;i<nums.length;i++) {
        nums[0] = nums[0] ^ nums[i]
    }
    return nums[0]
};

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

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

输入: [0,1,0,1,0,1,99]
输出: 99

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    // 这个方法也可以做上面的题，i+=2，可以以此类推下去
    nums.sort();
    for (let i = 0; i < nums.length; i+=3) {
        if (nums[i] !== nums[i + 1]) {
          return nums[i];
          break;
        }
    }
};

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]
示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]
说明:

输出结果中的每个元素一定是唯一的。 *
我们可以不考虑输出结果的顺序。

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    return Array.from(new Set(nums1.filter(item => nums2.indexOf(item)>-1)))
};

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
说明：

输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。
进阶:

如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
    let res = []
    function fnc(min, max) {
        let index = -1
        for (let i = 0; i < min.length; i++) {
            if (max.indexOf(min[i]) > -1) {
                res.push(min[i])
                max.splice(max.indexOf(min[i]),1)
            }
        }
    }
    if (nums1.length > nums2.length) {
        fnc(nums2, nums1)
    } else {
        fnc(nums1, nums2)
    }
    return res
};

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1:

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
	let res = []
	function fnc (arr) {
		let len = arr.length - 1
		if (arr[len] + 1 == 10) {
			if (len==0) {
				return [1,0,...res]
			}
			res.unshift(0)
			arr.pop()
			// 这里需要return 递归调用，不然会得到undefined
			return fnc(arr)
		} else {
			digits[len]+=1
			return [...arr,...res]
    	}
	}
	return fnc(digits)
};

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

示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

export default (str) => {
  // 建立电话号码键盘映射
  let map = ['', 1, 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
  // 字符串转成数组
  let num = str.split('')
  let code = []
  // code 是存储 str 对应的 映射 字符串的数组
  num.forEach(item => {
    if (map[item]) {
      code.push(map[item])
    }
  })
  // 递归函数
  let fnc = arr => {
    let tmp = []
    for (let i = 0; i < arr[0].length; i++) {
      for (let j = 0; j < arr[1].length; j++) {
        tmp.push(`${arr[0][i]}${arr[1][j]}`)
      }
    }
    // 替换数组前两项，至关重要
    arr.splice(0, 2, tmp)
    if (arr.length > 1) {
      fnc(arr)
    } else {
      return tmp
    }
    // 最后会返回一个二维数组，而我们需要的就是第一个
    return arr[0]
  }
  return fnc(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