class Solution { /** *@param n, m: Two integer *@param i, j: Two bit positions *return: An integer */ public int updateBits(int n, int m, int i, int j) { // write your code here for(int k = i ; k <= j; k++) { n = n & ~(1 << k); // set kth […]
最近看google的s2库, 里面用到了Hilbert Curve的算法, 算法早就忘了, 就记得那个图是以前家里厨房垫脚用的脚垫上面的图案, 当时还说了句, “看来这个设计师还是个数学家”. 先来个图: 是不是很像个迷宫. 这个图乍一看是有逻辑的, 但是很难立刻说出来, 因为上面的图没有划分boarder. 其实左上的图是order/level = 1的Hilbert Curve. 然后是2 3 4 5 6, 我怎么知道的? 先看看介绍: 在那遥远的年代, 18xx年吧..那时候有帮人,在研究: 如何将一个一维空间上的线映射到一个二维空间上, 致使线穿过二维空间上的每个点, 然后不交叉. 这个问题看起来很simple, 但是有好多条件哇, 首先是这个space是continue的, 就是说无限大, 然后线穿过的点要无限的小和无限的多, 也就是说, 你不能数出来这些点有多少, 但是你需要证明你这一条线是肯定穿的过去的.举几个反例: <–这图来自于https://www.youtube.com/watch?v=DuiryHHTrjU 这个视频很好哇 上面的图就不行, 为啥呢? 因为上面的space是由边际的,所以你才知道啥时候拐弯不是么? Hilbert Curve的构建: 先画上面的图1 做4个图1的copy, 然后翻转上面2个. 交叉连接两个脚 继续做2~3步… Hilbert Curve 有很多很好的性质 (那个视频介绍了很多): 连续性: 作为一个continually mapping, Hilbert Curve能准确的:1) […]