найти следующее большее число с таким же набором цифр
Учитывая число, найдите следующее большее число, которое имеет тот же самый набор цифр, что и исходный номер
Я просто бомбил интервью и делал почти нулевой прогресс по моему собеседованию. Может ли кто-нибудь дать мне знать, как это сделать? Я пробовал искать в Интернете, но ничего не мог найти:
Учитывая число, найдите следующее более высокое число, которое имеет то же самое набор цифр в качестве исходного номера. Например: при возврате 38276 38627
Я хотел начать с определения индекса первой цифры (справа), которая была меньше, чем одна цифра. Затем я бы повернул последние цифры в подмножестве так, чтобы это было следующее самое большое число, состоящее из одних и тех же цифр, но застряло.
Интервьюер также предложил попробовать поменять цифры по одному, но я не мог понять алгоритм и просто смотрел на экран примерно 20-30 минут. Само собой разумеется, я думаю, что мне придется продолжать охоту за работой.
изменить: за что его стоит, меня пригласили на следующий раунд интервью
ОТВЕТЫ
Ответ 1
Пример сделает это более понятным:
Доказательство корректности:
Поэтому N’ не может существовать, что означает, что наш алгоритм правильно находит следующее наибольшее число.
Ответ 2
Почти идентичная проблема возникла как проблема с кодовой замятием и имеет здесь решение:
Здесь приведено краткое описание метода с использованием примера:
а. Разделите последовательность цифр на две части, чтобы правая часть была как можно дольше, оставаясь в порядке убывания:
(Если все число находится в порядке убывания, больше не нужно делать число без добавления цифр.)
B.1. Выберите последнюю цифру первой последовательности:
С. Сортируйте вторую последовательность в порядке возрастания:
Ответ 3
Здесь компактное (но отчасти грубое) решение в Python
В C++ вы можете сделать перестановки следующим образом: fooobar.com/questions/32043/. (это тот же алгоритм, что и в itertools)
Здесь реализация верхнего ответа, описанного Weeble и BlueRaja, (другие ответы). Я сомневаюсь там что-нибудь лучше.
Ответ 4
Как минимум, вот пара примеров грубой силы String на основе решений, которые вы должны были бы придумать прямо с головы:
список цифр в 38627 отсортирован как 23678
Приращение грубой силы, сортировка и сравнение
Вдоль решений грубой силы будет преобразован в строку и скопировать все возможные числа, используя эти цифры.
Создайте все из них, поместите их в список и отсортируйте, введите следующую запись после целевой записи.
Если вы потратили на это 30 минут и по крайней мере не придумали хотя бы подход грубой силы, я бы тоже не нанял вас.
В деловом мире решение, которое является неэлегантным, медленным и неуклюжим, но выполняет свою работу, всегда более ценно, чем никакое решение вообще, факт, который в значительной степени описывает деловое программное обеспечение all неэлегантный, медленный и неуклюжий.
Ответ 5
Ответ 6
Я хотел начать с определения индекса первой цифры (справа), которая была меньше, чем одна цифра. Затем я бы повернул последние цифры в подмножестве так, чтобы это было следующее самое большое число, состоящее из одних и тех же цифр, но застряло.
довольно хорошо, на самом деле. Вам просто нужно учитывать не только последнюю цифру, но и все цифры меньшей значимости, чем в настоящее время. Поскольку до того, как это достигнуто, у нас есть монотонная последовательность цифр, то есть самая правая цифра, меньшая, чем ее правая сосед. Рассматривать
Следующее большее число с одинаковыми цифрами
Ответ 7
Я уверен, что ваш собеседник пытался мягко подтолкнуть вас к чему-то вроде этого:
Не обязательно самое эффективное или элегантное решение, но оно решает приведенный пример в два цикла и свопирует цифры по одному, как он предполагал.
Ответ 8
Это очень интересный вопрос.
Вот моя версия java. Возьмите меня около 3 часов, чтобы выяснить шаблон, чтобы полностью закончить код, прежде чем я проверил комментарии других участников. Рад видеть, что моя идея совсем не похожа на других.
O (n). Честно говоря, я проиграю это интервью, если время будет всего 15 минут и потребует полного завершения кода на белой доске.
Вот несколько интересных моментов для моего решения:
Я поставил подробный комментарий в моем коде и Big O на каждом шагу.
Вот результат, запущенный в Intellj:
Ответ 9
Возьмите число и разделите его на цифры. Итак, если у нас есть 5-значное число, у нас есть 5 цифр: abcde
Теперь замените d и e и сравните с исходным номером, если он больше, вы получите свой ответ.
Если он не больше, замените e и c. Теперь сравните, и если он будет меньше swap d и e снова (обратите внимание на рекурсию), возьмите наименьший.
Продолжайте, пока не найдете большее число. С рекурсией он должен работать как около 9 строк схемы, или 20 из С#.
Ответ 10
Выполнение javascript алгоритма @BlueRaja.
Ответ 11
Решение (на Java) может быть следующим (я уверен, что друзья здесь могут найти лучшее):
Начните менять цифры с конца строки до тех пор, пока не получите большее число. То есть сначала начните движение вверх по нижней цифре. Затем следующий более высокий и т.д., пока вы не нажмете следующий выше.
Затем сортируйте остальные. В вашем примере вы получите:
Ответ 12
Омар, удачи в будущем.
Ответ 13
Если вы программируете на С++, вы можете использовать next_permutation :
Ответ 14
При ответе на этот вопрос я ничего не знал об алгоритме грубой силы, поэтому подошел к нему с другой стороны. Я решил поискать весь спектр возможных решений, в которые можно переставить это число, начиная с number_given + 1 до максимального доступного числа (999 для трехзначного числа, 9999 для четырехзначного и т.д.). Я сделал подобный поиск палиндрома со словами, отсортировав номера каждого решения и сравнив его с отсортированным числом, указанным в качестве параметра. Затем я просто вернул первое решение в массиве решений, так как это было бы следующим возможным значением.
Вот мой код в Ruby:
Ответ 15
Для хорошей записи о том, как это сделать, см. » Алгоритм L» в Knuth » Искусство программирования: Создание всех перестановок» (.ps.gz).
Ответ 16
Вот мой код, это измененная версия этот пример
Ответ 17
Добавьте 9 к указанному n значению числа. Затем проверьте, находится ли он в пределах лимита (первое (n + 1) цифровое число). Если это тогда, проверьте, являются ли цифры нового номера такими же, как цифры в исходном номере. Повторите добавление 9 до тех пор, пока оба условия не будут истинными. Остановите алгоритм, когда число выходит за пределы.
Я не мог придумать противоречивый тестовый пример для этого метода.
Ответ 18
Ответ 19
Простое решение с использованием python:
Ответ 20
Ответ 21
Ниже приведен код для генерации всех перестановок числа.. хотя нужно сначала преобразовать это целое число в строку с использованием String.valueOf(integer).
Ответ 22
Ответ 23
Вот моя реализация этого в Ruby:
Ответ 24
Еще одна реализация Java, запускаемая из коробки и завершенная с помощью тестов. Это решение представляет собой O (n) пространство и время, используя хорошее старое динамическое программирование.
Если вы хотите использовать bruteforce, есть 2 вида грубой силы:
Перепишите все вещи, затем выберите min выше: O (n!)
Подобно этой реализации, но вместо DP, выполняйте шаг заселения Карта indexToIndexOfNextSmallerLeft будет работать в O (n ^ 2).
Ответ 25
Нам нужно найти правильный бит 0, за которым следует 1, и перевернуть это правое большинство из 0 бит в 1.
например, скажем, наш вход 487, который является 111100111 в двоичном формате.
мы переворачиваем правое большинство 0, у которого есть 1 после него
поэтому мы получаем 111101111
но теперь у нас есть лишний 1 и один меньше 0, поэтому мы уменьшаем число 1 справа от флип бит на 1 и увеличить значение 0 бит на 1, что дает
Ответ 26
Ответ 27
Вот реализация Java
Ответ 28
Я знаю, что это очень старый вопрос, но все же я не нашел простой код в С#. Это может помочь ребятам, которые посещают интервью.
Ответ 29
Очень простая реализация с использованием Javascript, следующего по величине числа с одинаковыми цифрами
Так как есть много комментариев, так что лучше скопировать его в текстовый редактор. Спасибо!
Ответ 30
Есть много хороших ответов, но я не нашел достойной реализации Java. Вот мои два цента:
Найти наибольшее и наименьшее из чисел, которые можно составить из всех цифр данного
Задано натуральное число N. Найти наименьшее и наибольшее число, состоящее из тех же цифр и в таком же количестве, что и N.
Входные данные:
Вы вводите с клавиатуры число N (1 ≤ N ≤ 2000000000).
Пример входных и выходных данных
Вход: 7051
Выход: 1057 7510
Определить количество всех различных 3-х значных чисел, которые можно составить из цифр данного числа
Дано 3-х значное число, определить количество всех различных 3-х значных чисел, которые можно.
Вывести наибольшее и наименьшее четырехзначное число, которые можно получить из цифр введенного числа
Вводим 4-х значное число. Вывести надо наибольшее и наименьшее четырехзначное число, которые можно.
15 чисел, найти наибольшее из всех [-] и наименьшее [+] Вывод в MsgBox
Введите последовательность из 15 целых чисел. Найти наибольшее из всех отрицательных чисел и.
Сколько различных четырехзначных чисел можно составить из данного набора цифр
Сколько различных четырехзначных чисел можно составить из данного набора цифр,если: а)никакая.
Тогда не знаю, думай сам.
Добавлено через 53 секунды
Если бы перевести число в строку, то нет проблем.
ФедосеевПавел, формально Ваша программа заданию не соответствует, поскольку в задании написано «Найти наименьшее и наибольшее число», а не «Вывести наименьшее и наибольшее число».
То же самое, но без применения «костыля» в виде строки, и с нахождением чисел:
Решение
Определить количество различных чисел, которое можно составить из цифр данного числа
Вводится трёхзначное число. Определить количество различных чисел, которое можно составить из цифр.
Требуется найти слова, которые можно составить из данного
Здравствуйте. Пользователь вводит слово. Слова, которые вообще известны, находятся в текстовом.
Сколько всех четырёхзначных чисел можно составить из цифр 1 5 6 7 8
сколько всех четырёхзначных чисел можно составить из цифр 1 5 6 7 8
Из заданных цифр составить наибольшее и наименьшее трёхзначные числа
Заданы три цифры. Напишите программу, которая из заданных цифр составит наибольшее и наименьшее.
Все варианты трехзначных чисел, которые можно составить из двух цифр
Заданы две цифры от 0 до 9. Получить все возможные варианты трехзначных чисел, которые можно.
Как вывести следующие большее число образованное теми же цифрами?
Мне нужно написать функцию которая принимает число и возвращает следующее большее число, образованное по тем же цифрам. Например:
У меня есть только вариант перебрать все возможные комбинации этих четырёх чисел и найти наиболее приближенные к нужному числу, но может есть какое-то другое решениe? Спасибо!
2 ответа 2
Эта задача эквивалентна нахождению следующей перестановки в лексикографическом порядке. В библиотеках некоторых языков есть средства типа std:: next_permutation в С++.
Хорошее описание алгоритма получения следующей перестановки можно прочитать, например, здесь, суть его:
По сути вам нужно отсортировать по убыванию цифры в составе числа. Наибольшее это отсортированное до конца, а все предыдущие перестановки заведомо меньше.
Всё ещё ищете ответ? Посмотрите другие вопросы с метками javascript алгоритм или задайте свой вопрос.
Похожие
Подписаться на ленту
Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.
дизайн сайта / логотип © 2021 Stack Exchange Inc; материалы пользователей предоставляются на условиях лицензии cc by-sa. rev 2021.11.19.40795
Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.
Учитывая число, найдите следующее более высокое число, которое имеет точно такой же набор цифр, как и исходное число
Учитывая число, найдите следующее более высокое число, которое имеет точно такое же значение. набор цифр в качестве исходного номера. Например: учитывая возврат 38276 38627
Я хотел начать с поиска индекса первой цифры (справа), которая была меньше, чем первая цифра. Затем я поворачивал последние цифры в подмножестве так, чтобы это было следующее по величине число, состоящее из тех же цифр, но застревал.
Интервьюер также предложил попробовать поменять цифры по одной за раз, но я не мог понять алгоритм и просто смотрел на экран около 28 минут. Излишне говорить, что мне придется продолжить поиски работы.
правка: как бы то ни было, меня пригласили на следующий раунд интервью
25 ответов
Пример сделает это более ясным:
Доказательство правильности:
Следовательно, N’ не может существовать, что означает, что наш алгоритм правильно находит следующее по величине число.
Почти идентичная проблема появилась как проблема замятия кода и имеет здесь решение:
Вот краткое изложение метода на примере:
Разделите последовательность цифр на две части так, чтобы правая часть была как можно длиннее, оставаясь при этом в порядке убывания:
(Если все число находится в порядке убывания, то нет большего числа, которое можно было бы сделать без добавления цифр.)
B.1. Выберите последнюю цифру из первой последовательности:
B.2. Найдите самую маленькую цифру во второй последовательности, которая больше ее:
B.3. Поменять их местами:
C. отсортируйте вторую последовательность в порядке возрастания:
Вот компактное (но частично грубое) решение в Python
В C++ вы можете сделать перестановки следующим образом: https://stackoverflow.com/a/9243091/1149664 (это тот же алгоритм, что и в itertools)
У меня есть число, и я хотел бы посмотреть, умножу ли я это число на действительное число, если новое число будет иметь точно такие же цифры, как и предыдущее число, только переставленное. Например, если бы я хотел умножить число на 2 и посмотреть, остались ли цифры прежними, я бы сделал это.
Как минимум, вот несколько примеров решений на основе грубой силы, которые вы должны были бы придумать прямо с головы:
список цифр в 38276 отсортирован так: 23678
список цифр в сортировке 38627 равен 23678
приращение грубой силы, сортировка и сравнение
Вдоль решений грубой силы было бы преобразовать в строку и грубой силой все возможные числа, используя эти цифры.
Создайте ints из них всех, поместите их в список и отсортируйте, получите следующую запись после целевой записи.
Если бы вы потратили на это 30 минут и не придумали хотя бы грубого подхода, я бы тоже вас не нанял.
В деловом мире решение, которое является неэлегантным, медленным и неуклюжим, но выполняет свою работу, всегда более ценно, чем отсутствие решения вообще, фактически это в значительной степени описывает все бизнес-программное обеспечение, неэлегантное, медленное и неуклюжее.
Учитывая число, найдите следующее большее число, которое имеет тот же набор цифр, что и исходное число
учитывая число, найдите следующее большее число, которое имеет то же самое набор цифр исходного числа. Например: given 38276 return 38627
Я хотел начать с поиска индекса первой цифры (справа), который был меньше, чем те цифра. Затем я поворачивал последние цифры в подмножестве так, чтобы это было следующее по величине число, состоящее из тех же цифр, но застряло.
интервьюер также предложил попробовать поменять цифры по одному, но я не мог понять алгоритм и просто смотрел на экран в течение 20-30 минут. Излишне говорить, что мне придется продолжить поиски работы.
edit: для чего это стоит, меня пригласили на следующий раунд интервью
30 ответов
вы можете сделать это O(n) (где n это количество цифр), как это:
начиная с правой, вы найдете первую пару цифр, так что левая цифра меньше, чем правая цифра. Давайте обратимся к левой цифре «цифра-x». Найдите наименьшее число больше цифры-x справа от цифры-x и поместите его сразу слева от цифры-x. Наконец, отсортируйте оставшиеся цифры в порядке возрастания-так как они уже были в спуск порядок, все, что вам нужно сделать, это обратить их (за исключением цифры-x, которая может быть размещена в правильном месте в O(n) ).
пример сделает это более понятным:
доказательство корректности:
N’ не может существовать, что означает, что наш алгоритм правильно находит следующее по величине число.
почти идентичная проблема появилась как проблема с Замятием кода и имеет решение здесь:
вот краткое описание метода с использованием примера:
A. разделите последовательность цифр на две части, чтобы правая часть была как можно дольше, оставаясь в порядке убывания:
(если весь число уменьшается заказ, нет большего числа, которое можно сделать без добавления цифр.)
Б. 1. Выберите последнюю цифру первой последовательности:
Б. 2. Найдите наименьшую цифру во второй последовательности, которая больше:
Б. 3. Поменять их местами:
С. вроде второй последовательности в порядке возрастания:
вот компактное (но частично грубое) решение в Python
В C++ вы можете сделать перестановки следующим образом:https://stackoverflow.com/a/9243091/1149664 (это тот же алгоритм, что и в itertools)
здесь реализации ответа описано Weeble и BlueRaja, (другие ответы). Сомневаюсь, что есть что-то лучше.
как минимум, вот несколько примеров решений на основе грубой силы, которые вы должны были придумать прямо с верхней части головы:
список цифр в 38276 отсортированный составляет 23678
список цифр в 38627 отсортированный составляет 23678
приращение грубой силы, сортировка и сравнение
вдоль решений грубой силы будет преобразовано в строку и грубой силой все возможные числа, используя те десятичные знаки.
создайте ints из них всех, поместите их в список и отсортируйте его, сделать следующую запись после целевой записи.
если бы вы потратили на это 30 минут и не придумали хотя бы подход грубой силы, я бы вас тоже не нанял.
в деловом мире решение, которое является неэлегантным, медленным и неуклюжим, но выполняет работу, всегда более ценно, чем никакое решение вообще, на самом деле, которое в значительной степени описывает все бизнес-программное обеспечение, неэлегантный, медленный и неуклюжий.
Я хотел начать с поиска индекса первой цифры (справа), которая была меньше, чем одна цифра. Затем я поворачивал последние цифры в подмножестве так, чтобы это было следующее по величине число, состоящее из тех же цифр, но застряло.
довольно хорошо, на самом деле. Вы просто должны учитывать не только последнюю цифру, но и все цифры меньшего значения, чем рассматриваемые в настоящее время. Так как до этого дошло, мы имейте монотонную последовательность цифр, то есть самая правая цифра меньше, чем ее правый сосед. Внимание
Я уверен, что ваш интервьюер пытался мягко подтолкнуть вас к чему-то вроде этого:
Не обязательно самое эффективное или элегантное решение, но оно решает приведенный пример в двух циклах и меняет цифры по одному за раз, как он предложил.
это очень интересный вопрос.
вот моя версия java. Возьми меня примерно через 3 часа еще, чтобы полностью закончить код, прежде чем я проверил комментарии других участников. Рад видеть, что моя идея совпадает с другими.
решение за o(n) времени. Честно говоря, я провалю это интервью, если время составляет всего 15 минут и требует полного завершения кода на белой доске.
вот некоторые моменты, интересные для моего решение:
я помещаю подробный комментарий в свой код и большой O на каждом шаге.
вот результат работы в Intellj:
возьмите число и разделите его на цифры. Итак, если у нас есть 5-значный номер, у нас есть 5 цифр: abcde
теперь поменяйте местами d и e и сравните с исходным номером, если он больше, у вас есть ответ.
если он не больше, замените e и C. Теперь сравните, и если это меньший своп d и e снова (обратите внимание на рекурсию), возьмите наименьший.
продолжайте, пока не найдете большее число. С рекурсией он должен работать как около 9 строк схемы, или 20 из с.#
реализация javascript алгоритма @BlueRaja.
решение (на Java) может быть следующим (Я уверен, что друзья здесь могут найти лучшее):
Начните обмениваться цифрами с конца строки, пока не получите большее число.
Т. е. сначала начните движение вверх по нижней цифре.Затем следующий выше и т. д., Пока вы не нажмете следующий выше.
Потом разберемся с остальным. В вашем примере вы получите:
Я проверил это только с двумя числами. Они работали. Как ИТ-менеджер за 8 лет до выхода на пенсию в декабре прошлого года, я заботился о трех вещах: 1) точность: хорошо если она работает-всегда. 2) Скорость: должна быть приемлема для пользователя. 3) ясность: я, вероятно, не так умен, как вы, но я плачу вам. Обязательно объясните, что вы делаете, по-английски.
Омар, удачи в будущем.
Если вы программируете на C++, вы можете использовать next_permutation :
Я ничего не знал об алгоритме грубой силы, отвечая на этот вопрос, поэтому я подошел к нему с другого угла. Я решил искать весь спектр возможных решений, в которые можно было бы переставить это число, начиная с number_given+1 до максимального числа (999 для 3-значного числа, 9999 для 4 цифр и т. д.).). Я сделал это, как найти палиндром со словами, сортируя номера каждого решения и сравнивая его с отсортированным номером задается в качестве параметра. Затем я просто вернул первое решение в массив решений, так как это было бы следующим возможным значением.
вот мой код в Ruby:
Def PermutationStep (num)
для хорошей записи о том, как это сделать, см. » Алгоритм L» в «искусство компьютерного программирования: генерация всех перестановок» (.ps.gz).
вот мой код, это модифицированная версия
добавить 9 к заданному N-значному номеру. Затем проверьте, находится ли он в пределах лимита(первый (n+1) цифровой номер). Если это так, проверьте, совпадают ли цифры в новом номере с цифрами в исходном номере. Повторите добавление 9, пока оба условия не будут выполнены. Останавливать алгоритм, когда количество зашкаливает.
Я не мог придумать противоречащий тестовый пример для этого метода.
еще одно решение с использованием python:
вот моя реализация этого в ruby:
вы можете подробнее здесь
еще одна реализация Java, выполняемая из коробки и завершенная тестами. Это решение O (n) пространство и время с использованием старого доброго динамического программирования.
Если кто-то хочет bruteforce, есть 2 вида bruteforce:
переставьте все вещи, затем выберите min выше: O (n!)
аналогично этой реализации, но вместо DP, bruteforcing шаг заполнения карта indexToIndexOfNextSmallerLeft будет запущена в O (n^2).
нам нужно найти самый правильный бит 0, за которым следует 1 и перевернуть этот самый бит 0 на 1.
например, допустим, что наш вход-487, что 111100111 в двоичном формате.
мы флип самый правый 0 с 1 после этого
Итак, мы получаем 111101111
но теперь у нас есть дополнительный 1 и один меньше 0, поэтому мы уменьшаем число 1 справа от флипа бит на 1 и увеличить нет 0 бит на 1, что дает