Распечатайте последнюю строку, когда строки с минимальным значением объединяются в каждой операции

Опубликовано: 23 Января, 2022

Дан массив строк и массив целых чисел, где 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 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: идея состоит в том, чтобы использовать очередь с приоритетами и создать пару строк и их соответствующие значения и сохранить их в очереди с приоритетами и продолжать исключать две пары из очереди с приоритетами, добавляя целые числа, объединяя строки и помещая их обратно в очередь. очередь с приоритетом, пока размер очереди не уменьшится до единицы, а затем вывести единственную оставшуюся строку в очереди.

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);
    }
}
Output: 
GeeksForGeeks

 

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.