列表

详情


QQ6. geohash编码

描述

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;

原站题解

C++ 解法, 执行用时: 1ms, 内存消耗: 220KB, 提交时间: 2017-07-21

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

int main()
{
	int n;
	while (cin >> n && n >= -90 && n <= 90)
	{
		string code = "";
		int low = -90, high = 90;
		while (high - low >= 5){
			int mid = (high + low) / 2;
			if (n >= low&&n < mid){
				code += "0";
				high = mid;
			}
			else if (n >= mid&&n <= high){
				code += "1";
				low = mid;
			}
		}
		if (code != "")cout << code << endl;
	}
	return 0;
}

C++ 解法, 执行用时: 1ms, 内存消耗: 368KB, 提交时间: 2017-08-10

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <unordered_set>

using namespace std;


int main() {
    int n;
    while (cin >> n) {
        int high = 90, low = -90;
        vector<int> ans;
        for (int i = 0; i < 6; ++i) {
            int mid = (low + high) / 2;
            if (n >= mid) {
                ans.push_back(1);
                low = mid;
            } else {
                ans.push_back(0);
                high = mid;
            }
        }
        for (auto x:ans) cout << x;
        cout << endl;
    }
    return 0;
}

C++ 解法, 执行用时: 1ms, 内存消耗: 368KB, 提交时间: 2017-07-30

#include<iostream>
int main()
{
	int x1 = -90, x2 = 90;
	int x = 0;
	std::cin >> x;

	char bits[7] = {};
	for (int i = 0; i < 6; ++i)
	{
		int mid = (x1 + x2) / 2;
		if (x < mid)
		{
			x2 = mid;
			bits[i] = '0';
		}
		else
		{
			x1 = mid;
			bits[i] = '1';
		}
	}

	std::cout << bits << std::endl;
}

C++ 解法, 执行用时: 1ms, 内存消耗: 368KB, 提交时间: 2017-07-29

#include <iostream> 
  using namespace std; 
  int main(){ 
      int n; 
      cin>>n; 
      int low=-90,high=90; 
      while((high-low)>=5){ 
          int mid=(low+high)/2; 
          if(mid<=n){ 
              low=mid; 
              cout<<1; 
          } 
          else{ 
              high=mid; 
              cout<<0; 
          } 
      } 
      return 0; 
  }

C++ 解法, 执行用时: 1ms, 内存消耗: 368KB, 提交时间: 2017-07-27

#include <iostream>
using namespace std;

int main()
{
	int n;
	while (cin>>n)
	{
		int cnt = 1, a = 0, b = 90;
		if (n >= 0)
		{
			cout << 1;
			int Mid = (a + b) / 2;
			while (cnt < 6)
			{
				if (n >= Mid)
				{
					cout << 1;
					a = Mid;
				}
				else
				{
					cout << 0;
					b = Mid;
				}
				++cnt;
				Mid = (a + b) / 2;
			}
		}
		else
		{
			n = -n;
			cout << 0;
			int Mid = (a + b) / 2;
			while (cnt < 6)
			{
				if (n > Mid)
				{
					cout << 0;
					a = Mid;
				}
				else
				{
					cout << 1;
					b = Mid;
				}
				++cnt;
				Mid = (a + b) / 2;
			}
		}
		cout << endl;
	}
	return 0;
}

上一题