LeetCode: варианты решения задач

dev28.05.2020

Решаю задачи с LeetCode. В первую очередь по алгоритмам и структурам данных. Для начала планирую решить порядка 150 простых задач, после чего перейду к средним и сложным.

Публикуемые решения не всегда будут самыми быстрыми и оптимальными, а скорее "жизненными", т.е. подобные тем, какие я обычно использую в работе. Разумеется это не отменяет того, что код должен быть лаконичным и понятным и проходить все тесты за адекватное время 🙂

Решения на Python3

Выбрал Python3 за его математичность 🤓

Код решений публикую через GitHub Gist. В дальнейшем, возможно, изменю формат для большего удобства. Статья будет дополняться и обновляться.

https://gist.github.com/RiseLab/dc4a1557d9be4e44688452788456f606

Решения на Golang

Начал изучать Golang, поэтому новые решения будут на этом языке 😼

6. Zigzag Conversion medium

https://leetcode.com/problems/zigzag-conversion/

Разбить строку на заданное количество подстрок по шаблону "зигзаг". Результатом должна быть строка, состоящая из получившихся подстрок.

Например, для строки "PAYPALISHIRING" при разбиении на 3 подстроки результатом будет строка "PAHNAPLSIIGYIR":

P   A   H   N
A P L S I I G
Y   I   R

Решение

func convert(s string, numRows int) string {
	if numRows == 0 { return "" }
	if numRows == 1 { return s }
	res := make([]string, numRows)
	c, m := 0, 1
	for i := 0; i < len(s); i++ {
		res[c] += string(s[i])
		c += m
		if c == 0 || c == numRows-1 {
			m *= -1
		}
	}
	return strings.Join(res, "")
}

21. Merge Two Sorted Lists easy

https://leetcode.com/problems/merge-two-sorted-lists/

Нужно объединить 2 отсортированных списка в отсортированный список.

Линейное решение

Решение сводится к присоединению к результирующему списку той "головы" одного из двух исходных списков, которая содержит меньшее значение. После этого "головой" выбранного списка становится его следующий элемент. Как только значения в одном из списков заканчиваются, то, что осталось в другом списке присоединяется к результирующему списку.

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	result := new(ListNode)
	current := result
	for list1 != nil && list2 != nil {
		if list1.Val < list2.Val {
			current.Next = list1
			list1 = list1.Next
		} else {
			current.Next = list2
			list2 = list2.Next
		}
		current = current.Next
	}
	if list1 == nil {
		current.Next = list2
	} else {
		current.Next = list1
	}
	return result.Next
}

Рекурсивный подход

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}
	if list2 == nil {
		return list1
	}
	if list1.Val < list2.Val {
		list1.Next = mergeTwoLists(list1.Next, list2)
		return list1
	}
	list2.Next = mergeTwoLists(list1, list2.Next)
	return list2
}

45. Jump Game II medium

https://leetcode.com/problems/jump-game-ii/

Дан массив целых чисел. Каждое число определяет максимальное количество элементов, на которое можно переместиться вправо от текущего. Найти минимальное количество шагов для перемещения от начала к концу массива.

Решение "в лоб"

Двигаясь от начала, рассчитываем максимально удалённую доступную позицию и перемещаемся в неё.

func jump(nums []int) int {
	var res int
	i := 0
	for i < len(nums)-1 {
		if nums[i] == 0 { return 0 }
		if i+nums[i] >= len(nums)-1 { return res+1 }
		m, s := 0, 1
		for j := s; j <= nums[i]; j++ {
			if j + nums[i+j] > m {
				m, s = j + nums[i+j], j
			}
		}
		i += s
		res++
	}
	return res
}

Красивое решение

Поэлементно перемещаясь от начала массива, каждый раз пересчитываем границу текущего шага и максимально достижимое смещение.

func jump(nums []int) int {
	var res int
	end, far := 0, 0
	for i := 0; i < len(nums)-1; i++ {
		if i+nums[i] > far {
			far = i+nums[i]
		}
		if i == end {
			res++
			end = far
		}
	}
	return res
}

66. Plus one easy

https://leetcode.com/problems/plus-one/

Нужно увеличить на 1 большое целое число, представленное массивом его цифр.

Решение

func plusOne(digits []int) []int {
	for i := len(digits) - 1; i >= 0; i-- {
		if digits[i] == 9 {
			digits[i] = 0
		} else {
			digits[i]++
			return digits
		}
	}
	return append([]int{1}, digits...)
}

70. Climbing Stairs easy

https://leetcode.com/problems/climbing-stairs/

Найти всевозможные варианты подъёма по лестнице из n ступеней при условии, что за раз можно подниматься на 1 или 2 ступени.

Решение

При увеличении числа ступеней количество возможных вариантов подъёма составляет последовательность, очень похожую на последовательность Фибоначчи. Для 3 и более ступеней число решений можно рассчитать по формуле: F(n) = F(n - 1) + F(n - 2). Решения с использованием рекурсии и бэктрекинга не проходят по временному лимиту, линейное же работает быстрее и является оптимальным.

func climbStairs(n int) int {
	if n <= 2 { return n }

	a, b := 1, 2

	for i := 3; i <= n; i++ {
		a, b = b, a+b
	}

	return b
}

83. Remove Duplicates from Sorted List easy

https://leetcode.com/problems/remove-duplicates-from-sorted-list/

Требуется удалить дубликаты из отсортированного списка.

Решение

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	current := head
	for current.Next != nil {
		if current.Val == current.Next.Val {
			current.Next = current.Next.Next
		} else {
			current = current.Next
		}
	}
	return head
}

88. Merge Sorted Array easy

https://leetcode.com/problems/merge-sorted-array/

Даны 2 массива целых чисел, элементы которых отсортированы по возрастанию. Нужно объединить их в один отсортированный массив без использования вспомогательного массива. Результат поместить в первый массив.

Решение

По условию задачи в конец первого массива изначально добавлены нули в соответствии с количеством элементов второго массива, которые нужно перенести. Эти нули являются "свободными местами". Двигаясь от конца обоих массивов поочерёдно сравниваем элементы и переносим в последнее "свободное место" больший из них. Делаем это до тех пор, пока не перенесём все элементы второго массива. Т.к. массивы изначально отсортированы, в результате получим также отсортированный массив.

func merge(nums1 []int, m int, nums2 []int, n int)  {
	i, j := m - 1, n - 1
	for j >= 0 {
		if i >= 0 && nums1[i] > nums2[j] {
			nums1[i+j+1], nums1[i] = nums1[i], nums1[i+j+1]
			i--
		} else {
			nums1[i+j+1] = nums2[j]
			j--
		}
	}
}

93. Restore IP Addresses medium

https://leetcode.com/problems/restore-ip-addresses/

Дана строка, содержащая цифры. Найти всевозможные варианты IP-адресов, которые могут быть получены из строки путём добавления точек между цифрами.

Решение

Идея в том, чтобы найти все варианты разбиения исходной строки на 4 подстроки. Если все 4 подстроки являются частью валидного IP-адреса, вариант добавляется в результат. Используется вспомогательная функция, вызываемая рекурсивно. При каждом вызове происходит попытка добавить в текущий вариант разбивки следующие 1, 2 или 3 цифры из копии исходной строки. Если добавляемая часть валидна, снова происходит вызов функции с обновлённым вариантом решения и обновлённой (обрезанной) копией исходной строки. Если при очередном вызове достигается граничное условие (вариант решения содержит 4 подстроки), работа функции завершается. Если при этом в копии исходной строки не осталось символов, значит вариант решения является верным и он добавляется в результат. Из строк, содержащих менее 4 или более 12 цифр, заведомо невозможно получить валидные адреса, поэтому в этом случае сразу же возвращается пустой результат.

func restoreIpAddresses(s string) []string {
	var res []string
	if len(s) < 4 || len(s) > 12 {
		return res
	}
	bt(s, []string{}, &res)
	return res
}

func bt(s string, cur []string, res *[]string) {
	if len(cur) == 4 {
		if len(s) == 0 {
			*res = append(*res, strings.Join(cur, "."))
		}
		return
	}
	for i := 1; i <= 3; i++ {
		if len(s) >= i && isValid(s[:i]) {
			bt(s[i:], append(cur, s[:i]), res)
		}
	}
}

func isValid(s string) bool {
	if len(s) > 1 && s[0] == '0' {
		return false
	}
	intVal, _ := strconv.Atoi(s)
	return intVal <= 255
}

94. Binary Tree Inorder Traversal easy

https://leetcode.com/problems/binary-tree-inorder-traversal/

Выполнить неупорядоченный обход бинарного дерева, записывая значения узлов в массив.

Решение

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
	var res []int
	if root == nil {
		return res
	}
	if root.Left != nil {
		res = append(res, inorderTraversal(root.Left)...)
	}
	res = append(res, root.Val)
	if root.Right != nil {
		res = append(res, inorderTraversal(root.Right)...)
	}
	return res
}

100. Same Tree easy

https://leetcode.com/problems/same-tree/

Нужно проверить 2 бинарных дерева на идентичность.

Решение

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSameTree(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}
	if p == nil || q == nil {
		return false
	}
	return p.Val == q.Val && isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}

101. Symmetric Tree easy

https://leetcode.com/problems/symmetric-tree/

Определить, является ли бинарное дерево "зеркальным", т.е. симметричным относительно его центра.

Решение с помощью рекурсии

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	}
	return isSymTree(root.Left, root.Right)
}

func isSymTree(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	}
	if p == nil || q == nil {
		return false
	}
	return p.Val == q.Val && isSymTree(p.Left, q.Right) && isSymTree(p.Right, q.Left)
}

Линейное решение с использованием стека

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
	if root == nil { return true}
	stack := []*TreeNode{root.Left, root.Right}
	for len(stack) > 0 {
		l, r := stack[0], stack[1]
		stack = stack[2:]
		if l == nil && r == nil {
			continue
		} else if (l == nil && r != nil) || (l != nil && r == nil) || l.Val != r.Val {
			return false
		}
		stack = append(stack, l.Left, r.Right, l.Right, r.Left)
	}
	return true
}

438. Find All Anagrams in a String medium

https://leetcode.com/problems/find-all-anagrams-in-a-string/

Найти все анаграммы строки p в строке s и вернуть их начальные индексы.

Решение

func findAnagrams(s string, p string) []int {
	var res []int
	mp := strToMap(p)
	for i := 0; i <= len(s) - len(p); i++ {
		if _, ok := mp[s[i]]; ok {
			ms := strToMap(s[i:i+len(p)])
			if fmt.Sprint(ms) == fmt.Sprint(mp) {
				res = append(res, i)
			}
		}
	}
	return res
}

func strToMap(s string) map[byte]int {
	res := make(map[byte]int)
	for i := 0; i < len(s); i++ {
		res[s[i]]++
	}
	return res
}

567. Permutation in String medium

https://leetcode.com/problems/permutation-in-string/

Определить, содержится ли в строке s2 хотя бы одна премутация строки s1. Премутацией строки называется строка, состоящая из тех же символов.

Решение

func checkInclusion(s1 string, s2 string) bool {
	m1 := strToMap(s1)
	for i := 0; i <= len(s2) - len(s1); i++ {
		if _, ok := m1[s2[i]]; ok {
			m2 := strToMap(s2[i:i+len(s1)])
			if fmt.Sprint(m1) == fmt.Sprint(m2) { return true }
		}
	}
	return false
}

func strToMap(s string) map[byte]int {
	res := make(map[byte]int)
	for i := 0; i < len(s); i++ {
		res[s[i]]++
	}
	return res
}

904. Fruit Into Baskets medium

https://leetcode.com/problems/fruit-into-baskets/

Дан массив целых чисел. Найти его максимально длинный подмассив, содержащий не более 2 уникальных чисел.

Решение

Используем метод "скользящего окна" (Sliding Window). Двигаясь от начала массива, последовательно сдвигаем правую границу диапазона до тех пор, пока количество уникальных чисел в подмассиве, определяемом границами диапазона, не превысит 2. Если это происходит, начинаем также сдвигать левую границу, пока количество уникальных чисел в подмассиве снова не станет равным 2. Фиксируем длину диапазона на каждой итерации, в результат записываем её максимальное значение.

func totalFruit(fruits []int) int {
	var res int
	i, h := 0, map[int]int{}
	for j := 0; j < len(fruits); j++ {
		h[fruits[j]]++
		for len(h) > 2 {
			if h[fruits[i]] > 1 {
				h[fruits[i]]--
			} else {
				delete(h, fruits[i])
			}
			i++
		}
		if j-i+1 > res { res = j-i+1 }
	}
	return res
}

953. Verifying an Alien Dictionary easy

https://leetcode.com/problems/verifying-an-alien-dictionary/

Дана строка, представляющая альтернативную версию английского алфавита с изменённым порядком следования букв. Определить, является ли заданная последовательность слов лексикографически отсортированной в соответствии с этим алфавитом.

Решение

func isAlienSorted(words []string, order string) bool {
	orderMap := make(map[uint8]int)
	for i := 0; i < len(order); i++ {
		orderMap[order[i]] = i
	}
	for i := 0; i < len(words) - 1; i++ {
		for j := 0; j < len(words[i]); j++ {
			if j == len(words[i+1]) { return false}
			l1, l2 := orderMap[words[i][j]], orderMap[words[i+1][j]]
			if l1 < l2 { break }
			if l1 > l2 { return false }
		}
	}
	return true
}

1071. Greatest Common Divisor of Strings easy

https://leetcode.com/problems/greatest-common-divisor-of-strings/

Подстрока является делителем строки, если строка полностью состоит из таких подстрок. Даны 2 строки, нужно найти их максимально длинный общий делитель.

Решение "в лоб"

Решение основано на том, что делитель двух строк также является префиксом для них обеих. Последовательно проверяем префиксы строк длиной от 1 до длины более короткой из них.

func gcdOfStrings(str1 string, str2 string) string {
	var res string
	for i := 1; i <= len(str1) && i <= len(str2); i++ {
		if str1[:i] == str2[:i] && checkDiv(str1, str1[:i]) && checkDiv(str2, str1[:i]){
			res = str1[:i]
		}
	}
	return res
}

func checkDiv(s string, d string) bool {
	return len(s) % len(d) == 0 && strings.Count(s, d) == len(s) / len(d)
}

Красивое решение

Строки s1 и s2 имеют общий делитель, если s1 + s2 = s2 + s1. В этом случае его длина равна максимальному общему делителю длин этих строк.

func gcdOfStrings(str1 string, str2 string) string {
	if str1 + str2 != str2 + str1 {
		return ""
	}
	return str1[:gcd(len(str1), len(str2))]
}

func gcd(x int, y int) int {
	if y == 0 {
		return x
	}
	return gcd(y, x % y)
}

1137. N-th Tribonacci Number easy

https://leetcode.com/problems/n-th-tribonacci-number/

Найти n-й член последовательности Трибоначчи, определённой следующим образом:

T₀ = 0, T₁ = 1, T₂ = 1, ..., Tₙ = Tₙ₋₁ + Tₙ₋₂ + Tₙ₋₃

Решение

func tribonacci(n int) int {
	if n < 2 { return n }
	if n == 2 { return 1 }

	a, b, c := 0, 1, 1

	for i := 3; i <= n; i++ {
		a, b, c = b, c, a+b+c
	}

	return c
}

1162. As Far from Land as Possible medium

https://leetcode.com/problems/as-far-from-land-as-possible/

Дана матрица, содержащая нули и единицы. Найти ячейку с нулём, расстояние от которой до ближайшей ячейки с единицей является максимальным, и вернуть это расстояние. Расстояние между ячейками рассчитывается по формуле |x₀ - x₁| + |y₀ - y₁|.

Решение

Записываем координаты всех ячеек с единицами в очередь. До тех пор, пока очередь не пуста, выполняем следующие действия:

• Одновременно извлекаем все имеющиеся ячейки из очереди и проверяем их соседние ячейки (левую, правую, верхнюю и нижнюю);
• Если в соседней ячейке 0, меняем её значение на 1 и добавляем в очередь;
• После проверки всех извлечённых ячеек увеличиваем результат на 1.

func maxDistance(grid [][]int) int {
	res := -1
	dirs := [][]int{ { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } }
	var queue, gridCopy [][]int
	for i := 0; i < len(grid); i++ {
		gridCopy = append(gridCopy, grid[i])
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == 1 {
				queue = append(queue, []int{ i, j })
			}
		}
	}
	for len(queue) > 0 {
		s := len(queue)
		for i := 0; i < s; i++ {
			cell := queue[0]
			queue = queue[1:]
			for _, d := range dirs {
				x, y := cell[0] + d[0], cell[1] + d[1]
				if x >= 0 && y >= 0 && x < len(grid[0]) && y < len(grid) && gridCopy[x][y] == 0 {
					gridCopy[x][y] = 1
					queue = append(queue, []int{ x, y })
				}
			}
		}
		res++
	}
	if res == 0 { return -1 }
	return res
}

1470. Shuffle the Array easy

https://leetcode.com/problems/shuffle-the-array/

Дан массив целых чисел, состоящий из 2n элементов: [x₁, x₂, ...,xₙ, y₁, y₂, ..., yₙ]. Получить из него массив вида [x₁, y₁, x₂, y₂, ...,xₙ, yₙ].

Решение

func shuffle(nums []int, n int) []int {
	var res []int
	for i := 0; i < n; i++ {
		res = append(res, nums[i], nums[i+n])
	}
	return res
}

2306. Naming a Company hard

https://leetcode.com/problems/naming-a-company/

Дан массив слов. Для получения названия компании берутся 2 любых слова, затем меняются местами их первые буквы. Если ни одно из получившихся в результате слов не присутствует в исходном массиве, названием компании будет их запись через пробел. Определить, сколько уникальных названий можно получить.

Решение

Сначала группируем слова по их первым буквам. Затем для каждой пары групп вычисляем количество слов с одинаковыми окончаниями. Валидные названия можно получить только из слов с отличающимися окончаниями в обеих группах. Из любых двух подходящих слов можно получить 2 варианта названия путём их перестановки.

func distinctNames(ideas []string) int64 {
	var res int
	var g []map[string]int
	h := map[byte]int{}
	for i := 0; i < len(ideas); i++ {
		if _, ok := h[ideas[i][0]]; !ok {
			g = append(g, map[string]int{})
			h[ideas[i][0]] = len(g) - 1
		}
		g[h[ideas[i][0]]][ideas[i][1:]]++
	}
	for i := 0; i < len(g)-1; i++ {
		for j := i + 1; j < len(g); j++ {
			m := 0
			for v := range g[i] {
				if _, ok := g[j][v]; ok {
					m++
				}
			}
			res += 2 * (len(g[i]) - m) * (len(g[j]) - m)
		}
	}
	return int64(res)
}