16.8.18网易内推笔试题（二）——混合颜料 详解

这道题的地址网页内推笔试题（二）——混合颜料

题目如下:

屏幕快照 2016-08-18 16.06.59.png

<u>题目翻译理解</u>

ok，这道题翻译过来，就是进行多次输入，每次输入n个数，将这些数之间进行多次xor（异或操作），其中一个数可能被xor多次，看最后能剩余多少不重复的数，输出数量即可。

<u>解题思路</u>

在C++中，将两个数进行xor，用的是^符号，但是实际上是将十进制转换为二进制之后，再进行xor，这样，这n个十进制的数，就被转换成了n个二进制的包含1，0的字符串，将每个数转换成二进制之后单成一行，位数小的前面被补全0，这样这n个数就变成了n行矩阵，由于1 ≤ xi ≤ 1,000,000,000，而2的30次幂是10亿多，所以这个矩阵最大是n＊30的矩阵。

现在将这个矩阵列出来，如：

101010
111010
101101
110110

然后进行行与行之间的xor，其中1^1=0; 0^0=0; 1^0=1; 0^1=1;
有没有发现这种运算很像求矩阵的秩？相同的相减为0，不同的相减为1.

矩阵的秩定义：是其行向量或列向量的极大无关组中包含向量的个数。
矩阵的秩求法：用初等行变换化成梯矩阵, 梯矩阵中非零行数就是矩阵的秩.

所以这道题就被转化成了求矩阵的秩, 求法如下。

//
//  main.cpp
//  NiuKe_HunHeYanLiao
//
//  Created by 麦心 on 16/8/18.
//  Copyright © 2016年 程序工匠0_0小姐. All rights reserved.
//

#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>

//求一个数的二进制的最高位是哪位
int getHighBit(int num){
    int highbit = 0;
    while (num) {
        //将该数的二进制右移一位
        num>>=1;
        highbit++;
    }
    return highbit;
}

int main() {
    vector<int> colors;
    int n;
    
    while(cin >> n){
        colors.clear();
        int result = 0;
        int temp;
        int i = n;
        while (i--) {
            cin>>temp;
            colors.push_back(temp);
        }
        
        //将colors进行从小到大的排序
        sort(colors.begin(), colors.end());
        int bigger, smaller;
        //bigger和smaller始终指向的是最后一位和倒数第二位数
        bigger = n - 1;
        smaller = bigger - 1;
        
        while (colors.size()>2) {
            //如果两者的最高位相同，说明最高位可以消掉，
            //将两者xor，或者说将矩阵两行相减消掉最高位
            if(getHighBit(colors[bigger]) == getHighBit(colors[smaller])){
                int tem = colors[bigger]^colors[smaller];
                //find函数头文件是<algorithm>
                //泛型算法的 find，在非string类型的容器里，可以直接找出所对应的元素
                //从vector的头开始一直到尾，找到第一个值为temp的元素，返回的是一个指向该元素的迭代器std::vector<int>::iterator类型
                
                //因为现在xor的是两个最大的数，而且最高位已被消掉，所以xor得到的结果一定比这两个数小  
                //如果temp这个 比最大两个数小的 数没有被找到，则将temp加到colors数组中，进行再次xor
                //找不到的话，返回colors.end应该是固定用法
                if(find(colors.begin(), colors.end(), tem)==colors.end()){
                    colors.push_back(tem);
                    sort(colors.begin(), colors.end());
                    bigger++;//因为colors中多了一个数，所以需要位数＋1
                    smaller++;
                }
            }else{
                result++;
            }

            //如果两者最高位不同，说明已经所有数的最高位已经只有最大的那个数是1了，这样它已经不可能被消掉了，结果＋1
            
            //如果两个最大数的最高位可以消掉，那么消除之后，最大数已被消掉，没有用了
            //如果两个最大数的最高位不可以消掉，那么结果＋1，最大数也没有用了。
            //弹出最大数
            colors.pop_back();
            
            //因为弹出了一个数，所以bigger和smaller都要相应－1
            bigger = smaller;
            smaller--;
        }
        cout<<result+colors.size()<<endl;
    }
}

提交，用例全部通过。