如何判断两条直线是否相交?
这很容易。平面直线,无非就是两种关系:相交 或 平行。因此,只需判断它们是否平行即可。而直线平行,等价于它们的斜率相等,只需分别计算出它们的斜率,即可做出判断。
但倘若我把“直线”换成“线段”呢——如何判断两条线段是否相交?
这就有些难度了。和 直线 不同,线段 是有固定长度的,即使它们所属的两条直线相交,这两条线段也不一定相交。
线段树(segment tree),顾名思义, 是用来存放给定区间(segment, or interval)内对应信息的一种数据结构。与树状数组(binary indexed tree)相似,线段树也用来处理数组相应的区间查询(range query)和元素更新(update)操作。与树状数组不同的是,线段树不止可以适用于区间求和的查询,也可以进行区间最大值,区间最小值(Range Minimum/Maximum Query problem)或者区间异或值的查询。
对应于树状数组,线段树进行更新(update)的操作为O(logn),进行区间查询(range query)的操作也为O(logn)。
求取数组中最大连续子序列和,例如给定数组为A={1, 3, -2, 4, -5}, 则最大连续子序列和为
$math_inline$6$math_inline$
,即
$math_inline$1+3+(-2)+4=6$math_inline$
。
方法一共有三种,复杂度分别为
$math_inline$O(N^2)$math_inline$
、
$math_inline$O(NlgN)$math_inline$
、
$math_inline$O(N)$math_inline$
每个合数都可以写成几个质数相乘的形式,其中每个质数都是这个合数的质因数。如果一个质数是某个数的因数,那么就说这个质数是这个数的质因数。而这个因数一定是一个质数。
把一个合数用质因数相乘的形式表示出来,叫做分解质因数。如30=2×3×5 。分解质因数只针对合数。
质数: 质数(prime number)又称素数,有无限个。
质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。
合数: 合数指自然数中除了能被1和本身整除外,还能被其他数(0除外)整除的数。与之相对的是质数,而1既不属于质数也不属于合数。最小的合数是4。其中,完全数与相亲数是以它为基础的。