Итак, если вы столкнулись с этой проблемой или чем-то подобным, вот как ее решить.
Сначала постановка проблемы.
Вам дан набор S целых чисел от -30000 до 30000 (включительно).
которые удовлетворяют:
d!=0
Вход
В первой строке записано целое число N (1 ≤ N ≤ 100) - размер множества S.
Элементы S приведены в следующих N строках, по одному целому числу в строке. Данные числа будут разными.
Выход
Выведите общее количество возможностей.
Эта редакционная статья - не просто решение проблемы, а мыслительный процесс, который мы будем развивать со временем, чтобы вы могли подумать в следующий раз, когда возникнет аналогичная проблема.
Давайте начнем!
Когда мы интерпретируем проблему, это выводы.
1. Из заданного массива мы должны выбрать 6 чисел.
2. Числа могут повторяться. Это означает, что вам не нужно минимум 6 чисел (не волнуйтесь, даже если это было условие, вы сможете решить его после того, как мы закончим).
Например, допустим, вам нужно рис 4 числа из массива [2,1,3] в форму 6: вы можете выбрать 2 три раза, или 3 два раза, или 1 шесть раз, или 1,2 и 3, чтобы сформировать 6.
3.Эти 6 чисел имеют чтобы удовлетворить уравнение. Это означает, что LHS и RHS должны быть одинаковыми.
Итак, сначала метод грубой силы, о котором подумал бы любой начинающий конкурентоспособный программист, заключается в том, как мы изобразим числа из массива, каковы их комбинации. Давайте теперь подробно рассмотрим процесс выбора.
скажем, array = [1,3,4] и нам нужно выбрать 4 числа
вы можете выбрать
1,1,1,1
1,1,1,3
1,1,1,4
1,1,3,1
1,1,3,3
1,1, 3,4
1,1,4,1
…. и так далее .
Теперь внимательно наблюдайте! Я меняю только одно число за раз со всеми возможными числами.
Это означает, что для выбора 4 чисел из любого массива вам нужно 4 цикла, в которых индекс меняется один за другим (i, j, k, l )
Итак, псевдокод будет выглядеть следующим образом.
комбинации var = пустой массив
для i = от 0 до i ‹длина массива:
для j = от 0 до j‹ длина массива:
для k = 0 до k ‹длина массива:
для l = 0 до l ‹длина массива:
var комбинация = [array [i], array [j], array [k], array [l]]
добавить комбинацию к массив комбинаций
- Обратите внимание на отступ.
Итак, мы просто получили каждую комбинацию в комбинациях
Теперь все, что нам нужно сделать, это проверить комбинации, которые соответствуют определенным критериям.
Но разве это не худший из возможных способов решения нашей проблемы?
Наша задача будет иметь временную сложность n степени 6.
Итак, давайте придумаем, как это уменьшить.
Посмотрите на данное нам уравнение.
((a * b + c) / d) -e = f
можем ли мы изменить это, чтобы выбрать только 3 числа
Да, мы можем
а * б + с = (е + д) г
Итак, теперь мы можем поместить комбинации левой стороны (lhs) в один массив и комбинации правой стороны (rhs) в другой, и для этого нам понадобится всего 3 цикла.
Круто, не так ли?
Давай сделаем это
для i = от 0 до i ‹длина массива:
для j = от 0 до j‹ длина массива:
для k = 0 до k ‹длина массива:
lhs.append (arr [i] * arr [j] + arr [k])
rhs.append (arr [k] * (arr [i] -arr [j]))
Итак, теперь все, что нам нужно сделать, это посмотреть, сколько чисел в левой части совпадают с числами в правой части.
Еще 1 концепт (маленький) - Пример «c1.
Допустим, у вас есть массив [2,2,3,4,5,5,6]
и другие как [2,3,3,5,5,5,6,6]
Каждый из них в обоих массивах имеет уникальный способ получить это число.
Итак, если я спрошу вас сейчас, сколькими способами (комбинациями) вы можете получить число 5, которое есть в обоих массивах, каков был бы ваш ответ?
Число 5 в array1 (x), умноженное на количество раз в array2 (y)!
Это 2 * 3 = 6 (x * y)
Если бы было 3 массива, вы бы умножили количество появлений во всех трех массивах (x * y * z)
Итак, мы применим эту концепцию к массивам lhs и rhs.
Суммируйте, чтобы получить общее количество раз!
Итого = сумма возможностей
Как в примере «c1»: Итого = 2 * 1 + 1 * 2 + 1 * 0 + 2 * 3 + 1 * 6
что есть не что иное, как возможности 2, 3,4,5,6 соответственно.
Последняя часть включает в себя нижнюю границу и верхнюю границу для подсчета в каждом массиве, с которым все знакомы (я думаю).
Также помните, что есть условие d! = 0: поэтому, если d равно 0, не учитывайте эту комбинацию.
Все, до следующего раза. Холод!
