频道栏目
IT货架 > > 正文
LeetCode算法编程之连载四(二分法)« 1、题目 – Sqrt(x) 2、题目 - Search a 2D Matrix
网友分享于:Jun 12, 2018 11:40:04 PM    来源: IT货架   

1、题目 – Sqrt(x)

题目意思很简单,就是求出x的平方根。

分析:

一看这题目,感觉很简单,很容易想到的是二分法,我最开始的解法是从1、2、4、8 … 2 * n,计算出n < x < 2n,然后再在 n 和 2n间,用二分法,找到平方根结果。

这种方法比较麻烦的一点是,乘积是有可能越界的,要处理乘积越界的情况,代码可读性不强。

要解决乘积越界的情况,有没有什么好的办法呢?能不能思考一下,在32位可表达的情况下,平方根可能出现的最大的情况?想到位图是不是可以来表示呢?利用二分法

(1 << 16)的平方为1 << 32位(这已越界),那么最大值是1 << 15,既然知道可表示的最大位数是15,那么依次往低走,根据乘积与x的比较看看每一位可否置1,根据这个思路,有了位图的解决方法:

这个代码是不是很漂亮了

2、题目 - Search a 2D Matrix

题目解释:

输入为一个m x n的矩阵,矩阵每行已从小到大排序,每行第一个数大上一行的最后一个数,在矩阵中是否能找到数x。

分析:

很容易想到,先到这个数所在行,然后在找到这个数所在的列。当然依次遍历过去的是可以的,反正是已经排过序的,这是最笨的方法。但作为搞算法的,最基本的方法就是二分法,

思路是一样的,利用行二分法,找到所在行,再利用列二分法,找到所在的列。


广告服务联系QQ:1134687142 | 网站地图

版权所有: IT货架- 内容来自互联网,仅供用于技术学习,请遵循相关法律法规. 京ICP备11030978号-1