刷算法题必备的数学考点汇总¶
统计信息：字数 2078 阅读5分钟
原文：leetcode 微信
https://mp.weixin.qq.com/s/INpy-GVMz7ny4zHcVwLnGw
主要分为数论和排列组合部分，这是一部分算法题目必须的基础知识（部分图片无法拷贝，详细参考原始文章）
数论¶
位运算¶
我们通常使用 D和B表示十进制和二进制数（10D，123D， 10B，1010B）。在计算机中使用二进制进行计算，叫做位运算。
& 与
| 或
^ 异或
~ 取反
<< 左移
>> 右移
具体原理需要了解原码、反码、补码。
快速幂¶
快速幂基于位运算，开始介绍「快速幂」算法，该算法常用于快速指数运算。
// 计算 a ^ b
int pow (int a, int b) {
int base = a, ans = 1;
while (b) {
if (b & 1) ans *= base;
base *= base;
b >>= 1;
}
return ans;
}
排列组合¶
https://mp.weixin.qq.com/s/INpy-GVMz7ny4zHcVwLnGw
2月3日
基本概念
加法原则：如果一个问题有很多情况，每一个情况有N种解决方法，那么最后的解决方法就是 n1 + n2 + n3... 分治算法思路
乘法原则：如果一个问题可以划分成互不干涉的M步，那么最后解决问题的方法就是 m1 * m2 * m3...
排列：Amn 有顺序 = m! / (n - m)!
组合：Cmn 没有顺序 = Amn / n! = m! / (n - m)! / n!
可以推导出：Cmn = Cmn-1 + Cm-1n-1 这个递推式可以用于动态规划，或者利用缓存存储结果
基本例题：
机器人走路问题。从（0， 0）点走到（m, n）点，每次只能走1步，问一共有多少情况？
思路：也就是从 (0 -> m) (0 -> n) 从X轴和Y轴上分别走即可。实际走的步数就是 m - 1 + n - 1 = m + n - 2。其中水平走路 n - 1。那么就是一个组合问题。C(n - 1)(m + n - 2) 带入上面的公式计算即可。
Last update:
November 9, 2024