共有 277 篇文章
📅 最近更新
判断两个线段相交
2019-05-29
- 2024-09-15
如何判断两条直线是否相交？
这很容易。平面直线，无非就是两种关系：相交 或 平行。因此，只需判断它们是否平行即可。而直线平行，等价于它们的斜率相等，只需分别计算出它们的斜率，即可做出判断。
但倘若我把“直线”换成“线段”呢——如何判断两条线段是否相交？
这就有些难度了。和 直线 不同，线段 是有固定长度的，即使它们所属的两条直线相交，这两条线段也不一定相交。
C++输出格式控制
2019-05-28
- 2024-09-18
叙述在输出数据时，为简便起见，往往不指定输出的格式，由系统根据数据的类型采取默认的格式，但有时希望数据按指定的格式输出，如要求以十六进制或八进制形式 输出一个 整数，对输出的小数只保留两位小数等。有两种方法可以达到此目的。
- 使用控制符的方法
- 使用流对象的有关成员函数
线段树
2019-05-28
- 2024-09-15
线段树（segment tree），顾名思义， 是用来存放给定区间（segment, or interval）内对应信息的一种数据结构。与树状数组（binary indexed tree）相似，线段树也用来处理数组相应的区间查询（range query）和元素更新（update）操作。与树状数组不同的是，线段树不止可以适用于区间求和的查询，也可以进行区间最大值，区间最小值（Range Minimum/Maximum Query problem）或者区间异或值的查询。
对应于树状数组，线段树进行更新（update）的操作为O(logn)，进行区间查询（range query）的操作也为O(logn)。
Linux/Unix 环境下实现精确计算程序运行的时间
2019-05-27
- 2024-09-18
写程序时，程序的运行效率很重要，其往往是评价程序优劣性的直接标准。程序运行效率的最简单方法就是计算程序的运行时间。为了提高程序效率，使用适当的方法对程序的各个部分进行运行时间的计算是很有必要的。
最大子列和问题
2019-05-27
- 2024-09-15
求取数组中最大连续子序列和，例如给定数组为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_$