算法思路 - 差分数组

差分数组与前缀和数组什么是前缀和数组前缀和数组是一个辅助数组,下面给出定义:对于原数组 nums[i] , 其前缀和数组 sums[i] = (nums[0] + nums[1] + … + nums[i])前缀和数组下标为 i 的数字表示原数组从 0 到 i 的数的和。前缀和数组的性质前缀和数组主要用于频繁求区间和 :定义 nums[i, j] = (nums[i] + nums[i+1] +

- 阅读全文 -

算法思路 - 动态规划

动态规划什么是动态规划动态规划,Dynamic Programming,简称 DP。这个词其实是运筹学的一个分支,在求解决策中占重要地位。当然这里只是取其一个狭义的意思,就是算法题中的一种解题的方法,或者说思考方法。能用动态规划解决的题,有以下特点:问题能进行拆分,大问题能拆分成小问题,并且这些问题都有共同的特点这些问题能转换成一个函数,有输入和输出。这个函数的递推表达式容易得出有点抽象,不理解也

- 阅读全文 -

算法思路 - 有序线性表二分查找模板

对于一串有序线性表,要在里面查找某个值,想都不用想直接二分,但是实际问题不会简单的在线性表里查某个值,而是要求范围第一个大于某值的下标等,这种时候就涉及到一些边界的处理问题,这里整理出几个模板,以后遇到要用到二分的题可以直接套用模板。中间值计算首先中间值计算要使用 mid = left + (right-left)/2,如果直接使用 mid = (left+right)/2 ,会产生溢出问题。其次

- 阅读全文 -

算法模型 三边定位实现

最近有一个需求,有三个基站和一个定位点。每个基站可以测出自己和其他两个基站之间的距离以及自己和定位点的距离。要求以定位点为中心建立直角坐标系画出三个基站的点。抽象成数学模型,如下图:已知六条边 abcdefg 的长度,求 ABC 三点坐标。如果是数学题,其实也不是很难,这里问题在于基站测出的距离是有精度损失的,也就是说这里距离是有误差的,可能最终 OA 的距离会大于 e。或者说可能给出的距离无法组

- 阅读全文 -