牛客网华为机试
上篇：算法|牛客网华为机试41-52C++
文章目录
- HJ53 杨辉三角的变形
- HJ54 表达式求值
- HJ55 挑7
- HJ56 完全数计算
- HJ57 高精度整数加法
- HJ58 输入n个整数，输出其中最小的k个
- HJ59 找出字符串中第一个只出现一次的字符
- HJ60 查找组成一个偶数最接近的两个素数
- HJ61 放苹果
- HJ62 查找输入整数二进制中1的个数
HJ53 杨辉三角的变形
题目描述：
解题思路：
写几行就可以发现规律：
n1或2时，没有偶数，cout<<-1;
n3时，index=2;
n4,index=3;
n5,index=2;
n6,index=4;
n7,index=2;
n8,index=3;
n9,index=2;
n10,index=4;
…
可以发现，index=2,3,2,4重复出现，将n对4取余，可以发现如下规律：
n%43||n%41,index2;
n%40,index=3;
n%42,index=4;
解法：
#include<iostream>
using namespace std;
int main()
{
int n;
while(cin>>n)
{
if(n==1||n==2)
{
cout<<-1<<endl;
}
else if(n%4==3||n%4==1)
{
cout<<2<<endl;
}
else if(n%4==0)
{
cout<<3<<endl;
}
else
{
cout<<4<<endl;
}
}
return 0;
}
HJ54 表达式求值
题目描述：
解题思路：
题解 | #表达式求值#
解法：
#include <iostream>
#include <vector>
using namespace std;
int compute(string& s,int left,int right){
char op = '+';//默认加开始
int num = 0;
vector<int> st;
for(int i = left; i <= right;i++){
if(isdigit(s[i])) // 数字
num = num * 10 + s[i] - '0';//计算该部分数字总和
if(s[i] == '('){ //进入左括号
int layer = 0; //统计左括号层数
int j = i;
while (j <= right) {//遍历到右边
if(s[j]=='(')
layer++;//遇到左括号，层数累加
else if (s[j] == ')') {
layer--;//遇到右括号层数递减
if (layer == 0) {
break;
}
}
j++;
}
num = compute(s, i+1, j-1);//递归计算括号中的部分
i = j + 1;
}
if (!isdigit(s[i]) || i == right) {//遇到运算符或者结尾
switch (op) {//根据运算符开始计算
case '+':st.push_back(num); break;//加法加入到末尾
case '-':st.push_back(-num); break;
case '*':st.back()*=num; break;
case '/':st.back()/=num; break;
}
op = s[i]; //修改为下一次的运算符
num = 0;
}
}
int res = 0;
for(int x:st)
res+=x;
return res;
}
int main() {
string s;
while (cin >> s) { // 注意 while 处理多个 case
cout << compute(s, 0, s.length() - 1) << endl;
}
return 0;
}
HJ55 挑7
题目描述：
解题思路：
写一个判断函数
核心就是取余、除以
解法：
#include <iostream>
using namespace std;
bool isSev(int num){
while (num>0) {
if(num % 10 == 7){
return true;
}
num /= 10;
}
return false;
}
int main() {
int n;
while (cin >> n) { // 注意 while 处理多个 case
int ans = 0;
for(int i = 1;i <= n; ++i){
if(i % 7 == 0){
ans++;
continue;
}
if(isSev(i)){
ans++;
}
}
cout<<ans<<endl;
}
return 0;
}
HJ56 完全数计算
题目描述：
解题思路：
#include <numeric> 是C++中的一个预处理指令，用于包含标准库中的 <numeric> 头文件。这个头文件提供了一些用于数值计算的函数模板，比如累加、累乘、部分求和等。
accumulate 是 <numeric> 头文件中定义的一个函数模板，它用于计算一个范围内所有元素的累加和。具体来说，accumulate 函数接受三个参数：
- 第一个参数：
InputIt first，表示输入范围的起始迭代器。 - 第二个参数：
InputIt last，表示输入范围的结束迭代器（不包括这个迭代器指向的元素）。 - 第三个参数：
T init，表示累加的初始值。
函数模板的基本形式如下：
template< class InputIt, class T >
T accumulate( InputIt first, InputIt last, T init );
这里，InputIt 是一个迭代器类型，它可以指向任何支持递增和解引用操作的容器或数组的元素。T 是累加结果的类型，也是初始值的类型。
accumulate 函数的工作原理是从 first 开始，逐个将 last 之前的每个元素加到 init 上，直到遍历完所有的元素。
下面是一个使用 accumulate 函数的简单例子：
#include <iostream>
#include <numeric>
#include <vector>
int main() {
std::vector<int> data = {1, 2, 3, 4, 5};
int sum = std::accumulate(data.begin(), data.end(), 0);
std::cout << "Sum: " << sum << std::endl; // 输出 15
return 0;
}
在这个例子中，accumulate 函数计算了 vector 中所有整数的和，并将结果存储在变量 sum 中。
accumulate 还可以接受一个可选的第四个参数，这是一个二元操作函数或函数对象，用于指定如何合并元素，而不仅仅是加法。例如：
#include <iostream>
#include <numeric>
#include <vector>
int main() {
std::vector<int> data = {1, 2, 3, 4, 5};
int product = std::accumulate(data.begin(), data.end(), 1, std::multiplies<int>());
std::cout << "Product: " << product << std::endl; // 输出 120
return 0;
}
在这个例子中，accumulate 函数计算了 vector 中所有整数的乘积，使用了 std::multiplies<int>() 作为二元操作函数。
另一种解法：HJ56_iNOC产品部–完全数计算(C++)
解法：
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <numeric>
using namespace std;
bool judge(int x){
vector<int> ivec;
int result=0;
for(int i =1;i<x;i++){
if(x%i==0) ivec.push_back(i);
}
result=accumulate(ivec.begin(),ivec.end(),0);
if(result==x) return true;
return false;
}
int main() {
int N;
while(cin>>N){
int cnt = 0;
bool perfect = false;
for(int i =1;i<=N;i++){
perfect = judge(i);
if(perfect) cnt++;
}
cout<<cnt<<endl;
}
}
HJ57 高精度整数加法
题目描述：
解题思路：
高精度整数用长整型也会越界，需要用STL容器处理，用stack 栈后进先出（LIFO）或者vector都可以。
解法：
#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
// 将两个字符串存入两个栈中，后进先出（LIFO），逐个斩当头，直到栈为空
// 主要注意进位问题，最后一位的问题
int main() {
string s1,s2;
while (cin >> s1 >> s2) { // 注意 while 处理多个 case
string ans;
stack<char> str1,str2;
for(auto c:s1){
str1.push(c);
}
for(auto c:s2){
str2.push(c);
}
int flag = 0;
while (str1.size() != 0 || str2.size() != 0) {
int temp = 0;
if(str1.size() != 0){
temp += str1.top() - '0';
str1.pop();
}
if(str2.size() != 0){
temp += str2.top() - '0';
str2.pop();
}
// temp和flag加完后再取余和除以，这是考虑到加完flag后刚好为10的情况
ans+=(temp+flag)%10+'0';
flag = (temp+flag)/10;
//对于两个栈都空之前，判断有没有进位，如果进位则直接加1
if(flag == 1 && str1.size() == 0 && str2.size() == 0)
ans+='1';
}
// 记得反转一下再输出
reverse(ans.begin(),ans.end());
cout<<ans<<endl;
}
return 0;
}
HJ58 输入n个整数，输出其中最小的k个
题目描述：
解题思路：
使用sort直接获得答案。
解法：
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
int a, b;
while (cin >> a >> b) { // 注意 while 处理多个 case
vector<int> vec(a,0);
for (int i=0; i<a; ++i) {
cin>>vec[i];
}
sort(vec.begin(), vec.end());
for (int i=0;i<b;++i) {
cout<<vec[i]<<" ";
}
}
return 0;
}
HJ59 找出字符串中第一个只出现一次的字符
题目描述：
解题思路：
使用vector数组顺序存储，输出第一个元素。
解法：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
string str;
cin >> str;
vector<char> vec;
vector<char> vecs;
for (char c : str) {
// 检查 vecs 中是否已经存在字符 c
if (std::find(vecs.begin(), vecs.end(), c) != vecs.end()) {
continue;
}
// 检查 vec 中是否已经存在字符 c
if (std::find(vec.begin(), vec.end(), c) != vec.end()) {
// 如果存在，添加到 vecs 并从 vec 中移除所有相同的字符
vecs.push_back(c);
auto newEnd = std::remove(vec.begin(), vec.end(), c);
vec.erase(newEnd, vec.end());
} else {
// 如果不存在，添加到 vec
vec.push_back(c);
}
}
if(vec.size()>0){
cout<<vec.at(0);
}
else {
cout<<-1;
}
return 0;
}
HJ60 查找组成一个偶数最接近的两个素数
题目描述：
解题思路：
暴力解。
解法：
#include <cmath>
#include <iostream>
using namespace std;
// 判断一个数是否为素数
bool isPrime(int n){
for(int i=2;i<n;++i){
if(n%i == 0){
return false;
}
}
return true;
}
int main() {
int a;
while (cin >> a) { // 注意 while 处理多个 case
int mindis = a;
pair<int,int> res;// 记录两个素数
for(int i = 2;i<a;i++){
if(isPrime(i) && isPrime(a - i)){
if(abs(a - i - i)<mindis){
res = {i,a-i};
mindis = abs(a - i - i);
}
}
}
cout<<res.first<<endl<<res.second<<endl;
}
return 0;
}
HJ61 放苹果
题目描述：
解题思路：
动态规划，分两种情况，有空盘子和没有空盘子，递归到最后只有两种情况，0个盘子放n个苹果或者n个苹果放1个盘子。
解法：
#include <stdio.h>
#include <string.h>
int f(int m, int n);
int main()
{
int m, n;
while (scanf("%d %d", &m, &n) != EOF)
{
printf("%d\n", f(m, n));
}
return 0;
}
int f(int m, int n)
{
int ret;
if (n == 1)
{
ret = 1; //m个果放1个盘子 1种
}
else if (m == 0)
{
ret = 1; //0个果放n个盘子 1种
}
else if (m < n)
{
ret = f(m,m);
//当m<n：必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响，
//即if(n>m) f(m,n) = f(m,m) 问题变成m个苹果，m个盘子的问题。即下面的m>=n的情况.
}
else if (m >= n)
{
ret = f(m - n, n) + f(m, n - 1);
//1.至少有一个空盘f(m,n) = f(m,n-1)；
//2.一个空盘都没有f(m,n) = f(m-n,n);(即如果所有盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响不同放法的数目.
//分析则有，总的放苹果的放法数目等于1、2两者的和，即 f(m,n) =f(m,n-1)+f(m-n,n))
}
return ret;
}
HJ62 查找输入整数二进制中1的个数
题目描述：
解题思路：
解法一使用STL库。
解法二运用位运算进行操作。
解法一：
#include <iostream>
#include <bitset>
using namespace std;
int main() {
int n;
while(cin>>n){
bitset<32> b(n);
cout<<b.count()<<endl;
}
}
// 64 位输出请用 printf("%lld")
解法二：
#include <iostream>
using namespace std;
int n, res; // 定义我们输入的 n 和我们最后的二进制1的个数
void solve() {
while(cin >> n) { // 多组输入我们的 n
res = 0; // 因为是多组输入，我们把我们每次的答案都先清空为 0
while(n) { // 如果 n 还有数字，不为0
if (n & 1) res++; // 如果当前 n 的最后一位二进制位是 1， 答案加1
n >>= 1; // n 向右移一次，将刚才计算过的二进制位剔除掉
}
cout << res << "\n"; // 输出最后的一个答案
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
solve();
return 0;
}
