Shulou(Shulou.com)06/01 Report--

Today, I would like to share with you the relevant knowledge points about Java greed and enumeration. The content is detailed and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this article.

Written test skills: learn to guess knowledge points according to the data range

Generally speaking, for questions with a time limit of 1 second, the time complexity can run to about 1e8 (python and java will be less, so it is recommended that you use cCompact + pen to do the test).

N range less than 20:

O (n * 2 ^ n)

Pressure search / dfs search

N range less than 200:

O (n ^ 3)

3D dp

N range within 3000:

O (n ^ 2)

2D dp knapsack enumeration 2D prefixes and so on

Within the n-range 1e5:

O (n √ n)

Violence factor, etc.

Within the n-range 1e6:

O (nlogn)

Use all kinds of stl and look up Euler sieve and so on.

Within the n-range 1e7:

O (n)

Double pointer linear dp difference / prefix sum

Within the n-range 1e14:

O (√ n)

Find divisors and approximate numbers

Greed:

Greed means making the best choice at every step. The general problems solved have the following characteristics: local optimization can lead to global optimization.

Please note that greed is not everything!

There are n items. Each item has value v [I] and weight w [I].

What is the maximum value of the items with a total weight of no more than m now? (backpack problem)

Strategy 1: arrange them in descending order of value, and take the ones with the highest value each time.

Strategy 2: arrange them in ascending order, taking the lightest one each time.

Strategy 3: arrange it in descending order of value / weight (that is, unit value), taking the one with the highest unit value each time.

Enumeration: 1. Naive enumeration

As the name implies, enumerate all cases with a for loop.

two。 Shape pressure enumeration

Enumerate with the help of the properties of n-ary.

Suitable for the scene: there are a total of n items, and each item has m states. Enumerate all states of all items with a complexity of O (m ^ n).

Binary pressure enumeration is written:

Typical scenario: there are a total of n: A1, a2. An, with or without each number, enumerates all scenarios.

For (int iTuno Bandi)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.