SilentSpiral

腾讯笔试-拼凑硬币

拼凑硬币

腾讯2017年的笔试题目

描述:

小Q十分富有，拥有非常多的硬币，小Q拥有的硬币是有规律的，对于所有的非负整数K，小Q恰好各有两个面值为2K的硬币，所以小Q拥有的硬币就是1,1,2,2,4,4,8,8,…。小Q有一天去商店购买东西需要支付n元钱，小Q想知道有多少种方案从他拥有的硬币中选取一些拼凑起来恰好是n元。

（如果两种方案某个面值的硬币选取的个数不一样就考虑为不一样的方案）

输入：

输入包括一个整数 n (1 ≤ n ≤ 1018)，表示小Q需要支付多少钱。注意n的范围。

输出：

输出一个整数，表示小Q可以拼凑出n元钱放的方案数。

解答

此解答来源于网络，初看即惊为天人

将硬币分为两份：1，2，4，8，16，…..和1，2，4，8，16….
组成两个数值为a,b的两个数字，他们的和是a+b=n;
a在每一份中只可能有一种组合方式（二进制的思想）。
将a和b使用二进制表示，那么对于n=11，有a=101，b=110这种组合，即a=1+0+4=5,b=0+2+4=6。但是，请注意，对于a和b，在相同位取不同值，只有一种组合方法。
如111+100和101+110（即交换中间位）本质上都是同一种组合方法，因此对于该类型可以使用二进制异或进行去重。

1
2
3
4
5
6
7
8
9
10
11
#include<set>
using namespace std;

int WithXor(int n){
    set<int> countset;
    for(int i=0;i<=n/2;i++){
        int result =i|(n-i);
        countset.insert(result);
    }
    return countset.size();
}

争鸣

而大佬发表了对此发表了反对意见, 引述如下：

但是异或,有一个天然性问题,当硬币用两次和用零次是一个效果
所以参考它的解法,还是将硬币分成两堆,然后统计他用的零次一次和二次,将这个序列作为key插入到set.

  1. 因为5+6等价于6+5所以只需要循环到一半.
  2. 对于2的整数次幂需要特判一发.如果2的整数次幂,n,存在0和n的分法,在算法的循环中,l=0会被跳过.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int fakeXor(int n){
    set<string> countset;
    int l,r;
    string key;
    for(int i=0;i<=n/2;i++){
        l=i,r=n-i,key.clear();
        while(l||r){
            key+=char((l&1)+(r&1));
            l>>=1,r>>=1;
        }
        countset.insert(key);
    }
    return countset.size()+((n-1)&n==0);
}

思考

对于用异或作为每种方案的标示以去重的原因，原答案未加以解释。
在我看来这种操作可能是有效的。

一个简单的思路：

反对意见认为在异或后的结果中硬币用两次和用零次是一个效果
所以可能会出现不同方案异或特征的碰撞

考虑到除了异或值以外，两个二进制数仍需要满足a+b=n的要求
假设存在两个发生碰撞的硬币拼凑方案，在某一位上都是0，但一个是2枚，一个是0枚：
那么为了保证两个方案的总钱数n相等，这两个方案必然会有至少一个别的同为0位上产生相反的分歧。

所以对于异或值碰撞的两个方案AB，仅考察异或值为0的位，必然有一部分位A是2枚B是0枚，另一部分位上A是0枚B是2枚，且这两部分各自组成的二进制数相等。即存在有两个在二进制下表示不同的数，其值相等。考虑到二进制数表示法的唯一性，这是不可能的，所以假设不成立。

再数学一点

前面的思路其实并不那么清晰，可能不够严谨，下面换一种思路。

如果每一个拼凑方案对应了唯一的异或值，那么作为简单的数学变换，理应可以由异或值反求出对应的拼凑方案。

记 :
A = a xor b 表示a,b中所有和为1的位所组成的二进制数
B = a and b 表示a,b中所有和为2的位所组成的二进制数
C = a or b 表示a,b中所有不为0的位所组成的二进制数

知道了B和C，即意味着可以还原出对应的拼凑方案

易知：
1. A + 2B= n
2. A + B = C
3. B + C = n

由这三组对应关系（其实是两组）知，在我们知道n和A的时候，可以快速的求出B，C。
在知道n和B 或n和C时，也容易求出剩余的两个量。
所以ABC都可以当作唯一的标识。

即a与b的异或，与，或值都可以作为每种拼凑方案唯一的标识。

改进程序

得到结论以后，可以着手借结论进一步优化程序。

思路是遍历所有可能的标识，判断是否可以得到合法的拼凑方案，并对之计数。
这里的合法即是对标识的约束
易知(a and b) and (a xor b) = 0 ; 即 A and B=0
在对A或B进行遍历时可以检查这一条件
又易知(a and b) and (a or b) = (a and b)；即 B and C = B
或者其变形(a and b) or (a or b) = (a or b)；即 B or C = C
对C或B进行遍历时也可以检查这一条件

三者殊途同归，仅就其中一种形式编写 

1
2
3
4
5
6
7
8
int WithAnd(int n){
	int cnt=0;
	for(int i=0;i<=(n>>1);i++){ //i遍历a&b的取值，至于范围就不写了
		if (!(i&(n-2*i)))
			cnt++;
	}
	return cnt;
}

空间复杂度降到了O(1)

考虑到c++里的set是用红黑树实现的，可能时间复杂度也降下来了一个logn级别 (小声逼逼)

推广

这个问题值得推广，当每种硬币有m枚时，可以以何种方案作为特征唯一的标示呢？

一个浅显的方案是用 (m+1) 进制下，把每种硬币数量作为其中的一位，以无符号整数存储这个(m+1)进制数作为标示。

但是异或，与，或，同或这些特征，能否作为标示？

挖个坑，不一定填。

动态规划解法

使用res[n,i]表示：使用1，1，2，2，4，4，…，2i，2i可以组合出n的方案数
可见

res[n,i]=1，当n=0，即所有面值的硬币所取数目都为0
res[n,i]=1，当n=1，即只取一个一元的硬币
res[2,0]=1，即只取两个一元硬币
res[n,0]=0，当n>=3，因为无法只使用1，1组成大于等于3的组合
res[n,i]=sum(res[n-m2i,i-1]) n,i 取其他，0≤m≤2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.Scanner;
public class Main {
    private static  int n;  //支付数
    private static int count=0;  
    private static int[][]res=null;  

    //初始化数组
    private static void init(){
        double lo=Math.log(n)/Math.log(2);
        int length=(int)lo+1;
        res=new int[n+1][length];
        for(int i=0;i<res[0].length;i++){
            res[0][i]=1;
            res[1][i]=1;
        }
        res[1][0]=1;
        res[2][0]=1;
    }

    //动态规划
    private static final int solve(){
        if(n==0) return 1;
        if(n==1) return 1;
        
        init();
        for(int i=1;i<n+1;i++){
            for(int j=1;j<res[0].length;j++){
                int sum=0;
                for(int m=0;m<3;m++){
                    int rest=(int) (i-Math.pow(2, j)*m);
                    if(rest>=0)
                    {
                        sum+=res[rest][j-1];
                    }
                }
                res[i][j]=sum;
            }
        }
        return res[n][res[0].length-1];
    }
    
    
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        scanner.close();
        double start=System.currentTimeMillis();
        int result=solve();
        System.out.println(result);
        System.out.println("use time="+(System.currentTimeMillis()-start));
    }
}

可能在这种情况下写成备忘录法更优雅吧。有空试一试，下次一定。

打赏