Dada una lista enlazada individualmente que contiene N Nodes, la tarea es encontrar la media de todos los Nodes distintos de la lista cuyo valor de datos es un número impar de Fibonacci .
Ejemplos:
Entrada: LL = 5 -> 21 -> 8 ->12-> 3 -> 13 ->144 -> 6
Salida 10.5
Explicación:
Los Nodes de Fibonacci presentes en la lista enlazada son {5, 21, 8, 3, 13, 144 }
Los Nodes impares de Fibonacci presentes en la lista son {5, 21, 3, 13} El
recuento de Nodes impares de Fibonacci es 4
Por lo tanto, la media de los valores de los Nodes impares de Fibonacci = (5 + 21 + 3 + 13) / 4 = 10,5Entrada: LL = 55 -> 3 -> 91 -> 89 -> 76 -> 233 -> 34 -> 87 -> 5 -> 100
Salida: 77
Explicación:
Los Nodes de Fibonacci presentes en la lista enlazada son {55, 3, 89, 233, 34, 5}
Los Nodes impares de Fibonacci presentes en la lista enlazada son {55, 3, 89, 233, 5} El
recuento de Nodes impares de Fibonacci es 5
Por lo tanto, la media de los valores impares de los Nodes de Fibonacci = (55 + 5 + 3 + 89 + 233) / 5 = 77
Enfoque: la idea es utilizar hashing para precalcular y almacenar todos los números de Fibonacci hasta el elemento más grande en la lista enlazada .
Siga los pasos que se indican a continuación para resolver el problema:
- Inicialice dos variables, digamos cnt , sum para almacenar el recuento de Nodes impares de Fibonacci y la suma de todos los Nodes impares de Fibonacci respectivamente.
- Recorra la lista enlazada individualmente y almacene el elemento más grande de la lista enlazada , digamos Max .
- Cree un conjunto , digamos hashmap para almacenar todos los números de Fibonacci hasta Max .
- Recorra la lista enlazada y verifique si el Node actual es un número impar y de Fibonacci o no. Si se determina que es cierto, incremente el valor de cnt y agregue el valor de datos del Node actual para sumar y eliminar el Node de Hashmap .
- Finalmente, imprima el valor de (sum / cnt) como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a
// singly Linked List
struct Node {
// Stores data value
// of a Node
int data;
// Stores pointer
// to next Node
Node* next;
};
// Function to insert a node at the
// beginning of the singly Linked List
void push(Node** head_ref, int new_data)
{
// Create a new Node
Node* new_node = new Node;
// Insert the data into
// the Node
new_node->data = new_data;
// Insert pointer to
// the next Node
new_node->next = (*head_ref);
// Update head_ref
(*head_ref) = new_node;
}
// Function to find the largest
// element from the linked list
int largestElement(struct Node* head_ref)
{
// Stores the largest element
// in the linked list
int Max = INT_MIN;
Node* head = head_ref;
// Iterate over the linked list
while (head != NULL) {
// If max is less than
// head->data
if (Max < head->data) {
// Update max
Max = head->data;
}
// Update head
head = head->next;
}
return Max;
}
// Function to store all Fibonacci numbers
// up to the largest element of the list
set<int> createHashMap(int Max)
{
// Store all Fibonacci numbers
// up to Max
set<int> hashmap;
// Stores first element of
// Fibonacci number
int prev = 0;
// Stores second element of
// Fibonacci number
int curr = 1;
// Insert prev into hashmap
hashmap.insert(prev);
// Insert curr into hashmap
hashmap.insert(curr);
// Insert all elements of
// Fibonacci numbers up to Max
while (curr <= Max) {
// Stores current fibonacci number
int temp = curr + prev;
// Insert temp into hashmap
hashmap.insert(temp);
// Update prev
prev = curr;
// Update curr
curr = temp;
}
return hashmap;
}
// Function to find the mean
// of odd Fibonacci nodes
double meanofnodes(struct Node* head)
{
// Stores the largest element
// in the linked list
int Max = largestElement(head);
// Stores all fibonacci numbers
// up to Max
set<int> hashmap
= createHashMap(Max);
// Stores current node
// of linked list
Node* curr = head;
// Stores count of
// odd Fibonacci nodes
int cnt = 0;
// Stores sum of all
// odd fibonacci nodes
double sum = 0.0;
// Traverse the linked list
while (curr != NULL) {
// if the data value of
// current node is an odd number
if ((curr->data) & 1){
// if data value of the node
// is present in hashmap
if (hashmap.count(curr->data)) {
// Update cnt
cnt++;
// Update sum
sum += curr->data;
// Remove current fibonacci number
// from hashmap so that duplicate
// elements can't be counted
hashmap.erase(curr->data);
}
}
// Update curr
curr = curr->next;
}
// Return the required mean
return (sum / cnt);
}
// Driver Code
int main()
{
// Stores head node of
// the linked list
Node* head = NULL;
// Insert all data values
// in the linked list
push(&head, 5);
push(&head, 21);
push(&head, 8);
push(&head, 12);
push(&head, 3);
push(&head, 13);
push(&head, 144);
push(&head, 6);
cout<<meanofnodes(head);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Structure of a
// singly Linked List
static class Node
{
// Stores data value
// of a Node
int data;
// Stores pointer
// to next Node
Node next;
};
static Node head;
// Function to insert a
// node at the beginning
// of the singly Linked List
static Node push(Node head_ref,
int new_data)
{
// Create a new Node
Node new_node = new Node();
// Insert the data into
// the Node
new_node.data = new_data;
// Insert pointer to
// the next Node
new_node.next = head_ref;
// Update head_ref
head_ref = new_node;
return head_ref;
}
// Function to find the largest
// element from the linked list
static int largestElement(Node head_ref)
{
// Stores the largest element
// in the linked list
int Max = Integer.MIN_VALUE;
Node head = head_ref;
// Iterate over the
// linked list
while (head != null)
{
// If max is less than
// head.data
if (Max < head.data)
{
// Update max
Max = head.data;
}
// Update head
head = head.next;
}
return Max;
}
// Function to store all
// Fibonacci numbers up
// to the largest element
// of the list
static HashSet<Integer>
createHashMap(int Max)
{
// Store all Fibonacci
// numbers up to Max
HashSet<Integer> hashmap =
new HashSet<>();
// Stores first element of
// Fibonacci number
int prev = 0;
// Stores second element of
// Fibonacci number
int curr = 1;
// Insert prev into hashmap
hashmap.add(prev);
// Insert curr into hashmap
hashmap.add(curr);
// Insert all elements of
// Fibonacci numbers up
// to Max
while (curr <= Max)
{
// Stores current fibonacci
// number
int temp = curr + prev;
// Insert temp into hashmap
hashmap.add(temp);
// Update prev
prev = curr;
// Update curr
curr = temp;
}
return hashmap;
}
// Function to find the mean
// of odd Fibonacci nodes
static double meanofnodes()
{
// Stores the largest element
// in the linked list
int Max = largestElement(head);
// Stores all fibonacci numbers
// up to Max
HashSet<Integer> hashmap =
createHashMap(Max);
// Stores current node
// of linked list
Node curr = head;
// Stores count of
// odd Fibonacci nodes
int cnt = 0;
// Stores sum of all
// odd fibonacci nodes
double sum = 0.0;
// Traverse the linked list
while (curr != null)
{
// if the data value of
// current node is an
// odd number
if ((curr.data) %2== 1)
{
// if data value of the node
// is present in hashmap
if (hashmap.contains(curr.data))
{
// Update cnt
cnt++;
// Update sum
sum += curr.data;
// Remove current fibonacci
// number from hashmap so that
// duplicate elements can't be
// counted
hashmap.remove(curr.data);
}
}
// Update curr
curr = curr.next;
}
// Return the required mean
return (sum / cnt);
}
// Driver Code
public static void main(String[] args)
{
// Stores head node of
// the linked list
head = null;
// Insert all data values
// in the linked list
head = push(head, 5);
head = push(head, 21);
head = push(head, 8);
head = push(head, 12);
head = push(head, 3);
head = push(head, 13);
head = push(head, 144);
head = push(head, 6);
System.out.print(meanofnodes());
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement # the above approach # Structure of a # singly Linked List class Node: def __init__(self): # Stores data value # of a Node self.data = 0 # Stores pointer # to next Node self.next = None # Function to add a node at the # beginning of the singly Linked List def push( head_ref, new_data): # Create a new Node new_node = Node() # Insert the data into # the Node new_node.data = new_data; # Insert pointer to # the next Node new_node.next = head_ref # Update head_ref head_ref = new_node; return head_ref # Function to find the largest # element from the linked list def largestElement(head_ref): # Stores the largest element # in the linked list Max = -10000000 head = head_ref; # Iterate over the linked list while (head != None): # If max is less than # head.data if (Max < head.data): # Update max Max = head.data; # Update head head = head.next; return Max; # Function to store all Fibonacci numbers # up to the largest element of the list def createHashMap(Max): # Store all Fibonacci numbers # up to Max hashmap = set() # Stores first element of # Fibonacci number prev = 0; # Stores second element of # Fibonacci number curr = 1; # Insert prev into hashmap hashmap.add(prev); # Insert curr into hashmap hashmap.add(curr); # Insert all elements of # Fibonacci numbers up to Max while (curr <= Max): # Stores current fibonacci number temp = curr + prev; # Insert temp into hashmap hashmap.add(temp); # Update prev prev = curr; # Update curr curr = temp; return hashmap; # Function to find the mean # of odd Fibonacci nodes def meanofnodes(head): # Stores the largest element # in the linked list Max = largestElement(head); # Stores all fibonacci numbers # up to Max hashmap = createHashMap(Max); # Stores current node # of linked list curr = head; # Stores count of # odd Fibonacci nodes cnt = 0; # Stores sum of all # odd fibonacci nodes sum = 0.0; # Traverse the linked list while (curr != None): # if the data value of # current node is an odd number if ((curr.data) % 2 == 1): # if data value of the node # is present in hashmap if (curr.data in hashmap): # Update cnt cnt += 1 # Update sum sum += curr.data; # Remove current fibonacci number # from hashmap so that duplicate # elements can't be counted hashmap.remove(curr.data); # Update curr curr = curr.next; # Return the required mean return (sum / cnt); # Driver Code if __name__=='__main__': # Stores head node of # the linked list head = None; # Insert all data values # in the linked list head = push(head, 5); head = push(head, 21); head = push(head, 8); head = push(head, 12); head = push(head, 3); head = push(head, 13); head = push(head, 144); head = push(head, 6); print(meanofnodes(head)) # This code is contributed by rutvik_56
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Structure of a
// singly Linked List
public class Node
{
// Stores data value
// of a Node
public int data;
// Stores pointer
// to next Node
public Node next;
};
static Node head;
// Function to insert a
// node at the beginning
// of the singly Linked List
static Node push(Node head_ref,
int new_data)
{
// Create a new Node
Node new_node = new Node();
// Insert the data into
// the Node
new_node.data = new_data;
// Insert pointer to
// the next Node
new_node.next = head_ref;
// Update head_ref
head_ref = new_node;
return head_ref;
}
// Function to find the largest
// element from the linked list
static int largestElement(Node head_ref)
{
// Stores the largest element
// in the linked list
int Max = int.MinValue;
Node head = head_ref;
// Iterate over the
// linked list
while (head != null)
{
// If max is less than
// head.data
if (Max < head.data)
{
// Update max
Max = head.data;
}
// Update head
head = head.next;
}
return Max;
}
// Function to store all
// Fibonacci numbers up
// to the largest element
// of the list
static HashSet<int> createDictionary(int Max)
{
// Store all Fibonacci
// numbers up to Max
HashSet<int> hashmap = new HashSet<int>();
// Stores first element of
// Fibonacci number
int prev = 0;
// Stores second element of
// Fibonacci number
int curr = 1;
// Insert prev into hashmap
hashmap.Add(prev);
// Insert curr into hashmap
hashmap.Add(curr);
// Insert all elements of
// Fibonacci numbers up
// to Max
while (curr <= Max)
{
// Stores current fibonacci
// number
int temp = curr + prev;
// Insert temp into hashmap
hashmap.Add(temp);
// Update prev
prev = curr;
// Update curr
curr = temp;
}
return hashmap;
}
// Function to find the mean
// of odd Fibonacci nodes
static double meanofnodes()
{
// Stores the largest element
// in the linked list
int Max = largestElement(head);
// Stores all fibonacci numbers
// up to Max
HashSet<int> hashmap = createDictionary(Max);
// Stores current node
// of linked list
Node curr = head;
// Stores count of
// odd Fibonacci nodes
int cnt = 0;
// Stores sum of all
// odd fibonacci nodes
double sum = 0.0;
// Traverse the linked list
while (curr != null)
{
// if the data value of
// current node is an
// odd number
if ((curr.data) % 2 == 1)
{
// if data value of the node
// is present in hashmap
if (hashmap.Contains(curr.data))
{
// Update cnt
cnt++;
// Update sum
sum += curr.data;
// Remove current fibonacci
// number from hashmap so that
// duplicate elements can't be
// counted
hashmap.Remove(curr.data);
}
}
// Update curr
curr = curr.next;
}
// Return the required mean
return (sum / cnt);
}
// Driver Code
public static void Main(String[] args)
{
// Stores head node of
// the linked list
head = null;
// Insert all data values
// in the linked list
head = push(head, 5);
head = push(head, 21);
head = push(head, 8);
head = push(head, 12);
head = push(head, 3);
head = push(head, 13);
head = push(head, 144);
head = push(head, 6);
Console.Write(meanofnodes());
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program to implement
// the above approach
// Structure of a
// singly Linked List
class Node {
constructor()
{
// Stores data value
// of a Node
this.data = 0;
// Stores pointer
// to next Node
this.next = null;
}
};
// Function to insert a node at the
// beginning of the singly Linked List
function push(head_ref, new_data)
{
// Create a new Node
var new_node = new Node();
// Insert the data into
// the Node
new_node.data = new_data;
// Insert pointer to
// the next Node
new_node.next = (head_ref);
// Update head_ref
(head_ref) = new_node;
return head_ref;
}
// Function to find the largest
// element from the linked list
function largestElement(head_ref)
{
// Stores the largest element
// in the linked list
var Max = -1000000000;
var head = head_ref;
// Iterate over the linked list
while (head != null) {
// If max is less than
// head.data
if (Max < head.data) {
// Update max
Max = head.data;
}
// Update head
head = head.next;
}
return Max;
}
// Function to store all Fibonacci numbers
// up to the largest element of the list
function createHashMap(Max)
{
// Store all Fibonacci numbers
// up to Max
var hashmap = new Set();
// Stores first element of
// Fibonacci number
var prev = 0;
// Stores second element of
// Fibonacci number
var curr = 1;
// Insert prev into hashmap
hashmap.add(prev);
// Insert curr into hashmap
hashmap.add(curr);
// Insert all elements of
// Fibonacci numbers up to Max
while (curr <= Max) {
// Stores current fibonacci number
var temp = curr + prev;
// Insert temp into hashmap
hashmap.add(temp);
// Update prev
prev = curr;
// Update curr
curr = temp;
}
return hashmap;
}
// Function to find the mean
// of odd Fibonacci nodes
function meanofnodes(head)
{
// Stores the largest element
// in the linked list
var Max = largestElement(head);
// Stores all fibonacci numbers
// up to Max
var hashmap
= createHashMap(Max);
// Stores current node
// of linked list
var curr = head;
// Stores count of
// odd Fibonacci nodes
var cnt = 0;
// Stores sum of all
// odd fibonacci nodes
var sum = 0.0;
// Traverse the linked list
while (curr != null) {
// if the data value of
// current node is an odd number
if ((curr.data) & 1){
// if data value of the node
// is present in hashmap
if (hashmap.has(curr.data)) {
// Update cnt
cnt++;
// Update sum
sum += curr.data;
// Remove current fibonacci number
// from hashmap so that duplicate
// elements can't be counted
hashmap.delete(curr.data);
}
}
// Update curr
curr = curr.next;
}
// Return the required mean
return (sum / cnt);
}
// Driver Code
// Stores head node of
// the linked list
var head = null;
// Insert all data values
// in the linked list
head = push(head, 5);
head = push(head, 21);
head = push(head, 8);
head = push(head, 12);
head = push(head, 3);
head = push(head, 13);
head = push(head, 144);
head = push(head, 6);
document.write( meanofnodes(head));
// This code is contributed by noob2000.
</script>
Producción:
10.5
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por crisscross y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA