Как решить проблему с кодом Counting Valleys от HackerRank с помощью JavaScript
Проблема
Задача «Подсчет долин» - подсчитать количество долин, по которым проходит Гэри путешественник:
- Гэри = Путешественник
- Уровень моря 0 - Также начальный уровень
- S = Строка описания, которая представляет собой путь шагов, которые предпринимает путешественник Гэри.
- U и D - это «Вверх» и «Вниз» соответственно, а также направление шага Гэри.
- N = количество шагов от 2 до 10⁶ (1000000)
- AR - это одна строка чисел с интервалом от 1 до 100 - ex 10 11 20 31
- N - количество значений в шагах на пути от 2 до 1 000 000 (что может оказаться бесполезным, если мы просто вычисляем длину массива).
- Долина определяется как спускающаяся ниже уровня моря, а затем возвращающаяся к уровню моря.
Пример 1:
N =8 S = UDDDUDUU_/\ _ \ / \/\/Result: 1 Valley
Пример 2:
N = 10S = UDDDUDUUDU_/\ _ _ \ / \/ \/\/Result: 2 Valleys
Цель
Напишите функцию или функции, которые возвращают общее количество впадин, найденных путем обхода строкового пути (S) шагов
Покрытие наших баз
Прикрывая наши базы, мы должны убедиться, что:
- Количество элементов (значений) S находится в диапазоне от 2 до 10⁶.
- N - целое число от 2 до 10⁶
- N = общее количество значений S
Подсчет ценностей пути (S)
Чтобы лучше понять, сколько значений в S, нам нужно преобразовать строку в массив и посчитать ее.
function countingValleys(n, s) {
// setting the constraints
const min = 2;
const max = 1000000;
// if it's a string convert it to an array
// ex "UDU" = ["U", "D", "U"]
s = (typeof ar === "string") ? s.split('') : s;
// check if s meets the requirements
if (s.length >= min && s.length <= max) {
// continue
}
}
Проверка N
Затем нам нужно убедиться, что N является целым числом и соответствует тому же количеству значений пути (S).
function countingValleys(n, s) {
// setting the constraints
const min = 2;
const max = 1000000;
// if it's a string convert it to an array
// ex "UDU" = ["U", "D", "U"]
s = (typeof s === "string") ? s.split('') : s;
// check if s meets the requirements
if (s.length >= min
&& s.length <= max
&& n === parseInt(n, 0)
&& n >= min
&& n <= max
&& n === s.length) {
// continue
}
}
Понимание проблемы
Чтобы получить лучшее представление о направлениях, мы могли бы по-другому взглянуть на вещи: «Вверх» (U) будет +1, а «Вниз» (D) будет -1. Если определение долины - спуститься ниже уровня моря, а затем вернуться к уровню моря, наша цель - найти способ начать отсчет только тогда, когда мы выполним это условие.
Преобразование шагов в целые числа
Преобразование массива в целые числа - это первый шаг к получению указаний.
// Example // n = 8 // s = "UDDDUDUU"function countingValleys(n, s) { // setting the constraints const min = 2; const max = 1000000; // if it's a string convert it to an array // ex "UDU" = ["U", "D", "U"] s = (typeof s === "string") ? s.split('') : s; // ["U", "D", "D", "D", "U", "D", "U", "U"]// check if s meets the requirements if (s.length >= min && s.length <= max && n === parseInt(n, 0) && n >= min && n <= max && n === s.length) { // converting the array steps to integers s = s.map(steps => ((steps === "U") ? 1 : -1)); // [1, -1, -1, -1, 1, -1, 1, 1] } }
Зацикливание на шагах
Затем мы создадим цикл for и будем непрерывно суммировать шаги, чтобы пройти полный путь.
// Example // n = 8 // s = "UDDDUDUU"function countingValleys(n, s) { // setting the constraints const min = 2; const max = 1000000; // if it's a string convert it to an array // ex "UDU" = ["U", "D", "U"] s = (typeof s === "string") ? s.split('') : s; // ["U", "D", "D", "D", "U", "D", "U", "U"]// check if s meets the requirements if (s.length >= min && s.length <= max && n === parseInt(n, 0) && n >= min && n <= max && n === s.length) { // converting the array steps to integers s = s.map(steps => ((steps === "U") ? 1 : -1)); // [1, -1, -1, -1, 1, -1, 1, 1] let path = 0; for(let i in s) { path += s[i]; } // 0 + 1 = 1 // 1 + -1 = 0 // 0 + -1 = -1 // -1 + -1 = -2 // -2 + 1 = -1 // -1 + -1 = -2 // -2 + 1 = -1 // -1 + 1 = 0 // initial = 0 // end = 0 } }
Определение начальных условий для путей
Далее нам нужно обработать условие соответствия требованиям долины.
- Ниже уровня моря (‹0)
- Вернуться на уровень моря (= 0)
// Example // n = 8 // s = "UDDDUDUU"function countingValleys(n, s) { // setting the constraints const min = 2; const max = 1000000; let valleys = 0; // if it's a string convert it to an array // ex "UDU" = ["U", "D", "U"] s = (typeof s === "string") ? s.split('') : s; // ["U", "D", "D", "D", "U", "D", "U", "U"]// check if s meets the requirements if (s.length >= min && s.length <= max && n === parseInt(n, 0) && n >= min && n <= max && n === s.length) { // converting the array steps to integers s = s.map(steps => ((steps === "U") ? 1 : -1)); // [1, -1, -1, -1, 1, -1, 1, 1] let path = 0; for(let i in s) { path += s[i]; if (path < 0) { // start of a valley } if (path == 0) { // end of valley, increase count } } // 0 + 1 = 1 (Moved up = valley not started) // 1 + -1 = 0 (Back to sea level = valley not started) // 0 + -1 = -1 (Below sea level = valley started) // -1 + -1 = -2 (Moved lower = still in valley // -2 + 1 = -1 (Moved up = still in valley) // -1 + -1 = -2 (Moved lower = still in valley) // -2 + 1 = -1 (Moved up = still in valley) // -1 + 1 = 0 (Back to sea level = 1 valley) // initial = 0 // end = 0 } }
Учет того, что все еще нахожусь в долине
Теперь, когда мы определили начало и конец долины, нам также нужно учитывать, чтобы не считать долины, пока мы все еще находимся в долине.
// Example // n = 8 // s = "UDDDUDUU"function countingValleys(n, s) { // setting the constraints const min = 2; const max = 1000000; let valleys = 0; let isInValley = false; // if it's a string convert it to an array // ex "UDU" = ["U", "D", "U"] s = (typeof s === "string") ? s.split('') : s; // ["U", "D", "D", "D", "U", "D", "U", "U"]// check if s meets the requirements if (s.length >= min && s.length <= max && n === parseInt(n, 0) && n >= min && n <= max && n === s.length) { // converting the array steps to integers s = s.map(steps => ((steps === "U") ? 1 : -1)); // [1, -1, -1, -1, 1, -1, 1, 1] let path = 0; for(let i in s) { path += s[i]; if (path < 0 && !isInValley) { // to check that we're not already in a valley // start of a valley isInValley = true; } if (path == 0 && isInValley) { // to check if we're just coming out of a valley // end of valley, increase count valleys++; // increase count isInValley = false; // reset isInValley } } // 0 + 1 = 1 (Moved up = valley not started) // 1 + -1 = 0 (Back to sea level = valley not started) // 0 + -1 = -1 (Below sea level = valley started) // -1 + -1 = -2 (Moved lower = still in valley // -2 + 1 = -1 (Moved up = still in valley) // -1 + -1 = -2 (Moved lower = still in valley) // -2 + 1 = -1 (Moved up = still in valley) // -1 + 1 = 0 (Back to sea level = 1 valley) // initial = 0 // end = 0 } // to make sure we return even when the req. are not met return valleys; }
Давайте снова запустим те же значения сверху:
// Example 1
// n = 8
// s = "UDDDUDUU"
countingValleys(8, "UDDDUDUU");
// path = 1
// isInValley = false
// valleys = 0
// path = 0
// isInValley = false
// valleys = 0
// path = -1
// isInValley = true
// valleys = 0
// path = -2
// isInValley = true
// valleys = 0
// path = -1
// isInValley = true
// valleys = 0
// path = -2
// isInValley = true
// valleys = 0
// path = -1
// isInValley = true
// valleys = 0
// path = 0
// isInValley = false
// valleys = 1
// Solution = 1
Вот пример 2 (почти такой же):
// Example 2
// n = 10
// s = UDDDUDUUDU
// ...
// path = 0
// isInValley = false
// valleys = 1
// path = -1
// isInValley = true
// valleys = 1
// path = 0
// isInValley = false
// valleys = 2
// Solution = 2
Рефакторинг для повышения производительности
Теперь, когда у нас есть решение, давайте реорганизуем цикл for с помощью более эффективных методов, таких как map и reduce .
До
function countingValleys(n, s) {
const min = 2;
const max = 1000000;
let valleys = 0;
let isInValley = false;
s = (typeof s === "string") ? s.split('') : s;
if (s.length >= min
&& s.length <= max
&& n === parseInt(n, 0)
&& n >= min
&& n <= max
&& n === s.length) {
s = s.map(steps => ((steps === "U") ? 1 : -1));
let path = 0;
for(let i in s) {
path += s[i];
if (path < 0 && !isInValley) {
isInValley = true;
}
if (path == 0 && isInValley) {
valleys++;
isInValley = false;
}
}
}
return valleys;
}
После
function countingValleys(n, s) {
const min = 2;
const max = 1000000;
let valleys = 0;
let isInValley = false;
s = (typeof s === "string") ? s.split('') : s;
if (s.length >= min
&& s.length <= max
&& n === parseInt(n, 0)
&& n >= min
&& n <= max
&& n === s.length) {
// remove s = s.map because we're already iterating
s.map(steps => ((steps === "U") ? 1 : -1))
.reduce((prev, next) => {
if (prev < 0 && !isInValley) {
isInValley = true;
}
if ((prev + next) === 0 && isInValley) {
valleys++;
isInValley = false;
}
// continue incrementing by adding
return prev + next;
});
}
return valleys;
}
Решение
И вот полное решение:
function countingValleys(n, s) {
const min = 2;
const max = 1000000;
let isInValley = false;
let valleys = 0;
s = (typeof s === "string") ? s.split('') : s;
if (s.length >= min
&& s.length <= max
&& n === parseInt(n, 0)
&& n >= min
&& n <= max
&& n === s.length) {
s.map(steps => ((steps === "U") ? 1 : -1))
.reduce((prev, next) => {
if (prev < 0 && !isInValley) {
isInValley = true;
}
if ((prev + next) === 0 && isInValley) {
valleys++;
isInValley = false;
}
return prev + next;
});
}
return valleys;
}
Тестовые кейсы
// N = 8, S = "UDDDUDUU", Expected 1 // N = 12, S = "DDUUDDUDUUUD", Expected 2 // N = 1, S = "DU", Expected 0 // N = 2, S = "DU", Expected 1 // N = 3, S = "DDU", Expected 0 // N = 1000001, S = "DDU", Expected 0 // N = 20, S = "DDUUDDUUDDUUDDUUDDUU", Expected 5 // N = 10, S = "UUUUUDUUUU", Expected 0 countingValleys(8, "UDDDUDUU"); // 1 ✅ countingValleys(12, "DDUUDDUDUUUD"); // 2 ✅ countingValleys(1, "DU"); // 0 ✅ countingValleys(2, "DU"); // 1 ✅ countingValleys(3, "DDU"); // 0 ✅ countingValleys(100001, "DDU"); // 0 ✅ countingValleys(20, "DDUUDDUUDDUUDDUUDDUU"); // 5 ✅ countingValleys(10, "UUUUUDUUUU"); // 0 ✅
Обратная связь?
Если у вас есть несколько советов или рекомендаций о том, как это можно оптимизировать, или даже лучшее решение, я определенно буду готов поговорить об этом и приветствовать любые отзывы.
Если вы получили от этого пользу, поделитесь им в Twitter 🐦 или других социальных сетях. Еще раз спасибо за чтение. 🙏
Также подпишитесь на меня в twitter: @codingwithmanny и instagram на @codingwithmanny.
