Задачи на слайсы

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`

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`

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`

Импорт необходимых пакетов:
- 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).

PreviousЗадачи на строки NextЗадачи на мапы

Last updated 8 months ago

1) Что выведет данная программа и почему?

2) Что выведет данная программа и почему?

3) Что будет выведено без аппенд и потом с ним?

Код без использования append

Код с использованием append

Заключение

Реализация функции на Go

Объяснение алгоритма

Оценка сложности

5) Что выведет данная программа и почему?

Разбор кода

Вывод программы

Почему так происходит?

Заключение

6) Задача: Требуется реализовать функцию uniqRandn, которая генерирует слайс длины n уникальных рандомных чисел:

Реализация функции uniqRandn

Код

Объяснение кода

Заключение

Код без использования `append`

Код с использованием `append`

Реализация функции `uniqRandn`