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

2017-7-21未命名文件

2024-11-01 17:48:39   210人阅读

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. { 
  9. if (str.length() > 128) 
  10. { 
  11. return false; 
  12. } 
  13. vector<bool> char_set(128); 
  14. for (int i = 0; i < str.length(); i++) 
  15. { 
  16. int val = str[i]; 
  17. if (char_set[val]) 
  18. { 
  19. return false; 
  20. } 
  21. char_set[val] = true; 
  22. } 
  23. return true; 
  24. } 
  25.  
  26. bool isUniqueChars_bitvector(const string &str) { 
  27. //Reduce space usage by a factor of 8 using bitvector.  
  28. //Each boolean otherwise occupies a size of 8 bits. 
  29. bitset<256> bits(0); 
  30. for(int i = 0; i < str.length(); i++) { 
  31. int val = str[i]; 
  32. if(bits.test(val) > 0) { 
  33. return false; 
  34. } 
  35. bits.set(val); 
  36. } 
  37. return true; 
  38. } 
  39. bool isUniqueChars_noDS(const string &str) { 
  40. for(int i = 0; i < str.length()-1; i++) { 
  41. for(int j = i+1; j < str.length(); j++) { 
  42. if(str[i] == str[j]) { 
  43. return false; 
  44. } 
  45. } 
  46. } 
  47. return true;  
  48. } 
  49.  
  50. int main(){ 
  51. vector<string> words = {"abcde", "hello", "apple", "kite", "padle"}; 
  52. for (auto word : words) 
  53. { 
  54. cout << word << string(": ") << boolalpha << isUniqueChars(word) <<endl; 
  55. } 
  56. cout <<endl << "Using bit vector" <<endl; 
  57. for (auto word : words) 
  58. { 
  59. cout << word << string(": ") << boolalpha << isUniqueChars_bitvector(word) <<endl; 
  60. } 
  61. cout <<endl << "Using no Data Structures" <<endl; 
  62. for (auto word : words) 
  63. { 
  64. cout << word << string(": ") << boolalpha << isUniqueChars_bitvector(word) <<endl; 
  65. } 
  66. return 0; 
  67. } 

2017-7-21未命名文件


联系
我们