首页 > 代码库 > [LeetCode] Combinations

[LeetCode] Combinations

2024-09-13 15:17:15   217人阅读

题目： Combinations

1-n个数字中找k个数字的所有不同组合。

思路：从1-k开始，每次从k开始，让最后面的元素加1，超过了，就让前面一个元素加1，后面一个元素变为前面一个元素的值加1.

循环知道所有元素都没有超过，则是一种不同的情况。

例如：n = 6，k = 4;

1234->1235->1236->1245->1246->1256->1345->1346->1356->1456

->2345->...->3456

package com.example.medium;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class Combinations {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> list = new LinkedList<>();
        int indexs[] = new int[k];
        int j = 0;
        for(int i = 0;i < k;i++){
            indexs[i] = i;
        }
        while(indexs[0] <= n - k){
            List<Integer> item = new ArrayList<Integer>(k);
            for(int i = 0;i <k;i++){//添加当前的k个元素
                item.add(i, indexs[i] + 1);
            }
                list.add(item);
                j = k - 1;
                indexs[j]++;//最后一个元素加一
                while(indexs[j] >= n - k + j + 1){//超过了n则倒数第二个元素加一,然后判断是否超过n,如此循环
                    j--;
                    if(j < 0)break;
                    indexs[j]++;
                }
                for(;j >= 0 && j < k - 1;j++)
                    indexs[j + 1] = indexs[j] + 1;
        }
        return list;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        List<List<Integer>> list = new Combinations().combine(17, 5);
        Iterator<List<Integer>> iterator = list.iterator();
        while(iterator.hasNext()){
            List<Integer> item = iterator.next();
            for(int i = 0;i < item.size();i++)
                System.out.print(item.get(i) + " ");
            System.out.println();
        }

    }

}

 

[LeetCode] Combinations


联系
我们