alexbuki
@alexbuki
программист js

Как вам такое решение задачки?

Данная задачка была на одном из собеседований в ай-ти компанию.
Свертка списка в диапазоны.
Дан список интов, повторяющихся элементов в списке нет.
Нужно преобразовать это множество в строку, сворачивая соседние по числовому ряду числа в диапазоны.
Примеры:
[1, 4, 5, 2, 3, 9, 8, 11, 0] => "0-5, 8-9, 11"
[1, 4, 3, 2] => "1-4"
[1, 4] => "1, 4"

Ниже мое решение, хочу понять насколько оно грамотное.
function range (arr) {
  arr.sort((a, b) => a - b)
  let str = arr[0]
  let iteration
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] + 1 === arr[i + 1]) {
      iteration = true
    } else {
      if (!iteration) {
        str += ',' + arr[i]
      } else {
        str += '-' + arr[i]
        if (arr[i + 1] + 1 === arr[i + 2]) {
          str += ',' + arr[i + 1]
        }
        iteration = false
      }
    }
  }
  return str
}
  • Вопрос задан
  • 2592 просмотра
Решения вопроса 6
@dimoff66
Кратко о себе: Я есть
Немного кривоватое на мой взгляд, я бы сделал так

const range = arr => arr
   .sort((a, b) => a - b)
   .reduce((agg, v) => {
      const currRange = agg[agg.length - 1]
      if (!currRange || v > currRange.last + 1) {
         agg.push({first: v, last: v})
      } else {
         currRange.last = v
      }
      return agg
   }, [])
   .map(v => v.first + (v.first !== v.last ? '-' + v.last : '')).join()
Ответ написан
0xD34F
@0xD34F Куратор тега JavaScript
Что меня здесь бесит:

  1. Мутирование переданного массива
  2. Для массивов нулевой и единичной длины результат не строка
  3. Многовато if'ов, слишком сложно

UPD. Ну и ещё результаты кривоваты. Посмотрите [ 1, 2 ], например. Или [ 5, 6, 8, 9 ].
Т.е., задача по сути не решена.
Ответ написан
profesor08
@profesor08 Куратор тега JavaScript
Твоя функция может вернуть строку, может вернуть число, а может вернуть undefined. Такое не должно происходить. Глянь ниже тестовые данные. Далее ты вручную строишь строки на основе массива, это сильно снижает читабельность кода, если не вникать то вообще не понятно что там происходит.

function range(array: number[]): string { 
  return array.sort(
    (a, b) => a - b
  ).reduce((acc, next, i) => {
    const prev = array[i - 1];

    if (prev !== undefined && next - prev === 1) {
      acc[acc.length - 1][1] = next;
    }
    else {
      acc.push([next]);
    }

    return acc;
  }, []).map(
    arr => arr.join("-")
  ).join(", ");
}

console.log(range([1, 4, 5, 2, 3, 9, 8, 11, 0])); // 0-5, 8-9, 11
console.log(range([1, 4, 3, 2])); // 1-4
console.log(range([1, 4])); // 1, 4
console.log(range([1])); // 1
console.log(range([])); // ""
Ответ написан
sergiks
@sergiks Куратор тега JavaScript
♬♬
Предложу свой велосипед на костылях. Без сортировки!
const zip = arr => arr
  .reduce((agg, c) => {
    const iR = agg.indexOf(c + 1);
    const iL = agg.lastIndexOf(c - 1);
    if (!!~iR && !!~iL) agg.splice(iL, 2); // закрыли дырку
    else if (!!~iR) agg[iR] = c; // сдвинули границу
    else if (!!~iL) agg[iL] = c; // то же
    else { // вставляем сироту - найти позицию сразу после меньшего
      let pos = 0;
      while (pos < agg.length  &&  agg[pos] < c) pos++;
      agg.splice(pos, 0, c, c); // вставляем дважды
    }
    return agg;
  }, [])
  .reduce((agg, c, i, arr) => {
    if (!(i&1)) agg.push(arr[i+1] === c ? c : [c, arr[i+1]].join('-'));
    return agg;
  }, [])
  .join(', ')
;

Массив границ диапазонов, в нём всегда чётное число элементов.
Очередное число вставляем в массив: ищем, есть ли его ближайшие соседи слева и справа.
  • Если есть оба, число закрывает «дырку», надо просто убрать этих двух соседей.
  • Если нашёлся только один – заменяем его собой, сдвигая границу.
  • Если ни одного соседа, значит, число пока сирота, вставляем его дважды,
    как будто это и левая и правая граница диапазона.
Так из первого примера получается [ 0, 5, 8, 9, 11, 11 ]
Остаётся форматирование. Смотрим только чётные элементы. Если текущий и следующий элементы равны, это «одинокое» число. Если не равны — это диапазон через дефис. И склеиваем через запятую-с-пробелом.

Учитывая сортированность собираемого массива, можно ускорить, заменив indexOf() и lastIndexOf() на самописный поиск, останавливающийся на элементе, бОльшем или меньшем искомого.

Fiddle с тестами

Ответ написан
@Flying
Можно воспользоваться тем фактом что в JavaScript в reduce()передаётся текущий индекс и сам массив, это позволяет упростить backreference. В итоге у меня получилось нечто подобное:
/**
 * @param {Array} list
 * @return {string}
 */
const range = list => list
    .sort((a,b) => a - b)
    .reduce((r, v, i, a) => {
        if (i > 0 &&  v - a[i - 1] === 1) {
            let l = r.pop();
            l.push(v);
            r.push(l);
        } else {
            r.push([v]);
        }
        return r;
    }, [])
    .map(v => v.length > 1 ? `${v.shift()}-${v.pop()}` : v)
    .join(', ');

Кусок с pop/push можно ускорить за счёт усложнения обращения к массивам, но так код получается выразительнее.

Отдельное спасибо Дмитрий за .sort((a,b) => a - b) - не знал
Ответ написан
GBreazz
@GBreazz
Вопрос автору, где такие задачи задают?
Мой код, решение универсальное работает с повторениями. По классике
function range (a) {
    if (a.length < 2) return a
    a.sort( (a, b) => a-b )
    let pred = null
    let e = false
    let result = ''
    for (let i of a) {    
        if (pred === null) {  
            result = pred = i
            continue
        }
        if (i != pred+1 )  {
            e ? result += '-' + pred + ', ' + i : result += ', ' + i
            e = false
        } else e = true
        pred = i
    }
if (e) result += '-' + pred 
return result
}

console.log(range([1, 4, 5,  2, 3, 9, 8, 11, 0]))
console.log(range([1, 4, 3, 2]))
console.log(range([1, 4, 8]))

Или так
function range (a) {
    a.sort( (a, b) => a-b )
    a = [...a,'']
    return a.reduce((st, item, i, arr) => i==0 ? st += item : ( item != arr[i-1]+1  ) ? st += '-' + arr[i-1] + ', ' + item :  st = st, '')
            .split(',')
            .map((item) => (eval(item) == 0 ? item.slice(0, item.indexOf('-')) : item).trim())
            .slice(0, -1)
            .join(', ')
  
}

console.log(range([1, 4, 5,  2, 3, 9, 8, 11, 0]))
console.log(range([1, 4, 3, 2]))
console.log(range([1, 4, 8]))

И для полной идиоматичности сделаем так
const range = a => [...a.sort( (a, b) => a-b ),''].reduce((st, item, i, arr) => i==0 ? st += item : ( item != arr[i-1]+1  ) ? st += '-' + arr[i-1] + ', ' + item :  st = st, '')
                                                  .split(',')
                                                  .map((item) => (eval(item) == 0 ? item.slice(0, item.indexOf('-')) : item).trim())
                                                  .slice(0, -1)
                                                  .join(', ')

console.log(range([1, 4, 5,  2, 3, 9, 8, 11, 0]))
console.log(range([1, 4, 3, 2]))
console.log(range([1, 4, 8]))
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Как минимум ошибка в том, что arr[i+1] и arr[i+2] будут неопределёнными на последних итерациях цикла.
Ответ написан
iCoderXXI
@iCoderXXI
React.JS/FrontEnd developer
Ой намудрили коллеги. :) Все очень просто, если сортирнуть... :) Если не сортировать, то меньше итераций особо не получится, поэтому таки сортируем и не паримся. :)

const rangeIt = data => {
  const a = [...data].sort((a, b) => a-b), r = [[a[0], a[0]]];
  for (i = 1; i < a.length; i++) {
    if (r[r.length - 1][1] + 1 === a[i]) {
      r[r.length - 1][1] = a[i];
    } else {
      r.push([a[i], a[i]]);
    }
  }
  return r.map(rr => rr[0] === rr[1] ? rr[0] : rr.join('-')).join(', ');
}


вот как-то так :)

const rangeIt = data => {
  const a = [...data].sort((a, b) => a - b), r = [[a[0], a[0]]];
  const calcRanges = (n, i) => {
    if (!i) return;
    if (r[r.length - 1][1] + 1 === n) {
      r[r.length - 1][1] = n;
    } else {
      r.push([n, n]);
    }
  };
  a.forEach(calcRanges);
  return r.map(rr => rr[0] === rr[1] ? rr[0] : rr.join('-')).join(', ');
}


или так
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы