Google
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"
1
Example 1:
2
Input:
3
color = "#09f166"
4
5
Output: "#11ee66"
6
7
Explanation:
8
The similarity is -(0x09 - 0x11)^2 -(0xf1 - 0xee)^2 - (0x66 - 0x66)^2 = -64 -9 -0 = -73.
9
This is the highest among any shorthand color.
Copied!
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
1
class Solution {
2
public String similarRGB(String color) {
3
StringBuilder res = new StringBuilder();
4
res.append("#");
5
6
for (int i = 1; i < color.length(); i += 2) {
7
res.append(getHexDigits(color.charAt(i), color.charAt(i + 1)));
8
}
9
return res.toString();
10
}
11
12
public String getHexDigits(char c1, char c2) {
13
int digit1 = Character.isDigit(c1) ? c1 - '0' : 10 + c1 - 'a';
14
int digit2 = Character.isDigit(c2) ? c2 - '0' : 10 + c2 - 'a';
15
16
int num = digit1 * 16 + digit2;
17
int index = num / 17;
18
if (num % 17 > 8) {
19
++index;
20
}
21
char c = '0';
22
23
if (index >= 10) {
24
c = (char)('a' + index - 10);
25
}
26
else {
27
c = (char)('0' + index);
28
}
29
return String.valueOf(c) + String.valueOf(c);
30
}
31
}
Copied!

3. Time & Space Complexity

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