2020华为软挑总结

一、热身赛

编程闯关：

用户贷款风险预测。要求参赛者建立准确的风控模型，预测用户是否会逾期还款。

评价标准：

速度为王，只要速度够快，准确率可以忽略不计。

问题分析

二分类问题：采用logistic回归算法对用户类型进行分类。
在此分类算法上依次采用L2正则化、影子滑动平均、学习衰减率、随机梯度下降、自适应梯度下降等优化策略。以提高收敛速度，保证泛化能力。
最终结果:不堪入目。

二、初赛

问题描述

通过金融风控的资金流水分析，可有效识别循环转账，辅助公安挖掘洗钱组织，帮助银行预防信用卡诈骗。基于给定的资金流水，检测并输出指定约束条件的所有循环转账。

评价标准：

在保证准确率的基础之上，速度为王！
结果一定要100%正确，否则无法参与评分。

问题分析

在有向图结构中找出所有长度在[3,7]的简单环，并按规则输出。详细规则 gitee链接-coding记录 中有记录。

思路一：

采用vector储存所有顶点信息，list存储所有边结构信息。采用 深度优先搜索+破环边结构 的方法搜索所有简单环。在官方给的56环数据中，该思路能正确运行；但在线上运行失败。故此路不通。

思路二：

先采用tarjan算法找出图中所有强连通子图；其后在各强连通子图采用johnson算法中寻找所有简单环。
此算法适用于强连通子图比较多的图结构。大赛线上表现一般。
推荐一位小哥的视频，该视频很好地讲诉了该算法的思路。
johnson找环算法视频

思路三：

暴力找环法。依次针对每个节点递归7层结构，只找以此节点为开头的环。该法能确保结果正确，但存在大量重复查找的过程。

针对思路三的提速：

提速一：改变图的存储结构，使用二维数组储存邻接表结构的图，提高访问速度。针对文件的输入，有两种方式。
一种是有序的图结构（按id大小排序）：采用set记录所有顶点，并按顶点id大小排序。采用unordered_multimap储存所有边结构。采用unordered_map绑定顶点id与索引号。最终使得图结构按 ID升序排列。顶点ID+边顶点索引号。
一种是无序结构：采用unordered_map绑定顶点与其索引号，将边结构顶点的索引号（按查找的方式，从unordered_map对象中获得。 顶点ID顺序与其添加顺序有关。顶点ID+边顶点索引号。
提速二：每个起始结点只找比自己id号大的环结构，这样可保证输出的排序规则。
提速三：采用四线程，将数据分成4部分分别查找，最终将所有结果综合排序。

//定义一个计时器类
class Timer
{
public:Timer() : beg_(clock_::now()) {}void reset() { beg_ = clock_::now(); }double elapsed() const {return std::chrono::duration_cast<second_>(clock_::now() - beg_).count();}void out(std::string message = "") {double t = elapsed();std::cout << message << " elasped time:" << t << "s" << std::endl;reset();}
private:typedef std::chrono::high_resolution_clock clock_;typedef std::chrono::duration<double, std::ratio<1> > second_;std::chrono::time_point<clock_> beg_;
};Timer t;
t.out("Tatal");//开启线程的两种方式
#include
#include
//#include
#include//多线程找环//std::future m1 = std::async(FFCC1, std::ref(g)); //线程一//std::thread t1(FFCC1, std::ref(g)); //线程一//std::thread t2(FFCC2, std::ref(g)); //线程二//std::thread t3(FFCC3, std::ref(g)); //线程三std::future <void> m1 = std::async(FFCC1, std::ref(g)); //线程一std::future <void> m2 = std::async(FFCC2, std::ref(g)); //线程一std::future <void> m3 = std::async(FFCC3, std::ref(g)); //线程一g.FC(); //主线程m1.wait();//线程一m2.wait();//线程一m3.wait();//线程一//t1.join(); //线程一//t2.join(); //线程二//t3.join(); //线程三

提速四：一个剪枝的方法。递归消除所有出度为0的结点。

最终结果：