牛客网 vivo2020届春季校园招聘在线编程考试第2题

川长思鸟来 2023-02-13 05:41 89阅读 0赞

### 牛客网 vivo2020届春季校园招聘在线编程考试 第2题 ###

*  1、问题分析
 *  2、问题解决
 *  3、总结

# 1、问题分析 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70]

基本思路是：

> 1、如果有因子大于等于 10 ，说明不存在 m,使得 m 的各位（个位、十位、百位 … …）之乘积等于n，提前结束  
> 2、如果满足第一个条件，则尽量将因子个数减少。  
> 代码我已经进行了详细的注释，理解应该没有问题，读者可以作为参考，如果看不懂(可以多看几遍)，欢迎留言哦！我看到会解答一下。

# 2、问题解决 #

笔者以`C++`方式解决。

#include "iostream"
    
    using namespace std;
    
    #include "algorithm"
    #include "vector"
    #include "queue"
    #include "set"
    #include "map"
    #include "cstring"
    #include "stack"
    
    class Solution { 
    private:
        // 存储 n 因式分解的结果
        // 如：n = 36, 则 dp={2,2,3,3}
        vector<int> dp;
    public:
        /** * 输入一个整形数值，返回一个整形值 * @param n int整型 n>9 * @return int整型 */
        int solution(int n) { 
            // write code here
            // 将 n 因式分解
            deal(n);
    
            // 处理因式分解之后的结果
            return dfs();
        }
    
        /** * 处理因式分解之后的结果 * 基本思路是： * 1、如果有因子大于等于 10 ，说明不存在 m,使得 m 的各位（个位、十位、百位 ... ...）之乘积等于n，提前结束 * 2、如果满足第一个条件，则尽量将因子个数减少 * @return */
        int dfs() { 
            // m 的各位（个位、十位、百位 ... ...） 结果数组
            vector<int> temp;
            int data = 1;
            // 遍历因子数组
            for (int i = dp.size() - 1; i >= 0; --i) { 
                // 如果有因子大于等于 10 ，说明不存在 m,使得 m 的各位（个位、十位、百位 ... ...）之乘积等于n，提前结束
                if (dp[i] >= 10) { 
                    return -1;
                }
                // 由于最小的数，他的位数一定是最小，所以我们需要尽量将因子个数减少，如果可以减少，则更新因子的值
                if (data * dp[i] < 10) { 
                    data = data * dp[i];
                } else { 
                    // 如果因子的值无法更新，则将其放入结果数组，初始化为 dp[i] 并重复上述操作
                    temp.push_back(data);
                    data = dp[i];
                }
            }
            // 最后的 data 还有剩余的值要记得存放到 结果数组汇总
            if (data != 1) { 
                temp.push_back(data);
            }
    
            int result = 0;
            // 将结果数组从小到大排序
            sort(temp.begin(), temp.end());
            // 将结果数组变成真实的结果
            for (int i = 0; i < temp.size(); ++i) { 
                result = result * 10 + temp[i];
            }
    
            // 返回最终的结果
            return result;
        }
    
        /** * 将 n 因式分解 * 并将因式分解的结果保存到 dp 数组中 * @param n */
        void deal(int n) { 
            // 之所以是 i <= n ，是每次有新的因子时，我们都会更新 n 的值
            for (int i = 2; i <= n; ++i) { 
                if (n % i == 0) { 
                    // 保存新的因子
                    dp.push_back(i);
                    // 重置 n 的值
                    n /= i;
                    // 这里注意边界
                    --i;
                }
            }
        }
    
    };
    
    int main() { 
        Solution *pSolution = new Solution;
        int i = pSolution->solution(36);
        cout << i << endl;
        system("pause");
        return 0;
    }

运行结果

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70 1]

有点菜，有时间再优化一下。

# 3、总结 #

书上的代码直接运行绝大部分是对的，但是总有一些软件的更新使得作者无能为力。之前的API是对的，但是之后就废弃了或修改了是常有的事。所以我们需要跟踪源代码。这只是一个小小的问题，如果没有前辈的无私奉献，很难想象我们自己一天能学到多少内容。感谢各位前辈的辛勤付出，让我们少走了很多的弯路！

点个赞再走呗！欢迎留言哦！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200527161814924.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200527161836734.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNTEwNTk3,size_16,color_FFFFFF,t_70