Задача: 1275. Find Winner on a Tic Tac Toe Game
Сложность: easy

В игру "Крестики-нолики" играют два игрока A и B на сетке 3 x 3. Правила игры "Крестики-нолики" таковы: игроки по очереди помещают символы в пустые квадраты ' '. Первый игрок A всегда помещает символы "X", а второй игрок B - "O". Символы "X" и "O" всегда помещаются в пустые квадраты, а не в заполненные.
Игра заканчивается, когда три одинаковых (непустых) символа заполняют любую строку, столбец или диагональ. Игра также заканчивается, если все клетки непустые. Больше ходов не может быть сыграно, если игра закончена. Учитывая двумерный целочисленный массив moves, где moves[i] = [rowi, coli] указывает, что i-й ход будет сыгран на сетке[rowi][coli]. верните победителя игры, если он существует (A или B). Если игра закончилась вничью, верните "Ничья". Если еще есть ходы для игры, верните "Pending". Можно предположить, что ходы действительны (т.е. соответствуют правилам игры в Крестики-нолики), сетка изначально пуста, и A будет играть первым.

Пример:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"

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

1⃣Инициализируйте пустую 3x3 сетку.

2⃣Пройдите по списку ходов и обновите сетку в соответствии с ходами игроков A и B.

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

😎 Решение:

class Solution {
    func tictactoe(_ moves: [[Int]]) -> String {
        var grid = Array(repeating: Array(repeating: "", count: 3), count: 3)
        for (i, move) in moves.enumerated() {
            grid[move[0]][move[1]] = i % 2 == 0 ? "X" : "O"
        }

        for i in 0..<3 {
            if grid[i][0] == grid[i][1] && grid[i][1] == grid[i][2] && grid[i][0] != "" {
                return grid[i][0] == "X" ? "A" : "B"
            }
            if grid[0][i] == grid[1][i] && grid[1][i] == grid[2][i] && grid[0][i] != "" {
                return grid[0][i] == "X" ? "A" : "B"
            }
        }

        if grid[0][0] == grid[1][1] && grid[1][1] == grid[2][2] && grid[0][0] != "" {
            return grid[0][0] == "X" ? "A" : "B"
        }
        if grid[0][2] == grid[1][1] && grid[1][1] == grid[2][0] && grid[0][2] != "" {
            return grid[0][2] == "X" ? "A" : "B"
        }

        return moves.count == 9 ? "Draw" : "Pending"
    }
}

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

Задача: 126.Word Ladder II
Сложность: Hard

Последовательность преобразований от слова beginWord до слова endWord с использованием словаря wordList — это последовательность слов beginWord -> s1 -> s2 -> ... -> sk, для которой выполняются следующие условия:

Каждая пара соседних слов отличается ровно одной буквой.
Каждое si для 1 <= i <= k находится в wordList. Отметим, что beginWord не обязательно должно быть в wordList.
sk == endWord.
Для двух слов, beginWord и endWord, и словаря wordList, вернуть все самые короткие последовательности преобразований от beginWord до endWord или пустой список, если такая последовательность не существует. Каждая последовательность должна возвращаться в виде списка слов [beginWord, s1, s2, ..., sk].

Пример:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation: There are 2 shortest transformation sequences:
"hit" -> "hot" -> "dot" -> "dog" -> "cog"
"hit" -> "hot" -> "lot" -> "log" -> "cog"

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

1⃣Сохранение слов из списка слов (wordList) в хэш-таблицу (unordered set) для эффективного удаления слов в процессе поиска в ширину (BFS).

2⃣Выполнение BFS, добавление связей в список смежности (adjList). После завершения уровня удалять посещенные слова из wordList.

3⃣Начать с beginWord и отслеживать текущий путь как currPath, просматривать все возможные пути, и когда путь ведет к endWord, сохранять путь в shortestPaths.

😎 Решение:

class Solution {
    var adjList = [String: [String]]()
    var shortestPaths = [[String]]()

    func findLadders(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> [[String]] {
        var wordSet = Set(wordList), queue = [beginWord]
        var isEnqueued = [beginWord: true]
        while !queue.isEmpty {
            var visited = [String]()
            for currWord in queue {
                queue.removeFirst()
                for i in 0..<currWord.count {
                    var wordArray = Array(currWord)
                    let oldChar = wordArray[i]
                    for c in Character("a").asciiValue!...Character("z").asciiValue! {
                        wordArray[i] = Character(UnicodeScalar(c))
                        let newWord = String(wordArray)
                        if newWord == currWord || !wordSet.contains(newWord) { continue }
                        visited.append(newWord)
                        adjList[newWord, default: []].append(currWord)
                        if !isEnqueued[newWord, default: false] {
                            queue.append(newWord)
                            isEnqueued[newWord] = true
                        }
                    }
                    wordArray[i] = oldChar
                }
            }
            visited.forEach { wordSet.remove($0) }
        }
        
        func backtrack(_ path: [String], _ word: String) {
            if word == endWord {
                shortestPaths.append(path.reversed())
                return
            }
            for neighbor in adjList[word, default: []] {
                backtrack(path + [neighbor], neighbor)
            }
        }
        
        backtrack([beginWord], beginWord)
        return shortestPaths
    }
}

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

🔥 Записал видос "Как за 3 минуты настроить Автоотклики на вакансии HeadHunter" больше не придется заниматься этой унылой рутиной

📺 Видео: https://youtu.be/G_FOwEGPwlw

Задача: 326. Power of Three
Сложность: easy

Дано целое число n. Верните true, если оно является степенью тройки, иначе верните false.

Целое число n является степенью тройки, если существует целое число x такое, что n == 3^x.

Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

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

1⃣Проверка начального значения
Если n меньше или равно нулю, вернуть false, так как степени тройки всегда положительны.

2⃣Цикл деления на 3
Пока n делится на 3 без остатка, делите n на 3. Повторяйте этот процесс до тех пор, пока n делится на 3.

3⃣Проверка конечного значения
Если после всех делений значение n стало равно 1, значит исходное число является степенью тройки, вернуть true. В противном случае вернуть false.

😎 Решение:

class Solution {
    func isPowerOfThree(_ n: Int) -> Bool {
        if n <= 0 {
            return false
        }
        var num = n
        while num % 3 == 0 {
            num /= 3
        }
        return num == 1
    }
}

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