Обзор
Проблемы с бросанием яиц - очень классический вопрос для интервью, использовались Google, Baidu, Tencent и другие крупные предприятия.У этого вопроса есть несколько вариантов вариантов, расширяемость очень сильна, решает многие виды, давайте обсудим это!
Стандартные вопросы для интервью
Описание темы
有2个鸡蛋，从100层楼上往下扔，以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎，在第10层摔碎了，那么鸡蛋不会摔碎的临界点就是9层。
问：如何用最少的尝试次数，测试出鸡蛋不会摔碎的临界点？
Пример:
举个栗子，最笨的测试方法是什么样呢？
把其中一个鸡蛋从第1层开始往下扔。
如果在第1层没碎，换到第2层扔
如果在第2层没碎，换到第3层扔
.......
如果第59层没碎，换到第60层扔
如果第60层碎了，说明不会摔碎的临界点是第59层
在最坏情况下，这个方法需要扔100次。
Метод 1: дихотомия
На первый взгляд на этот вопрос некоторые студенты могут подумать, что это не эквивалентно найти определенное число с 1-100? Это самый быстрый для использования метода дихотомии. Давайте выделим его ниже.
Используя метод, аналогичный бинарному поиску, яйца сбрасываются с половины этажа (50-й этаж).
Если первое яйцо разбивается на 50-м слое, второе яйцо кидается из 1-го слоя, увеличиваясь слой за слоем, пока не будет брошено на 49-й слой. Если первое яйцо не разбито на 50-м этаже, продолжайте использовать дихотомию и бросьте его на половину оставшихся этажей (75-й этаж)...
В худшем случае этот метод требует 50 попыток (100/2).
Метод 2: Метод квадратного корня
Как я могу сделать количество попыток для первого яйца и второго яйца максимально сбалансированным?
Очень просто, сделайте операцию извлечения квадратного корня, квадратный корень из 100 равен 10.
Следовательно, мы пытаемся бросить один раз каждые 10 слоев, 10 слоев из первого броска, бросая со второго слоя 20, а третья была брошена с 30-го этажа ...... 100 слоев.
В лучшем случае это разбить на 10-м слое с 1 + 9 = 10 попытками.
В худшем случае разбивается на уровне 100, 10 + 9 = 19 попыток.
Здесь есть момент оптимизации, например, мы можем начать кидать с 15-го слоя, потом 25, 35.... до 95-го слоя, самый быстрый случай - 95-й слой пробит, а количество попыток 9+ 9 = 18 раз
Метод 3: Решение методом уравнения
Со средней школы ученики все выучили уравнения.Пусть есть неизвестное X, удовлетворяющее условиям.По известным условиям составьте уравнение n-й степени одной переменной и решит его.Теперь выведем это уравнение по формуле описание темы.
Если предположить, что у задачи есть оптимальное решение (процесс бросания яиц), а число попыток этого решения в худшем случае равно x раз, то какой слой мы должны выбрать для первого бросания яиц?
Именно с х слоя начинать кидать, не подходит выбирать выше или ниже слой
Зачем выбирать слой x для первого броска?
Объяснение здесь также через метод предположений, а затем дедуктивное, немного выжигающее мозги, настаивают друзья:
Предположим, что первый бросок находится на уровне x+1 (больше, чем x):
Если первое яйцо разбито, второе яйцо можно перебрасывать только слой за слоем из слоя 1 в слой x.
Таким образом, мы попытались в общей сложности x+1 раз, вопреки предположению, что мы попытались x раз. Видно, что этаж первого броска должен быть меньше x+1 этажа.
Предположим, что первый бросок находится на уровне x-1 (меньше x):
Если первое яйцо разбито, второе яйцо можно бросать только слой за слоем, начиная со слоя 1 и заканчивая слоем x-2.
Это дает нам общее количество попыток x-2+1 = x-1, что, хотя и не превышает предполагаемого числа, кажется несколько консервативным.
Предположим, что первый бросок находится на уровне x:
Если первое яйцо разбито, второе яйцо можно бросать только слой за слоем, начиная со слоя 1 и заканчивая слоем x-1.
Таким образом, мы попробовали всего x-1+1 = x раз, просто не превышая предполагаемое количество раз.
Следовательно, если вы хотите сделать пролет пола максимально большим и убедиться, что он не превышает предполагаемого числа попыток x, оптимальным выбором для первого бросания яиц является x-й этаж.
Вышеуказанные являются допущениями + логическими рассуждениями и не были строго доказаны математикой, и мы не математики
индукция
Если яйцо не разбивается с первого раза, наша попытка расходуется один раз, и задача превращается в бросок двух яиц на 100-х этажей, требующих не более х-1 попыток
Таким образом, пролет пола во второй попытке равен x-1 этажам, а абсолютный этаж равен x+(x-1) этажам.
Точно так же, если яйцо не разбилось, пролет третьего этажа равен х-2, а четвертого раза - х-3.
Друзья, а вы сейчас видели закон?По сводке можно составить уравнение на этажность:
x + (x-1) + (x-2) + ... + 1 = 100
Давайте решим это уравнение:
(x+1)*x/2 = 100
Окончательный x округляется, чтобы получитьx=14
Таким образом, число попыток оптимального решения в худшем случае равно14пол, на который в первый раз было брошено яйцо, тоже был14Этаж.
Наконец, давайте перечислим количество перепробованных этажей, не разбив первое яйцо:
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100
举个栗子验证下：
假如鸡蛋不会碎的临界点是65层，那么第一个鸡蛋扔出的楼层是14，27，50，60，69。这时候啪的一声碎了。
第二个鸡蛋继续，从61层开始，61，62，63，64，65，66，啪的一声碎了。
因此得到不会碎的临界点65层，总尝试次数是 6 + 6 = 12 < 14 。
Дополнительные вопросы для интервью
Описание темы
Вы получите K-яйца и можете использовать в общей сложности N-этаж здания от 1 до N.
Каждое яйцо работает одинаково, если яйцо разобьется, вы не сможете его снова уронить.
Вы знаете, что существует этаж F такой, что 0
За каждый ход вы можете взять яйцо (если у вас есть целое яйцо) и бросить его с любого этажа X (где 1
Ваша цель — точно знать, каково значение F.
Независимо от начального значения F, за какое минимальное количество ходов можно определить значение F?
Пример 1:
输入：K = 1, N = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。
Пример 2:
输入：K = 2, N = 6
输出：3
Пример 3:
输入：K = 3, N = 14
输出：4
намекать:
1. 1 <= K <= 100
2. 1 <= N <= 10000
Динамическое программирование находит общее решение проблемы метания яиц 1
Что такое динамическое программирование?
Динамическое программирование (ДП) — это метод, используемый в математике, менеджменте, информатике, экономике и биоинформатике для решения сложных задач путем разложения исходной проблемы на относительно простые подзадачи.
Динамическое программирование решает проблему в два этапа:
1. Поиск уравнения перехода состояния
2. Используйте уравнение перехода состояний для решения задачи снизу вверх
Как найти уравнение перехода состояния?
В стандартном варианте задачи при условии двух яиц по 100 этажей находим закон:
Если предположить, что существует оптимальное решение, количество попыток в худшем случае равно х, тогда этаж, на который в первый раз брошено первое яйцо, также равен х
Может ли это правило применяться при наличии более трех яиц?
假设有三个鸡蛋，100层楼，第一个鸡蛋扔在第10层并摔碎了。这时候我们还剩下两个鸡蛋，因此第二个鸡蛋不必从底向上一层一层扔，而是可以选择在第5层扔。如果第二个鸡蛋也摔碎了，那么第三个鸡蛋才需要老老实实从第1层开始一层一层扔。
这样一来，总的尝试次数是1+1+4 = 6 < 10(最少次数)。
因此，最优解的最坏情况下尝试次数是 X，鸡蛋首次扔出的楼层也是 X 这个规律不再成立。
Итак, как мы находим закономерности?
Здесь мы абстрагируем проблему M этажей / N яиц в функцию черного ящика F (M, N).Количество этажей M и количество яиц N являются двумя параметрами функции, а возвращаемое значение функции оптимальное решение максимальное количество попыток
Предполагая, что первое брошенное яйцо находится на X-м слое (1
1. Первое яйцо не разбито
Затем остальные M-Xные этажи и остальные N-яйца могут быть преобразованы в следующую функцию:
F(M-X,N)+1, 1
2. Первое яйцо разбито
Затем нужно попробовать только этажи с 1 по X-1, а оставшееся количество яиц равно N-1, что можно преобразовать в следующую функцию:
F(X-1, N-1) + 1, 1
В целом, то, что мы просим, — это решение с наименьшим максимальным числом попыток при условии N этажей / K яиц, поэтому уравнение перехода состояний для этой задачи выглядит следующим образом:
X может быть 1...N, поэтому есть M значений Max (F(NX,K)+1, F(X-1,K-1)+1) и, наконец, F(N,K) является минимумом этих значений M, т. е. оптимальным решением
F(N,K)=Min(Max(F(N-X,K)+1,F(X-1,K-1)+1)), 1
Как это решить?
С уравнением перехода состояния, как рассчитать результат этого уравнения?
Конечно, мы можем сделать это рекурсивно. Но временная сложность рекурсии экспоненциальна, когда значения M и N велики, эффективность рекурсии станет очень низкой.
Согласно идее динамического программирования, мы можем вычислить результат уравнения снизу вверх.
Что такое снизу вверх? В качестве примера возьмем случай с 3 яйцами и 4 этажами.
Согласно уравнению перехода состояний динамического программирования и идее восходящего решения, нам нужно шаг за шагом вывести последующее состояние от оптимального количества попыток для 1 яйца и 1 этажа до количества попыток для 3 яиц и 4 этажей. рассчитывается. .
Во-первых, мы можем заполнить количество попыток для первого яйца на каждом этаже и количество попыток для любого количества яиц на 1 этаже.
причина проста:
1. Яйцо всего одно, так что подвоха нет, кинуть его можно только с 1 этажа на последний этаж, а количество попыток равно количеству этажей.
2. Этаж только один, сколько бы яиц ни было, способ броска только один, и количество попыток может быть только 1.
Согласно вышеприведенному уравнению, заменяя вычисленные следующие результаты. Не вдаваться в детали расчета
Код
По идее только сейчас изначально реализован код:
func superEggDrop(K, N int) int {
if K < 1 || N < 1 {
return 0
}
//备忘录，存储K个鸡蛋，N层楼条件下的最优化尝试次数
//cache := [K + 1][N + 1]int{}
cache := make([][]int, K+1)
//把备忘录每个元素初始化成最大的尝试次数
for i := 0; i <= K; i++ {
cache[i] = make([]int, N+1)
for j := 1; j <= N; j++ {
cache[i][j] = j
}
}
for n := 2; n <= K; n++ {
for m := 1; m <= N; m++ {
//假设楼层数可以是1---N,
min := cache[n][m]
for k := 1; k < m; k++ {
//M层,N鸡蛋,F（N，K）= Min（Max（ F（N-X，K）+ 1， F（X-1，K-1） + 1）），1<=X<=N
//(动态规划)
//鸡蛋碎了
max := cache[n-1][k-1] + 1
if cache[n][m-k]+1 > max {
max = cache[n][m-k] + 1 //鸡蛋没碎
}
if max < min {
min = max
}
}
cache[n][m] = min
}
}
return cache[K][N]
}
Трехслойная петля, временная сложность O(K*N*N)
Двумерный массив: пространственная сложность O(M*N)
Временная сложность слишком высока, чтобы пройти тестовый пример leetcode, и время ожидания истекло.
Динамическое программирование находит общее решение проблемы метания яиц 2
Временная сложность приведенного выше решения довольно высока, так что есть ли более быстрый алгоритм?
В приведенном выше алгоритме, в основном для трех циклов, соответственно, необходимо предположить первые яйца, брошенные с первого слоя 1 ..... n
Существует ли алгоритм, сочетающий идеи индуктивной дедукции и динамического программирования, который можно здесь абстрагировать?
假设移动x次,k个鸡蛋,最优解的最坏条件下可以检测n层楼,层数n=黑箱子函数f(x,k)
假设从n0+1层丢下鸡蛋,
1,鸡蛋破了
剩下x-1次机会和k-1个鸡蛋,可以检测n0层楼
2, 鸡蛋没破
剩下x-1次机会和k个鸡蛋,可以检测n1层楼
那么 临界值层数F在[1,n0+n1+1]中的任何一个值,都都能被检测出来
归纳的状态转移方程式为:f(x,k) = f(x-1,k-1)+f(x-1,k)+1,即x次移动的函数值可以由x-1的结果推导,这个思路很抽象,需要花时间去理解,具体看代码,对照着代码理解
可以简化为黑箱子函数的返回值只跟鸡蛋个数k有关系:
本次fun(k) = 上次fun(k-1)+上次fun(k)+1
Код
Временная сложность составляет O(K*ходов), что не имеет ничего общего с количеством этажей (значение количества этажей N относительно велико).
func superEggDrop(K, N int) int {
moves := 0
dp := make([]int, K+1) // 1 <= K <= 100
// dp[i] = n 表示， i 个鸡蛋，利用 moves 次移动，最多可以检测 n 层楼
for dp[K] < N {
for i := K; i > 0; i-- {
//逆序从K---1,dp[i] = dp[i]+dp[i-1] + 1 相当于上次移动后的结果,dp[]函数要理解成抽象出来的一个黑箱子函数,跟上一次移动时鸡蛋的结果有关系
dp[i] += dp[i-1] + 1
// 以上计算式，是从以下转移方程简化而来
// dp[moves][k] = 1 + dp[moves-1][k-1] + dp[moves-1][k]
// 假设 dp[moves-1][k-1] = n0, dp[moves-1][k] = n1
// 首先检测，从第 n0+1 楼丢下鸡蛋会不会破。
// 如果鸡蛋破了，F 一定是在 [1：n0] 楼中，
// 利用剩下的 moves-1 次机会和 k-1 个鸡蛋，可以把 F 找出来。
// 如果鸡蛋没破，假如 F 在 [n0+2:n0+n1+1] 楼中
// 利用剩下的 moves-1 次机会和 k 个鸡蛋把，也可以把 F 找出来。
// 所以，当有 moves 个放置机会和 k 个鸡蛋的时候
// F 在 [1, n0+n1+1] 中的任何一楼，都能够被检测出来。
}
moves++
}
return moves
}
Суммировать
- Для подобных головоломок, если мы не можем найти другие решения, мы можем сначала предположить, что существует оптимальное решение x, которое удовлетворяет результату, а затем подставить его в контекст, чтобы проанализировать проблему, индуктивно вывести и выяснить правила
- Для очень сложных задач может потребоваться очень дивергентное мышление и высокая степень абстракции алгоритма.
- Процесс обдумывания проблемы очень утомительный, и я поделюсь с вами!
GitHub
- Исходный код проекта здесь
- Автор всегда будет поддерживать проект, решать проблемы с алгоритмами в leetcode и записывать свои собственные идеи и мнения, посвященные понятным каждому алгоритмам.
Личный публичный аккаунт
- Друзья, кому нравится, можете подписаться, спасибо за вашу поддержку
- От: Ву Мин (WeChat: wm497735138), автор: Ву Мин