800. Similar RGB Color

Description

In the following, every capital letter represents some hexadecimal digit from 0 to f.

The red-green-blue color "#AABBCC" can be written as "#ABC" in shorthand. For example, "#15c" is shorthand for the color "#1155cc".

Now, say the similarity between two colors "#ABCDEF" and "#UVWXYZ" is -(AB - UV)^2 - (CD - WX)^2 - (EF - YZ)^2.

Given the color "#ABCDEF", return a 7 character color that is most similar to #ABCDEF, and has a shorthand (that is, it can be represented as some "#XYZ"

Example 1:
Input: color = "#09f166"
Output: "#11ee66"
**Explanation: **
The similarity is -(0x09 - 0x11)^2 -(0xf1 - 0xee)^2 - (0x66 - 0x66)^2 = -64 -9 -0 = -73.
This is the highest among any shorthand color.

Note:

• color is a string of length 7.
• color is a valid RGB color: for i > 0, color[i] is a hexadecimal digit from 0 to f
• Any answer which has the same (highest) similarity as the best answer will be accepted.
• All inputs and outputs should use lowercase letters, and the output is 7 characters.

Solution

Math, O(1), S(1)

这道题需要将color转换成离它距离最近的shorthand color。很容易可以想到，两位两位单独处理，最后将结果combine在一起。

找规律可以发现：
[ 0x00(0) , 0x11(17), 0x22(34), 0x33(51), ........., 0xff(255) ]
所求均是17的倍数。

所以可以先计算出某两位16进制对应的10进制val，然后与17进行计算，取最接近的即可。

另外还要注意运用java内置的进制转换api，很方便。

class Solution {
    public String similarRGB(String color) {
        StringBuilder sb = new StringBuilder();
        sb.append("#");
        
        for (int i = 1; i < color.length(); i += 2) {
            sb.append(findClosest(color.substring(i, i + 2)));
        }
        
        return sb.toString();
    }
    
    private String findClosest(String s) {
        int val = Integer.parseInt(s, 16);
        val = val / 17 + (val % 17 > 8 ? 1 : 0);
        return Integer.toHexString(17 * val);
    }
}