C++笔试强训day10

目录

1.最长回文字符串

2.买卖股票的最好时机(一)

3.过河卒

---

1.最长回文字符串

链接

一开始没认真看题目，直到提交了好几遍没过还是没去检查题目，一直检查代码逻辑，哎呦，难受了。

我以为是收尾字母相同就行了。

错误代码：

#include <algorithm>
class Solution {
public:
	int getLongestPalindrome(string A) {
		if (A.size() == 1 || A.size() == 0)
			return A.size();
		int len = 0;
		int r = A.size() - 1;
		for (int i = r; i >= 0; --i) {
			for (int j = 0; j <= r; ++j) {
				if (A[i] == A[j]) {
					int newlen = i - j + 1;
					len = max(len, newlen);
					break;
				}
			}
		}
		return len;
	}
};

正解：

双指针往该数的两边同时走，然后一直更新len就好了。

核心代码：

        for (int i = 1; i < A.size(); ++i) {
            l = i - 1;
            r = i + 1;
            while (l >= 0 && r < n) {
                if (A[l] == A[r]) {
                    l--;
                    r++;
                }
                else {
                    break;
                }
            }
            len = max(len, r - l - 1);

细节：不确定是不是两数连一起相同，比如ababa 和 abaabc。

如果只用上述核心代码的话，就不能准确的计算出abaabc的长度了，因为他只是比他的前后。

要添加一个本身也计算的核心：

        for (int i = 1; i < A.size(); ++i) {
            l = i - 1;
            r = i + 1;
            while (l >= 0 && r < n) {
                if (A[l] == A[r]) {
                    l--;
                    r++;
                }
                else {
                    break;
                }
            }
            len = max(len, r - l - 1);
 
            l = i - 1;
            r = i;
            while (l >= 0 && r < n) {
                if (A[l] == A[r]) {
                    l--;
                    r++;
                }
                else {
                    break;
                }
            }
            len = max(len, r - l - 1);

这样就能保证另一种也能过。

详细代码：

class Solution {
public:
    int getLongestPalindrome(string A) {
        int n = A.size();
        if (n < 2) {
            return n;
        }
 
        int len = 0;
        int l, r;
        for (int i = 1; i < A.size(); ++i) {
            l = i - 1;
            r = i + 1;
            while (l >= 0 && r < n) {
                if (A[l] == A[r]) {
                    l--;
                    r++;
                }
                else {
                    break;
                }
            }
            len = max(len, r - l - 1);
 
            l = i - 1;
            r = i;
            while (l >= 0 && r < n) {
                if (A[l] == A[r]) {
                    l--;
                    r++;
                }
                else {
                    break;
                }
            }
            len = max(len, r - l - 1);
        }
        return len;
    }
};

2.买卖股票的最好时机(一)

链接

我的一开始的解法是用队列存储一个pair<int, int>一个存值，一个存下标。

然后暴力枚举每个组合，最后肯定是超时了。

正解就是一边遍历数组，一边更新下标 i 之前的最小值Min，同时更新总值sum。

详细代码：

#include <iostream>
#include <vector>
using namespace std;
 
int sum = 0;
 
int main() {
    int n;
    cin >> n;
 
    vector<int> v(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> v[i];
    }
 
    int Min = v[0];
    for (int i = 1; i < n; ++i)
    {
        if (v[i] - Min > sum)
        {
            sum = v[i] - Min;
        }
        Min = min(Min, v[i]);
    }
 
    cout << sum << endl;
    return 0;
}

3.过河卒

链接

一道线性加约束条件dp问题。

细节：x1 ！= x，y2 ！= y，dp数组的初始化

处理好这些细节之后，解题就不容易出错。

详细代码：（我这里是将所有坐标挪动了1位，即起点在1，1；所以马的位置x，y也都要+=上一个数字1）

#include <iostream>
using namespace std;
 
int n, m, x, y; 
long long dp[30][30];
int main() 
{
    cin >> n >> m >> x >> y;
 
    x++, y++;
    dp[0][1] = 1;
    for(int i = 1; i <= n + 1; i++)
    {
        for(int j = 1; j <= m + 1; j++)
        {
            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 - 1][j] + dp[i][j - 1];
        }
    }
    cout << dp[n + 1][m + 1] << endl;
}