阿里巴巴2021年春招机器学习实习岗(运筹优化)笔试

本文主要是介绍阿里巴巴2021年春招机器学习实习岗(运筹优化)笔试，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 第一题
- - - 1.1 题目介绍
    - 1.2 题目条件
    - 1.3 我的思路
    - 1.4 代码
- 第二题

第一题

1.1 题目介绍

牛牛有一串混合数字和字母的密码，目前大意的牛牛忘记了密码，只知道密码的位数为m >= 3，以及他在键盘上的常用键数量为n >= 3，常用键中包含牛牛的密码。已知牛牛的密码中的数字至少有1位，字母至少有2位，假设题目所给输入一定满足上述条件，存在可行解，请设计算法找到牛牛密码的所有可能，每个可能的密码字符串中不能包含重复字符，且需按ASCII码升序排列打印

【Input 1】

3 4
k n 9 6

【Output 1】

6kn
9kn

说明，密码一共有3位，常用键数量为4，至少有1个数字和2个字符且升序排列无重复，那只有6kn和9kn

【Input 2】

3 6
n k n 9 6 9

【Output 2】

6kn
9kn

1.2 题目条件

输出的密码位数为m
数字个数>= 1
字母个数>= 2
密码中所有字符升序排列 (eg.6kn)
密码中不能包含重复字符 (eg.不能有6aa)
输出的密码组合不能有重复

1.3 我的思路

考虑到输入的字符串是乱序，需要先对字符串来一波升序排序（字符串内部升序 + 分离数字和字母 + 重复元素相邻）
然后将数字和字母分离，由于字母的ASCII比数字大，这里我选择直接找到字母的第一个索引来实现
分别对数字字符串和字母字符串进行回溯法，存储其子集组合，由于之前升序使重复元素相邻，直接通过str[i] == str[i - 1]跳过重复即可
两层for训练打印两个子集组合的所有组合，需过滤总长不等于m的字符串

如果有更好的思路，欢迎大佬前来拍砖~

1.4 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;string path = "";
vector<string> numvec;
vector<string> strvec;void backtrack(vector<string>& solution, string str, int lessLen, int first) {if (path.size() >= lessLen) solution.emplace_back(path);// 由于求子集组合，所以此处没有returnfor (int i = first; i < str.size(); i++) {if (i > 0 && str[i] == str[i - 1]) continue;path += str[i];backtrack(solution, str, lessLen, i + 1);path = path.substr(0, path.size() - 1);}
}int main() {int m, n;cin >> m; // 3cin >> n; // 4string mima = "";  // "69kn"for (int i = 0; i < n; i++) {char ch;cin >> ch;mima += ch;}// 1.升序排序sort(mima.begin(), mima.end());// 找到数字和字母边界，将两者分开int chidx = 0;for (int i = 0; i < mima.size(); i++) if (mima[i] > '9') {chidx = i;break;}vector<string> numvec, strvec;// 2. 数字密码回溯得子集组合结果(len > 1)backtrack(numvec, mima.substr(0, chidx), 1, 0);path.clear();// 3. 字符密码回溯得子集组合结果(len > 2)backtrack(strvec, mima.substr(chidx, mima.size() - chidx), 2, 0);// 打印结果for (int i = 0; i < numvec.size(); i++) for (int j = 0; j < strvec.size(); j++) {// 拼接数字字符串 + 字母字符串string str = numvec[i] + strvec[j];// 过滤总长不等于m的字符串if (str.size() == m) cout << str << endl;}return 0;
}