牛客网在线编程题-geohash编码

这是牛客网在线编程题-geohash编码我使用java语言的解答。

题目描述

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)

输出描述

输出二进制编码

示例
输入:

80

输出:

111100

java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
题目本身较为简单,其实就相当于实现了一个二分查找,主要的思想就是只要(右边界-左边界)> 精度就继续循环下去。
*/
import java.io.IOException;
import java.util.Scanner;

public class Main {
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
String result = "";
int left = -90, right = 90, mid = 0;//分别定义左边界,右边界和中间值
while(right - left > 6) { // 根据题目可知精度为6
if (n >= mid) { // 如果在右区间内
result += "1";
left = mid; // 左边界的值为原先的中间值
mid = (right+left) / 2; // 中间值为左右边界和的1/2
}else { // 如果在左区间内
result += "0";
right = mid;
mid = (left+right) / 2;
}
}
System.out.println(result);
}
}
}

本文作者:Qiu Qingyu
版权声明:本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 CN许可协议。转载请注明出处!
本文永久链接:http://qiuqingyu.cn/2017/10/17/牛客网在线编程题-geohash编码/