Задача: 767. Reorganize String
Сложность: medium

Дана строка s, переставьте символы строки s так, чтобы любые два соседних символа не были одинаковыми.

Верните любую возможную перестановку строки s или верните "", если это невозможно.

Пример:

Input: s = "aab"
Output: "aba"

👨‍💻 Алгоритм:

1⃣Инициализируйте пустой список ans для хранения переставленных символов. Создайте приоритетную очередь pq, используя структуру данных кучи. Каждый элемент в pq — это кортеж, содержащий количество символов и сам символ. Приоритетная очередь упорядочена так, что элементы с большим количеством имеют более высокий приоритет.

2⃣Извлеките элемент с наивысшим приоритетом из pq. Присвойте его количество и символ переменным count_first и char_first соответственно. Если ans пуст или текущий символ char_first отличается от последнего символа в ans, добавьте char_first в ans. Если количество char_first не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Перейдите к следующей итерации.

3⃣В противном случае, если char_first совпадает с последним символом в ans, нужно выбрать другой символ. Если pq пуста, верните пустую строку, так как переставить символы невозможно. Извлеките следующий элемент из pq, присвоив его количество и символ переменным count_second и char_second соответственно. Добавьте char_second в ans. Если количество char_second не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Наконец, поместите оригинальный char_first обратно в pq. Верните переставленные символы как строку, объединив элементы в ans.

😎 Решение:

import java.util.*;

class Solution {
    public String reorganizeString(String s) {
        int[] charCounts = new int[26];
        for (char c : s) {
            charCounts[c - 'a']++;
        }

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int i = 0; i < 26; i++) {
            if (charCounts[i] > 0) {
                pq.add(new int[]{charCounts[i], i + 'a'});
            }
        }
        
        StringBuilder result = new StringBuilder();
        while (!pq.isEmpty()) {
            int[] first = pq.poll();
            if (result.length() == 0 || first[1] != result.charAt(result.length() - 1)) {
                result.append((char)first[1]);
                if (--first[0] > 0) {
                    pq.add(first);
                }
            } else {
                if (pq.isEmpty()) {
                    return "";
                }
                int[] second = pq.poll();
                result.append((char)second[1]);
                if (--second[0] > 0) {
                    pq.add(second);
                }
                pq.add(first);
            }
        }

        return result.toString();
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1464. Maximum Product of Two Elements in an Array
Сложность: easy

Дан массив целых чисел nums, выберите два разных индекса i и j этого массива. Верните максимальное значение (nums[i]-1)*(nums[j]-1).

Пример:

Input: nums = [3,4,5,2]
Output: 12 
Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)*(nums[2]-1) = (4-1)*(5-1) = 3*4 = 12. 

👨‍💻 Алгоритм:

1⃣Инициализируйте biggest = 0 и secondBiggest = 0.

2⃣Итерируйте по каждому элементу массива nums:
Если текущий элемент больше biggest, обновите secondBiggest = biggest и biggest = текущий элемент.
Иначе обновите secondBiggest, если текущий элемент больше secondBiggest.

3⃣Верните (biggest - 1) * (secondBiggest - 1).

😎 Решение:

class Solution {
    public int maxProduct(int[] nums) {
        int biggest = 0;
        int secondBiggest = 0;
        for (int num : nums) {
            if (num > biggest) {
                secondBiggest = biggest;
                biggest = num;
            } else {
                secondBiggest = Math.max(secondBiggest, num);
            }
        }
        
        return (biggest - 1) * (secondBiggest - 1);
    }
}

Ставь 👍 и забирай 📚 Базу знаний