Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

2024.7.10

**Daily Question**

2970. Count the number of increasing subarrays removed I. This question is about double pointers and the basic properties of arrays. The question is to count how many subarrays can satisfy the strict increasing relationship of the remaining elements after removal. At the beginning, I did not consider that the removed elements must be continuous, so I made a mistake. After considering this problem, we can discuss it by category; first, we can count the maximum prefix of the array. If the entire array is increasing, then we don’t need to calculate other cases; if not, then we first add the answer that only considers all increasing prefixes, which is the subscript of the maximum increasing prefix plus 2; then we consider the general case, that is, removing the middle array, which will result in an increasing prefix and an increasing suffix, and the front of the connection is smaller than the back. For this kind of question that requires enumeration and discussion on both sides, we can only enumerate one side and then determine the value of the other side, so we choose to enumerate the suffix. As long as the suffix satisfies the forward decreasing relationship, we will perform the calculation. We first let the largest increasing prefix go back until the connection satisfies the relationship. Then the answer at this time is the subscript of the largest prefix plus 2. The remaining task is to imitate this process to complete the loop until the suffix does not satisfy the situation.

63. Different Paths II, this is a simple dynamic programming question, the main purpose is to train our DP thinking. According to the question, the robot goes right or down, so the number of methods for each step is the number of methods for the previous step plus the number of methods for the left step. But we noticed that there are obstacles, so when we encounter obstacles, we just set the total number of methods to 0. This question also requires initialization, first determine the starting point, and then initialize the first row and the first column, and initialization also requires determining obstacles.