QQ6. geohash编码
描述
geohash编码:geohash常用于将二维的经纬度转换为字符串,分为两步:第一步是经纬度的二进制编码,第二步是base32转码。输入描述
输入包括一个整数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; }