- 时间：2019-10-11
- 题目链接：腾讯真题
- tag：
BitDP
小Q十分富有，拥有非常多的硬币，小Q拥有的硬币是有规律的，对于所有的非负整数K，小Q恰好各有两个面值为2^k的硬币，所有小Q拥有的硬币就是1，1，2，2，4，4，8，8.....小Q有一天去商店购买东西需要支付n元钱，小Q想知道有多少种方案从他拥有的硬币中选取一些拼凑起来恰好是n元（如果两种方案某个面值的硬币选取的个数不一样就考虑为不一样的方案）
集合：和为n的可选数据集，在本题中就是可选的硬币面值：1，1，2，2，4… 以下统一称为集合
-
由集合中元素的特点可以联想到 二进制。如果将集合中的所有元素都用二进制来表示的话：
1 等于 2的0次方 等于 二进制的 1 2 等于 2的1次方 等于 二进制的 10 4 等于 2的2次方 等于 二进制的 100 ... 即： 1=2^0=(1)2; 2=2^1=(10)2; 4 = 2^2 = (100)2;..... .（等号最后的数都是二进制表示法）
集合中的每一个元素都可以表示为 首位为 1 其他位为 0 的二进制数。
-
集合中元素是成对出现的，那么可以将集合拆分为完全相同的两部分, 每一个数都可以由二进制中指定位置的1 来表示：
8 4 2 1 —> 1 1 1 1
8 4 2 1 —> 1 1 1 1
那么，若目标数 n 为 11.那么 11 = 1 + 10 = 2 + 9 = 3 + 8 = 4 + 7 = 5 + 6；
a. 以 1 + 10 为例 ： 1 的 二进制 1， 10的二进制为 1010 那么 (11) 就相当于
取 二进制数 第一位的1， 第四位的1 ，第2位的 1 [从右往左]
即可组成 十进制的11。
b. 2 + 9 = (10)2+ (1001)2 ： 取第二位的1， 第四位的1， 从第一位的1 [从右往左]
同理：
c. 3 + 8= (11)2+(1000)2
d. 4 + 7 = (100)2+(111)2
e. 5 + 6=(101)2+(110)2
a 和 b ,c 中 其实是同一种方案。可通过异或运算进行去重：
比如，这三组方案的异或结果是相同的。1^10 == 2^9 == 3^8 == (1011)2
d,e 也是同一种方案
- 从i=0开始**(如果n=4 那么 0+4 也是一种方案，只不过只选择一个 4 而已)**，i<=(n/2), 每次i+1 循环开始：循环中将 i^(n-i)的值放到 Set（无重复元素）中
- 最终求 Set的 size大小。就是最终的方案数。
代码如下：
import java.util.HashSet;
import java.util.Set;
public class CoinsOfQy {
/**测试*/
public static void main(String[] args) {
int n = 11;
int result = coinsOfQy(n);
System.out.println(result);
}
private static int coinsOfQy(int n) {
Set<Integer> resultSet = new HashSet<>();
for (int i =0; i<= n/2; i++){
int r = i^(n-i);
resultSet.add(r);
}
return resultSet.size();
}
}
暂缺