Задача: 345. Reverse Vowels of a String
Сложность: easy

Дана строка s, переверните только все гласные в строке и верните её.

Гласные: 'a', 'e', 'i', 'o', 'u', а также их верхние регистры.

Пример:

Input: s = "hello"
Output: "holle"

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

1⃣Инициализация указателей и гласных:
Создайте набор гласных для быстрой проверки.
Установите два указателя: один на начало строки (left), другой на конец строки (right).

2⃣Перестановка гласных:
Пока левый указатель меньше правого, перемещайте указатели к центру, пока не найдёте гласные.
Обменивайте найденные гласные и продолжайте сдвигать указатели.

3⃣Завершение работы:
Когда указатели пересекутся, остановите процесс и верните строку.

😎 Решение:

func reverseVowels(s string) string {
    vowels := "aeiouAEIOU"
    chars := []rune(s)
    left, right := 0, len(chars) - 1
    
    isVowel := func(c rune) bool {
        return strings.ContainsRune(vowels, c)
    }
    
    for left < right {
        if !isVowel(chars[left]) {
            left++
        } else if !isVowel(chars[right]) {
            right--
        } else {
            chars[left], chars[right] = chars[right], chars[left]
            left++
            right--
        }
    }
    
    return string(chars)
}

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

Задача: 1535. Find the Winner of an Array Game
Сложность: medium

Дан целочисленный массив arr из различных целых чисел и целое число k.

Игра будет проводиться между первыми двумя элементами массива (т.е. arr[0] и arr[1]). В каждом раунде игры мы сравниваем arr[0] с arr[1], большее число побеждает и остается на позиции 0, а меньшее число перемещается в конец массива. Игра заканчивается, когда одно число выигрывает k подряд раундов.

Верните число, которое выиграет игру.

Гарантируется, что у игры будет победитель.

Пример:

Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round |       arr       | winner | win_count
  1   | [2,1,3,5,4,6,7] | 2      | 1
  2   | [2,3,5,4,6,7,1] | 3      | 1
  3   | [3,5,4,6,7,1,2] | 5      | 1
  4   | [5,4,6,7,1,2,3] | 5      | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

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

1⃣Инициализируйте maxElement как максимальный элемент в arr, queue как очередь с элементами массива, кроме первого, curr = arr[0] и winstreak = 0.

2⃣Пока очередь не пуста (или используйте бесконечный цикл), извлеките opponent из начала очереди. Если curr > opponent, добавьте opponent в конец очереди и увеличьте winstreak на 1. В противном случае добавьте curr в конец очереди, установите curr = opponent и winstreak = 1.

3⃣Если winstreak = k или curr = maxElement, верните curr. Код никогда не должен достигать этой точки, так как гарантированно есть победитель. Верните любое значение.

😎 Решение

public class Solution {
    public int GetWinner(int[] arr, int k) {
        int maxElement = arr[0];
        Queue<int> queue = new Queue<int>();
        for (int i = 1; i < arr.Length; i++) {
            maxElement = Math.Max(maxElement, arr[i]);
            queue.Enqueue(arr[i]);
        }
        
        int curr = arr[0];
        int winstreak = 0;
        
        while (queue.Count > 0) {
            int opponent = queue.Dequeue();
            
            if (curr > opponent) {
                queue.Enqueue(opponent);
                winstreak++;
            } else {
                queue.Enqueue(curr);
                curr = opponent;
                winstreak = 1;
            }
            
            if (winstreak == k || curr == maxElement) {
                return curr;
            }
        }
        
        return -1;
    }
}

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

Задача: 923. 3Sum With Multiplicity
Сложность: medium

Если задан целочисленный массив arr и целое число target, верните количество кортежей i, j, k, таких, что i < j < k и arr[i] + arr[j] + arr[k] == target. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.

Пример:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

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

1⃣Отсортировать массив arr.

2⃣Инициализировать счетчик для количества кортежей.
Пройти по массиву тремя указателями i, j, и k:
Для каждого i, установить j на i + 1, и k на конец массива.
Использовать двухуказательный метод для нахождения пар (j, k), таких что arr[i] + arr[j] + arr[k] == target.

3⃣Вернуть результат по модулю 10^9 + 7.

😎 Решение:

package main

import "sort"

func threeSumMulti(arr []int, target int) int {
    sort.Ints(arr)
    const MOD = 1_000_000_007
    count := 0
    
    for i := 0; i < len(arr); i++ {
        j, k := i+1, len(arr)-1
        for j < k {
            sum := arr[i] + arr[j] + arr[k]
            if sum == target {
                if arr[j] == arr[k] {
                    count += (k - j + 1) * (k - j) / 2
                    break
                } else {
                    left, right := 1, 1
                    for j+1 < k && arr[j] == arr[j+1] {
                        left++
                        j++
                    }
                    for k-1 > j && arr[k] == arr[k-1] {
                        right++
                        k--
                    }
                    count += left * right
                    j++
                    k--
                }
            } else if sum < target {
                j++
            } else {
                k--
            }
        }
    }
    
    return count % MOD
}

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