Golang | LeetCode

Задача: 1506. Find Root of N-Ary Tree Сложность: medium Вам даны все узлы N-арного дерева в виде массива объектов Node, где каждый узел имеет уникальное значение. Верните корень N-арного дерева. Пример: Input: tree = [1,null,3,2,4,null,5,6] Output: [1,null,3,2,4,null,5,6] Explanation: The tree from the input data is shown above. The driver code creates the tree and gives findRoot the Node objects in an arbitrary order. For example, the passed array could be [Node(5),Node(4),Node(3),Node(6),Node(2),Node(1)] or [Node(2),Node(6),Node(1),Node(3),Node(5),Node(4)]. The findRoot function should return the root Node(1), and the driver code will serialize it and compare with the input data. The input data and serialized Node(1) are the same, so the test passes. 👨💻 Алгоритм: 1⃣Используйте хэшсет (named as seen) для отслеживания всех посещенных дочерних узлов. В конечном итоге корневой узел не будет в этом множестве. 2⃣Выполняйте первую итерацию, проходя по элементам входного списка. Для каждого элемента добавляйте его дочерние узлы в хэшсет seen. Поскольку значение каждого узла уникально, можно добавлять либо сам узел, либо просто его значение в хэшсет. 3⃣Посетите список еще раз. На этот раз у нас будут все дочерние узлы в хэшсете. Как только вы наткнетесь на узел, который не находится в хэшсете, это и будет корневой узел, который мы ищем. 😎 Решение func findRoot(tree []*Node) *Node {     seen := make(map[int]struct{})     for _, node := range tree {         for _, child := range node.Children {             seen[child.Val] = struct{}{}         }     }     for _, node := range tree {         if _, found := seen[node.Val]; !found {             return node         }     }     return nil } Ставь 👍 и забирай 📚 Базу знаний

🔴 Тестовое собеседование с Go Senior с опытом работы в Яндексе, EPAM и Uzum в этот четверг 3 сентября(в четверг!) в 19:00 по мск приходи онлайн на открытое собеседование, чтобы посмотреть на настоящее интервью на Middle Go-разработчика. Как это будет: 📂 Маруф Караев, Senior в европейской компании, ex-Uzum, ex-Яндекс, ex-EPAM будет задавать реальные вопросы и задачи разработчику-добровольцу 📂 Маруф будет комментировать каждый ответ респондента, чтобы дать понять, чего от вас ожидает собеседующий на интервью 📂 В конце можно будет задать любой вопрос Маруфу Это бесплатно. Эфир проходит в рамках менторской программы от ШОРТКАТ для Go-разработчиков, которые хотят повысить свой грейд, ЗП и прокачать скиллы. Переходи в нашего бота, чтобы получить ссылку на эфир → @shortcut_go_bot Реклама. О рекламодателе.

Задача: 789. Escape The Ghosts Сложность: medium Вы играете в упрощенную игру PAC-MAN на бесконечной 2D-сетке. Вы начинаете в точке [0, 0], и у вас есть конечная точка target = [xtarget, ytarget], к которой вы пытаетесь добраться. На карте находятся несколько привидений, их начальные позиции заданы в виде двумерного массива ghosts, где ghosts[i] = [xi, yi] представляет начальную позицию i-го привидения. Все входные данные являются целочисленными координатами. Каждый ход вы и все привидения можете независимо выбирать перемещение на 1 единицу в любом из четырех основных направлений: север, восток, юг или запад, или оставаться на месте. Все действия происходят одновременно. Вы сможете сбежать, если и только если сможете достичь цели раньше, чем любое привидение достигнет вас. Если вы достигнете любой клетки (включая конечную точку) одновременно с привидением, это не считается побегом. Верните true, если можно сбежать независимо от того, как движутся привидения, иначе верните false. Пример: Input: ghosts = [[1,0],[0,3]], target = [0,1] Output: true Explanation: You can reach the destination (0, 1) after 1 turn, while the ghosts located at (1, 0) and (0, 3) cannot catch up with you. 👨💻 Алгоритм: 1⃣Проверьте, что наше таксическое расстояние до цели меньше, чем расстояние от любого привидения до цели. 2⃣Если это так, мы можем гарантированно добраться до цели раньше любого привидения. 3⃣Если привидение может добраться до цели раньше нас или одновременно с нами, побег невозможен. 😎 Решение: package main import "math" func escapeGhosts(ghosts [][]int, target []int) bool { taxi := func(P, Q []int) int { return int(math.Abs(float64(P[0] - Q[0])) + math.Abs(float64(P[1] - Q[1]))) } playerDistance := taxi([]int{0, 0}, target) for _, ghost := range ghosts { if taxi(ghost, target)

Задача: 1339. Maximum Product of Splitted Binary Tree Сложность: medium Дано корневое дерево. Разделите бинарное дерево на два поддерева, удалив одно ребро так, чтобы произведение сумм поддеревьев было максимальным. Верните максимальное произведение сумм двух поддеревьев. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7. Обратите внимание, что вам нужно максимально увеличить ответ до взятия модуля, а не после. Пример: Input: root = [1,2,3,4,5,6] Output: 110 Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10) 👨💻 Алгоритм: 1⃣Рассчитать сумму значений всех узлов дерева и сохранить суммы всех поддеревьев в списке. 2⃣Перебрать все сохраненные суммы поддеревьев и для каждой вычислить произведение суммы поддерева и разности между общей суммой дерева и данной суммой поддерева. 3⃣Найти максимальное произведение среди всех вычисленных и вернуть его значение по модулю 10^9 + 7. 😎 Решение: type TreeNode struct { Val int Left *TreeNode Right *TreeNode } type Solution struct { allSums []int } func (s *Solution) MaxProduct(root *TreeNode) int { totalSum := s.treeSum(root) var best int64 = 0 for _, sum := range s.allSums { best = max(best, int64(sum)*(int64(totalSum)-int64(sum))) } return int(best % 1000000007) } func (s *Solution) treeSum(subroot *TreeNode) int { if subroot == nil { return 0 } leftSum := s.treeSum(subroot.Left) rightSum := s.treeSum(subroot.Right) totalSum := leftSum + rightSum + subroot.Val s.allSums = append(s.allSums, totalSum) return totalSum } func max(a, b int64) int64 { if a > b { return a } return b } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1277. Count Square Submatrices with All Ones Сложность: medium Если задана матрица m * n из единиц и нулей, верните, сколько квадратных подматриц имеют все единицы. Пример: Input: matrix = [   [0,1,1,1],   [1,1,1,1],   [0,1,1,1] ] Output: 15 👨💻 Алгоритм: 1⃣Создайте вспомогательную матрицу dp таких же размеров, что и исходная матрица, для хранения размеров максимальных квадратов. 2⃣Пройдите по каждому элементу матрицы и обновите dp следующим образом: если элемент равен 1, то dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. 3⃣Суммируйте все значения в dp, чтобы получить количество квадратных подматриц, состоящих из всех единиц. 😎 Решение: func countSquares(matrix [][]int) int {     m := len(matrix)     n := len(matrix[0])     dp := make([][]int, m)     for i := range dp {         dp[i] = make([]int, n)     }     count := 0     for i := 0; i < m; i++ {         for j := 0; j < n; j++ {             if matrix[i][j] == 1 {                 if i == 0 || j == 0 {                     dp[i][j] = 1                 } else {                     dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1                 }                 count += dp[i][j]             }         }     }     return count } func min(a, b int) int {     if a < b {         return a     }     return b } Ставь 👍 и забирай 📚 Базу знаний

Задача: 710. Random Pick with Blacklist Сложность: hard Вам дано целое число n и массив уникальных целых чисел blacklist. Разработайте алгоритм выбора случайного целого числа из диапазона [0, n - 1], не входящего в черный список. Любое целое число, находящееся в указанном диапазоне и не входящее в черный список, должно с равной вероятностью быть возвращено. Оптимизируйте алгоритм так, чтобы он минимизировал количество обращений к встроенной функции random вашего языка. Реализуйте класс Solution: Solution(int n, int[] blacklist) Инициализирует объект целым числом n и целым числом из черного списка blacklist. int pick() Возвращает случайное целое число в диапазоне [0, n - 1] и не входящее в черный список. Пример: Input ["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"] [[7, [2, 3, 5]], [], [], [], [], [], [], []] Output [null, 0, 4, 1, 6, 1, 0, 4] 👨💻 Алгоритм: 1⃣Создайте маппинг для чисел, входящих в черный список, чтобы сопоставить их с числами из диапазона [n - len(blacklist), n - 1], которые не входят в черный список. 2⃣Создайте массив для хранения возможных чисел для выбора, исключая числа из черного списка. 3⃣При каждом вызове функции pick() используйте встроенную функцию random для выбора случайного индекса из массива возможных чисел и возвращайте соответствующее значение. 😎 Решение: package main import ( "math/rand" "time" ) type Solution struct { mapping map[int]int bound int } func Constructor(n int, blacklist []int) Solution { mapping := make(map[int]int) bound := n - len(blacklist) blackset := make(map[int]struct{}) for _, b := range blacklist { blackset[b] = struct{}{} } whitelist := bound for _, b := range blacklist { if b < bound { for { if _, exists := blackset[whitelist]; !exists { break } whitelist++ } mapping[b] = whitelist whitelist++ } } return Solution{mapping: mapping, bound: bound} } func (this *Solution) Pick() int { r := rand.Intn(this.bound) if mapped, exists := this.mapping[r]; exists { return mapped } return r } func main() { rand.Seed(time.Now().UnixNano()) } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1396. Design Underground System Сложность: medium Подземная железнодорожная система отслеживает время поездок между станциями для вычисления среднего времени поездки от одной станции до другой. Реализуйте класс UndergroundSystem: - void checkIn(int id, string stationName, int t) Пассажир с карточкой, идентификатор которой равен id, регистрируется на станции stationName в момент времени t. Пассажир может быть зарегистрирован только в одном месте в одно и то же время. - void checkOut(int id, string stationName, int t) Пассажир с карточкой, идентификатор которой равен id, покидает станцию stationName в момент времени t. - double getAverageTime(string startStation, string endStation) Возвращает среднее время, необходимое для поездки от startStation до endStation. Среднее время рассчитывается на основе всех предыдущих поездок от startStation до endStation, где пассажиры зарегистрировались на startStation и вышли на endStation. Время поездки от startStation до endStation может отличаться от времени поездки от endStation до startStation. Перед вызовом getAverageTime как минимум один пассажир уже совершил поездку от startStation до endStation. Предполагается, что все вызовы методов checkIn и checkOut последовательны и происходят в хронологическом порядке. Пример: Input ["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"] [[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]] Output [null,null,null,5.00000,null,null,5.50000] Explanation UndergroundSystem undergroundSystem = new UndergroundSystem(); undergroundSystem.checkIn(10, "Leyton", 3); undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5 undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5 undergroundSystem.checkIn(5, "Leyton", 10); undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6 undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5 👨💻 Алгоритм: 1⃣При регистрации на входе сохраняем информацию о начале пути (станция и время) в словаре checkInData. 2⃣При регистрации на выходе извлекаем информацию о начале пути из checkInData, вычисляем время поездки и обновляем статистику для маршрута в journeyData. 3⃣Для получения среднего времени поездки по заданному маршруту извлекаем статистику из journeyData и вычисляем среднее значение. 😎 Решение: type UndergroundSystem struct { journeyData map[string][2]float64 checkInData map[int][2]interface{} } func Constructor() UndergroundSystem { return UndergroundSystem{ journeyData: make(map[string][2]float64), checkInData: make(map[int][2]interface{}), } } func (this *UndergroundSystem) CheckIn(id int, stationName string, t int) { this.checkInData[id] = [2]interface{}{stationName, t} } func (this *UndergroundSystem) CheckOut(id int, stationName string, t int) { checkIn := this.checkInData[id] startStation := checkIn[0].(string) startTime := checkIn[1].(int) delete(this.checkInData, id) routeKey := startStation + "->" + stationName tripTime := float64(t - startTime) if _, exists := this.journeyData[routeKey]; !exists { this.journeyData[routeKey] = [2]float64{0, 0} } this.journeyData[routeKey][0] += tripTime this.journeyData[routeKey][1] += 1 } func (this *UndergroundSystem) GetAverageTime(startStation string, endStation string) float64 { stats := this.journeyData[startStation+"->"+endStation] return stats[0] / stats[1] } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1134. Armstrong Number Сложность: easy Дано целое число n, верните true, если и только если оно является числом Армстронга. k-значное число n является числом Армстронга, если сумма k-й степени каждой его цифры равна n. Пример: Input: n = 153 Output: true Explanation: 153 is a 3-digit number, and 153 = 1^3 + 5^3 + 3^3. 👨💻 Алгоритм: 1⃣Получите количество цифр в n, преобразовав его в строку и найдя длину. 2⃣Создайте функцию getSumOfKthPowerOfDigits(n, k), которая возвращает сумму k-й степени каждой цифры числа n. Инициализируйте переменную result для хранения результата. Пока n не равно 0, добавляйте k-ю степень последней цифры n к result и удаляйте последнюю цифру. 3⃣Верните true, если результат равен исходному числу n. 😎 Решение: import "math" func getSumOfKthPowerOfDigits(n, k int) int { result := 0 for n != 0 { digit := n % 10 result += int(math.Pow(float64(digit), float64(k))) n /= 10 } return result } func isArmstrong(n int) bool { length := len(strconv.Itoa(n)) return getSumOfKthPowerOfDigits(n, length) == n } Ставь 👍 и забирай 📚 Базу знаний

Задача: 684. Redundant Connection Сложность: medium В этой задаче дерево — это неориентированный граф, который является связным и не содержит циклов. Вам дан граф, который изначально был деревом с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Граф представлен массивом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует ребро между узлами ai и bi в графе. Верните ребро, которое можно удалить, чтобы результирующий граф стал деревом из n узлов. Если существует несколько ответов, верните тот, который встречается последним в исходных данных. Пример: Input: edges = [[1,2],[1,3],[2,3]] Output: [2,3] 👨💻 Алгоритм: 1⃣Для каждого ребра (u, v) создайте представление графа с использованием списка смежности. Это позволит легко выполнять обход в глубину (DFS) для проверки соединений между узлами. 2⃣Выполняйте обход в глубину для каждого ребра, временно удаляя его из графа. Проверьте, можно ли соединить узлы u и v с помощью обхода в глубину. Если узлы остаются соединенными, значит, это ребро является дублирующимся. 3⃣Верните дублирующееся ребро, которое встречается последним в исходных данных. Это обеспечит корректность решения, даже если существует несколько ответов. 😎 Решение: package main func findRedundantConnection(edges [][]int) []int { const MAX_EDGE_VAL = 1000 graph := make([][]int, MAX_EDGE_VAL+1) for i := range graph { graph[i] = make([]int, 0) } seen := make(map[int]bool) var dfs func(source, target int) bool dfs = func(source, target int) bool { if !seen[source] { seen[source] = true if source == target { return true } for _, nei := range graph[source] { if dfs(nei, target) { return true } } } return false } for _, edge := range edges { seen = make(map[int]bool) if len(graph[edge[0]]) > 0 && len(graph[edge[1]]) > 0 && dfs(edge[0], edge[1]) { return edge } graph[edge[0]] = append(graph[edge[0]], edge[1]) graph[edge[1]] = append(graph[edge[1]], edge[0]) } return nil } Ставь 👍 и забирай 📚 Базу знаний