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에서 메모리 제한 초과 오류가 발생합니다

여기에는 일부 오류가 있습니다.

1, 루프 조건이 잘못되었습니다. i를 사용해야 하는데 위 코드에서는 최종 평가 조건으로 base를 사용합니다.
도 2에서, 올바른 임계값은 n일 수 있고 i

미세한 코드

    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 <= 숫자.길이 <= 4
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);
        }
    }
</p>

위 내용은 LeetCode DayBackTracking 파트 ​​1의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!