今日头条春招第一次笔试题(二)

第二题

题目描述

定义两个字符串变量: s和m, 再定义两种操作,

第一种操作:

m = s;
s = s + s;

第二种操作:

s = s + m;

假设s, m 初始化如下:

s = "a";
m = s;

求最小的操作步骤数, 可以将s拼接到长度等于n.

输入描述:

一个整数n, 表明我们需要得到的s字符串长度
对于100%的数据, 0 < n < 10000

输出描述:

一个整数,表明总共操作的次数.

解法分析

这道题, 我的理解是在考察二叉树的层次遍历.
并且我认为这应该是比较优秀的解决方案之一.
首先, 题目中提到了最小的操作步骤数, 因此我们就要想到我们需要用一个广度优先的搜索,这在二叉树这种数据结构中就是层次遍历.

我们来描述一下这棵二叉树, 二叉树的根节点是中存放的是初始的s和m的值. 其中左指针指向采用第一种操作得到的s和m的值, 右指针指向采用第二种操作得到的s和m的值. 这样一次的递归下去.
而叶子节点就是第一次超过给定长度的情况下的s和m的值. 即叶子节点的根节点的s的长度都小于要求的长度.叶子节点的s的长度都大于或等于要求的长度.我们需要找到叶子节点, 满足

1. 叶子节点中s的长度恰好等于要求的长度.
2. 满足条件1的叶子节点的深度最小.

实际操作的时候,我们没必要建立一棵树结构.采用队列去模拟层次遍历即可.

代码

#include <iostream>
#include <deque>

using namespace std;
int func0_s(int s, int m)
{
    return s * 2;
}
int func0_m(int s, int m)
{
    return s;
}

int func1_s(int s, int m)
{
    return s + m;
}
int func1_m(int s, int m)
{
    return m;
}

int main()
{
    int n;
    cin >> n;

    deque<int> layer_s_queue;
    deque<int> layer_m_queue;
    deque<int> layer_queue;
    int s = 1;
    int m = s;
    layer_s_queue.push_back(s);
    layer_m_queue.push_back(m);
    layer_queue.push_back(0);
    int min_layer = 0;

    while(!layer_s_queue.empty())
    {
        int temp_s = layer_s_queue.front();
        layer_s_queue.pop_front();
        int temp_m = layer_m_queue.front();
        layer_m_queue.pop_front();
        int temp_layer = layer_queue.front();
        layer_queue.pop_front();


        if(func0_s(temp_s, temp_m) < n)
        {
            layer_s_queue.push_back(func0_s(temp_s, temp_m));
            layer_m_queue.push_back(func0_m(temp_s, temp_m));
            layer_queue.push_back(temp_layer + 1);
        }
        else if(func0_s(temp_s, temp_m) == n)
        {
            min_layer = temp_layer + 1;
            break;
        }


        if(func1_s(temp_s, temp_m) < n)
        {
            layer_s_queue.push_back(func1_s(temp_s, temp_m));
            layer_m_queue.push_back(func1_m(temp_s, temp_m));
            layer_queue.push_back(temp_layer + 1);
        }
        else if(func1_s(temp_s, temp_m) == n)
        {
            min_layer = temp_layer + 1;
            break;
        }
    }

    cout << min_layer;

    return 0;
}