Часто бывает полезно, если вы излагаете на простом английском языке sh (или на том языке, на котором вам больше всего нравится), как вы думаете, как выглядит рекурсивное отношение, и я вполне уверен, что ваша идея рекурсии неверна. Вот что вы написали:
- В пустом массиве нет подмассивов (но вы возвращаете
None вместо 0. Почему? - Если произведение все числа в массиве меньше
k, количество подмассивов равно 1. - В противном случае это число подмассивов, если мы отбросим первый элемент, плюс количество подмассивов, если мы d опустить второй элемент.
Во всех этих трех пунктах что-то не так. Во-первых, в 1. вы должны вернуть 0 вместо «ничто». Пустой массив не имеет смежных подмассивов, поэтому » 0 "- правильный ответ.
Теперь для числа 2. Ваш return 1 делает так, чтобы другая строка, return res1 + res2 никогда не выполнялась. Ясно, что это не может быть вашим намерением, но объясняет, почему в итоге вы получите ответ 2: в вашем примере полный массив не удовлетворяет критерию <= k, поэтому мы возвращаем res1 + res2, и они, скорее всего, будут равны 1.
Исправление для , которое часть логики c: вместо взамен ng 1, вы бы вернули `1 + res1 + res2 '.
Итак, теперь давайте рассмотрим вашу логику рекурсии c:
Вы говорите:« Подсчитать все смежные подмассивы данного массив, так что их произведение меньше k, мы сначала подсчитываем все смежные подмассивы этого массива, которые не включают первый элемент массива. Затем мы подсчитываем все смежные подмассивы этого массива, которые не включают последний элемент массива. Мы складываем эти два числа вверх, и, наконец, мы проверяем, является ли произведение всего массива меньше или равным k, и добавляем 1, если это так ".
Проблема с этой рекурсивной логикой c что вы будете дважды считать несколько массивов в «середине» вашего массива! Они не содержат ни первого, ни последнего элемента!
Хотя вы думаете в правильном направлении! Это «все, кроме первый "и" все, кроме последнего "вида рекурсии появляется здесь и там в компьютерной и математической науке. Хитрость в том, что вам нужно немного подправить вещи, чтобы" заставить "вашу формулировку принять во внимание первый элемент:
Что мы хотим : Учитывая мой массив, сколько существует подходящих смежных подмассивов, которые определенно содержат первый элемент, но определенно не содержат последний элемент? И сколько смежных подмассивов там, которые определенно содержат последний элемент, но определенно не содержат первый элемент?
У вас уже есть "do не может содержать первую / последнюю часть элемента справа, с индексами массива. Теперь, как нам «заставить» его содержать первый элемент? С помощью также удаляем его из индексов и соответствующим образом корректируем k.
Вот пример того, что я имею в виду:
Сколько смежных подмассивов удовлетворяют условию [10, 5, 2, 6] с k = 100, чтобы они содержали 10, но не содержали 6?
Ровно столько, сколько существует смежных подмассивов, которые удовлетворяют условию [5, 2] с k = 10. По сути, отбрасывая 10 из массива и деля k на 10, мы говорим: «О да, мы определенно выбираем 10, поэтому мы должны соответствующим образом скорректировать k».
затем в вашей рекурсии, в обоих случаях это будет array[1:-1] и k заменено на k / array[0] или k / array[-1] (убедитесь, что выбрали правильный, и потратьте некоторое время на размышления о целочисленном делении и округление, которое я оставляю в качестве упражнения для вас: p)
Это должно помочь вам в решении этого вопроса, но теперь вот еще один трюк, чтобы ускорить процесс. Быстрый вопрос, не задумываясь, сколько смежных подмассивов [1, 2, 3, 4, 5,] имеют продукт меньше 1000? Ответ: ВСЕ ИХ. Поэтому, если вы сначала вычислите произведение массива, а оно меньше k, вам больше не нужно выполнять рекурсию методом грубой силы! Вам просто нужно вычислить общее количество этих смежных подмассивов! В зависимости от вашего происхождения это простая комбинаторная проблема.
РЕДАКТИРОВАТЬ: Еще немного размышлений :) Хорошо, давайте подумаем над решением этой проблемы. Во-первых, если вы действительно хотите использовать грубую силу, вам просто нужно создать каждый возможный непрерывный подмассив и проверить его произведение:
count = 0
for start in range(0, len(array)):
for end in range(start+1, len(array)):
if product_arr(array[start:end]) <= k:
count += 1
Время выполнения этого, к сожалению, равно O (N ^ 3), поскольку у вас по сути есть три вложенных цикла.
Что мне все это напоминает, так это проблема наибольшей суммы смежных подмассивов: https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
Это можно решить в O (N), и я думаю, что общая идея может быть использована и здесь, но вместо того, чтобы отслеживать максимум, вы отслеживаете количество подмассивов, которые «работают», и вы делаете это умным способом… .
Вы запускаете al oop с «началом подмассива», а затем внутри другого l oop с «концом подмассива». Вы продолжаете увеличивать конец на 1 и проверяете, поддерживает ли добавление этого дополнительного целого числа к вашему продукту значение «k». Если это так, вы продолжаете и увеличиваете количество подмассивов на «end - start + 1». Это решающий трюк для ускорения процесса. По сути, вы учитываете не только один недавно идентифицированный подмассив, но и все другие подмассивы, которые вы получите, отбросив первый, второй, третий и т. Д. c. элемент. Потому что, если a * b * c <= k для целых положительных чисел a, b, c, то, очевидно, также b * c <= k и c <= k. </p>
Это немного сложно определить границы и точные детали, но я не могу вам с этим помочь.