【C++】0314算法阿里笔试题「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。

一、题目

二、自己的dfs的题解

我并没有参加这个笔试，这种方法应该A不了所有用例，有什么错误的地方恳请指导指导(*￣︶￣) respect

代码语言：javascript复制

#include <bits/stdc  .h>
using namespace std;
int res3=INT_MAX;
int transfet(vector<string> &tmp) { 

int sum=0;
for (auto &t: tmp) { 

sum  = stoi(t);
}
return sum;
}
void dfs(string str, vector<string> &tmp, int start, int nums, int k) { 

if (start==str.size()) { 
 //str.size()==0
if (!(transfet(tmp)%k)) { 

res3 = min(res3, nums-1);
return;
}
else return;
}
for (int i=start; i<str.size(); i  ) { 

int end = i;
tmp.emplace_back(str.substr(start ,end-start 1));
bfs(str, tmp, end 1, nums 1, k);
tmp.pop_back();
}
}
int leastNum(string str, int k) { 
  
vector<string> tmp;
dfs(str, tmp, 0, 0, k);
return res3;
}
int main(int argc, char* argv[])
{ 

vector<string> a = { 
"1","34","567"};
cout<<transfet(a)<<endl;
string s = "1231";
cout<<"最小的次数："<<leastNum(s, 5)<<endl; // 结果为2
}

在牛客上看到的大佬的DP做法，如下： 其余的题目信息见：阿里笔试(0314算法岗)

代码语言：javascript复制

#include<bits/stdc  .h>
using namespace std;
typedef long long ll;
vector<int> gao(ll n, int k) { 

string s = to_string(n);
vector<vector<int>> dp(s.size() 1, vector<int>(k, 0x3f3f3f3f));
dp[0][0] = 0;
for (int i = 0; i < s.size(); i  ) { 

int cur = 0;
for (int j = i; j < s.size(); j  ) { 

cur = (cur * 10   s[j]-'0')%k;
for (int x = 0; x < k; x  ) { 

dp[j 1][(cur x)%k] = min(dp[j 1][(cur x)%k] , dp[i][x] (i!=0));
}
}
}
return dp.back();
}
int main() { 

int n, k; cin >> n >> k;
vector<ll> A(n); for (auto &x: A) cin >> x;
vector<int> cur(k, 0x3f3f3f3f);
cur[0] = 0;
for (auto &t: A) { 

vector<int> nxt(k, 0x3f3f3f3f);
vector<int> tmp = gao(t, k);
for (int i = 0; i < k; i  ) { 

for (int j = 0; j < k; j  ) nxt[(i j)%k] = min(nxt[(i j)%k], cur[i] tmp[j]); 
}
cur = nxt;
}
cout << cur[0] << endl;
}

dfs dp

0 人点赞

【C++】0314算法阿里笔试题「建议收藏」

一、题目

二、 自己的dfs的题解

二、自己的dfs的题解