准备秋招（二）

一、笔试强训1. 数字统计题目链接数字统计_牛客题霸_牛客网算法思想枚举每个数后对数字通过 %10/10 进行位数拆分然后判断是否符合条件。考查知识数学 模拟C实现#include iostream using namespace std; int main() { int l, r; cin l r; int ret 0; for(int i l; i r; i) { int tmp i; while(tmp) { if(tmp % 10 2) ret; tmp / 10; } } cout ret endl; }2. 两个数组的交集题目链接两个数组的交集_牛客题霸_牛客网算法思想由于需要快速判断某些数据中是否存在期望数据联想到哈希表。但是因为hash这种容器在引入的时候时间开销比较大针对本题来说所以我们采用布尔类型数组来模拟hash容器。通过将数组一装入“哈希表”然后对数组二进行枚举判断来完成要求。考查知识哈希Tips根据题意交集中出现多个重复数字时只输出一个数字通过对模拟哈希表置false解决。C实现class Solution { bool hash[1024] { 0 }; public: vectorint intersection(vectorint nums1, vectorint nums2) { vectorint ret; for(auto x : nums1) { hash[x] true; } for(auto x : nums2) { if(hash[x]) { ret.push_back(x); hash[x] false; } } return ret; } };3. 点击消除题目链接点击消除_牛客题霸_牛客网算法思想通过相邻匹配消除的思想联想到栈这种数据结构。为了方便我们使用string来模拟栈因为string的尾插尾删就能模拟栈的特性且方便直接输出。准备两个string类型变量其中一个作为目标结果通过向目标string依次“入栈”和消除相邻元素就能完成题目要求。考查知识栈C实现#include iostream #include string using namespace std; int main() { string s, st; cin s; for(auto ch : s) { if(st.back() ch) st.pop_back(); else st ch; } cout (st.size() 0 ? 0 : st) endl; }4. 牛牛的快递题目链接牛牛的快递_牛客题霸_牛客网算法思想根据题目要求模拟即可在上取整的时候可以通过库函数ceil也可以通过if语句的判断来实现。考查知识模拟C实现#include iostream #include cmath using namespace std; int main() { double a; char b; cin a b; int ret 0; if(a 1) { ret 20; } else { ret 20; a - 1; ret ceil(a); //double c a - 1; //if(c - (int)c 0) ret (int)c 1; //else ret (int)c; } if(b y) ret 5; cout ret endl; return 0; }5. 最小花费爬楼梯题目链接最小花费爬楼梯_牛客题霸_牛客网算法思想按照动态规划的步骤来分析——1、状态表示 2、状态转移方程 3、初始化 4、填表顺序5、返回值。本题的状态转移方程是dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2])考察知识动态规划 - 线性dpC实现#include iostream using namespace std; const int N 1e5 10; int n; int cost[N]; int dp[N]; int main() { cin n; for(int i 0; i n; i) cin cost[i]; for(int i 2; i n; i) { dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]); } cout dp[n] endl; return 0; }