Dada una lista enlazada de caracteres. La tarea es encontrar el carácter máximo que aparece en la lista enlazada. si hay varias respuestas, devuelve el primer carácter máximo que aparece.
Ejemplos:
Input : g -> e -> e -> k -> s Output : e Input : a -> a -> b -> b -> c -> c -> d -> d Output : d
Método 1:
cuente iterativamente la frecuencia de cada carácter en una string y devuelva el que tiene la máxima ocurrencia.
C++
// C++ program to count the maximum
// occurring character in linked list
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
struct Node {
char data;
struct Node *next;
};
char maxChar(struct Node *head) {
struct Node *p = head;
int max = -1;
char res;
while (p != NULL) {
// counting the frequency of current element
// p->data
struct Node *q = p->next;
int count = 1;
while (q != NULL) {
if (p->data == q->data)
count++;
q = q->next;
}
// if current counting is greater than max
if (max < count) {
res = p->data;
max = count;
}
p = p->next;
}
return res;
}
/* Push a node to linked list. Note that
this function changes the head */
void push(struct Node **head_ref, char new_data) {
struct Node *new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* Driver program to test above function*/
int main() {
/* Start with the empty list */
struct Node *head = NULL;
char str[] = "skeegforskeeg";
int i;
// this will create a linked list of
// character "geeksforgeeks"
for (i = 0; str[i] != '\0'; i++)
push(&head, str[i]);
cout << maxChar(head);
return 0;
}
Java
// Java program to count the
// maximum occurring character
// in linked list
import java.util.*;
class GFG{
// Link list node
static class Node
{
char data;
Node next;
};
static Node head_ref;
static char maxChar(Node head)
{
Node p = head;
int max = -1;
char res = '0';
while (p != null)
{
// counting the frequency
// of current element
// p.data
Node q = p.next;
int count = 1;
while (q != null)
{
if (p.data == q.data)
count++;
q = q.next;
}
// if current counting
// is greater than max
if (max < count)
{
res = p.data;
max = count;
}
p = p.next;
}
return res;
}
// Push a node to linked list.
// Note that this function
// changes the head
static void push(char new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
}
// Driver code
public static void main(String[] args)
{
// Start with the empty list
head_ref = null;
String str = "skeegforskeeg";
char st[] = str.toCharArray();
int i;
// this will create a linked
// list of character "geeksforgeeks"
for (i = 0; i < st.length; i++)
push(st[i]);
System.out.print(maxChar(head_ref));
}
}
// This code is contributed by shikhasingrajput
Python3
# Python program to count the # maximum occurring character # in linked list # Link list Node class Node: def __init__(self, data): self.data = data; self.next = next; head_ref = None; def maxChar(head): p = head; max = -1; res = '0'; while (p != None): # counting the frequency # of current element # p.data q = p.next; count = 1; while (q != None): if (p.data == q.data): count += 1; q = q.next; # if current counting # is greater than max if (max < count): res = p.data; max = count; p = p.next; return res; # Push a Node to linked list. # Note that this function # changes the head def push(new_data): global head_ref; new_node = Node(0); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; head_ref = new_node; # Driver code if __name__ == '__main__': # Start with the empty list head_ref = None; str = "skeegforskeeg"; st = str; i = 0; # this will create a linked # list of character "geeksforgeeks" for i in range(len(st)): push(st[i]); print(maxChar(head_ref)); # This code is contributed by shikhasingrajput
C#
// C# program to count the
// maximum occurring character
// in linked list
using System;
class GFG
{
// Link list node
class Node
{
public char data;
public Node next;
};
static Node head_ref;
static char maxChar(Node head)
{
Node p = head;
int max = -1;
char res = '0';
while (p != null)
{
// counting the frequency
// of current element
// p.data
Node q = p.next;
int count = 1;
while (q != null)
{
if (p.data == q.data)
count++;
q = q.next;
}
// if current counting
// is greater than max
if (max < count)
{
res = p.data;
max = count;
}
p = p.next;
}
return res;
}
// Push a node to linked list.
// Note that this function
// changes the head
static void push(char new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
}
// Driver code
public static void Main(string[] args)
{
// Start with the empty list
head_ref = null;
string str = "skeegforskeeg";
char []st = str.ToCharArray();
int i;
// this will create a linked
// list of character "geeksforgeeks"
for (i = 0; i < st.Length; i++)
push(st[i]);
Console.Write(maxChar(head_ref));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program to count the
// maximum occurring character
// in linked list
// Link list node
class Node
{
constructor()
{
this.data = '';
this.next = null;
}
};
var head_ref = null;
function maxChar( head)
{
var p = head;
var max = -1;
var res = '0';
while (p != null)
{
// counting the frequency
// of current element
// p.data
var q = p.next;
var count = 1;
while (q != null)
{
if (p.data == q.data)
count++;
q = q.next;
}
// if current counting
// is greater than max
if (max < count)
{
res = p.data;
max = count;
}
p = p.next;
}
return res;
}
// Push a node to linked list.
// Note that this function
// changes the head
function push(new_data)
{
var new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
}
// Driver code
// Start with the empty list
head_ref = null;
var str = "skeegforskeeg";
var st = str.split('');
var i;
// this will create a linked
// list of character "geeksforgeeks"
for (i = 0; i < st.length; i++)
push(st[i]);
document.write(maxChar(head_ref));
</script>
Producción:
e
Tiempo de complejidad: (N*N)
Método 2: (use una array de conteo)
Cree una array de conteo y cuente la frecuencia de cada carácter para devolver el carácter máximo que aparece.
C++
// C++ program to count the maximum
// occurring character in linked list
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
struct Node {
char data;
struct Node *next;
};
char maxChar(struct Node *head) {
struct Node *p = head;
int hash[256] = {0};
// Storing element's frequencies
// in a hash table.
while (p != NULL) {
hash[p->data]++;
p = p->next;
}
p = head;
int max = -1;
char res;
// calculating the first maximum element
while (p != NULL) {
if (max < hash[p->data]) {
res = p->data;
max = hash[p->data];
}
p = p->next;
}
return res;
}
/* Push a node to linked list. Note that
this function changes the head */
void push(struct Node **head_ref, char new_data) {
struct Node *new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* Driver program to test above function*/
int main() {
struct Node *head = NULL;
char str[] = "skeegforskeeg";
for (int i = 0; str[i] != '\0'; i++)
push(&head, str[i]);
cout << maxChar(head);
return 0;
}
Java
// Java program to count the maximum
// occurring character in linked list
import java.util.*;
class GFG
{
/* Link list node */
static class Node
{
char data;
Node next;
};
static Node head;
static char maxChar(Node head)
{
Node p = head;
int []hash = new int[256];
// Storing element's frequencies
// in a hash table.
while (p != null)
{
hash[p.data]++;
p = p.next;
}
p = head;
int max = -1;
char res = 0;
// calculating the first maximum element
while (p != null)
{
if (max < hash[p.data])
{
res = p.data;
max = hash[p.data];
}
p = p.next;
}
return res;
}
/* Push a node to linked list. Note that
this function changes the head */
static void push(Node head_ref, char new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
head = head_ref;
}
// Driver Code
public static void main(String[] args)
{
head = null;
char str[] = "skeegforskeeg".toCharArray();
for (int i = 0; i < str.length; i++)
{
push(head, str[i]);
}
System.out.println(maxChar(head));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to count the maximum # occurring character in linked list # Link list node class Node: def __init__(self): self.data = '' self.next = None def maxChar(head): p = head hash = [0 for i in range(256)] # Storing element's frequencies # in a hash table. while (p != None): hash[ord(p.data)] += 1 p = p.next p = head max = -1 res = '' # Calculating the first maximum element while (p != None): if (max < hash[ord(p.data)]): res = p.data max = hash[ord(p.data)] p = p.next return res # Push a node to linked list. Note that # this function changes the head def push(head_ref, new_data): new_node = Node() new_node.data = new_data new_node.next = (head_ref) (head_ref) = new_node return head_ref # Driver Code if __name__=='__main__': head = None str = "skeegforskeeg" for i in range(len(str)): head = push(head, str[i]) print(maxChar(head)) # This code is contributed by pratham76
C#
// C# program to count the maximum
// occurring character in linked list
using System;
public class GFG
{
/* Link list node */
class Node
{
public char data;
public Node next;
};
static Node head;
static char maxChar(Node head)
{
Node p = head;
int []hash = new int[256];
// Storing element's frequencies
// in a hash table.
while (p != null)
{
hash[p.data]++;
p = p.next;
}
p = head;
int max = -1;
char res= '\x0000';
// calculating the first maximum element
while (p != null)
{
if (max < hash[p.data])
{
res = p.data;
max = hash[p.data];
}
p = p.next;
}
return res;
}
/* Push a node to linked list. Note that
this function changes the head */
static void push(Node head_ref, char new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
head = head_ref;
}
// Driver Code
public static void Main(String[] args)
{
head = null;
char []str = "skeegforskeeg".ToCharArray();
for (int i = 0; i < str.Length; i++)
{
push(head, str[i]);
}
Console.WriteLine(maxChar(head));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to count the maximum
// occurring character in linked list
// Link list node
class Node
{
constructor()
{
this.data = 0;
this.next = null;
}
}
var head = null;
function maxChar(head)
{
var p = head;
var hash = new Array(256).fill(0);
// Storing element's frequencies
// in a hash table.
while (p != null)
{
hash[p.data.charCodeAt(0)]++;
p = p.next;
}
p = head;
var max = -1;
var res = "";
// Calculating the first maximum element
while (p != null)
{
if (max < hash[p.data.charCodeAt(0)])
{
res = p.data;
max = hash[p.data.charCodeAt(0)];
}
p = p.next;
}
return res;
}
// Push a node to linked list. Note that
// this function changes the head
function push(head_ref, new_data)
{
var new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
head = head_ref;
}
// Driver Code
head = null;
var str = "skeegforskeeg".split("");
for(var i = 0; i < str.length; i++)
{
push(head, str[i]);
}
document.write(maxChar(head) + "<br>");
// This code is contributed by rdtank
</script>
Producción:
e
Complejidad temporal: (N)
Publicación traducida automáticamente
Artículo escrito por Shahnawaz_Ali y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA