每日幾題

//問題描述：實現一個算法來判斷一個字符串中的字符是否唯一(即沒有重復).不能使用額外的數據結構。 (即只使用基本的數據結構)

#include "stdafx.h"
#include"FindUnique.h"
#include<cstring>
#include<iostream>
using namespace std;
/*

//算法思想：ASCII字符集中字符數256個，可用256位表示某個字符是否出現過，所有位始化為0，若第i位為1，表示出現過此字符，否則，將其設為訪問過

bool isUnique(const char *s)
{
  bool b[256];
  memset(b,0,sizeof(b));
  for(int  i=0;s[i]!='\0';i++)
  {
   int pos=(int )s[i];
   if(b[pos])
    return false;
   else
      b[pos]=true;
  }
  return true;
}
*/
//用位操作實現
 
bool isUnique(const char *s)
{
 int a[8]={0};
 for(int i=0;s[i]!='\0';i++)
 {
  int pos=(int)s[i];  //把字符轉化成對應的整數
  int index=pos>>5;   //整數又移5位，相當於除32取整，可得出整數所在數組中的位置
  if(a[index]&(1<<(pos&0x1F)))   //pos&0x0F相當於取整數的低5位，也即整數除32取余。1<<(pos&0x1F)找出整數所在的具體的位
   return false;
  else
   a[index]|=(1<<(pos&0x1F));
 }
 return true;
}

此題用位操作，讓我聯想到編程珠玑中用位圖對大規模數據進行排序的問題。以前只是看了書，並沒有動手實踐，借機一試，發現許多問題，記下以備後用

#include "stdafx.h"
#include<iostream>
using namespace std;
void bitSort(int a[],int n)
{
 
 const int N=10000;  // N的值應該為數據中最大的數值加一，N值的大小有較多疑惑，需要用到數組中的最大數，還需求數組最大值？若設的過大時間和空間上都是一種浪費
  int bit_map[N/32+1];
 for(int i=0;i<N;i++)
        bit_map[i>>5]&=~(1<<(0x1F&i)); //清零  所有位操作的解釋如上題解法二
   for(int i=0;i<n;i++)
  bit_map[a[i]>>5]|=(1<<(0x1F&a[i]));
 for(int i=0;i<N;i++)
 {
    if(bit_map[i>>5]&(1<<(0x1F&i)))
  cout<<i<<'\t';
 }
}

#include<iostream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
   int a[]={3,2,4,69,1,8};
 bitSort(a,6);
 
 return 0;
}