SHARE
TWEET

Untitled

bbescos Jan 18th, 2019 58 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 <vector>
  5. #include <unordered_set>
  6. #include <unordered_map>
  7.  
  8. // Complexity: runtime O(n2), memory O(1)
  9. std::pair<int, int> two_sum(const std::vector<int>& numbers, const int x) {
  10.    
  11.     for (int i = 0; i < numbers.size(); i++){
  12.         for (int j = i + 1; j < numbers.size(); j++){
  13.             int val0 = numbers[i];
  14.             int val1 = numbers[j];
  15.             if (val0 + val1 == x){
  16.                 std::cout << "Encontrados! val0: " << val0 << ", val1: " << val1 << std::endl;
  17.                 std::pair<int, int> result(val0, val1);
  18.                 return result;
  19.             }
  20.         }
  21.     }
  22. }
  23. //Comments: brute-force or naïve approach
  24.  
  25.  
  26. // Complexity: runtime O(n), memory O(n)
  27. std::pair<int, int> two_sum_hashset(const std::vector<int>& numbers, const int x) {
  28.    
  29.     std::unordered_set<int> hashset;
  30.    
  31.     for (int i : numbers){
  32.         int complement = x - i;
  33.         if (hashset.count(complement) == 1){
  34.             std::pair<int, int> result(complement, i);
  35.             return result;
  36.         }
  37.         hashset.insert(i);
  38.     }
  39. }
  40.  
  41. /*
  42. Now we want to return the indexes in which these two numbers are:
  43. */
  44. // Complexity: runtime O(n), memory O(n)
  45. std::pair<int, int> two_sum_hashmap(const std::vector<int>& numbers, const int x) {
  46.    
  47.     std::unordered_map<int, int> hashmap;
  48.    
  49.     for (int i = 0; i < numbers.size(); ++i) {
  50.        
  51.         int current = numbers[i];
  52.         int complement = x - current;
  53.        
  54.         if (hashmap.count(complement)) {
  55.             std::pair<int, int> result{hashmap[complement], i};
  56.             return result;
  57.         }
  58.        
  59.         hashmap[current] = i;
  60.     }
  61. }
  62.  
  63.  
  64. //Comments: int 4bytes = 32 bits = 4*10^9 -> [-2*10^9, +2*10^9]
  65. /*
  66.  char 1 byte
  67.  int 4 bytes
  68.  long  8 bytes
  69.  float 4 bytes
  70.  double 8 bytes
  71.  bool 1 byte
  72.  
  73.  ...const int x)   <- 4 bytes
  74.  ...const int& x)  <- 8 bytes
  75.  
  76.  
  77.  ...const imagen y) <-- 100000 bytes
  78.  ...const imagen& y) <-- 8 bytes
  79. */
  80.  
  81. int main(){
  82.  
  83.     std::vector<int> nums_1 = {1, 2, 3};
  84.     int x1 = 3;
  85.     std::pair<int, int> result_1 = {1, 2};
  86.    
  87.     std::vector<int> nums_2 = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  88.     int x2 = 17;
  89.     std::pair<int, int> result_2 = {8, 9};
  90.    
  91.     std::cout<<"Test 1: "<<std::endl;
  92.     auto res_1_berta = two_sum_hashset(nums_1, x1);
  93.    
  94.     if (res_1_berta == result_1) {
  95.         std::cout<<"Bien!"<<std::endl;
  96.     } else {
  97.         std::cout<<"Mal!"<<std::endl;
  98.     }
  99.    
  100.     std::cout<<"Test 2: "<<std::endl;
  101.     auto res_2_berta = two_sum_hashset(nums_2, x2);
  102.    
  103.     if (res_2_berta == result_2) {
  104.         std::cout<<"Bien!"<<std::endl;
  105.     } else {
  106.         std::cout<<"Mal!"<<std::endl;
  107.     }
  108.      
  109.     return 0;
  110. }
  111.  
  112. /*
  113. std::vector<int> numeros = "902183901234031892748923651";
  114. int x;
  115.  
  116. Como harias una funcion que te devuelva dos numeros del vector cuya suma sea x? Asumir que hay siempre solucion.
  117. Aunque haya mas de una solucion devolver una.
  118.  
  119. */
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