As suggested in both Quora and StackOverflow, the coin change problem should be the second problems for beginner to solve. There are actually multiple variations of this problem, however, my approach will be finishing the basic version first, which is: Given a set of coins with values, find the possible way to form N (order is not considered). Example: Given…
Category: Algorithms
My dynamic programming journey [1] – Fib with memorization
It is rather complicated to consider the advance level of dynamic programming at the beginning, so I have decided to start with a basic example: finding Fibonacci numbers. Since the concepts of recursion and memorization are often required in dynamic programming, therefore, I have implemented a version of memorization. Set base case of 0 and 1 equal to 1 Check…
Breadth first search
Steps: Add root to queue If left child not null, add it to queue If right child not null, add it to queue Repeat 2 & 3 until the queue is empty
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
void print_tree_bfs() { queue<Node *> q; Node *cur = this->root; q.push(cur); while (!q.empty()) { cur = q.front(); cout << cur->data << " "; if (cur->left) q.push(cur->left); if (cur->right) q.push(cur->right); q.pop(); } } |
std::map
Simple insert
|
1 2 3 4 5 6 7 8 |
map<string, int> dataMap; // Two methods to insert // 1. Insert with pair dataMap.insert(pair<string, int>("TESTING", 1)); // 2. Insert with array dataMap["TESTING"] = 1; |
Access to second element using key (C++ 11)
|
1 2 3 |
cout << dataMap.at("TESTING"); // Console output = 1 |
Iterate
|
1 2 3 4 5 6 |
map<string, int>::iterator iter; for (iter = dataMap.begin(); iter != dataMap.end(); iter++) { string first = iter->first; int second = iter->second; } |
Find element
|
1 2 3 4 |
if (dataMap.find("TESTING") != dataMap.end()) {...} // Found else {...} // NOT Found |
Unordered Map
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include <unordered_map> using namespace std; unordered_map<int, int> map; map[2] = 4; // Map 4 to key value 2 auto p = map.find(3); //unordered_map<int, int>::const_iterator p = map.find(3); if (p != map.end()){ // Found } else{ // NOT Found } |
According to the documentation, the average searching complexity is O(1), by looking more into unordered_map.find()
|
1 2 3 4 |
iterator find(const key_type& _Keyval) { // find an element in mutable hash table that matches _Keyval return (lower_bound(_Keyval)); } |
It is redirected to lower_bound, passing in the original key value
|
1 2 3 4 5 6 7 8 9 10 |
iterator lower_bound(const key_type& _Keyval) { // find leftmost not less than _Keyval in mutable hash table size_type _Bucket = _Hashval(_Keyval); for (_Unchecked_iterator _Where = _Begin(_Bucket); _Where != _End(_Bucket); ++_Where) if (!_Traitsobj(_Traits::_Kfn(*_Where), _Keyval)) return (_Traitsobj(_Keyval, _Traits::_Kfn(*_Where)) ? end() : _Make_iter(_Where)); return (end()); } |
For _Traits, it’s the template operators (open hashing I supposed), for the iterator defined within the _Traits class
|
1 2 3 4 5 6 7 8 |
for (_Iter _Next1 = _Left.begin(); _Next1 != _Left.end(); ++_Next1){ // look for element with equivalent key _Iter _Next2 = _Right.find(_Traits::_Kfn(*_Next1)); if (_Next2 == _Right.end() || !(_Traits::_Nonkfn(*_Next1) == _Traits::_Nonkfn(*_Next2))) return (false); } return (true); } |
1. Two Sum
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> output; for (int i = 0; i < nums.size(); i++) for (int j = nums.size() - 1; j>i; j--) if (nums[i] + nums[j] == target) { output.push_back(i); output.push_back(j); return output; } } }; |
7. Reverse Integer
Reverse digits of an integer. Example1: x = 123, return 321 Example2: x = -123, return -321 Note: The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { public: int reverse(int x) { string result = to_string(abs(x)); string output = ""; for (int i = result.length(); i >= 0; i--) output += result.substr(i, 1); try{ stoi(output); } catch(...){ return 0; } if (x <= 0) return stoi(output) * -1; else return stoi(output); } }; |
[ProjectEuler+] #8: Largest product in a series
Using string & substr instead of int for large result
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include #include using namespace std; int main() { int T, N, K; string target; scanf("%d", &T); while (T--) { scanf("%d%d", &N, &K); cin >> target; string s = ""; int max = 0, temp = 1; for (int i = 0;i < (target.length() - K + 1);i++) // Loop until last k digits { temp = 1; s = target.substr(i, K); // Take k digits for (int j = 0;j < K;j++)// Split and multiply each digit temp *= atoi((s.substr(j, 1)).c_str()); // atoi for string to int if (temp > max) max = temp; } printf("%d\n", max); } return 0; } |
[ProjectEuler+] #6: Sum square difference
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include #include using namespace std; int main() { long long T; scanf("%lld", &T); while (T--) { long long N, sum = 0; scanf("%lld", &N); N += 1; for (long long i = 1;i < N;i++) sum += pow(i, 2); N -= 1; printf("%lld\n", ((N*(1 + N) / 2)*(N*(1 + N) / 2) - sum)); } return 0; } |
[ProjectEuler+] #5: Smallest multiple
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include #include #include using namespace std; int findPrime(int totalSize, vector &primeList) { int primeListSize = 1; bool isPrime; primeList[0] = 2; for (int i = 3;i <= totalSize;i += 2) // Skip even number, loop within "max" { isPrime = false; // reset to find prime for (int k = 0;k < primeListSize;k++) { if (i%primeList[k] == 0) // Not Prime { isPrime = false; break; } isPrime = true; // Survive the break = Prime } if (isPrime) { primeList[primeListSize] = i; // Store into array primeListSize++; } } return primeListSize; } int main() { int n, count = 0, max = 0; scanf("%d", &n); vector input(n); for (int i = 0;i < n;i++) { scanf("%d", &input[i]); if (input[i] > max) max = input[i]; } vector primeList(max); // Find only the MAX value prime array int primeListSize = findPrime(max, primeList); for (int i = 0;i < input.size();i++) { long long sum = 1; int j = 0, n = 1; while (true) { if (primeList[j] == 0) // Out of the primeList break; n = 1; while (pow(primeList[j], n) <= input[i]) n++; sum *= pow(primeList[j], n - 1); j++; } printf("%lld\n", sum); } return 0; } |