Задача: 830. Positions of Large Groups
Сложность: easy

В строке s из строчных букв эти буквы образуют последовательные группы одного и того же символа.
Например, строка s = "abbxxxxzyy" имеет группы "a", "bb", "xxxx", "z" и "yy".
Группа идентифицируется интервалом [start, end], где start и end обозначают начальный и конечный индексы (включительно) группы. В приведенном выше примере "xxxx" имеет интервал [3,6].
Группа считается большой, если в ней 3 или более символов.

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

Пример:

Input: s = "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]
Explanation: The large groups are "ddd", "eeee", and "bbb".

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

1⃣Поддерживайте указатели i и j, где i <= j. Указатель i представляет начало текущей группы, а j будет инкрементироваться вперед, пока не достигнет конца группы.

2⃣Когда j достигнет конца строки или S[j] != S[j+1], у нас будет группа [i, j]. Если длина группы больше или равна 3, добавьте её в результат.

3⃣Обновите i = j + 1 и начните новую группу.

😎 Решение:

class Solution {
    fun largeGroupPositions(S: String): List<List<Int>> {
        val ans = mutableListOf<List<Int>>()
        var i = 0
        val N = S.length

        for (j in 0 until N) {
            if (j == N - 1 || S[j] != S[j + 1]) {
                if (j - i + 1 >= 3) {
                    ans.add(listOf(i, j))
                }
                i = j + 1
            }
        }

        return ans
    }

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

Задача: 252. Meeting Rooms
Сложность: easy

Дан массив интервалов времени встреч, где intervals[i] = [starti, endi]. Определите, может ли человек посетить все встречи.

Пример:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false

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

1⃣Создайте функцию для проверки перекрытия двух интервалов:
Возвращайте true, если начало одного интервала находится внутри другого интервала.

2⃣Проверьте каждый интервал с каждым другим интервалом:
Если найдено перекрытие, верните false.

3⃣Если все интервалы проверены и перекрытий не найдено, верните true.

😎 Решение:

class Solution {
    fun canAttendMeetings(intervals: List<List<Int>>): Boolean {
        fun overlap(interval1: List<Int>, interval2: List<Int>): Boolean {
            return (interval1[0] >= interval2[0] && interval1[0] < interval2[1]) ||
                   (interval2[0] >= interval1[0] && interval2[0] < interval1[1])
        }

        for (i in intervals.indices) {
            for (j in i + 1 until intervals.size) {
                if (overlap(intervals[i], intervals[j])) {
                    return false
                }
            }
        }
        return true
    }
}

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

Задача: 416. Partition Equal Subset Sum
Сложность: medium

Если задан целочисленный массив nums, верните третье максимальное число в этом массиве. Если третьего максимального числа не существует, верните максимальное число.

Пример:

Input: nums = [1,5,11,5]
Output: true

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

1⃣Проверьте, является ли сумма всех элементов массива четной. Если нет, верните false.

2⃣Используйте динамическое программирование для определения, можно ли найти подмножество с суммой, равной половине от общей суммы элементов.

3⃣Инициализируйте массив для хранения возможных сумм и обновляйте его, проверяя каждое число в массиве.

😎 Решение:

fun canPartition(nums: IntArray): Boolean {
    val sum = nums.sum()
    if (sum % 2 != 0) return false
    val target = sum / 2
    val dp = BooleanArray(target + 1) { false }
    dp[0] = true
    
    for (num in nums) {
        for (j in target downTo num) {
            dp[j] = dp[j] || dp[j - num]
        }
    }
    
    return dp[target]
}

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

Задача: 417. Pacific Atlantic Water Flow
Сложность: medium

Имеется прямоугольный остров размером m x n, который граничит с Тихим и Атлантическим океанами. Тихий океан касается левого и верхнего краев острова, а Атлантический океан - правого и нижнего краев. Остров разбит на сетку квадратных ячеек. Вам дана целочисленная матрица heights размером m x n, где heights[r][c] - высота над уровнем моря клетки с координатами (r, c). На острове выпадает много осадков, и дождевая вода может стекать в соседние клетки прямо на север, юг, восток и запад, если высота соседней клетки меньше или равна высоте текущей клетки. Вода может течь из любой клетки, прилегающей к океану, в океан. Верните двумерный список координат сетки result, где result[i] = [ri, ci] означает, что дождевая вода может течь из клетки (ri, ci) как в Тихий, так и в Атлантический океаны.

Пример:

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

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

1⃣Определите две матрицы для отслеживания клеток, из которых вода может течь в Тихий и Атлантический океаны, используя поиск в глубину (DFS) или поиск в ширину (BFS), начиная с границ, примыкающих к каждому океану.

2⃣Выполните поиск для каждого океана, обновляя матрицы достижимости.

3⃣Соберите координаты клеток, которые могут стекать в оба океана, проверяя пересечение двух матриц достижимости.

😎 Решение:

fun pacificAtlantic(heights: Array<IntArray>): List<List<Int>> {
    val m = heights.size
    val n = heights[0].size
    val pacific = Array(m) { BooleanArray(n) }
    val atlantic = Array(m) { BooleanArray(n) }
    val directions = arrayOf(intArrayOf(-1, 0), intArrayOf(1, 0), intArrayOf(0, -1), intArrayOf(0, 1))
    
    fun dfs(r: Int, c: Int, ocean: Array<BooleanArray>) {
        ocean[r][c] = true
        for (dir in directions) {
            val nr = r + dir[0]
            val nc = c + dir[1]
            if (nr in 0 until m && nc in 0 until n && !ocean[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                dfs(nr, nc, ocean)
            }
        }
    }
    
    for (i in 0 until m) {
        dfs(i, 0, pacific)
        dfs(i, n - 1, atlantic)
    }
    for (j in 0 until n) {
        dfs(0, j, pacific)
        dfs(m - 1, j, atlantic)
    }
    
    val result = mutableListOf<List<Int>>()
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (pacific[i][j] && atlantic[i][j]) {
                result.add(listOf(i, j))
            }
        }
    }
    return result
}

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