目录
1、过河卒
dfs
bfs
动态规划
2、扑克牌顺子
排序 + 模拟
找规律
3、最长回文子串
中心拓展法
1、过河卒
5493. 过河卒 - AcWing题库
这道题我们很容易就能够想到dfs或bfs，但这两种算法都是会超时的
dfs
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 25;
int a[N][N], n, m, x, y;
int dx[2] = {1, 0}, dy[2] = {0, 1};
void dfs(vector<pair<int, int>>& v, int& res, int x, int y)
{
if(x == n && y == m) res ++;
auto it = find(v.begin(), v.end(), make_pair(x, y));
if(it != v.end()) return ; // 当前的x和y在马或马能跳到的点上
// 当前位置是合法的
for(int i = 0;i < 2;i ++)
{
int a = x + dx[i], b = y + dy[i];
if(a >= 0 && a <= n && b >= 0 && b <= m)
{
dfs(v, res, a, b);
}
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m >> x >> y;
// 需要知道马能跳跃到的点，看这8个点是否在方格中即可
vector<pair<int, int>> v;
v.push_back({x, y});
if(x - 2 >= 0 && y - 1 >= 0) v.push_back({x - 2, y - 1});
if(x - 1 >= 0 && y - 2 >= 0) v.push_back({x - 1, y - 2});
if(x - 2 >= 0 && y + 1 <= m) v.push_back({x - 2, y + 1});
if(x - 1 >= 0 && y + 2 <= m) v.push_back({x - 1, y + 2});
if(x + 1 <= n && y + 2 <= m) v.push_back({x + 1, y + 2});
if(x + 2 <= n && y + 1 <= m) v.push_back({x + 2, y + 1});
if(x + 2 <= n && y - 1 >= 0) v.push_back({x + 2, y - 1});
if(x + 1 <= n && y - 2 >= 0) v.push_back({x + 1, y - 2});
int res = 0;
dfs(v, res, 0, 0);
cout << res << endl;
return 0;
}bfs
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 25;
int a[N][N], n, m, x, y;
int dx[2] = {1, 0}, dy[2] = {0, 1};
int bfs(vector<pair<int, int>>& v, int x, int y)
{
auto it = find(v.begin(), v.end(), make_pair(x, y));
if(it != v.end()) return 0;
queue<pair<int, int>> q;
q.push({x, y});
int res = 0;
while(!q.empty())
{
int t = q.front().first, p = q.front().second;
q.pop();
if(t == n && p == m) res ++;
else
{
for(int i = 0;i < 2;i ++)
{
int a = t + dx[i], b = p + dy[i];
auto it = find(v.begin(), v.end(), make_pair(a, b));
if(a >= 0 && a <= n && b >= 0 && b <= m && it == v.end())
q.push({a, b});
}
}
}
return res;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m >> x >> y;
// 需要知道马能跳跃到的点，看这8个点是否在方格中即可
vector<pair<int, int>> v;
v.push_back({x, y});
if(x - 2 >= 0 && y - 1 >= 0) v.push_back({x - 2, y - 1});
if(x - 1 >= 0 && y - 2 >= 0) v.push_back({x - 1, y - 2});
if(x - 2 >= 0 && y + 1 <= m) v.push_back({x - 2, y + 1});
if(x - 1 >= 0 && y + 2 <= m) v.push_back({x - 1, y + 2});
if(x + 1 <= n && y + 2 <= m) v.push_back({x + 1, y + 2});
if(x + 2 <= n && y + 1 <= m) v.push_back({x + 2, y + 1});
if(x + 2 <= n && y - 1 >= 0) v.push_back({x + 2, y - 1});
if(x + 1 <= n && y - 2 >= 0) v.push_back({x + 1, y - 2});
cout << bfs(v, 0, 0) << endl;
return 0;
}动态规划
真正要解决这道题，需要使用动态规划
我们先看看没有马时，从A点走到B点的路线数有几条
我们会发现第一行和第一列上的位置，到达这个位置的路线条数永远只有1条。其余位置到达这个位置的路线条数等于上边的点和左边的点的路线条数之和。
我们现在将马加入
此时第一行和第一列上的位置到达的路线数就不都是1条了，因为马所在位置和马经过一步跳跃能到达的位置都是不能到达的，所以我们直接让这些位置的路线数都是0，我们就会发现，第一行和第一列上的位置到达的路线数等于前一个位置的路线数。其余位置仍然等于上边的点和左边的点的路线条数之和。
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 25;
ll f[N][N];
int n, m, x, y;
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m >> x >> y;
// 先将所有位置初始化为1，再将马所在的点以及马能够到达的点赋值为0，以此区分
for(int i = 0;i <= n;i ++)
for(int j = 0;j <= m;j ++) f[i][j] = 1;
f[x][y] = 0;
if(x - 2 >= 0 && y - 1 >= 0) f[x - 2][y - 1] = 0;
if(x - 1 >= 0 && y - 2 >= 0) f[x - 1][y - 2] = 0;
if(x - 2 >= 0 && y + 1 <= m) f[x - 2][y + 1] = 0;
if(x - 1 >= 0 && y + 2 <= m) f[x - 1][y + 2] = 0;
if(x + 1 <= n && y + 2 <= m) f[x + 1][y + 2] = 0;
if(x + 2 <= n && y + 1 <= m) f[x + 2][y + 1] = 0;
if(x + 2 <= n && y - 1 >= 0) f[x + 2][y - 1] = 0;
if(x + 1 <= n && y - 2 >= 0) f[x + 1][y - 2] = 0;
for(int i = 0;i <= n;i ++)
for(int j = 0;j <= m;j ++)
{
if(i == 0 && j == 0) continue; // 起点不需要修改
if(f[i][j] == 0) continue; // 马能到达的点不能走
if(i == 0) f[i][j] = f[i][j - 1]; // 第一行
else if(j == 0) f[i][j] = f[i - 1][j]; // 第一列
else f[i][j] = f[i - 1][j] + f[i][j - 1]; // 其余位置
}
cout << f[n][m] << endl;
return 0;
}并且由于数据过大，还需要使用long long
2、扑克牌顺子
扑克牌顺子_牛客题霸_牛客网
排序 + 模拟
可以先将数组排为升序，然后计算出这个数组中0的个数，接着从不是0的位置开始，判断每个位置与后一个位置之间，需要几个数才能保证这个连续，用0的个数减去这个数，最终看存储0的个数的变量，若大于等于0，返回true，若小于0，返回false
class Solution {
public:
bool IsContinuous(vector<int>& numbers) {
sort(numbers.begin(), numbers.end());
int zeros = 0;
for(int i = 0;i < numbers.size();i ++)
if(numbers[i] == 0) zeros ++;
if(zeros == 4) return true;
for(int i = zeros;i < numbers.size() - 1;i ++)
{
if(numbers[i] == numbers[i + 1]) return false;
zeros = zeros - (numbers[i + 1] - numbers[i] -1);
}
if(zeros >= 0) return true;
else return false;
}
};找规律
我们会发现，如果能构成顺子的话，会满足以下两个条件：
1、不会出现重复元素
2、max - min <= 4
class Solution {
bool hash[14] = {0};
public:
bool IsContinuous(vector<int>& numbers) {
int maxVal = 0, minVal = 14;
for(auto x : numbers)
{
if(x)
{
if(hash[x]) return false;
hash[x] = true;
maxVal = max(maxVal, x);
minVal = min(minVal, x);
}
}
return maxVal - minVal <= 4;
}
};3、最长回文子串
1524. 最长回文子串 - AcWing题库
这里顺便说一下子串和子序列的区别：
子串：原始字符串中的一个连续子串
子序列：原始字符串的一个子集
中心拓展法
我们可以枚举字符串中所有的点，并以这些点为中心，向两边扩散，直到扩散到超出字符串范围或者两个新加入的元素的值不相等时。此时要注意，对于回文子串可以是奇数，也可以是偶数，所以我们在由中心向两边扩展时，需要同时考虑两种情况。
#include<iostream>
#include<string>
using namespace std;
int main()
{
string s;
getline(cin, s);
int max_len = 0;
for(int i = 0;i < s.size();i ++)
{
int l = i, r = i;
while(l >= 0 && r < s.size() && s[l] == s[r])
{
if(r - l + 1 > max_len) max_len = r - l + 1;
l --, r ++;
}
l = i, r = i + 1;
while(l >= 0 && r < s.size() && s[l] == s[r])
{
if(r - l + 1 > max_len) max_len = r - l + 1;
l --, r ++;
}
}
cout << max_len << endl;
return 0;
}时间复杂度是O(n^2)，空间复杂度是O(1)
