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

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

Жесткий

Мы можем повернуть цифры на 180 градусов, чтобы сформировать новые цифры. Когда 0, 1, 6, 8, 9 повернуты на 180 градусов, они становятся 0, 1, 9, 8, 6 соответственно. Когда 2, 3, 4, 5 и 7 повернуты на 180 градусов, они становятся недействительными.

вводящее в заблуждение число - это число, которое при повороте на 180 градусов становится другим числом с действительной каждой цифрой (обратите внимание, что повернутое число может быть больше исходного числа).

Учитывая положительное целое число N, верните количество сбивающих с толку чисел от 1 до N включительно.

Пример 1:

Input: 20
Output: 6
Explanation: 
The confusing numbers are [6,9,10,16,18,19].
6 converts to 9.
9 converts to 6.
10 converts to 01 which is just 1.
16 converts to 91.
18 converts to 81.
19 converts to 61.

Пример 2:

Input: 100
Output: 19
Explanation: 
The confusing numbers are [6,9,10,16,18,19,60,61,66,68,80,81,86,89,90,91,98,99,100].

Примечание.

  1. 1 <= N <= 10^9

Если вы застряли, вот несколько советов:

  1. Какой набор цифр содержит действительные числа?
  2. Только 0, 1, 6, 8, 9 являются допустимым набором цифр, выполните поиск с возвратом, чтобы сгенерировать все числа, содержащие эти цифры, и проверить их действительность.

Другая версия этого вопроса, с которой вы можете столкнуться:

Вы проводите аукцион с n аукционистами. Каждому аукционисту назначается карточка с уникальным номером от 1 до n. Некоторые из них можно перевернуть вверх дном. Напишите программу, которая возвращает все числа от 1 до n, которые могут быть ошибочно приняты за другое возможное число.

Пары чисел, которые можно спутать друг с другом, включают:
«108» и «801»
«68» и «89».

Если вам было сложно ответить на этот вопрос, значит, вы не одиноки! Пожалуйста, оставляйте свои JS-решения (желательно) в комментариях. Как всегда, я опубликую решение, которое придумал. Удачи и оставайтесь в безопасности 🦠!