JS: Массивы (3)

продолжительность 27 часов

Массивы — основной способ объединять данные в коллекции. При выводе курсов на Хекслете или списка сайтов в Гугле — всё опирается на них. В отличие от примитивных типов данных, при обращении с массивами требуются дополнительные знания. Значительная часть алгоритмических задач оперирует ни чем иным, как массивами. Именно поэтому им посвящён целый курс. Уверенная работа с коллекциями — фундамент, на котором стоит всё остальное.

Чему вы научитесь:

• Определять массивы в коде и манипулировать ими
• Формировать и обрабатывать массивы в циклах
• Применять базовые алгоритмы и оценивать их сложность
• Использовать spread, rest операторы и деструктуризацию

Уроки курса

1. О курсе Узнать о курсе, его структуре, задачах и целях
2. Синтаксис Изучить синтаксис для работы с массивами
3. Модификация Познакомиться с основными способами изменения массивов
4. Проверка существования значения Разобрать типичные ошибки при работе с массивами: выход за границу, обращение к несуществующему ключу.
5. Цикл for Научиться применять цикл for для массивов
6. Ссылки Познакомиться с понятием "ссылочные данные" и узнать как правильно обрабатывать массивы в функциях.
7. Агрегация Научиться агрегировать данные
8. Цикл for...of Научиться простому способу обходить массив
9. Удаление элементов массива Узнать о правильных и неправильных способах удаления элементов
10. Управляющие инструкции Изучить работу break и continue
11. Вложенные массивы Познакомиться с синтаксисом создания и обновления вложенных массивов
12. Генерация строки в цикле Научиться эффективно собирать строки
13. Обработка строк через преобразование в массив Узнать, как обрабатывать строки с помощью массивов
14. Вложенные циклы Научиться вкладывать циклы друг в друга
15. Теория Множеств Приобщиться к прекрасному
16. Сортировка массивов Познакомиться с базовыми алгоритмами
17. Стек Познакомиться с одной из самых фундаментальных структур данных
18. Big O Познакомиться с оценкой сложности алгоритмов
19. Деструктуризация Научиться раскладывать массив на части
20. Rest-оператор и деструктуризация Научиться сворачивать данные в массив
21. Spread-оператор и создание новых массивов Научиться применять spread-оператор (оператор "расширения") для массивов.
22. Массивы в памяти компьютера

Испытания

Это практические задания, которые мы советуем выполнить после завершения курса. Задания помогут вам получить дополнительный опыт в программировании и закрепить полученные навыки.

1 Умножение матриц

Операция умножения двух матриц А и В представляет собой вычисление результирующей матрицы С, где каждый элемент C(ij) равен сумме произведений элементов в соответствующей строке первой матрицы A(ik) и элементов в столбце второй матрицы B(kj).

Две матрицы можно перемножать только в том случае, если количество столбцов в первой матрице совпадает с количеством строк во второй матрице. Это значит, что первая матрица обязательно должна быть согласованной со второй матрицей. В результате операции умножения матрицы размера M×N на матрицу размером N×K является матрица размером M×K.

matrix.js

Реализуйте и экспортируйте по умолчанию функцию, которая принимает две матрицы и возвращает новую матрицу — результат их произведения.

Примеры

import multiply from './matrix.js';

const matrixA = [[1, 2], [3, 2]];
const matrixB = [[3, 2], [1, 1]];

multiply(matrixA, matrixB);
// [[5, 4], [11, 8]]

const matrixC = [
  [2, 5],
  [6, 7],
  [1, 8],
];
const matrixD = [
  [1, 2, 1],
  [0, 1, 0],
];

multiply(matrixC, matrixD);
// [
//   [2, 9, 2],
//   [6, 19, 6],
//   [1, 10, 1],
// ]

Подсказки

• Описание алгоритма перемножения матриц.
• Демонстрация операции перемножения матриц.

Успешных завершений: 82%

2 Обратная польская запись

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

Обратная польская нотация или постфиксная нотация — форма записи математических и логических выражений, в которой операнды расположены перед знаками операций. Выражение читается слева направо. Когда в выражении встречается знак операции, выполняется соответствующая операция над двумя ближайшими операндами, находящимися слева от знака операции. Результат операции заменяет в выражении последовательность её операндов и знак, после чего выражение вычисляется дальше по тому же правилу. Таким образом, результатом вычисления всего выражения становится результат последней вычисленной операции.

Например, выражение (1 + 2) * 4 + 3 в постфиксной нотации будет выглядеть так: 1 2 + 4 * 3 +, а результат вычисления: 15. Другой пример - выражение: 7 - 2 * 3, в постфиксной нотации: 7 2 3 * -, результат: 1.

solution.js

Реализуйте функцию calcInPolishNotation, которая принимает массив, каждый элемент которого содержит число или знак операции (+, -, *, /). Функция должна вернуть результат вычисления по обратной польской записи. Экспортируйте функцию по умолчанию.

calcInPolishNotation([1, 2, '+', 4, '*', 3, '+']); // 15
calcInPolishNotation([7, 2, 3, '*', '-']); // 1

Успешных завершений: 87%

3 Сумма интервалов

solution.js

Реализуйте и экспортируйте по умолчанию функцию, которая принимает на вход массив интервалов и возвращает сумму всех длин интервалов. В данной задаче используются только интервалы целых чисел от -100 до 100 , которые представлены в виде массива. Первое значение интервала всегда будет меньше, чем второе значение. Например, длина интервала [-100, 0] равна 100, а длина интервала [5, 5] равна 0. Пересекающиеся интервалы должны учитываться только один раз.

Примеры

sumIntervals([
   [5, 5]
]); // 0

sumIntervals([
   [-100, 0]
]); // 100

sumIntervals([
   [1, 2],
   [11, 12]
]); // 2

sumIntervals([
   [2, 7],
   [6, 6]
]); // 5

sumIntervals([
   [1, 9],
   [7, 12],
   [3, 4]
]); // 11

sumIntervals([
   [1, 5],
   [-30, 19],
   [1, 7],
   [16, 19],
   [5, 100]
]); // 130

Успешных завершений: 76%

4 Улитка

Матрицу можно представить в виде двумерного списка. Например, список [[1, 2, 3], [4, 5, 6], [7, 8, 9]] — это отображение матрицы:

1 2 3
4 5 6
7 8 9

snail.js

Реализуйте и экспортируйте по умолчанию функцию, которая принимает на вход матрицу и возвращает список элементов матрицы по порядку следования от левого верхнего элемента по часовой стрелке к внутреннему. Движение по матрице напоминает улитку:

Примеры:

buildSnailPath([
  [1, 2],
  [3, 4],
]); // [1, 2, 4, 3]

buildSnailPath([
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12],
]) // [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7] 

Подсказки

• В этом испытании можно использовать функции из библиотеки lodash.

Успешных завершений: 73%

5 Список диапазонов

solution.js

Реализуйте и экспортируйте по умолчанию функцию, которая находит в массиве непрерывные возрастающие последовательности чисел и возвращает массив с их перечислением.

Примеры

summaryRanges([]);
// []

summaryRanges([1]);
// []

summaryRanges([1, 2, 3]);
// ['1->3']

summaryRanges([0, 1, 2, 4, 5, 7]);
// ['0->2', '4->5']

summaryRanges([110, 111, 112, 111, -5, -4, -2, -3, -4, -5]);
// ['110->112', '-5->-4']

Успешных завершений: 84%

6 Возрастающая последовательность

arrays.js

Реализуйте и экспортируйте по умолчанию функцию, которая проверяет, является ли переданная последовательность целых чисел возрастающей непрерывно (не имеющей пропусков чисел). Например, последовательность [4, 5, 6, 7] — непрерывная, а [0, 1, 3] — нет. Последовательность может начинаться с любого числа, главное условие — отсутствие пропусков чисел. Последовательность из одного числа не может считаться возрастающей.

Примеры

isContinuousSequence([10, 11, 12, 13]);     // true
isContinuousSequence([-5, -4, -3]);         // true

isContinuousSequence([10, 11, 12, 14, 15]); // false
isContinuousSequence([1, 2, 2, 3]);         // false
isContinuousSequence([7]);                  // false
isContinuousSequence([]);                   // false

Успешных завершений: 95%

7 Вращение матрицы

matrix.js

Реализуйте и экспортируйте функции rotateLeft() и rotateRight(), которые поворачивают матрицу влево (против часовой стрелки) и соответственно вправо (по часовой стрелке).

• Матрица реализована на массивах.
• Функции должны возвращать новую матрицу не изменяя исходную.

Примеры:

const matrix = [
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 0, 1, 2],
];

rotateLeft(matrix);
// [
//   [4, 8, 2],
//   [3, 7, 1],
//   [2, 6, 0],
//   [1, 5, 9],
// ]

rotateRight(matrix);
// [
//   [9, 5, 1],
//   [0, 6, 2],
//   [1, 7, 3],
//   [2, 8, 4],
// ]

Успешных завершений: 86%

8 Морской бой

Перед вами популярная игра "Морской бой".

solution.js

Реализуйте и экспортируйте функцию calcShipsCount(), которая принимает на вход поле боя в виде квадратного двумерного массива из нулей и единиц. Ноль — пустая ячейка, единица — часть корабля. Функция должна вернуть количество кораблей на поле боя.

Так как корабли не должны соприкасаться друг с другом, реализуйте и экспортируйте функцию isValidField(), которая проверяет расстановку кораблей на корректность.

Примеры

calcShipsCount([]); // 0
calcShipsCount([
  [0, 1, 0, 0, 0, 0],
  [0, 1, 0, 1, 1, 1],
  [0, 0, 0, 0, 0, 0],
  [0, 1, 1, 1, 0, 1],
  [0, 0, 0, 0, 0, 1],
  [1, 1, 0, 1, 0, 0],
]); // 6
isValidField([
  [0, 1, 0, 0],
  [1, 0, 0, 1],
  [0, 0, 0, 0],
  [0, 1, 1, 1],
]); // false

Успешных завершений: 72%

9 Чанкование

chunk.js

Реализуйте и экспортируйте функцию по умолчанию, которая принимает на вход массив и число, которое задает размер чанка (куска). Функция должна вернуть массив, состоящий из чанков указанной размерности.

Примеры

chunk(['a', 'b', 'c', 'd'], 2);
// [['a', 'b'], ['c', 'd']]

chunk(['a', 'b', 'c', 'd'], 3);
// [['a', 'b', 'c'], ['d']]

Успешных завершений: 91%

10 Длина последнего слова

solution.js

Реализуйте и экспортируйте по умолчанию функцию, которая возвращает длину последнего слова переданной на вход строки. Словом считается любая последовательность, не содержащая пробелов.

Примеры

lengthOfLastWord(''); // 0

lengthOfLastWord('man in BlacK'); // 5

lengthOfLastWord('hello, world!  '); // 6

Успешных завершений: 95%

11 Треугольник Паскаля

Треугольник Паскаля — бесконечная таблица биномиальных коэффициентов, имеющая треугольную форму. В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Строки треугольника симметричны относительно вертикальной оси.

0:      1
1:     1 1
2:    1 2 1
3:   1 3 3 1
4:  1 4 6 4 1

solution.js

Напишите функцию generate, которая возвращает указанную строку треугольника паскаля в виде массива. Экспортируйте функцию по умолчанию.

Пример:

generate(1); // [1, 1]
generate(4); // [1, 4, 6, 4, 1]

Успешных завершений: 80%

12 Зеркалирование матрицы

arrays.js

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

Примеры

getMirrorMatrix([
  [11, 12, 13, 14],
  [21, 22, 23, 24],
  [31, 32, 33, 34],
  [41, 42, 43, 44],
]);

//  [
//     [11, 12, 12, 11],
//     [21, 22, 22, 21],
//     [31, 32, 32, 31],
//     [41, 42, 42, 41],
//  ]

Подсказки

• Постарайтесь решить данное испытание без использования встроенных методов массива. Ограничение не касается метода push(), который добавляет элементы в массив.

Успешных завершений: 92%

13 Вес Хэмминга

Вес Хэмминга — это количество единиц в двоичном представлении числа.

solution.js

Реализуйте и экспортируйте по умолчанию функцию, которая считает вес Хэмминга.

Примеры

hammingWeight(0); // 0
hammingWeight(4); // 1
hammingWeight(101); // 4

Успешных завершений: 94%

14 Самая длинная подстрока

solution.js

Реализуйте функцию getLongestLength() принимающую на вход строку и возвращающую длину максимальной последовательности из неповторяющихся символов. Подстрока может состоять из одного символа. Например в строке qweqrty, можно выделить следующие подстроки: qwe, weqrty. Самой длинной будет weqrty.

Экспортируйте функцию по умолчанию.

Пример

getLongestLength('abcdeef'); // 5
getLongestLength('jabjcdel'); // 7
getLongestLength(''); // 0

Подсказки

• чтобы получить индекс элемента в массиве, используйте метод .indexOf()

Успешных завершений: 77%

Хештеги