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

╰+攻爆jí腚メ 2023-02-13 05:42 71阅读 0赞

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

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

# 1、问题分析 #

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

主要就是两个数学公式。代码我已经进行了详细的注释，理解应该没有问题，读者可以作为参考，如果看不懂(可以多看几遍)，欢迎留言哦！我看到会解答一下。  
高斯自然数求和公式如下：

1 + 2 + . . . + n = n × ( n + 1 ) 2 1 + 2 + ... + n = \\frac\{ \{n \\times (n + 1)\}\}\{2\} 1\+2\+...\+n=2n×(n\+1)

平方和公式如下：

1 2 + 2 2 + . . . + n 2 = n × ( n + 1 ) × ( 2 n + 1 ) 6 \{1^2\} + \{2^2\} + ... + \{n^2\} = \\frac\{ \{n \\times (n + 1) \\times (2n + 1)\}\}\{6\} 12\+22\+...\+n2=6n×(n\+1)×(2n\+1)

# 2、问题解决 #

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

#include "iostream"
    
    using namespace std;
    
    #include "algorithm"
    #include "vector"
    #include "queue"
    #include "set"
    #include "map"
    #include "cstring"
    #include "stack"
    
    class Solution { 
    private:
        long long sum = 0;
        // 定义返回节点是否是完美节点 0 不是; 1 是
        int flag = 0;
    public:
        /** * * @param n int整型 第n天 * @return int整型 */
        int solution(int n) { 
            // write code here
            int result = deal(n);
            int temp;
    
            // 完美节点
            if (flag == 1) { 
                // 根据数学公式 1^2+2^2+...+n^2=(n)*(n+1)*(2*n+1)/6
                result = result * (result + 1) * (2 * result + 1)/6;
            }
            else { 
                // 非完美节点，最后一个节点的效率无法全部发挥，计算 返回节点之前节点的和
                temp = (result-1) * ((result - 1) + 1) * (2 * (result - 1) + 1)/6;
                // 使用最后节点的工作效率有几天
                int number_data = n - (result - 1) * ((result - 1) + 1) / 2;
                // 将之前的结果和最后几天高效率工作结果累加即最终结果
                result = result * number_data + temp;
            }
    
            return result;
        }
    
        // 获取 n 对应的最后一个数的值，并记录是否正好整数个整数相加（是否是完美点）
        // 如 1 + 2 + 3 + 4 < 11 < 1 + 2 + 3 + 4 + 5 ,说明此时 4 和 5 是临界节点
        // 此处我们按照 5 返回结果，由于 11 ！= 1 + 2 + 3 + 4 + 5 ，说明 5 不是完美节点，所以flag ==0;
        // 如果 n = 15 ,此时 15 = 1 + 2 + 3 + 4 + 5 ，此时 5 就是完美节点 ，此处 flag == 1
        int deal(int n) { 
            for (int i = 1; i < n; ++i) { 
                // 根据数学公式 1+2+ ... + n = (n)*(n+1)/2 ,计算和
                sum = i * (i + 1) / 2;
                // 如果是完美节点
                if (sum == n) { 
                    flag = 1;
                    return i;
                }
                else if (sum > n) { 
                    return i;
                }
            }
        }
    };
    
    int main() { 
        Solution *pSolution = new Solution;
        int i = pSolution->solution(15);
        cout << i << endl;
        system("pause");
        return 0;
    }

运行结果

![在这里插入图片描述][20200527164020887.png]

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

# 3、总结 #

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

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

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