Dado un tapete de array que consta de * y alfabetos ingleses en minúsculas, la tarea es encontrar el carácter que tiene el número máximo de * a su alrededor (incluidos los elementos diagonales también). Si dos caracteres tienen el mismo número máximo, imprima lexicográficamente el carácter más pequeño.
Fuente : Ejemplos de experiencias de entrevistas de DE Shaw :
Input:
mat[][] = {{'b', '*', '*', '*'},
{'*', '*', 'c', '*'},
{'*', 'a', '*', '*'},
{'*', '*', '*', 'd'}}
Output: a
'a', 'b', 'c' and 'd' are surrounded by
'7', '3', '7' and '3' stars respectively.
'a' and 'c' are surrounded by maximum stars
but 'a' is lexicographically smaller than 'c'.
Input:
mat[][] = {{'*', 'r', '*', '*'},
{'m', 'a', 'z', '*'},
{'l', '*', 'f', 'k'},
{'*', '*', '*', 'd'} }
Output: f
Enfoque: la idea es atravesar la array y, si se encuentra un personaje, calcular el número de estrellas a su alrededor. Verifique las 8 posiciones a su alrededor y cuente el número de arranques.
Use un mapa para realizar un seguimiento del personaje y la cantidad de estrellas que lo rodean. Luego recorra el mapa y encuentre el carácter que está rodeado por el máximo de estrellas y es lexicográficamente más pequeño.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find alphabet in a Matrix
// which has maximum number of stars
// surrounding it
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of stars
// around a particular index
int countStars(int mat[][4], int i, int j, int n)
{
int count = 0;
int rowNum[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int colNum[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
// consider all 8 neighbours
for (int k = 0; k < 8; k++) {
int x = i + rowNum[k];
int y = j + colNum[k];
if (x >= 0 && x < n && y >= 0 && y < n
&& mat[x][y] == '*')
count++;
}
return count;
}
// Function to return the character in a Matrix
// which has maximum number of stars around it
char alphabetWithMaxStars(int mat[][4], int n)
{
unordered_map<char, int> umap;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// If current element is a character
if ((mat[i][j] - 97) >= 0
&& (mat[i][j] - 97) < 26) {
// Count of start surrounding it
int stars = countStars(mat, i, j, n);
umap[mat[i][j]] = stars;
}
}
}
int max = -1;
char result = 'z' + 1;
// Traverse the map
for (auto x : umap) {
if (x.second > max || (x.second == max
&& x.first < result)) {
max = x.second;
result = x.first;
}
}
return result;
}
// Driver code
int main()
{
int mat[][4] = { { 'b', '*', '*', '*' },
{ '*', '*', 'c', '*' },
{ '*', 'a', '*', '*' },
{ '*', '*', '*', 'd' } };
int n = 4;
cout << alphabetWithMaxStars(mat, n);
return 0;
}
Java
// Java program to find alphabet in a Matrix
// which has maximum number of stars
// surrounding it
import java.util.*;
class GFG
{
// Function to return the count of stars
// around a particular index
static int countStars(int mat[][], int i, int j, int n)
{
int count = 0;
int rowNum[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int colNum[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
// consider all 8 neighbours
for (int k = 0; k < 8; k++)
{
int x = i + rowNum[k];
int y = j + colNum[k];
if (x >= 0 && x < n && y >= 0 && y < n
&& mat[x][y] == '*')
count++;
}
return count;
}
// Function to return the character in a Matrix
// which has maximum number of stars around it
static char alphabetWithMaxStars(int mat[][], int n)
{
HashMap<Character,Integer> umap =
new HashMap<Character,Integer>();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
// If current element is a character
if ((mat[i][j] - 97) >= 0
&& (mat[i][j] - 97) < 26)
{
// Count of start surrounding it
int stars = countStars(mat, i, j, n);
umap.put((char)mat[i][j], stars);
}
}
}
int max = -1;
char result = 'z' + 1;
// Traverse the map
for (Map.Entry<Character,Integer> x : umap.entrySet())
{
if (x.getValue() > max || (x.getValue() == max
&& x.getKey() < result))
{
max = x.getValue();
result = x.getKey();
}
}
return result;
}
// Driver code
public static void main(String[] args)
{
int mat[][] = { { 'b', '*', '*', '*' },
{ '*', '*', 'c', '*' },
{ '*', 'a', '*', '*' },
{ '*', '*', '*', 'd' } };
int n = 4;
System.out.print(alphabetWithMaxStars(mat, n));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to find alphabet in a
# Matrix which has maximum number of stars
# surrounding it
import math as mt
# Function to return the count of stars
# around a particular index
def countStars(mat, i, j, n):
count = 0
rowNum = [-1, -1, -1, 0, 0, 1, 1, 1 ]
colNum = [-1, 0, 1, -1, 1, -1, 0, 1 ]
# consider all 8 neighbours
for k in range(8):
x = i + rowNum[k]
y = j + colNum[k]
if (x >= 0 and x < n and y >= 0 and
y < n and mat[x][y] == '*'):
count += 1
return count
# Function to return the character in a Matrix
# which has maximum number of stars around it
def alphabetWithMaxStars(mat, n):
umap = dict()
for i in range(n):
for j in range(n):
# If current element is a character
if ((ord(mat[i][j]) - 97) >= 0 and
(ord(mat[i][j]) - 97) < 26):
# Count of start surrounding it
stars = countStars(mat, i, j, n)
umap[mat[i][j]] = stars
Max = -1
result = chr(ord('z') + 1)
# Traverse the map
for x in umap:
if (umap[x] > Max or
(umap[x] == Max and x < result)):
Max = umap[x]
result = x
return result
# Driver code
mat = [[ 'b', '*', '*', '*' ],
[ '*', '*', 'c', '*' ],
[ '*', 'a', '*', '*' ],
[ '*', '*', '*', 'd' ]]
n = 4
print(alphabetWithMaxStars(mat, n))
# This code is contributed by
# Mohit kumar 29
C#
// C# program to find alphabet in a Matrix
// which has maximum number of stars
// surrounding it
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the count of stars
// around a particular index
static int countStars(int [,]mat, int i, int j, int n)
{
int count = 0;
int []rowNum = { -1, -1, -1, 0, 0, 1, 1, 1 };
int []colNum = { -1, 0, 1, -1, 1, -1, 0, 1 };
// consider all 8 neighbours
for (int k = 0; k < 8; k++)
{
int x = i + rowNum[k];
int y = j + colNum[k];
if (x >= 0 && x < n && y >= 0 && y < n
&& mat[x, y] == '*')
count++;
}
return count;
}
// Function to return the character in a Matrix
// which has maximum number of stars around it
static char alphabetWithMaxStars(int [,]mat, int n)
{
Dictionary<char,int> umap =
new Dictionary<char,int>();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
// If current element is a character
if ((mat[i, j] - 97) >= 0
&& (mat[i, j] - 97) < 26)
{
// Count of start surrounding it
int stars = countStars(mat, i, j, n);
if(umap.ContainsKey((char)mat[i,j]))
umap[(char)mat[i,j]] = stars;
else
umap.Add((char)mat[i,j], stars);
}
}
}
int max = -1;
char result = (char)('z' + 1);
// Traverse the map
foreach(KeyValuePair<char, int> x in umap)
{
if (x.Value > max || (x.Value == max
&& x.Key < result))
{
max = x.Value;
result = x.Key;
}
}
return result;
}
// Driver code
public static void Main(String[] args)
{
int [,]mat = { { 'b', '*', '*', '*' },
{ '*', '*', 'c', '*' },
{ '*', 'a', '*', '*' },
{ '*', '*', '*', 'd' } };
int n = 4;
Console.Write(alphabetWithMaxStars(mat, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to find alphabet in a Matrix
// which has maximum number of stars
// surrounding it
// Function to return the count of stars
// around a particular index
function countStars(mat,i,j,n)
{
let count = 0;
let rowNum = [-1, -1, -1, 0, 0, 1, 1, 1];
let colNum = [-1, 0, 1, -1, 1, -1, 0, 1];
// consider all 8 neighbours
for (let k = 0; k < 8; k++)
{
let x = i + rowNum[k];
let y = j + colNum[k];
if (x >= 0 && x < n && y >= 0 && y < n
&& mat[x][y] == '*')
count++;
}
return count;
}
// Function to return the character in a Matrix
// which has maximum number of stars around it
function alphabetWithMaxStars(mat,n)
{
let umap = new Map();
for (let i = 0; i < n; i++)
{
for (let j = 0; j < n; j++)
{
// If current element is a character
if ((mat[i][j].charCodeAt(0) - 97) >= 0
&& (mat[i][j].charCodeAt(0) - 97) < 26)
{
// Count of start surrounding it
let stars = countStars(mat, i, j, n);
umap.set((mat[i][j]), stars);
}
}
}
let max = -1;
let result = String.fromCharCode('z'.charCodeAt(0) + 1);
// Traverse the map
for (let [key, value] of umap.entries())
{
if (value > max || (value == max
&& key < result))
{
max = value;
result = key;
}
}
return result;
}
// Driver code
let mat = [[ 'b', '*', '*', '*' ],
[ '*', '*', 'c', '*' ],
[ '*', 'a', '*', '*' ],
[ '*', '*', '*', 'd' ]];
let n = 4;
document.write(alphabetWithMaxStars(mat, n));
// This code is contributed by unknown2108.
</script>
Producción:
a
Otro enfoque:
C++
// C++ program to find alphabet in a Matrix
// which has maximum number of stars
// surrounding it
#include <bits/stdc++.h>
using namespace std;
/**
* Counts the number of stars around the letter at position i,j
* start at position max(i-1,0),max(j-1,0) and iterate the 3*3 mini matrix
* while watching out the boundaries of
* our main matrix.
* @param i
* @param j
* @param mat
* @return
*/
int countStars(int i, int j, vector<vector<char>> mat)
{
int initialRow = i != 0 ? i - 1 : i;
int initialCol = j != 0 ? j - 1 : j;
int stars = 0;
for (int row=initialRow;(row <= i + 1) &&
row < mat.size() ; row++)
{
for (int col=initialCol;(col <= j + 1) &&
col < mat.size() ; col++)
{
if (mat[row][col] == '*')
{
stars++;
}
}
}
return stars;
}
// Function to return the character in a Matrix
// which has maximum number of stars around it
char getStarredLetter (vector<vector<char>> mat)
{
char currentSuperStar = 'a';
int currentFans = 0;
for (int i = 0 ; i < mat.size() ; i++)
{
vector<char> row = mat[i];
for (int j = 0 ; j < row.size(); j++)
{
char currentChar = row[j];
if (currentChar != '*')
{
// Count of start surrounding it
int fans = countStars(i, j, mat);
if (fans > currentFans)
{
currentSuperStar = currentChar;
currentFans = fans;
}
else if(fans == currentFans &&
currentChar < currentSuperStar)
{
currentSuperStar = currentChar;
}
}
}
}
return currentSuperStar;
}
// Driver Code
int main()
{
vector<vector<char>> mat = { { 'b', '*', '*', '*' },
{ '*', '*', 'c', '*' },
{ '*', 'a', '*', '*' },
{ '*', '*', '*', 'd' } };
cout << getStarredLetter(mat);
return 0;
}
// This code is contributed by rag2127.
Java
// Java program to find alphabet in a Matrix
// which has maximum number of stars
// surrounding it
public class SuperStarLetter {
// Function to return the character in a Matrix
// which has maximum number of stars around it
private static char getStarredLetter (char[][] mat) {
char currentSuperStar = 'a';
int currentFans = 0;
for (int i=0 ; i < mat.length ; i++) {
char[] row = mat[i];
for (int j = 0 ; j < row.length; j++) {
char currentChar = row[j];
if (currentChar != '*') {
// Count of start surrounding it
int fans = countStars(i, j, mat);
if (fans > currentFans) {
currentSuperStar = currentChar;
currentFans = fans;
} else if (fans == currentFans &&
currentChar < currentSuperStar) {
currentSuperStar = currentChar;
}
}
}
}
return currentSuperStar;
}
/**
* Counts the number of stars around the letter at position i,j
* start at position max(i-1,0),max(j-1,0) and iterate the 3*3 mini matrix
* while watching out the boundaries of
* our main matrix.
* @param i
* @param j
* @param mat
* @return
*/
private static int countStars(int i, int j, char[][] mat) {
int initialRow = i != 0 ? i-1 : i;
int initialCol = j != 0 ? j-1 : j;
int stars= 0;
for (int row=initialRow;(row <= i+1) && row < mat.length ; row++) {
for (int col=initialCol;(col <= j+1) && col < mat.length ; col++) {
if (mat[row][col] == '*') {
stars++;
}
}
}
return stars;
}
//Driver Code
public static void main(String[] args) {
char[][] mat = { { 'b', '*', '*', '*' },
{ '*', '*', 'c', '*' },
{ '*', 'a', '*', '*' },
{ '*', '*', '*', 'd' } };
System.out.println(getStarredLetter(mat));
}
}
Python3
# Python3 program to find alphabet # in a Matrix which has maximum # number of stars surrounding it # Function to return the character # in a Matrix which has maximum # number of stars around it def getStarredLetter (mat) : currentSuperStar = 'a' currentFans = 0 for i in range(len(mat)) : row = mat[i] for j in range(len(row)) : currentChar = row[j] if (currentChar != '*') : # Count of start surrounding it fans = countStars(i, j, mat) if (fans > currentFans) : currentSuperStar = currentChar currentFans = fans elif (fans == currentFans and currentChar < currentSuperStar) : currentSuperStar = currentChar; return currentSuperStar; """ * Counts the number of stars around the * letter at position i,j start at position * max(i-1,0),max(j-1,0) and iterate the 3*3 * mini matrix while watching out the boundaries * of our main matrix. * @param i * @param j * @param mat * @return """ def countStars(i, j, mat) : if i != 0 : initialRow = i - 1 else : initialRow = i if j != 0 : initialCol = j - 1 else : initialCol = j stars = 0 row = initialRow while ((row <= i + 1) and (row < len(mat))): col = initialCol while ((col <= j + 1) and (col < len(mat))): if (mat[row][col] == '*') : stars += 1 col += 1 row += 1 return stars # Driver Code if __name__ == "__main__" : mat = [ [ 'b', '*', '*', '*' ], [ '*', '*', 'c', '*' ], [ '*', 'a', '*', '*' ], [ '*', '*', '*', 'd' ] ] print(getStarredLetter(mat)) # This code is contributed by Ryugaa
C#
// C# program to find row with
// max sum in a matrix
using System;
public class SuperStarLetter
{
// Function to return the character in a Matrix
// which has maximum number of stars around it
private static char getStarredLetter (char[,] mat)
{
char currentSuperStar = 'a';
int currentFans = 0;
for (int i = 0 ; i < mat.GetLength(0) ; i++)
{
char[] row = GetRow(mat, i);
for (int j = 0 ; j < row.Length; j++)
{
char currentChar = row[j];
if (currentChar != '*')
{
// Count of start surrounding it
int fans = countStars(i, j, mat);
if (fans > currentFans)
{
currentSuperStar = currentChar;
currentFans = fans;
}
else if (fans == currentFans &&
currentChar < currentSuperStar)
{
currentSuperStar = currentChar;
}
}
}
}
return currentSuperStar;
}
public static char[] GetRow(char[,] matrix, int row)
{
var rowLength = matrix.GetLength(1);
var rowVector = new char[rowLength];
for (var i = 0; i < rowLength; i++)
rowVector[i] = matrix[row, i];
return rowVector;
}
/**
* Counts the number of stars around the letter at position i,j
* start at position max(i-1,0),max(j-1,0) and iterate the 3*3 mini matrix
* while watching out the boundaries of
* our main matrix.
* @param i
* @param j
* @param mat
* @return
*/
private static int countStars(int i, int j, char[,] mat)
{
int initialRow = i != 0 ? i-1 : i;
int initialCol = j != 0 ? j-1 : j;
int stars= 0;
for (int row = initialRow;(row <= i+1) && row < mat.GetLength(0) ; row++)
{
for (int col=initialCol;(col <= j+1) && col < mat.GetLength(1); col++)
{
if (mat[row,col] == '*')
{
stars++;
}
}
}
return stars;
}
// Driver Code
public static void Main(String[] args)
{
char[,] mat = { { 'b', '*', '*', '*' },
{ '*', '*', 'c', '*' },
{ '*', 'a', '*', '*' },
{ '*', '*', '*', 'd' } };
Console.WriteLine(getStarredLetter(mat));
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find alphabet in a Matrix
// which has maximum number of stars
// surrounding it
// Function to return the character in a Matrix
// which has maximum number of stars around it
function getStarredLetter (mat)
{
let currentSuperStar = 'a';
let currentFans = 0;
for (let i = 0 ; i < mat.length ; i++)
{
let row = mat[i];
for (let j = 0 ; j < row.length; j++)
{
let currentChar = row[j];
if (currentChar != '*')
{
// Count of start surrounding it
let fans = countStars(i, j, mat);
if (fans > currentFans)
{
currentSuperStar = currentChar;
currentFans = fans;
}
else if (fans == currentFans &&
currentChar < currentSuperStar)
{
currentSuperStar = currentChar;
}
}
}
}
return currentSuperStar;
}
/**
* Counts the number of stars around the letter at position i,j
* start at position max(i-1,0),max(j-1,0) and iterate the 3*3 mini matrix
* while watching out the boundaries of
* our main matrix.
* @param i
* @param j
* @param mat
* @return
*/
function countStars(i,j,mat)
{
let initialRow = i != 0 ? i-1 : i;
let initialCol = j != 0 ? j-1 : j;
let stars= 0;
for (let row=initialRow;(row <= i+1) && row < mat.length ; row++) {
for (let col=initialCol;(col <= j+1) && col < mat.length ; col++) {
if (mat[row][col] == '*') {
stars++;
}
}
}
return stars;
}
// Driver Code
let mat = [[ 'b', '*', '*', '*' ],
[ '*', '*', 'c', '*' ],
[ '*', 'a', '*', '*' ],
[ '*', '*', '*', 'd' ] ];
document.write(getStarredLetter(mat));
// This code is contributed by patel2127
</script>
Producción:
a
Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(N * M)
Publicación traducida automáticamente
Artículo escrito por Kushdeep_Mittal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA