Golang | LeetCode
Kanalga Telegram’da o‘tish
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Ko'proq ko'rsatish
Tarmoq:3 542
Obunachilar
-124 soatlar
-137 kun
-5630 kun
Ma'lumotlar yuklanmoqda
O'xshash kanallar
Taglar buluti
Kirish va chiqish esdaliklari
---
---
---
---
---
---
Obunachilarni jalb qilish
Oktabr '26Okt '26
Oktabr '26
+11
0 kanalda
Sentabr '26
+19
0 kanalda
Get PRO
Avgust '26
+22
0 kanalda
Get PRO
Iyul '26
+49
0 kanalda
Get PRO
Iyun '26
+22
1 kanalda
Get PRO
May '26
+13
0 kanalda
Get PRO
Aprel '26
+21
0 kanalda
Get PRO
Mart '26
+30
0 kanalda
Get PRO
Fevral '26
+26
0 kanalda
Get PRO
Yanvar '26
+31
0 kanalda
Get PRO
Dekabr '25
+36
0 kanalda
Get PRO
Noyabr '25
+123
1 kanalda
Get PRO
Oktabr '25
+170
1 kanalda
Get PRO
Sentabr '25
+97
0 kanalda
Get PRO
Avgust '25
+156
0 kanalda
Get PRO
Iyul '25
+162
1 kanalda
Get PRO
Iyun '25
+153
0 kanalda
Get PRO
May '25
+149
0 kanalda
Get PRO
Aprel '25
+197
0 kanalda
Get PRO
Mart '25
+320
2 kanalda
Get PRO
Fevral '25
+194
0 kanalda
Get PRO
Yanvar '25
+342
53 kanalda
Get PRO
Dekabr '24
+166
0 kanalda
Get PRO
Noyabr '24
+133
1 kanalda
Get PRO
Oktabr '24
+273
13 kanalda
Get PRO
Sentabr '24
+809
329 kanalda
Get PRO
Avgust '24
+127
0 kanalda
Get PRO
Iyul '24
+671
219 kanalda
Get PRO
Iyun '24
+756
232 kanalda
| Sana | Obunachilarni jalb qilish | Esdaliklar | Kanallar | |
| 26 Oktabr | +1 | |||
| 25 Oktabr | 0 | |||
| 24 Oktabr | +1 | |||
| 23 Oktabr | 0 | |||
| 22 Oktabr | +1 | |||
| 21 Oktabr | +1 | |||
| 20 Oktabr | +1 | |||
| 19 Oktabr | 0 | |||
| 18 Oktabr | +1 | |||
| 17 Oktabr | +2 | |||
| 16 Oktabr | 0 | |||
| 15 Oktabr | 0 | |||
| 14 Oktabr | 0 | |||
| 13 Oktabr | 0 | |||
| 12 Oktabr | 0 | |||
| 11 Oktabr | 0 | |||
| 10 Oktabr | 0 | |||
| 09 Oktabr | +2 | |||
| 08 Oktabr | 0 | |||
| 07 Oktabr | 0 | |||
| 06 Oktabr | 0 | |||
| 05 Oktabr | +1 | |||
| 04 Oktabr | 0 | |||
| 03 Oktabr | 0 | |||
| 02 Oktabr | 0 | |||
| 01 Oktabr | 0 |
Kanal postlari
🎃 Хеллоуинская акция на easyoffer
В честь Хеллоуина до 31 октября можно забрать PRO навсегда. Покупаешь один раз и пользуешься всю жизнь
🍬Что внутри мешка с угощениями:
– База вопросов и задач из собеседований
– Примеры видео-ответов на вопросы
– Записи реальных собеседований
– Тренажёры «Проработка вопросов» и «Реальное собеседование»
– Аналитика требований из вакансий
– Автоотклики на вакансии
👉 Забрать PRO со скидкой 70%: https://easyoffer.ru/pro
| 2 | Задача: 139. Word Break
Сложность: medium
Дана строка s и словарь строк wordDict. Верните true, если строку s можно разделить на последовательность одного или нескольких слов из словаря, разделённых пробелами.
Обратите внимание, что одно и то же слово из словаря может использоваться несколько раз при разделении.
Пример:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
👨💻 Алгоритм:
1⃣Инициализация структур данных:
Преобразуйте wordDict в множество words для быстрой проверки вхождения.
Инициализируйте очередь queue начальным значением 0 (индекс начала строки) и множество seen для отслеживания посещённых индексов.
2⃣Обход в ширину (BFS):
Пока очередь не пуста, извлекайте первый элемент из очереди, обозначающий начальную позицию start.
Если start равен длине строки s, возвращайте true, так как достигнут конец строки, и строку можно разделить на слова из словаря.
Итерируйте end от start + 1 до s.length включительно. Для каждого end, проверьте, посещён ли он уже.
3⃣Проверка подстроки и обновление структур:
Проверьте подстроку начиная с start и заканчивая перед end. Если подстрока находится в множестве words, добавьте end в очередь и отметьте его в seen как посещённый.
Если BFS завершается и конечный узел не достигнут, возвращайте false.
😎 Решение:
func wordBreak(s string, wordDict []string) bool {
words := make(map[string]bool)
queue := make([]int, 0)
seen := make([]bool, len(s)+1)
for _, word := range wordDict {
words[word] = true
}
queue = append(queue, 0)
for len(queue) > 0 {
start := queue[0]
queue = queue[1:]
if start == len(s) {
return true
}
for end := start + 1; end <= len(s); end++ {
if seen[end] {
continue
}
if _, ok := words[s[start:end]]; ok {
queue = append(queue, end)
seen[end] = true
}
}
}
return false
}
Ставь 👍 и забирай 📚 Базу знаний | 79 |
| 3 | Задача: 1120. Maximum Average Subtree
Сложность: medium
Дан корень бинарного дерева. Верните максимальное среднее значение поддерева этого дерева. Ответы, отличающиеся от фактического ответа не более чем на 10^-5, будут приняты.
Поддерево дерева — это любой узел этого дерева плюс все его потомки.
Среднее значение дерева — это сумма его значений, деленная на количество узлов.
Пример:
Input: root = [5,6,1]
Output: 6.00000
Explanation:
For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4.
For the node with value = 6 we have an average of 6 / 1 = 6.
For the node with value = 1 we have an average of 1 / 1 = 1.
So the answer is 6 which is the maximum.
👨💻 Алгоритм:
1⃣Инициализация и определение State:
Определите класс State для хранения количества узлов в поддереве, суммы значений узлов в поддереве и максимального среднего значения поддерева.
2⃣Постобход (postorder traversal):
Реализуйте функцию maxAverage, которая выполняет постобход дерева, вычисляя nodeCount, valueSum и maxAverage для каждого узла, начиная с дочерних узлов и продвигаясь к родительским узлам.
3⃣Вычисление максимального среднего значения:
Используйте значения, полученные от дочерних узлов, для вычисления среднего значения для текущего узла и обновите maxAverage, если новое среднее значение больше текущего максимума.
😎 Решение:
package main
import "math"
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
type State struct {
nodeCount int
valueSum int
maxAverage float64
}
func maximumAverageSubtree(root *TreeNode) float64 {
return maxAverage(root).maxAverage
}
func maxAverage(node *TreeNode) State {
if node == nil {
return State{0, 0, 0}
}
left := maxAverage(node.Left)
right := maxAverage(node.Right)
nodeCount := left.nodeCount + right.nodeCount + 1
valueSum := left.valueSum + right.valueSum + node.Val
currentAverage := float64(valueSum) / float64(nodeCount)
maxAverage := math.Max(currentAverage, math.Max(left.maxAverage, right.maxAverage))
return State{nodeCount, valueSum, maxAverage}
}
Ставь 👍 и забирай 📚 Базу знаний | 118 |
| 4 | Задача: 1461. Check If a String Contains All Binary Codes of Size K
Сложность: medium
Дана бинарная строка s и целое число k, верните true, если каждый бинарный код длины k является подстрокой s. В противном случае верните false.
Пример:
Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indices 0, 1, 3 and 2 respectively.
👨💻 Алгоритм:
1⃣Определите количество возможных двоичных кодов длины k.
2⃣Создайте массив для отслеживания, какие коды были найдены. Итерируйте по строке s, вычисляя хэш для текущего окна длины k и обновляя массив отслеживания.
3⃣Возвращайте true, если все возможные коды найдены, иначе false.
😎 Решение:
func hasAllCodes(s string, k int) bool {
need := 1 << k
got := make([]bool, need)
allOne := need - 1
hashVal := 0
for i := 0; i < len(s); i++ {
hashVal = ((hashVal << 1) & allOne) | int(s[i]-'0')
if i >= k-1 && !got[hashVal] {
got[hashVal] = true
need--
if need == 0 {
return true
}
}
}
return false
}
Ставь 👍 и забирай 📚 Базу знаний | 150 |
| 5 | Задача: 1042. Flower Planting With No Adjacent
Сложность: medium
У вас есть n садов, помеченных от 1 до n, и массив paths, где paths[i] = [xi, yi] описывает двунаправленный путь между садом xi и садом yi. В каждом саду вы хотите посадить один из 4 типов цветов. Все сады имеют не более 3 путей, входящих и выходящих из него. Ваша задача - выбрать тип цветка для каждого сада так, чтобы для любых двух садов, соединенных путем, они имели разные типы цветов. Верните любой такой выбор в виде массива answer, где answer[i] - тип цветка, посаженного в (i+1)-м саду. Типы цветов обозначаются 1, 2, 3 или 4. Ответ гарантированно существует.
Пример:
Input: n = 3, paths = [[1,2],[2,3],[3,1]]
Output: [1,2,3]
👨💻 Алгоритм:
1⃣Построение графа:
Создайте граф из садов и путей между ними.
2⃣Присваивание цветов:
Для каждого сада выберите тип цветка, который не используется соседними садами.
3⃣Мы будем проходить по каждому саду и выбирать тип цветка, который не совпадает с типами цветов в соседних садах. Поскольку у каждого сада не более трех соседей, всегда будет возможность выбрать тип цветка из 4 возможных типов.
😎 Решение:
func gardenNoAdj(n int, paths [][]int) []int {
graph := make([][]int, n)
for _, path := range paths {
graph[path[0]-1] = append(graph[path[0]-1], path[1]-1)
graph[path[1]-1] = append(graph[path[1]-1], path[0]-1)
}
answer := make([]int, n)
for garden := 0; garden < n; garden++ {
used := [5]bool{}
for _, neighbor := range graph[garden] {
used[answer[neighbor]] = true
}
for flower := 1; flower <= 4; flower++ {
if !used[flower] {
answer[garden] = flower
break
}
}
}
return answer
}
Ставь 👍 и забирай 📚 Базу знаний | 144 |
| 6 | Задача: 1032. Stream of Characters
Сложность: hard
Разработайте алгоритм, который принимает поток символов и проверяет, является ли суффикс этих символов строкой заданного массива строк words. Например, если words = ["abc", "xyz"] и в поток добавлены четыре символа (один за другим) 'a', 'x', 'y' и 'z', ваш алгоритм должен определить, что суффикс "xyz" символов "axyz" соответствует "xyz" из words.
Реализуйте класс StreamChecker: StreamChecker(String[] words) Инициализирует объект с массивом строк words. boolean query(char letter) Принимает новый символ из потока и возвращает true, если любой непустой суффикс из потока образует слово, которое есть в words.
Пример:
Input
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]
Output
[null, false, false, false, true, false, true, false, false, false, false, false, true]
👨💻 Алгоритм:
1⃣Построение суффиксного Trie:
Создайте суффиксный Trie (префиксное дерево) для хранения всех слов из массива words в обратном порядке. Это позволяет эффективно искать слова, которые являются суффиксами потока символов.
2⃣Проверка суффиксов:
Для каждого нового символа, проходите по текущему списку символов и проверяйте, образуют ли они какой-либо суффикс, присутствующий в Trie. Если найдено совпадение, возвращайте true, иначе продолжайте добавлять новые символы и проверять суффиксы.
3⃣Сравнение двух случаев:
Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая.
😎 Решение:
type TrieNode struct {
children map[byte]*TrieNode
isEndOfWord bool
}
type StreamChecker struct {
root *TrieNode
stream []byte
}
func Constructor(words []string) StreamChecker {
root := &TrieNode{children: make(map[byte]*TrieNode)}
for _, word := range words {
node := root
for i := len(word) - 1; i >= 0; i-- {
if node.children[word[i]] == nil {
node.children[word[i]] = &TrieNode{children: make(map[byte]*TrieNode)}
}
node = node.children[word[i]]
}
node.isEndOfWord = true
}
return StreamChecker{root: root}
}
func (this *StreamChecker) Query(letter byte) bool {
this.stream = append([]byte{letter}, this.stream...)
node := this.root
for _, char := range this.stream {
if node.children[char] == nil {
return false
}
node = node.children[char]
if node.isEndOfWord {
return true
}
}
return false
}
Ставь 👍 и забирай 📚 Базу знаний | 139 |
| 7 | Задача: 1249. Minimum Remove to Make Valid Parentheses
Сложность: medium
Дана строка s из '(' , ')' и строчных английских символов. Ваша задача - удалить минимальное количество скобок ( '(' или ')' в любых позициях), чтобы полученная строка со скобками была допустимой, и вернуть любую допустимую строку. Формально строка со скобками допустима тогда и только тогда, когда: она пустая, содержит только строчные символы, или может быть записана как AB (A, конкатенированная с B), где A и B - допустимые строки, или может быть записана как (A), где A - допустимая строка.
Пример:
Input: s = "lee(t(c)o)de)"
Output: "lee(t(c)o)de"
👨💻 Алгоритм:
1⃣Пройдите по строке s и сохраните индексы всех открывающих скобок '(' в стек. При встрече закрывающей скобки ')', удалите соответствующую открытую скобку из стека. Если в стеке нет соответствующей открывающей скобки, пометьте эту закрывающую скобку для удаления.
2⃣После первого прохода, все оставшиеся в стеке открывающие скобки пометьте для удаления.
3⃣Создайте новую строку, удалив все помеченные скобки.
😎 Решение:
func minRemoveToMakeValid(s string) string {
stack := []int{}
res := []byte(s)
for i := 0; i < len(res); i++ {
if res[i] == '(' {
stack = append(stack, i)
} else if res[i] == ')' {
if len(stack) > 0 {
stack = stack[:len(stack)-1]
} else {
res[i] = '*'
}
}
}
for len(stack) > 0 {
res[stack[len(stack)-1]] = '*'
stack = stack[:len(stack)-1]
}
return strings.ReplaceAll(string(res), "*", "")
}
Ставь 👍 и забирай 📚 Базу знаний | 148 |
| 8 | Задача: 1180. Count Substrings with Only One Distinct Letter
Сложность: easy
Дана строка s. Верните количество подстрок, которые содержат только одну уникальную букву.
Пример:
Input: s = "aaaba"
Output: 8
Explanation: The substrings with one distinct letter are "aaa", "aa", "a", "b".
"aaa" occurs 1 time.
"aa" occurs 2 times.
"a" occurs 4 times.
"b" occurs 1 time.
So the answer is 1 + 2 + 4 + 1 = 8.
👨💻 Алгоритм:
1⃣Инициализируйте целочисленную переменную total для подсчета количества подстрок, а также два указателя left и right, которые отмечают начало и конец подстроки, содержащей только одну уникальную букву.
2⃣Итерируйте по строке S: Если мы не достигли конца и новый символ S[right] такой же, как и начальный символ S[left], увеличьте right на 1 для дальнейшего исследования строки S; в противном случае вычислите длину подстроки как right - left и примените формулу суммы арифметической последовательности; не забудьте установить right в left для начала исследования новой подстроки.
3⃣После завершения итерации добавьте к total количество подстрок для последнего сегмента, если он не был учтен. Верните значение total.
😎 Решение
func countLetters(S string) int {
total := 0
left := 0
for right := 0; right <= len(S); right++ {
if right == len(S) || S[left] != S[right] {
lenSubstring := right - left
total += (1 + lenSubstring) * lenSubstring / 2
left = right
}
}
return total
}
Ставь 👍 и забирай 📚 Базу знаний | 166 |
| 9 | Задача: 1020. Number of Enclaves
Сложность: medium
Вам дана двоичная матричная сетка m x n, где 0 обозначает морскую ячейку, а 1 - сухопутную. Ход состоит из перехода от одной сухопутной ячейки к другой соседней (в 4-х направлениях) или выхода за границу сетки. Верните количество сухопутных ячеек в сетке, для которых мы не можем выйти за границу сетки за любое количество ходов.
Пример:
Input: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3
👨💻 Алгоритм:
1⃣Обработка граничных сухопутных ячеек:
Пройдитесь по всем ячейкам, которые находятся на границе сетки (первый и последний ряды, первый и последний столбцы). Если ячейка содержит 1, начните поиск в глубину (DFS) или поиск в ширину (BFS), чтобы пометить все достижимые из нее сухопутные ячейки как посещенные.
2⃣Проверка всех ячеек:
Пройдите по всем ячейкам матрицы, считая количество сухопутных ячеек, которые не были посещены в предыдущем шаге.
3⃣Возврат результата:
Верните количество не посещенных сухопутных ячеек.
😎 Решение:
func numEnclaves(grid [][]int) int {
m, n := len(grid), len(grid[0])
var dfs func(x, y int)
dfs = func(x, y int) {
if x < 0 || y < 0 || x >= m || y >= n || grid[x][y] != 1 {
return
}
grid[x][y] = 0
dfs(x+1, y)
dfs(x-1, y)
dfs(x, y+1)
dfs(x, y-1)
}
for i := 0; i < m; i++ {
if grid[i][0] == 1 {
dfs(i, 0)
}
if grid[i][n-1] == 1 {
dfs(i, n-1)
}
}
for j := 0; j < n; j++ {
if grid[0][j] == 1 {
dfs(0, j)
}
if grid[m-1][j] == 1 {
dfs(m-1, j)
}
}
count := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] == 1 {
count++
}
}
}
return count
}
Ставь 👍 и забирай 📚 Базу знаний | 161 |
| 10 |  Задача: 171. Excel Sheet Column Number
Сложность: easy
Дана строка columnTitle, представляющая название столбца, как это отображается в Excel. Вернуть соответствующий номер столбца.
Пример:
Input: columnTitle = "A"
Output: 1
👨💻 Алгоритм:
1⃣Создайте отображение букв алфавита и их соответствующих значений (начиная с 1).
2⃣Инициализируйте переменную-аккумулятор result.
3⃣Начиная справа налево, вычислите значение символа в
зависимости от его позиции и добавьте его к result.
😎 Решение:
func titleToNumber(s string) int {
result := 0
alpha_map := make(map[rune]int)
for i := 0; i < 26; i++ {
alpha_map[rune(i + 65)] = i + 1
}
n := len(s)
for i := 0; i < n; i++ {
cur_char := rune(s[n - 1 - i])
result += alpha_map[cur_char] * pow(26, i)
}
return result
}
func pow(x int, y int) int {
result := 1
for i := 0; i < y; i++ {
result *= x
}
return result
}
Ставь 👍 и забирай 📚 Базу знаний | 161 |
| 11 | Задача: 820. Short Encoding of Words
Сложность: medium
Допустимым кодированием массива слов является любая опорная строка s и массив индексов indices, такие что:
words.length == indices.length
Опорная строка s заканчивается символом '#'.
Для каждого индекса indices[i], подстрока строки s, начинающаяся с indices[i] и заканчивающаяся (но не включительно) следующим символом '#', равна words[i].
Дан массив слов, верните длину самой короткой возможной опорной строки s для любого допустимого кодирования слов.
Пример:
Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"
👨💻 Алгоритм:
1⃣Поскольку слово имеет не более 6 собственных суффиксов (так как words[i].length <= 7), давайте итерироваться по всем из них. Для каждого собственного суффикса мы попытаемся удалить его из нашего списка слов. Для эффективности сделаем words множеством.
2⃣Затем создадим список оставшихся слов и сформируем опорную строку, объединяя каждое слово с символом '#'.
3⃣В конце вернем длину полученной опорной строки.
😎 Решение:
func minimumLengthEncoding(words []string) int {
good := make(map[string]struct{})
for _, word := range words {
good[word] = struct{}{}
}
for _, word := range words {
for k := 1; k < len(word); k++ {
delete(good, word[k:])
}
}
length := 0
for word := range good {
length += len(word) + 1
}
return length
}
Ставь 👍 и забирай 📚 Базу знаний | 175 |
| 12 | Задача: 712. Minimum ASCII Delete Sum for Two Strings
Сложность: medium
Если даны две строки s1 и s2, верните наименьшую ASCII-сумму удаленных символов, чтобы сделать две строки равными.
Пример:
Input: s1 = "sea", s2 = "eat"
Output: 231
👨💻 Алгоритм:
1⃣Создайте двумерный массив dp размером (len(s1) + 1) x (len(s2) + 1), где dp[i][j] будет хранить наименьшую ASCII-сумму удаленных символов для первых i символов s1 и первых j символов s2.
2⃣Заполните первую строку и первый столбец массива dp суммами ASCII значений символов, которые необходимо удалить для достижения пустой строки.
3⃣Заполните оставшуюся часть массива dp следующим образом: Если символы s1[i-1] и s2[j-1] равны, dp[i][j] = dp[i-1][j-1]. Иначе, dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]), dp[i][j-1] + ord(s2[j-1])).
😎 Решение:
package main
func minimumDeleteSum(s1 string, s2 string) int {
dp := make([][]int, len(s1) + 1)
for i := range dp {
dp[i] = make([]int, len(s2) + 1)
}
for i := 1; i <= len(s1); i++ {
dp[i][0] = dp[i - 1][0] + int(s1[i - 1])
}
for j := 1; j <= len(s2); j++ {
dp[0][j] = dp[0][j - 1] + int(s2[j - 1])
}
for i := 1; i <= len(s1); i++ {
for j := 1; j <= len(s2); j++ {
if s1[i - 1] == s2[j - 1] {
dp[i][j] = dp[i - 1][j - 1]
} else {
dp[i][j] = min(dp[i - 1][j] + int(s1[i - 1]), dp[i][j - 1] + int(s2[j - 1]))
}
}
}
return dp[len(s1)][len(s2)]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
Ставь 👍 и забирай 📚 Базу знаний | 189 |
| 13 |  🔥 Скрытые вакансии с удаленной работой для Golang разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров.
🔹 Golang Go Jobs | Вакансии
🔸 Все каналы с вакансиями | 223 |
| 14 | Задача: 1151. Minimum Swaps to Group All 1's Together
Сложность: medium
Дан бинарный массив data, необходимо вернуть минимальное количество перестановок, чтобы сгруппировать все 1, присутствующие в массиве, вместе в любом месте массива.
Пример:
Input: data = [1,0,1,0,1]
Output: 1
Explanation: There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.
👨💻 Алгоритм:
1⃣Используем два указателя, left и right, чтобы поддерживать скользящее окно длиной ones и проверяем каждый фрагмент массива data, подсчитывая количество единиц в нем (cnt_one) и запоминая максимальное значение max_one.
2⃣Пока окно скользит по массиву data, поддерживаем его длину равной ones.
3⃣Обновляем количество единиц в окне, добавляя новую границу data[right] и вычитая левую границу data[left].
😎 Решение
func minSwaps(data []int) int {
ones := 0
for _, num := range data {
ones += num
}
cnt_one, max_one := 0, 0
left, right := 0, 0
for right < len(data) {
cnt_one += data[right]
right++
if right - left > ones {
cnt_one -= data[left]
left++
}
if cnt_one > max_one {
max_one = cnt_one
}
}
return ones - max_one
}
Ставь 👍 и забирай 📚 Базу знаний | 239 |
| 15 | Задача: №17. Letter Combinations of a Phone Number
Сложность: medium
Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число.
Верните ответ в любом порядке. Соответствие цифр буквам (как на кнопках телефона) приведено ниже.
Обратите внимание, что 1 не соответствует никаким буквам.
Пример:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
👨💻 Алгоритм:
1⃣Создать хэш-таблицу, сопоставляющую цифры 2-9 с соответствующими буквами.
2⃣Использовать рекурсивный backtracking, чтобы формировать комбинации, перебирая буквы для каждой цифры.
3⃣Добавлять полные комбинации в список результатов.
😎 Решение:
func letterCombinations(digits string) []string {
if len(digits) == 0 {
return []string{}
}
phoneMap := map[byte]string{
'2': "abc", '3': "def", '4': "ghi", '5': "jkl",
'6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz",
}
res := []string{}
var backtrack func(int, string)
backtrack = func(index int, path string) {
if index == len(digits) {
res = append(res, path)
return
}
letters := phoneMap[digits[index]]
for i := 0; i < len(letters); i++ {
backtrack(index+1, path+string(letters[i]))
}
}
backtrack(0, "")
return res
}
Ставь 👍 и забирай 📚 Базу знаний | 215 |
| 16 | Задача: 659. Split Array into Consecutive Subsequences
Сложность: medium
Вам дан отсортированный в неубывающем порядке массив целых чисел nums.
Определите, можно ли разделить nums на одну или несколько подпоследовательностей так, чтобы выполнялись оба следующих условия:
Каждая подпоследовательность является последовательностью последовательных возрастающих чисел (то есть каждое целое число на 1 больше предыдущего).
Все подпоследовательности имеют длину 3 или более.
Верните true, если можно разделить nums согласно вышеуказанным условиям, или false в противном случае.
Подпоследовательность массива — это новый массив, который формируется из исходного массива путем удаления некоторых (может быть, ни одного) элементов без нарушения относительных позиций оставшихся элементов. (например, [1,3,5] является подпоследовательностью [1,2,3,4,5], тогда как [1,3,2] не является).
Пример:
Input: nums = [1,2,3,3,4,5]
Output: true
👨💻 Алгоритм:
1⃣Подсчет частоты элементов:
Создайте хеш-таблицу для подсчета количества вхождений каждого элемента в массиве nums.
2⃣Создание подпоследовательностей:
Создайте хеш-таблицу для отслеживания количества подпоследовательностей, которые могут быть продолжены для каждого элемента.
Пройдите по каждому элементу в массиве и выполните следующие действия:
Если элемент можно добавить к существующей подпоследовательности (проверяя хеш-таблицу подпоследовательностей), добавьте его и обновите хеш-таблицу.
Если элемент нельзя добавить к существующей подпоследовательности, начните новую последовательность длиной 3 или более элементов.
Если ни одно из условий не выполнено, верните false.
3⃣Проверка результата:
Верните true, если все элементы успешно распределены по подпоследовательностям.
😎 Решение:
func isPossible(nums []int) bool {
freq := make(map[int]int)
need := make(map[int]int)
for _, num := range nums {
freq[num]++
}
for _, num := range nums {
if freq[num] == 0 {
continue
}
if need[num] > 0 {
need[num]--
need[num+1]++
} else if freq[num+1] > 0 && freq[num+2] > 0 {
freq[num+1]--
freq[num+2]--
need[num+3]++
} else {
return false
}
freq[num]--
}
return true
}
Ставь 👍 и забирай 📚 Базу знаний | 232 |
| 17 | Задача: 1189. Maximum Number of Balloons
Сложность: easy
Дана строка text. Вы хотите использовать символы строки text, чтобы сформировать как можно больше экземпляров слова "balloon".
Каждый символ строки text можно использовать не более одного раза. Верните максимальное количество экземпляров, которые можно сформировать.
Пример:
Input: text = "nlaebolko"
Output: 1
👨💻 Алгоритм:
1⃣Подсчитайте количество появлений каждого символа 'b', 'a', 'l', 'o', 'n' в строке text.
2⃣Вычислите потенциал для каждого символа: для 'b' и 'a' потенциал равен количеству их появлений, для 'l' и 'o' потенциал равен количеству их появлений, деленному на 2, а для 'n' потенциал равен количеству его появлений.
3⃣Найдите символ с наименьшим потенциалом среди 'b', 'a', 'l', 'o', 'n', который ограничивает количество возможных слов "balloon", и верните это значение.
😎 Решение
func maxNumberOfBalloons(text string) int {
bCount, aCount, lCount, oCount, nCount := 0, 0, 0, 0, 0
for _, c := range text {
switch c {
case 'b':
bCount++
case 'a':
aCount++
case 'l':
lCount++
case 'o':
oCount++
case 'n':
nCount++
}
}
lCount /= 2
oCount /= 2
return min(bCount, aCount, lCount, oCount, nCount)
}
func min(a, b, c, d, e int) int {
return min2(min2(a, b), min2(min2(c, d), e))
}
func min2(x, y int) int {
if x < y {
return x
}
return y
}
Ставь 👍 и забирай 📚 Базу знаний | 329 |
| 18 | Задача: 389. Find the Difference
Сложность: easy
Даны две строки s и t.
Строка t генерируется путем случайного перемешивания строки s с добавлением еще одной буквы в случайную позицию.
Верните букву, которая была добавлена в t.
Пример:
Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.
👨💻 Алгоритм:
1⃣Отсортируйте строки s и t.
2⃣Итерируйте по длине строк и сравнивайте их посимвольно. Это позволяет проверить, присутствует ли текущий символ строки t в строке s.
3⃣Как только встретится символ, который есть в строке t, но отсутствует в строке s, мы найдем лишний символ, который скрывала строка t все это время.
😎 Решение:
package main
import (
"sort"
"strings"
)
func findTheDifference(s string, t string) byte {
sortedS := strings.Split(s, "")
sortedT := strings.Split(t, "")
sort.Strings(sortedS)
sort.Strings(sortedT)
for i := 0; i < len(sortedS); i++ {
if sortedS[i] != sortedT[i] {
return sortedT[i][0]
}
}
return sortedT[len(sortedS)][0]
}
Ставь 👍 и забирай 📚 Базу знаний | 286 |
| 19 | Задача: 336. Palindrome Pairs
Сложность: hard
Вам дан массив уникальных строк words, индексируемый с 0.
Пара палиндромов — это пара целых чисел (i, j), таких что:
0 <= i, j < words.length,
i != j, и
words[i] + words[j] (конкатенация двух строк) является палиндромом.
Верните массив всех пар палиндромов из слов.
Вы должны написать алгоритм с временной сложностью O(сумма длин всех слов в words).
Пример:
Input: words = ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["abcddcba","dcbaabcd","slls","llssssll"]
👨💻 Алгоритм:
1⃣Инициализация и подготовка данных:
Создайте структуру для хранения результатов (список пар индексов).
Создайте словарь для хранения слов и их индексов, чтобы ускорить поиск.
2⃣Итерация по всем парам слов и проверка:
Пройдите по всем парам слов в массиве words, используя два вложенных цикла.
Для каждой пары слов проверяйте, образуют ли они палиндром при конкатенации. Это делается путем объединения строк и проверки, равна ли объединенная строка своей обратной версии.
3⃣Добавление найденных пар в результат:
Если проверка на палиндром проходит, добавьте текущую пару индексов в список результатов.
Верните итоговый список всех найденных пар.
😎 Решение:
func palindromePairs(words []string) [][]int {
var pairs [][]int
for i := 0; i < len(words); i++ {
for j := 0; j < len(words); j++ {
if i == j {
continue
}
combined := words[i] + words[j]
if combined == reverseString(combined) {
pairs = append(pairs, []int{i, j})
}
}
}
return pairs
}
func reverseString(s string) string {
runes := []rune(s)
for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
runes[i], runes[j] = runes[j], runes[i]
}
return string(runes)
}
Ставь 👍 и забирай 📚 Базу знаний | 311 |
| 20 | 🔥 Скрытые вакансии с удаленной работой для Golang разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров.
🔹 Golang Go Jobs | Вакансии
🔸 Все каналы с вакансиями | 347 |
