滴滴 算法 821笔试
第一题 蛇形输出斐波那契数列 100%
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
bool inarea(int i , int j , vector<vector<long>>&res)
{
return i >= 0 && i < res.size() && j >= 0 && j < res[0].size();
}
int main()
{
int n; cin >> n;
if(n == 1)
{
cout << 1 << endl;
return 0;
}
vector<vector<long>>res(n,vector<long>(n,0));
vector<long>dp(n * n,0);
dp[0] = 1; dp[1] = 1;
for(int i = 2; i < n * n; i++)
{
dp[i] = dp[i-1] + dp[i-2];
}
int count = n * n - 1;
int i = 0, j = -1;
vector<pair<int,int>>dir;
dir.push_back({0,1});dir.push_back({1,0});dir.push_back({0,-1});dir.push_back({-1,0});
int cur = 0;
while(count >= 0)
{
while(1)
{
if(inarea(i+dir[cur].first,j+dir[cur].second,res) && res[i+dir[cur].first][j+dir[cur].second] == 0)
{
i += dir[cur].first;
j += dir[cur].second;
res[i][j] = dp[count];
break;
}
else
{
cur++;
cur = cur % 4;
}
}
count --;
}
for(auto i : res)
{
for(auto j : i)
{
cout << j << " ";
}
cout << endl;
}
return 0;
} 第二题 找CHINA个数 91% 最后突然意识到问题出在visit数组上，比如A在前一次遍历之后，下一个路径结束位点A可能和上一个相同，visit标记过的化会导致少计数一次 #include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
int res = 0;
string target = "CHINA";
bool inarea(vector<vector<char>>&num,int i, int j)
{
return i >= 0 && i < num.size() && j >= 0 && j < num[0].size();
}
void dfs(vector<vector<char>>&num, int i, int j,vector<vector<char>>&visit,int index)
{
if(!inarea(num,i,j)) return ;
if(index == 4 && num[i][j] == target[index])
{
res++;
return;
}
if(visit[i][j] == true) return;
visit[i][j] = true;
if(num[i][j] == target[index])
{
dfs(num,i,j+1,visit,index+1);
dfs(num,i+1,j,visit,index+1);
dfs(num,i,j-1,visit,index+1);
dfs(num,i-1,j,visit,index+1);
}
}
int main()
{
int n;
cin >> n;
vector<vector<char>>num(n,vector<char>(n,'-1'));
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
cin >> num[i][j];
}
}
for(int i = 0; i < n;i++)
{
for(int j = 0; j < n; j++)
{
vector<vector<char>>visit(n,vector<char>(n,false));
dfs(num,i,j,visit,0);
}
}
cout << res;
}
