好未来笔试 2018【C++实现】

1. 拆数字串

一个数字串可以被拆成多个子数字串，求可以被3整除（0也可以被3整除）的子数字串的最大个数。

测试样例：输入：12345 = 12 + 3 + 45 输出：3

思路：从左到右依次处理，注意这种情况：输入：12346 = 12 + 3 + 6 输出：3 （要把4去除）

测试代码中应该没有 221， 1723271 这样的例子。

#include <iostream>
#include <string>

using namespace std;

int main() {
    // input
    string data;
    cin >> data;
    
    // main
    vector<int> v(data.size() + 1, 0);
    int result = 0;
    int begin  = 0;
    int end    = 1;
    
    while (end <= data.size())
    {  
        int current_num = data[end - 1] - '0';  
        if (current_num % 3 == 0)  
       {  
            ++result;  
            begin = end;  
            end += 1;  
            continue;  
        }  
        v[end] = v[end - 1] + current_num;  
        int temp = begin;
        while (temp < end)  
        {
            if ((v[end] - v[temp]) % 3 == 0)  
           {  
                ++result;
                begin = end;
                break;
            }  
           ++temp;  
        }
        ++end;
    }
    
    cout << result << endl;
    return 0;
}

2. 加与或的关系

x + y = x | y 求第 k 个 y，x, y均为正整数。

最佳思路：可参考 https://www.nowcoder.com/discuss/100031?type=2&order=0&pos=7&page=1

思路：比暴力解稍微好一点

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

pair<int, int> get_zero(int num)
{
    int count = 0;
    int count_1 = 0;
    while(num)
    {
        if( (num & 1) == 0)
        {
            ++ count;
        }
        num >>= 1;
        ++count_1;
    }
    return {count, count_1};
}


int main() {
    // input
    int t;
    cin >> t;
    cin.get();

    vector<vector<int> > data(t, vector<int>(2));
    
    // 
    int x = 0;
    int k = 0;
    int y = 1;
    
    for (int i = 0; i < t; ++i)
    {
        cin >> x >> k;
        cin.get();
        data[i] = {x, k};
    }


    for (int _t = 0; _t < t; ++_t)
    {
        x = data[_t][0];
        k = data[_t][1];
        auto counts = get_zero(x);
        int zeros   = counts.first;
        int ones    = counts.second;

        int temp   = pow(2, zeros);
        int cycle  = k / temp;
        int offset = k % temp;

        int _k = 0;
        y = 0;
        while(_k != offset)
        {
            ++y;
            if((x + y) == (x | y))
            {
                ++_k;
            }
        }

        y = y + cycle * pow(2, ones);
        cout << y << endl;

    }

    return 0;
}

3. 字符串组合

固定数组：{0，1，2，3，4，5，6，7，8，9}

布尔数组：{0，1，1，1，1，1，1，1，1，0} 0表示对应数组的下标元素可出现亦可不出现，1则表示必须出现

输出所有可能的组合，最终结果按升序排序。

思路：回溯，深度遍历。

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

void dfs(vector<int>& b, int idx, vector<int> temp, vector<string>& res)
{
    if (idx == b.size())
    {
        string r;
        for (auto e : temp) r += to_string(e);
        res.push_back(r);
        return;
    }

    if (b[idx] == 0)
    {
        dfs(b, idx + 1, temp, res);
    }

    temp.push_back(idx);
    dfs(b, idx+1, temp, res);
}

int main()
{
    int temp;
    vector<int> v;
    while (cin >> temp) v.push_back(temp);
    vector<string> res;

    dfs(v, 0, vector<int>(), res);
    sort(res.begin(), res.end());
    for (const auto &e : res) cout << e << endl;
}

4. 掷骰子

一个骰子共有 n 个面，掷每一面都是等概率的，其中有m个奖励面（掷到奖励面可再掷一次），

每一面都有相应的分数，掷到哪一面即可获得相应面得分数。求分数的期望。

思路：几何分布：几何分布的期望。

在伯努利试验中，成功的概率为p，ξ表示出现首次成功时的试验次数，则ξ是离散型随机变量，它只取正整数，且有P(ξ=k)=(1-p)的(k-1)次方乘以p (k=1，2，…，0<p<1)，此时称随机变量ξ服从几何分布。它的期望为1/p。

所以题目的分数的期望为次数 * 每次平均分数，即：

E = 1 / p * avg_scores . p = 1 - m/n.

#include <iostream>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    int temp;
    int sum = 0;
    for(int _n = 0; _n < n; ++_n)
    {
        cin >> temp;
        sum += temp;
    }
    
    printf("%.2f", double(sum) / (n - m) );
    return 0;
}

5.最大升序子序列和

输入：{5，1，3，4，9，7，6，8}

最大升序序列为：1，3，4，7，8

输出：23

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int main()
{
    int temp;
    vector<int> v;
    while (cin >> temp) v.push_back(temp);
    vector<int> sum = v;

    for (int i = 0; i < v.size(); ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            if (v[i] > v[j] && sum[i] < sum[j] + v[i])
            {
                sum[i] = sum[j] + v[i];
            }
        }
    }

    cout << *max_element(sum.begin(), sum.end()) << endl;
    return 0；
}

6. C实现字符串替换


	#include <stdio.h>



	#include <stdlib.h>



	#include <ctype.h>



	#include <string.h>



	





	





	char* ReplaceSubStr(const char* str, const char* srcSubStr, const char* dstSubStr, char* out)



	{   



	 char *p;



	 char *_out = out;



	 const char *_str = str;



	 const char *_src = srcSubStr;



	 const char *_dst = dstSubStr;



	





	 int src_size = strlen(_src);



	 int dst_size = strlen(_dst);



	 int len = 0;



	





	 do



	 {



	 p = strstr(_str, _src);



	 if(p == 0)



	 {



	 strcpy(_out, _str);



	 return out;



	 }



	 len = p - _str;



	 memcpy(_out, _str, len);



	 memcpy(_out + len, _dst, dst_size);



	 _str = p + src_size;



	 _out = _out + len + dst_size;



	





	 } while(p);



	





	 return out;



	





	}



	





	





	int main()



	{



	 char str[1024];



	 char srcSubStr[1024];



	 char dstSubStr[1024];



	 char out[1024];



	





	 gets(str);



	 gets(srcSubStr);



	 gets(dstSubStr);



	 ReplaceSubStr(str, srcSubStr, dstSubStr, out);



	





	 printf("%s\n", out);



	 return 0;



	}