数学是自然科学之母,数学也是算法之母,有一些数学相关的题目需要总结一下。当然暴力法也都是可以解决的,但是通过数学一些公式的引入会提升时间效率。
数学题目的特点
用暴力法或者模拟法也可以解决。
运用相关的数学知识或者数学公式,可以提升效率。
一般都可以使用查表大法。
数论
主要是以整数为基础的一些题目,一般会涉及素数,数位等。
典型题目
题目 | 题解 | 说明 |
---|---|---|
202. 快乐数 | 题解 | |
258. 各位相加 | 题解 | |
1175. 质数排列 | 题解 | |
2180. 统计各位数字之和为偶数的整数个数 | 题解 | |
题解 |
数组轮转
一般就是把数组的元素按照一定的规则进行移动和轮转。一般涉及LCM(最小公倍数)。
典型题目
题目 | 题解 | 说明 |
---|---|---|
189. 轮转数组 | 题解 | |
1806. 还原排列的最少操作步数 | 题解 | |
题解 |
计算几何
几何相关的题目也是比较常见的,但通常都是离散化的,一般主要涉及直线,三角形和圆。
计算几何相关问题最需要注意的问题就是精度问题,特别是当坐标是以整数形式给出的时候,这时计算斜率要用乘法,而不能直接用除法。
典型题目
题目 | 题解 | 说明 |
---|---|---|
149. 直线上最多的点数 | 题解 | |
883. 三维形体投影面积 | 题解 | |
1037. 有效的回旋镖 | 题解 | |
1828. 统计一个圆中点的数目 | 题解 | |
题解 |
其他
典型题目
题目 | 题解 | 说明 |
---|---|---|
96. 不同的二叉搜索树 | 题解 | |
89. 格雷编码 | 题解 | |
题解 |