牛客-华为编程题

每一个你不满意的现在，都有一个你没有努力的曾经。

华为研发工程师编程题

来源

汽水瓶

正常思路，递归

链接：https://www.nowcoder.com/questionTerminal/fe298c55694f4ed39e256170ff2c205f
来源：牛客网
/*
递归问题：最主要是先分析出其递归方程，此外，可以考虑是否可以使用迭代替换。

3个瓶子换1瓶水+1个空瓶子，两个瓶子换1瓶水+0个空瓶子，1个瓶子换0瓶水。
f(1) = 0
f(2) = 1
f(3) = 1
f(4) = f(2)+1    //4个瓶子，其中3个可以换1瓶水+1个空瓶，所以是f(2)+1
f(5) = f(3)+1    //3个瓶子换1瓶水+1个空瓶，所以是f(3)+1
...
f(n) = f(n-2)+1
*/
#include <iostream>
using namespace std;

int f(int n)
{
    if(n==1) return 0;
    if(n==2) return 1;
    return f(n-2)+1;
}
  
int main()
{
    int n;
    while(cin >> n){
        if(n==0)
            break;
        cout<<f(n)<<endl;
    }
    return 0;
}

巧解

#include <iostream>
using namespace std;
int main()
{
	int n;
	while(cin>>n)
	{
        if(n == 0) break;
		//每3瓶换一瓶，剩余一瓶
		//实际上每两瓶就能换一瓶且没有剩余
		//极限想法，尽可能地借即得最大量
		//数学证明：
		cout<<n/2<<endl;
	}
	return 0;
}

明明的随机数

正常解法

链接：https://www.nowcoder.com/questionTerminal/3245215fffb84b7b81285493eae92ff0
来源：牛客网
#include<iostream>
#include<set>
  
using namespace std;
  
int main()
{
    int loop = 0;
    while (cin >> loop)
    {
        int a[1000], i = 0;
        for (int i = 0; i < loop; i++)
	    cin >> a[i];
        set<int> num(a, a + loop);
        for (set<int>::iterator it = num.begin(); it != num.end(); it++){
            cout << *it << endl;
        }
    }
    return 0;
}

巧解

#include <iostream>
using namespace std;
int main() {
    int N, n;
    while (cin >> N) {
        int a[1001] = { 0 };
        while (N--) {
            cin >> n;
            a[n] = 1;
        }
        for (int i = 0; i < 1001; i++)
            if (a[i])
                cout << i << endl;
    }
    return 0;
}

进制转换

普通解法

#include<iostream>
#include<string>
#include<cmath>
using namespace std;
int main()
{
    string str;
    int i = 0, len, res;
    while(cin>>str)
    {
        len = str.size();
        res = 0;
        for(i = len -1; i>=0; i--)
        {
            if(str[i] >= '0' && str[i] <='9')
            {
                res += (str[i]-'0')* pow(16, len - i - 1);
            }
            else if(str[i] >= 'A' && str[i] <= 'F')
            {
                res += (str[i] - 55) * pow(16, len - i - 1);
            }
        }
        cout<<res<<endl;
    }
}

巧解

#include <iostream>
using namespace std;

int main()
{
    int a;
    while(cin>>hex>>a)
    {
        cout<<a<<endl;
    }
}

华为2016研发工程师编程题

来源

删数

约瑟夫定理

#include <iostream>
using namespace std;
int main(){
    int N;
    while(cin>>N){
        int last=0;
        for(int i=2;i<=N;i++)
            last=(last+3)%i;
        cout<<last<<endl;
    }
    return 0;
}

使用队列

循环，不断把剩下的重新添加至队列中。

#include <iostream>
#include <queue>
using namespace std;
int main()
{
	int n;
	while(cin>>n)
	{
		queue<int> loop;
		for(int i=0; i<n; i++)
		{
			loop.push(i);
		}
		while(loop.size()>1)
		{
			int c = 2;
			while(c--)
			{
				loop.push(loop.front());
				loop.pop();
			}
			loop.pop();
		}
		cout<<loop.front()<<endl;
	}
	return 0;
}

字符集合

常规（和上面的明明随机数思想一样）

#include <iostream>
#include <string>
using namespace std;
int main()
{
    string str;
    while(cin>>str)
    {
        int a[124] = {0};
        char b[54] = {0};
        int j = 0;
        for(int i=0; i<str.size(); i++)
        {
            if(a[str[i]] == 0)
            {
                a[str[i]] = 1;
                b[j] = str[i];
                j++;
            }
        }
        cout<<b<<endl;
    }
    return 0;
}

哈希表

思路和上面的一样

#include<iostream>
#include<string>
#include<map>
using namespace std;
int main(){
    string s;
    while(cin>>s){
        string res;
        map<char,int> cnt;
        for(int i=0;i<s.size();i++){
            if(cnt[s[i]]==0){
                cnt[s[i]]++;
                res+=s[i];
            }
        }
        cout<<res<<endl;
    }
}