LeetCode DayBackTracking 第 1 部分

77. 組合

給定兩個整數 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 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 出現 Memory Limit Exceeded 錯誤

這裡有一些錯誤。

1，循環條件錯誤，應該使用i，但上面的程式碼使用base作為結束條件。
如圖2所示，正確的閾值可以是n，如果i＜n，則將錯過當n是潛在組合的元素時的可能性。

精細程式碼

    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();
        }
    }

這裡有一些差異，我們可以直接依賴全域路徑列表的大小，但這裡 nums 的大小是正確的答案!!!
之前的大小不是正確的答案，因為我們還沒有將最後一個元素加入路徑清單。

貌似採用全域變數會導致效能下降？

這是一種更通用的方法，但問題是我們只使用 = 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);
        }
    }

sum 似乎使用了一些冗餘計算

    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 digits[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中文網其他相關文章！