some useful links
1. Glib example: https://www.ibm.com/developerworks/linux/tutorials/l-glib/ 在blogger裡面轉換格式: http://formatmysourcecode.blogspot.tw/ python: https://repl.it/languages/python3
發表文章
基於在 glib 庫中 hash 函數上搭建的 LRU 緩衝框架
https://buzzorange.com/techorange/2015/12/17/programmers-dilemma/ 1.定義LRU緩衝的資料結構 LRU緩衝 = (數目，大小)； ex: largeLRU = new LRU(50, 512*1024/*512K*/) smallLRU = new LRU(100, 4*1024 /*4K*/)
https://leetcode.com/contest/leetcode-weekly-contest-49/problems/cut-off-trees-for-golf-event/
http://alrightchiu.github.io/SecondRound/all-pairs-shortest-pathfloyd-warshall-algorithm.html http://slideplayer.com/slide/4393766/14/images/28/Some+Algorithms+When+no+negative+edges.jpg https://stackoverflow.com/questions/26547816/understanding-time-complexity-calculation-for-dijkstra-algorithm void Solution::dijkstraSingleSource(vector<list<pair<int, int> > > &edge, int src) { set< pair<int, int> > active_vertices; active_vertices.insert(make_pair(0, src)); while (active_vertices.size() != 0) { int vertex = (active_vertices.begin())->second; active_vertices.erase(make_pair(shortestDist[src][vertex], vertex)); list<pair<int, int> >::iterator iter; for (iter = edge[vertex].begin(); iter != edge[vertex].end(); iter++) { int dist = iter->first; int edgeLength = iter->second; if ((shortestDist[src][vertex] + edgeLength) < shorte...
Floyd_Warshall implementation
矩陣輸入 #include <stdio.h> #include <limits.h> #include <vector> using namespace std; void Floyd_Warshall(vector<vector<int> > &graph, vector<vector<int> > &shortest) { int none = -1; int n = graph.size(); if (n == 0) { return; } if (shortest.size() != n) { return; } for (int i = 0; i < n; i++) { if ((shortest[i].size()) != n || (graph[i].size() != n)) return; } // initialize shortest for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (graph[i][j] >= 0) { shortest[i][j] = graph[i][j]; } else { shortest[i][j] = INT_MAX; } } } for (int maxHalfway = 0; maxHalfway < n; maxHalfway++) { for (int source = 0; source < n; source++) { for (int dist = 0; dist < n; dist++) { if (shortest[source][maxHalfway] != INT...
Bellman_Ford implementation
Bellman Ford implementation #include <iostream> #include <limits.h> #include <list> #include <vector> using namespace std; void Bellman_Ford(vector<pair<pair<int, int>, int> > &edges, int numVertex, vector<vector<int> > &shortest/*result*/) { int none = -1; if (numVertex == 0) { return; } if (shortest.size() != numVertex) { return; } for (int i = 0; i < numVertex; i++) { if ((shortest[i].size()) != numVertex) return; } // initialize shortest for (int i = 0; i < numVertex; i++) { for (int j = 0; j < numVertex; j++) { if (i == j) { shortest[i][j] = 0; } else { shortest[i][j] = INT_MAX; } } } bool globalChanged = true; for (int round = 0; round < numVertex; round++) { globalChanged = false; printf("round = %d\n", roun...
Dijkstra
#include <iostream> // std::cout #include <set> #include <vector> using namespace std; void dijkstra(vector<vector<int> > &graph, int src) { int size = graph.size(); vector<int> shortestDist; for (int i = 0; i < size; i++) { shortestDist.push_back(INT_MAX); } shortestDist[src] = 0; set< pair<int, int> > active_vertices; active_vertices.insert(make_pair(0, src)); while (active_vertices.size() != 0) { int vertex = (active_vertices.begin())->second; active_vertices.erase(make_pair(shortestDist[vertex], vertex)); for (int i = 0; i < size; i++) { if (graph[vertex][i] != 0) { ...
https://leetcode.com/problems/number-of-longest-increasing-subsequence/description/
#include <iostream> #include <vector> #include <algorithm> using namespace std; class Solution { public: int findNumberOfLIS(vector<int>& nums) { if (nums.size() == 0) return 0; vector<pair<int, int>> LISInfo (nums.size(), make_pair(1, 1)); for (unsigned int i = 0; i < nums.size(); i++) { for (unsigned int j = 0; j < i; j++) { if (nums[j] < nums[i]) { if ((LISInfo[j].first + 1) > LISInfo[i].first) { LISInfo[i].first = LISInfo[j].first + 1; LISIn...
Longest Increasing Subsequence
#include <iostream> #include <vector> using namespace std; class Solution { public: int longestIncreasingSubsequence(vector<int>& nums) { vector<int> LIS (nums.size(), 0); vector<int> LISPrevious (nums.size(), -1); int max = 0; int end = -1; for (unsigned int i = 0; i < nums.size(); i++) { LIS[i] = 1; for (unsigned int j = 0; j < i; j++) { if ((LIS[j] + 1) > LIS[i]) { if (nums[j] < nums[i]) { LIS[i] = LIS[j] + 1; ...
https://leetcode.com/problems/maximum-width-of-binary-tree/description/
#include <iostream> #include <queue> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ void inOrder(TreeNode* root) { if (!root) return; if (root->left) inOrder(root->left); cout << root->val << "\n"; if (root->right) inOrder(root->right); } void preOrder(TreeNode* root) { if (!root) return; cout <...
https://leetcode.com/problems/non-decreasing-array/description/
#include <iostream> #include <vector> #include <climits> using namespace std; class Solution { public: bool checkPossibility(vector<int>& nums) { if (nums.size() < 1) { return true; } int first = -1; for (int i = (nums.size() - 1); i > 0 ; i--) { nums[i] = nums[i] - nums[i - 1]; if (nums[i] < 0) { if (first != -1) { return false; } first = i; } } if (f...
https://leetcode.com/contest/leetcode-weekly-contest-48/problems/maximum-swap/
Way 1: #include <iostream> #include <list> using namespace std; class Solution { public: int maximumSwap(int num) { list<int> *buckets = new list<int>[10]; int digit = 0; int temp = num; while (temp != 0) { buckets[temp % 10].push_front(digit++); temp /= 10; } for (int i = 9; i >= 0; i--) { while (!buckets[i].empty()) { if (buckets[i].front() != (--digit)) { int target = buckets[i].back(); int plus = numberFromDigit(num, target); ...
https://leetcode.com/contest/leetcode-weekly-contest-48/problems/trim-a-binary-search-tree/
[1st version] not so good.... #include <iostream> #include <queue> using namespace std; typedef struct TreeNode TreeNode; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* trimBST(TreeNode* root, int L, int R) { if (!root) { return root; } TreeNode *lChild = trimBST(root->left, L, R); TreeNode *rChild = trimBST(root->right, L, R); TreeNode *temp, *newRoot; newRoot = root; if (root->val <...
https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/description/
1. To verify the result, we create a tree constructor procedure firstly. #include <iostream> #include <queue> using namespace std; typedef struct TreeNode TreeNode; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int findSecondMinimumValue(TreeNode* root) { if (!root || !(root->left)) { return -1; } int min = root->val; int lresult, rresult; if (root->left->val != min) { lresult = root->left->val; } el...
http://www.geeksforgeeks.org/search-an-element-in-a-sorted-and-pivoted-array/
#include <iostream> using namespace std; #define CEIL(x, n) ((x) > (n) ? ((x) - (n)) : (x)) int binarySearchRotated(int *input, int n, int target) { if (n < 1) return -1; int start = 0; int end = n - 1; for (int i = 0; i < (n - 1); i++) { if (input[i] > input[(i + 1)]) { start = i + 1; end = i; } } if (end < start) end += n; int loop = 0; while(1) { loop++; if (start > end) { break; } int middle = start + ((end - start + 1) / 2); if (target == input[CEIL(middle, n)]) { cout << "loop = " << loop << "\n"; return CEIL(middle, n); } else if (target > input[CEIL(...