lintcode 1017 · 相似的RGB颜色【进制计算】

题目链接，题目描述

https://www.lintcode.com/problem/1017

在本题中，每个大写字母代表从“0”到“f”的一些十六进制数字。红绿蓝三元色#AABBCC可以简写为#ABC。 例如，#15c是颜色#1155cc的简写。现在，定义两种颜色#ABCDEF和#UVWXYZ之间的相似度是abs((AB - UV)^2 + (CD - WX)^2 + (EF - YZ)^2)。给定颜色#ABCDEF，返回与#ABCDEF最相似（即相似度最小）且可以简写表示的7字符颜色（也就是说，它可以用类似#XYZ的形式表示）。color 是一个长度为7的字符串。
color 是一个合法的RGB颜色: 对于每一个 i > 0, color[i] 是一个 0 到 f的十六进制数字。
任何一个有最高相似度的答案都是正确的。
所有的输入输出都是小写字母，输出应为7个字符的字符串。
样例
样例 1：输入：color = "#09f166"
输出："#11ee66"
解释：二者相似程度为 -(0x09 - 0x11)^2 -(0xf1 - 0xee)^2 - (0x66 - 0x66)^2 = -64 -9 -0 = -73.
这是所有能够简写的颜色里最接近的颜色。样例 2：输入：color = "#010000"
输出："#000000"
解释：二者相似程度为 -(0x01 - 0x00)^2 -(0x00 - 0x00)^2 - (0x00 - 0x00)^2 = -1 -0 -0 = -1.
这是所有能够简写的颜色里最接近的颜色。

思路，以及疑惑的地方

题目描述中给的公式是每2位平方相加。给的例子确是相减。看了其他题解，才知道是是相加。 其他题解全是用的工具类库，比如 int q = Integer.parseInt(comp, 16); return String.format("%02x", 17 * q); 其实这样不太好，知其然不知其所以然。底层进制计算，新手估计很难写出来。
我的答案没用到工具类库，而是自己写的16进制转10进制，10进制转16进制的方法，对于别的语言完全适用
解题关键点：
第一步：理解题目意思：关键是，请看代码 int closest1 = int1 / 17 + (int1 % 17 > 8 ? 1 : 0); //最接近的
第二步： 参考其他题解。我没有用工具类库，自己从0开始写了16进制转10进制，10进制转16进制的方法

我的答案，其他用工具类库的答案自己去看题解

public class Solution {/*** @param color: the given color* @return: a 7 character color that is most similar to the given color*/public String similarRGB(String color) {/*方法：独立性 + 枚举我们可以发现，颜色中的每一维都是独立的，因此我们只需要分别计算出 color = #ABCDEF中与 AB，CD 和 EF 相似度最大的颜色即可。最终的答案为这三个颜色的结合。对于 AB，我们要在 00 到 ff 中找到一个相似度最大的。在方法一中我们得知，00 到 ff 均为 17 的倍数，因此我们需要找到一个 17 的倍数，使得其与 AB 的差的绝对值最小。显然，当 AB mod 17 > 8 时，取刚好比 AB 大的那个数；当 AB mod 17 <= 8 时，取刚好比 AB 小或与 AB 相等的那个数。*/Map<Integer, Character> mapi = new HashMap<>();mapi.put(10, 'a');mapi.put(11, 'b');mapi.put(12, 'c');mapi.put(13, 'd');mapi.put(14, 'e');mapi.put(15, 'f');Map<Character, Integer> mapc = new HashMap<>();for (int k : mapi.keySet()) {mapc.put(mapi.get(k), k);}String s1 = color.substring(1, 3);String s2 = color.substring(3, 5);String s3 = color.substring(5, 7);int int1 = to10hex(s1, mapi, mapc);int int2 = to10hex(s2, mapi, mapc);int int3 = to10hex(s3, mapi, mapc);//System.out.println(s1 + " " + s2 + " " + s3);//System.out.println(int1 + " " + int2 + " " + int3);int closest1 = int1 / 17 + (int1 % 17 > 8 ? 1 : 0); //最接近的int closest2 = int2 / 17 + (int2 % 17 > 8 ? 1 : 0); //最接近的int closest3 = int3 / 17 + (int3 % 17 > 8 ? 1 : 0); //最接近的//System.out.println("最接近的："+closest1+" "+ closest2+" "+closest3);String ans = "#";ans += h10to16(closest1, mapi, mapc);ans += h10to16(closest2, mapi, mapc);ans += h10to16(closest3, mapi, mapc);return ans;}//16进制转十进制public static int to10hex(String s, Map<Integer, Character> mapi, Map<Character, Integer> mapc) {int ans = 0;char[] chars = s.toCharArray();int n = chars.length;int pow = 0;for (int i = n - 1; i >= 0; i--) {char c = chars[i];if (mapc.containsKey(c)) { // 10-15int num = Integer.parseInt(mapc.get(c) + "");ans += num * (int) (Math.pow(16, pow));} else {int num = Integer.parseInt(c + "");ans += num * (int) (Math.pow(16, pow));}pow++;}return ans;}//10进制转16进制public static String h10to16(int n, Map<Integer, Character> mapi, Map<Character, Integer> mapc) {n*=17;List<Integer> list = new ArrayList<>(); //先列出n的二进制表示boolean start = false;for (int i = 31; i >= 0; i--) {int a = (n & (1 << i)) == 0 ? 0 : 1;if(a==1 && !start){start =true;}if(start) list.add(a);}//System.out.println(n+"   "+ list);//正对二进制表示，每4个一组，计算16进制int len = list.size();int cnt = 0;int sum=0;List<String> ll = new ArrayList<>();for (int i = len-1; i >=0 ; i--) {sum += (int)(Math.pow(2,cnt++))*list.get(i);if(cnt==4){if(sum <10) ll.add(sum+"");else ll.add(mapi.get(sum)+"");sum=0;cnt =0;}}if(sum >0){if(sum <10) ll.add(sum+"");else ll.add(mapi.get(sum)+"");}Collections.reverse(ll);String ans = "";for (String s : ll) {ans+=s;}//System.out.println(ans);return ans.length()==0?"00": ans;}}