As suggested in both Quora and StackOverflow, the coin change problem should be the second…
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,…
Breadth first search
Steps: Add root to queue If left child not null, add it to queue If…
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…
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…
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…
[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; } |