SimilarRGBColor [source code]

public class SimilarRGBColor {
static
/******************************************************************************/
class Solution {
    public String similarRGB(String color) {
        String[] vals = {getClosest (color.substring (1, 3)), getClosest (color.substring (3, 5)), getClosest (color.substring (5, 7))};
        return String.format ("#%s%s%s%s%s%s", vals[0], vals[0], vals[1], vals[1], vals[2], vals[2]);
    }

    String getClosest (String s) {
        int val = Integer.parseInt (s, 16);
        int min_square = Integer.MAX_VALUE, min_num = -1;
        for (int i = 0; i < 16; i++) {
            int cur_square = Math.abs (i * 16 + i - val);
            if (cur_square < min_square) {
                min_square = cur_square;
                min_num = i;
            }
        }
        return Integer.toString (min_num, 16);
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SimilarRGBColor.Solution tester = new SimilarRGBColor.Solution();
        String[] inputs = {
            "#09f166", "#11ee66",
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            System.out.println (Printer.separator ());
            String color = inputs[2 * i], ans = inputs[2 * i + 1], output = tester.similarRGB (color);
            System.out.printf ("%s\n%s, expected: %s\n", 
                color, Printer.wrap (output, output.equals (ans) ? 92 : 91), ans
            );
        }
    }
}

一开始题目有问题, 最后几乎所有人都有至少一个bug;

速度49ms (NA);

editorial

Approach #1: Brute Force [Accepted]

Intuition

For each possible shorthand-RGB color from "#000" to "#fff", let's find it's similarity to the given color. We'll take the best one.

Algorithm

This problem is straightforward, but there are a few tricky implementation details.

To iterate over each shorthand color, we'll use an integer based approach, (though other ones exist.) Each digit in the shorthand "#RGB" could be from 0 to 15. This leads to a color of 17 R (1 << 16) + 17 G (1 << 8) + 17 B. The reason for the 17 is because a hexadecimal value of 0x22 is equal to 2 16 + 2 1 which is 2 (17). The other values for red and green work similarly, just shifted up by 8 or 16 bits.

这里这个17没有看懂; 为什么你所有的地方都加上一个17的因子, 最后就不用担心17的问题了? 0x22多了这个17之后, 不还是变成了17 2 17, 这个有什么区别吗, 跟之前?

To determine the similarity between two colors represented as integers, we'll sum the similarity of each of their colored components separately. For a color like hex1, it has 3 colored components r1 = (hex1 >> 16) % 256, g1 = (hex1 >> 8) % 256, b1 = (hex1 >> 0) % 256. Then, the first addend in the similarity is -(r1 - r2) * (r1 - r2), etc.

To convert an integer back to a hex string, we'll use String.format. The 06 refers to a zero padded string of length 6, while x refers to lowercase hexadecimal.

Finally, it should be noted that the answer is always unique. Indeed, for two numbers that differ by 17, every integer is closer to one than the other. For example, with 0 and 17, 8 is closer to 0 and 9 is closer to 17 - there is no number that is tied in closeness.

这个的意思就是不可能有tie的情况;

class Solution {  
    public String similarRGB(String color) {  
        int hex1 = Integer.parseInt(color.substring(1), 16);  
        int ans = 0;  
        for (int r = 0; r < 16; ++r)  
            for (int g = 0; g < 16; ++g)  
                for (int b = 0; b < 16; ++b) {  
                    int hex2 = 17 * r * (1 << 16) + 17 * g * (1 << 8) + 17 * b;  
                    if (similarity(hex1, hex2) > similarity(hex1, ans))  
                        ans = hex2;  
                }  

        return String.format("#%06x", ans);  
    }  

    public int similarity(int hex1, int hex2) {  
        int ans = 0;  
        for (int shift = 16; shift >= 0; shift -= 8) {  
            int col1 = (hex1 >> shift) % 256;  
            int col2 = (hex2 >> shift) % 256;  
            ans -= (col1 - col2) * (col1 - col2);  
        }  
        return ans;  
    }  
}

总体来说这个方法还是很奇怪的; 他这个方法是整个都看成是一个integer来处理, 然后循环range找到最相似的一个; 而我的方法是分别对每一个digit找到最相似的:

For Brute Force, do we really need 3 loop?

To get a a+b b+c * c smallest, we can make sure a, b, c itself is the smallest.

So we can lower the complexity from O(16 16 16) to O(3 * 16).

Yes, both are O(1). But the latter one looks better.

这个解释非常的合理; 一个是乘法, 一个是加法;

这个17还是想不通; 那就不要浪费时间了, 直接就试一试这个17是不是必须的就行了;

改成1之后:

Input:  
"#09f166"  
Output:  
"#090f0f"  
Expected:  
"#11ee66"

哦, 理解了, 里面的r, g, b这三个数字的循环, 循环的其实是一个数字; 而我们最后计算的时候, 是要计算, 比如你b选择的是2, 你最后实际上要比较的是0x22和原来的数字对应的部分的差距, 而不是0x2; 所以这个17并不是一个什么hack, 而是这里两个digit的duplicate对应的东西而已;

总体还行的一个做法;

Approach #2: Rounding By Component [Accepted]

Intuition and Algorithm

Because color similarity is a sum of the similarity of individual color components, we can treat each colored component separately and combine the answer.

As in the previous approach, we want the colored component to be the closest to a multiple of 17. We can just round it to the closest such value.

class Solution {  
    public String similarRGB(String color) {  
        return "#" + f(color.substring(1, 3)) + f(color.substring(3, 5)) + f(color.substring(5));  
    }  

    public String f(String comp) {  
        int q = Integer.parseInt(comp, 16);  
        q = q / 17 + (q % 17 > 8 ? 1 : 0);  
        return String.format("%02x", 17 * q);  
    }  
}

原来这个分开component的办法他还是想到了, 而且因为上一个算法当中意识到这个17的重要性, 这题直接只要考虑

大概就是这个计算方式, 更深刻的解释实际上我也说不出来;

https://leetcode.com/problems/similar-rgb-color/discuss/119876/C++-Solution-easy-to-understand-8ms

class Solution {  
public:  
    string similarRGB(string color) {  
        string res = "#";  
        string digits = "0123456789abcdef";  
        map<char, int> code;  
        for (int i = 0; i < digits.length(); i ++){  
            code[digits[i]] = i;  
        }         
        for (int i = 1; i <= 5; i += 2 ) {  
            long distance = INT_MAX;  
            vector<string> candidates;  
            string winner;  
            candidates.push_back(string(2, color[i]));  
            if (color[i] != '0') candidates.push_back(string(2, digits[code[color[i]] - 1]));  
            if (color[i] != 'f') candidates.push_back(string(2, digits[code[color[i]] + 1]));  
            for (string s : candidates) {       
                long dis = abs (16 * (code[s[0]] - code[color[i]]) + (code[s[1]] - code[color[i + 1]]));  
                if (dis < distance) {  
                    winner = s;  
                    distance = dis;  
                }  
            }  
            res += winner;  
        }          
        return res;  
    }  
};

HEX向DEC的转换还要手动自己建立反向lookup, 这个可以说是很姜了;

反正是没什么意思的方法吧, 包括这里i实际上只有1,3,5三个值, 也要用一个循环来写;

没有大概看了, 不过他这里的思想还是理解了, 有点意思的一个地方是, 他每一个component只有三个candidate: 大概意思就是比如你这个component是0x81, 那么他只考虑, 0x77, 0x88, 0x99这三个;

这个想法本身还是有点意思的;

https://leetcode.com/problems/similar-rgb-color/discuss/119844/Concise-java-solution

public String similarRGB(String color) {  
    StringBuilder sb = new StringBuilder(color.length());  
    sb.append("#");  
    for (int i = 1; i < color.length(); i += 2){  
        sb.append(getHexDigits(color.charAt(i), color.charAt(i + 1)));  
    }  
    return sb.toString();  
}  

private String getHexDigits(char c1, char c2){  
    int d1 = Character.isDigit(c1)? c1 - '0': 10 + c1 - 'a';  
    int d2 = Character.isDigit(c2)? c2 - '0': 10 + c2 - 'a';  

    int sum       = d1 * 16 + d2;  
    int index     = sum / 17; // [ 0x00(0) , 0x11(17), 0x22(34),  0x33(51), ........., 0xff(255) ]  
    int remainder = sum % 17;  
    if (remainder > 8){  
        index++;  
    }  

    char c = 0 <= index && index <= 9? (char)('0' + index): (char)('a' + index - 10);  
    return String.valueOf(c) + String.valueOf(c);  
}

怎么都特么喜欢手动parse HEX;

基本思路其实跟awice的第二个方法是类似的, 不过各种手动parse搞得代码看起来很乱;

maybe it is clearer
if if (remainder > 17 / 2){
index++;
}
for example, let’s say index is 0 , meaning sum falls in [0x00(0) , 0x11(17)], then we need to determine whether sum is closer to 0x00 or sum is closer to 0x11 by checking whether or not remainder is greater than half of (0x11 - 0x00).

这个讲的没问题;

submission:

contest:

class Solution {  
    public String similarRGB(String color) {  
        String s="0123456789abcdef";  
        int r=Integer.parseInt(color.substring(1,3),16);  
        int g=Integer.parseInt(color.substring(3,5),16);  
        int b=Integer.parseInt(color.substring(5,7),16);  
        int ans=100000000,ansr=0,ansb=0,ansg=0;  
        for (int rr=0;rr<=15;rr++)  
        for (int gg=0;gg<=15;gg++)  
        for (int bb=0;bb<=15;bb++)  
        {  
            int r2=rr*17,b2=bb*17,g2=gg*17;  
            int now=(r-r2)*(r-r2)+(b-b2)*(b-b2)+(g-g2)*(g-g2);  
            if (now<ans)  
            {  
                ans=now;  
                ansr=rr;  
                ansb=bb;  
                ansg=gg;  

            }  
        }  
        return "#"+s.charAt(ansr)+s.charAt(ansr)+s.charAt(ansg)+s.charAt(ansg)+s.charAt(ansb)+s.charAt(ansb);  
    }  
}

随便看的一个, 这次contest uwi没有打;

这个应该就是一个普通的暴力算法;

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

Difficulty:Easy
Total Accepted:2.1K
Total Submissions:3.9K
Contributor:awice
Companies
google
Related Topics
mathstring