Управляемое чтение

Я считаю, что у каждого должен быть опыт получения билетов на поезд.В конце каждого года это праздник. Однако задумывались ли вы когда-нибудь о том, как реализован алгоритм захвата билетов на поезд? Наверное, нет, давайте сегодня обсудим их по порядку. Это не так сложно, как вы думаете

растровые и битовые операции

Мы уже познакомили вас с базовым использованием растрового изображения redis ранее, если вы не знакомы с ним, вы можете посмотреть здесь.Основные операции и приложения растрового изображения Redis

Сегодня мы сначала рассмотрим битовую операцию.

Подробное объяснение алгоритма захвата билетов 12306

Возьмем для примера скоростной поезд из Пекина в Сиань.Например мой маршрут из Пекина в Сиань.Если на поезде остался только последний билет,то если есть другие люди,покупайте любой билет между Пекином и Сиань. станцией, то я не могу купить билет. Другими словами, для одного места, это должны быть все станции между отправной точкой и пунктом назначения. Если никто не покупает его, то он можно рассматривать как состояние билета.

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

• Например, в поезде всего 4 места.

• От Пекина до Сианя всего 4 остановки, на самом деле есть три интервала, а именно: Пекин->Шицзячжуан, Шицзячжуан->Чжэнчжоу, Чжэнчжоу->Сиань.

Во-первых, мы создаем пустую растровую карту для каждого интервала (0 голосует, 1 не голосует)

Далее предположим, что кто-то купил билет из Пекина в Сиань.

Например, для действия по покупке билета назначенным местом является место с номером 1, затем мы напрямую устанавливаем все станции от Пекина до Сианя, а место номер 1 устанавливается на 1, как показано на следующем рисунке. фигура

Потом кто-то купил билет из Шицзячжуана в Сиань.

Например, на этот раз выделено место 2, тогда мы можем установить для всех билетов из Шицзячжуана в Сиань место 1, как показано ниже.

Как узнать, сколько билетов осталось?

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

Или если в результате операции несколько нулей, значит, сколько билетов осталось.

Суммировать

На самом деле основное решение этой проблемы заключается в построении растрового изображения, потому что для билета на поезд, пока занят определенный интервал между начальной и конечной точками (установлен в 1), то все место занято. недопустимо, что очень просто. Думая использовать результат операции ИЛИ для суждения о результате покупки билета, мы используем здесь только 4 цифры для удобства объяснения проблемы. На самом деле это должно быть сколько мест есть на поезде, и длина растрового изображения должна быть. Что ж, мы познакомим вас с алгоритмом захвата билетов. Или у вас есть лучший способ сделать это?

нытье

Всем привет, я Xiaofan, бэкенд-инженер. Если вы считаете, что статья немного полезна для вас, поделитесь ею со своими друзьями и поставьте лайк Сяофань. Ниже приведена моя официальная учетная запись. Откройте WeChat и выполните поиск «Программист Сяофань», чтобы увидеть ее. Если вам интересно, Вы можете следовать ему. Это мотивация для Сяофань продолжать, спасибо, увидимся в следующий раз!