맥시 멀 스퀘어

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 AppDynamics Apple Facebook 구글 IBM 페이팔 Twitter
배열 동적 프로그래밍 매트릭스조회수 105

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

최대 제곱 문제에서 우리는 2D 바이너리를 제공했습니다. 매트릭스 0과 1로 채워지면 1 만 포함 된 가장 큰 정사각형을 찾아 면적을 반환합니다.

입력:

1 0 1 0 0

0 0 1 1 1

1 1 1 1 1

0 0 0 1 0

출력:

4

무차별 대입 접근

이 문제를 해결하는 무차별 대입 방법은 가능한 모든 정사각형 하위 행렬을 반복하고 최대 값을 선택하는 것입니다.

최대 제곱을위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
int maximalSquare(vector<vector<char>> &matrix)
{
    int answer = 0;
    int n = matrix.size();
    if (n == 0)
    {
        return 0;
    }
    int m = matrix[0].size();
    if (m == 0)
    {
        return 0;
    }
    for (int sidelength = 1; sidelength <= min(n, m); sidelength++) // sidelength denotes the side length of the sub-matrix
    {
        // i,j are the top left index of the current sub-matrix
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if ((i + sidelength > n) or (j + sidelength > m)) //check if the current sub-matrix is not out of bounds
                {
                    continue;
                }
                bool zero = false;
                // check if this sub matrix contain any zero or not
                for (int x = i; x < i + sidelength; x++)
                {
                    for (int y = j; y < j + sidelength; y++)
                    {
                        if (matrix[x][y] == '0')
                        {
                            zero = true;
                        }
                    }
                }
                if (zero == false) // if this does not contain any zero than this is a valid sub matrix
                {
                    answer = max(answer, sidelength * sidelength);
                }
            }
        }
    }
    return answer;
}
int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<char>> matrix(n, vector<char>(m));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> matrix[i][j];
        }
    }
    int answer = maximalSquare(matrix);
    cout << answer << endl;
    return 0;
}
4 4
1 0 1 0 
1 0 1 1 
1 1 1 1 
1 0 0 1 
4

Maximal Square를위한 JAVA 프로그램

import java.util.*;
public class Main
{
    public static int maximalSquare(char[][] matrix)
    {
        int answer = 0;
        int n = matrix.length;
        if (n == 0)
        {
            return 0;
        }
        int m = matrix[0].length;
        if (m == 0)
        {
            return 0;
        }
        for (int sidelength = 1; sidelength <= Math.min(n, m); sidelength++) // sidelength denotes the side length of the sub-matrix
        {
            // i,j are the top left index of the current sub-matrix
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if ((i + sidelength > n) || (j + sidelength > m)) //check if the current sub-matrix is not out of bounds
                    {
                        continue;
                    }
                    boolean zero = false;
                    // check if this sub matrix contain any zero or not
                    for (int x = i; x < i + sidelength; x++)
                    {
                        for (int y = j; y < j + sidelength; y++)
                        {
                            if (matrix[x][y] == '0')
                            {
                                zero = true;
                            }
                        }
                    }
                    if (zero == false) // if this does not contain any zero than this is a valid sub matrix
                    {
                        answer = Math.max(answer, sidelength * sidelength);
                    }
                }
            }
        }
        return answer;
    }
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int m = sc.nextInt();;
        char[][] matrix = new char[n][m];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                matrix[i][j] = sc.next().charAt(0);
            }
        }
        int answer = maximalSquare(matrix);
    System.out.println(answer);
  }
}



4 5
1 0 1 1 1
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
9

복잡성 분석

시간 복잡성

모든 제곱을 반복하고 대략 N ^ 2 제곱이 있으므로 총 시간 복잡도는 다음과 같습니다. O (N ^ 4).

공간 복잡성

추가 공간을 사용하지 않았으므로 공간 복잡성은 O (1).

동적 프로그래밍 접근법

설명

DP가 있다고 가정 해 봅시다. 정렬 크기 (n + 1, m + 1) 여기서 dp [i] [j]는 왼쪽 상단 모서리가 I, j 인 모든 사각형의 가장 큰 변 길이를 나타냅니다.

따라서 행렬 [i] [j]가 1보다 1이면 dp [i] [j] = 1 + min (dp [i-1], dp [i] [j-1], dp [i-1 ] [j-1]) 왼쪽 상단 모서리 I, j가있는 가장 큰 사각형은 왼쪽 상단 모서리가있는 가장 큰 사각형의 교차점 (i-1, j), (I, j-1), ( i-XNUMX, j-XNUMX).

암호알고리즘

  1. 1으로 크기 (n + 1, m + XNUMX)의 dp 배열을 초기화합니다.
  2. XNUMX으로 정수 ans를 초기화합니다.
  3. 행렬의 모든 셀을 반복합니다.
    1. 행렬 [i] [j]가 업데이트 dp [i] [j] = 1 + min (dp [i-1], dp [i] [j-1], dp [i-1] [j- 1]).
    2. ans = max (ans, dp [i] [j])를 업데이트합니다.
  4. 반환 ans.

예 :

Matrix[][]={{‘1’, ‘0’, ‘1’, ‘0’, ‘0’},

{ '1', '0', '1', '1', '1'},

{ '1', '1', '1', '1', '1'},

{ '1', '0', '0', '1', '0'}}

이 행렬의 경우 dp [] [] 배열은 다음과 같습니다.

맥시 멀 스퀘어

dp [i] [j]는 왼쪽 상단에 인덱스 (i, j)가있는 최대 제곱의 변 길이를 나타냅니다.

최대 제곱을위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
int maximalSquare(vector<vector<char>> &matrix)
{
    int n = matrix.size();
    if (n == 0)
    {
        return 0;
    }
    int m = matrix[0].size();
    if (m == 0)
    {
        return 0;
    }
    int ans = 0;
    vector<vector<int>> dp(n, vector<int>(m, 0));
    for (int i = n - 1; i >= 0; i--)
    {
        if (matrix[i][m - 1] == '1')
        {
            dp[i][m - 1]++;
            ans = 1;
        }
    }
    for (int i = m - 1; i >= 0; i--)
    {
        if (matrix[n - 1][i] == '1')
        {
            dp[n - 1][i]++;
            ans = 1;
        }
    }
    for (int i = n - 2; i >= 0; i--)
    {
        for (int j = m - 2; j >= 0; j--)
        {
            if (matrix[i][j] == '1')
            {
                dp[i][j] = min(dp[i + 1][j + 1], min(dp[i + 1][j], dp[i][j + 1])) + 1;
                ans = max(ans, dp[i][j]);
            }
        }
    }
    return ans * ans;
}
int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<char>> matrix(n, vector<char>(m));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> matrix[i][j];
        }
    }
    int answer = maximalSquare(matrix);
    cout << answer << endl;
    return 0;
}
4 2
1 0 
1 1 
1 1
1 0
4

Maximal Square를위한 JAVA 프로그램

import java.util.*;
public class Main
{
    public static int maximalSquare(char[][] matrix)
    {
        int n = matrix.length;
        if (n == 0)
        {
            return 0;
        }
        int m = matrix[0].length;
        if (m == 0)
        {
            return 0;
        }
        int ans = 0;
        int[][] dp = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                dp[i][j]=0;
            }
        }
        for (int i = n - 1; i >= 0; i--)
        {
            if (matrix[i][m - 1] == '1')
            {
                dp[i][m - 1]++;
                ans = 1;
            }
        }
        for (int i = m - 1; i >= 0; i--)
        {
            if (matrix[n - 1][i] == '1')
            {
                dp[n - 1][i]++;
                ans = 1;
            }
        }
        for (int i = n - 2; i >= 0; i--)
        {
            for (int j = m - 2; j >= 0; j--)
            {
                if (matrix[i][j] == '1')
                {
                    dp[i][j] = Math.min(dp[i + 1][j + 1], Math.min(dp[i + 1][j], dp[i][j + 1])) + 1;
                    ans = Math.max(ans, dp[i][j]);
                }
            }
        }
        return ans * ans;
    }

  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int m = sc.nextInt();;
        char[][] matrix = new char[n][m];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                matrix[i][j] = sc.next().charAt(0);
            }
        }
        int answer = maximalSquare(matrix);
    System.out.println(answer);
  }
}
4 5
0 1 1 1 1
1 1 1 1 1
1 1 1 1 1
0 1 1 1 1
16

복잡성 분석

시간 복잡성

행렬을 한 번만 반복하므로 시간 복잡성은 O (N ^ 2).

공간 복잡성

크기 (n + 1, m + 1)의 dp 배열을 가져 왔으므로 공간 복잡성은 O (N ^ N).

참조

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