77、k个数字组合

leetcode

Created At : 2020-07-26 00:19

Count:500 Views 👀 :

示例:

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

代码

递归回溯

class Solution {
    List<List<Integer>> res = new LinkedList<List<Integer>>();
    public List<List<Integer>> combine(int n, int k) {
        // 递归回溯，深度眼优先搜索，
        LinkedList<Integer> temp = new LinkedList<Integer>();
        combine(n,k,1,temp);
        return res;
    }
    
    private void combine(int n,int k,int index,LinkedList<Integer> temp){
        if (temp.size() == k) {
            res.add(new LinkedList<Integer>(temp));
            return;// 可以不返回
        }
        for (int i = index;i <= n;i++) {
            temp.add(i);
            combine(n,k,i+1,temp);
            temp.removeLast();
        }
    }
}
// 官网解答 
class Solution {
  List<List<Integer>> output = new LinkedList();
  int n;
  int k;

  public void backtrack(int first, LinkedList<Integer> curr) {
    // if the combination is done
    if (curr.size() == k)
      output.add(new LinkedList(curr));

    for (int i = first; i < n + 1; ++i) {
      // add i into the current combination
      curr.add(i);
      // use next integers to complete the combination
      backtrack(i + 1, curr);
      // backtrack
      curr.removeLast();
    }
  }

  public List<List<Integer>> combine(int n, int k) {
    this.n = n;
    this.k = k;
    backtrack(1, new LinkedList<Integer>());
    return output;
  }
}

// 作者：LeetCode
// 链接：https://leetcode-cn.com/problems/combinations/solution/zu-he-by-leetcode/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

字典序列组合

class Solution {
  public List<List<Integer>> combine(int n,int k) {
    // 初始化字典数组
    LinkedList<Integer> nums = new LinkedList<Integer>();
    for (int i = 1;i < k + 1;++i) {
      nums.add(i);
    }
    nums.add(n+1);// 哨兵

    List<List<Integer>> res = new ArrayList<List<Integer>>();
    int j = 0;
    while(j < k) {
      // 获取满足要求的子组合
      res.add(new LinkedList(nums,subList(0,k)));
      j = 0;
      // 循环判断是否都连续
      while ((j < k) && (nums.get(j + 1) == nums.get(j) + 1)){
        nums.set(j,j++ + 1);// 更改响应位置的数字 较快
      }
      nums.set(j, nums.get(j) + 1);// 更换开始数字
    }
    return res;
  }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com