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；
[编程题]geohash编码
- 热度指数：18964 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
输入包括一个整数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；
### 思路：
判断一个数在一个区间的左半边还是右半边来给结果字符串添加0还是1，这样重复6次，输出结果。第一反应是使用递归，当累计的递归次数达到6次结束递归，输出结果。
### 代码：
```java
import java.util.Scanner;
import java.util.Arrays;
public class Main{
public static void main(String[]args){
Scanner scan = new Scanner(System.in);
int target = scan.nextInt();
int[]res = new int[6];
StringBuffer sb = new StringBuffer();
process(sb,target,0,-90,90);
String ans = sb.toString();
System.out.println(ans);
}
public static void process(StringBuffer sb, int target, int index, int left, int right){
if(index >= 6){
return;
}
int mid = (left + right)/2;
if(target >= mid){
sb.append("1");
index++;
process(sb,target,index,mid,right);
}else{
sb.append("0");
index++;
process(sb,target,index,left,mid);
}
}
}
```
判断一个数在一个区间的左半边还是右半边来给结果字符串添加0还是1，这样重复6次，输出结果。第一反应是使用递归，当累计的递归次数达到6次结束递归，输出结果。
### 代码：
```java
import java.util.Scanner;
import java.util.Arrays;
public class Main{
public static void main(String[]args){
Scanner scan = new Scanner(System.in);
int target = scan.nextInt();
int[]res = new int[6];
StringBuffer sb = new StringBuffer();
process(sb,target,0,-90,90);
String ans = sb.toString();
System.out.println(ans);
}
public static void process(StringBuffer sb, int target, int index, int left, int right){
if(index >= 6){
return;
}
int mid = (left + right)/2;
if(target >= mid){
sb.append("1");
index++;
process(sb,target,index,mid,right);
}else{
sb.append("0");
index++;
process(sb,target,index,left,mid);
}
}
}
```
发表于 2020-08-10 11:18:00
回复(0)
- 精度为6， 对应right - left >= 5。
- 每次需要记录区间左右端点是开还是闭，二分更新区间后需要更新。
import java.util.*; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); StringBuilder sb = new StringBuilder(); int left = -90, right = 90; // a,b分别记录是否包含左右端点，包含端点为0，不包含为1。 int a = 0, b = 0; while(right - left >= 5) { int mid = (right+left) / 2; if(n >= mid) { left = mid; a = 0; sb.append("1"); } else { right = mid; b = 1; sb.append("0"); } } System.out.println(sb.toString()); } }
编辑于 2020-07-11 14:16:32
回复(0)
public class Main{
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int n = scan.nextInt();
int left=0;
int right;
String str="";
if (n>=0) {
left=0;
right=90;
str+=1;
}
else {
left=-90;
right=0;
str+=0;
}
while (right-left>4) {
int mid=(left+right)/2;
if (mid<=n) {
left=mid;
str+=1;
}
if (mid>n) {
right=mid;
str+=0;
}
}
System.out.println(str);
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int n = scan.nextInt();
int left=0;
int right;
String str="";
if (n>=0) {
left=0;
right=90;
str+=1;
}
else {
left=-90;
right=0;
str+=0;
}
while (right-left>4) {
int mid=(left+right)/2;
if (mid<=n) {
left=mid;
str+=1;
}
if (mid>n) {
right=mid;
str+=0;
}
}
System.out.println(str);
}
}
发表于 2018-10-02 22:58:12
回复(0)
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int a = scanner.nextInt();
System.out.println(encode(a));
}
public static String encode(int a) {
int left = -90;
int right = 90;
StringBuilder sb = new StringBuilder();
while (left < right && sb.length() < 6) {
int mid = (left + right)/2;
if (a < mid) {
right = mid - 1;
sb.append(0);
}else {
left = mid + 1;
sb.append(1);
}
}
return sb.toString();
}
}
发表于 2018-06-05 23:20:53
回复(0)
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Integer input = Integer.parseInt(br.readLine());
int high = 90;
int low = -90;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 6; i++) {
int mid = (high + low) / 2;
if (input >= mid){
sb.append("1");
low = mid;
} else {
sb.append("0");
high = mid;
}
}
System.out.println(sb.toString());
}
}
发表于 2018-03-18 14:02:00
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
getres(n);
}
public static void getres(int n){
int low = -90;
int high = 90;
int mid = 0;
int count = 6;
while (count > 0){
mid = (low + high)/2;
if (n>=mid){
System.out.print(1);
low = mid;
}
else{
System.out.print(0);
high = mid;
}
count--;
}
}
}
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
getres(n);
}
public static void getres(int n){
int low = -90;
int high = 90;
int mid = 0;
int count = 6;
while (count > 0){
mid = (low + high)/2;
if (n>=mid){
System.out.print(1);
low = mid;
}
else{
System.out.print(0);
high = mid;
}
count--;
}
}
}
发表于 2018-03-04 17:06:45
回复(0)
//审题，审题，审题~~注意精度为6
import java.util.*;
public class Main {
private static boolean flagR = true;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int num = in.nextInt();
StringBuilder sb = new StringBuilder();
int left = -90, right = 90;
int mid = (left + right) / 2;
while (isInLeft(num, left, mid) || isInRight(num, mid, right)) {
if (isInLeft(num, left, mid)) {
sb.append(0);
right = mid; flagR = false;
} else if (isInRight(num, mid, right)) {
sb.append(1);
left = mid;
}
if (sb.toString().length() == 6) break;
mid = (left + right) / 2;
}
System.out.println(sb.toString());
}
private static boolean isInLeft(int num, int left, int mid) {
return num >= left && num < mid;
}
private static boolean isInRight(int num, int mid, int right) {
if (flagR)
return num >= mid && num <= right;
else
return num >= mid && num < right;
}
}
编辑于 2017-12-18 21:27:36
回复(0)
import java.util.Scanner; public class Main { public static void main(String args[]) { Scanner scanner = new Scanner(System.in); int min = -90; int max = 90; while (scanner.hasNext()) { int n = Integer.parseInt(scanner.nextLine()); StringBuffer sb = new StringBuffer(); for (int i = 1; i <= 6; i++) { if (n >= (min + max) / 2) { min = (min + max) / 2; sb.append(1); } else { max = (min + max) / 2; sb.append(0); } } System.out.println(sb); } } }这个题蛮简单的，思路很清晰，就是二分法，而且连步数都确定了，基本没什么难点
发表于 2017-11-23 19:58:17
回复(0)
个人做法：进行二分法每次判断n是在哪组，然后输出0/1；这里需要注意的是当区间最大值为负数和为正数时的中间值赋值不一样
import java.util.Scanner;
public class StringUtil{
//gethash编码
public static void main(String[] args){
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int n = in.nextInt();
int l = -90;
int r = 90;
boolean temp = true;
while(temp == true){
int c = r-(r-l)/2;
if(r > 0)
c = (r-l)/2+l;
System.out.println("l="+l+" r="+r+" c="+c+" n="+n);
if(l <= n && c > n){
System.out.print(0);
if(c-l < 6 && r-c < 6)
temp = false;
r = c;
}
else{
System.out.print(1);
if(c-l < 6 && r-c < 6)
temp = false;
l = c;
}
}
}
}
} 到后面发现其实它固定了最终的结果是六位的二进制数，所以就是知道了循环次数，直接for就可以了，不用判断了
发表于 2017-09-07 13:41:14
回复(0)
问题信息
难度：
9条回答
97收藏
14538浏览
通过挑战的用户
查看代码-
2022-10-16 19:32:21
-
2022-10-16 14:19:41 -
2022-10-16 00:16:00
-
2022-10-15 21:15:30 -
2022-10-15 16:46:43
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
