ຮຽບຮ້ອຍສູງສຸດ  


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Adobe Amazon AppDynamics ຈາກຫນາກແອບເປີ ເຟສບຸກ ກູໂກ IBM PayPal Twitter
Array ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ ມາຕຣິກເບື້ອງ

ໃນບັນຫາຮູບສີ່ຫຼ່ຽມມົນສູງສຸດພວກເຮົາໄດ້ໃຫ້ປື້ມຄູ່ 2D matrix ເຕັມໄປດ້ວຍ 0's ແລະ 1's, ພົບຕາລາງທີ່ໃຫຍ່ທີ່ສຸດມີພຽງແຕ່ 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

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

ໃນຂະນະທີ່ພວກເຮົາປ່ຽນຮູບສີ່ຫຼ່ຽມມົນທັງ ໝົດ ແລະຈະມີປະມານ N ^ 2 ຮຽບຮ້ອຍສະນັ້ນຄວາມສັບສົນຂອງເວລາທັງ ໝົດ ແມ່ນ O (N ^ 4).

ເບິ່ງ
ດຶງອອກຈາກບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງອອກຈາກ Leetcode Solution

ຄວາມສັບສົນໃນອະວະກາດ

ດັ່ງທີ່ພວກເຮົາບໍ່ໄດ້ໃຊ້ພື້ນທີ່ພິເສດໃດໆດັ່ງນັ້ນຄວາມສັບສົນຂອງພື້ນທີ່ກໍ່ຄືກັນ O (1).

ວິທີການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ  

ຄໍາອະທິບາຍ

ໃຫ້ເວົ້າວ່າພວກເຮົາມີ dp array of size (n + 1, m + 1) ບ່ອນທີ່ dp [i] [j] ເປັນຕົວແທນຂອງຄວາມຍາວຂ້າງໃຫຍ່ທີ່ສຸດຂອງຮູບສີ່ຫລ່ຽມມົນທົນທັງ ໝົດ ທີ່ມຸມຊ້າຍຂອງຂ້ອຍແມ່ນ,

ດັ່ງນັ້ນ, ຖ້າຫາກວ່າຕາຕະລາງ [i] [j] ແມ່ນ ໜຶ່ງ ທີ່ພວກເຮົາສາມາດເວົ້າວ່າ dp [i] [j] = 1 + ນາທີ (dp [i-1], dp [i] [j-1], dp [i-1 ] [j-1]) ເພາະວ່າຮູບສີ່ຫຼ່ຽມມົນທີ່ໃຫຍ່ທີ່ສຸດທີ່ມີແຈເບື້ອງຊ້າຍດ້ານເທິງຂອງຂ້ອຍ, j ແມ່ນພຽງແຕ່ຕັດກັນຂອງສີ່ຫລ່ຽມທີ່ໃຫຍ່ທີ່ສຸດເທົ່າກັບແຈເບື້ອງຊ້າຍດ້ານເທິງ (i-1, j), (ຂ້ອຍ, j-1), ( i-1, j-1).

ລະບົບວິເຄາະ

  1. ເລີ່ມຕົ້ນຂະ ໜາດ dp ຂອງຂະ ໜາດ (n + 1, m + 1) ດ້ວຍເລກສູນ.
  2. ເລີ່ມຕົ້ນ ຄຳ ຕອບເລກເຕັມກັບເລກສູນ.
  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

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

ດັ່ງທີ່ພວກເຮົາໄດ້ປຽບທຽບກັບຕາຕະລາງພຽງແຕ່ຄັ້ງດຽວເທົ່ານັ້ນສະນັ້ນຄວາມສັບສົນຂອງເວລາກໍ່ຄືກັນ O (N ^ 2).

ເບິ່ງ
ລົບ ຄຳ ດຽວກັນຕິດຕໍ່ກັນຕາມ ລຳ ດັບ

ຄວາມສັບສົນໃນອະວະກາດ

ພວກເຮົາເອົາຂະ ໜາດ dp (n + 1, m + 1) ດັ່ງນັ້ນຄວາມສັບສົນຂອງພື້ນທີ່ກໍ່ຄືກັນ O (N ^ N).

ເອກະສານ