Дорога к гению: продвинутый # 30

Каждый день я решаю несколько задач по программированию и головоломок из рейтингового режима Codr. Цель - достичь звания гения, попутно объясняю, как их решаю. Для начала вам не нужен опыт программирования, и вы узнаете массу нового и интересного по ходу дела.

function canJump(nums) {
  let max = 0; 
  for(let i = 0; i < nums.length; i++) {
      if (max < i) return false; 
      max = Math.max(nums[i] + i, max);
  }
  return max >= nums.length - 1
}
let A = canJump([5,0,0,6,4,6]);
// A = ? (boolean)

Код этого задания довольно короткий, давайте посмотрим, о чем он вообще. Нам нужно вычислить логическое значение A:
let A = canJump([5,0,0,6,4,6]);

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

for (let i = 0; i < nums.length; i++) {
    if (max < i) return false; 
    max = Math.max(nums[i] + i, max);
}

Эти три строки кода делают следующее: перебирают каждое число в массиве nums; проверка того, меньше ли max, чем i, в этом случае функция немедленно возвращает ложное значение; наконец, он определяет новое максимальное значение. Условие if фактически гарантирует, что размер max перехода больше текущего индекса i цикла for.

Этот алгоритм на самом деле определяет, может ли он «прыгнуть» в определенную позицию, где каждое число представляет максимальную длину прыжка.

Последняя строка кода показывает его окончательное состояние:
return max >= nums.length - 1
Он проверяет, больше ли max или равен размеру массива nums ', что означает, что весь алгоритм проверяет, можно ли достичь конца массива, начиная с первый индекс.

Ниже приведен псевдокод, чтобы проиллюстрировать это:

nums = [5, 0, 0, 6, 4, 6]
-> i = 0
   nums[i] = 5
   max = max(5+0, 0) = 5
   * from this index, we can jump max 5 positions further
-> i = 1
   nums[i] = 0
   max = max(0+1, 5) = 5
   * if we jump to here, we cannot jump any further (= 0)
-> i = 2
   nums[i] = 0
   max = max(0+2, 5) = 5
   * if we jump to here, we cannot jump any further (= 0)
-> i = 3
   nums[i] = 6
   max = max(6+3, 5) = 9
   * if we jump to here, we can jump max 6 positions further
-> i = 4
   nums[i] = 4
   max = max(4+4, 9) = 9
   * if we jump to here, we can jump max 4 positions further
-> i = 5
   nums[i] = 6
   max = max(6+5, 9) = 11
   * if we jump to here, we can jump max 6 positions further

Эта задача довольно тривиальна и в нашу пользу, потому что мы можем достичь конца массива (i = 5) с самого первого индекса; потому что первое число 5.

Мы даже можем значительно оптимизировать этот алгоритм, выполнив следующие действия:

function canJump(nums) {
  let max = 0; 
  for(let i = 0; i < nums.length; i++) {
      if (max < i) return false; 
      else if (max >= nums.length - 1) return true;
      max = Math.max(nums[i] + i, max);
  }
  return max >= nums.length - 1
}
let A = canJump([5,0,0,6,4,6]);

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

Альтернативный способ написания этого кода таков:

function canJump(nums) {
  let max = 0; 
  for(let i = 0; i < nums.length; i++) {
      if (max < i) return false; 
      max = Math.max(nums[i] + i, max);
      if (max >= nums.length - 1) return true;
  }
  return false;
}
let A = canJump([5,0,0,6,4,6]);

Решая эти задачи, вы становитесь лучшим программистом. Вы узнаете новые и лучшие способы анализа, отладки и улучшения кода. В результате вы станете более продуктивным и ценным в бизнесе. Присоединяйтесь ко мне на Пути к гениальности и улучшите свои навыки программирования на https://nevolin.be/codr/