Concurrency Freaks: Concurrency Pattern: Distributed Cache-Line Counte...: On the previous post we showed a Counter that can be used for single-Writer scenarios, this time we have one that works for multiple-writers...
Shawn's Pit
No code too long to read. No code too short to write.
1/10/2014
7/01/2013
Print object properties in Javascript
Print object properties in Javascript
var print = function(element) { var str = ""; for (var prop in element){ if (typeof(element[prop]) == "string") { str += prop + ": " + element[prop] + "<br/>"; } else if (typeof(element[prop]) == "function") { str += prop + ": (function)<br/>"; } else { str += prop + ": { <br/>" + print(element[prop]) + "}"; } } return str; }
3/22/2013
CTRL+A, CTRL+C, CTRL+V
Imagine you have a special keyboard with the following keys:I do believe there should be an O(n) solution, but sort of tricky. The O(n^2) solution is quite straightforward in DP problems.
where CTRL+A, CTRL+C, CTRL+V each acts as one function key for “Select All”, “Copy”, and “Paste” operations respectively.
- A
- Ctrl+A
- Ctrl+C
- Ctrl+V
If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys.
That is to say, the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce).
public static int maxChar(int n) { int[] dp = new int[n]; for (int i = 0; i < n; ++i) { dp[i] = i + 1; // type A } for (int i = 0; i < n; ++i) { for (int j = i + 4; j < n; ++j) { dp[j] = Math.max(dp[j], dp[i] * (j - i - 3)); // using Ctrl + V } } return dp[n - 1]; }
3/04/2013
Interleaving String
Interleaving StringAug 31 '12
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 =
s2 =
Given:
s1 =
"aabcc"
,s2 =
"dbbca"
,
When s3 =
When s3 =
"aadbbcbcac"
, return true.When s3 =
"aadbbbaccc"
, return false.class Solution { public: bool isInterleave(string s1, string s2, string s3) { // Start typing your C/C++ solution below // DO NOT write int main() function if (s1.empty()) return s2 == s3; else if (s2.empty()) return s1 == s3; else if (s3.empty()) return s1.empty() && s2.empty(); else if (s1.size() + s2.size() != s3.size()) return false; int lengthS1 = s1.size() + 1, lengthS2 = s2.size() + 1; vector<vector<bool>> dp(lengthS2, vector<bool>(lengthS1, false)); dp[0][0] = true; for (int i = 1; i < lengthS2; ++i) { dp[i][0] = s2[i - 1] == s3[i - 1] ? dp[i - 1][0] : false; } for (int j = 1; j < lengthS1; ++j) { dp[0][j] = s1[j - 1] == s3[j - 1] ? dp[0][j - 1] : false; } for (int i = 1; i < lengthS2; ++i) { for (int j = 1; j < lengthS1; ++j) { if (s1[j - 1] == s3[i + j - 1]) { dp[i][j] = dp[i][j] || dp[i][j - 1]; } if (s2[i - 1] == s3[i + j - 1]) { dp[i][j] = dp[i][j] || dp[i - 1][j]; } } } return dp[lengthS2 - 1][lengthS1 - 1]; } };
2/28/2013
Surrounded Regions
Surrounded RegionsFeb 22
Given a 2D board containing
'X'
and 'O'
, capture all regions surrounded by 'X'
.
A region is captured by flipping all
'O'
s into 'X'
s in that surrounded region .
For example,
X X X X X O O X X X O X X O X X
After running your function, the board should be:
X X X X X X X X X X X X X O X X
class Solution { public: void solve(vector<vector<char>> &board) { // Start typing your C/C++ solution below // DO NOT write int main() function if (board.size() <= 1) return; int rows = board.size(); int cols = board[0].size(); vector<vector<bool>> visited(rows, vector<bool>(cols, false)); vector<vector<bool>> checked(rows, vector<bool>(cols, false)); for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { if (!visited[i][j]) { if (board[i][j] == 'O') { if (checkIfSurrounded(i, j, board, visited, checked)) { markChecked(i, j, board, checked); } } else { visited[i][j] = true; } } } } } bool checkIfSurrounded(int i, int j, vector<vector<char>> &board, vector<vector<bool>> &visited, vector<vector<bool>> &checked) { queue<Pos> q; bool result = true; q.push(Pos(i, j)); visited[i][j] = true; while (!q.empty()) { Pos pos = q.front(); q.pop(); i = pos.row; j = pos.col; checked[i][j] = true; if (j - 1 >= 0) { if (board[i][j - 1] == 'O' && !visited[i][j - 1]) { q.push(Pos(i, j - 1)); visited[i][j - 1] = true; } } else { result = false; } if (j + 1 < board[0].size()) { if (board[i][j + 1] == 'O' && !visited[i][j + 1]) { q.push(Pos(i, j + 1)); visited[i][j + 1] = true; } } else { result = false; } if (i + 1 < board.size()) { if (board[i + 1][j] == 'O' && !visited[i + 1][j]) { q.push(Pos(i + 1, j)); visited[i + 1][j] = true; } } else { result = false; } if (i - 1 >= 0) { if (board[i - 1][j] == 'O' && !visited[i - 1][j]) { q.push(Pos(i - 1, j)); visited[i - 1][j] = true; } } else { result = false; } } return result; } void markChecked(int i, int j, vector<vector<char>> &board, vector<vector<bool>> &checked) { queue<Pos> q; bool result = true; q.push(Pos(i, j)); while (!q.empty()) { Pos pos = q.front(); q.pop(); i = pos.row; j = pos.col; board[i][j] = 'X'; checked[i][j] = false; if (j - 1 >= 0) { if (checked[i][j - 1]) { q.push(Pos(i, j - 1)); checked[i][j - 1] = false; } } if (j + 1 < board[0].size()) { if (checked[i][j + 1]) { q.push(Pos(i, j + 1)); checked[i][j + 1] = false; } } if (i + 1 < board.size()) { if (checked[i + 1][j]) { q.push(Pos(i + 1, j)); checked[i + 1][j] = false; } } if (i - 1 >= 0) { if (checked[i - 1][j]) { q.push(Pos(i - 1, j)); checked[i - 1][j] = false; } } } } typedef struct Pos { int row, col; Pos(int i, int j): row(i), col(j) {}; }; };
2/21/2013
Restore IP Addresses
Restore IP AddressesAug 8 '12
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given
Given
"25525511135"
,
return
["255.255.11.135", "255.255.111.35"]
. (Order does not matter)DFS
class Solution { public: vector<string> restoreIpAddresses(string s) { // Start typing your C/C++ solution below // DO NOT write int main() function if (s.size() > 12 || s.size() < 4) return vector<string>(); return getValidIP(s.c_str(), 0); } vector<string> getValidIP(const char *c, int n) { const char *head = c; if (n == 3) { int num = 0; while (*c != '\0') { num = num * 10 + *c - '0'; ++c; } vector<string> ret; // last segment requirements // at least one digit and at most one leading zero if (c - head > 1 && *head == '0' || c == head) return ret; // segment number cannot exceed 255 if (num <= 255) { string seg(head, c - head); ret.push_back(seg); } return ret; } int num = 0; vector<string> ret; for (int i = 0; i < 3; ++i) { // reaches end or digits exceed 3 if (*c == '\0' || c - head > 2) break; num = num * 10 + *c - '0'; // each segment can be at most 255 if (num > 255) break; vector<string> rest = getValidIP(++c, n + 1); string add_seg(head, c - head); for (auto s : rest) { string address(add_seg); address += "."; address += s; ret.push_back(address); } // only one leading 0 allowed if (*(c - 1) == '0' && i == 0) break; } return ret; } };
2/11/2013
Reverse Linked List II
Reverse Linked List IIJun 27 '12
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given
Given
1->2->3->4->5->NULL
, m = 2 and n = 4,
return
1->4->3->2->5->NULL
.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *reverseBetween(ListNode *head, int m, int n) { // Start typing your C/C++ solution below // DO NOT write int main() function nodeAtN = NULL; nodeAfterN = NULL; return revHelper(head, m - 1, n - 1); } ListNode *revHelper(ListNode *current, int m, int n) { if (!current) return NULL; ListNode *ret = current; if (m > 0) { current->next = revHelper(current->next, m - 1, n - 1); } else if (n > 0) { ListNode *currentNext = revHelper(current->next, m - 1, n - 1); currentNext->next = current; if (m == 0) { current->next = nodeAfterN; ret = nodeAtN; } } else if (n == 0) { nodeAtN = current; nodeAfterN = current->next; } return ret; } private: ListNode *nodeAfterN; ListNode *nodeAtN; };
Subscribe to:
Posts (Atom)