800 Similar RGB Color

800. Similar RGB Color

1. Question

In the following, every capital letter represents some hexadecimal digit from0tof.

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:

• coloris a string of length7.

• coloris a valid RGB color: fori > 0,color[i]is a hexadecimal digit from0tof

• 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.

2. Implementation

思路: 这道题的关键是要知道

(1) RGB三种颜色所对应的hexadecimal是可以分别计算的，也就是从color的第2位开始没隔两位的找出离它们最接近的hexadecimal

(2) 由于题目中表明要找出有shorthand的16进制(RGB三种颜色所对应的16进制数每位都一样，如11，22，ff)，且我们发现这些有shorthand的16进制数每个之间的差刚好等于17，如数组[0, 17, 34, 51 ... 255]，这给我们的启示是给定一个16进制数，将其转为10进制后num, 那么其最接近它的数 应该是在index = num / 17这个位置上，但这里要注意的是，我们还需要检查余数 num % 17, 确保余数是小于8的 (17的一半), 否则index要加1。举个例子，给定10进制数29，index = 29/17 = 1, 但事实上34比17更加接近29

class Solution {
    public String similarRGB(String color) {
        StringBuilder res = new StringBuilder();
        res.append("#");

        for (int i = 1; i < color.length(); i += 2) {
            res.append(getHexDigits(color.charAt(i), color.charAt(i + 1)));
        }
        return res.toString();
    }

    public String getHexDigits(char c1, char c2) {
        int digit1 = Character.isDigit(c1) ? c1 - '0' : 10 + c1 - 'a';
        int digit2 = Character.isDigit(c2) ? c2 - '0' : 10 + c2 - 'a';

        int num = digit1 * 16 + digit2;
        int index = num / 17;
        if (num % 17 > 8) {
            ++index;
        }
        char c = '0';

        if (index >= 10) {
            c = (char)('a' + index - 10);
        }
        else {
            c = (char)('0' + index);
        }
        return String.valueOf(c) + String.valueOf(c);
    }
}

3. Time & Space Complexity

时间复杂度O(n), n是color的长度，但因为color的长度固定为7，所以严格来说时间复杂度是O(1), 同理空间复杂度是O(1)