Square Leetcode 솔루션에 성냥개비

난이도 중급
자주 묻는 질문 Microsoft
배열 역 추적 비트 조작 비트 마스크 동적 프로그래밍조회수 48

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

정수 배열이 주어집니다. matchsticks 어디에 matchsticks[i] 의 길이입니다 ith 성냥개비. 사용하고 싶은 모든 성냥개비 하나의 정사각형을 만들기 위해. 너 깨지면 안된다 아무 막대기나 연결할 수 있으며 각 성냥개비를 사용해야 합니다. 정확히 한 번.

반품 true 이 정사각형을 만들 수 있다면 false 그렇지 않으면.

Square Leetcode 솔루션에 성냥개비

입력:

 matchsticks = [1,1,2,2,2]

출력:

 true

설명 :

 You can form a square with length 2, one side of the square came two sticks with length 1.

 

입력:

 matchsticks = [3,3,3,3,4]

출력:

 false

설명 :

 You cannot find a way to form a square with all the matchsticks.

 

접근

생각

여기서 주요 아이디어는 다음을 사용하여 모든 가능성을 취하는 것입니다. 역 추적. 정사각형에 4개의 모서리가 있으므로 i번째 성냥개비는 4개의 선택을 가질 수 있으므로 모든 선택을 탐색할 수 있으며 전체 성냥개비 배열을 순회한 후 4개의 변의 길이와 이들이 모두 목표 값과 같은지 여부를 확인할 수 있습니다. 그렇다면 true, 그렇지 않으면 false를 반환합니다.

위의 솔루션은 연장되고 기하급수적인 시간 복잡도를 갖습니다. 더 큰 성냥개비를 더 일찍 처리하도록 성냥개비 배열을 내림차순으로 정렬하여 이 속도를 상당히 높일 수 있습니다. 솔루션이 없으면 더 긴 성냥개비를 시도하면 먼저 부정적인 결론.

또한 모든 스틱 길이의 합이 4의 배수인지 여부와 같은 경우를 추가하여 솔루션의 런타임을 개선할 수 있습니다.

또한 막대기 길이가 sum/4보다 엄격하게 크면 성냥개비를 만들 수 없습니다.

암호

Square C++ 솔루션에 대한 성냥개비:

class Solution {
public:
    bool calc(int pos,vector<int> &nums,vector<long long int> &sides,long long int &tar){
        if(pos == nums.size()){
            if(sides[0]==tar && sides[1]==tar && sides[2]==tar && sides[3]==tar){
                return true;
            }
            return false;
        }
        
        for(int i=0;i<4;i++){
            if(sides[i] + nums[pos] <= tar){
                sides[i] += nums[pos];
                if(calc(pos+1,nums,sides,tar)){return true;}
                sides[i] -= nums[pos];
            }
        }
        
        return false;
    }
    bool makesquare(vector<int>& matchSticks) {
        
        long long int sum = 0;
        int n = matchSticks.size();
        for(int i=0;i<n;i++){
            sum += matchSticks[i];
        }
        
        if(sum%4){return false;}
        // If sum is not divisible by 4 return false.
        if(n<4){return false;}
        // if number of matchsticks are less than 4 then square cannot be formed return false.
        long long int tar = sum/4;
        
        vector<long long int> sides(4,0);
        //To store the length od each side.
        
        
        sort(matchSticks.begin(),matchSticks.end(),greater<int>());
        //sorting matchSticks in decreasing order.
        
        return calc(0,matchSticks,sides,tar);
    }
};

Square Java 솔루션에 대한 성냥개비:

import java.util.HashMap;
import java.util.Collections;

class Solution {
    public List<Integer> nums;
    public int[] sums;
    public int possibleSquareSide;

    public Solution() {
        this.sums = new int[4];
    }

    // Depth First Search function.
    public boolean dfs(int index) {

        // If we have exhausted all our matchsticks, check if all sides of the square are of equal length
        if (index == this.nums.size()) {
            return sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == sums[3];
        }

        // Get current matchstick.
        int element = this.nums.get(index);

        // Try adding it to each of the 4 sides (if possible)
        for(int i = 0; i < 4; i++) {
            if (this.sums[i] + element <= this.possibleSquareSide) {
                this.sums[i] += element;
                if (this.dfs(index + 1)) {
                    return true;
                }
                this.sums[i] -= element;
            }
        }

        return false;
    }

    public boolean makesquare(int[] nums) {
        // Empty matchsticks.
        if (nums == null || nums.length == 0) {
            return false;
        }

        // Find the perimeter of the square (if at all possible)
        int L = nums.length;
        int perimeter = 0;
        for(int i = 0; i < L; i++) {
            perimeter += nums[i];
        }

        this.possibleSquareSide =  perimeter / 4;
        if (this.possibleSquareSide * 4 != perimeter) {
            return false;
        }

        // Convert the array of primitive int to ArrayList (for sorting).
        this.nums = Arrays.stream(nums).boxed().collect(Collectors.toList());
        Collections.sort(this.nums, Collections.reverseOrder());
        return this.dfs(0);
    }
}

 

Matchsticks to Square Leetcode 솔루션의 복잡성 분석

시간 복잡성

솔루션의 전체 시간 복잡도는 4^n입니다. 재귀의 각 단계에서 4개의 선택이 있으므로 O(4^N)이 최악의 시간 복잡도입니다. 솔루션의 런타임은 기하급수적입니다.

공간 복잡성

사용된 재귀 스택 공간은 O(n)이며, 여기서 n은 성냥개비의 수이므로 전체 공간 복잡도는 O(n)입니다.

균열 시스템 설계 인터뷰
Translate »