Golang | LeetCode

Задача: 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 } Ставь 👍 и забирай 📚 Базу знаний

Задача: 952. Largest Component Size by Common Factor Сложность: hard Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае. Пример: Input: nums = [4,6,15,35] Output: 4 👨‍💻 Алгоритм: 1⃣Построить граф, в котором узлы представляют числа из массива, а ребра между узлами существуют, если два числа имеют общий делитель больше 1. 2⃣Использовать алгоритм Union-Find для объединения узлов в связные компоненты. Для каждого числа в массиве nums найти его простые делители и использовать их для объединения узлов. 3⃣Найти размер наибольшей связной компоненты. 😎 Решение: package main import ( "math" ) func largestComponentSize(nums []int) int { parent := make(map[int]int) rank := make(map[int]int) for _, num := range nums { parent[num] = num rank[num] = 0 } var find func(int) int find = func(x int) int { if parent[x] != x { parent[x] = find(parent[x]) } return parent[x] } union := func(x, y int) { rootX := find(x) rootY := find(y) if rootX != rootY { if rank[rootX] > rank[rootY] { parent[rootY] = rootX } else if rank[rootX] < rank[rootY] { parent[rootX] = rootY } else { parent[rootY] = rootX rank[rootX]++ } } } primeFactors := func(n int) map[int]struct{} { factors := make(map[int]struct{}) d := 2 for d*d <= n { for n%d == 0 { factors[d] = struct{}{} n /= d } d++ } if n > 1 { factors[n] = struct{}{} } return factors } primeToIndex := make(map[int][]int) for _, num := range nums { primes := primeFactors(num) for prime := range primes { primeToIndex[prime] = append(primeToIndex[prime], num) } } for _, primes := range primeToIndex { for i := 1; i < len(primes); i++ { union(primes[0], primes[i]) } } size := make(map[int]int) for _, num := range nums { root := find(num) size[root]++ } maxSize := 0 for _, value := range size { if value > maxSize { maxSize = value } } return maxSize } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1305. All Elements in Two Binary Search Trees Сложность: medium Даны два бинарных дерева поиска root1 и root2. Вернуть список, содержащий все целые числа из обоих деревьев, отсортированные в порядке возрастания. Пример: Input: root1 = [2,1,4], root2 = [1,0,3] Output: [0,1,1,2,3,4] 👨‍💻 Алгоритм: 1⃣Выполните итеративный обход в порядке возрастания обоих деревьев параллельно. 2⃣На каждом шаге добавляйте наименьшее доступное значение в выходной список. 3⃣Верните выходной список. 😎 Решение: package main type TreeNode struct { Val int Left *TreeNode Right *TreeNode } func getAllElements(root1 *TreeNode, root2 *TreeNode) []int { stack1, stack2 := []*TreeNode{}, []*TreeNode{} output := []int{} for root1 != nil || root2 != nil || len(stack1) > 0 || len(stack2) > 0 { for root1 != nil { stack1 = append(stack1, root1) root1 = root1.Left } for root2 != nil { stack2 = append(stack2, root2) root2 = root2.Left } if len(stack2) == 0 || (len(stack1) > 0 && stack1[len(stack1)-1].Val <= stack2[len(stack2)-1].Val) { root1 = stack1[len(stack1)-1] stack1 = stack1[:len(stack1)-1] output = append(output, root1.Val) root1 = root1.Right } else { root2 = stack2[len(stack2)-1] stack2 = stack2[:len(stack2)-1] output = append(output, root2.Val) root2 = root2.Right } } return output } Ставь 👍 и забирай 📚 Базу знаний

Задача: 941. Valid Mountain Array Сложность: easy Задав массив целых чисел arr, верните true тогда и только тогда, когда он является допустимым горным массивом. Напомним, что arr является горным массивом тогда и только тогда, когда: arr.length >= 3 Существует некоторое i с 0 < i < arr.length - 1 такое, что: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] arr[i] > arr[i + 1] > ... > arr[arr.length - 1] Пример: Input: arr = [2,1] Output: false 👨‍💻 Алгоритм: 1⃣Убедиться, что длина массива не меньше 3. 2⃣Найти вершину горы, которая удовлетворяет условиям горного массива. Проверить, что все элементы слева от вершины строго возрастают. Проверить, что все элементы справа от вершины строго убывают. 3⃣Вернуть true, если оба условия выполнены, иначе вернуть false. 😎 Решение: package main func validMountainArray(arr []int) bool { if len(arr) < 3 { return false } i := 1 for i < len(arr) && arr[i] > arr[i-1] { i++ } if i == 1 || i == len(arr) { return false } for i < len(arr) && arr[i] < arr[i-1] { i++ } return i == len(arr) } Ставь 👍 и забирай 📚 Базу знаний

Задача: 442. Find All Duplicates in an Array Сложность: medium Дан целочисленный массив nums длины n, где все целые числа nums находятся в диапазоне [1, n], и каждое число появляется один или два раза. Верните массив всех чисел, которые появляются дважды. Вы должны написать алгоритм, который работает за время O(n) и использует только постоянное дополнительное пространство. Пример: Input: nums = [4,3,2,7,8,2,3,1] Output: [2,3] 👨‍💻 Алгоритм: 1⃣Когда мы итерируемся по элементам входного массива, мы можем просто искать любое другое вхождение текущего элемента в оставшейся части массива. 2⃣Поскольку элемент может появляться только один или два раза, нам не нужно беспокоиться о получении дубликатов элементов, которые появляются дважды: Случай I: Если элемент встречается в массиве только один раз, при поиске его в остальной части массива ничего не найдется. Случай II: Если элемент встречается дважды, вы найдете второе вхождение элемента в оставшейся части массива. Когда вы наткнетесь на второе вхождение в более поздней итерации, это будет аналогично случаю I (поскольку больше вхождений этого элемента в оставшейся части массива не будет). 3⃣Таким образом, можно эффективно определить все элементы, которые встречаются дважды, и добавить их в результирующий массив, проходя по каждому элементу массива и проверяя наличие его второго вхождения в оставшейся части массива. 😎 Решение: func findDuplicates(nums []int) []int { ans := []int{} for i := 0; i < len(nums); i++ { for j := i + 1; j < len(nums); j++ { if nums[j] == nums[i] { ans = append(ans, nums[i]) break } } } return ans } Ставь 👍 и забирай 📚 Базу знаний

Задача: 256. Paint House Сложность: medium Есть ряд из n домов, где каждый дом можно покрасить в один из трёх цветов: красный, синий или зелёный. Стоимость покраски каждого дома в определённый цвет разная. Необходимо покрасить все дома так, чтобы никакие два соседних дома не были окрашены в один и тот же цвет. Стоимость покраски каждого дома в определённый цвет представлена в виде матрицы стоимости n x 3. Например, costs[0][0] — это стоимость покраски дома 0 в красный цвет; costs[1][2] — это стоимость покраски дома 1 в зелёный цвет и так далее... Верните минимальную стоимость покраски всех домов. Пример: Input: costs = [[17,2,17],[16,16,5],[14,3,19]] Output: 10 Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. Minimum cost: 2 + 5 + 3 = 10. 👨‍💻 Алгоритм: 1⃣Инициализируйте массив dp размера n x 3 для хранения минимальных затрат на покраску домов. Установите начальные значения для первого дома: dp[0][0] = costs[0][0], dp[0][1] = costs[0][1], dp[0][2] = costs[0][2]. 2⃣Для каждого дома i от 1 до n-1 обновите значения массива dp: dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2]) dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2]) dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1]) 3⃣Верните минимальное значение из последней строки массива dp: min(dp[n-1][0], dp[n-1][1], dp[n-1][2]). 😎 Решение: func minCost(costs [][]int) int { n := len(costs) dp := make([][3]int, n) dp[0] = [3]int{costs[0][0], costs[0][1], costs[0][2]} for i := 1; i < n; i++ { dp[i][0] = costs[i][0] + min(dp[i-1][1], dp[i-1][2]) dp[i][1] = costs[i][1] + min(dp[i-1][0], dp[i-1][2]) dp[i][2] = costs[i][2] + min(dp[i-1][0], dp[i-1][1]) } return min(dp[n-1][0], dp[n-1][1], dp[n-1][2]) } func min(a, b int) int { if a < b { return a } return b } Ставь 👍 и забирай 📚 Базу знаний

Задача: 936. Stamping The Sequence Сложность: hard Вам даны две строки stamp и target. Изначально имеется строка s длины target.length со всеми s[i] == '?'. За один ход вы можете поместить штамп над s и заменить каждую букву в s на соответствующую букву из штампа. Например, если штамп = "abc" и target = "abcba", то s изначально будет "?????". За один ход вы можете: поместить штамп в индекс 0 s, чтобы получить "abc??", поместить штамп в индекс 1 s, чтобы получить "?abc?", или поместить штамп в индекс 2 s, чтобы получить "??abc". Обратите внимание, что штамп должен полностью находиться в границах s, чтобы штамповать (то есть вы не можете поместить штамп в индекс 3 s). Мы хотим преобразовать s в цель, используя не более 10 * target.length ходов. Верните массив индекса самой левой буквы, которая штампуется на каждом ходу. Если мы не можем получить цель из s за 10 * target.length оборотов, верните пустой массив Пример: Input: stamp = "abc", target = "ababc" Output: [0,2] 👨‍💻 Алгоритм: 1⃣Инициализировать переменные: s как массив символов '?', длиной target.length. res как список для хранения результатов. done как массив булевых значений для отслеживания того, какие позиции уже штампованы. target как массив символов для удобства. 2⃣Использовать функцию canStamp для проверки, можно ли штамповать stamp в target начиная с индекса i. Использовать функцию doStamp для штампования stamp в target начиная с индекса i. Повторять шаги, пока штампы возможны или достигнут максимум ходов (10 * target.length): Перебрать все возможные начальные позиции для штампа. Проверить, можно ли штамповать в текущей позиции. Если можно, штамповать и добавить индекс в res. 3⃣Если все символы в s соответствуют символам в target, вернуть массив res в обратном порядке. Иначе, вернуть пустой массив. 😎 Решение: package main func movesToStamp(stamp string, target string) []int { s, t := []rune(stamp), []rune(target) m, n := len(s), len(t) res := []int{} done := make([]bool, n) canStamp := func(i int) bool { for j := 0; j < m; j++ { if t[i + j] != '?' && t[i + j] != s[j] { return false; } } return true; } doStamp := func(i int) { for j := 0; j < m; j++ { t[i + j] = '?' } res = append(res, i) done[i] = true } changed := true for changed { changed = false for i := 0; i <= n - m; i++ { if !done[i] && canStamp(i) { doStamp(i) changed = true } } } for _, c := range t { if c != '?' { return []int{} } } for i, j := 0, len(res) - 1; i < j; i, j = i + 1, j - 1 { res[i], res[j] = res[j], res[i] } return res } Ставь 👍 и забирай 📚 Базу знаний

Задача: 405. Convert a Number to Hexadecimal Сложность: easy Если задано целое число num, верните строку, представляющую его шестнадцатеричное представление. Для отрицательных целых чисел используется метод дополнения до двух. Все буквы в строке ответа должны быть строчными, и в ответе не должно быть никаких ведущих нулей, кроме самого нуля. Примечание: Вам не разрешается использовать какие-либо встроенные библиотечные методы для непосредственного решения этой задачи. Пример: Input: num = 26 Output: "1a" 👨‍💻 Алгоритм: 1⃣Определите, является ли число отрицательным. Если да, преобразуйте его в положительное число с помощью метода дополнения до двух. Для этого прибавьте к числу 2^32 и используйте битовую операцию И с маской 0xFFFFFFFF. 2⃣Создайте строку с шестнадцатеричными символами. Последовательно делите число на 16 и добавляйте соответствующий символ к результату, пока число не станет равным нулю. 3⃣Переверните строку результата и удалите ведущие нули, если они есть. Если строка пустая, верните "0". 😎 Решение: package main import ( "fmt" "strings" ) func toHex(num int) string { if num == 0 { return "0" } hexChars := "0123456789abcdef" if num < 0 { num += 1 << 32 } result := []byte{} for num > 0 { result = append(result, hexChars[num%16]) num /= 16 } for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 { result[i], result[j] = result[j], result[i] } return string(result) } func main() { fmt.Println(toHex(26)) fmt.Println(toHex(-1)) } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1262. Greatest Sum Divisible by Three Сложность: medium Если задан целочисленный массив nums, верните максимально возможную сумму элементов массива, которая делится на три. Пример: Input: nums = [3,6,5,1,8] Output: 18 👨‍💻 Алгоритм: 1⃣Найдите сумму всех элементов массива. 2⃣Если сумма делится на 3, то она и есть ответ. 3⃣Если сумма при делении на 3 дает остаток 1, удалите один элемент с остатком 1 или два элемента с остатком 2 (если их сумма равна 2). Если сумма при делении на 3 дает остаток 2, удалите один элемент с остатком 2 или два элемента с остатком 1 (если их сумма равна 2). 😎 Решение: import (     "sort" ) func maxSumDivThree(nums []int) int {     totalSum := 0     for _, num := range nums {         totalSum += num     }     if totalSum % 3 == 0 {         return totalSum     }         mod1 := []int{}     mod2 := []int{}         for _, num := range nums {         if num % 3 == 1 {             mod1 = append(mod1, num)         } else if num % 3 == 2 {             mod2 = append(mod2, num)         }     }         sort.Ints(mod1)     sort.Ints(mod2)         if totalSum % 3 == 1 {         remove1 := int(^uint(0) >> 1) // maximum int         if len(mod1) > 0 {             remove1 = mod1[0]         }         remove2 := int(^uint(0) >> 1)         if len(mod2) >= 2 {             remove2 = mod2[0] + mod2[1]         }         if remove1 < remove2 {             return totalSum - remove1         } else {             return totalSum - remove2         }     } else {         remove2 := int(^uint(0) >> 1)         if len(mod2) > 0 {             remove2 = mod2[0]         }         remove1 := int(^uint(0) >> 1)         if len(mod1) >= 2 {             remove1 = mod1[0] + mod1[1]         }         if remove2 < remove1 {             return totalSum - remove2         } else {             return totalSum - remove1         }     } } Ставь 👍 и забирай 📚 Базу знаний

Задача: 970. Powerful Integers Сложность: medium Даны три целых числа x, y и bound. Верните список всех мощных чисел, которые имеют значение меньше или равное bound. Целое число является мощным, если оно может быть представлено как x^i + y^j для некоторых целых чисел i >= 0 и j >= 0. Вы можете вернуть ответ в любом порядке. В вашем ответе каждое значение должно встречаться не более одного раза. Пример: Input: x = 2, y = 3, bound = 10 Output: [2,3,4,5,7,9,10] Explanation: 2 = 20 + 30 3 = 21 + 30 4 = 20 + 31 5 = 21 + 31 7 = 22 + 31 9 = 23 + 30 10 = 20 + 32 👨‍💻 Алгоритм: 1⃣Вычислите степени a и b как логарифмы bound по основаниям x и y соответственно. Создайте множество powerfulIntegers для хранения результатов. 2⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers. 3⃣Используйте вложенные циклы, где внешний цикл проходит от 0 до a, а внутренний цикл от 0 до b. На каждом шаге вычисляйте x^i + y^j и, если значение меньше или равно bound, добавляйте его в множество powerfulIntegers. 😎 Решение: package main import ( "math" ) func powerfulIntegers(x int, y int, bound int) []int { a := bound if x != 1 { a = int(math.Log(float64(bound)) / math.Log(float64(x))) } b := bound if y != 1 { b = int(math.Log(float64(bound)) / math.Log(float64(y))) } powerfulIntegers := make(map[int]struct{}) for i := 0; i <= a; i++ { for j := 0; j <= b; j++ { value := int(math.Pow(float64(x), float64(i))) + int(math.Pow(float64(y), float64(j))) if value Ставь 👍 и забирай 📚 Базу знаний

Задача: 847. Shortest Path Visiting All Nodes Сложность: hard У вас есть неориентированный связный граф из n узлов, пронумерованных от 0 до n - 1. Вам дан массив graph, где graph[i] — это список всех узлов, соединенных с узлом i ребром. Верните длину кратчайшего пути, который посещает каждый узел. Вы можете начать и закончить в любом узле, вы можете несколько раз посещать узлы и использовать ребра повторно. Пример: Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]] Output: 4 Explanation: One possible path is [0,1,4,2,3] 👨‍💻 Алгоритм: 1⃣Если граф содержит только один узел, верните 0, так как мы можем начать и закончить в этом узле, не делая никаких шагов. 2⃣Инициализируйте необходимые переменные: количество узлов n, маску окончания endingMask, структуру данных seen для предотвращения циклов, очередь для выполнения BFS и счетчик шагов steps. 3⃣Заполните очередь и seen начальными состояниями (начало в каждом узле с маской, указывающей, что посещен только данный узел), затем выполните BFS для поиска кратчайшего пути, который посещает все узлы. Если найден путь, возвращайте количество шагов. 😎 Решение: type Pair struct { node, mask int } func shortestPathLength(graph [][]int) int { n := len(graph) if n == 1 { return 0 } endingMask := (1 << n) - 1 seen := make([][]bool, n) for i := range seen { seen[i] = make([]bool, endingMask) } queue := []Pair{} for i := 0; i < n; i++ { queue = append(queue, Pair{i, 1 << i}) seen[i][1<<i] = true } steps := 0 for len(queue) > 0 { nextQueue := []Pair{} for _, p := range queue { node, mask := p.node, p.mask for _, neighbor := range graph[node] { nextMask := mask | (1 << neighbor) if nextMask == endingMask { return 1 + steps } if !seen[neighbor][nextMask] { seen[neighbor][nextMask] = true nextQueue = append(nextQueue, Pair{neighbor, nextMask}) } } } steps++ queue = nextQueue } return -1 } Ставь 👍 и забирай 📚 Базу знаний

Задача: 713. Subarray Product Less Than K Сложность: medium Если задан массив целых чисел nums и целое число k, верните количество смежных подмассивов, в которых произведение всех элементов в подмассиве строго меньше k. Пример: Input: nums = [10,5,2,6], k = 100 Output: 8 👨‍💻 Алгоритм: 1⃣Инициализируйте переменные для отслеживания текущего произведения и количества допустимых подмассивов. Используйте два указателя для границ подмассива. 2⃣Перемещайте правый указатель по массиву и умножайте текущий элемент на текущее произведение. Если произведение становится больше или равно k, перемещайте левый указатель, уменьшая произведение до тех пор, пока оно снова не станет меньше k. 3⃣Подсчитайте количество подмассивов с текущим правым указателем, добавив к общему количеству допустимых подмассивов разницу между правым и левым указателями. 😎 Решение: package main func numSubarrayProductLessThanK(nums []int, k int) int { if k <= 1 { return 0 } product, count, left := 1, 0, 0 for right := 0; right < len(nums); right++ { product *= nums[right] for product >= k { product /= nums[left] left++ } count += right - left + 1 } return count } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1533. Find the Index of the Large Integer Сложность: medium У нас есть целочисленный массив arr, в котором все элементы равны, кроме одного элемента, который больше остальных. Вам не будет предоставлен прямой доступ к массиву, вместо этого у вас будет API ArrayReader, который имеет следующие функции: int compareSub(int l, int r, int x, int y): где 0 <= l, r, x, y < ArrayReader.length(), l <= r и x <= y. Функция сравнивает сумму подмассива arr[l..r] с суммой подмассива arr[x..y] и возвращает: 1, если arr[l] + arr[l+1] + ... + arr[r] > arr[x] + arr[x+1] + ... + arr[y]. 0, если arr[l] + arr[l+1] + ... + arr[r] == arr[x] + arr[x+1] + ... + arr[y]. -1, если arr[l] + arr[l+1] + ... + arr[r] < arr[x] + arr[x+1] + ... + arr[y]. int length(): Возвращает размер массива. Вам разрешено вызывать compareSub() не более 20 раз. Вы можете предположить, что обе функции работают за O(1) время. Верните индекс массива arr, который содержит наибольший элемент. Пример: Input: arr = [7,7,7,7,10,7,7,7] Output: 4 Explanation: The following calls to the API reader.compareSub(0, 0, 1, 1) // returns 0 this is a query comparing the sub-array (0, 0) with the sub array (1, 1), (i.e. compares arr[0] with arr[1]). Thus we know that arr[0] and arr[1] doesn't contain the largest element. reader.compareSub(2, 2, 3, 3) // returns 0, we can exclude arr[2] and arr[3]. reader.compareSub(4, 4, 5, 5) // returns 1, thus for sure arr[4] is the largest element in the array. Notice that we made only 3 calls, so the answer is valid. 👨‍💻 Алгоритм: 1⃣Установите left = 0 и length = reader.length. left - это самый левый индекс нашего поискового пространства, а length - это размер нашего поискового пространства. Индекс большего числа всегда должен находиться в пределах [left, left + length). 2⃣Пока length > 1: — Обновите length до length / 2. — Установите cmp равным reader.compareSub(left, left + length - 1, left + length, left + length + length - 1). — Если cmp равно 0, верните left + length + length, так как оставшийся элемент является большим числом. Это возможно только если текущее поисковое пространство имеет нечетную длину, поэтому если у нас четная длина, мы не беспокоимся об этом случае. — Если cmp равно -1, увеличьте left на length. — Если cmp равно 1, ничего не делайте, так как наш left остается прежним и мы уже разделили length на 2. 3⃣Верните left. Это стандартная процедура для бинарного поиска, когда если поиск завершается без возврата, то левая граница указывает на ответ. 😎 Решение type ArrayReader struct{} func (ar *ArrayReader) CompareSub(l, r, x, y int) int {     return 0 } func (ar *ArrayReader) Length() int {     return 0 } type Solution struct{} func (s *Solution) GetIndex(reader *ArrayReader) int {     left := 0     length := reader.Length()     for length > 1 {         length /= 2         cmp := reader.CompareSub(left, left+length-1, left+length, left+2*length-1)         if cmp == 0 {             return left + 2*length         }         if cmp < 0 {             left += length         }     }     return left } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1250. Check If It Is a Good Array Сложность: hard Дан массив nums из целых положительных чисел. Ваша задача - выбрать некоторое подмножество nums, умножить каждый элемент на целое число и сложить все эти числа.Массив считается хорошим, если из него можно получить сумму, равную 1, при любом возможном подмножестве и множителе. Верните True, если массив хороший, иначе верните False. Пример: Input: nums = [12,5,7,23] Output: true 👨‍💻 Алгоритм: 1⃣Если наибольший общий делитель (НОД) всех чисел в массиве равен 1, то массив считается хорошим. 2⃣Если НОД всех чисел больше 1, то массив не считается хорошим 3⃣Получить сумму, равную 1, умножая и складывая элементы. 😎 Решение: func isGoodArray(nums []int) bool {     gcd := nums[0]     for _, num := range nums {         gcd = gcdFunc(gcd, num)         if gcd == 1 {             return true         }     }     return gcd == 1 } func gcdFunc(a, b int) int {     for b != 0 {         a, b = b, a % b     }     return a } Ставь 👍 и забирай 📚 Базу знаний

Задача: 532. K-diff Pairs in an Array Сложность: medium Дан массив целых чисел nums и целое число k. Верните количество уникальных пар с разницей k в массиве. Пара с разницей k — это пара целых чисел (nums[i], nums[j]), для которой выполняются следующие условия: 0 <= i, j < nums.length i != j |nums[i] - nums[j]| == k Обратите внимание, что |val| обозначает абсолютное значение val. Пример: Input: nums = [3,1,4,1,5], k = 2 Output: 2 Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5). Although we have two 1s in the input, we should only return the number of unique pairs. 👨‍💻 Алгоритм: 1⃣ Создайте частотный хэш-словарь для подсчета количества каждого уникального числа в массиве nums. 2⃣ Для каждого ключа в хэш-словаре проверьте, можно ли найти пару, удовлетворяющую условиям: Если k > 0, проверьте, существует ли ключ, равный x + k. Если k == 0, проверьте, есть ли более одного вхождения x. 3⃣ Увеличьте счётчик результатов, если условие выполняется. 😎 Решение: func findPairs(nums []int, k int) int { counter := make(map[int]int) for _, num := range nums { counter[num]++ } result := 0 for x, val := range counter { if k > 0 { if _, exists := counter[x + k]; exists { result++ } } else if k == 0 && val > 1 { result++ } } return result } Ставь 👍 и забирай 📚 Базу знаний

Задача: 229. Majority Element II Сложность: medium Дан массив целых чисел размера n, найдите все элементы, которые встречаются более ⌊ n/3 ⌋ раз. Пример: Input: nums = [3,2,3] Output: [3] 👨‍💻 Алгоритм: 1⃣Поиск кандидатов: Пройдите через массив, используя алгоритм Бойера-Мура для поиска двух потенциальных кандидатов, которые могут встречаться более ⌊ n/3 ⌋ раз. Поддерживайте два счётчика и двух кандидатов. Если текущий элемент равен одному из кандидатов, увеличьте соответствующий счётчик. Если счётчик равен нулю, установите текущий элемент как кандидата и установите счётчик в 1. Если текущий элемент не совпадает ни с одним из кандидатов, уменьшите оба счётчика. 2⃣Подсчёт голосов: После определения двух кандидатов, пройдите через массив снова, чтобы посчитать фактическое количество появлений каждого кандидата. 3⃣Проверка порога: Проверьте, превышает ли количество появлений каждого кандидата порог ⌊ n/3 ⌋. Если да, добавьте кандидата в результат. 😎 Решение: package main func majorityElement(nums []int) []int { count1, count2 := 0, 0 var candidate1, candidate2 *int for _, n := range nums { if candidate1 != nil && *candidate1 == n { count1++ } else if candidate2 != nil && *candidate2 == n { count2++ } else if count1 == 0 { candidate1 = &n count1 = 1 } else if count2 == 0 { candidate2 = &n Ставь 👍 и забирай 📚 Базу знаний

Задача: 926. Flip String to Monotone Increasing Сложность: medium Двоичная строка является монотонно возрастающей, если она состоит из некоторого количества 0 (возможно, ни одного), за которым следует некоторое количество 1 (также возможно, ни одного). Вам дана двоичная строка s. Вы можете перевернуть s[i], изменив ее значение с 0 на 1 или с 1 на 0. Пример: Input: s = "00110" Output: 1 👨‍💻 Алгоритм: 1⃣Создать массив left для подсчета количества операций, чтобы сделать подстроку до текущего индекса монотонной (только 0). 2⃣Создать массив right для подсчета количества операций, чтобы сделать подстроку после текущего индекса монотонной (только 1). Пройти по строке и заполнить массивы left и right. 3⃣Пройти по строке и найти минимальное количество операций, чтобы сделать всю строку монотонной. 😎 Решение: package main func minFlipsMonoIncr(s string) int { n := len(s) left := make([]int, n+1) right := make([]int, n+1) for i := 0; i < n; i++ { left[i+1] = left[i] if s[i] == '1' { left[i+1]++ } } for i := n - 1; i >= 0; i-- { right[i] = right[i+1] if s[i] == '0' { right[i]++ } } result := n for i := 0; i <= n; i++ { if sum := left[i] + right[i]; sum < result { result = sum } } return result } Ставь 👍 и забирай 📚 Базу знаний

Задача: 672. Bulb Switcher II Сложность: medium Дано количество лампочек n (все включены) и количество нажатий presses. Есть 4 кнопки с разной логикой. Нужно определить, сколько различных состояний лампочек может быть получено после ровно presses нажатий. Пример: Input: n = 1, presses = 1` → Output: 2 👨‍💻 Алгоритм: 1⃣Ограничиваем количество лампочек до 6 Поскольку шаблоны переключений кнопок начинают повторяться при n > 6, достаточно проверять только первые min(n, 6) лампочек. Остальные комбинации будут симметричны и не дадут новых состояний. 2⃣Перебираем все возможные комбинации нажатий кнопок Каждая из 4 кнопок может быть либо нажата, либо нет — всего 2⁴ = 16 комбинаций. Проверяем каждую комбинацию cand, у которой: - Кол-во нажатых кнопок bcount ≤ presses - Чётность bcount % 2 == presses % 2 (так как порядок не важен) 3⃣Симулируем состояние лампочек и собираем уникальные Для каждой валидной комбинации симулируем, какие лампочки будут переключены (с помощью битовых масок и XOR). Сохраняем результат в map, чтобы получить множество уникальных состояний. Возвращаем размер множества. 😎 Решение: import ( "math/bits" ) func flipLights(n int, m int) int { seen := make(map[int]struct{}) n = min(n, 6) shift := max(0, 6-n) for cand := 0; cand < 16; cand++ { bcount := bits.OnesCount(uint(cand)) if bcount % 2 == m % 2 && bcount <= m { lights := 0 if (cand>>0)&1 > 0 { lights ^= 0b111111 >> shift } if (cand>>1)&1 > 0 { lights ^= 0b010101 >> shift } if (cand>>2)&1 > 0 { lights ^= 0b101010 >> shift } if (cand>>3)&1 > 0 { lights ^= 0b100100 >> shift } seen[lights] = struct{}{} } } return len(seen) } func min(a, b int) int { if a < b { return a } return b } func max(a, b int) int { if a > b { return a } return b } Ставь 👍 и забирай 📚 Базу знаний

Задача: 1114. Print in Order Сложность: easy Предположим, у нас есть класс: public class Foo { public void first() { print("first"); } public void second() { print("second"); } public void third() { print("third"); } } Один и тот же экземпляр Foo будет передан трем разным потокам. Поток A вызовет first(), поток B вызовет second(), и поток C вызовет third(). Спроектируйте механизм и модифицируйте программу, чтобы гарантировать, что second() выполняется после first(), а third() выполняется после second(). Примечание: Мы не знаем, как потоки будут планироваться в операционной системе, даже если числа в вводе подразумевают порядок выполнения. Формат ввода, который вы видите, в основном предназначен для обеспечения полноты наших тестов. Пример: Input: nums = [1,2,3] Output: "firstsecondthird" Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output. 👨‍💻 Алгоритм: 1⃣Инициализация переменных: Инициализируйте координационные переменные firstJobDone и secondJobDone, чтобы указать, что задания еще не выполнены. 2⃣Функция first(): В этой функции нет зависимости, поэтому можно сразу приступить к выполнению задания. В конце функции обновите переменную firstJobDone, чтобы указать, что первое задание выполнено. 3⃣Функции second() и third(): В функции second() проверьте статус firstJobDone. Если она не обновлена, подождите, иначе переходите к выполнению второго задания. В конце функции обновите переменную secondJobDone, чтобы отметить завершение второго задания. В функции third() проверьте статус secondJobDone. Аналогично функции second(), подождите сигнала secondJobDone перед тем, как приступить к выполнению третьего задания. 😎 Решение: package main import ( "sync" ) type Foo struct { firstJobDone sync.Mutex secondJobDone sync.Mutex } func NewFoo() *Foo { f := &Foo{} f.firstJobDone.Lock() f.secondJobDone.Lock() return f } func (f *Foo) First(printFirst func()) { printFirst() f.firstJobDone.Unlock() } func (f *Foo) Second(printSecond func()) { f.firstJobDone.Lock() printSecond() f.firstJobDone.Unlock() f.secondJobDone.Unlock() } func (f *Foo) Third(printThird func()) { f.secondJobDone.Lock() printThird() f.secondJobDone.Unlock() } Ставь 👍 и забирай 📚 Базу знаний