LeetCode DayBackTracking パート 1

77. 組み合わせ

2 つの整数 n と k を指定すると、[1, n] の範囲から選択された k 個の数値の可能な組み合わせをすべて返します。

回答はどのような順序で返しても構いません。

例 1:

入力: n = 4、k = 2
出力: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
説明: 4 つの選択 2 = 合計 6 つの組み合わせがあります。
組み合わせには順序がないことに注意してください。つまり、[1,2] と [2,1] は同じ組み合わせとみなされます。
例 2:

入力: n = 1、k = 1
出力: [[1]]
説明: 1 つの選択 = 合計 1 つの組み合わせがあります。

制約:

1 1

間違ったコード

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> list = new ArrayList<>();

        List<Integer> nums = new ArrayList<>();

        backTracking(list,1,1,n,k,nums);

        return list;
    }

    public void backTracking(List<List<Integer>> list, int base,int size,int n, int k,List<Integer> nums)
    {
        if(size>k){
            list.add(new ArrayList<>(nums));
            return;
        }

        for(int i=base; base<n; i++ ){
            nums.add(i);
            backTracking(list,i+1,size+1,n,k,nums);
            nums.remove(nums.size()-1);
        }
    }

ただし、LeetCode でメモリ制限超過エラーが発生します

ここにはいくつかの間違いがあります。

1、ループ条件が間違っています。i を使用する必要がありますが、上記のコードでは終了評価条件として Base を使用しています。
図２の場合、正しい閾値はｎであり、ｉ＜ｎの場合、ｎが潜在的な組み合わせの要素である可能性を逃すことになる。

ファインコード

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> list = new ArrayList<>();

        List<Integer> nums = new ArrayList<>();

        backTracking(list,1,1,n,k,nums);

        return list;
    }

    public void backTracking(List<List<Integer>> list, int base,int size,int n, int k,List<Integer> nums)
    {
        if(size>k){
            list.add(new ArrayList<>(nums));
            return;
        }

        for(int i=base; i<=n; i++ ){
            nums.add(i);
            backTracking(list,i+1,size+1,n,k,nums);
            nums.remove(nums.size()-1);
        }
    }

    List<List<Integer>> list = new LinkedList<>();
    List<Integer> nums = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        backTracking(1,n,k);
        return list;
    }

    public void backTracking(int base, int n, int k)
    {
        if(nums.size()==k){
            list.add(new ArrayList<>(nums));
            return;
        }

        for(int i=base; i<=n; i++ ){
            nums.add(i);
            backTracking(i+1,n,k);
            nums.removeLast();
        }
    }

ここにはグローバル パス リストのサイズに直接依存するいくつかの違いがありますが、ここでは数値のサイズが正しい答えです!!!
サイズの前は、パス リストに最後の要素を追加していないため、正しい答えではありません。

グローバル変数を採用するとパフォーマンスの低下につながる可能性があるようですか?

これはより一般的な方法ですが、質問では <= 9 および >= 1 の数値のみを使用するように求められています。

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> path = new LinkedList<>();
        backTracking(list, path, 1, k, n);
        return list;

    }

    public void backTracking(List<List<Integer>>list,  List<Integer> path, 
    int start, int k, int n){
        if(path.size() == k){
            int sum = path.stream().reduce(0,Integer::sum);
            if(sum == n){
                list.add(new ArrayList<>(path));
            }
        }
        for(int i=start ; i<=n; i++){
            int sum = path.stream().reduce(0,Integer::sum);
            if(sum>n){
                break;
            }
            path.add(i);
            backTracking(list,path,i+1, k,n );
            path.remove(path.size()-1);
        }
    }

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> path = new LinkedList<>();
        backTracking(list, path, 1, k, n);
        return list;

    }

    public void backTracking(List<List<Integer>>list,  List<Integer> path, 
    int start, int k, int n){
        if(path.size() == k){
            int sum = path.stream().reduce(0,Integer::sum);
            if(sum == n){
                list.add(new ArrayList<>(path));
            }
        }
        for(int i=start ; i<=9; i++){
            int sum = path.stream().reduce(0,Integer::sum);
            if(sum>n){
                break;
            }
            path.add(i);
            backTracking(list,path,i+1, k,n );
            path.remove(path.size()-1);
        }
    }

合計のためにいくつかの冗長な計算が使用されているようです

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> path = new LinkedList<>();
        backTracking(list, path, 1, k, n, 0);
        return list;

    }

    public void backTracking(List<List<Integer>>list,  List<Integer> path, 
    int start, int k, int n, int sum){
        if(path.size() == k){
            if(sum == n){
                list.add(new ArrayList<>(path));
            }
        }
        for(int i=start ; i<=9; i++){
            sum += i;
            if(sum>n){
                break;
            }
            path.add(i);
            backTracking(list,path,i+1, k,n, sum);
            path.remove(path.size()-1);
            sum -= i;
        }
    }

17. 電話番号の文字の組み合わせ

2 から 9 までの数字を含む文字列を指定すると、その数字が表すことができるすべての文字の組み合わせを返します。任意の順序で答えを返します。

数字と文字のマッピング (電話のボタンと同じように) を以下に示します。 1 はどの文字にもマップされないことに注意してください。

例 1:

入力: 桁数 = "23"
出力: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
例 2:

入力: 数字 = ""
出力: []
例 3:

入力: 数字 = "2"
出力: ["a","b","c"]

制約:

0 数字[i]は範囲['2', '9']内の数字です。

    public List<String> letterCombinations(String digits) {
        List<String> list = new LinkedList<>();
        if(digits.length() == 0){
            return list;
        }
        String[] arr = {
            "",
            "",
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"
        };
        backTracking(list, new StringBuilder(), 0, digits, arr);
        return list;

    }

    public void backTracking(List<String> list, StringBuilder s, int start, String digits, String[] arr){
        if(start == digits.length()){
            list.add(s.toString());
            return;
        }

        int num = digits.charAt(start)-'0';
        String button = arr[num];
        for(int i=0; i<button.length(); i++){
            s.append(button.charAt(i));
            backTracking(list, s, start+1, digits, arr);
            s.setLength(s.length()-1);
        }
    }

以上がLeetCode DayBackTracking パート 1の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。