Рубрики

Минимальная сумма квадратов количества символов в данной строке после удаления k символов

Заданная строка строчных букв и число k, задача состоит в том, чтобы напечатать минимальное значение строки после удаления символов «k». Значение строки определяется как сумма квадратов числа каждого отдельного символа. Например, рассмотрим строку «saideep», здесь частоты символов s-1, a-1, i-1, e-2, d-1, p-1 и значение строки 1 ^ 2 + 1 ^ 2 + 1 ^ 2 + 1 ^ 2 + 1 ^ 2 + 2 ^ 2 = 9.

Ожидаемая сложность времени: O (n)

Примеры:

Input :  str = abccc, K = 1
Output :  6
We remove c to get the value as 12 + 12 + 22

Input :  str = aaab, K = 2
Output :  2

Спросил в: Amazon

Одно четкое наблюдение заключается в том, что нам нужно удалить персонажа с максимальной частотой. Один трюк — это персонаж ма

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

Лучшее решение, используемое для очереди приоритетов, которая имеет самый высокий элемент сверху.

  1. Инициализируйте пустую очередь с приоритетами.
  2. Подсчитайте частоту каждого символа и сохраните во временном массиве.
  3. Удалить K символов, которые имеют наибольшую частоту из очереди.
  4. Наконец подсчитайте сумму квадратов каждого элемента и верните ее.

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для поиска минимальной суммы квадратов
// символов после k удалений
#include <bits/stdc++.h>

using namespace std;

  

const int MAX_CHAR = 26;

  
// Основная функция для расчета минимальной суммы
// квадраты символов после k удалений

int minStringValue(string str, int k)

{

    int l = str.length(); // найти длину строки

  

    // если K больше длины строки

    // поэтому уменьшенная строка станет 0

    if (k >= l)

        return 0;

  

    // Иначе найти частоту каждого символа и

    // сохранить в массиве

    int frequency[MAX_CHAR] = {0};

    for (int i=0; i<l; i++)

        frequency[str[i]-'a']++;

  

    // Вставляем каждую частоту символа в приоритетную очередь

    priority_queue<int> q;

    for (int i=0; i<MAX_CHAR; i++)

        q.push(frequency[i]);

  

  

    // Удаление K символов

    while (k--)

    {

        // Получить верхний элемент в priority_queue,

        // убери это. Уменьшение на 1 и снова

        // вставляем в файл priority_queue

        int temp = q.top();

        q.pop();

        temp = temp-1;

        q.push(temp);

    }

  

    // После удаления K символов находим сумму

    // квадратов строки Value

    int result = 0; // Инициализировать результат

    while (!q.empty())

    {

        int temp = q.top();

        result += temp*temp;

        q.pop();

    }

  

    return result;

}

  
// Код драйвера

int main()

{

    string str = "abbccc";   // Вход 1

    int k = 2;

    cout << minStringValue(str, k) << endl;

  

    str = "aaab";           // Вход 2

    k = 2;

    cout << minStringValue(str, k);

  

    return 0;

}

Джава

// Java-программа для поиска минимальной суммы квадратов
// символов после k удалений

import java.util.Comparator;

import java.util.PriorityQueue;

public class GFG {

        

    static final int MAX_CHAR = 26;

      

    // Определение класса компаратора

    static class IntCompare implements Comparator<Integer>{

        @Override

        public int compare(Integer arg0, Integer arg1) {

            if(arg0 > arg1)

                return -1;

            else if(arg0 < arg1)

                return 1;

            else

                return 0;

        }

    }

      

    // Основная функция для расчета минимальной суммы

    // квадраты символов после k удалений

    static int minStringValue(String str, int k)

    {

        int l = str.length(); // найти длину строки

       

        // если K больше длины строки

        // поэтому уменьшенная строка станет 0

        if (k >= l)

            return 0;

       

        // Иначе найти частоту каждого символа и

        // сохранить в массиве

        int[] frequency = new int[MAX_CHAR];

        for (int i=0; i<l; i++)

            frequency[str.charAt(i)-'a']++;

       

          

        // создание объекта для компаратора

        Comparator<Integer> c = new IntCompare();

          

        // создаем приоритетную очередь с компаратором

        // так, что элементы в очереди находятся в

        // в порядке убывания.

        PriorityQueue<Integer> q = new PriorityQueue<>(c);

          

        // Вставляем каждую частоту символа в приоритетную очередь

        for (int i = 0; i < MAX_CHAR; i++){

            if(frequency[i] != 0)

                q.add(frequency[i]);

        }

       

          

        // Удаление K символов

        while (k != 0)

        {

            // Получить верхний элемент в priority_queue,

            // убери это. Уменьшение на 1 и снова

            // вставляем в файл priority_queue

            int temp = q.peek();

            q.poll();

            temp = temp-1;

            q.add(temp);

            k--;

        }

       

        // После удаления K символов находим сумму

        // квадратов строки Value

        int result = 0; // Инициализировать результат

        while (!q.isEmpty())

        {

            int temp = q.peek();

            result += temp*temp;

            q.poll();

        }

          

        return result;

    }

       

    // Код драйвера

    public static void main(String args[])

    {

        String str = "abbccc";   // Вход 1

        int k = 2;

        System.out.println(minStringValue(str, k));

       

        str = "aaab";           // Вход 2

        k = 2;

        System.out.println(minStringValue(str, k));

    }

}
// Этот код предоставлен Sumit Ghosh

Python 3

# Python3 программа для поиска минимальной суммы
# квадраты символов после k удалений

from queue import PriorityQueue

  

MAX_CHAR = 26

  
# Основная функция для расчета минимальной суммы
# квадраты символов после k удалений

def minStringValue(str, k):

    l = len(str) # найти длину строки

  

    # если K больше длины строки

    # так что уменьшенная строка станет 0

    if(k >= l):

        return 0

      

    # Еще найти частоту каждого

    # символ и сохранить в массиве

    frequency = [0] * MAX_CHAR

    for i in range(0, l):

        frequency[ord(str[i]) - 97] += 1

  

    # Нажмите каждый символ отрицательной частоты

    # в priority_queue в качестве очереди

    # по умолчанию это minheap

    q = PriorityQueue()

    for i in range(0, MAX_CHAR):

        q.put(-frequency[i])

  

    # Удаление K символов

    while(k > 0):

          

        # Получить верхний элемент в priority_queue

        # умножить его на -1, так как температура отрицательна

        # убери это. Инкремент на 1 и снова

        # нажать в priority_queue

        temp = q.get()

        temp = temp + 1

        q.put(temp, temp)

        k = k - 1

  

    # После удаления K символов найти

    # сумма квадратов строки Value

    result = 0; # инициализировать результат

    while not q.empty():

        temp = q.get()

        temp = temp * (-1)

        result += temp * temp

    return result 

  
Код водителя

if __name__ == "__main__":

    str = "abbccc"

    k = 2

    print(minStringValue(str, k))

  

    str = "aaab"

    k = 2

    print(minStringValue(str, k))

      
# Этот код добавлен
# Сайрахул Джелла


Выход:

6
2

Сложность времени: O (n)

Эта статья предоставлена г-ном Сомешем Авастхи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Минимальная сумма квадратов количества символов в данной строке после удаления k символов

0.00 (0%) 0 votes