Распечатайте последнюю строку, когда строки с минимальным значением объединяются в каждой операции
Дан массив строк и массив целых чисел, где i- е целое число в массиве соответствует значению i- й строки, присутствующей в массиве строк. Теперь выберите две строки, которые имеют наименьшие значения в целочисленном массиве, суммируйте оба целых числа и объедините строки и добавьте суммированное целое число в массив целых чисел и объединенную строку в массив строк и продолжайте повторять весь процесс до тех пор, пока в обоих массивах остается только один элемент. Также обратите внимание, что после выбора любых двух строк и целых чисел они удаляются из массива, а новые строки и целые числа добавляются обратно в соответствующие массивы.
Задача - распечатать полученную финальную строку.
Примеры:
Input: str = {“Geeks”, “For”, “Geeks”}, num = {2, 3, 7}
Output: GeeksForGeeks
Pick 2 and 3 add them, and form “GeeksFor” and 5
Add them back to the arrays, str = {“GeeksFor”, “Geeks”}, num = {5, 7}
Now pick 7 and 5 add them to form “GeeksForGeeks” which is the final string.Input: str = {“abc”, “def”, “ghi”, “jkl”}, num = {1, 4, 2, 6}
Output: jklabcghidef
Подход: идея состоит в том, чтобы использовать очередь с приоритетами и создать пару строк и их соответствующие значения и сохранить их в очереди с приоритетами и продолжать исключать две пары из очереди с приоритетами, добавляя целые числа, объединяя строки и помещая их обратно в очередь. очередь с приоритетом, пока размер очереди не уменьшится до единицы, а затем вывести единственную оставшуюся строку в очереди.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Class that represents a pair struct Priority { string s; int count; }; struct Compare { int operator()(Priority a, Priority b) { if (a.count > b.count) return 1; else if (a.count < b.count) return -1; return 0; } }; // Function that prints the final string static void FindString(string str[], int num[], int n) { priority_queue< int , vector<Priority>, Compare> p; // Add all the strings and their corresponding // values to the priority queue for ( int i = 0; i < n; i++) { Priority x; x.s = str[i]; x.count = num[i]; p.push(x); } // Take those two strings from the priority // queue whose corresponding integer values // are smaller and add them up as well as // their values and add them back to the // priority queue while there are more // than a single element in the queue while (p.size() > 1) { // Get the minimum valued string Priority x = p.top(); p.pop(); // p.remove(x); // Get the second minimum valued string Priority y = p.top(); p.pop(); // Updated integer value int temp = x.count + y.count; string sb = x.s + y.s; // Create new entry for the queue Priority z; z.count = temp; z.s = sb; // Add to the queue p.push(z); } // Print the only remaining string Priority z = p.top(); p.pop(); cout << z.s << endl; } // Driver code int main() { string str[] = { "Geeks" , "For" , "Geeks" }; int num[] = { 2, 3, 7 }; int n = sizeof (num) / sizeof ( int ); FindString(str, num, n); } // This code is contributed by sanjeev2552 |
Java
// Java implementation of the approach import java.util.*; import java.lang.*; // Class that represents a pair class Priority { String s; int count; } class PQ implements Comparator<Priority> { public int compare(Priority a, Priority b) { if (a.count > b.count) return 1 ; else if (a.count < b.count) return - 1 ; return 0 ; } } class GFG { // Function that prints the final string static void FindString(String str[], int num[], int n) { Comparator<Priority> comparator = new PQ(); PriorityQueue<Priority> p = new PriorityQueue<Priority>(comparator); // Add all the strings and their corresponding // values to the priority queue for ( int i = 0 ; i < n; i++) { Priority x = new Priority(); x.s = str[i]; x.count = num[i]; p.add(x); } // Take those two strings from the priority // queue whose corresponding integer values are smaller // and add them up as well as their values and // add them back to the priority queue // while there are more than a single element in the queue while (p.size() > 1 ) { // Get the minium valued string Priority x = p.poll(); p.remove(x); // Get the second minium valued string Priority y = p.poll(); p.remove(y); // Updated integer value int temp = x.count + y.count; String sb = x.s + y.s; // Create new entry for the queue Priority z = new Priority(); z.count = temp; z.s = sb; // Add to the queue p.add(z); } // Print the only remaining string Priority z = p.poll(); System.out.println(z.s); } // Driver code public static void main(String[] args) { String str[] = { "Geeks" , "For" , "Geeks" }; int num[] = { 2 , 3 , 7 }; int n = num.length; FindString(str, num, n); } } |
GeeksForGeeks
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.