Задачи на слайсы
1) Что выведет данная программа и почему?
package main
import ("fmt")
func main() {
arr1 :=[...]int{1, 2,3, 4, 5}
arr2 := arr1[:4]
arr3 := append(arr2[:2], 9, 8, 7)
fmt.Println(arr3)
fmt.Println(arr2)
fmt.Println(arr1)
}
Программа выведет следующие значения:
[1 2 9 8 7]
[1 2 9 8]
[1 2 9 8 7]
Давайте разберемся, почему так происходит:
arr1 := [...]int{1, 2, 3, 4, 5}
создает массивarr1
с пятью элементами.arr2 := arr1[:4]
создает срезarr2
, который ссылается на первые четыре элемента массиваarr1
. То естьarr2
это[1, 2, 3, 4]
.arr3 := append(arr2[:2], 9, 8, 7)
берет срез первых двух элементов изarr2
(то есть[1, 2]
), и добавляет к нему элементы9, 8, 7
. Важно отметить, чтоappend
может изменять исходный массив, если в нем достаточно места для новых элементов.В данном случае, начало слайса
arr2
ссылается на начало массиваarr1
, поэтому изменения вarr2
отражаются наarr1
.После выполнения
append
,arr3
становится[1, 2, 9, 8, 7]
,arr2
изменяется на[1, 2, 9, 8]
, (7ка не влазит, так как слайсarr2
имеет фиксированную длину в 4 элемента), аarr1
теперь[1, 2, 9, 8, 7] (так как в нем достаточно места и для 7ки)
.Вывод
fmt.Println(arr3)
,fmt.Println(arr2)
,fmt.Println(arr1)
показывает измененные значения массивов и срезов после операций сappend
.
Это пример того, как операции с срезами и функцией append
могут влиять на исходные массивы в Go, особенно когда срезы создаются на основе этих массивов.
2) Что выведет данная программа и почему?
package main
import(
"fmt"
)
func add(s []string) {
s = append(s, "x")
}
func main() {
s := []string{"a", "b", "c"}
add(s[1:2])
fmt.Println(s)
}
Программа выведет ["a", "b", "x"] вот почему:
1. В функции `main()` создается массив `s` с элементами `["a", "b", "c"]`.
2. Затем вызывается функция `add`, в которую передается срез `s[1:2]`. Этот срез содержит только один элемент — `["b"]`, и он ссылается на ту же часть базового массива, что и исходный срез `s`.
3. В функции `add`, срез `s` (который является локальной копией переданного среза) модифицируется с помощью `append`, добавляя к нему строку `"x"`. Поскольку исходный срез `s` в `main()` и переданный срез в `add` ссылаются на один и тот же базовый массив, и в этом массиве есть место для добавления элемента (так как его емкость позволяет это), `append` добавляет `"x"` непосредственно в базовый массив, изменяя его.
5. Поэтому, когда в функции `main()` выполняется `fmt.Println(s)`, выводится измененный базовый массив, который теперь содержит `["a", "b", "x"]`.
3) Что будет выведено без аппенд и потом с ним?
package main
import (
"fmt"
)
func mod(a []int) {
//a = append(a, 125)
for i := range a {
a[i] = 5
}
}
func main() {
sl := []int{1, 2, 3, 4}
mod(sl)
fmt.Println(sl)
}
Давайте разберем, что произойдет в коде с и без использования append
.
Код без использования append
append
package main
import (
"fmt"
)
func mod(a []int) {
for i := range a {
a[i] = 5
}
}
func main() {
sl := []int{1, 2, 3, 4}
mod(sl)
fmt.Println(sl)
}
Объяснение:
В функции
main
создается срезsl
с элементами[1, 2, 3, 4]
.Срез
sl
передается в функциюmod
.В функции
mod
происходит итерация по срезуa
(который является ссылкой наsl
), и каждый элемент заменяется на5
.После выполнения функции
mod
, срезsl
вmain
будет изменен на[5, 5, 5, 5]
, так как срезы в Go передаются по ссылке.
Вывод:
[5 5 5 5]
Код с использованием append
append
package main
import (
"fmt"
)
func mod(a []int) {
a = append(a, 125)
for i := range a {
a[i] = 5
}
}
func main() {
sl := []int{1, 2, 3, 4}
mod(sl)
fmt.Println(sl)
}
Объяснение:
В функции
main
создается срезsl
с элементами[1, 2, 3, 4]
.Срез
sl
передается в функциюmod
.В функции
mod
выполняетсяappend(a, 125)
, что создает новый срез, который является копиейa
с добавленным элементом125
. Этот новый срез присваивается переменнойa
внутри функцииmod
.Затем происходит итерация по новому срезу
a
, и каждый элемент заменяется на5
. Однако это изменение не влияет на исходный срезsl
, так какa
теперь указывает на новый срез.После выполнения функции
mod
, срезsl
вmain
останется неизменным, так как изменения были сделаны в копии среза.
Вывод:
[1 2 3 4]
Заключение
Без использования
append
: Срезsl
будет изменен на[5, 5, 5, 5]
, так как изменения происходят непосредственно в переданном срезе.С использованием
append
: Срезsl
останется неизменным[1, 2, 3, 4]
, так какappend
создает новый срез, и изменения происходят в этом новом срезе, а не в исходном.
4) Написать функцию, которая на вход принимает 2 отсортированных слайса с типом Int в ответ выдает 1 отсортированный слайс, содержащий данные из входящих слайсов. Оценить сложность алгоритма.
Для объединения двух отсортированных слайсов в один отсортированный слайс можно использовать алгоритм слияния, который является частью алгоритма сортировки слиянием (merge sort). Этот алгоритм работает за линейное время, то есть его временная сложность составляет O(n + m), где n и m — размеры входных слайсов.
Реализация функции на Go
package main
import (
"fmt"
)
func mergeSortedSlices(a, b []int) []int {
// Инициализируем результирующий слайс
result := make([]int, 0, len(a)+len(b))
// Индексы для итерации по слайсам a и b
i, j := 0, 0
// Слияние двух слайсов
for i < len(a) && j < len(b) {
if a[i] < b[j] {
result = append(result, a[i])
i++
} else {
result = append(result, b[j])
j++
}
}
// Добавляем оставшиеся элементы из слайса a, если они есть
for i < len(a) {
result = append(result, a[i])
i++
}
// Добавляем оставшиеся элементы из слайса b, если они есть
for j < len(b) {
result = append(result, b[j])
j++
}
return result
}
func main() {
a := []int{1, 3, 5, 7}
b := []int{2, 4, 6, 8}
merged := mergeSortedSlices(a, b)
fmt.Println(merged) // Ожидаемый вывод: [1 2 3 4 5 6 7 8]
}
Объяснение алгоритма
Инициализация:
Создаем результирующий слайс
result
с начальной емкостью, равной сумме длин входных слайсовa
иb
.Инициализируем индексы
i
иj
для итерации по слайсамa
иb
соответственно.
Основной цикл слияния:
Пока оба индекса
i
иj
находятся в пределах длин своих слайсов, сравниваем текущие элементыa[i]
иb[j]
.Добавляем меньший элемент в результирующий слайс и увеличиваем соответствующий индекс.
Добавление оставшихся элементов:
После завершения основного цикла, один из слайсов может содержать оставшиеся элементы. Добавляем их в результирующий слайс.
Оценка сложности
Временная сложность: O(n + m), где n и m — размеры входных слайсов. Это обусловлено тем, что каждый элемент из обоих слайсов обрабатывается ровно один раз.
Пространственная сложность: O(n + m), так как создается новый слайс, содержащий все элементы из входных слайсов.
Этот алгоритм является оптимальным для задачи слияния двух отсортированных слайсов и работает эффективно даже для больших входных данных.
5) Что выведет данная программа и почему?
package main
import (
"fmt"
)
func a() {
x := []int{}
x = append(x, 0)
x = append(x, 1)
x = append(x, 2)
y := append(x, 3)
z := append(x, 4)
fmt.Println(y, z)
}
func main() {
a()
}
Давайте разберем, что происходит в этой программе и что она выведет.
Разбор кода
Создание и заполнение слайса
x
:x := []int{} x = append(x, 0) x = append(x, 1) x = append(x, 2)
После этих операций
x
будет содержать[0, 1, 2]
.Создание слайсов
y
иz
:y := append(x, 3) z := append(x, 4)
Здесь начинается интересное. Важно понимать, что
append
может изменять базовый массив слайса, если его емкость позволяет. Если емкость недостаточна,append
создаст новый массив и скопирует в него данные.y := append(x, 3)
добавляет3
кx
, так чтоy
становится[0, 1, 2, 3]
.z := append(x, 4)
добавляет4
кx
, так чтоz
становится[0, 1, 2, 4]
.
Однако, так как
x
иy
ссылаются на один и тот же базовый массив, изменениеx
черезappend
может повлиять наy
.
Вывод программы
Когда мы вызываем fmt.Println(y, z)
, мы получаем:
[0 1 2 4] [0 1 2 4]
Почему так происходит?
Когда
y := append(x, 3)
выполняется,y
ссылается на тот же базовый массив, что иx
, но с дополнительным элементом3
.Когда
z := append(x, 4)
выполняется,z
также ссылается на тот же базовый массив, что иx
, но с дополнительным элементом4
.
Так как x
и y
ссылаются на один и тот же базовый массив, изменение x
через append
влияет на y
. В результате, оба слайса y
и z
содержат [0, 1, 2, 4]
.
Заключение
Программа выводит [0 1 2 4] [0 1 2 4]
из-за того, что append
изменяет базовый массив слайса, если его емкость позволяет. В данном случае, x
, y
и z
ссылаются на один и тот же базовый массив, что приводит к такому результату.
6) Задача: Требуется реализовать функцию uniqRandn, которая генерирует слайс длины n уникальных рандомных чисел:
package main
import (
"fmt"
"math/rand"
)
func main() {
fmt.Println(uniqRandn(10))
}
func uniqRandn(n int) []int {
//
}
Для реализации функции uniqRandn
, которая генерирует слайс длины n
уникальных случайных чисел, можно использовать несколько подходов. Один из них — это использование карты (map) для отслеживания уже сгенерированных чисел, чтобы избежать дубликатов.
Реализация функции uniqRandn
uniqRandn
Импорт необходимых пакетов:
math/rand
для генерации случайных чисел.time
для инициализации генератора случайных чисел.
Инициализация генератора случайных чисел:
Используем текущее время в наносекундах для инициализации генератора случайных чисел.
Использование карты для отслеживания уникальных чисел:
Генерируем случайные числа и добавляем их в карту до тех пор, пока не наберем нужное количество уникальных чисел.
Код
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
fmt.Println(uniqRandn(10))
}
func uniqRandn(n int) []int {
rand.Seed(time.Now().UnixNano()) // Инициализация генератора случайных чисел
nums := make(map[int]struct{}) // Карта для отслеживания уникальных чисел
result := make([]int, 0, n) // Слайс для хранения результата
for len(nums) < n {
num := rand.Intn(100) // Генерация случайного числа (в диапазоне от 0 до 99)
if _, exists := nums[num]; !exists {
nums[num] = struct{}{}
result = append(result, num)
}
}
return result
}
Объяснение кода
Инициализация генератора случайных чисел:
rand.Seed(time.Now().UnixNano())
Это гарантирует, что генератор случайных чисел будет инициализирован текущим временем, что делает последовательность случайных чисел уникальной при каждом запуске программы.
Создание карты и слайса:
nums := make(map[int]struct{}) result := make([]int, 0, n)
Карта
nums
используется для отслеживания уникальных чисел, а слайсresult
для хранения результата.Генерация уникальных случайных чисел:
for len(nums) < n { num := rand.Intn(100) if _, exists := nums[num]; !exists { nums[num] = struct{}{} result = append(result, num) } }
Цикл продолжается до тех пор, пока количество уникальных чисел в карте
nums
не достигнетn
. Внутри цикла генерируется случайное числоnum
. Если это число еще не присутствует в картеnums
, оно добавляется в карту и слайсresult
.
Заключение
Этот код генерирует слайс длины n
уникальных случайных чисел. Если требуется другой диапазон случайных чисел, можно изменить аргумент функции rand.Intn
. Например, для генерации чисел в диапазоне от 0 до 999, используйте rand.Intn(1000)
.
Last updated