首页 > 试题广场 >

geohash 编码

[问答题]

geohash 编码： geohash 常用于将二维的经纬度转换为字符串，分为两步：第一步是经纬度的二进制编码，第二部是 base32 转码。

此题考察唯独的二进制编码：算法对维度 [-90,90] 通过二分法进行无限逼近（取决于所需精度，本题精度为 6 ）。注意，本题进行二分法逼近过程中只采用向下取整来进行二分，针对二分中间值属于右区间。算法举例如下：

（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] 进行二分为 [89,84),[84,90] ，可以确定 80 位左区间，标记为 0 ；

（6）针对 [78,84) 进行二分为 [78,81),[81,84) ，可以确定 80 位左区间，标记为 0 ；

已达精度要求，编码为 111100

样本输入： 80

样本输出： 111100

逗比请来的猴子

public class Geohash {
    public String geohash(int n) {
        StringBuilder stringBuilder = new StringBuilder();
        int left = -90;
        int right = 90;
        for (int i = 0; i < 6; i++) {
            int mid = (left + right) / 2;
            if (n < mid) {
                right = mid;
                stringBuilder.append(0);
            } else if (n >= mid) {
                left = mid;
                stringBuilder.append(1);
            }
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args){
        Geohash geohash = new Geohash();
        System.out.println(geohash.geohash(80));
    }
}

发表于 2018-03-25 21:36:27 回复(0)

感性的小鲸鱼少糖去冰

#include<stdio.h>

int main(){

float val=0;

int bin[6];

int min=-90;

int max=90;

scanf("%f",&val);

for(int i=0;i<6;i++){

if((min+max)/2>val){

max=(min+max)/2;

bin[i]=0;

}

else{

min=(min+max)/2;

bin[i]=1;

}

for(int i=0;i<6;i++){

printf("%d",bin[i]);

}

return 0;

}

发表于 2020-02-04 22:18:53 回复(0)

GilgameshCaesar

#include <cstdio>  int main() { int n;  while (~(scanf("%d", &n))) { int left = -90, right = 90;  int mid;  char *str = new char[8];  int count = 0;  do {
            mid = (left + right) / 2;  if (n >= left && n < mid) {
                str[count++] = '0';  right = mid;  } else if (n >= mid && n <= right) {
                str[count++] = '1';  left = mid;  }
        } while (count < 6 && mid != n);  str[count] = '\0';  printf("%s\n", str);  } return 0; }

发表于 2019-03-09 18:24:20 回复(0)

Jackie09

#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int target;
    int min = -90;
    vector<int>flag(0);
    cin >> target;
    vector<int>arr(0);
    for (int i = 0;i < 181;i++)
        arr.push_back(min++);
    vector<int>a(0);
    int mid = 0;
    while (flag.size() != 6)
    {
        mid = (*arr.begin() + *(arr.end()-1)) / 2;
        if (target > mid)
        {
            for (int i = mid;i <= *(arr.end() - 1);i++)
            {
                a.push_back(mid);
                mid++;
            }
            flag.push_back(1);
        }
        else
        {
            vector<int>::iterator itr = arr.begin();
            for (int i = *itr;i < mid;i++)
            {
                a.push_back(*itr);
                itr++;
            }
            flag.push_back(0);
        }
        arr.resize(0);
        for (int i = 0;i < a.size();i++)
            arr.push_back(a[i]);
        a.resize(0);


    }
    for (int i = 0;i < flag.size();i++)
    {
        cout << flag[i];
    }
    return 0;
}

发表于 2018-09-13 19:38:30 回复(0)

成201806061800803

//递归方案，思路，未检验！

#include <iostream>

#include <vector>

using namespace std;

int main(){
int a;

vector<int> res;

cin >> a;

two_sort(-90,90,a,res);

for(auto x:res)

cout << x;

return 0;

}

void two_sort(int left,int right,int sign,vector<int> & res){

if(right - 6 >= left) return;

if(sign >= (left + right)/2){

res.push_back(1);

two_sort((left + right)/2,right,sign,res);

}

else if(sign < (left + right)/2){

res.push_back(0);

two_sort(left,(left + right)/2,sign,res);

}

发表于 2018-08-31 10:48:59 回复(0)

冷静。

#include<iostream>
using namespace std;

char* fun(int x, char *encode)
{
if (encode == NULL || x < -90 || x > 90)
{
return NULL;
}
else
{
int index = 0;
int left = -90;
int right = 90;
int middle = 0;
while (right-left >= 6)
{
middle = (left + right) / 2;
if (middle == x)
{
*(encode + index) = '1';
index++;
break;
}
else if (middle > x)
{
*(encode + index) = '0';
index++;
right = middle;
}
else
{
*(encode + index) = '1';
index++;
left = middle;
}
}
return encode;
}
}

int main()
{
int y;
cin >> y;
char encode[20]={'\0'};
cout<<fun(y,encode)<<endl;
return 0;
}

发表于 2018-08-06 22:34:03 回复(0)

胖哥哥飘过

import java.util.Scanner; public class Main {     public static void count(int target) {         int[] a=new int[6];         int min=-90;         int max=90;         for (int i = 0; i < 6; i++) {             int mid=(min+max)/2;             if (target>mid) {                 a[i]=1;                 min=mid;             }else if(target<mid){                 a[i]=0;                 max=mid;             }         }         for(int i=0;i<6;i++){             System.out.print(a[i]);         }     }     public static void main(String[] args) {         Scanner scanner=new Scanner(System.in);         int target=scanner.nextInt();         count(target);     } }

发表于 2018-04-09 11:48:03 回复(0)

唐唐苦不苦呀

#盗用别人的思路
n = int(raw_input())

degree = list(range(-90,91))
left = 0
right = len(degree) - 1
result = ""
while left <= right:
    mid = (left + right) / 2
    if degree[mid] < n:
        result += '1'
        left = mid + 1
    elif degree[mid] > n:
        result += '0'
        right = mid - 1
    else:
        break
print result

发表于 2018-04-05 15:58:42 回复(0)

qtSunnylove

//AC代码

#include <iostream>

using namespace std;

//判断x属于[left,right]区间的左半边还是右半边
//左返回0，右返回1
int panDuanQuJian(int x,int left,int right)
{
if(x<(left+right)/2)
return 0;
else return 1;
}

int main()
{
int n;
cin>>n;
int res[6];
int left=-90,right=90;
for(int i=0;i<6;i++){
int value=panDuanQuJian(n,left,right);
res[i]=value;
cout<<value;
if(value==1){
left=(left+right)/2;
}
else right=(left+right)/2;
}
cout<<endl;
return 0;
}

发表于 2018-04-05 10:04:08 回复(0)

KeMoing

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class GeoHash {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        List<Integer> list = new ArrayList<>();
        fun(num, list, -90, 90);
        for(int temp : list){
            System.out.print(temp);
        }
    }

    public static void fun(int num, List<Integer> list, int start, int end) {
        int count = 0;
        while (count < 6) {
            int mid = (start + end + 1) / 2;
            if (num >= start && num <= mid - 1) {
                list.add(0);
                end = mid - 1;
            } else if (num >= mid && num <= end) {
                list.add(1);
                start = mid;
            }
            else{
                break;
            }
            count++;
        }
    }
}

发表于 2018-04-04 23:34:08 回复(0)

星空加微风

#pragma warning(disable:4996)
#include <stdio.h>
#include<iostream>
#include<vector>

using namespace std;
using std::cout;
using std::cin;
using std::vector;

void geohash(int& leftpoint, int& rightpoint, int num, bool& findnum, vector<int>& vec)
{
    int middlenum = leftpoint + (rightpoint - leftpoint) / 2;
    if (middlenum == num)
    {
        findnum = true;
    }
    if (num < middlenum)
    {
        vec.push_back(0);
        rightpoint = middlenum;
    }
    else {
        vec.push_back(1);
        leftpoint = middlenum;
    }
}

int main()
{
    int leftpoint = -90, rightpoint = 90;
    int num;
    bool findnum = false;
    vector<int> vec;
    while (cin >> num)
    {
        if (num > rightpoint || num<leftpoint)
            return 0;
        while (rightpoint - leftpoint >= 6|| findnum == true)
        {
            geohash(leftpoint, rightpoint, num, findnum,vec);
        }
        for (vector<int>::iterator rvec = vec.begin(); rvec != vec.end(); rvec++)
        {
            cout << *rvec;
        }
        cout << '\n';

    }
    system("pause");
    return 0;
}

发表于 2018-04-04 10:09:52 回复(0)

.20180322150443

#include<iostream>

#include<vector>

using namespace std;

int main()

{

  int n;
    cin >> n;
    std::vector<int> code;
    int lb = -90, rb = 90;
    while (code.size()<6)
    {
        int mid = (lb + rb) / 2;
        if (n<mid)
        {
            code.push_back(0);
            rb = mid;
        }
        else {
            code.push_back(1);
            lb = mid;
        }
    }
    for (int i = 0; i<code.size(); i++)
        cout << code[i];

return 0;

{

发表于 2018-04-02 00:07:30 回复(0)

浪漫巴黎

import java.util.Scanner;

public class Tencent01 {
public static void main(String[] args) {
    Scanner in=new Scanner(System.in);
    int W;
    W=in.nextInt();
    int left=-90;
    int right=90;
    StringBuilder stringBuilder=new StringBuilder();
    for(int i=0;i<6;i++){
        int mid=(left+right)/2;
        if (W<mid) {
            right=mid;
            stringBuilder.append(0);
        }else if (mid<=W) {
            stringBuilder.append(1);
            left=mid;
        }


    }
    System.out.println(stringBuilder.toString());
}
}

发表于 2018-04-01 20:16:47 回复(0)

肥圆四叶

#include<cmath>
#include<iostream>
#include<string>
using namespace std;

static int n = 0;
static string s = "";
void fuc(int l, int r, int x) {
    int mid = (l + r) / 2;
    if (x >= mid) {
        s += "1";
        n++;
        if (n == 6)
            return;
        else
            fuc(mid, r, x);
    }
    else if (x < mid) {
        s += "0";
        n++;
        if (n == 6)
            return;
        else
            fuc(l, mid, x);
    }
}

int main() {
    int x;
    cin >> x;
    fuc(-90, 90, x);
    cout << s;
    system("pause");
    return 0;
}

发表于 2018-01-23 00:26:19 回复(0)

NodYoung

import sys

input_num = int(sys.stdin.readline().strip('\n'))

degree=list(range(-90,91))
begin=0 end=len(degree)-1 result=[] while begin<=end:
    mid = int((begin+end)/2) if degree[mid]<input_num:
        result.append(1)
        begin=mid+1  elif degree[mid]>input_num:
        result.append(0)
        end=mid-1  else: break  print(result)

发表于 2017-09-01 00:37:01 回复(0)

牛客2482637号

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <set>
using namespace std;

void GetGeohash(int num, int left, int right, int& precision, vector<int>& vec)
{
	if( num < left || num > right || precision == 0 )
		return;

	int middle = ( left + right ) >> 1;
	if( num >= middle ){
		vec.push_back(1);
		--precision;
		left = middle;
	}
	else if( num < middle ){
		vec.push_back(0);
		--precision;
		right = middle;
	} 

	GetGeohash(num, left, right, precision, vec);

}

void geohash(int num, int precision = 6, int left = -90, int right = 90)
{
	if( num < left || num > right )
		return;

	vector<int> result;

	GetGeohash(num, left, right, precision, result);

	for( int i = 0; i < result.size(); i++ )
		cout << result[i];
	cout << endl;

}
int main()
{
    int num;
    cin >> num;
    geohash(num);

    return 0;
}

发表于 2017-08-27 21:59:36 回复(0)

Fu师傅啊

def binary_search(n):
    n = int(n) if n > 90 or n < -90: return False  mid = 0  high = 90  low = -90  arry_code = [] for i in range(6): if n >= mid:
            low = mid
            mid = (high + mid)/2   #mid = (high + low)/2  arry_code.append(1) elif n < mid:
            high = mid
            mid = (low + high)/2  arry_code.append(0) return arry_code def main():
    n = int(input()) print((''.join(map(str,binary_search(n)))))
main()

发表于 2017-08-23 20:55:26 回复(0)

斗战胜宝

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		if (n < -90 || n > 90) {
			return;
		}
		ArrayList<Integer> list = new ArrayList<Integer>();
		list = binSearch(list, n, -90, 90);
		for (int ele : list) {
			System.out.print(ele);
		}
	}
	//二分查找
	public static ArrayList<Integer> binSearch(ArrayList<Integer> list, int n,int start, int end) {
		int mid = (start + end) / 2;
		if (end - start >= 6) {//取决于所需精度，本题精度为 6,所以>=6就继续 递归思想
			if (n >= mid) {//二分中间值属于右区间
				list.add(1);
				binSearch(list, n, mid, end);
			} else {
				list.add(0);
				binSearch(list, n, start, mid);
			}
		}
		return list;
	}
}

发表于 2017-08-23 14:27:45 回复(0)

牛客3897179号

#include <iostream>

#include <string>

using namespace std;

string Solve(int n)

{

string ret;

int start = -90;

int end = 90;

int mid = 0;

for (int i = 0; i < 6 && start < end; i++)

{

mid = start + (end - start)/2;

if (n < mid)

{

end = mid;

ret += "0";

}

else

{

start = mid;

ret += "1";

}

return ret;

}

int main()

{

int n = 0;

cin >> n;

cout << Solve(n) << endl;

system("pause");

return 0;

}

发表于 2017-08-21 11:04:20 回复(0)

啊啊啊62

public void myMethod(int N)

{

int high=90;

int low=-90;

int mid;

String result="";

for(int i=0; i<6; i++)

{

mid=(high+low)/2;

if(N>=mid)

{

result+='1';

low=mid;

}

else

{

result+='0';

high=mid;

}

System.out.println(result);

}

发表于 2017-08-20 18:59:27 回复(0)

提交观点

问题信息

Python

来自：腾讯2017校招开发工...

上传者：牛100

难度：

22条回答 104收藏 4581浏览

geohash 编码

问题信息

热门推荐

相关试题