比亚迪，学历大于一切

大家好，我是吴师兄。

前几天在牛客网上刷到一个帖子，“吐槽”了在比亚迪里面学历与晋升之间的博弈。

他曾在比亚迪工作，入职时级别为G3/F1，但在三年内看来，升职到E1的可能性并不高。与此同时，一些学历较好的硕士应届生却可以直接以E1级别进入比亚迪。并且，比亚迪的职级倒挂更加明显，因为这种倒挂不仅仅是在薪资上，更体现在职级晋升的机会上。

进而推断出在比亚迪，学历大于一切。

如果一家公司只看重员工的学历背景，而忽视了他们的实际工作能力和贡献，那么很可能会错失许多优秀人才，影响到公司的长远发展。

除了对于晋升机会的影响外，这种以学历为主导的职级制度也可能带来其他一些负面影响。比如，可能会造成“新人优待”现象，即新员工凭借着较高的学历直接进入高级别职位，而忽视了老员工多年的工作经验和努力。这种情况不仅会降低老员工的工作积极性，也会造成团队内部的不和谐和紧张气氛。

好像互联网行业这种现象比较少，其它行业比如传统制造行业多多少少有这种苗头，大家是怎么看的？

继续今天的算法学习，来一个简单的算法题：灯泡开关。

一、题目描述

初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭第二个。

第三轮，你每三个灯泡就切换第三个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。

找出并返回 n 轮后有多少个亮着的灯泡。

示例 1：

输入：n = 3
输出：1 
解释：
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 

你应该返回 1，因为只有一个灯泡还亮着。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：1

提示：

• 0 <= n <= 10^9

二、题目解析

这题的代码很简单，关键是证明。

数学归纳法严格证明

假设结论“当灯泡数目为n-1时，经过n-1轮后，最后有剩下floor(sqrt(n-1))个灯泡是亮着的”成立，用数学归纳法证明，需要考虑

1. 灯泡数目为n = 1的情况
2. 灯泡数目为n的情况

n = 1时，第1个灯泡经过1轮后从关变到开，上述结论显然成立。故证明的重点是，考虑灯泡数目取n时，结论“当灯泡数目为n时，经过n轮后，最后有剩下floor(sqrt(n))个灯泡是亮着的”是否成立。

当灯泡数目为n时，考虑前n-1个灯泡的行为：

• 经过n-1轮后，前n-1个灯泡的行为和考虑灯泡数目为n-1时经过n-1轮后的行为是完全一致的，故此时有floor(sqrt(n-1))个灯泡是亮着的。
• 在第n轮中，只有第n个灯泡进行了切换，故前n-1个灯泡会维持存在floor(sqrt(n-1))个灯泡是亮着的情况。

考虑最后一个灯泡，即第n个灯泡在n轮中的行为。

注意到，当且仅当i是n的因数时，第n个灯泡在遇到第i轮的时候会切换状态。考虑n的因数个数

• 若个数为偶数，那么经过偶数次状态转换后，第n个灯泡的状态为关。
• 若个数为奇数，那么经过奇数次状态转换后，第n个灯泡的状态为开。

因数总是成对出现的，假设i为n的因数，那么n/i一定是n的因数。即灯泡会在第i轮和第n/i轮，都会进行状态切换。

• 若i != n/i，那么会进行2次切换。
• 若i == n/i，那么仅进行1次切换，即第i轮和第n/i轮属于同一轮。

根据i == n/i可以计算出，i^2 == n。我们可以得出结论：当且仅当n为某个正整数i的平方，即当n为一个完全平方数时，第n个灯泡经过n轮会经过奇数次状态转换，最终的状态为开。

令A和B是满足A^2 <= n-1 <= B^2和A+1 = B成立的两个正整数，即n-1是位于两个相差为1的正整数A和B的平方A^2和B^2之间的一个整数。显然A = floor(sqrt(n-1))。

我们将考虑前n-1个灯泡和第n个灯泡的情况结合起来，计算经过n轮之后状态为开的灯泡的总数。若

• n不是完全平方数
  • 那么n的最终状态为关，最终亮着的灯泡数为前n-1个灯泡亮着的数目，即floor(sqrt(n-1))。
  • 由于n不是完全平方数，那么A^2 <= n-1 < n < B^2成立，此时存在A = floor(sqrt(n))成立，故floor(sqrt(n-1)) = floor(sqrt(n))成立。
  • 因此，对于n个灯泡经过n轮，最终会有floor(sqrt(n))个灯泡亮着，结论成立。
• n是完全平方数
  • 那么n的最终状态为开，最终亮着的灯泡数为前n-1个灯泡亮着的数目加上第n个灯泡，即floor(sqrt(n-1))+1。
  • 由于n是完全平方数，那么A^2 <= n-1 < n = B^2成立，此时存在B = floor(sqrt(n))成立，故floor(sqrt(n-1))+1 = A+1 = B = floor(sqrt(n))成立。
  • 因此，对于n个灯泡经过n轮，最终会有floor(sqrt(n))个灯泡亮着，结论成立。

综合上述两种情况，数学归纳法得证，结论“当灯泡数目为n时，经过n轮后，最后有剩下floor(sqrt(n))个灯泡是亮着的”成立。

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 添加微信 278166530 获取最新课程
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 灯泡开关（LeetCode 319）:https://leetcode.cn/problems/bulb-switcher/
class Solution {
    public int bulbSwitch(int n) {
        // n = 14  , 3.xx
        // n = 15  , 3.xx
        // n = 16  , 4
        // 求小于等于 n 的完全平方数的个数
        return (int)Math.sqrt(n);
    }
}

2、C++ 代码

class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n + 0.5);
    }
};

3、Python 代码

class Solution:
    def bulbSwitch(self, n: int) -> int:
        return int(sqrt(n + 0.5))