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

【C++】0314算法阿里笔试题「建议收藏」一、题目二、自己的dfs的题解#include<bits/stdc++.h>usingnamespacestd;intres3=INT_MAX;inttransfet(vector<string>&tmp){intsum=0;for(auto&t:tmp){sum+=stoi(t);}returnsum;}voiddfs(stringstr,vector&l

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一、题目在这里插入图片描述

二、 自己的dfs的题解

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

#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算法岗)

#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;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/195833.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 樱桃键盘 Cherry 键盘 windows键 无效 没反应

    樱桃键盘 Cherry 键盘 windows键 无效 没反应FUN+F9解锁,这是为了防止误触把几个键给锁定了。

  • GridView使用RenderControl取得HTML的问题[通俗易懂]

    GridView使用RenderControl取得HTML的问题[通俗易懂]
    如果想在CodeFile中取得GridView结果的HTML内容,首先会遇到这样的错误讯息:
     型别’GridView’的控制项’GridView1’必须置于有runat=server的表单标记之中。
    这个问题,可以在您的CodeFile中加入以下这段来解决Public Overrides Sub VerifyRenderingInServerForm(ByVal control As Control)      ‘处理’GridView’的控制项’GridView’必须置

  • Spring Cloud Security 整合 OAuth 2.0,从原理到实战一次说明白

    Spring Cloud Security 整合 OAuth 2.0,从原理到实战一次说明白若有收获,请记得分享和转发哦本篇文章介绍一下OAuth2.0相关的知识点,并且手把手带大家搭建一个认证授权中心、资源服务进行OAuth2.0四种授权模式的验证,案例源码详细,一梭子带大家了…

  • [分享]Ubuntu12.04安装基础教程(图文)

    [分享]Ubuntu12.04安装基础教程(图文)

  • USB流量分析「建议收藏」

    USB流量分析「建议收藏」1.USB接口简介通过监听USB接口流量,可获取键盘击键,鼠标移动与点击,存储设备的明文传输通信,USB无线网卡网络传输内容等。2.题目wireshark打开数据包后发现为usb协议USB协议数据部分在LeftoverCaptureData域中,使用tshark命令将其单独提取出来tshark-rudn.pcapng-Tfields-eusb.capdata>us

  • 浅谈安卓UI设计「建议收藏」

    浅谈安卓UI设计「建议收藏」用户界面在程序开发中十分重要,一个好的用户界面设计需要考虑到用户使用体验、是否美观方便等。在界面设计的过程中,需要考虑如何制作出UI界面,怎么样控制UI界面两大块。这里先放上之前我们UI作业的截图:本文主要介绍通过两种方式来进行界面设计:1、通过xml文件进行界面设计2、通过代码控制进行界面设计一、…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号