首页 > 试题广场 >

geohash编码

[编程题]geohash编码
  • 热度指数：18964 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
geohash编码：geohash常用于将二维的经纬度转换为字符串，分为两步：第一步是经纬度的二进制编码，第二步是base32转码。
此题考察纬度的二进制编码：算法对纬度[-90, 90]通过二分法进行无限逼近（取决于所需精度，本题精度为6）。注意，本题进行二分法逼近过程中只保留整数部分而忽略掉小数部分（也即抹去小数部分）来进行二分，针对二分中间值属于右区间。算法举例如下： 针对纬度为80进行二进制编码过程：
1) 区间[-90, 90]进行二分为[-90, 0),[0, 90]，成为左右区间，可以确定80为右区间，标记为1；
2) 针对上一步的右区间[0, 90]进行二分为[0, 45),[45, 90]，可以确定80是右区间，标记为1；
3) 针对[45, 90]进行二分为[45, 67),[67,90],可以确定80为右区间，标记为1；
4) 针对[67,90]进行二分为[67, 78),[78,90]，可以确定80为右区间，标记为1；
5) 针对[78, 90]进行二分为[78, 84),[84, 90]，可以确定80为左区间，标记为0；
6) 针对[78, 84)进行二分为[78, 81), [81, 84)，可以确定80为左区间，标记为0；

输入描述:
输入包括一个整数n,(-90 ≤ n ≤ 90)


输出描述:
输出二进制编码
示例1

输入

80

输出

111100
示例2

输入

-66

输出

001000

说明

1) 区间[-90, 90]进行二分为[-90, 0),[0, 90]，成为左右区间，可以确定-66在左区间，标记为0；
2) 针对上一步的左区间[-90, 0)进行二分为[-90, -45),[-45, 0)，可以确定-66在左区间，标记为0；
3) 因(-90-45)/2=-135/2=-67.5，只取整数部分可得-67，所以针对[-90, -45)进行二分为[-90, -67),[-67,-45),可以确定-66在右区间，标记为1；
4) 针对[-67,-45)进行二分为[-67, -56),[-56,-45]，可以确定-66在左区间，标记为0；
5) 因(-67-56)/2=-123/2=-61.5，只取整数部分可得-61，所以针对[-67, -56)进行二分为[-67, -61),[-61, -56]，可以确定-66在左区间，标记为0；
6) 针对[-67, -61)进行二分为[-67, -64), [-64, -61)，可以确定-66在左区间，标记为0；
算法知识视频讲解
添加回答
JavaScript
Williammm头像 Williammm 
var n = parseInt(readline())
var start = -90
var end = 90
var result = ""
for(var i =0;i<6;i++){
    var mid = parseInt((start+end)/2)
    if(n<mid){
        result+="0"
        end = mid
    }
    if(n>=mid){
        result+="1"
        start = mid
    } 
        
}
console.log(result)

发表于 2021-08-28 17:36:21 回复(0)
JavaScript
是函数不是方法头像 是函数不是方法 

var number = +(readline());//获取数字 function f(num){     var arr = []; var qujian1 = 90;
    var qujian2 = -90;
    var mid = parseInt((qujian1+qujian2)/2);
    while((qujian1-qujian2) >= 5){
        if(num>=mid){
            arr.push(1);
            qujian2 = mid;
        }else{
            arr.push(0);
            qujian1 = mid;
        }
        mid = parseInt((qujian1+qujian2)/2);
    }
    console.log(arr.join(""));
}
f(number);
就算通过了我也非常想问= =为啥必须区间之差为5啊，为啥6不行，按道理来讲应该是6才对吧。
发表于 2018-07-14 22:35:23 回复(0)
JavaScript
静水深流828头像 静水深流828
var readline = require('readline');
//创建readline接口实例
var ri = readline.createInterface({
    input: process.stdin,
    output: process.stdout

});
//读取每行的数据，并进行相应的操作
ri.on('line',function(data) {
    //var arr = data.trim().split('');
    var n=parseInt(data);
    var f=-90;
    var last=90;
    var m=0;
    var a=[];
    while(a.length!=6){
        if(n>=m){
            f=m;
            a.push(1);
            m=Math.floor((f+last)/2);
        }else if(n<m){
            last=m;
            a.push(0);
            m=Math.floor((f+last)/2);
        }
    }
    console.log(a.join(""));

});
您提交的程序没有通过所有的测试用例
case通过率为90.00%
测试用例:
-66
对应输出应该为:
001000
你的输出为:
001001
不知道哪里错了
发表于 2017-08-13 18:02:22 回复(1)
提交观点

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 腾讯 模拟 Java工程师
难度：
3条回答 14535浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号