Առավելագույն հրապարակ


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Adobe Amazon AppDynamics խնձոր facebook Google IBM PayPal ծլվլոց
Դասավորություն Դինամիկ ծրագրավորում Matrix

Քառակուսի առավելագույն խնդրում մենք տվել ենք 2D երկուական matrix լցված 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

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

Բարդության վերլուծություն

Timeամանակի բարդությունը

Քանի որ մենք կրկնում ենք բոլոր քառակուսիների վրա և կլինեն մոտ N ^ 2 քառակուսիներ, այնպես որ ընդհանուր ժամանակի բարդությունը կազմում է Ո (N ^ 4).

Տիեզերական բարդություն

Քանի որ մենք ոչ մի լրացուցիչ տարածք չենք օգտագործել, այնպես որ տարածության բարդությունը մեծ է Ո (1).

Դինամիկ ծրագրավորման մոտեցում

բացատրություն

Ասենք, որ մենք ունենք dp դասավորություն չափի (n + 1, m + 1), որտեղ dp [i] [j] ներկայացնում է բոլորի քառակուսիի ամենամեծ կողմնային երկարությունը, որոնց ձախ վերին անկյունը I, j է:

Այսպիսով, եթե [i] [j] մատրիցը մեկն է, մենք կարող ենք ասել dp [i] [j] = 1 + րոպե (dp [i-1], dp [i] [j-1], dp [i-1 ] [j-1]), որովհետև վերին ձախ անկյունով I, j- ի ամենամեծ քառակուսին վերևի ձախ անկյունով (i-1, j), (I, j-1), ամենամեծ քառակուսիների խաչմերուկն է, ( i-1, j-1):

Ալգորիթմ

  1. Նախաձեռնեք չափի dp զանգվածը (n + 1, m + 1) զրոներով:
  2. Նախադրեք ամբողջությամբ ans և զրո:
  3. Կրկնել մատրիցայի բոլոր բջիջները:
    1. Եթե ​​[i] [j] մատրիցը մեկն է, քան թարմացումը dp [i] [j] = 1 + րոպե (dp [i-1], dp [i] [j-1], dp [i-1] [j- 1]):
    2. Թարմացնել ans = առավելագույնը (ans, dp [i] [j]):
  4. Վերադարձնել պատասխանները

Օրինակ `

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

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

Բարդության վերլուծություն

Timeամանակի բարդությունը

Քանի որ մենք մատրիցայի վրա կրկնում ենք միայն մեկ անգամ, այնպես որ ժամանակի բարդությունն է Ո (N ^ 2).

Տիեզերական բարդություն

Մենք վերցրեցինք չափի dp զանգված (n + 1, m + 1), այնպես որ տարածության բարդությունը մեծ է Ո (N ^ N).

Սայլակ