您的位置: 首页  >  文章  >  javascript实现剑指offer——字符串/数组的排列组合题目合集

javascript实现剑指offer——字符串/数组的排列组合题目合集

分类: 文章 • 2024-06-15 15:12:28

leetcode：46. 全排列

描述：

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

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

思路

特殊情况：数组长度==0时，返回[[]];

  1. 新建一个空数组存放结果

  2. 全排列的情况考虑递归的方法，

  3. 首先固定第一个字符，第一个字符可以是数组中的任意元素，所以先遍历数组，拿出第一个元素和剩下的元素；

  4. 对剩下的元素递归调用，递归的出口是arr长度为1，此时返回[单个元素]；

  5. 最后对递归的结果数组遍历，每一个都拼接上拿出的第一个元素，然后push进结果数组；
    注意：长度为1（递归出口）和其他递归情况return格式必须统一为数组，因为如果return一个元素，则无法对return的结果进行数组的遍历，递归到1的时候就会报错：foreach is not a function

javascript实现剑指offer——字符串/数组的排列组合题目合集

代码


/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
  let result = [];
  // 长度为1，直接返回自身
  if (nums.length <= 1) {
    return [nums];
  }
  for (let i = 0; i < nums.length; i++) {
    //遍历每一个数组元素，
    let first = nums[i]; //作为排列数组的第一个
    let newArr = nums.slice(0, i).concat(nums.slice(i + 1)); //剔除愿数组中的“first”，保存起来
    let others = permute(newArr); //对newArr递归调用，返回剩下的数组元素的全排列数组
    // 遍历others数组，对每个排列拼接first
    others.forEach(item => {
      result.push([].concat(first, item));
    });
  }
  return result;
};
permute([1, 2, 3]);

leetcode：47. 全排列 II

描述：

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

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

思路

  1. 其他同上，关键是数组元素重复，导致全排列得到的结果会有重复，所以在最后这里加上一层数组去重。
  2. 这里是二维数组，二维数组去重比较特殊，不能使用set（Set 对象允许你存储任何类型的唯一值，无论是原始值或者是对象引用。），实验结果set只能去掉第一个重复的数组（？？？）
  • 通过对象的键值对来实现二维数组去重，首先新建一个空对象，作为对照；
  • 然后遍历数组，对每个元素判断对象里面是否有对应的key，有的话，就代表这个元素被遍历到过，从原来数组里删掉这个重复的元素，然后i–（否则会漏过下一个元素）
  • 没有的话，把这个obj【key】=1，作为对照。
  • 出口：遍历完成，原数组重复元素被删除。
var permuteUnique = function(nums) {
  function permute(nums) {
    let result = [];
    // 长度为1，直接返回自身
    if (nums.length <= 1) {
      return [nums];
    }
    for (let i = 0; i < nums.length; i++) {
      //遍历每一个数组元素，
      let first = nums[i]; //作为排列数组的第一个
      let newArr = nums.slice(0, i).concat(nums.slice(i + 1)); //剔除愿数组中的“first”，保存起来
      let others = permute(newArr); //对newArr递归调用，返回剩下的数组元素的全排列数组
      // 遍历others数组，对每个排列拼接first
      others.forEach(item => {
        result.push([].concat(first, item));
      });
    }
    return result;
  }
  let result2 = permute(nums);

  let obj = {};//对照对象
  for (var i = 0; i < result2.length; i++) {
    // 判断当前项是否遍历过，是则删除，否存入obj以作对照

    if (obj[result2[i]]) {
      result2.splice(i, 1);
      i--; //数组删除了一项，要把i回退一下，不然会跳过下一项不去遍历
    } else {
      obj[result2[i]] = 1;
    }
  }
  // return arr;
  return result2;
};
var result = permuteUnique([1, 1, 2]);

牛客网：字符串的排列

描述

题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路

字符串的排列和上面思路基本类似，不同点：

  1. 特殊情况：字符串为“”时输出为[],多加一层判断
  2. 字符串的连接用“+”
  3. 对于有重复字符的字符串，最后对result数组去重，就可以剔除掉全排列重复的部分了
    数组去重方法具体请看我的另一篇博文https://blog.****.net/weixin_28900307/article/details/88384480

代码

function Permutation(str) {
  let result = [];
  // 长度为1，直接返回自身
  if (str.length <= 1) {
    return str.length == 0 ? [] : [str]; //单个字符串也要放进数组里，这样递归调用的返回才能统一：全是数组
  }
  for (let i = 0; i < str.length; i++) {
    //遍历每一个数组元素，
    let first = str[i]; //作为排列数组的第一个
    let newArr = str.slice(0, i) + str.slice(i + 1); //剔除愿数组中的“first”，保存起来
    let others = Permutation(newArr); //对newArr递归调用，返回剩下的数组元素的全排列数组
    // 遍历others数组，对每个排列拼接first
    others &&
      others.forEach(item => {
        result.push(first + item);
      });
  }
  result = [...new Set(result)];
  return result;
}
Permutation("abc");

相关推荐