Maksimum ada sahəsi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Bloomberg Qapılar Facebook google Kahin Palantir Texnologiyaları
Geyim Genişlik İlk Axtarış Dərinlik İlk Axtarış Qrafik MatrisBaxılıb 92

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problemin təsviri: 2D matris nəzərə alındıqda, matris yalnız 0 (suyu təmsil edən) və 1 (ərazini təmsil edən) giriş kimi var. Matritsada bir ada, bütün bitişik 1 lərin 4 istiqamətə (üfüqi və şaquli) birləşdirilərək əmələ gəlməsi ilə meydana gəlir. Adanın maksimum sahəsini tapın matris. Şəbəkənin dörd kənarının hamısının su ilə əhatə olunduğunu düşünək.

Qeyd: Bir ada qrupunun sahəsi bu ada qrupundakı hüceyrələrin sayıdır.

misal

Input 1: 
Grid = {{0,0,1,0,0,0,0,1,0,0,0,0,0}, 
        {0,0,0,0,0,0,0,1,1,1,0,0,0}, 
        {0,1,1,0,1,0,0,0,0,1,0,0,0}, 
        {0,1,0,0,1,1,0,0,1,0,1,0,0}, 
        {0,1,0,0,1,1,0,0,1,1,1,0,0}, 
        {0,0,0,0,0,0,0,0,1,0,1,0,0}, 
        {0,0,0,0,0,0,0,1,1,1,0,0,0}, 
        {0,0,0,0,0,0,0,1,1,0,0,0,0}}

Output: Area of largest island = 12 


Input 2: 
Grid = {{0,1,0,0,1,1,0}, 
        {0,0,0,0,1,0,0}, 
        {0,0,0,1,1,0,0}, 
        {0,0,1,1,0,0,0}}

Output: Area of largest island = 7

Yuxarıda verilmiş ilk giriş nümunəsini nəzərdən keçirin. Aşağıda yuxarıda göstərilən 2D şəbəkənin təsviri verilmişdir, ərazini təmsil edən hüceyrələr 1 (yaşıl rəngdə) və suyu təmsil edən hücrələr 0 (mavi rəngdə) kimi qeyd olunur.

Maksimum ada sahəsiPin

Diaqramdan da göründüyü kimi 5 ada qrupu qurulur. Ən böyük ada qrupu qırmızı, kiçik ada qrupları sarı rənglə göstərilmişdir. Ən böyük ada qrupunun sahəsi 12 vahiddir.

Maksimum ada sahəsiPin

Qeyd: qeyd etmək lazımdır ki, ada qrupları ızgara hüceyrələrini üfüqi (sağ və sol) və şaquli (yuxarı və aşağı) istiqamətlərdə (diaqonal istiqamətlərdə deyil) birləşdirərək meydana gəlir.

Maksimum ada sahəsi üçün həll növləri

  1. Dərinlik İlk Axtarış
  2. Genişlik İlk Axtarış

Dərinlik İlk Axtarış

Max Island Island üçün yanaşma

1-i olan hüceyrələrin bütün qonşularını (və bu qonşuların qonşularını) rekursiv şəkildə ziyarət edərək ən böyük adanın sahəsini hesablamağı hədəfləyirik. Qonşu və qonşu qonşularına bu rekursiv keçid həyata keçirilərək əldə edilir. DFS. DFS tətbiq edərkən, ziyarət edilən hər yeni hücrə üçün (yalnız 1-dən ibarət) ziyarət olunan ümumi ərazini 1 dəfə artırırıq.

Maksimum ada sahəsi üçün alqoritm

  1. 2 ölçülü hüceyrələrin hər birindən DFS keçidini yerinə yetirin və 1 ölçülü şəbəkəni keçin.
  2. Cari dəyəri 0-a dəyişdirərək mövcud hüceyrəni ziyarət olunduğu kimi qeyd edin.
  3. Cari hücrədən başlayaraq adanın sahəsi 1-dir.
  4. 1 olan cari hüceyrələrin bütün qonşularını (yuxarıdan sağdan soldan) təkrarən ziyarət edin, bu qonşuları ziyarət edildiyi kimi qeyd edin və ziyarət edilən hər bir etibarlı qonşu (dəyəri 1 olan hüceyrələr) üçün ərazini 1 artırın (hüceyrə dəyərini dəyişdirərək) 0-a).
  5. Keçid tamamlandıqdan sonra alınan ərazini geri qaytarın.
  6. 2,3,4-i ehtiva edən hüceyrələrin hər biri üçün (matrisin) 5 və 1-ci addımları yerinə yetirin və əldə edilmiş bütün sahə dəyərlərinin maksimumunu qaytarın.

Yuxarıda verilmiş nümunə şəbəkəsini nəzərdən keçirin: ən böyük adanın dəyəri 1 olan ən sol və ən yuxarı hücrədən başlayırıq (indiyə qədər bu hüceyrənin yuxarıdakı və soldakı bütün hüceyrələri ziyarət edilmişdir) və DFS keçidini həyata keçiririk.

DFS keçidi hüceyrələri müəyyən bir istiqamətdə mümkün olan ən böyük dərinliyə qədər ziyarət edir. Müəyyən bir hüceyrədən başlayaraq keçid istiqaməti aşağıdakı sıradadır: yuxarı-sağ-sol. DFS keçidi alqoritm ən böyük adanın ən üst və ən sol hücrəsindən aşağıda təsvir edilmişdir:

Ən böyük adada ziyarət edilən hücrələrə rad işarəsi qoyulmuşdur.

Maksimum ada sahəsiPin

Maksimum ada sahəsiPin

Maksimum ada sahəsiPin

Maksimum ada sahəsiPin

Maksimum ada sahəsiPin

Müşahidə etdiyimiz kimi, keçid zamanı keçilən hüceyrə sayı 12-dir. Buna görə də ən böyük adanın sahəsi 12-dir.

Həyata keçirilməsi

C ++ Proqramı
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// function to perform DFS in four directions(up-right-down-left)
int dfs(vector<vector<int>>& grid, int row, int col) 
{
    int m = grid.size();
    int n = grid[0].size();
    
    /* since the current cell has value = 1
        minimum area we start with is 1*/
    int area = 1;
    
    /* since you have already visited the current cell
    mark it as already visited */
    grid[row][col] = 0;
    
    /* used for traversing in four directions(up-right-down-left)*/
    vector<int> dir({-1,0,1,0,-1});
    
    /* we begin our traversal into four directions from the current cell*/
    for (int i = 0; i < 4; i++) 
    {
        int r = row+dir[i], c = col+dir[i+1];
        
        /* make traversals only when next cell lies within the matrix and is unvisited*/
        if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) 
            area += dfs(grid, r, c);
    }
    /* total number of cells with value 1 visited from the current cell */
    return area;
}

/* function that returns area of largest island */
int largestIsland(vector<vector<int>> grid)
{
    int m = grid.size();
    int n = grid[0].size();
    
    /* stores the area of largest consecutive 1's*/
    int maxArea = 0;
    
    /* visit each cell of the matrix*/
    for (int i = 0; i < m; i++) 
        for (int j = 0; j < n; j++) 
        /* begin your traversal from the cell which has value as 1(land)*/
            if (grid[i][j] == 1) 
            /* store the largest area*/
            maxArea = max(maxArea, dfs(grid, i, j));
            
    return maxArea;    
}

/* main function to implement above function */
int main()
{
    vector<vector<int>> grid = {{0,0,1,0,0,0,0,1,0,0,0,0,0},
                                {0,0,0,0,0,0,0,1,1,1,0,0,0},
                                {0,1,1,0,1,0,0,0,0,1,0,0,0},
                                {0,1,0,0,1,1,0,0,1,0,1,0,0},
                                {0,1,0,0,1,1,0,0,1,1,1,0,0},
                                {0,0,0,0,0,0,0,0,1,0,1,0,0},
                                {0,0,0,0,0,0,0,1,1,1,0,0,0},
                                {0,0,0,0,0,0,0,1,1,0,0,0,0}};
    
    
    cout<<"Area of largest island = "<<largestIsland(grid);
    
    return 0;
}
Area of largest island = 12
Java Proqramı
import java.util.*;
import java.io.*;

class tutorialCup
{
    // function to perform DFS in four directions(up-right-down-left)
    static int dfs(int grid[][], int row, int col) 
    {
        int m = grid.length;
        int n = grid[0].length;
        
        /* since the current cell has value = 1
            minimum area we start with is 1*/
        int area = 1;
        
        /* since you have already visited the current cell
        mark it as already visited */
        grid[row][col] = 0;
        
        /* used for traversing in four directions(up-right-down-left)*/
        int [] dir = {-1,0,1,0,-1};
        
        /* we begin our traversal into four directions from the current cell*/
        for (int i = 0; i < 4; i++) 
        {
            int r = row+dir[i], c = col+dir[i+1];
            
            /* make traversals only when next cell lies within the matrix and is unvisited*/
            if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) 
                area += dfs(grid, r, c);
        }
        /* total number of cells with value 1 visited from the current cell */
        return area;
    }

    
    /* function that returns area of largest island */
    static int largestIsland(int grid[][])
    {
        int m = grid.length;
        int n = grid[0].length;
        
        /* stores the area of largest consecutive 1's*/
        int maxArea = 0;
        
        /* visit each cell of the matrix*/
        for (int i = 0; i < m; i++) 
            for (int j = 0; j < n; j++) 
            /* begin your traversal from the cell which has value as 1(land)*/
                if (grid[i][j] == 1) 
                /* store the largest area*/
                maxArea = Math.max(maxArea, dfs(grid, i, j));
                
        return maxArea;    
    }
    
    /* main function to implement above function */
    public static void main (String[] args) 
    {
        int grid[][] =  {{0,0,1,0,0,0,0,1,0,0,0,0,0},
                        {0,0,0,0,0,0,0,1,1,1,0,0,0},
                        {0,1,1,0,1,0,0,0,0,1,0,0,0},
                        {0,1,0,0,1,1,0,0,1,0,1,0,0},
                        {0,1,0,0,1,1,0,0,1,1,1,0,0},
                        {0,0,0,0,0,0,0,0,1,0,1,0,0},
                        {0,0,0,0,0,0,0,1,1,1,0,0,0},
                        {0,0,0,0,0,0,0,1,1,0,0,0,0}};
    
        System.out.print("Area of largest island = "+largestIsland(grid)); 
    }
}
Area of largest island = 12

Maksimum Ada Sahəsi üçün Mürəkkəblik Analizi

  1. Zamanın mürəkkəbliyi: T (n) = O (R * C), matrisin hər hüceyrəsini tam bir dəfə keçirik.
  2. Məkan Mürəkkəbliyi: A (n) = O (R * C), çünki müəyyən bir hüceyrənin olub-olmamasını izləyən başqa bir matris məkanı istifadə etmədiyimiz üçün, sadəcə qrafiki dəyərləri dəyişdirdik ki, ziyarət olunan hüceyrələr işarələnsin ziyarət olunduğu kimi.

Genişlik İlk Axtarış

Max Island Island üçün yanaşma

1-i olan hüceyrələrin təkrarən bütün qonşularını (və bu qonşuların qonşularını) ziyarət edərək ən böyük adanın sahəsini hesablamağı hədəfləyirik. Qonşu və qonşu qonşularına bu təkrarlanan keçiş BFS reallaşdırılaraq əldə edilir. BFS tətbiq edərkən, ziyarət edilən hər yeni hüceyrə üçün (yalnız 1-i olan) ziyarət edilən ümumi ərazini təkrarən artırırıq.

Maksimum ada sahəsi üçün alqoritm

  1. 2 ölçülü hüceyrələrin hər birindən BFS keçidini yerinə yetirmək üçün 1B şəbəkəni keçin.
  2. Cari dəyəri 0-a dəyişdirərək mövcud hüceyrəni ziyarət olunduğu kimi qeyd edin.
  3. Cari hücrədən başlayaraq adanın sahəsi 1-dir.
  4. 1 olan cari hüceyrələrin bütün qonşularını (sağdan aşağı-sola) mütəmadi olaraq ziyarət edin, bu qonşuları ziyarət olunduğunu qeyd edin və həmçinin ziyarət edilən hər bir etibarlı qonşu üçün (dəyəri 1 olan hüceyrələr) ərazini 1 artırın (hüceyrə dəyərini dəyişdirərək) 0-a).
  5. Keçid tamamlandıqdan sonra alınan ərazini geri qaytarın.
  6. 2,3,4-i ehtiva edən hüceyrələrin hər biri üçün (matrisin) 5 və 1-ci addımları yerinə yetirin və əldə edilmiş bütün sahə dəyərlərinin maksimumunu qaytarın.

Yuxarıda verilmiş nümunə cədvəlini nəzərdən keçirin: 1 dəyərinə sahib olan ən böyük adanın ən sol və ən üst hücrəsindən başlayırıq (indiyə qədər bu hüceyrənin yuxarıdakı və soldakı bütün hüceyrələri ziyarət edilmişdir) və BFS keçidini həyata keçiririk.

BFS keçidi əvvəlcə müəyyən bir hüceyrənin bütün qonşu hücrələrini (yuxarı sağdan aşağı-sol) ziyarət edir və sonra təkrarən bu qonşuların qonşularını ziyarət edir. Ən böyük adanın ən üst və ən sol hücrəsindən BFS keçid alqoritmi aşağıda təsvir edilmişdir:

Ən böyük adada ziyarət edilən hücrələr qırmızı rəngdə qeyd edilmişdir.

Pin

Pin

Pin

Pin

Pin

Pin

Müşahidə etdiyimiz kimi, keçid zamanı keçilən hüceyrə sayı 12-dir. Buna görə də ən böyük adanın sahəsi 12-dir.

Həyata keçirilməsi

C ++ Proqramı
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// function to perform BFS in four directions(up-right-down-left)
int bfs(vector<vector<int>>& grid, int row, int col) 
{
    int m = grid.size();
    int n = grid[0].size();
    
    /* since the current cell has value = 1
            minimum area we start with is 1*/
    int area = 1;
    
    /* create a queue to be used in BFS*/
    queue<pair<int,int>> q;
    /* push the current cell */
    q.push({row, col});
    
    /* since you have already visited the current cell
        mark it as already visited */
    grid[row][col] = 0;
    /* used for traversing in four directions(up-right-down-left)*/
    vector<int> dir({-1,0,1,0,-1});
    
    /* begin BFS traversal */
    while (!q.empty()) 
    {
        /* pop a cell with containing 1(land) */
        int y = q.front().first, x = q.front().second;
        q.pop();
        
        /* we begin our traversal into four directions from the current cell*/
        for (int i = 0; i < 4; i++) 
        {
            int r = y+dir[i], c = x+dir[i+1];
            /* make traversals only when next cell lies within the matrix and is unvisited*/
            if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) 
            {
                /* mark next cell as visited, increase the visited area and push next cells into the queue*/
                grid[r][c] = 0;
                area++;
                q.push({r,c});
            }
        }
    }
    /* total number of cells with value 1 visited from the current cell */
    return area;
}
/* function that returns area of largest island */
int largestIsland(vector<vector<int>> grid)
{
    int m = grid.size();
    int n = grid[0].size();
    
    /* stores the area of largest consecutive 1's*/
    int maxArea = 0;
    
    /* visit each cell of the matrix*/
    for (int i = 0; i < m; i++) 
        for (int j = 0; j < n; j++) 
        /* begin your traversal from the cell which has value as 1(land)*/
            if (grid[i][j] == 1) 
            /* store the largest area*/
            maxArea = max(maxArea, bfs(grid, i, j));
            
    return maxArea;    
}

/* main function to implement above function */
int main()
{
    vector<vector<int>> grid = {{0,0,1,0,0,0,0,1,0,0,0,0,0},
                                {0,0,0,0,0,0,0,1,1,1,0,0,0},
                                {0,1,1,0,1,0,0,0,0,1,0,0,0},
                                {0,1,0,0,1,1,0,0,1,0,1,0,0},
                                {0,1,0,0,1,1,0,0,1,1,1,0,0},
                                {0,0,0,0,0,0,0,0,1,0,1,0,0},
                                {0,0,0,0,0,0,0,1,1,1,0,0,0},
                                {0,0,0,0,0,0,0,1,1,0,0,0,0}};
    
    
    cout<<"Area of largest island = "<<largestIsland(grid);   
    return 0;
}
Area of largest island = 12
Java Proqramı
import java.util.*;
import java.io.*;

class tutorialCup
{
    /* define pair class to handle 2D co-ordinates in a matrix*/
    static class pair
    {
        int row;
        int col;
        
        pair(int y,int x)
        {
            row = y;
            col = x;
        }
    }
    // function to perform DFS in four directions(up-right-down-left)
    static int dfs(int grid[][], int row, int col) 
    {
        int m = grid.length;
        int n = grid[0].length;
        
        /* since the current cell has value = 1
                minimum area we start with is 1*/
        int area = 1;
        
        /* create a queue to be used in BFS*/
        Queue<pair> q = new LinkedList<pair>();
        /* push the current cell */
        q.add(new pair(row, col));
        
        /* since you have already visited the current cell
            mark it as already visited */
        grid[row][col] = 0;
        /* used for traversing in four directions(up-right-down-left)*/
        int [] dir = {-1,0,1,0,-1};
        
        /* begin BFS traversal */
        while (!q.isEmpty()) 
        {
            /* pop a cell with containing 1(land) */
            pair p = q.remove();
            int y = p.row, x = p.col;
            
            /* we begin our traversal into four directions from the current cell*/
            for (int i = 0; i < 4; i++) 
            {
                int r = y+dir[i], c = x+dir[i+1];
                /* make traversals only when next cell lies within the matrix and is unvisited*/
                if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1) 
                {
                    /* mark next cell as visited, increase the visited area and push next cells into the queue*/
                    grid[r][c] = 0;
                    area++;
                    q.add(new pair(r,c));
                }
            }
        }
        /* total number of cells with value 1 visited from the current cell */
        return area;
    }

    
    /* function that returns area of largest island */
    static int largestIsland(int grid[][])
    {
        int m = grid.length;
        int n = grid[0].length;
        
        /* stores the area of largest consecutive 1's*/
        int maxArea = 0;
        
        /* visit each cell of the matrix*/
        for (int i = 0; i < m; i++) 
            for (int j = 0; j < n; j++) 
            /* begin your traversal from the cell which has value as 1(land)*/
                if (grid[i][j] == 1) 
                /* store the largest area*/
                maxArea = Math.max(maxArea, dfs(grid, i, j));
                
        return maxArea;    
    }
    
    /* main function to implement above function */
    public static void main (String[] args) 
    {
        int grid[][] =  {{0,0,1,0,0,0,0,1,0,0,0,0,0},
                        {0,0,0,0,0,0,0,1,1,1,0,0,0},
                        {0,1,1,0,1,0,0,0,0,1,0,0,0},
                        {0,1,0,0,1,1,0,0,1,0,1,0,0},
                        {0,1,0,0,1,1,0,0,1,1,1,0,0},
                        {0,0,0,0,0,0,0,0,1,0,1,0,0},
                        {0,0,0,0,0,0,0,1,1,1,0,0,0},
                        {0,0,0,0,0,0,0,1,1,0,0,0,0}};
    
        System.out.print("Area of largest island = "+largestIsland(grid)); 
    }
}
Area of largest island = 12

Maksimum Ada Sahəsi üçün Mürəkkəblik Analizi

  1. Zamanın mürəkkəbliyi: T (n) = O (R * C), matrisin hər hüceyrəsini tam bir dəfə keçirik.
  2. Kosmik Mürəkkəblik: A (n) = O (R * C). müəyyən bir hüceyrənin ziyarət edilib-edilməməsini izləyən başqa bir matris sahəsi istifadə etmədiyimizdən, sadəcə ziyarət olunan hüceyrələrin ziyarət edildiyi kimi qeyd edilməsi üçün şəbəkə dəyərlərini dəyişdiririk.

References

Crack Sistemi Dizayn Müsahibələri
Translate »