Golang | LeetCode
الذهاب إلى القناة على Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
إظهار المزيد
الشبكة:3 582
المشتركون
+124 ساعات
-117 أيام
-3030 أيام
أرشيف المشاركات
3 582
🎓 Тестовый собес с Go Senior из Гамбурга, с опытом работы в Yandex и Uzum
[ + эталонные ответы на 50 сложных вопросов в подарок ]
В четверг, 8 октября, в 19:00 МСК приходи онлайн на тестовое собеседование. Можно посмотреть, как всё устроено изнутри, и понять, насколько ты готов к такому интервью.
Интервьюер: Маруф Караев — Senior Software Engineer из Гамбурга, ex-Yandex, ex-Uzum.
Как это будет:
📂 Маруф задаст разработчику-добровольцу те вопросы и задачи, которые даёт кандидатам на своих интервью. Заранее их никто не знает;
📂 После каждого ответа Маруф даст обратную связь: что прозвучало сильно, а что стоило раскрыть иначе. Так станет понятнее, на что обращают внимание на собесе;
📂 В конце сможешь задать Маруфу любой вопрос и получить развёрнутый ответ;
Эфир проходит в рамках менторской программы ШОРТКАТ для Go-разработчиков, которые хотят сменить работу и вырасти в грейде и зарплате.
🎁 Подарок для всех, кто зарегается на веб:
файл с эталонными ответами на 50 сложных вопросов с Go-интервью 🔥
Жми на кнопку, чтобы попасть на эфир и забрать подарок ↓
@shortcut_go_bot
Реклама.
О рекламодателе.
3 582
Задача: 897. Increasing Order Search Tree
Сложность: easy
Задав корень дерева двоичного поиска, перестройте дерево по порядку так, чтобы самый левый узел дерева теперь был корнем дерева, а каждый узел не имел левого и только одного правого дочернего узла.
Пример:
Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9] Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]👨💻 Алгоритм: 1⃣Выполнить обход дерева в порядке in-order, чтобы получить список узлов. 2⃣Перестроить дерево, устанавливая каждый узел из списка как правый дочерний элемент предыдущего узла и устанавливая левые дочерние элементы в null. 3⃣Вернуть новый корень дерева (первый элемент списка). 😎 Решение:
package main
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func increasingBST(root *TreeNode) *TreeNode {
nodes := []*TreeNode{}
var inorder func(node *TreeNode)
inorder = func(node *TreeNode) {
if node == nil {
return
}
inorder(node.Left)
nodes = append(nodes, node)
inorder(node.Right)
}
inorder(root)
for i := 0; i < len(nodes)-1; i++ {
nodes[i].Left = nil
nodes[i].Right = nodes[i+1]
}
nodes[len(nodes)-1].Left = nil
nodes[len(nodes)-1].Right = nil
return nodes[0]
}3 582
Задача: 200. Number of Islands
Сложность: medium
Дана двумерная бинарная сетка размером
m x n, представляющая карту из '1' (земля) и '0' (вода). Верните количество островов.
Остров окружён водой и образуется путём соединения соседних земель горизонтально или вертикально. Можно предположить, что все четыре края сетки окружены водой.
Пример:
Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1👨💻 Алгоритм: 1⃣Обход всей сетки: - Если найден
'1', запускаем поиск в глубину (DFS).
2⃣DFS для пометки острова:
- Заменяем '1' на '0', чтобы избежать повторного посещения.
- Рекурсивно вызываем DFS для всех четырёх направлений.
3⃣Подсчет островов:
- Каждый запуск DFS означает новый остров.
- Увеличиваем счетчик островов.
😎 Решение:
package main
func numIslands(grid [][]byte) int {
if len(grid) == 0 {
return 0
}
numIslands := 0
for i := 0; i < len(grid); i++ {
for j := 0; j < len(grid[0]); j++ {
if grid[i][j] == '1' {
dfs(grid, i, j)
numIslands++
}
}
}
return numIslands
}
func dfs(grid [][]byte, r, c int) {
if r < 0 || c < 0 || r >= len(grid) || c >= len(grid[0]) || grid[r][c] != '1' {
return
}
grid[r][c] = '0'
dfs(grid, r-1, c)
dfs(grid, r+1, c)
dfs(grid, r, c-1)
dfs(grid, r, c+1)
}3 582
Задача: 313. Super Ugly Number
Сложность: medium
Супер некрасивое число — это положительное целое число, простые множители которого находятся в массиве primes.
Дано целое число n и массив целых чисел primes. Верните n-е супер некрасивое число.
Гарантируется, что n-е супер некрасивое число помещается в 32-битное знаковое целое число.
Пример:
Input: n = 12, primes = [2,7,13,19] Output: 32 Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19].👨💻 Алгоритм: 1⃣Инициализация Создайте массив ugly_numbers длиной n для хранения супер некрасивых чисел. Создайте массив indices длиной primes для отслеживания позиций в массиве ugly_numbers. Создайте массив next_ugly длиной primes для хранения следующего возможного супер некрасивого числа для каждого простого числа из primes. 2⃣Генерация супер некрасивых чисел Установите первое значение в ugly_numbers как 1. Повторяйте до тех пор, пока не заполните массив ugly_numbers: Найдите минимальное значение в массиве next_ugly и добавьте его в ugly_numbers. Обновите соответствующий индекс в indices и пересчитайте значение в next_ugly. 3⃣Возврат результата Верните последнее значение в массиве ugly_numbers, которое будет n-м супер некрасивым числом. 😎 Решение:
func nthSuperUglyNumber(n int, primes []int) int {
ugly_numbers := make([]int, n)
ugly_numbers[0] = 1
indices := make([]int, len(primes))
next_ugly := append([]int(nil), primes...)
for i := 1; i < n; i++ {
next_val := min(next_ugly)
ugly_numbers[i] = next_val
for j := 0; j < len(primes); j++ {
if next_val == next_ugly[j] {
indices[j]++
next_ugly[j] = ugly_numbers[indices[j]] * primes[j]
}
}
}
return ugly_numbers[n-1]
}
func min(arr []int) int {
minVal := arr[0]
for _, val := range arr {
if val < minVal {
minVal = val
}
}
return minVal
}3 582
Задача: 1166. Design File System
Сложность: medium
Вам нужно разработать файловую систему, которая позволяет создавать новые пути и связывать их с различными значениями.
Формат пути - это одна или несколько конкатенированных строк в форме: /, за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" - допустимые пути, в то время как пустая строка "" и "/" не допустимы.
Реализуйте класс FileSystem:
-
bool createPath(string path, int value) создает новый путь и связывает с ним значение, если это возможно, и возвращает true. Возвращает false, если путь уже существует или его родительский путь не существует.
- int get(string path) возвращает значение, связанное с путем, или возвращает -1, если путь не существует.
Пример:
Input:
["FileSystem","createPath","get"]
[[],["/a",1],["/a"]]
Output:
[null,true,1]
Explanation:
FileSystem fileSystem = new FileSystem();
fileSystem.createPath("/a", 1); // return true
fileSystem.get("/a"); // return 1type FileSystem struct {
paths map[string]int
}
func Constructor() FileSystem {
return FileSystem{paths: make(map[string]int)}
}
func (this *FileSystem) CreatePath(path string, value int) bool {
if path == "" || (len(path) == 1 && path == "/") || this.paths[path] != 0 {
return false
}
delimIndex := strings.LastIndex(path, "/")
parent := path[:delimIndex]
if len(parent) > 1 && this.paths[parent] == 0 {
return false
}
this.paths[path] = value
return true
}
func (this *FileSystem) Get(path string) int {
if val, ok := this.paths[path]; ok {
return val
}
return -1
}3 582
Задача: 947. Most Stones Removed with Same Row or Column
Сложность: medium
Учитывая массив stones длины n, где stones[i] = [xi, yi] представляет местоположение i-го камня, верните наибольшее возможное количество камней, которые могут быть удалены.
Пример:
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]] Output: 5👨💻 Алгоритм: 1⃣Представить каждую строку и столбец как узлы в графе. 2⃣Создать связи между узлами для камней, которые находятся в той же строке или столбце. Использовать алгоритм поиска в глубину (DFS) или объединение-поиска (Union-Find), чтобы найти компоненты связности. 3⃣Количество камней, которые могут быть удалены, это общее количество камней минус количество компонентов связности. 😎 Решение:
package main
func removeStones(stones [][]int) int {
parent := make(map[int]int)
var find func(int) int
find = func(x int) int {
if parent[x] == 0 {
parent[x] = x
}
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
union := func(x, y int) {
parent[find(x)] = find(y)
}
for _, stone := range stones {
union(stone[0], ^stone[1])
}
uniqueRoots := make(map[int]bool)
for k := range parent {
uniqueRoots[find(k)] = true
}
return len(stones) - len(uniqueRoots)
}3 582
Задача: 1064. Fixed Point
Сложность: medium
Дан массив различных целых чисел arr, отсортированный в порядке возрастания. Верните наименьший индекс i, который удовлетворяет условию arr[i] == i. Если такого индекса нет, верните -1.
Пример:
Input: arr = [-10,-5,0,3,7]
Output: 3
Explanation: For the given array, arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3, thus the output is 3.func fixedPoint(arr []int) int {
left, right := 0, len(arr) - 1
answer := -1
for left <= right {
mid := (left + right) / 2
if arr[mid] == mid {
answer = mid
right = mid - 1
} else if arr[mid] < mid {
left = mid + 1
} else {
right = mid - 1
}
}
return answer
}3 582
Задача: 1413. Minimum Value to Get Positive Step by Step Sum
Сложность: easy
Дан массив целых чисел nums, вы начинаете с начального положительного значения startValue.
На каждой итерации вы вычисляете поэтапную сумму startValue плюс элементы из nums (слева направо).
Верните минимальное положительное значение startValue, такое что поэтапная сумма никогда не будет меньше 1.
Пример:
Input: nums = [-3,2,-3,4,2] Output: 5 Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1. step by step sum startValue = 4 | startValue = 5 | nums (4 -3 ) = 1 | (5 -3 ) = 2 | -3 (1 +2 ) = 3 | (2 +2 ) = 4 | 2 (3 -3 ) = 0 | (4 -3 ) = 1 | -3 (0 +4 ) = 4 | (1 +4 ) = 5 | 4 (4 +2 ) = 6 | (5 +2 ) = 7 | 2👨💻 Алгоритм: 1⃣Инициализируйте переменные startValue со значением 1 и total со значением startValue. 2⃣Итеративно добавляйте каждый элемент массива nums к total и проверяйте, не опускается ли total ниже 1. 3⃣Если total падает ниже 1, увеличьте startValue на 1 и повторите шаги 2-3. Если total остается не менее 1, верните текущее значение startValue. 😎 Решение:
func minStartValue(nums []int) int {
startValue := 1
for {
total := startValue
isValid := true
for _, num := range nums {
total += num
if total < 1 {
isValid = false
break
}
}
if isValid {
return startValue
}
startValue++
}
}3 582
🔴AI кодинг интервью с разработчиком из международного FinTech в четверг в 19:00
ДА! Вайбкодинг реально начали проверять на интервью, поэтому мы нашли собеседующего, который проводит AI-секцию в международном финтехе, чтобы вы увидели что на ней спрашивают и как к ней подготовиться
Как это будет:
📂 Александр Дмитриев, разработчик из известного международного финтеха, ex-VK, ex-Ozon проведет вайбкодинг секцию разработчику-добровольцу
📂 Александр будет задавать реальные вопросы с секций, которые проводил сам и комментировать ответы
📂 В конце можно будет задать любой вопрос Александру
Это бесплатно. Эфир проходит в рамках менторской программы от ШОРТКАТ для разработчиков, которые хотят сменить работу, повысить свой грейд, ЗП и прокачать скиллы.
Переходи в нашего бота, чтобы получить ссылку на эфир → @shortcut_go_bot
Реклама.
О рекламодателе.
3 582
Задача: 231. Power of Two
Сложность: easy
Дано целое число n, верните true, если оно является степенью двойки. В противном случае верните false.
Целое число n является степенью двойки, если существует целое число x, такое что n == 2^x.
Пример:
Input: n = 1 Output: true Explanation: 2^0 = 1👨💻 Алгоритм: 1⃣Проверка на ноль: Если n равно нулю, верните false, так как ноль не является степенью двойки. 2⃣Преобразование к длинному типу: Преобразуйте n к типу long, чтобы избежать переполнения при выполнении побитовых операций. 3⃣Побитовая проверка: Используйте побитовую операцию, чтобы проверить, является ли число степенью двойки. Число является степенью двойки, если результат выражения (x & (-x)) равен x. 😎 Решение:
func isPowerOfTwo(n int) bool {
if n == 0 {
return false
}
x := int64(n)
return (x & -x) == x
}3 582
Задача: 441. Arranging Coins
Сложность: easy
У вас есть n монет, и вы хотите построить лестницу из этих монет. Лестница состоит из k рядов, где i-й ряд содержит ровно i монет. Последний ряд лестницы может быть неполным.
Дано целое число n, верните количество полных рядов лестницы, которые вы сможете построить.
Пример:
Input: n = 5 Output: 2 Explanation: Because the 3rd row is incomplete, we return 2.👨💻 Алгоритм: 1⃣Если мы глубже посмотрим на формулу задачи, мы можем решить её с помощью математики, без использования итераций. 2⃣Напомним, что условие задачи можно выразить следующим образом: k(k + 1) ≤ 2N. 3⃣Это можно решить методом выделения полного квадрата, (k + 1/2)² - 1/4 ≤ 2N. Что приводит к следующему ответу: k = [sqrt(2N + 1/4) - 1/2]. 😎 Решение:
import "math"
func arrangeCoins(n int) int {
return int(math.Sqrt(float64(2 * n) + 0.25) - 0.5)
}3 582
Задача: 647. Palindromic Substrings
Сложность: medium
Реализуйте структуру данных
MapSum, поддерживающую:
- Insert(key string, val int) — вставляет или обновляет значение по ключу.
- Sum(prefix string) — возвращает сумму значений всех ключей, начинающихся с указанного префикса.
Пример:
mapSum := Constructor()
mapSum.Insert("apple", 3)
mapSum.Sum("ap") // 3
mapSum.Insert("app", 2)
mapSum.Sum("ap") // 5 (3 + 2)map[string]int для хранения всех ключей и их значений.
2⃣Операция Insert
Если ключ уже существует — просто перезаписываем новое значение.
3⃣Операция Sum
Проходим по всем ключам. Если ключ начинается с prefix, прибавляем его значение к результату.
😎 Решение:
package main
import "strings"
type MapSum struct {
mapData map[string]int
}
func Constructor() MapSum {
return MapSum{mapData: make(map[string]int)}
}
func (this *MapSum) Insert(key string, val int) {
this.mapData[key] = val
}
func (this *MapSum) Sum(prefix string) int {
ans := 0
for key, val := range this.mapData {
if strings.HasPrefix(key, prefix) {
ans += val
}
}
return ans
}3 582
Задача: 315. Count of Smaller Numbers After Self
Сложность: hard
Дан целочисленный массив nums, верните целочисленный массив counts, где counts[i] - это количество элементов справа от nums[i], которые меньше nums[i].
Пример:
Input: nums = [5,2,6,1] Output: [2,1,1,0] Explanation: To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.👨💻 Алгоритм: 1⃣Реализуйте дерево отрезков (segment tree). Поскольку дерево инициализируется нулями, нужно реализовать только операции обновления и запроса. Установите смещение offset = 10^4. 2⃣Итерация по каждому числу в nums в обратном порядке. Для каждого числа выполните следующие действия: Смещайте число на num + offset. Запросите количество элементов в дереве отрезков, которые меньше текущего числа. Обновите счетчик текущего числа в дереве отрезков. 3⃣Верните результат. 😎 Решение:
package main
import (
"fmt"
"sort"
)
func countSmaller(nums []int) []int {
offset := 10000
size := 2 * 10000 + 1
tree := make([]int, size * 2)
result := make([]int, len(nums))
for i := len(nums) - 1; i >= 0; i-- {
smallerCount := query(0, nums[i] + offset, tree, size)
result[i] = smallerCount
update(nums[i] + offset, 1, tree, size)
}
return result
}
func update(index, value int, tree []int, size int) {
index += size
tree[index] += value
for index > 1 {
index /= 2
tree[index] = tree[index * 2] + tree[index * 2 + 1]
}
}
func query(left, right int, tree []int, size int) int {
result := 0
left += size
right += size
for left < right {
if left % 2 == 1 {
result += tree[left]
left++
}
left /= 2
if right % 2 == 1 {
right--
result += tree[right]
}
right /= 2
}
return result
}
func main() {
nums := []int{5, 2, 6, 1}
fmt.Println(countSmaller(nums))
}3 582
Задача: 283. Move Zeroes
Сложность: easy
Дан целочисленный массив nums. Переместите все нули в конец массива, сохраняя относительный порядок ненулевых элементов.
Обратите внимание, что вы должны сделать это на месте, не создавая копию массива.
Пример:
Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0]👨💻 Алгоритм: 1⃣Инициализация указателей: Инициализируйте два указателя: lastNonZeroFoundAt для отслеживания позиции последнего ненулевого элемента и cur для итерации по массиву. 2⃣Итерация и обмен элементами: Итерируйтесь по массиву с помощью указателя cur. Если текущий элемент ненулевой, поменяйте его местами с элементом, на который указывает lastNonZeroFoundAt, и продвиньте указатель lastNonZeroFoundAt. 3⃣Завершение итерации: Повторяйте шаг 2 до конца массива. В итоге все нули будут перемещены в конец массива, сохраняя относительный порядок ненулевых элементов. 😎 Решение:
func moveZeroes(nums []int) {
lastNonZeroFoundAt := 0
for cur := 0; cur < len(nums); cur++ {
if nums[cur] != 0 {
nums[lastNonZeroFoundAt], nums[cur] = nums[cur], nums[lastNonZeroFoundAt]
lastNonZeroFoundAt++
}
}
}3 582
Задача: №28. Find the Index of the First Occurrence in a String
Сложность: easy
Учитывая две строки,
needle и haystack, верните индекс первого вхождения needle в haystack, или -1, если needle не является частью haystack.
Пример:
Input: haystack = "sadbutsad", needle = "sad" Output: 0👨💻 Алгоритм: 1⃣Обработка граничного случая: - Если
needle — пустая строка, вернуть 0 (по определению).
2⃣Итерация по возможным позициям:
- Проходим по всем индексам i от 0 до len(haystack) - len(needle),
- На каждой итерации сравниваем срез haystack[i:i+len(needle)] с needle.
3⃣Проверка совпадений:
- Если подстроки совпали — возвращаем текущий индекс i.
- Если не нашли ни одного совпадения — возвращаем -1.
😎 Решение:
func strStr(haystack string, needle string) int {
n := len(needle)
if n == 0 {
return 0
}
for i := 0; i <= len(haystack)-n; i++ {
if haystack[i:i+n] == needle {
return i
}
}
return -1
}3 582
Задача: 943. Find the Shortest Superstring
Сложность: hard
Учитывая массив строк words, верните наименьшую строку, которая содержит каждую строку в words в качестве подстроки. Если существует несколько допустимых строк наименьшей длины, верните любую из них. Вы можете предположить, что ни одна строка в words не является подстрокой другой строки в words.
Пример:
Input: words = ["alex","loves","leetcode"] Output: "alexlovesleetcode"👨💻 Алгоритм: 1⃣Реализовать функцию overlap для вычисления максимального перекрытия двух строк, где одна строка заканчивается, а другая начинается. 2⃣Реализовать функцию merge для объединения двух строк с максимальным перекрытием. Использовать жадный алгоритм для нахождения двух строк с максимальным перекрытием и объединить их, повторяя до тех пор, пока не останется одна строка. 3⃣Вернуть результат. 😎 Решение:
package main
func shortestSuperstring(words []string) string {
for len(words) > 1 {
maxOverlap := -1
l, r := 0, 0
merged := ""
for i := 0; i < len(words); i++ {
for j := 0; j < len(words); j++ {
if i != j {
ovlp := overlap(words[i], words[j])
if ovlp > maxOverlap {
maxOverlap = ovlp
l = i
r = j
merged = merge(words[i], words[j], ovlp)
}
}
}
}
words[l] = merged
words = append(words[:r], words[r+1:]...)
}
return words[0]
}
func overlap(a, b string) int {
maxOverlap := 0
for i := 1; i <= min(len(a), len(b)); i++ {
if a[len(a)-i:] == b[:i] {
maxOverlap = i
}
}
return maxOverlap
}
func merge(a, b string, overlapLen int) string {
return a + b[overlapLen:]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}3 582
Задача: 164. Maximum Gap
Сложность: medium
Дан массив целых чисел nums. Верните максимальную разницу между двумя последовательными элементами в его отсортированной форме. Если массив содержит менее двух элементов, верните 0.
Необходимо написать алгоритм, который работает за линейное время и использует линейное дополнительное пространство.
Пример:
Input: nums = [3,6,9,1] Output: 3 Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.👨💻 Алгоритм: 1⃣Инициализация: Определите минимальное и максимальное значения в массиве для расчета возможного максимального интервала (разрыва) между элементами в идеально распределенном массиве. Вычислите размер ведра (bucket size), необходимый для размещения всех элементов массива так, чтобы если массив был равномерно распределен, каждый ведер должен содержать хотя бы один элемент. Размер ведра = (max_value - min_value) / (количество элементов - 1). 2⃣Размещение элементов в ведрах: Создайте ведра для хранения минимальных и максимальных значений каждого ведра. Используйте формулу для распределения каждого элемента в соответствующем ведре на основе его значения. Игнорируйте пустые ведра при расчете максимального интервала. 3⃣Вычисление максимального интервала: Пройдите через ведра и вычислите максимальный интервал, сравнивая минимальное значение текущего непустого ведра с максимальным значением предыдущего непустого ведра. Максимальный интервал будет наибольшей разницей между "минимальными" и "максимальными" значениями последовательных непустых ведер. 😎 Решение:
func maximumGap(nums []int) int {
if len(nums) < 2 {
return 0
}
sort.Ints(nums)
maxGap := 0
for i := 0; i < len(nums)-1; i++ {
diff := nums[i+1] - nums[i]
if diff > maxGap {
maxGap = diff
}
}
return maxGap
}3 582
Разница между Go-разработчиком с зарплатой в 100–200 тысяч и 500 тысяч не в количестве написанных строк кода
Первый решает, как написать сервис. Второй нужен ли он вообще, что сломается на десятикратной нагрузке и как правильно построить ожидания. Разницу платят за ответственность, а не за код.
Литкод или курсы с этим не помогут. А карьерный рост должен идти по твоему плану, а не зависеть от удачи.
Поэтому мы в ШОРТКАТ сделали для тебя карьерную консультацию 1-на-1 с лидом из бигтеха. Часовой звонок, где лид погрузится в твой контекст, разберет резюме и построит персональный план:
👉 Как повысить грейд и зарплату в ближайшее время
👉 Что делать вдолгую, чтобы остаться востребованным на рынке труда
👉 На чем сфокусироваться, а на что лучше не тратить время
Задач и оценок не будет — это не собеседование.
Консультация стоит 1990 рублей. В неделю проводим не больше 10, чтобы хватало внимания на каждого
Оставить заявку: @shortcut_go_bot
Реклама.
О рекламодателе.
3 582
Задача: 999. Available Captures for Rook
Сложность: easy
Вам дана матрица 8 x 8, изображающая шахматную доску. На ней есть ровно одна белая ладья, представленная символом "R", некоторое количество белых слонов "B" и некоторое количество черных пешек "p". Пустые клетки обозначаются символом '.'. Ладья может перемещаться на любое количество клеток по горизонтали или вертикали (вверх, вниз, влево, вправо), пока не достигнет другой фигуры или края доски. Ладья атакует пешку, если она может переместиться на ее клетку за один ход. Примечание: Ладья не может перемещаться через другие фигуры, такие как слоны или пешки. Это означает, что ладья не может атаковать пешку, если путь ей преграждает другая фигура. Верните количество пешек, которые атакует белая ладья.
Пример:
Input: board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]] Output: 3👨💻 Алгоритм: 1⃣Поиск ладьи: Найдите координаты белой ладьи "R" на шахматной доске. 2⃣Проверка направлений атаки: Проверьте все четыре направления (влево, вправо, вверх, вниз) от позиции ладьи. Перемещайтесь по каждому направлению до тех пор, пока не встретите другую фигуру или край доски. 3⃣Подсчет атакованных пешек: Если встреченная фигура - черная пешка "p", увеличьте счетчик атакованных пешек. Если встреченная фигура - белый слон "B" или край доски, остановитесь в этом направлении. 😎 Решение:
func numRookCaptures(board [][]byte) int {
countPawns := func(x, y, dx, dy int) int {
for x >= 0 && x < 8 && y >= 0 && y < 8 {
if board[x][y] == 'B' {
break
}
if board[x][y] == 'p' {
return 1
}
x += dx
y += dy
}
return 0
}
for i := 0; i < 8; i++ {
for j := 0; j < 8; j++ {
if board[i][j] == 'R' {
return countPawns(i, j, -1, 0) + countPawns(i, j, 1, 0) +
countPawns(i, j, 0, -1) + countPawns(i, j, 0, 1)
}
}
}
return 0
}3 582
Задача: 1230. Toss Strange Coins
Сложность: medium
У вас есть несколько монет. Вероятность выпадения орла для i-й монеты равна prob[i].
Верните вероятность того, что количество монет, на которых выпал орел, равно target, если вы подбросите каждую монету ровно один раз.
Пример:
Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0 Output: 0.03125👨💻 Алгоритм: 1⃣Инициализация: Создайте переменную n и инициализируйте её размером массива prob. Создайте 2D массив dp размером n + 1 строк и target + 1 столбцов, где dp[i][j] хранит вероятность получить j орлов, используя первые i монет. Установите базовый случай dp[0][0] = 1. 2⃣Итерация: Используйте два вложенных цикла для заполнения массива dp. Внешний цикл итерируется от i = 1 до n. Для каждого i установите dp[i][0], что обозначает вероятность получить 0 орлов при использовании i монет: dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1]). Внутренний цикл итерируется от j = 1 до target. Для каждого j вычислите dp[i][j] по формуле: dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1]). 3⃣Возврат результата: Верните значение dp[n][target], которое содержит искомую вероятность. 😎 Решение:
func probabilityOfHeads(prob []float64, target int) float64 {
n := len(prob)
dp := make([][]float64, n+1)
for i := range dp {
dp[i] = make([]float64, target+1)
}
dp[0][0] = 1.0
for i := 1; i <= n; i++ {
dp[i][0] = dp[i-1][0] * (1 - prob[i-1])
for j := 1; j <= target; j++ {
if j <= i {
dp[i][j] = dp[i-1][j-1] * prob[i-1] + dp[i-1][j] * (1 - prob[i-1])
}
}
}
return dp[n][target]
}