2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
After reading the question, we know that in a string of length n, we need to find the length of the longest palindrome substring. A palindrome substring can be understood as a symmetrical string. Because of its symmetry, the basic idea is the "center expansion method", that is, to traverse the string in sequence, and then expand to both sides of the character when it is traversed. If the characters on both sides are equal, then record them in the retlen variable, and return the maximum length after traversing. To facilitate understanding, draw a picture:
In addition, when analyzing the examples, we must also pay attention to the difference between odd and even numbers, so the next step is program implementation.
First, according to the "center expansion method" of the idea analysis, traverse the string and expand from the center station at i, and compare and update the retlen obtained in turn. Then, because it is necessary to distinguish between odd and even numbers, the maximum value is obtained respectively. Finally, compare them in turn to get the final maximum retlen and return it.
class Solution
{
public:
int getLongestPalindrome(string A)
{
size_t len = A.size();
int left = 0;
int right = 0;
int retlen = 0;
//偶数
for(int i = 0;i < len; i++)
{
left = i;
right = i + 1;
while(left >= 0 && right < len && A[left] == A[right])
{
left--;
right++;
}
retlen = max(retlen ,right - left - 1);
}
//奇数
for(int j = 0;j < len;j++)
{
left = j;
right = j;
while(left >= 0 && right < len && A[left] == A[right])
{
left--;
right++;
}
retlen = max(retlen ,right - left - 1);
}
return retlen ;
}
};
After reading the question, we know that for a group of stocks, the buying and selling mechanism can only be bought and sold once, so as to obtain the highest profit. If it is a loss no matter when buying and selling, no matter how much the loss is, that is, there is no profit, then output 0. Then, the basic idea is to enumerate/brute force method, find the profit difference of each group, and return the maximum value. After trying, it is found that the two layers of for will time out, and this problem is limited to 1ms to solve. Therefore, it is necessary to optimize based on the brute force method, so the brute force method is also written. Then, based on the brute force method, backtracking is repeated too many times, and optimization is performed. Thinking and finding that if we reverse the thinking, first consider the value of selling, then we only need to obtain the minimum value before the selling point, and the difference obtained is the maximum difference, that is, only one traversal is needed. The next step is program implementation.
First, according to the brute force method, we can enumerate all the cases in turn and find the maximum difference output. This problem will time out. So we need to optimize it.
#include <iostream>
using namespace std;
const int N = 1e5 +10;
int arr[N];
int main()
{
int n;
cin >> n;
for(int i = 0;i < n;i++)
cin >> arr[i];
int maxval = 0;
for(int i = 0;i < n; i++)
{
for(int j = i;j < n;j++)
{
maxval = max(maxval , arr[j]- arr[i]);
}
}
cout << maxval << endl;
return 0;
}
Based on the above brute force method, optimization is performed. For the sake of comprehensive understanding, a demonstration diagram is drawn according to the analysis of ideas:
Then, to implement the program, write the input as required, and then define minval to initialize arr[0] as the assumed minimum value for traversal, comparison and update. Then define maxSub to represent the maximum difference between minval and position i when traversing. It is worth noting that when traversing, pay attention to the order of minval and maxSub, and first find the minimum value minval and then find maxSub.
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n = 0;
cin >> n;
vector<int> arr(n);
int m = 0;
while(n--)
{
cin >> arr[m];
m++;
}
int minval = arr[0];
int submax = 0;
for(int i = 0;i<arr.size();i++)
{
minval = min(arr[i],minval);
submax = max(submax, arr[i] - minval);
}
cout << submax << endl;
return 0;
}
After reading the question, we know that we need to find the maximum number of paths that can be walked from point A to point B according to certain rules. To analyze the question, we need to know that according to certain rules, we can walk to the right or down, which brings up the idea of dynamic programming dp. Then we also need to pay attention to the question that the control point of the knight cannot be walked (visited), that is, the point designed by the oblique "sun" that the knight walks on the coordinates in chess, and the starting point of the knight is called the control point. Among them, the knight is a fixed point (x, y) given at the beginning, and the question also gives the relationship between the knight's jumping point and the knight's starting point. In addition, it should be noted that according to the example and the chessboard, the size of the chessboard is (n+1)(m+1)。
Therefore, after summarizing the above, we can conclude that:
(1) Dynamic programming DP ideas can be used to solve the problem;
(2) The horse’s control points include not only the oblique “sun” but also its own starting position;
(3) The size of the chessboard is (n+1)(m+1).
So after analyzing the points to note, we return to the DP state representation and state transfer equation of dynamic programming;
According to the walking rules of the question, define the dp[i][j] state to represent: how many paths there are at most to reach this position;
Derive the state transfer equation: dp[i][j] = d[i][j-1] + d[i-1][j];
In addition, please note that if the starting position of point B coincides with the starting position of the horse or the control point, and the top and left of point B are all blocked, that is, the control point, then in the above extreme cases, dp[i][j] = 0; then the next step is program implementation.
First, write the input according to the analysis of the idea, define and open up the dp array (two pitfalls will be mentioned later), and according to the size of the chessboard, in order to describe the coordinates uniformly, an extra row and column are opened here, so x and y need to map the coordinates += 1, and then explore the initialization problem of dp, and draw a picture to make it clearer:
Next, the actual two-dimensional array is traversed from [1, n+1] and [1, m+1], and the processing of extreme cases is constantly judged, and finally dp[n+1][m+1] is output. At this point, the idea is correct, and the steps are summarized as follows:
(1) Map x and y coordinates;
(2) According to the (open one more layer) array definition, either dp[0][1] = 1 or dp[1][0] = 1 is OK;
(3) Traverse the two-bit array, paying attention to the boundary control from [1, n+1] and [1, m+1];
a. Determine extreme situations: 1. The horse's control point blocks the path 2. Overlap problem;
b. Normal execution state transfer equation: dp[i][j] = d[i][j-1] + d[i-1][j];
(4) Finally, output dp[n+1][m+1].
In addition, the two pitfalls mentioned above are that after I wrote it, the submission failed because the data was out of range, so it is best to use long long to open the array. Another pitfall is that the size range of the array is opened because of the use of multiple layers, so it must be at least greater than or equal to 22. Previously, using dp[21][21] could not pass all use cases.
#include <iostream>
using namespace std;
long long dp[22][22];
int main()
{
int n,m,x,y;
cin >> n >> m >> x >> y;
//映射坐标
x += 1;
y += 1;
//初始化
dp[0][1] = 1;
//遍历
for(int i = 1;i <= n+1; i++)
{
for(int j = 1;j <= m+1; j++)
{
//极端情况的处理: 1.马控制点 2.自身重合
if((i != x && j != y && abs(i - x) + abs(j - y) == 3) || (i == x && j == y))
{
dp[i][j] = 0;
}
else
{
dp[i][j] = dp[i][j-1] + dp[i-1][j];
}
}
}
cout << dp[n+1][m+1] << endl;
return 0;
}
Longest palindrome substring
The best time to buy and sell stocks (I)
[NOIP2002 Popularization Group] Crossing the River