精华内容
下载资源
问答
  • 是由一堆无序的、相关联的,且不重复的内存结构【数学中称为元素】组成的组合 字典 是一些元素的集合。每个元素有一个称作key 的域,不同元素的key 各不相同 区别? 共同点:集合、字典都可以存储不重复的值 不同点...

    在这里插入图片描述
    如果要用一句来描述,我们可以说

    Set是一种叫做集合的数据结构,Map是一种叫做字典的数据结构

    什么是集合?什么又是字典?

    集合
    是由一堆无序的、相关联的,且不重复的内存结构【数学中称为元素】组成的组合

    字典
    是一些元素的集合。每个元素有一个称作key 的域,不同元素的key 各不相同

    区别?

    共同点:集合、字典都可以存储不重复的值
    不同点:集合是以[值,值]的形式存储元素,字典是以[键,值]的形式存储
    Set
    Set是es6新增的数据结构,类似于数组,但是成员的值都是唯一的,没有重复的值,我们一般称为集合

    Set本身是一个构造函数,用来生成 Set 数据结构

    const s = new Set();
    增删改查
    Set的实例关于增删改查的方法:

    add()

    delete()

    has()

    clear()

    add()
    添加某个值,返回 Set 结构本身

    当添加实例中已经存在的元素,set不会进行处理添加

    s.add(1).add(2).add(2); // 2只被添加了一次
    delete()
    删除某个值,返回一个布尔值,表示删除是否成功

    s.delete(1)
    has()
    返回一个布尔值,判断该值是否为Set的成员

    s.has(2)
    clear()
    清除所有成员,没有返回值

    s.clear()
    遍历
    Set实例遍历的方法有如下:

    关于遍历的方法,有如下:

    keys():返回键名的遍历器
    values():返回键值的遍历器
    entries():返回键值对的遍历器
    forEach():使用回调函数遍历每个成员
    Set的遍历顺序就是插入顺序

    keys方法、values方法、entries方法返回的都是遍历器对象

    let set = new Set([‘red’, ‘green’, ‘blue’]);

    for (let item of set.keys()) {
    console.log(item);
    }
    // red
    // green
    // blue

    for (let item of set.values()) {
    console.log(item);
    }
    // red
    // green
    // blue

    for (let item of set.entries()) {
    console.log(item);
    }
    // [“red”, “red”]
    // [“green”, “green”]
    // [“blue”, “blue”]
    forEach()用于对每个成员执行某种操作,没有返回值,键值、键名都相等,同样的forEach方法有第二个参数,用于绑定处理函数的this

    let set = new Set([1, 4, 9]);
    set.forEach((value, key) => console.log(key + ’ : ’ + value))
    // 1 : 1
    // 4 : 4
    // 9 : 9
    扩展运算符和 Set 结构相结合实现数组或字符串去重

    // 数组
    let arr = [3, 5, 2, 2, 5, 5];
    let unique = […new Set(arr)]; // [3, 5, 2]

    // 字符串
    let str = “352255”;
    let unique = […new Set(str)].join(""); // “”
    实现并集、交集、和差集

    let a = new Set([1, 2, 3]);
    let b = new Set([4, 3, 2]);

    // 并集
    let union = new Set([…a, …b]);
    // Set {1, 2, 3, 4}

    // 交集
    let intersect = new Set([…a].filter(x => b.has(x)));
    // set {2, 3}

    // (a 相对于 b 的)差集
    let difference = new Set([…a].filter(x => !b.has(x)));
    // Set {1}
    二、Map
    Map类型是键值对的有序列表,而键和值都可以是任意类型

    Map本身是一个构造函数,用来生成 Map 数据结构

    const m = new Map()
    增删改查
    Map 结构的实例针对增删改查有以下属性和操作方法:

    size 属性
    set()
    get()
    has()
    delete()
    clear()
    size
    size属性返回 Map 结构的成员总数。

    const map = new Map();
    map.set(‘foo’, true);
    map.set(‘bar’, false);

    map.size // 2
    set()
    设置键名key对应的键值为value,然后返回整个 Map 结构

    如果key已经有值,则键值会被更新,否则就新生成该键

    同时返回的是当前Map对象,可采用链式写法

    const m = new Map();

    m.set(‘edition’, 6) // 键是字符串
    m.set(262, ‘standard’) // 键是数值
    m.set(undefined, ‘nah’) // 键是 undefined
    m.set(1, ‘a’).set(2, ‘b’).set(3, ‘c’) // 链式操作
    get()
    get方法读取key对应的键值,如果找不到key,返回undefined

    const m = new Map();

    const hello = function() {console.log(‘hello’);};
    m.set(hello, ‘Hello ES6!’) // 键是函数

    m.get(hello) // Hello ES6!
    has()
    has方法返回一个布尔值,表示某个键是否在当前 Map 对象之中

    const m = new Map();

    m.set(‘edition’, 6);
    m.set(262, ‘standard’);
    m.set(undefined, ‘nah’);

    m.has(‘edition’) // true
    m.has(‘years’) // false
    m.has(262) // true
    m.has(undefined) // true
    delete()
    delete方法删除某个键,返回true。如果删除失败,返回false

    const m = new Map();
    m.set(undefined, ‘nah’);
    m.has(undefined) // true

    m.delete(undefined)
    m.has(undefined) // false
    clear()
    clear方法清除所有成员,没有返回值

    let map = new Map();
    map.set(‘foo’, true);
    map.set(‘bar’, false);

    map.size // 2
    map.clear()
    map.size // 0
    遍历
    Map 结构原生提供三个遍历器生成函数和一个遍历方法:

    keys():返回键名的遍历器
    values():返回键值的遍历器
    entries():返回所有成员的遍历器
    forEach():遍历 Map 的所有成员
    遍历顺序就是插入顺序

    const map = new Map([
    [‘F’, ‘no’],
    [‘T’, ‘yes’],
    ]);

    for (let key of map.keys()) {
    console.log(key);
    }
    // “F”
    // “T”

    for (let value of map.values()) {
    console.log(value);
    }
    // “no”
    // “yes”

    for (let item of map.entries()) {
    console.log(item[0], item[1]);
    }
    // “F” “no”
    // “T” “yes”

    // 或者
    for (let [key, value] of map.entries()) {
    console.log(key, value);
    }
    // “F” “no”
    // “T” “yes”

    // 等同于使用map.entries()
    for (let [key, value] of map) {
    console.log(key, value);
    }
    // “F” “no”
    // “T” “yes”

    map.forEach(function(value, key, map) {
    console.log(“Key: %s, Value: %s”, key, value);
    });
    三、WeakSet 和 WeakMap
    WeakSet
    创建WeakSet实例

    const ws = new WeakSet();
    WeakSet 可以接受一个具有 Iterable 接口的对象作为参数

    const a = [[1, 2], [3, 4]];
    const ws = new WeakSet(a);
    // WeakSet {[1, 2], [3, 4]}
    在API中WeakSet与Set有两个区别:

    没有遍历操作的API
    没有size属性
    WeackSet只能成员只能是引用类型,而不能是其他类型的值

    let ws=new WeakSet();

    // 成员不是引用类型
    let weakSet=new WeakSet([2,3]);
    console.log(weakSet) // 报错

    // 成员为引用类型
    let obj1={name:1}
    let obj2={name:1}
    let ws=new WeakSet([obj1,obj2]);
    console.log(ws) //WeakSet {{…}, {…}}
    WeakSet 里面的引用只要在外部消失,它在 WeakSet 里面的引用就会自动消失

    WeakMap
    WeakMap结构与Map结构类似,也是用于生成键值对的集合

    在API中WeakMap与Map有两个区别:

    没有遍历操作的API
    没有clear清空方法
    // WeakMap 可以使用 set 方法添加成员
    const wm1 = new WeakMap();
    const key = {foo: 1};
    wm1.set(key, 2);
    wm1.get(key) // 2

    // WeakMap 也可以接受一个数组,
    // 作为构造函数的参数
    const k1 = [1, 2, 3];
    const k2 = [4, 5, 6];
    const wm2 = new WeakMap([[k1, ‘foo’], [k2, ‘bar’]]);
    wm2.get(k2) // “bar”
    WeakMap只接受对象作为键名(null除外),不接受其他类型的值作为键名

    const map = new WeakMap();
    map.set(1, 2)
    // TypeError: 1 is not an object!
    map.set(Symbol(), 2)
    // TypeError: Invalid value used as weak map key
    map.set(null, 2)
    // TypeError: Invalid value used as weak map key
    WeakMap的键名所指向的对象,一旦不再需要,里面的键名对象和所对应的键值对会自动消失,不用手动删除引用

    举个场景例子:

    在网页的 DOM 元素上添加数据,就可以使用WeakMap结构,当该 DOM 元素被清除,其所对应的WeakMap记录就会自动被移除

    const wm = new WeakMap();

    const element = document.getElementById(‘example’);

    wm.set(element, ‘some information’);
    wm.get(element) // “some information”
    注意:WeakMap 弱引用的只是键名,而不是键值。键值依然是正常引用

    下面代码中,键值obj会在WeakMap产生新的引用,当你修改obj不会影响到内部

    const wm = new WeakMap();
    let key = {};
    let obj = {foo: 1};

    wm.set(key, obj);
    obj = null;
    wm.get(key)
    // Object {foo: 1}

    展开全文
  • 是由一堆无序的、相关联的,且不重复的内存结构【数学中称为元素】组成的组合 字典 是一些元素的集合。每个元素有一个称作key 的域,不同元素的key 各不相同 区别? 共同点:集合、字典都可以存储不重复的值 不同点...

    故心故心故心故心小故冲啊



    在这里插入图片描述
    如果要用一句话来描述,我们可以说

    Set是一种叫做集合的数据结构,Map是一种叫做字典的数据结构

    什么是集合?什么又是字典?

    集合
    是由一堆无序的、相关联的,且不重复的内存结构【数学中称为元素】组成的组合

    字典
    是一些元素的集合。每个元素有一个称作key 的域,不同元素的key 各不相同

    区别?

    共同点:集合、字典都可以存储不重复的值
    不同点:集合是以[值,值]的形式存储元素,字典是以[键,值]的形式存储

    一、Set

    Set是es6新增的数据结构,类似于数组,但是成员的值都是唯一的,没有重复的值,我们一般称为集合
    Set本身是一个构造函数,用来生成 Set 数据结构

    增删改查

    Set的实例关于增删改查的方法:

    • add()

    • delete()

    • has()

    • clear()

    add()
    添加某个值,返回 Set 结构本身
    当添加实例中已经存在的元素,set不会进行处理添加

    s.add(1).add(2).add(2); // 2只被添加了一次
    

    delete()
    删除某个值,返回一个布尔值,表示删除是否成功

    s.delete(1)
    

    has()
    返回一个布尔值,判断该值是否为Set的成员

    s.has(2)
    

    clear()
    清除所有成员,没有返回值

    s.clear()
    

    遍历

    Set实例遍历的方法有如下:

    关于遍历的方法,有如下:

    • keys():返回键名的遍历器
    • values():返回键值的遍历器
    • entries():返回键值对的遍历器
    • forEach():使用回调函数遍历每个成员
      Set的遍历顺序就是插入顺序
      keys方法、values方法、entries方法返回的都是遍历器对象
    let set = new Set(['red', 'green', 'blue']);
    
    for (let item of set.keys()) {
      console.log(item);
    }
    // red
    // green
    // blue
    
    for (let item of set.values()) {
      console.log(item);
    }
    // red
    // green
    // blue
    
    for (let item of set.entries()) {
      console.log(item);
    }
    // ["red", "red"]
    // ["green", "green"]
    // ["blue", "blue"]
    

    forEach()用于对每个成员执行某种操作,没有返回值,键值、键名都相等,同样的forEach方法有第二个参数,用于绑定处理函数的this

    let set = new Set([1, 4, 9]);
    set.forEach((value, key) => console.log(key + ' : ' + value))
    // 1 : 1
    // 4 : 4
    // 9 : 9
    

    扩展运算符和Set 结构相结合实现数组或字符串去重

    // 数组
    let arr = [3, 5, 2, 2, 5, 5];
    let unique = [...new Set(arr)]; // [3, 5, 2]
    
    // 字符串
    let str = "352255";
    let unique = [...new Set(str)].join(""); // ""
    

    实现并集、交集、和差集

    let a = new Set([1, 2, 3]);
    let b = new Set([4, 3, 2]);
    
    // 并集
    let union = new Set([...a, ...b]);
    // Set {1, 2, 3, 4}
    
    // 交集
    let intersect = new Set([...a].filter(x => b.has(x)));
    // set {2, 3}
    
    // (a 相对于 b 的)差集
    let difference = new Set([...a].filter(x => !b.has(x)));
    // Set {1}
    

    二、Map

    增删改查
    Map 结构的实例针对增删改查有以下属性和操作方法:

    • size 属性
    • set()
    • get()
    • has()
    • delete()
    • clear()

    size
    size属性返回 Map 结构的成员总数。

    const map = new Map();
    map.set('foo', true);
    map.set('bar', false);
    
    map.size // 2
    

    set()
    设置键名key对应的键值为value,然后返回整个 Map 结构

    如果key已经有值,则键值会被更新,否则就新生成该键

    同时返回的是当前Map对象,可采用链式写法

    const m = new Map();
    
    m.set('edition', 6)        // 键是字符串
    m.set(262, 'standard')     // 键是数值
    m.set(undefined, 'nah')    // 键是 undefined
    m.set(1, 'a').set(2, 'b').set(3, 'c') // 链式操作
    

    get()
    get方法读取key对应的键值,如果找不到key,返回undefined

    
    const m = new Map();
    
    const hello = function() {console.log('hello');};
    m.set(hello, 'Hello ES6!') // 键是函数
    
    m.get(hello)  // Hello ES6!
    

    has()
    has方法返回一个布尔值,表示某个键是否在当前 Map 对象之中

    const m = new Map();
    
    m.set('edition', 6);
    m.set(262, 'standard');
    m.set(undefined, 'nah');
    
    m.has('edition')     // true
    m.has('years')       // false
    m.has(262)           // true
    m.has(undefined)     // true
    

    delete()
    delete方法删除某个键,返回true。如果删除失败,返回false

    const m = new Map();
    m.set(undefined, 'nah');
    m.has(undefined)     // true
    
    m.delete(undefined)
    m.has(undefined)       // false
    

    clear()
    clear方法清除所有成员,没有返回值

    let map = new Map();
    map.set('foo', true);
    map.set('bar', false);
    
    map.size // 2
    map.clear()
    map.size // 0
    

    遍历

    Map结构原生提供三个遍历器生成函数和一个遍历方法:

    • keys():返回键名的遍历器
    • values():返回键值的遍历器
    • entries():返回所有成员的遍历器
    • forEach():遍历 Map 的所有成员

    遍历顺序就是插入顺序

    const map = new Map([
      ['F', 'no'],
      ['T',  'yes'],
    ]);
    
    for (let key of map.keys()) {
      console.log(key);
    }
    // "F"
    // "T"
    
    for (let value of map.values()) {
      console.log(value);
    }
    // "no"
    // "yes"
    
    for (let item of map.entries()) {
      console.log(item[0], item[1]);
    }
    // "F" "no"
    // "T" "yes"
    
    // 或者
    for (let [key, value] of map.entries()) {
      console.log(key, value);
    }
    // "F" "no"
    // "T" "yes"
    
    // 等同于使用map.entries()
    for (let [key, value] of map) {
      console.log(key, value);
    }
    // "F" "no"
    // "T" "yes"
    
    map.forEach(function(value, key, map) {
      console.log("Key: %s, Value: %s", key, value);
    });
    

    三、WeakSet 和 WeakMap

    WeakSet

    创建WeakSet实例

    const ws = new WeakSet();
    

    WeakSet可以接受一个具有 Iterable接口的对象作为参数

    const a = [[1, 2], [3, 4]];
    const ws = new WeakSet(a);
    // WeakSet {[1, 2], [3, 4]}
    

    在API中WeakSet与Set有两个区别:

    • 没有遍历操作的API
    • 没有size属性

    WeackSet只能成员只能是引用类型,而不能是其他类型的值

    let ws=new WeakSet();
    
    // 成员不是引用类型
    let weakSet=new WeakSet([2,3]);
    console.log(weakSet) // 报错
    
    // 成员为引用类型
    let obj1={name:1}
    let obj2={name:1}
    let ws=new WeakSet([obj1,obj2]); 
    console.log(ws) //WeakSet {{…}, {…}}
    

    WeakSet里面的引用只要在外部消失,它在 WeakSet里面的引用就会自动消失

    WeakMap

    WeakMap结构与Map结构类似,也是用于生成键值对的集合

    在API中WeakMap与Map有两个区别:

    • 没有遍历操作的API
    • 没有clear清空方法
    // WeakMap 可以使用 set 方法添加成员
    const wm1 = new WeakMap();
    const key = {foo: 1};
    wm1.set(key, 2);
    wm1.get(key) // 2
    
    // WeakMap 也可以接受一个数组,
    // 作为构造函数的参数
    const k1 = [1, 2, 3];
    const k2 = [4, 5, 6];
    const wm2 = new WeakMap([[k1, 'foo'], [k2, 'bar']]);
    wm2.get(k2) // "bar"
    

    WeakMap只接受对象作为键名(null除外),不接受其他类型的值作为键名

    const map = new WeakMap();
    map.set(1, 2)
    // TypeError: 1 is not an object!
    map.set(Symbol(), 2)
    // TypeError: Invalid value used as weak map key
    map.set(null, 2)
    // TypeError: Invalid value used as weak map key
    

    WeakMap的键名所指向的对象,一旦不再需要,里面的键名对象和所对应的键值对会自动消失,不用手动删除引用

    举个场景例子:
    在网页的 DOM 元素上添加数据,就可以使用WeakMap结构,当该 DOM 元素被清除,其所对应的WeakMap记录就会自动被移除

    const wm = new WeakMap();
    
    const element = document.getElementById('example');
    
    wm.set(element, 'some information');
    wm.get(element) // "some information"
    

    注意:WeakMap 弱引用的只是键名,而不是键值。键值依然是正常引用

    下面代码中,键值obj会在WeakMap产生新的引用,当你修改obj不会影响到内部

    const wm = new WeakMap();
    let key = {};
    let obj = {foo: 1};
    
    wm.set(key, obj);
    obj = null;
    wm.get(key)
    // Object {foo: 1}
    

    参考文献

    https://es6.ruanyifeng.com/#docs/set-map

    展开全文
  • 6.5 排列与组合的推广

    2021-01-10 14:27:40
    这个怎么理解呢,当我们允许选择重复值时,其实就是在其中允许加入空值,这样的空值最多允许加入(r-1)位,因为全部的空值在之前的选项中有,如下图所示: 部分重复的排列 简单来说就是不是所有值都可以重复,比如...

    6.5 排列与组合的推广

    有重复的排列

    当具有n个元素的集合允许重复的r位排列时,排列数是 n^r

    比如以5个字母为总数的英语单词数量最多是:5^26

    有重复的组合

    当具有n个元素的集合允许重复的r位组合时,组合总数是 C(n+r-1,r)=C(n+r-1,n-1)

    这个怎么理解呢,当我们允许选择重复值时,其实就是在其中允许加入空值,这样的空值最多允许加入(r-1)位,因为全部的空值在之前的选项中有,如下图所示:

    部分重复的排列

    简单来说就是不是所有值都可以重复,比如Apple这个单词有多少种排列方式,你就不能简单的用5^5来计算了,因为其中有重复项。

    设类型1的相同物体有n1个,类型2的相同物体有n2个。。。。。。类型k的相同物体有nk个,那么n个物体的不同排列数是

    n!(n1)!(n2)!(nk)! \frac{n!}{(n_1)!(n_2)! \cdots (n_k)!}

    证明:
    1C(n,n1)2C(nn1,n2)kC(nn1n2n3nnk1,nk)C(n,n1)C(nn1,n2)C(nn1n2n3nnk1,nk)=n!(nn1)!n1!(nn1)!(nn1n2)!n2!=n!(n1)!(n2)!(nk)! 对类型1的物体,其有 C(n,n_1)种组合,\\ 对类型2的物体,其有 C(n-n_1,n_2)种组合,\\ \vdots \\ 对类型k的物体,其有 C(n-n_1-n_2-n_3 \cdots -{n}_{n_k-1},n_k)种组合 \\ 所以总共的排列总数是\\ C(n,n_1) \cdot C(n-n_1,n_2) \cdots C(n-n_1-n_2-n_3 \cdots -{n}_{n_k-1},n_k) \\ = \frac{n!}{(n-n_1)!{n}_{1}!} \cdot \frac{(n-n_1)!}{(n-n_1-n_2)!{n}_{2}!} \cdots \\ = \frac{n!}{(n_1)!(n_2)! \cdots (n_k)!}

    变形

    可辨别的物体与可辨别的盒子

    例如,把52张牌,分给4个人,每个人5张牌,问有多少种方式。这个问题和上面部分重复的排列是一样的。只是有一点,那就是最后需要剩下32张牌,即最后一个类型的值是32.


    nk使niin!(n1)!(n2)!(nk)! 把n个不同的物体分配到k个不同的盒子使得n_i个物体放入盒子i的方式数等于\\ \frac{n!}{(n_1)!(n_2)! \cdots (n_k)!}

    不可辨别的物体与可辨别的盒子

    这个啥意思呢?比如将相同的10个小球放入编号1-8的桶中,共有多少种放法,是不是就是上面的有重复的组合,所以结论就是:
    C(10+81,8) C(10+8-1,8)

    可辨别的物体与不可辨别的盒子

    这个比较麻烦,那就是将10个不同的小球,放到4个相同的桶中,共有多少种放法。

    这个等到《第八章:高级计数》的时候再去介绍。

    不可辨别的物体和不可辨别的盒子

    这个就是将10个相同的小球,放到4个相同的桶中,共有多少种放法。

    这个换一种问法就是10可以拆分成多少种4个数的加法,暂时好像只有列举法:

    • 10=10+0+0+0
    • 10=1+9+0+0
    • 10=1+8+1+0
    展开全文
  • 算法中的排列与组合

    千次阅读 2019-03-24 15:05:45
    排列组合公式 不含重复元素的排列组合 含有重复元素的排列组合 ...怎么理解上面的定义呢,举个例子,冰淇淋有3种口味可以选择,我可以选择3种相同口味,也可以选择不同口味,每次选择即可相同也可...

    排列组合公式

    不含重复元素的排列组合

    在这里插入图片描述

    含有重复元素的排列组合

    如果产生的组合和排列可以包含有重复的元素,其实这类问题在苏荷数学上是多种集的排列和组合问题。

    多重集的排列问题

    1. 设S是有k种不同类型对象的多重集合,每个元素都有无限的重复数。那么s的r排列数目是krk^r.
      需要注意的是,只要每种元素的数目大于r,对于r组合来说就是无限多的。
      怎么理解上面的定义呢,举个例子,冰淇淋有3种口味可以选择,我可以选择3种相同口味,也可以选择不同口味,每次选择即可相同也可不相同。再举个例子抛硬币3次,很显然,可能会出现3次都是正面,硬币出现正反面是可重复的。
      这很好理解,一次有k种选择,第二次有k∗k种选择,……,第r次有krk^r种选择。
      剑指offer中的面试题17.打印从1到最大的n位数,就是这类问题。可以假设一共有0-9十种对象,每种对象都有无数个(无数个和大于等于n个一样,因为排列的最长长度是n),n位数就是十种对象的n排列,一共有10n10^n种。其实很好理解,第一位数字有10种选择,第二位也有10种选择,… 第n位也有10种选择。
    2. 设s是多重集合,有k种类型的对象,且每种类型的有限重复数是n1,n2,……,nk。s的大小是n=n1+n2+n3+……+nk。那么s的全排列数目等于:result=n!(n1!n2!nk!)result=\frac{n!}{(n1!*n2!*……*nk!)}
      例子:词MISSISSIPPI中字母的排列数是?
      分析:词含有的字母总个数是11,M:1,I:4,S:4,P:2。所以result=11!/(1*4!*4!*2!).

    多重集合的组合

    设S是有k种类型对象的多重集合,每种元素均有无限的重复数。那么S的r组合的个数等于:C(r+k-1,r)==C(r+k-1,k-1).
    需要注意的是,只要每种元素的数目大于r,对于r组合来说就是无限多的。
    证明:S任何r组合一定呈现{x1a1,x2a2,……,xk*ak}的组合形式。x1+x2+……+xk=r.先将x系列数字分割成k部分,这样有了r+k-1个元素(要插入k-1个隔板,可以看做值为0的元素),用这些元素组成的一个r排列就是解。那么这样的排列个数是(r+k-1)!/(k-1)!/r!(除以同类型值的排列),即C(r+k-1,r)。

    LeetCode:46. 全排列

    题目描述:
    给定一个没有重复数字的序列,返回其所有可能的全排列。
    示例:
    输入: [1,2,3]
    输出:
    [
    [1,2,3],
    [1,3,2],
    [2,1,3],
    [2,3,1],
    [3,1,2],
    [3,2,1]
    ]
    代码:

    class Solution {
    public:
        //深度优先遍历加回溯:这种方法只适合与没有重复元素的数组,但是可以这样处理,如果vv中已经存在这个字符串则不添加
        vector<vector<int>> permute(vector<int>& nums) {
            vector<vector<int>> vv;
            vector<bool> marked(nums.size(),false);
            vector<int> v;
            permulate(vv, v, nums, marked);
            return vv;
            
        }
        void permulate(vector<vector<int>> &vv, vector<int> &v, vector<int>& nums, vector<bool>& marked){
            if(v.size() == nums.size()){
                vector<int> rv(v.begin(),v.end());
                vv.push_back(rv);
                return;
            }
            for(int i = 0; i < nums.size(); i++){
                if(marked[i])
                    continue;
                v.push_back(nums[i]);
                marked[i] = true; 
                permulate(vv, v, nums, marked);
                marked[i] = false; //回溯
                v.erase(v.end()-1);
            }
            
        }
    };
    

    组合

    上面是求数组的全排列,我们同时思考一下数组的组合怎么求。思路来自剑指offer:面试题 38. 字符串的排列后的相关拓展。
    思路解析:
    首先需要弄清楚排列和组合的区别,对于字符串"abc",它的全排列包括:abc、acb、bac、bca、cab、cba。但它的所有组合为:a、b、c、ab、ac、bc、abc。也就是说一个长度为n的字符串,它的组合包括长度为1~n的所有字符子串(忽略顺序)。下面具体探讨一下字符串的组合问题的实现。
    在求长度为n的字符串的组合时,我们要遍历从1到n所有的子串,当求长度为m(1≤m≤n)的组合时,可以把那个字符分成两部分:第一个字符和其余所有的字符。此时就分为两种情况了:
    (1)组合包含第一个字符,则下一步在剩余字符里选取m-1个字符。
    (2)组合不包含第一个字符,则下一步在剩余的n-1个字符中选取m个字符。
    很明显,这个用递归实现比较清晰。总的来说,可以把求n个字符组成对的长度为m的组合问题分成两个子问题,即分别求n-1个字符中长度为m-1的组合;以及求n-1个字符中长度为m的组合。

    class Solution {
    public:
    
    	vector<vector<int>> combination(vector<int>& nums) {
    		vector<vector<int>> vv;
    		vector<int> v;
    		if (nums.size() == 0)
    			return vv;
    		for (int i = 1; i <= nums.size(); i++){
    			combination(vv, v, nums, i, 0);
    		}
    		return vv;
    
    	}
    	void combination(vector<vector<int>> &vv, vector<int> &v, vector<int>& nums, int len, int start){
    		if (len == 0){
    			vector<int> rv(v.begin(), v.end());
    			vv.push_back(rv);
    			return;
    		}
    		if (start == nums.size())
    			return;
    		v.push_back(nums[start]);
    		combination(vv, v, nums, len-1,start+1);
    		v.pop_back();
    		combination(vv, v, nums, len , start+1);
    	}
    };
    

    剑指offer:面试题 38. 字符串的排列

    题目描述
    输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
    输入描述:
    输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
    解题思路:
    链接:https://www.nowcoder.com/questionTerminal/fe6b651b66ae47d7acce78ffdd9a96c7
    递归法,问题转换为先固定第一个字符,求剩余字符的排列;求剩余字符排列时跟原问题一样。
    (1) 遍历出所有可能出现在第一个位置的字符(即:依次将第一个字符同后面所有字符交换);
    (2) 固定第一个字符,求后面字符的排列(即:在第1步的遍历过程中,插入递归进行实现)。
    需要注意的几点:
    (1) 先确定递归结束的条件,例如本题中可设begin == str.size() - 1;
    (2) 形如 aba 或 aa 等特殊测试用例的情况,vector在进行push_back时是不考虑重复情况的,需要自行控制;
    (3) 输出的排列可能不是按字典顺序排列的,可能导致无法完全通过测试用例,考虑输出前排序,或者递归之后取消复位操作。
    在这里插入图片描述

    #include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    using namespace std;
    class Solution {
    public:
        vector<string> Permutation(string str) {
            vector<string> a;
            if(str.empty())
                return a;
            Permutation(a,str,0);
            sort(a.begin(),a.end());//按照字典序输出
            return a;
         }
         void Permutation(vector<string> &array, string str, int begin)//遍历第begin位的所有可能性
         {
            //一次遍历的结束条件
            if(begin == str.size()-1)
            {
                array.push_back(str);
            }
            for(int i=begin;i<str.size();i++)
            {
                if(i!=begin && str[i] == str[begin])
                {
                    continue;//有与begin位重复的字符串不进行交换,跳过
                }
                swap(str[i],str[begin]);
                //当i==begin时,也要遍历其后面的所有字符
                //当i!=begin时,先交换,使第begin位取到不同的可能字符,再遍历后面的字符
                Permutation(array,str,begin+1);
                swap(str[i],str[begin]);//为了防止重复的情况,还需要将begin处的元素重新换回来
            }
         }
    };
    int main()
    {
        string a = "abc";
        Solution s;
        vector<string> b;
        b = s.Permutation(a);
        for(int i=0;i<b.size();i++)
        {
            cout<<b[i]<<endl;
        }
        return 0;
    }
    

    懒得敲了,代码来自:27、剑指offer–字符串的排列.
    这种解法和上面的那道全排列的题是两种,解全排列的方法。

    剑指offer中的面试题17.打印从1到最大的n位数

    输入数字n,按顺序打印出从1到最大的n位十进制数。比如输入3,则打印出1、2、3一直到最大的3位数999。
    注意不能直接打印输出,因为当n比较大的时候会溢出。
    为了解决大数问题,可以使用字符串模拟加法。代码可以参考:打印从1到最大的n位数.
    除此之外,还有一种解法就是多重集的全排列的解法。

    void Print1ToMaxofNDigits(int n)
    {
        if (n <= 0)
            return;
    
        char *number = new char[n + 1];
        number[n] = '\0';
    
        for (int i = 0; i < 10; ++i){
            number[0] = i + '0';
            Print1ToMaxofNDigitsRecursively(number,n,0);
        }
    
        delete[]number;
    }
    
    void Print1ToMaxofNDigitsRecursively(char* number, int length, int index)
    {
        if (index == length - 1)
        {
            PrintNumber(number);
            return;
        }
    
        for (int i = 0; i < 10; ++i){
            number[index + 1] = i + '0';
            Print1ToMaxofNDigitsRecursively(number, length, index + 1);
        }
    }
    
    //打印数
    void PrintNumber(char *number)
    {
        bool isBeginning0 = true;
        int nLength = strlen(number);
    
        for (int i = 0; i < nLength; ++i){
            if (isBeginning0 && number[i] != '0')
                isBeginning0 = false;
    
            if (!isBeginning0)
                printf("%c", number[i]);
        }
    
        printf("\t");
    }
    
    

    懒得敲了,代码来自:打印从1到最大的n位数.

    字符串的组合

    参考文章:

    1. 排列组合详解
    2. 多重集合的排列与组合
    展开全文
  • 排列组合 permutations and combinations

    千次阅读 2013-01-21 18:27:47
    推荐《程序员的数学》中排列组合...为此必须理解计数对象具有怎么样的特性和结构。 一个例子,内存中排列着要处理的100个数据。从第一个开始依次编号为0号,1号。。。那么最后1个数据的编号是多少呢? 答案:99。
  • 求问这里的互不相同无重复数字该怎么理解啊?像出现1111这种和1213这种的吗?还是其实是指111这种,有点懵 int main() 8 { 9 int g,s,b; 10 for(g=1;g;g++) 11 { 12 for(s=1;s;s++) 13 { 14 for(b=1;b;b++) ...
  • Spring是一个很厉害的框架,它帮助程序员做了很多繁琐且重复的工作,帮助程序员从繁杂的配置文件中解脱出来,那么它到底是怎么实现一系列神奇的功能呢? 首先springBoot的入口类上需要加一个注解@SpringBoot...
  • 同一台机器的同一个端口只可以被一个进程使用,一般用于tcp,或者udp。 那一个进程使用同一个端口同时监听tcp、...端口的唯一性的标识不是端口号,而是端口号和协议名称的组合,应用程序和协议寻址时就是靠的这个组合
  • 我也不知道机子是怎么产生的,英文叫rand,我也无法知道什么是真正的随机事件,感觉这世界上所有的事情当无法解释的时候,那就叫随机吧,当 我们掌握或可以彻底解释的话,它就不是随机的,之所以随机,是因为一点规律...
  • ”所以,我就毫不犹豫的列下这4个基本原则,因为它们“怎么强调都不过分”: 对比(Contrast) 千万不要畏畏缩缩。 如果两个项不完全相同,就应当使之不同,而且应当是截然不同。 在页面上增加对比能吸引人的眼球...
  • 因为它们可以仅仅通过组合(composition)就能表达<code>is-a和<code>has-a的关系: <ul><li><code>Button是有特定属性(specific properties)的DOM<code><button>。</li><li>...
  • 一些例子中,会在宏参数前加逗号、引号、和@的复杂组合怎么理解这些组合呢?这里用实验的方法来研究它们的作用,而不管什么规则、原理。先枚举各种组合: 0 'x:引号 1 x:没有符合 2 ,x:逗号 3 ,,x:两...
  • 页面引入选择include or iframe?

    千次阅读 热门讨论 2016-10-23 19:42:21
    由于页面有重复的样式,所以,计划采用引用jsp的方式,减少代码量。起初我采用的iframe的方式先写了一个单独的common.jsp页面,然后再每一个功能页引入这个common.jsp页面。... 怎么理解?  代码上的组合就是这两
  • 今天有一个朋友(手动艾特文彬)问我,这道题该怎么理解,该怎么去得出答案,研究了一波,并开始总结算法篇的博客; 看题目博主感觉这是一道小学的数学题,但是可以使用python来解答。 1、分析步骤 1、我们假设每种...
  • hdu 1258 Sum It Up

    2017-11-08 14:15:24
    这几个数随机组合等于sum时,输出怎么组合的。 注意:不能有重复的 解题思路:用DFS深搜,这个我写的时候都把自己搞晕了,看了别人的思路才憋出来,屡思路就屡了半天,还是去重的地方理解不深,还是太水啊 ...
  • awk ‘! a[$0]++’ 去重

    2017-06-18 16:54:00
    a[$0]++’ 怎么理解? 这是一个非常经典的去重复项的awk语句,虽然短小,不过涉及到了不少知识点,下面一一解读: <1> :”!” 即非。 <2>:a[$0],以$0为数据下标,建立数组a <3>:a[$0]+...
  • awk 除重

    2014-12-15 09:40:14
    a[$0]++’ 怎么理解? 这是一个非常经典的去重复项的awk语句,虽然短小,不过涉及到了不少知识点,下面一一解读: :”!” 即非。 :a[$0],以$0为数据下标,建立数组a :a[$0]++,即给数组a赋值,a[$0]+=1 ...
  • 设计模式用于软件设计中对于对于代码的重复利用,以及使得软件设计更加灵活。  定义:一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。使用设计模式是为了可重用代码、让代码更容易被他人理解...
  • 你要怎么样在你的书包里放入组合起来价值最大的物品。简而言之,在有限的空间怎样搭配才可以装入最大价值的东西,并且物品不重复。 解决思路 穷举法:把所有的可能性都列举出来,然后一一对比,可以达到一个解决问题...
  • 1.2.8 对大数据平台中的元数据管理是怎么理解的,元数据收集管理体系是怎么样的,会对大数据应用有什么样的影响 1.2.9 你理解常见如阿里,和友商大数据平台的技术体系差异以及发展趋势和技术瓶颈,在存储和计算两...
  • 问题的抽象描述和怎样用一个具有一般意义的元素组合(类或对象组合)来解决这个问题。 效果(consequences) 描述了模式应用的效果及使用模式应权衡的问题。尽管我们描述设计决策时,并不总提到模式 效果,但它们...
  • 二十三种设计模式【PDF版】

    热门讨论 2011-05-30 14:13:49
    你也希望避免重复设计或尽可能少做重复设计。有经验的面向对象设计者会告诉你,要一下子就得到复用性和灵活性好的设计, 即使不是不可能的至少也是非常困难的。一个设计在最终完成之前常要被复用好几次,而且每一次...
  • ⚠️ 特别提示:已报名并完成集成学习(上)所有学习内容的同学不需要重复报名。直接报名集成学习(中)的同学需要自行完成集成学习(上)课程内容的学习。 学习目标 本次课程是由Datawhale集成学习小组内部成员...
  • Java面试宝典2010版

    2011-06-27 09:48:27
    9.所有部门之间的比赛组合 10.每个月份的发生额都比101科目多的科目 11.统计每年每月的信息 12.显示文章标题,发帖人、最后回复时间 13.删除除了id号不同,其他都相同的学生冗余信息 14.航空网的几个航班查询题...
  • 最新Java面试宝典pdf版

    热门讨论 2011-08-31 11:29:22
    9.所有部门之间的比赛组合 100 10.每个月份的发生额都比101科目多的科目 101 11.统计每年每月的信息 102 12.显示文章标题,发帖人、最后回复时间 103 13.删除除了id号不同,其他都相同的学生冗余信息 104 14.航空网的...
  • Java面试宝典-经典

    2015-03-28 21:44:36
    9.所有部门之间的比赛组合 100 10.每个月份的发生额都比101科目多的科目 101 11.统计每年每月的信息 102 12.显示文章标题,发帖人、最后回复时间 103 13.删除除了id号不同,其他都相同的学生冗余信息 104 14.航空网的...
  • 冰河写的这部《深入理解高并发编程》电子书全网已累计下载15W+!! 高并发场景下如何优化服务器的性能? ReadWriteLock怎么和缓存扯上关系了?! 一起进大厂系列 头条一面:Spring IOC容器中只存放单例Bean吗? ...

空空如也

空空如也

1 2 3 4
收藏数 80
精华内容 32
关键字:

重复组合怎么理解