1. An overview of the

This blog post is from LeetCode. Played his 198th week game, and it was a lot worse than the previous weeks. But it doesn’t matter, I found myself very food in time, the road is long to repair xi! Blog here is mainly for the week of the fourth issue derived from the thinking. This includes RMQ questions and the process of coming up with your own questions. It’s not worth much, so just write it out.

2. The RMQ problem

RMQ (Range Minimum/Maximum Query) is an algorithm developed to solve the interval Maximum problem. There are many ways to solve RMQ problems, such as line tree, or using dynamic programming. The use of DP for static interval RMQ problems is well understood. Let’s talk about it.

Let’s take a simple example

For example, given an unordered array arR. Find the maximum value of all the intervals in the array. If you pass the violence enumeration, you will definitely get TLE. But it’s easy to imagine. For a large interval [0,1], we can divide it into two sub-intervals :[0,1] and [2,3]. So the maximum value of the big interval, you can actually get it from two subintervals.

Use the idea of dynamic programming

The outcome of a large problem depends on several subproblems.

Since we use dynamic programming, we need to list the state transition equations. We let dp[I][j] represent: starting with the ith number, the maximum value of the interval of the continuous 2^j number. For example, DP [2][1] is the maximum value of the interval [2,3]. How do I get the 3. So it’s 2 plus 2 to the 1 minus 1, minus the first term.

Next, let’s consider the boundary conditions (for dynamic programming, the boundary conditions are the breakthrough point).

According to the above definition: dp[I][0] represents the maximum value of the interval of a continuous number starting with the ith number of the array. There is only one consecutive number, which is itself.

So we get, we’re going to assume that arr starts at 1.

dp[i][0]=arr[i];
Copy the code

Derive transfer equation

How do we evaluate dp[I][j]?

You can actually divide this interval into two parts. The first part is dp[I][J-1], and the second part is DP [I +(1<<(J-1))][J-1]. And then depending on the results of the two intervals to find the maximum value of the larger interval. You can see that these two intervals are confusing. Take your time. Let’s take it one by one.

  • The first is dp[I][j-1], which should be easy for us to understand. It’s going to start with I, 2 to the j-1. It just starts with I, the first half of 2 to the j. Because 2 to the j minus 1 is half of 2 to the j.
  • Next is dp[I +(1<<(J-1))][J-1]. This looks complicated. But from above, this represents the maximum value of the remaining half interval. So let’s push it by the definition of dp. The second half of the interval is the element after the last element of the first half to the end of the interval. So we need to figure out where the next half of the interval starts. It’s going to be half the length of the interval. The length calculation depends on j. So I plus (1<<(j-1)).

Therefore, we can obtain the state transition equation (taking interval maximum as an example) :

dp[i][j]= max {dp[i][j- 1],dp[i+(1<<(j- 1)][j- 1]}  
Copy the code

Query the value

Through the above procedure, we calculate the maximum value, but how do we get the result?

We assume that len is the length of the interval to be queried. So we have log len, which is the length of j in dp[I][j]. But we can’t guarantee that 2 to the log of len is equal to len. Because len doesn’t have to be an integer power of 2. So we can’t guarantee the integrity of the interval.

If the length is exactly a power of 2. So there is nothing wrong with it. The result is dp[I][log(len)], otherwise we would miss some interval, as shown below. So how to solve the problem?

3. Competition topic analysis

Title link:

Leetcode-cn.com/problems/fi…

Analysis of the topic:

After analyzing the function, we find that for l<=r, his result is a decreasing sequence. Because of the alpha and beta operations. The more you add, the smaller you end up with. If an interval [L,r] is evaluated by the above function. It’s definitely less than or equal to the interval minimum.

Since it’s an ordered sequence, we can use dichotomy. We enumerate the right boundary. Then the interval is evaluated by dichotomy and the result is recorded. Time complexity is nlog(n).

Yes, that’s what I did in the beginning, but:

In addition, the results will not be affected by repeated and same numbers, which is crucial because we will double calculate the maximum value of the interval when we query it.

So I use dynamic programming to construct interval results. Finally solved the problem.

Post code

RMQ dynamic programming code implementation

//RMQ problem code
type RMQ struct {
    Dp [][]int
}
func (rmq *RMQ) init(arr []int) {
    dp := make([] []int.len(arr))
    rmq.Dp = dp
    for i := 0; i < len(arr); i++ {
        dp[i] = make([]int.20)}// Initialization conditions. The smallest value of a number starting from I (2 to the 0) is that number.
    for i := 1; i < len(arr); i++ {
        dp[i][0] = arr[i]
    }
    //
    for j := 1; (1 << j) < len(arr); j++ {
        for i := 1; i+(1<<(j- 1))"len(arr); i++ {
        I +(1<<(j-1)) < len(arr)
        // Because I is bounded by j. The greater the j. The smaller I can take. We just need to make sure that everything from I to the end is covered.
        // The scope is divided into two parts. Because we're based on powers of two. I'm just referring to binary properties. Dichotomy is possible by the shift operator.
            dp[i][j] = rmq.withStrategy(i, j)
        }
    }
}
func (rmq *RMQ) withStrategy(i int, j int) int {
    return rmq.Dp[i][j- 1] & rmq.Dp[i+(1<<(j- 1))][j- 1]}func (rmq *RMQ) withStrategyQuery(l int, r int, k int) int {
    return rmq.Dp[l][k] & rmq.Dp[r-(1<<k)+1][k]
}
func (rmq *RMQ) query(l int, r int) int {
    k := 0
    for ; (1 << (k + 1)) <= r-l+1; k++ {
    }
    return rmq.withStrategyQuery(l, r, k)
}
Copy the code

Algorithmic logic (dichotomy)

func closestToTarget(arr []int, target int) int {
    minVal := math.MaxInt32

    rmq := RMQ{}
    tmp := make([]int.len(arr)+1)
    for k := 0; k < len(arr); k++ {
        tmp[k+1] = arr[k]
    }
    rmq.init(tmp)
    for r := 1; r < len(tmp); r++ {
        left := 1
        right := r
        for left <= right {
            mid := left + (right-left)/2
            res := rmq.query(mid, r)
            if res == target {
                return 0
            } else if res > target {
                right = mid - 1
            } else {
                left = mid + 1}}if right == 0 {
            minVal = min(minVal, rmq.query(left, r)-target)
        } else if left == r+1 {
            minVal = min(minVal, target-rmq.query(right, r))
        } else {
            minVal = min(min(rmq.query(left, r)-target, minVal), target-rmq.query(right, r))
        }
    }
    return minVal
}
func min(x, y int) int {
    if x > y {
        return y
    }
    return x
}
Copy the code