Сумма всех нечетных частотных узлов Связанного списка
Опубликовано: 23 Января, 2022
Учитывая связанный список, задача состоит в том, чтобы найти сумму всех нечетных частотных узлов из данного связанного списка.
Примеры:
Input: 8 -> 8 -> 1 -> 4 -> 1 -> 2 -> 8 -> NULL
Output: 30
freq(8) = 3
freq(1) = 2
freq(4) = 1
freq(2) = 1
8, 4 and 2 appear odd number of times and (8 * 3) + (4 * 1) + (2 * 1) = 30Input: 6 -> 2 -> 2 -> 6 -> 2 -> 1 -> NULL
Output: 7
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход: эту проблему можно решить с помощью хеширования,
- Создайте хеш для хранения частот узлов.
- Просмотрите связанный список и обновите частоты узлов в хеш-переменной.
- Теперь просмотрите связанный список еще раз и для каждого узла, который появляется нечетное количество раз, добавьте его значение к текущей сумме.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include<bits/stdc++.h>using namespace std; // Node classstruct Node{ int data; Node* next; Node(int d) { data = d; next = NULL; } } ; // Function to push the new node // to head of the linked listNode* push(Node* head,int data){ // If head is null return new node as head if (!head) return new Node(data); Node* temp =new Node(data); temp->next = head; head = temp; return head;} // Function to find the sum of all odd // frequency nodes of the linked listint sumOfOddFreqEle(Node* head){ // Hash to store the frequencies of // the nodes of the linked list map<int,int> mp ; Node* temp = head; while(temp) { int d = temp->data; mp[d]++; temp = temp->next; } // Initialize total_sum as zero int total_sum = 0; // Traverse through the map to get the sum for (auto i : mp) { // If it appears for odd number of // times then add it to the sum if (i.second % 2 == 1) total_sum+=(i.second * i.first); } return total_sum;} // Driver codeint main(){ Node* head = NULL; head = push(head, 8); head = push(head, 2); head = push(head, 1); head = push(head, 4); head = push(head, 1); head = push(head, 8); head = push(head, 8); cout<<(sumOfOddFreqEle(head)); return 0;} // This code is contributed by Arnab Kundu |
Java
// Java implementation of the approachimport java.util.*;class GFG { // Node classstatic class Node{ int data; Node next; Node(int d) { data = d; next = null; } }; // Function to push the new node // to head of the linked liststatic Node push(Node head,int data){ // If head is null return new node as head if (head == null) return new Node(data); Node temp = new Node(data); temp.next = head; head = temp; return head;} // Function to find the sum of all odd // frequency nodes of the linked liststatic int sumOfOddFreqEle(Node head){ // Hash to store the frequencies of // the nodes of the linked list HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); Node temp = head; while(temp != null) { int d = temp.data; if(mp.containsKey(d)) { mp.put(d, mp.get(d) + 1); } else { mp.put(d, 1); } temp = temp.next; } // Initialize total_sum as zero int total_sum = 0; // Traverse through the map to get the sum for (Map.Entry<Integer, Integer> i : mp.entrySet()) { // If it appears for odd number of // times then add it to the sum if (i.getValue() % 2 == 1) total_sum+=(i.getValue() * i.getKey()); } return total_sum;} // Driver codepublic static void main(String[] args){ Node head = null; head = push(head, 8); head = push(head, 2); head = push(head, 1); head = push(head, 4); head = push(head, 1); head = push(head, 8); head = push(head, 8); System.out.println((sumOfOddFreqEle(head)));}} // This code is contributed by Rajput-Ji |
Python
# Python implementation of the approach # Node classclass Node: def __init__(self, data): self.data = data self.next = None # Function to push the new node # to head of the linked listdef push(head, data): # If head is null return new node as head if not head: return Node(data) temp = Node(data) temp.next = head head = temp return head # Function to find the sum of all odd # frequency nodes of the linked listdef sumOfOddFreqEle(head): # Hash to store the frequencies of # the nodes of the linked list mp ={} temp = head while(temp): d = temp.data if d in mp: mp[d]= mp.get(d)+1 else: mp[d]= 1 temp = temp.next # Initialize total_sum as zero total_sum = 0 # Traverse through the map to get the sum for digit in mp: # keep tracking the to tms = mp.get(digit) # If it appears for odd number of # times then add it to the sum if tms % 2 == 1: total_sum+=(tms * digit) return total_sum # Driver codeif __name__=="__main__": head = None head = push(head, 8) head = push(head, 2) head = push(head, 1) head = push(head, 4) head = push(head, 1) head = push(head, 8) head = push(head, 8) print(sumOfOddFreqEle(head)) |
C#
// C# implementation of the approachusing System;using System.Collections.Generic; class GFG { // Node classpublic class Node{ public int data; public Node next; public Node(int d) { data = d; next = null; } }; // Function to push the new node // to head of the linked liststatic Node push(Node head,int data){ // If head is null, // return new node as head if (head == null) return new Node(data); Node temp = new Node(data); temp.next = head; head = temp; return head;} // Function to find the sum of all odd // frequency nodes of the linked liststatic int sumOfOddFreqEle(Node head){ // Hash to store the frequencies of // the nodes of the linked list Dictionary<int, int> mp = new Dictionary<int, int>(); Node temp = head; while(temp != null) { int d = temp.data; if(mp.ContainsKey(d)) { mp[d] = mp[d] + 1; } else { mp.Add(d, 1); } temp = temp.next; } // Initialize total_sum as zero int total_sum = 0; // Traverse through the map to get the sum foreach(KeyValuePair<int, int> i in mp) { // If it appears for odd number of // times then add it to the sum if (i.Value % 2 == 1) total_sum += (i.Value * i.Key); } return total_sum;} // Driver codepublic static void Main(String[] args){ Node head = null; head = push(head, 8); head = push(head, 2); head = push(head, 1); head = push(head, 4); head = push(head, 1); head = push(head, 8); head = push(head, 8); Console.WriteLine((sumOfOddFreqEle(head)));}} // This code is contributed by Rajput-Ji |
Output:
30
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.