首页 > 代码库 > 2017-7-21未命名文件

2017-7-21未命名文件

2017-7-21未命名文件

新建
模板
小书匠

第一章 Arrays And Strings

  • 1.1 Is_unique.cpp
  1. #include <string> 
  2. #include <vector> 
  3. #include <iostream> 
  4. #include <bitset> 
  5. using namespace std
  6.  
  7. bool isUniqueChars(const string &str) 

  8. if (str.length() > 128

  9. return false

  10. vector<bool> char_set(128); 
  11. for (int i = 0; i < str.length(); i++) 

  12. int val = str[i]; 
  13. if (char_set[val]) 

  14. return false

  15. char_set[val] = true

  16. return true

  17.  
  18. bool isUniqueChars_bitvector(const string &str)
  19. //Reduce space usage by a factor of 8 using bitvector.  
  20. //Each boolean otherwise occupies a size of 8 bits. 
  21. bitset<256> bits(0); 
  22. for(int i = 0; i < str.length(); i++) { 
  23. int val = str[i]; 
  24. if(bits.test(val) > 0) { 
  25. return false

  26. bits.set(val); 

  27. return true

  28. bool isUniqueChars_noDS(const string &str)
  29. for(int i = 0; i < str.length()-1; i++) { 
  30. for(int j = i+1; j < str.length(); j++) { 
  31. if(str[i] == str[j]) { 
  32. return false



  33. return true;  

  34.  
  35. int main()
  36. vector<string> words = {"abcde", "hello", "apple", "kite", "padle"}; 
  37. for (auto word : words) 

  38. cout << word << string(": ") << boolalpha << isUniqueChars(word) <<endl

  39. cout <<endl << "Using bit vector" <<endl
  40. for (auto word : words) 

  41. cout << word << string(": ") << boolalpha << isUniqueChars_bitvector(word) <<endl

  42. cout <<endl << "Using no Data Structures" <<endl
  43. for (auto word : words) 

  44. cout << word << string(": ") << boolalpha << isUniqueChars_bitvector(word) <<endl

  45. return 0

2017-7-21未命名文件