Удалить нижние разряды числа

Question

Предоставлено число n от x цифры. Как удалить y цифры в том, как остальные цифры приводят к большему возможному числу?

Примеры:

1)x=7 y=3 
n=7816295 
    -8-6-95 
     =8695 

2)x=4 y=2 
n=4213 
    4--3 
     =43 

3)x=3 y=1 
n=888 
    =88 

Просто в состоянии: х> у> 0.

Answer 1

Для каждой цифры для удаления: итерации по цифрам слева направо; если вы найдете цифру, которая меньше, чем правая, удалите ее и остановите, иначе удалите последнюю цифру.

Если количество цифр x больше фактической длины номера, это означает, что есть ведущие нули. Поскольку они будут первыми, вы можете просто уменьшить количество y на соответствующую сумму.

Вот рабочая версия в Python:

def remove_digits(n, x, y): 
    s = str(n) 
    if len(s) > x: 
     raise ValueError 
    elif len(s) < x: 
     y -= x - len(s) 
    if y <= 0: 
     return n 
    for r in range(y): 
     for i in range(len(s)): 
      if s[i] < s[i+1:i+2]: 
       break 
     s = s[:i] + s[i+1:] 
    return int(s) 

>>> remove_digits(7816295, 7, 3) 
8695 
>>> remove_digits(4213, 4, 2) 
43 
>>> remove_digits(888, 3, 1) 
88 

Я колебался представить это, потому что кажется слишком простым. Но я не мог придумать случай, когда это не сработает.

Answer 2

Если x = y, мы должны удалить все цифры.

В противном случае вам нужно найти максимальную цифру в первых y + 1 цифрах. Затем удалите все элементы y0 до этой максимальной цифры. Затем вам нужно добавить этот максимум к ответу, а затем снова повторить эту задачу, но теперь вам нужно удалить элементы y-y0.

Прямая реализация будет работать в O (x^2) раз в худшем случае.

Но поиск максимума в данном диапазоне может быть эффективно осуществлен с использованием структуры данных Дерева сегментов. Сложность времени будет O (x * log (x)) в худшем случае.

P. S. Я только что понял, что можно решить в O (x) также, используя тот факт, что существует только 10 цифр (но алгоритм может быть немного сложнее). Нам нужно найти минимум в заданном диапазоне [L, R], но диапазоны в этой задаче будут «изменяться» слева направо (всегда увеличиваются L и R). И нам просто нужно сохранить 10 указателей на цифры (1 на цифру) до первой позиции в числе таких, что position> = L. Тогда, чтобы найти минимум, нам нужно проверить только 10 указателей. Чтобы обновить указатели, мы попытаемся переместить их вправо.

Таким образом, временная сложность будет O (10 * х) = О (х)

Answer 3

Вот Ф (х) решение. Он строит индекс, который отображает (i, d) в j, наименьшее число> i, так что j-я цифра n равна d. С помощью этого индекса можно легко найти максимально возможную следующую цифру в решении в O (1) раз.

def index(digits): 
    next = [len(digits)+1] * 10 
    for i in xrange(len(digits), 0, -1): 
     next[ord(digits[i-1])-ord('0')] = i-1 
     yield next[::-1] 

def minseq(n, y): 
    n = str(n) 
    idx = list(index(n))[::-1] 
    i, r = 0, [] 
    for ry in xrange(len(n)-y): 
     i = next(j for j in idx[i] if j <= y+ry) + 1 
     r.append(n[i - 1]) 
    return ''.join(r) 

print minseq(7816295, 3) 
print minseq(4213, 2) 

Answer 4

псевдокод:

Number.toDigits().filter (sortedSet (Number.toDigits()). take (y)) 

Имхо вам не нужно знать х.

Для повышения эффективности Number.toDigits() может быть предварительно вычислены

digits = Number.toDigits() 
digits.filter (sortedSet (digits).take (y)) 

В зависимости от языка и контекста, либо выход цифры и сделаны или должны снова конвертировать результат в число.

Рабочая Скала-код, например:

def toDigits (l: Long) : List [Long] = if (l < 10) l :: Nil else (toDigits (l /10)) :+ (l % 10) 

val num = 734529L 
val dig = toDigits (num) 
dig.filter (_ > ((dig.sorted).take(2).last)) 

отсортированный набор набор, который отсортирован, что означает, каждый элемент содержится только один раз и затем полученная коллекция отсортирована по некоторым критериям, например, числовое восходящее. => 234579.

Мы берем два из них (23) и из этого подмножества последнего (3) и отфильтровываем число по критериям, чтобы цифры были больше этого значения (3).

В вашем вопросе явно не сказано, что каждая цифра содержится только один раз в исходном номере, но поскольку вы не дали критерия, который нужно устранить с сомнением, я воспринял его как неявное предположение.

Другие языки могут, конечно, иметь другие выражения (x.sorted, x.toSortedSet, new SortedSet (num), ...) или лишены определенных классов, функций, которые вам придется строить самостоятельно.

Возможно, вам потребуется написать собственный метод фильтрации, который берет педикат P и коллекцию C и возвращает новую коллекцию всех элементов, которые удовлетворяют P, P, являющемуся методом, который принимает один T и возвращает логическое значение. Очень полезный материал.