Skip to main content

Домашнее задание

  1. Просмотреть задачи из урока, выучить термины и определения
  2. Решить самостоятельно задания из 'Практическая часть - решение задач и указание их сложности по времени';
    В решении задач придерживайтесь наиболее простых решений для первых 3 задач
  3. Известен номер, нужно найти фамилию в телефонной книге. Какая будет сложность у этого поиска?
  4. Сколько дней в факториале 11 секунд?

Практическая часть - решение задач и указание их сложности по времени​

Ответы на вопросы

Задача 1​

function getAverage(marks) {
  // Инициализируем сумму значением 0
  let sum = 0;

  // Проходим по каждому элементу массива и добавляем его к сумме
  for (let i = 0; i < marks.length; i++) {
    sum += marks[i];
  }

  // Вычисляем среднее значение
  const average = sum / marks.length;

  // Округляем среднее значение вниз до ближайшего целого числа и возвращаем его
  return Math.floor(average);
}

Сложность O(n)

Задача 2​

function matrix(array) {
  for (let i = 0; i < array.length; i++) {
    array[i][i] = array[i][i] < 0 ? 0 : 1;
  }
  return array;
}

Сложность О(n)

Задача 3​

function flipNumber(string) {
  // Преобразуем строку в массив символов
  let chars = [];
  for (let i = 0; i < string.length; i++) {
    chars.push(string[i]);
  }

  // Переворачиваем начальный массив
  for (let i = 0, j = chars.length - 1; i < j; i++, j--) {
    let temp = chars[i];
    chars[i] = chars[j];
    chars[j] = temp;
  }

  // Переворачиваем подстроки начиная с каждой позиции
  for (let i = 1; i < chars.length; i++) {
    let start = i;
    let end = chars.length - 1;
    while (start < end) {
      let temp = chars[start];
      chars[start] = chars[end];
      chars[end] = temp;
      start++;
      end--;
    }
  }

  // Преобразуем массив обратно в строку
  let result = "";
  for (let i = 0; i < chars.length; i++) {
    result += chars[i];
  }

  return result;
}

Сложность O(n^2)

Задача 4​

function cakes(recipe, available) {
  // Инициализируем переменную для хранения минимального количества тортов, которое можно испечь
  let minCakes = Infinity;

  // Проходим по каждому ингредиенту в рецепте
  for (let ingredient in recipe) {
    // Если ингредиента нет в наличии, то можно испечь 0 тортов
    if (!(ingredient in available)) {
      return 0;
    }

    // Вычисляем количество тортов, которое можно испечь с данным ингредиентом
    const possibleCakes = Math.floor(
      available[ingredient] / recipe[ingredient],
    );

    // Обновляем минимальное количество тортов
    if (possibleCakes < minCakes) {
      minCakes = possibleCakes;
    }
  }

  // Возвращаем минимальное количество тортов
  return minCakes;
}

Сложность O(от количества ингредиентов в рецепте)

Задача 5​

/**
 * @param {number[]} ratings
 * @return {number}
 */
var candy = function (ratings) {
  const n = ratings.length;
  const candies = new Array(n).fill(1); // Инициализируем массив конфет, каждый ребенок получает по одной конфете

  // Первый проход слева направо
  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) {
      candies[i] = candies[i - 1] + 1;
    }
  }

  // Второй проход справа налево
  for (let i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) {
      candies[i] = Math.max(candies[i], candies[i + 1] + 1);
    }
  }

  // Возвращаем сумму всех конфет
  let totalCandies = 0;
  for (let i = 0; i < n; i++) {
    totalCandies += candies[i];
  }
  return totalCandies;
};

Сложность O(n)