Python技术迷

员工举报调休,公司反手取消14天年假

刚看到个新闻,说深圳有家公司因为员工举报调休,结果公司一气之下直接取消了原本承诺的14天年假。这事儿瞬间把大家吓傻了。

Image

我觉得这事吧,说到底还是公司心态有问题。员工去劳动局举报,是因为觉得权益被侵犯,这是法律赋予的权利。可公司不去解决问题,反而用取消年假这种“连坐”的方式来惩罚全体,摆明了是把矛盾推给员工。说白了,这是拿大家的利益出气,既不合法,也不合情理。

网友们的讨论我也看了,有人觉得员工太轴,有人骂公司黑心。我比较认同“制度要公开透明”这一点。企业靠小动作维持秩序,只会让信任感彻底崩塌;而员工如果连基本的假期都没保障,干劲还能有多少?

合理的制度才是企业长久的保障。靠打击报复来管理,只会让人心寒,最终两败俱伤。【备注:文末可领最新资料】

面试题:划分数字的方案数

就一个正整数 n,把它拆成若干个正整数之和,顺序不算(3+2 和 2+3 是同一种)。问一共有多少种拆法。比如 n=5,有 7 种:5、4+1、3+2、3+1+1、2+2+1、2+1+1+1、1+1+1+1+1。

把 1..n 这些数看成“面额”,每个都能用无限次。求“用这些面额凑出金额 n 的方法数”,且不考虑顺序。典型的完全背包计数模型。 一维 DP 很好写:dp[x] 表示和为 x 的方案数。遍历“面额”在外层、遍历目标值在内层(从小到大),就能天然去重(避免 2+3 和 3+2 的重复)。

defpartitions(n: int) -> int:
if n < 0:
return0
    dp = [0] * (n + 1)
    dp[0] = 1
# coin 是每个可用的加数(1..n)
for coin in range(1, n + 1):
for x in range(coin, n + 1):
            dp[x] += dp[x - coin]
return dp[n]

这个写法的语义:对每个 coin,你要么不用它,要么用一次、两次……都在第二层循环的累加里体现了。外层 coin 递增,保证组合无序。

另一个角度:限制“最大部件”

也有人喜欢用二维 DP:f[i][j] 表示把 j 拆成若干数且每个数不超过 i 的方案数。转移:

  • 不用 i:f[i-1][j]
  • 至少用一个 i:f[i][j-i]于是 f[i][j] = f[i-1][j] + f[i][j-i]。空间可压成一维,实际就是上面的硬币模型。
if __name__ == "__main__":
for k in range(1, 8):
        print(k, partitions(k))
# 期望:1→1, 2→2, 3→3, 4→5, 5→7, 6→11, 7→15

时间复杂度约 O(n^2),空间 O(n)。 如果 n 很大(几千以上),这个二次算法就有点慢,可以做两件事:

  1. 取模(很多在线题会给个 MOD),避免整数过大;
  2. 需要多次查询不同 n 时,把 dp 一次性滚到最大值,后面直接查表。
defpartitions_mod(n: int, mod: int = 10**9+7) -> int:
    dp = [0]*(n+1)
    dp[0] = 1
for coin in range(1, n+1):
for x in range(coin, n+1):
            dp[x] = (dp[x] + dp[x-coin]) % mod
return dp[n]

更深一点有欧拉的“五边形数定理”可把 p(n) 用奇妙的递推算出来,理论很优雅,但实现细节多、易出错。面试或竞赛赶时间,完全背包计数这套写法最稳、也最好讲清楚。

就这样,代码能过大多数题;需要超大 n 再考虑更高级的数学公式或生成函数。

-END-

我为大家打造了一份RPA教程,完全免费:songshuhezi.com/rpa.html

🔥虎哥私藏精品🔥

虎哥作为一名老码农,整理了全网最全《python高级架构师资料合集》,总量高达650GB,点击下方公众号回复关键字 python 全部免费领