0800. 相似 RGB 颜色 #

标签：数学、字符串、枚举
难度：简单

题目大意 #

描述：RGB 颜色 "#AABBCC" 可以简写成 "#ABC" 。例如，"#1155cc" 可以简写为 "#15c"。现在给定一个按 "#ABCDEF" 形式定义的字符串 color 表示 RGB 颜色。

要求：返回一个与 color 相似度最大并且可以简写的颜色。

说明：

两个颜色 "#ABCDEF" 和 "#UVWXYZ" 的相似度计算公式为：$-(AB - UV)^2 - (CD - WX)^2 - (EF - YZ)^2$。

示例：

示例 1：

1
2
3


输入 color = "#09f166"
输出 "#11ee66"
解释： 因为相似度计算得出 -(0x09 - 0x11)^2 -(0xf1 - 0xee)^2 - (0x66 - 0x66)^2 = -64 -9 -0 = -73，这是所有可以简写的颜色中与 color 最相似的颜色

解题思路 #

思路 1：枚举算法 #

所有可以简写的颜色范围是 "#000" ~ "#fff"，共 $16^3 = 4096$ 种颜色。因此，我们可以枚举这些可以简写的颜色，并计算出其与 color的相似度，从而找出与 color 最相似的颜色。具体做法如下：

将 color 转换为十六进制数，即 hex_color = int(color[1:], 16)。
三重循环遍历 R、G、B 三个通道颜色，每一重循环范围为 0 ~ 15。
计算出每一种可以简写的颜色对应的十六进制，即 17 * R * (1 << 16) + 17 * G * (1 << 8) + 17 * B，17 是 0x11 = 16 + 1 = 17，(1 << 16) 为 R 左移的位数，17 * R * (1 << 16) 就表示 R 通道上对应的十六进制数。(1 << 8) 为 G 左移的位数，17 * G * (1 << 8) 就表示 G 通道上对应的十六进制数。17 * B 就表示 B 通道上对应的十六进制数。
然后我们根据 color 的十六进制数，与每一个可以简写的颜色对应的十六进制数，计算出相似度，并找出大相似对应的颜色。将其转换为字符串，并输出。

思路 1：枚举算法代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def similar(self, hex1, hex2):
        r1, g1, b1 = hex1 >> 16, (hex1 >> 8) % 256, hex1 % 256
        r2, g2, b2 = hex2 >> 16, (hex2 >> 8) % 256, hex2 % 256
        return - (r1 - r2) ** 2 - (g1 - g2) ** 2 - (b1 - b2) ** 2

    def similarRGB(self, color: str) -> str:
        ans = 0
        hex_color = int(color[1:], 16)
        for r in range(16):
            for g in range(16):
                for b in range(16):
                    hex_cur = 17 * r * (1 << 16) + 17 * g * (1 << 8) + 17 * b
                    if self.similar(hex_color, hex_cur) > self.similar(hex_color, ans):
                        ans = hex_cur
        
        return "#{:06x}".format(ans)