相似的RGB颜色——算法面试刷题3(for google),考察二分

时间:2023-12-09 16:29:55

在本题中,每个大写字母代表从“0”到“f”的一些十六进制数字。

红绿蓝三元色#AABBCC可以简写为#ABC。 例如,#15c是颜色#1155cc的简写。

现在,假设两种颜色#ABCDEF#UVWXYZ之间的相似性是-(AB - UV) ^ 2 - (CD - WX) ^ 2 - (EF - YZ) ^ 2

给定颜色#ABCDEF,返回与#ABCDEF最相似且含有一个简写的7字符颜色(也就是说,它可以用类似#XYZ的形式表示)。

  • color 是一个长度为7的字符串。
  • color 是一个合法的RGB颜色: 对于每一个 i > 0, color[i] 是一个 0f的十六进制数字。
  • 任何一个有最高相似度的答案都是正确的。
  • 所有的输入输出都是小写字母,输出应为7个字符的字符串。
您在真实的面试中是否遇到过这个题?  

样例

样例1:

输入: color = "#09f166"
输出: "#11ee66"
解释:
二者相似程度为 -(0x09 - 0x11)^2 -(0xf1 - 0xee)^2 - (0x66 - 0x66)^2 = -64 -9 -0 = -73.
这是所有能够简写的颜色里最接近的颜色。

样例2:

输入: color = "#010000"
输出: "#000000"
解释:
二者相似程度为 -(0x01 - 0x10)^2 -(0x00 - 0x00)^2 - (0x00 - 0x00)^2 = -1 -0 -0 = -1.
这是所有能够简写的颜色里最接近的颜色。 我的代码:
class Solution:
"""
@param color: the given color
@return: a 7 character color that is most similar to the given color
"""
def similarRGB(self, color):
# Write your code here
ans = "#"
for i in (1, 3, 5):
s = self.find_nearest_color(color[i:i+2])
ans += s
return ans def to_hex(self, i):
return hex(i)[2:] def find_nearest_color(self, hex_color):
arr = [0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77, 0x88, 0x99, 0xaa, 0xbb,
0xcc, 0xdd, 0xee, 0xff]
hex_color = int(hex_color, 16)
l, r = 0, len(arr)-1
while l+1 < r:
mid = (l+r)//2
if arr[mid] <= hex_color:
l = mid
else:
r = mid
if arr[l] == hex_color:
return self.to_hex(arr[l])
elif arr[r] == hex_color:
return self.to_hex(arr[r])
else:
if abs(arr[l]-hex_color) < abs(arr[r]-hex_color):
return self.to_hex(arr[l])
else:
return self.to_hex(arr[r])

参考代码:

class Solution:
"""
@param color: the given color
@return: a 7 character color that is most similar to the given color
"""
#形如AA的十六进制数必定是17的倍数,我们只要判断离原数最接近的17的倍数是多少即可。
def similarRGB(self, color):
# Write your code here
def geClosest(s):
return min(['00', '11', '22', '33', '44', '55', '66', '77', '88', '99', 'aa', 'bb', 'cc', 'dd', 'ee', 'ff'],
key=lambda x: abs(int(s, 16) - int(x, 16))) res = [geClosest(color[i:i+2]) for i in range(1, len(color), 2)]
return '#' + ''.join(res)

值得学习的地方:

1、直接暴力,使用min

2、字符串拼接join