В продолжение прошлой недели, проблема этой недели на торте интервью только что дала мне возможность снова просмотреть бинарный поиск. Состояния подсказки, переданные в функцию, представляют собой массив слов, взятых из словаря, который был открыт где-то недалеко от центра. Соответственно, первые слова в массиве начинаются с буквы где-то в середине алфавита. Затем человек, пытающийся улучшить свой словарный запас, продолжает листать, пока не дойдет до конца, после чего он поворачивается к началу и просматривает его, пока не вернется к тому, с чего начал.
Нас просят написать функцию, принимающую один такой массив и возвращающую индекс точки перегиба, точки, в которой очевидно, что детектив словаря начал снова с самого начала. В качестве примера приведен следующий массив с точкой перегиба, находящейся в «асимптоте»:
const words = [
'ptolemaic',
'retrograde',
'supplant',
'undulate',
'xenoepist',
'asymptote',
'babka',
'banoffee',
'engender',
'karpatka',
'othellolagkage',
]
Это псевдокод для моего подхода к проблеме:
// start at the middle; check to see if the inflection point is at the median // the value of the first letter of the word at the median should be less than the value of the first letter of the next word // if it is not, then the median is the inflection point // if the median is not the inflection point, go forward or backward depending on how close to the inflection point you are and // check the median again until you find it
И это мое решение:
function rotationPoint (words) {
let start = 0;
let end = words.length - 1;
let median;
while (start <= end){
median = parseInt((start + end) / 2);
if ((words[median][0] < words[median - 1][0])) {
return median;
}
else if (words[median][0]< words[0][0]) {
end = median - 1;
}
else {
start = median + 1;
}
}
}
Если медиана не является точкой перегиба, то я проверяю, не меньше ли первая буква слова там, чем значение первой буквы первого слова в массиве. Если это так, то это означает, что точка перегиба находится раньше в массиве; таким образом, конец теперь перемещается на одну позицию перед текущей медианой. В противном случае точка перегиба находится дальше по линии с правой стороны массива, поэтому начало становится медианой + 1.
Примечание об использовании операторов «больше» и «меньше» с буквами. JavaScript позволяет нам проводить это сравнение без преобразования символов в числа. Однако, если бы мы захотели, мы могли бы использовать вместо этого .charCodeAt(). Например,
words[median].charCodeAt(0) < words[median-1].charCodeAt(0)
работает так же, как
words[median][0] < words[median - 1][0]
Цикл while выполняется до тех пор, пока либо не будет возвращен индекс точки перегиба, либо начальное значение не станет больше, чем значение конечной точки (см. мой последний пост в блоге для объяснения этого).
Хотя я ее не знаю, это профиль на Github человека, чей код на LeetCode помог мне лучше понять Binary Search: https://github.com/yuyuhhh.
Спасибо! Ты заслуживаешь кусок пирога.
