My article was locked up by Jane, so it was carried to the nuggets. In preparation for brush job hopping, here is the pure implementation of Feynman method, I intend to explain to myself, but not to others.

LeetCode 1824

Link: leetcode.com/problems/mi…

Method 1: DP

Idea: This DP maintains the minimum sideway of the three lanes that reach the current point of the alphabet. So the DP array is just three elements. At 0, they say the frog starts at lane 2, so the initial array is {1, 0, 1}. When you traverse each point, there may be an obstacle. In principle, this point should count as infinity because it is impossible to reach this obstacle. There will be a problem, which will be explained in a few sentences. So the real dp, when you get to this lane at this point, the minimum number of hops is either you didn’t jump at all, you went straight from the same lane at the previous point, or you jumped from two other lanes at this point, So dp [I] = Math. Min (dp [I], Math. Min (dp [3] (I + 1) %, dp/(I + 2) % 3) + 1); There are two problems:

  1. Update the value of dp[I] directly in the for loop, for example, dp[0] is from the minimum value of dp[1] + 1 and dp[2] + 1, for example, dp[1] + 1, so when I update the value of dp[1], I will include dp[0] + 1. In other words, the value of dp[0] was just updated according to the value of dp[1], so now the value of dp[1] is updated using the value of dp[0], will there be a problem?

This will not be a problem, because if that happens, when dp[1] gets back dp[0] + 1, it will be dp[1] + 1 + 1. This term can never be smaller than dp[1], so there is no problem updating the for loop directly. 2. What should be the notation for infinity? We can’t use intege.max_value in this problem. For example, there are ways that I like [0,1,2,3,0]. When we update the index=2, there are ways that I like [2] =2. In the for loop, dp[2], dp[1], dp[2], dp[0], dp[1], dp[2], dp[0], dp[1], dp[2], dp[1], dp[2], Math.min(dp[1], dp[2]) + 1 will overflow into the minimum value in Integer, which is a negative number, so this time dp[0] will be a negative number. To solve this problem, we should pick the right infinity so that when we add 1 to infinity, it doesn’t overflow. They gave us a range of 5 times 10 to the fifth. In the worst case, dp[I] is dp[i-1] + 2 at most every time the frog jumps across another lane and back again at the next point. So you can’t get more than 10 to the sixth in the dp array. We can solve the problem by using 10^6 as infinity.

class Solution {
    public int minSideJumps(int[] obstacles) {
        int[] dp = new int[] {1, 0, 1};
        
        for (int a : obstacles) {
            if (a > 0) {
                dp[a - 1] = 1000000;
            }
            for (int i = 0; i < 3; i++) {
                if (a != i + 1) {
                    dp[i] = Math.min(dp[i], Math.min(dp[(i + 1) % 3], dp[(i + 2) % 3]) + 1);
                }
            }
        }
        
        return Math.min(dp[0], Math.min(dp[1], dp[2]));
    }
}
Copy the code

Method 2: Be greedy

Time complexity: O(n) Idea: During the weekly competition, I wrote a greedy idea that I would maintain only one variable position, which represented the path of the frog. Then, when I tried to jump, if the next point did not have obstacle or the obstacle of the next point was not on the same path as the frog’s current path, I would directly continue. If it’s on the same path, that means the frog has to jump once at this point. If the current point has an obstacle, then jump to the path that is different from the current obstacle and the next obstacle. If the current point has no obstacle, then there are two paths to choose. At this point, jump to the furthest path of the next obstacle. This is what I did in weekly competition, but later I thought it was not as easy as the first one, so I won’t post it here. But the specific writing method is to preprocess and get an array, which I called getNextDiffIndex. That is to say, for each point, where is the next obstacle that is different from it? Then follow the if else method described above.