数学是自然科学之母,数学也是算法之母,有一些数学相关的题目需要总结一下。当然暴力法也都是可以解决的,但是通过数学一些公式的引入会提升时间效率。
数学题目的特点
用暴力法或者模拟法也可以解决。
运用相关的数学知识或者数学公式,可以提升效率。
一般都可以使用查表大法。
数论
主要是以整数为基础的一些题目,一般会涉及素数,数位等。
典型题目
题目 | 题解 | 说明 |
---|---|---|
202. 快乐数 | 题解 | |
258. 各位相加 | 题解 | |
1175. 质数排列 | 题解 | |
2180. 统计各位数字之和为偶数的整数个数 | 题解 | |
题解 |
数组轮转
一般就是把数组的元素按照一定的规则进行移动和轮转。一般涉及LCM(最小公倍数)。
典型题目
题目 | 题解 | 说明 |
---|---|---|
189. 轮转数组 | 题解 | |
1806. 还原排列的最少操作步数 | 题解 | |
题解 |
矩阵
矩阵在数学中是非常重要的概念,在计算机科学中矩阵也是非常的重要,像在图形图像以及人工智能领域矩阵都有非常重要的应用。矩阵在编程语言中的表示也非常的容易一般用一个二维数组就可以表示一个矩阵。
典型题目
题目 | 题解 | 说明 |
---|---|---|
189. 轮转数组 | 题解 | |
1806. 还原排列的最少操作步数 | 题解 | |
题解 |
计算几何
几何相关的题目也是比较常见的,但通常都是离散化的,一般主要涉及直线,三角形和圆。
计算几何相关问题最需要注意的问题就是精度问题,特别是当坐标是以整数形式给出的时候,这时计算斜率要用乘法,而不能直接用除法。
典型题目
题目 | 题解 | 说明 |
---|---|---|
48. 旋转图像 | 题解 | |
566. 重塑矩阵 | 题解 | |
1828. 统计一个圆中点的数目 | 题解 | |
2319. 判断矩阵是否是一个 X 矩阵 | 题解 | |
题解 | ||
题解 |
随机化
涉及随机数。
典型题目
题目 | 题解 | 说明 |
---|---|---|
169. 多数元素 | 题解 | |
384. 打乱数组 | 题解 | 洗牌算法 |
题解 | ||
题解 |
大数运算
常规的数是有一定范围的,超出的数字用整数是无法表达的,这时就用字符串来表示数,称之为大数,大数也是要做四则运算的,这就是大数运算,通常就是用模拟正常加法乘法就行了。
典型题目
题目 | 题解 | 说明 |
---|---|---|
2. 两数相加 | 题解 | 加法模拟 |
43. 字符串相乘 | 题解 | 大数乘法 |
415. 字符串相加 | 题解 | 大数加法 |
其他
典型题目
题目 | 题解 | 说明 |
---|---|---|
89. 格雷编码 | 题解 | |
96. 不同的二叉搜索树 | 题解 | |
题解 |