Как ускорить выполнение моего кода JavaScript

Question

Есть автомобили, которые движутся вправо, и мы обозначаем их «>», и автомобили, которые движутся влево, и мы обозначаем их «<». Существуют также камеры, которые обозначаются: «.». Камера делает снимок автомобиля, если он движется в направлении камеры.

Нужно написать функцию, которая для входной строки, представляющей описанную дорогу, возвращает общее количество фотографий, сделанных камерами. Сложность должна быть строго O(N), чтобы пройти все тесты.

У меня не проходит один тест по времени, который должен выполняться не более 12 секунд. Как можно оптимизировать мой код?

Вот мое решение, оно работает корректно, но медленнее, чем того требуют тесты:

function countPhotos(road) {
    return road.split('').reduce(function (accumulator, currentValue, index, array) {
        if (currentValue == '.')
            accumulator += array.slice(index).filter(x => x == '<').length + array.slice(0, index).filter(x => x == '>').length;
        return accumulator;
    }, 0);
}

Answer 1

Проходите по строке слева направо, подсчитывая знаки >. Когда встретили точку, добавляете к результату текущее значение счётчика.

Теперь проходите справа налево, подсчитывая знаки <. Когда встретили точку, добавляете к результату текущее значение счётчика.

Всё, линейная сложность обеспечена

Answer 2

Вот решение. Оно работает за O(4*n) -> O(n).

let str = ".><.>>.<<";
let road = str.split("");
let totalLeftCars = road.filter(e => e === "<").length;
let totalRightCars = 0;
let leftPhotos = 0;
for (let i = 0; i < road.length; i++) {
    if (road[i] === ".") {
        leftPhotos += totalLeftCars;
    } else if (road[i] === "<") {
        totalLeftCars -= 1;
    }
}
let rightPhotos = 0;
for (let i = 0; i < road.length; i++) {
    if (road[i] === ".") {
        rightPhotos += totalRightCars;
    } else if (road[i] === ">") {
        totalRightCars +=1;
    }
}

console.log(leftPhotos + rightPhotos);

Answer 3

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

function countPhotos(road) {
    let result = 0;
    let countright = 0;
    let dots = 0;
    for(let i = 0; i < road.length; i++) {
       let symbol = road[i];
       if (symbol === ">") {
          countright += 1;
       } else if (symbol === "<") {
          // эта машина пересекла все точки, которые мы нашли ранее
          result += dots;
       } else {
          dots += 1;
          // все машины едущие направо справа пересекли эту точку
          result += countright;
       } 
    }
    return result;
}

console.log(countPhotos(">>."))
console.log(countPhotos(".>>"))
console.log(countPhotos(">.<."))
console.log(countPhotos(".><.>>.<<"))
console.log(countPhotos(".<<.<<<.>."))
console.log(countPhotos("..>>>.<<<>>>.<<<..>>>..<<<.."))

Answer 4

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

Решение:

const calcSnapshots = (inp)=> {
      let count = 0
      let tempToRight = 0
      let leftCams = 0
      for (let i = 0; i < inp.length; i++){
        if (inp[i] === '>') tempToRight++ // cчитаем машины едущие вправо
        else if (inp[i] === '<') count += leftCams // машины едущие влево проедут все камеры слева
        else if (inp[i] === '.') {
          count += tempToRight // встречная камера встретит все машины слева
          leftCams+=1    // увеличиваем число камер оставшихся слева
        }
      }
      return count
    }
    
    const test = (pat, expect) => {
      console.log(pat, expect, 
        calcSnapshots(pat) === expect ? 'OK' : 'FAIL')    
    }
    test(">>.", 2)
    test(".>>", 0)
    test(">.<.",3)
    test(".><.>>.<<", 11)
    test(".<<<", 3)
    test("<.<<", 2)
    test("<<.>>", 0)

БЛОГ НА HUSL

Как ускорить выполнение моего кода JavaScript

Ответы (4 шт):