Введение
Я часто использую приложение Meituan для покупки билетов в кино, и меня не может не интересовать его функция выбора рекомендуемого места, поэтому я планирую реализовать аналогичный алгоритм самостоятельно.Рекомендуемый интерфейс выбора места в приложении Meituan выглядит следующим образом.
Эта демонстрация создана с помощью Vue-cli, адрес github.кликните сюда, после клонирования вы можете напрямую запускать npm для выполнения определенных операций
Алгоритмический мыслительный процесс
Для этого алгоритма рекомендуемого места я попробовал разные фильмы для выбора рекомендуемого места и пришел к следующим выводам.
(1) Алгоритм рекомендации сначала начинает поиск с середины следующего ряда после среднего ряда театра.
Как показано ниже
(2) Сначала поиск в направлении заднего ряда, а затем поиск переднего ряда из средней начальной позиции после завершения поиска заднего ряда.
Это правильно в большинстве случаев, как показано на рисунке ниже, иногда отличается
(3) После завершения поиска в заднем ряду каждый ряд будет иметь результат (результатом каждого ряда является группа мест, ближайших к центральной оси), а результат с наименьшим расстоянием от центральной оси среди этих результатов равен принимается за окончательный результат, а не расстояние чем ближе экран
Это тоже верно в большинстве случаев, в некоторых случаях нет, очень странно
(4) Учитывайте только места, расположенные бок о бок и расположенные друг за другом, в середине ряда должен быть ряд или разделение, например проходы и т.п.
Это можно понять, ведь сидеть в ряд конечно намного лучше впечатления от просмотра
Структура данных места в кинотеатре
Обязательно используйте двумерный массивseatArrayПредставляет театральную рассадку с учетом того, что распределение зрительских мест в театре неравномерно, поэтому необходимо определитьseatRowа такжеseatColдля определения размера массива театральных мест, представляющего количество рядов и столбцов, и для тех мест, где нет мест,seatArrayЗаполните -1 для соответствующей позиции, а ниже указано конкретное значение и значение места.
-1 非座位
0 可选座位 (白色)
1 已选座位 (绿色)
2 已购票座位 (红色)
Затем инициализируйте место в смонтированном состоянии, начальное значение равно 0 (необязательное место), следующий код
//初始座位数组
initSeatArray: function(){
let seatArray = Array(this.seatRow).fill(0).map(()=>Array(this.seatCol).fill(0));
this.seatArray = seatArray;
//均分父容器宽度作为座位的宽度
this.seatSize = this.$refs.innerSeatWrapper
? parseInt(parseInt(window.getComputedStyle(this.$refs.innerSeatWrapper).width,10) / this.seatCol,10)
:0;
//初始化不是座位的地方
this.initNonSeatPlace();
},
//初始化不是座位的地方
initNonSeatPlace: function(){
for(let i=0;i<9;i++){
this.seatArray[i][0]=-1;
}
for(let i=0;i<8;i++){
this.seatArray[i][this.seatArray[0].length-1]=-1;
this.seatArray[i][this.seatArray[0].length-2]=-1;
}
for(let i=0;i<9;i++){
this.seatArray[i][this.seatArray[0].length-3]=-1;
}
for(let i=0;i<this.seatArray[0].length;i++){
this.seatArray[2][i]=-1;
}
}
После инициализации для построения html-структуры используется двойной цикл, а 2 v-for вложенные циклы выводят всю структуру, следующий код
<div class="inner-seat-wrapper" ref="innerSeatWrapper" >
<div v-for="row in seatRow">
<!--这里的v-if很重要，如果没有则会导致报错，因为seatArray初始状态为空-->
<div v-for="col in seatCol"
v-if="seatArray.length>0"
class="seat"
:style="{width:seatSize+'px',height:seatSize+'px'}">
<div class="inner-seat"
@click="handleChooseSeat(row-1,col-1)"
v-if="seatArray[row-1][col-1]!==-1"
:class="seatArray[row-1][col-1]===2?'bought-seat':(seatArray[row-1][col-1]===1?'selected-seat':'unselected-seat')">
</div>
</div>
</div>
</div>
Div вышеприведенного класса внутреннего сиденья является конкретным div места, v-if указывает, что если он равен -1, то есть проход или тому подобное, он не будет отображаться, а затем предложение :class управляет значением класса соответствующего состояния места, вложенный тернарный оператор для управления, привязка события клика для каждого местаhandleChooseSeat(row-1,col-1)сделать переключение состояния
//处理座位选择逻辑
handleChooseSeat: function(row,col){
let seatValue = this.seatArray[row][col];
let newArray = this.seatArray;
//如果是已购座位，直接返回
if(seatValue===2) return
//如果是已选座位点击后变未选
if(seatValue === 1){
newArray[row][col]=0
}else if(seatValue === 0){
newArray[row][col]=1
}
//必须整体更新二维数组，Vue无法检测到数组某一项更新,必须slice复制一个数组才行
this.seatArray = newArray.slice();
},
Здесь обратите внимание, что для изменения двумерного массива в данных в vue сначала нужно закешировать двумерный массив.После модификации двумерный массив окончательно переназначается, иначе модификация не вступит в силу, т.к. Vue не может обнаружить изменения в массиве.
Конкретный код для рекомендуемого места
Сначала привяжите событие smartChoose к кнопке каждого рекомендуемого места
//推荐选座,参数是推荐座位数目
smartChoose: function(num){
//找到影院座位水平垂直中间位置的后一排
let rowStart = parseInt((this.seatRow-1)/2,10)+1;
//先从中间排往后排搜索
let backResult = this.searchSeatByDirection(rowStart,this.seatRow-1,num);
if(backResult.length>0){
this.chooseSeat(backResult);
return
}
//再从中间排往前排搜索
let forwardResult = this.searchSeatByDirection(rowStart-1,0,num);
if(forwardResult.length>0) {
this.chooseSeat(forwardResult);
return
}
//提示用户无合法位置可选
alert('无合法位置可选!')
},
Первым делом нужно найти задний ряд по горизонтали и по вертикали по центру театральных кресел, а затем позвонитьthis.searchSeatByDirectionДля поиска в этом направлении сначала ищите от среднего ряда к заднему ряду, а затем от среднего ряда к переднему ряду. Если результат найден в каком-либо направлении, верните его напрямую, иначе он подскажет пользователю, что нет законного местоположения.chooseSeatИспользуется для изменения состояния сиденья
Дело в томsearchSeatByDirectionреализация, код выглядит следующим образом
//向前后某个方向进行搜索的函数,参数是起始行，终止行,推荐座位个数
searchSeatByDirection: function(fromRow,toRow,num){
/*
* 推荐座位规则
* (1)初始状态从座位行数的一半处的后一排的中间开始向左右分别搜索，取离中间最近的，如果满足条件，
* 记录下该结果离座位中轴线的距离，后排搜索完成后取距离最小的那个结果作为最终结果，优先向后排进行搜索，
* 后排都没有才往前排搜，前排逻辑同上
* (2)只考虑并排且连续的座位，不能不在一排或者一排中间有分隔
* */
/*
* 保存当前方向搜索结果的数组,元素是对象,result是结果数组，offset代表与中轴线的偏移距离
* {
* result:Array([x,y])
* offset:Number
* }
*/
let currentDirectionSearchResult = [];
//确定行数的大小关系，从小到大进行遍历
let largeRow = fromRow>toRow?fromRow:toRow,
smallRow = fromRow>toRow?toRow:fromRow;
//逐行搜索
for(let i=smallRow;i<=largeRow;i++){
//每一排的搜索,找出该排里中轴线最近的一组座位
let tempRowResult = [],
minDistanceToMidLine=Infinity;
for(let j=0;j<=this.seatCol - num;j++){
//如果有合法位置
if(this.checkRowSeatContinusAndEmpty(i,j,j+num-1)){
//计算该组位置距离中轴线的距离:该组位置的中间位置到中轴线的距离
let resultMidPos = parseInt((j+num/2),10);
let distance = Math.abs(parseInt(this.seatCol/2) - resultMidPos);
//如果距离较短则更新
if(distance<minDistanceToMidLine){
minDistanceToMidLine = distance;
//该行的最终结果
tempRowResult = this.generateRowResult(i,j,j+num-1)
}
}
}
//保存该行的最终结果
currentDirectionSearchResult.push({
result:tempRowResult,
offset:minDistanceToMidLine
})
}
//处理后排的搜索结果:找到距离中轴线最短的一个
//注意这里的逻辑需要区分前后排，对于后排是从前往后，前排则是从后往前找
let isBackDir = fromRow < toRow;
let finalReuslt = [],minDistanceToMid = Infinity;
if(isBackDir){
//后排情况,从前往后
currentDirectionSearchResult.forEach((item)=>{
if(item.offset < minDistanceToMid){
finalReuslt = item.result;
minDistanceToMid = item.offset;
}
});
}else{
//前排情况，从后往前找
currentDirectionSearchResult.reverse().forEach((item)=>{
if(item.offset < minDistanceToMid){
finalReuslt = item.result;
minDistanceToMid = item.offset;
}
})
}
//直接返回结果
return finalReuslt
},
Код немного длинноват, но логика несложная, это реализация предыдущих правил, по каждой строке поиска может быть несколько подходящих результатов по местам.
Затем после обхода всех строк в обратном направлении строки получается массив currentDirectionSearchResult, состоящий из лучших результатов каждой строки, и далее при обходе этого массива за правило берется ближайший к центральной оси.окончательный результат вернулся
Этот алгоритм можно оптимизировать, глядя прямо из середины в две стороны, и возвращаясь при нахождении, но его немного хлопотно писать, но эффективность определенно высока. Следует отметить, что в случае с первым рядомcurrentDirectionSearchResult.reverse()Переверните ряд, потому что для переднего ряда предпочтительна задняя часть переднего ряда (никто не хочет сидеть в первом ряду!), противоположная заднему ряду
наконец
Этот алгоритм просто немного проблема, как показано ниже