面试刷题总结(九)- 数学知识

数学类问题一定要记得进位 v = v1 + v2 + carry

最大公约数和最小公倍数

辗转相除法(欧几里得算法). 原理在于 gcd(a, b) == gcd(b, a % b)

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

排列组合

卡特兰数,为什么除以 n+1

牛顿迭代法

格雷码

二进制

  • 判断一个数是不是 2 的正整数次幂:n > 0 && (n & (n - 1)) == 0
  • 对 2 的非负整数次幂取模:x & (mod - 1)
  • 判断符号是否相同:(x ^ y) >= 0
  • 获取某一位:(a >> b) & 1
  • 遍历某个集合的子集:for (int s = u; s; s = (s - 1) & u)
  • 一的个数:while (n) {n = n & (n-1); count++}

求幂

long long binpow(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}

全排列

几何

有时候几何题也会出现在面试中。不过,毕竟是 coding interview 而不是 math interview,这部分复习的优先级不高。

参考

  • https://oi-wiki.org/math/

及时获取更新,请关注公众号“爬虫技术学习(spider-learn)”

公众号“爬虫技术学习(spider-learn)”

About 逸飞

后端工程师

发表评论

电子邮件地址不会被公开。 必填项已用*标注