LintCode-530: Geohash II (System Design 經典題)

This is a followup question for Geohash.

Convert a Geohash string to latitude and longitude.

Try http://geohash.co/.

Check how to generate geohash on wiki: Geohash or just google it for more details.

Example

Example1

Input: “wx4g0s”`

Output: lat = 39.92706299 and lng = 116.39465332

Example2

Input: “w”

Output: lat = 22.50000000 and lng = 112.50000000

解法1：

用一個string base32Map來表示具體編碼就可以了。

比如說11100 -> W, 11101 ->X。

string.find(‘W’)會傳回28, string.find(‘X’)會傳回29。

另外要注意isLongTurn的翻轉是全局有效，而不是僅對某個5-digit的字母有效。

class GeoHash {
public:
    /*
     * @param geohash: geohash a base32 string
     * @return: latitude and longitude a location coordinate pair
     */
    vector<double> decode(string &geohash) {
        string base32Map = "0123456789bcdefghjkmnpqrstuvwxyz";
        vector<double> latitude = {-90, 90};
        vector<double> longitude = {-180, 180};
        bool isLongTurn = true;     //longitude first, then latitude
            
        for (int i = 0; i < geohash.size(); ++i) {

            int val = base32Map.find(geohash[i]);  //position is the value
            
            for (int j = 0; j < 5; ++j) {
                
                if (isLongTurn) {
                
                    if (val & (1 << (4 - j)))
                        longitude[0] = (longitude[0] + longitude[1]) / 2;
                    else         
                        longitude[1] = (longitude[0] + longitude[1]) / 2;
                    
                } else {
                
                    if (val & (1 << (4 - j)))
                        latitude[0] = (latitude[0] + latitude[1]) / 2;
                    else         
                        latitude[1] = (latitude[0] + latitude[1]) / 2;
                
                }
                
                isLongTurn = !isLongTurn;
            }
        }
        
        vector<double> result = {(latitude[0] + latitude[1]) / 2, 
                                 (longitude[0] + longitude[1]) / 2};
        
        return result;
    }
};