daily pastebin goal
64%
SHARE
TWEET

Untitled

bbescos Jan 18th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Compiled with: g++ -Wall -std=c++14 -pthread
  2.  
  3. #include <iostream>
  4. #include <string>
  5. #include <vector>
  6. #include <unordered_set>
  7.  
  8. #include <algorithm>
  9.  
  10. using namespace std;
  11.  
  12. // Complexity: runtime O(n2), memory O(1)
  13. bool repeated_digits(const std::string& st){
  14.    
  15.     for (int i = 0; i < st.size(); ++i){
  16.         for (int j = i + 1; j < st.size(); ++j){
  17.             char val0 = st[i];
  18.             char val1 = st[j];
  19.             if (val0 == val1){
  20.                 return true;
  21.             }
  22.         }
  23.     }
  24.    
  25.     return false;
  26. }
  27. //Comments: brute-force or naïve approach
  28.  
  29.  
  30. // Complexity: runtime O(nlogn), memory O(1)
  31. bool repeated_digits_sort(std::string& st){
  32.     std::sort(st.begin(), st.end());
  33.     for (int i = 1; i < st.size(); ++i){
  34.         char val0 = st[i];
  35.         char val1 = st[i-1];
  36.         if (val0 == val1){
  37.             return true;
  38.         }
  39.     }
  40.    
  41.     return false;
  42. }
  43. //Comments: the runtime complexity of sorting algorithms is nlogn
  44. //Comments: runtime complexity = max(nlogn, n)
  45. //Comments: possible to modify st in-place? YES
  46. //Comments: In computer science, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure.
  47.  
  48. // Complexity: runtime O(nlogn), memory O(n)
  49. bool repeated_digits_sort_const(const std::string& st){
  50.     std::string st2 = st;
  51.     std::sort(st2.begin(), st2.end());
  52.     for (int i = 1; i < st2.size(); ++i){
  53.         char val0 = st2[i];
  54.         char val1 = st2[i-1];
  55.         if (val0 == val1){
  56.             return true;
  57.         }
  58.     }
  59.    
  60.     return false;
  61. }
  62. //Comments: the runtime complexity of sorting algorithms is nlogn
  63. //Comments: runtime complexity = max(nlogn, n)
  64. //Comments: possible to modify st in-place? NO
  65.  
  66.  
  67. // Complexity: runtime O(n), memory O(1)
  68. bool repeated_digits_hash(const std::string& st){
  69.     unordered_set<char> hashset;
  70.    
  71.     for (char c : st){
  72.         if (hashset.count(c) == 1) {
  73.             return true;
  74.         }
  75.         hashset.insert(c);
  76.     }
  77.    
  78.     return false;
  79. }
  80. //Comments: hashset.count() y hashset.insert() have constant runtime
  81. //Comments: for (char c : st) :)
  82.  
  83. // Complexity: runtime O(1), memory O(1)
  84. bool repeated_digits_smart(const std::string& st) {
  85.     if (st.size() > 10)
  86.         return true;
  87.    
  88.     return repeated_digits(st);
  89. }
  90. //Comments: important to know that the string contains only numbers
  91.  
  92.  
  93. int main(){
  94.  
  95.     std::vector<std::pair<std::string, bool>> tests = {
  96.         {"", false},
  97.         {"1", false},
  98.         {"5", false},
  99.         {"12", false},
  100.         {"894", false},
  101.         {"0987654321", false},
  102.         {"1324576098", false},
  103.         {"00", true},
  104.         {"12345678901", true}
  105.     };
  106.    
  107.     for (int i = 0; i < tests.size(); ++i) {
  108.         std::cout<<"TEST "<<i<<std::endl;
  109.         std::string query = tests[i].first;
  110.         bool expected = tests[i].second;
  111.         bool received = repeated_digits_smart(query);
  112.        
  113.         if (expected == received) {
  114.             std::cout<<"PASSED!"<<std::endl;
  115.         } else {
  116.             std::cout<<" * FAILED! Expected: "<<expected<<". Received: "<<received<<std::endl;
  117.         }
  118.         std::cout<<"-----------------------------"<<std::endl;
  119.     }
  120.    
  121.     return 0;
  122. }
  123.  
  124. /*
  125. std::string numeros = "902183901234031892748923651";
  126.  
  127. Como harias una funcion que te diga si hay 2 digitos repetidos en la string?
  128.  
  129. */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top