Lintcode 529. Geohash

Geohash is a hash function that convert a location coordinate pair into a base32 string.

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

Try http://geohash.co/.

You task is converting a (latitude, longitude) pair into a geohash string.

Example

Example1

Input: 
lat = 39.92816697 
lng = 116.38954991
precision = 12 
Output: "wx4g0s8q3jf9"

Example2

Input: 
lat = -90
lng = 180
precision = 12 
Output: "pbpbpbpbpbpb"

Notice

1 <= precision <=12

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

public class GeoHash {     /*      * @param latitude: one of a location coordinate pair      * @param longitude: one of a location coordinate pair      * @param precision: an integer between 1 to 12      * @return: a base32 string      */     public String encode(double latitude, double longitude, int precision) {         // write your code here         int len = (precision * 5) % 2 == 0 ? precision * 5 / 2 : precision * 5 / 2 + 1;         String latStr = generateCode(latitude, -90, 90, len);         String longStr = generateCode(longitude, -180, 180, len);                   String geoHashCode = getGeoHash(latStr, longStr);         StringBuilder finalCode = new StringBuilder();           String dict = "0123456789bcdefghjkmnpqrstuvwxyz";           for (int i = 0; i <= geoHashCode.length() - 5; i += 5) {             int num = 0;             for (int j = i; j < i + 5; j++) {                 num = num * 2 + Character.getNumericValue(geoHashCode.charAt(j));             }               finalCode.append(dict.charAt(num));         }           return finalCode.toString();     }       private String generateCode(double loc, double start, double end, int len) {         StringBuilder sb = new StringBuilder();         for (int i = 0; i < len; i++) {             double mid = start + (end - start) / 2;             if (loc <= mid) {                 sb.append('0');                 end = mid;             } else {                 sb.append('1');                 start = mid;             }         }           return sb.toString();     }       private String getGeoHash(String latitude, String longtitude) {         StringBuilder sb = new StringBuilder();         for (int i = 0; i < longtitude.length(); i++) {             sb.append(longtitude.charAt(i));             sb.append(latitude.charAt(i));         }           return sb.toString();     } }