Andy Niu �����ĵ�

1、考虑下面的需求，对文件中的1亿个32位整数排序，这些整数不重复。
    使用new int[1亿]，从文件中读取所有的整数，放入数组，排序。这种方法不可以行，因为需要的内存太大。
    怎么解决这个问题？
2、使用位向量表示整数，也就是第n个bit，表示整数n，bit的取值为整数出现的次数，0没有出现,1出现。
    而上面的方法，整数需要4个字节，32bit表示。因此，位向量只用到原来的32分之1。
    注意：如果重复次数不超过3，使用两个bit表示一个整数。也就是第2n-1和第2n个bit表示整数n，
    这两个bit的取值表示出现次数。
3、为了简化问题，考虑30个整数，使用位向量排序。
    new出32bit的内存，也就是4个字节。从文件中遍历读取整数，在对应的第n个bit，把bit置为1
    遍历位向量，输出bit值为1的位置。
4、位向量也就是，第n个bit表示整数n，bit的取值为整数n出现的次数。
5、考虑，如果文件中的数字更多，比如说有40亿，怎么处理？
    多趟处理，第一趟遍历40亿整数，过滤出大于等于0,小于1亿[0,1亿)，排序输出到目标文件,
    第二趟遍历40亿整数，过滤出大于等于1亿,小于2亿[1亿,2亿)，排序输出到目标文件。

头文件

#ifndef PEARLS_H_
#define PEARLS_H_
typedef unsigned char uint_8;

namespace Pearls
{
    void SetBitValue(uint_8* start,int index,int value);
    int  GetBitValue(uint_8* start,int index);
}
#endif

源代码

#include "pearls.h"

namespace Pearls
{
    void SetBitValue(uint_8* start,int index,int value)
    {       
        int bytePos = index/8; // 第几个字节
        int bitPos  = index%8; // 字节内的第几个bit

        start+=bytePos;
        if(value == 0)
        {
            (*start)&=(~(1<<bitPos)); // 把某一个bit置成0，与上一个对应位是0，其它位是1的数，这里有个取反
        }
        else if(value == 1)
        {
            (*start)|=(1<<bitPos);   // 把某一个bit置成1，或上一个对应位是1，其它位是0的数
        }       
    }

    int GetBitValue(uint_8* start,int index)
    {       
        int bytePos = index/8; // 第几个字节
        int bitPos  = index%8; // 字节内的第几个bit

        // 做个副本，转化为unsigned，再移位
        uint_8 ch = *(start+=bytePos);
        return ((ch)&=(1<<bitPos))>>bitPos;
    }
}

测试

#include "pearls.h"
#include <stdio.h>
#include <string.h>
#include <fstream>

void ReadFileAndSetBitVec(uint_8* bitVec)
{
    FILE* pf = fopen("./ints.txt","r");
    char readBuf[4] = {0};
    char* pBuf = readBuf;

    while(feof(pf) == false)
    {
        if((*pBuf++ = fgetc(pf)) == ' ')
        {
            int value = atoi(readBuf);
            Pearls::SetBitValue(bitVec,value,1);
            memset(readBuf,0,4);
            pBuf = readBuf;
        }
    }
}

void PrintBitVec(uint_8* bitVec)
{
    for(int i = 0; i<32; ++i)
    {
        int dd = Pearls::GetBitValue(bitVec,i);
        if(Pearls::GetBitValue(bitVec,i) == 1)
        {
            printf("%d ",i);
        }
    }
}

int main(int argc, char* argv[])
{
    uint_8* bitVec = new uint_8[4];
    memset(bitVec,0,4);

    ReadFileAndSetBitVec(bitVec);

    PrintBitVec(bitVec);

    getchar();
    return 0;
}

1、考虑字符串1234，输出全排列，如下：1234,1243,1324,1342,1423,1432，.....
2、思路一,初始左边为"",右边为1234，递归结束条件是右边只有一个字符，输出左边，和右边的一个字符。
3、思路二，全排列，最小是1234，最大是4321，从1234开始，找出下一个比1234大，且差值最小的排列，
    一直找到4321结束。

void PrintTotalOrder(const string& str)
{
    //PrintOrder("",str);

    PrintOrder_2(str);
}

void PrintOrder(const string& prefix,const string& other)
{
    if (other.size()==1)  
    {  
        //如果后缀只剩一个字符，输出当前顺序，递归结束  
        printf("%s%s\n",prefix.c_str(),other.c_str());  
    }  
    else  
    {  
        //如果后缀长度大于1，每次把后缀中的一个字符添加到前缀中，递归  
        for (int i=0;i<other.size();i++)  
        {  
            PrintOrder(prefix+other.substr(i,1),string(other).erase(i,1));  
        }  
    }  
}

void PrintOrder_2(const string& str)
{
    string cpy = str;
    do
    {
        printf("%s\n",cpy.c_str());
    }while(Next(cpy));
}

bool Next(string& str)
{
    int len = str.size();

    // 从后向前，找到第一个位置，这个位置的元素小于下一个位置的元素
    int pos = len-2; // 假定是倒数第二个元素
    while(pos>=0 && str[pos]>str[pos+1]) // 不满足条件，向前移动
    {
        --pos;
    }

    if(pos==-1) // 位置不存在，已经是逆序排列，取值最大
    {
        return false;
    }
    else        
    {
        // 从后面找出一个比当前下标大的元，这个backpos必定存在。
        int backPos = len-1;
        while(backPos>0 && str[backPos] < str[pos])
        {
            --backPos;
        }
        Swap(str[pos],str[backPos]);

        ReverseString(str,pos+1,str.size());
        return true;
    }
}

// 对string的left和right区间反转
void ReverseString(string& str,int left,int right)
{
    if(left>right)
    {
        Swap(left,right);
    }

    if(right>str.size())
    {
        return;
    }
    
    int mid = (left+right)/2;
    for(int i = left;i<mid;++i)
    {
        Swap(str[i],str[--right]); // left下标加1，right下标减1
    }
}

int main(int argc, char* argv[])
{
    Pearls::PrintTotalOrder("1234");
    getchar();
    return 0;
}

1、考虑下面的需求，给出包含单词的文档，找出其中的变位词。所谓的变位词，比如dog，god互为变位词。
2、最笨的办法是，dog不动，对god，cat进行排列组合，看看是否存在于dog相同的情况，存在就是变位词。
3、上面的办法效率太差，很长的单词，排列组合很多，cpu开销太大。怎么解决？
4、变位词的特点是，大家所包含的字符相同，只不过排列组合不同。包含的字符，可以认为是单词的标识符，
    标识符按字符顺序排列好，互为变位词，也就是说标识符相同。因此，解决思路是，对每个单词求标识符，
    比较标识符，相同就是变位词。
5、使用map，key是标识符（可能是一个无效的单词），value是vector，保存互为变位词的单词集合。
6、更广泛的用处，比如使用搜狗输入法输入 ty，就会提示 统一，同意，同义等等。这种情况也类似，对
    统一，同意，同义求标识符，放入map的key，value保存这些词。

    string GetIdentifier(const string& word)
    {
        char buf[64] = {0};
        sprintf(buf,word.c_str());
        qsort(buf,strlen(buf),sizeof(char),CharCmp);

        return buf;
    }

    int CharCmp(const void* a,const void* b)
    {
        return *(char*)a - *(char*)b;
    }

    bool IsSeparator(char ch)
    {
        return (ch == ' ' || ch == ',' || ch == '.'|| ch == '\r'|| ch == '\n');
    }

    void GetWord(vector<string>& wordVec,char* buf)
    {
        buf[strlen(buf)-1] = '\0'; //去除分隔符
        if(strlen(buf) > 0)
        {
            wordVec.push_back(buf);
        }
    }

    void ReadWordFromFile(vector<string>& wordVec)
    {
        FILE* pf = fopen("./words.txt","r");
        char readBuf[64] = {0};
        char* pBuf = readBuf;

        while(feof(pf) == false)
        {
            *pBuf = fgetc(pf);
            if(IsSeparator(*pBuf))
            {
                GetWord(wordVec,readBuf);
                memset(readBuf,0,64);
                pBuf = readBuf;
            }
            else
            {
                ++pBuf;
            }
        }
    }

int main(int argc, char* argv[])
{
    vector<string> wordVec;
    Pearls::ReadWordFromFile(wordVec);

    map<string,vector<string> > wordMap;
    for(vector<string>::iterator iter = wordVec.begin();
        iter != wordVec.end();++iter)
    {
        wordMap[Pearls::GetIdentifier(*iter)].push_back(*iter);
    }

    getchar();
    return 0;
}

1、循环移位，对于abcdefgh，向左循环移动3位，成为defghabc，给出一个字符数组和需要移动的位数n，输出结果。
2、一场考虑，字符指针为NULL，对于8个字符，左移11位等价于左移3位。
3、方法一：从头部取出一个字符，后面的依次左移，取出的字符放入尾部，执行n次。
4、方法一的cpu开销大，方法二是：分配n个字节的缓冲区，从头部取出n个字节，后面的字符左移n位，取出的n字节
    字符放入尾部。
5、方法二的内存开销大，需要多分配n字节字符。方法三，利用循环左移的特点，循环左移3位等价于前面3个反转，
    后面的字符反转，然后整个字符串反转。如下：abcdefgh-->cbadefgh-->cbahgfed-->defghabc

void LoopMove(char* pc,int moveSize)
{
    if(pc == NULL)
    {
        return;
    }
    int len = strlen(pc);
    if(len <= 1)
    {
        return;
    }

    moveSize = moveSize%len;

    // 每次左移一位，循环n次
    //for(int i=0;i<moveSize;++i)
    //{
    //  char first = pc[0];
    //  for(int j=0;j<len-1;++j)
    //  {
    //      pc[j]=pc[j+1];
    //  }
    //  pc[len-1]=first;
    //}

    // 一次左移n位
    //char* buf = new char[moveSize];
    //memset(buf,0,moveSize);
    //memcpy(buf,pc,moveSize);

    //for(int j=0;j<len-moveSize;++j)
    //{
    //  pc[j]=pc[j+moveSize];
    //}
    //memcpy(pc+len-moveSize,buf,moveSize);

    // 反转三次
    Reverse(pc,pc+moveSize);
    Reverse(pc+moveSize,pc+len);
    Reverse(pc,pc+len);
}

void Reverse(char* first,char* last)
{
    int len = last-first;
    for(int i=0;i<len/2;++i)
    {
        char tmp = first[i];
        first[i] = first[len-i-1];
        first[len-i-1]=tmp;
    }
}

{
    char buf[] = "abcdefgh";
    Pearls::LoopMove(buf,3);

    Pearls::LoopMove(buf,3);

    Pearls::LoopMove(buf,4);

    Pearls::LoopMove(buf,81);

    getchar();
    return 0;
}

void GetCharCountByMap(const string& str)   
{
    map<char,int> chMap;

    for(int i = 0;i<str.size();++i)
    {
        chMap[str[i]]++;
    }

    for(map<char,int>::iterator iter = chMap.begin();
        iter != chMap.end(); ++iter)
    {
        printf("[%c:%d]\n",iter->first,iter->second);
    }
}

void GetCharCountByHashTable(const string& str)
{
    // 最多512个字符，下标对应字符，下标取值对应出现的次数
    int hashTable[512]={0};

    for(int i = 0;i<str.size();++i)
    {
        hashTable[str[i]]++;
    }

    for(int i=0; i<512; ++i)
    {
        if(hashTable[i]>0) // 出现过
        {
            printf("[%c:%d]\n",i,hashTable[i]);
        }           
    }
}

int main(int argc, char*argv[])
{
    string str = "acbbdkdehfghgefahb";
    Pearls::GetCharCountByMap(str);
    Pearls::GetCharCountByHashTable(str);
    
    return 0;
}