tag:blogger.com,1999:blog-83345141898872827962024-03-14T05:55:20.855-07:00Silent Codesilenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.comBlogger108125tag:blogger.com,1999:blog-8334514189887282796.post-1158920219894036642017-07-15T20:18:00.001-07:002017-07-15T21:49:55.791-07:00Walls and Gates -- LeetCode 286<b>[Question]</b><br />
<div style="color: #494949; font-family: Arial, Helvetica, sans-serif; font-size: 14px; margin: 10px auto; padding: 0px;">
You are given a <em style="margin: 0px; padding: 0px;">m x n</em> 2D grid initialized with these three possible values.</div>
<ol style="color: #494949; font-family: Arial, Helvetica, sans-serif; font-size: 14px; margin: 0px; padding: 0px 0px 0px 40px;">
<li style="list-style: decimal; margin: 0px; padding: 0px;"><code style="margin: 0px; padding: 0px;">-1</code> - A wall or an obstacle.</li>
<li style="list-style: decimal; margin: 0px; padding: 0px;"><code style="margin: 0px; padding: 0px;">0</code> - A gate.</li>
<li style="list-style: decimal; margin: 0px; padding: 0px;"><code style="margin: 0px; padding: 0px;">INF</code> - Infinity means an empty room. We use the value <code style="margin: 0px; padding: 0px;">2<sup style="margin: 0px; padding: 0px;">31</sup> - 1 = 2147483647</code> to represent <code style="margin: 0px; padding: 0px;">INF</code> as you may assume that the distance to a gate is less than <code style="margin: 0px; padding: 0px;">2147483647</code>.</li>
</ol>
<div style="color: #494949; font-family: Arial, Helvetica, sans-serif; font-size: 14px; margin: 10px auto; padding: 0px;">
Fill each empty room with the distance to its <em style="margin: 0px; padding: 0px;">nearest</em> gate. If it is impossible to reach a gate, it should be filled with <code style="margin: 0px; padding: 0px;">INF</code>.</div>
<div style="color: #494949; font-family: Arial, Helvetica, sans-serif; font-size: 14px; margin: 10px auto; padding: 0px;">
For example, given the 2D grid:</div>
<pre style="color: #494949; font-size: 14px; padding: 0px; white-space: pre-wrap; word-wrap: break-word;">INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF</pre>
<div style="color: #494949; font-family: Arial, Helvetica, sans-serif; font-size: 14px; margin: 10px auto; padding: 0px;">
After running your function, the 2D grid should be:</div>
<pre style="color: #494949; font-size: 14px; padding: 0px; white-space: pre-wrap; word-wrap: break-word;"> 3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4</pre>
<pre style="color: #494949; font-size: 14px; padding: 0px; white-space: pre-wrap; word-wrap: break-word;"></pre>
<b><br /></b>
<b>[Analysis]</b><br />
DFS starting from each gate, each visited room store the minimum distance. It is also possible to use BFS.<br />
<br />
<b>[Solution]</b><br />
void walls_and_gates (vector<vector<int>>& grid) {<br />
for (int i=0; i<grid.size(); i++)<br />
for(int j=0; j<grid[0].size(); j++)<br />
if (grid[i][j]==0) dfs(grid, i, j, 0);<br />
return;<br />
}<br />
<br />
void dfs (vector<vector<int>>& grid, int i, int j, int dist) {<br />
if (i>=grid.size() || i<0 || j<0 || j>=grid[0].size() || grid[i][j]<dist) return;<br />
grid[i][j] = dist;<br />
dfs(grid, i+1, j, dist+1);<br />
dfs(grid, i, j+1, dist+1);<br />
dfs(grid, i-1, j, dist+1);<br />
dfs(grid, i, j-1, dist+1);<br />
}silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-27253409938915431122017-07-15T16:41:00.002-07:002017-07-15T16:41:44.845-07:00Verify Preorder Serialization of a Binary Tree -- LeetCode 331<b>[Question]</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node's value. If it is a null node, we record using a sentinel value such as <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">#</code>.</div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;"> _9_
/ \
3 2
/ \ / \
4 1 # 6
/ \ / \ / \
# # # # # #
</pre>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
For example, the above binary tree can be serialized to the string <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">"9,3,4,#,#,1,#,#,2,#,6,#,#"</code>, where <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">#</code>represents a null node.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Each comma separated value in the string must be either an integer or a character <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">'#'</code> representing <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">null</code>pointer.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
You may assume that the input format is always valid, for example it could never contain two consecutive commas such as <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">"1,,3"</code>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example 1:</span><br style="box-sizing: border-box;" /><code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">"9,3,4,#,#,1,#,#,2,#,6,#,#"</code><br style="box-sizing: border-box;" />Return <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">true</code></div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example 2:</span><br style="box-sizing: border-box;" /><code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">"1,#"</code><br style="box-sizing: border-box;" />Return <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">false</code></div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example 3:</span><br style="box-sizing: border-box;" /><code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">"9,#,#,1"</code><br style="box-sizing: border-box;" />Return <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">false</code></div>
<b>[Analysis]</b><br />
There are two approaches, using stack or using recursion.<br />
<br />
1) When scan the string backward (from the end), push "#" into stack. When non-"#" appears, there must be at least two "#" in the stack. Then pop up two "#" and push one "#" into stack -- that means one valid sub-tree is found. Then repeat the process until entire string is done. The stack should contain only one "#".<br />
<br />
2) Scan the string forward. For each sub-tree (starting from a non-"#'), the rest string should be able to be split into two valid sub-trees (left, right).<br />
<br />
<b>[Solution]</b><br />
//-- backward and using a stack --<br />
class Solution {<br />
public:<br />
bool isValidSerialization(string preorder) {<br />
reverse(preorder.begin(), preorder.end() );<br />
stringstream ss(preorder);<br />
<br />
string s;<br />
stack<string> st;<br />
while (getline(ss, s, ',')) {<br />
if (s.compare("#") == 0) st.push("#");<br />
else {<br />
if (st.size()<2) return false;<br />
st.pop(); // pop up 2 "#" and push 1 "#"<br />
}<br />
}<br />
return st.size()==1 && st.top().compare("#")==0;<br />
}<br />
};<br />
<br />
//-- recursion --<br />
class Solution {<br />
bool validate( string & str ) {<br />
if (str.empty()) return false;<br />
<br />
int end = str.find(',');<br />
if (end==string::npos) return false;<br />
<br />
string s = str.substr(0, end);<br />
str = str.substr(end+1);<br />
<br />
if (s.compare("#") == 0) return true;<br />
if (!validate(str)) return false;<br />
if (!validate(str)) return false;<br />
return true;<br />
}<br />
<br />
public:<br />
bool isValidSerialization(string preorder) {<br />
string data = preorder +",";<br />
return validate( data ) && data.empty();<br />
}<br />
};silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-11799028123957808782017-04-30T16:06:00.001-07:002017-04-30T16:10:48.631-07:00Next Permutation -- LeetCode 39<b>[Question]</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
The replacement must be in-place, do not allocate extra memory.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.<br />
<code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">1,2,3</code> → <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">1,3,2</code><br />
<code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">3,2,1</code> → <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">1,2,3</code><br />
<code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">1,1,5</code> → <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">1,5,1</code></div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;">
<div style="box-sizing: border-box; margin-bottom: 10px;">
<a href="https://leetcode.com/subscribe/" style="background-color: transparent; box-sizing: border-box; color: #0088cc; text-decoration-line: none;">Subscribe</a> to see which companies asked this question.</div>
</div>
<br />
<b>[Thoughts]</b><br />
In C++ STL lib, there is a function "<a href="http://www.cplusplus.com/reference/algorithm/next_permutation/">next_permutation()</a>" which exactly matches the need.<br />
<br />
To do it manually, think of the (lexicographically) largest permutation -- that must be a decreasing sequence. For any other permutations, we can come up with the following steps to get the next one:<br />
1) Find the increasing sequence from right to left, use i to denote the position of first decreasing digit.<br />
2) Find the fist number, from right to left, that is larger than N[i].<br />
3) Swap N[i] and N[j].<br />
4) Reverse the sub-string from N[i+1] to the end.<br />
<b><br /></b>
Additional note: the "<a href="https://leetcode.com/problems/next-greater-element-iii/#/description">Next Greater Number III</a>" -- LeetCode 556 is an alternative form of the same problem.<br />
<br />
<b>[Solution]</b><br />
//<br />
//-- Using STL --<br />
//<br />
void nextPermutation(vector<int>& nums) {<br />
next_permutation(nums.begin(), nums.end());<br />
<br />
}<br />
<br />
//<br />
//-- Manually --<br />
//<br />
class Solution {<br />
public:<br />
void nextPermutation(vector<int>& nums) {<br />
if (nums.size()<2) return;<br />
<br />
int i= nums.size()-2;<br />
while(i>=0 && nums[i]>=nums[i+1]) i--;<br />
if (i>=0) {<br />
int j= nums.size()-1;<br />
while(i<j && nums[i]>=nums[j]) j--;<br />
swap(nums[i], nums[j]);<br />
}<br />
reverse(nums.begin()+i+1, nums.end());<br />
}<br />
};<br />
<br />
//<br />
//-- Using STL again --<br />
//<br />
void nextPermutation(vector<int>& nums) {<br />
auto i = is_sorted_until(nums.rbegin(), nums.rend());<br />
if (i != nums.rend())<br />
swap(*i, *upper_bound(nums.rbegin(), i, *i));<br />
reverse(nums.rbegin(), i);<br />
}<br />
<br />silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-76284635368347426472017-04-19T23:05:00.000-07:002017-04-19T23:05:17.640-07:00Split Array Largest Sum -- LeetCode 419<b>[Question]</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Given an array which consists of non-negative integers and an integer <i style="box-sizing: border-box;">m</i>, you can split the array into <i style="box-sizing: border-box;">m</i> non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these <i style="box-sizing: border-box;">m</i> subarrays.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Note:</span><br />
Given <i style="box-sizing: border-box;">m</i> satisfies the following constraint: 1 ≤ m ≤ length(nums) ≤ 14,000.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Examples:</span></div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;">Input:
<span style="box-sizing: border-box; font-weight: 700;">nums</span> = [7,2,5,10,8]
<span style="box-sizing: border-box; font-weight: 700;">m</span> = 2
Output:
18
Explanation:
There are four ways to split <span style="box-sizing: border-box; font-weight: 700;">nums</span> into two subarrays.
The best way is to split it into <span style="box-sizing: border-box; font-weight: 700;">[7,2,5]</span> and <span style="box-sizing: border-box; font-weight: 700;">[10,8]</span>,
where the largest sum among the two subarrays is only 18.</pre>
<b>[Analysis]</b><br />
The largest sum <i>S</i> of each sub-array after a split, is within the range of [max element of the array, sum of the array]. Considering each possible <i>S</i>, if <i>S</i> is too large, the array could be split only by a number less than m; if <i>S</i> is too small, the array will be split by a number larger than m. So, using binary search, the minimal <i>S </i>will be found. <br />
<br />
<b>[Solution]</b><br />
class Solution {
<br />
public:
<br />
int splitArray(vector<int>& nums, int m) {
<br />
int lo=0, hi=0;
<br />
for (auto& n: nums) {
<br />
hi +=n;
<br />
lo = max(lo, n);
<br />
}
<br />
<br />
auto cut_by=[&](int upper) {
<br />
int cnt = 0, sum=0;
<br />
for (int i=0; i< nums.size(); i++) {
<br />
if (sum==0) cnt++;
<br />
sum += nums[i];
<br />
if (sum>upper) i--, sum=0;
<br />
}
<br />
return cnt<=m;
<br />
};
<br />
<br />
while (lo<hi) {
<br />
int mid = lo+(hi-lo)/2;
<br />
if (cut_by(mid))
<br />
hi = mid;
<br />
else
<br />
lo = mid+1;
<br />
}
<br />
return lo;
<br />
}
<br />
};<br />
<br />silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-38871225399402274122017-04-19T21:01:00.002-07:002017-04-19T21:01:39.422-07:00Number of Connected Components in an Undirected Graph -- LeetCode 323<b>[Question]</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 12.6000003814697px; padding: 2px 4px;">n</code> nodes labeled from <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 12.6000003814697px; padding: 2px 4px;">0</code> to <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 12.6000003814697px; padding: 2px 4px;">n - 1</code> and
a list of undirected edges (each edge is a pair of nodes), write a
function to find the number of connected components in an undirected
graph.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example 1:</span></div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; line-height: 1.42857143; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;"> 0 3
| |
1 --- 2 4
</pre>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 12.6000003814697px; padding: 2px 4px;">n = 5</code> and <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 12.6000003814697px; padding: 2px 4px;">edges = [[0, 1], [1, 2], [3, 4]]</code>, return <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 12.6000003814697px; padding: 2px 4px;">2</code>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example 2:</span></div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; line-height: 1.42857143; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;"> 0 4
| |
1 --- 2 --- 3
</pre>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
Given <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 12.6000003814697px; padding: 2px 4px;">n = 5</code> and <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 12.6000003814697px; padding: 2px 4px;">edges = [[0, 1], [1, 2], [2, 3], [3, 4]]</code>, return <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 12.6000003814697px; padding: 2px 4px;">1</code>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Note:</span><br />
You can assume that no duplicate edges will appear in <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 12.6000003814697px; padding: 2px 4px;">edges</code>. Since all edges are undirected, <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 12.6000003814697px; padding: 2px 4px;">[0, 1]</code> is the same as <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 12.6000003814697px; padding: 2px 4px;">[1, 0]</code> and thus will not appear together in <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 12.6000003814697px; padding: 2px 4px;">edges</code>.</div>
<br />
<b>[Analysis]</b><br />
Classic <a href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure">Union-find problem</a>. <br />
<br />
<b>[Solution]</b><br />
class UnionFind {<br />
vector<int> u;<br />
<br />
public:<br />
UnionFind(int n) { <br />
u =vector<int>(n,0);<br />
for (int i=0; i<n; i++)<br />
u[i] = i;<br />
}<br />
<br />
int find(int i) {<br />
if (u[i]==i) return i;<br />
u[i] = find(u[i]);<br />
return u[i];<br />
}<br />
<br />
void unions(int i, int j) {<br />
u[find(i)] = find(j);<br />
}<br />
};<br />
<br />
int countComponents(vector<pair<int,int>>& edges, int n) {<br />
UnionFind uf(n);<br />
<br />
for (auto& e:edges)<br />
uf.unions(e.first, e.second);<br />
<br />
unordered_set<int> res;<br />
for(int i=0; i<n; i++) <br />
res.insert(uf.find(i));<br />
<br />
return res.size();<br />
}<br />
<br />
<br />silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-18925804954838651572017-04-06T12:36:00.002-07:002017-04-06T12:36:41.968-07:00Combination Sum II, III -- LeetCode 40, 216<b>[Questions]</b><br />
<b>Combination Sum II:</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Given a collection of candidate numbers (<span style="box-sizing: border-box; font-weight: 700;"><i style="box-sizing: border-box;">C</i></span>) and a target number (<span style="box-sizing: border-box; font-weight: 700;"><i style="box-sizing: border-box;">T</i></span>), find all unique combinations in <span style="box-sizing: border-box; font-weight: 700;"><i style="box-sizing: border-box;">C</i></span> where the candidate numbers sums to <span style="box-sizing: border-box; font-weight: 700;"><i style="box-sizing: border-box;">T</i></span>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Each number in <span style="box-sizing: border-box; font-weight: 700;"><i style="box-sizing: border-box;">C</i></span> may only be used <span style="box-sizing: border-box; font-weight: 700;">once</span> in the combination.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Note:</span></div>
<ul style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px; margin-top: 0px;">
<li style="box-sizing: border-box;">All numbers (including target) will be positive integers.</li>
<li style="box-sizing: border-box;">The solution set must not contain duplicate combinations.</li>
</ul>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
For example, given candidate set <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">[10, 1, 2, 7, 6, 1, 5]</code> and target <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">8</code>, <br style="box-sizing: border-box;" />A solution set is: </div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;">[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]</pre>
<b>Combination Sum III:</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;">
<div style="box-sizing: border-box; margin-bottom: 10px;">
Find all possible combinations of <i style="box-sizing: border-box;"><span style="box-sizing: border-box; font-weight: 700;">k</span></i> numbers that add up to a number <i style="box-sizing: border-box;"><span style="box-sizing: border-box; font-weight: 700;">n</span></i>, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.</div>
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;">
<br style="box-sizing: border-box;" /><div style="box-sizing: border-box; margin-bottom: 10px;">
<i style="box-sizing: border-box;"><span style="box-sizing: border-box; font-weight: 700;">Example 1:</span></i></div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
Input: <i style="box-sizing: border-box;"><span style="box-sizing: border-box; font-weight: 700;">k</span></i> = 3, <i style="box-sizing: border-box;"><span style="box-sizing: border-box; font-weight: 700;">n</span></i> = 7</div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
Output:</div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
</div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;">[[1,2,4]]
</pre>
<div style="box-sizing: border-box; margin-bottom: 10px;">
</div>
<br style="box-sizing: border-box;" /><div style="box-sizing: border-box; margin-bottom: 10px;">
<i style="box-sizing: border-box;"><span style="box-sizing: border-box; font-weight: 700;">Example 2:</span></i></div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
Input: <i style="box-sizing: border-box;"><span style="box-sizing: border-box; font-weight: 700;">k</span></i> = 3, <i style="box-sizing: border-box;"><span style="box-sizing: border-box; font-weight: 700;">n</span></i> = 9</div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
Output:</div>
<div style="box-sizing: border-box; margin-bottom: 10px;">
</div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;">[[1,2,6], [1,3,5], [2,3,4]]</pre>
</div>
<b><br /></b>
<b>[Thoughts]</b><br />
Similar to "<a href="http://slientcode.blogspot.com/2017/04/combination-sum.html">Combination Sum</a>", those are just variations. The same code skeleton of backtracking on a vector can be reused. The variations are marked in the following code.<br />
<br />
<b>[Solution]</b><br />
//-- Combination Sum II --<br />
<span style="font-family: "georgia" , "times new roman" , serif;">class Solution {</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> void backtrack(vector<int>& cand, int target, int start, vector<int>& tmplist, vector<vector<int>>& res) {</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> if (target<0) return;</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> if (target==0) {</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> res.push_back(tmplist); return;</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> }</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"><br /></span>
<span style="font-family: "georgia" , "times new roman" , serif;"> for (int i=start; i<cand.size();i++) {</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"><br /></span>
<span style="font-family: "georgia" , "times new roman" , serif;"> tmplist.push_back(cand[i]);</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> backtrack(cand, target-cand[i], i+1, tmplist, res);</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> tmplist.pop_back();</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> </span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> <span style="color: magenta;">while(cand[i+1]==cand[i]) i++; //skip duplicates</span></span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> }</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> }</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;">public:</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> vector<vector<int>> res;</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> vector<int> sublist;</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> <span style="color: magenta;">sort(candidates.begin(), candidates.end());</span></span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> backtrack(candidates, target, 0, sublist, res);</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> return res;</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> }</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;">};</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"><br /></span>
<span style="font-family: "georgia" , "times new roman" , serif;">//-- Combination Sum III --</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;">class Solution {</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> void backtrack(int len, int target, int start, vector<int>&tmplist, vector<vector<int>>& res) {</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> if (target<0) return;</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> if (target==0 && <span style="color: magenta;">tmplist.size()==len</span>) {</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> res.push_back(tmplist); return;</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> }</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> <span style="color: magenta;">if (tmplist.size()>len) return; // length limit</span></span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> </span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> for (int i=start; i<10; i++) {</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> tmplist.push_back(i);</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> backtrack(len, target-i, i+1, tmplist, res);</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> tmplist.pop_back();</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> } </span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> }</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;">public:</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> vector<vector<int>> combinationSum3(int k, int n) {</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> vector<vector<int>> res;</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> vector<int> tmplist;</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> backtrack(k, n, 1, tmplist, res);</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> return res;</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> }</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"></span><br />
<span style="font-family: "georgia" , "times new roman" , serif;">};</span>silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-34225546578465111442017-04-06T08:42:00.000-07:002017-04-06T09:28:37.036-07:00Combination Sum -- LeetCode 39<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
<b>[Question]</b><br />
Given a set of candidate numbers (<span style="box-sizing: border-box; font-weight: 700;"><i style="box-sizing: border-box;">C</i></span>) and a target number (<span style="box-sizing: border-box; font-weight: 700;"><i style="box-sizing: border-box;">T</i></span>), find all unique combinations in <span style="box-sizing: border-box; font-weight: 700;"><i style="box-sizing: border-box;">C</i></span> where the candidate numbers sums to <span style="box-sizing: border-box; font-weight: 700;"><i style="box-sizing: border-box;">T</i></span>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
The <span style="box-sizing: border-box; font-weight: 700;">same</span> repeated number may be chosen from <span style="box-sizing: border-box; font-weight: 700;"><i style="box-sizing: border-box;">C</i></span> unlimited number of times.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Note:</span></div>
<ul style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px; margin-top: 0px;">
<li style="box-sizing: border-box;">All numbers (including target) will be positive integers.</li>
<li style="box-sizing: border-box;">Elements in a combination (<i style="box-sizing: border-box;">a</i><span style="bottom: -0.25em; box-sizing: border-box; font-size: 11px; line-height: 0; position: relative; vertical-align: baseline;">1</span>, <i style="box-sizing: border-box;">a</i><span style="bottom: -0.25em; box-sizing: border-box; font-size: 11px; line-height: 0; position: relative; vertical-align: baseline;">2</span>, … , <i style="box-sizing: border-box;">a</i><span style="bottom: -0.25em; box-sizing: border-box; font-size: 11px; line-height: 0; position: relative; vertical-align: baseline;">k</span>) must be in non-descending order. (ie, <i style="box-sizing: border-box;">a</i><span style="bottom: -0.25em; box-sizing: border-box; font-size: 11px; line-height: 0; position: relative; vertical-align: baseline;">1</span> ≤ <i style="box-sizing: border-box;">a</i><span style="bottom: -0.25em; box-sizing: border-box; font-size: 11px; line-height: 0; position: relative; vertical-align: baseline;">2</span> ≤ … ≤ <i style="box-sizing: border-box;">a</i><span style="bottom: -0.25em; box-sizing: border-box; font-size: 11px; line-height: 0; position: relative; vertical-align: baseline;">k</span>).</li>
<li style="box-sizing: border-box;">The solution set must not contain duplicate combinations.</li>
</ul>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 14px; line-height: 30px; margin-bottom: 10px;">
For example, given candidate set <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">2,3,6,7</code> and target <code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">7</code>,<br />
A solution set is:<br />
<code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">[7]</code><br />
<code style="background-color: #f9f2f4; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 13px; padding: 2px 4px;">[2, 2, 3]</code> </div>
<b>[Thoughts]</b><br />
Since the candidate array has no duplicates, a combination can be picked up by a <i>starting position</i>, <i>a reduced target </i>and <i>a current candidate list</i>. Therefore, the kind of combination problems can be solved by a backtracking function, which tracks the reduced <i>target</i>, <i>start </i>position, <i>candidate sub-list, </i>and usually a bag of current results.<br />
<br />
<b>[Solution]</b><br />
class Solution {<br />
void co_sum (vector<int>& cand, int target, int start, vector<int>& sub_res, vector<vector<int>>& res){<br />
if (target==0) res.push_back(sub_res);<br />
<br />
for (int i=start; i<cand.size(); i++ ) {<br />
<br />
for (int j=1; cand[i]*j<=target; j++) {<br />
for (int k=0; k<j; k++) sub_res.push_back(cand[i]);<br />
co_sum(cand, target-cand[i]*j, i+1, sub_res, res);<br />
for (int k=0; k<j; k++) sub_res.pop_back();<br />
}<br />
<br />
}<br />
}<br />
public:<br />
vector<vector<int>> combinationSum(vector<int>& cand, int target) {<br />
sort(cand.begin(), cand.end(), greater<int>());<br />
vector<vector<int>> res;<br />
vector<int> sub_res;<br />
co_sum(cand, target, 0, sub_res, res);<br />
return res;<br />
}<br />
};silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-6722646337247851842017-04-05T22:05:00.003-07:002017-04-05T22:08:36.376-07:00Binary Tree Postorder/Inorder/Preoder Traversal (non-recursive) -- LeetCode 145, 94<b>[Question]</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Given a binary tree, return the <i style="box-sizing: border-box;">inorder</i> traversal of its nodes' values.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
For example:<br />
Given binary tree <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">[1,null,2,3]</code>,</div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;"> 1
\
2
/
3
</pre>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
return <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">[1,3,2]</code>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Note:</span> Recursive solution is trivial, could you do it iteratively?</div>
<b>[Analysis]</b><br />
The state of recursive calls can be simulated by stacks. The key is to find the branch (left or right) where the stack pop() happened. The preorder/inorder,/postorder functions are placed in differnt branch (in, left, right) respectively.<br />
<b><br /></b>
<b>[Solution]</b><br />
<span style="font-family: "times" , "times new roman" , serif;">class Solution {</span><br />
<span style="font-family: "times" , "times new roman" , serif;">public:</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> vector<int> inorderTraversal(TreeNode* root) {</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> if (!root) return {};</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> stack<TreeNode*> st;</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> TreeNode* p=root;</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> st.push(p);</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> </span><br />
<span style="font-family: "times" , "times new roman" , serif;"> vector<int> res;</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> while(!st.empty()) {</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> if (st.top()==p && !p->left && !p->right) { </span><br />
<span style="font-family: "times" , "times new roman" , serif;"> //-- leave node is reached and is at the top of stack.</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> res.push_back(st.top()->val); //--shared by all orders.</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> st.pop();</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> continue;</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> }</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> if (st.top()==p) {</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> <span style="color: magenta;"> //res.push_back(st.top()->val); // -- pre-order output here</span>.</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> p=p->left;</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> if (p) st.push(p);</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> }</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> else if (st.top()->left==p) {</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> res.push_back(st.top()->val); // -- in-order output here</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> p=st.top()->right;</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> if (p) st.push(p);</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> }</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> else if (st.top()->right==p) {</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> <span style="background-color: white;"><span style="color: magenta;">//</span></span></span><span style="background-color: white;"><span style="color: magenta;"><span style="font-family: "times" , "times new roman" , serif;">res.push_back(st.top()->val);</span><span style="font-family: "times" , "times new roman" , serif;"> //-- post-order output here</span></span></span><br />
<span style="font-family: "times" , "times new roman" , serif;"> p=st.top();</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> st.pop();</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> }</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> }</span><br />
<span style="font-family: "times" , "times new roman" , serif;"><br /></span>
<span style="font-family: "times" , "times new roman" , serif;"> return res;</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> }</span><br />
<span style="font-family: "times" , "times new roman" , serif;">};</span>silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-91483317524199961372017-04-05T08:53:00.003-07:002017-04-05T08:53:52.741-07:00Queue Reconstruction by Height -- LeetCode<b>[Question]</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">(h, k)</code>, where <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">h</code> is the height of the person and <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">k</code> is the number of people in front of this person who have a height greater than or equal to <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">h</code>. Write an algorithm to reconstruct the queue.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Note:</span><br />
The number of people is less than 1,100.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example</span></div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;">Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]</pre>
<b><br /></b>
<b>[Analysis]</b><br />
Be Greedy. Person (h,k) at position 0 should have k=0. So group all (h,0), the one with smallest h' is at position 0. Then look at all other persons (h,k) whose h is greater or equal to h', decrease their k by 1 (because h' contribute 1 to their k values). Repeat the previous steps and find person at position 1, .., n. The time complexity is O(N^2).<br />
<br />
Another way to reconstruct the queue is by sorting. Suppose a person (h',k'), all persons (h,k) with greater or equal height have been in a sorted queue Q, the k' is the right position to insert (h',k') into the Q and create a Q' while maintaining all existing (h,k). Repeat the same process on Q' and remaining persons. The time complexity is O(N^2).<br />
<b><br /></b>
<b>[Solution]</b><br />
//-- using sorting --<br />
class Solution {<br />
public:<br />
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {<br />
auto comp=[](pair<int,int> &a, pair<int,int> &b)<br />
{ return a.first<b.first || a.first==b.first && a.second > b.second;};<br />
sort (people.begin(), people.end(), comp);<br />
vector<int,int> res;<br />
for (int i=people.size(); i>=0; i++)<br />
res.(res.begin()+people[i].second, people[i]);<br />
}<br />
};<br />
<br />
//--greedy --<br />
class Solution {<br />
public:<br />
vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {<br />
vector<pair<int, int>> rslt;<br />
<br />
vector<pair<int, int>> bak (people);<br />
auto comp= [](pair<int, int> a, pair<int,int> b)<br />
{ return a.second < b.second || a.second ==b.second && a.first<b.first;};<br />
<br />
while (rslt.size()!= people.size() ) {<br />
auto it = min_element(bak.begin(), bak.end(), comp);<br />
rslt.push_back(people[it-bak.begin()] );<br />
it->second = INT_MAX;<br />
for (auto &p: bak) {<br />
if (p.second!=INT_MAX && p.first<=it->first) {<br />
p.second --;<br />
}<br />
}<br />
}<br />
return rslt;<br />
}<br />
};silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-90630398303236914472017-04-04T13:56:00.000-07:002017-04-04T13:56:09.011-07:00Maximum Square -- LeetCode 221<b>[Question]</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
For example, given the following matrix:</div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;">1 0 1 0 0
1 0 <span style="box-sizing: border-box; color: red;">1</span> <span style="box-sizing: border-box; color: red;">1</span> 1
1 1 <span style="box-sizing: border-box; color: red;">1</span> <span style="box-sizing: border-box; color: red;">1</span> 1
1 0 0 1 0
</pre>
<span style="background-color: white; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;">Return 4.</span><br />
<span style="background-color: white; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;"><br /></span>
<b>[Analysis]</b><br />
This is similar with the <a href="http://slientcode.blogspot.com/2016/06/maximal-rectangle-leetcode.html">Maximum Rectangle</a> problem. While it can be done by the same approach, there is a Dynamic Programming solution to solve this. <br />
<br />
Define S[i,j] = the length of largest square positioned at Matrix[i,j], then<br />
S[i,0] = 1 if Matrix[i,0]= '1';<br />
S[0,j] = 1 if Matrix[0,j]= '1';<br />
S[i,j] = min ( S[i-1,j-1], S[i-1,j], S[i,j-1] ) + 1 if Matrix[i,j]='1', i>0, j>0;<br />
<br />
Time complexity and space complexity are O(M x N).<br />
<b><br /></b>
<b>[Solution]</b><br />
class Solution {<br />
public:<br />
int maximalSquare(vector<vector<char>>& matrix) {<br />
if (matrix.empty()) return 0;<br />
<br />
vector<vector<int>> s(matrix.size(), vector<int>(matrix[0].size(),0) );<br />
int max_len=0;<br />
<br />
for (int i=0; i< matrix.size(); i++) {<br />
s[i][0] = (matrix[i][0]=='1')?1:0;<br />
max_len |= s[i][0];<br />
}<br />
<br />
for (int i=0; i< matrix[0].size(); i++) {<br />
s[0][i] = (matrix[0][i]=='1')?1:0;<br />
max_len |= s[0][i];<br />
}<br />
<br />
for (int i=1; i< matrix.size(); i++)<br />
for (int j=1; j<matrix[0].size(); j++) {<br />
if (matrix[i][j] =='0') continue;<br />
s[i][j] = min(min(s[i-1][j], s[i][j-1]),s[i-1][j-1])+1;<br />
max_len = max(max_len, s[i][j]);<br />
}<br />
<br />
return max_len*max_len;<br />
}<br />
<br />
};silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-79284976831625356022017-03-31T15:31:00.000-07:002017-03-31T15:31:11.336-07:00Single Element in a Sorted Array -- LeetCode 540<b>[Question]</b><br />
<span style="background-color: white; color: #333333; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;">Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.</span><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example 1:</span></div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;"><span style="box-sizing: border-box; font-weight: 700;">Input:</span> [1,1,2,3,3,4,4,8,8]
<span style="box-sizing: border-box; font-weight: 700;">Output:</span> 2
</pre>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example 2:</span></div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;"><span style="box-sizing: border-box; font-weight: 700;">Input:</span> [3,3,7,7,10,11,11]
<span style="box-sizing: border-box; font-weight: 700;">Output:</span> 10
</pre>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Note:</span> Your solution should run in O(log n) time and O(1) space.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<br /></div>
<b>[Solution]</b><br />
<b>//</b>--- C++ ---<br />
class Solution {<br />
public:<br />
int singleNonDuplicate(vector<int>& nums) {<br />
int l=0, r=nums.size();<br />
int mid = 0;<br />
while (l+1<r) {<br />
mid = (l+r)>>1;<br />
if (nums[mid]==nums[mid^0x01])<br />
l = mid+1;<br />
else<br />
r = mid;<br />
}<br />
return nums[l];<br />
}<br />
};<br />
<br />
//--- Python ---<br />
class Solution(object):<br />
def singleNonDuplicate(self, nums):<br />
lo, hi=0, len(nums)-1<br />
while lo<hi:<br />
m = (lo+hi)/2<br />
if nums[m]==nums[m^1]:<br />
lo = m+1<br />
else:<br />
hi = m<br />
return nums[lo]<br />
silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-66391120123596907452017-03-07T14:17:00.001-08:002017-03-07T14:17:28.107-08:00Reverse Pairs -- LeetCode 493<b>[Question]</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Given an array <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">nums</code>, we call <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">(i, j)</code> an <span style="box-sizing: border-box; font-weight: 700;"><i style="box-sizing: border-box;">important reverse pair</i></span> if <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">i < j</code> and <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">nums[i] > 2*nums[j]</code>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
You need to return the number of important reverse pairs in the given array.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example1:</span></div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;"><span style="box-sizing: border-box; font-weight: 700;">Input</span>: [1,3,2,3,1]
<span style="box-sizing: border-box; font-weight: 700;">Output</span>: 2
</pre>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example2:</span></div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;"><span style="box-sizing: border-box; font-weight: 700;">Input</span>: [2,4,3,5,1]
<span style="box-sizing: border-box; font-weight: 700;">Output</span>: 3
</pre>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Note:</span></div>
<ol style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px; margin-top: 0px;">
<li style="box-sizing: border-box;">The length of the given array will not exceed <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">50,000</code>.</li>
<li style="box-sizing: border-box;">All the numbers in the input array are in the range of 32-bit integer.</li>
</ol>
<b><br /></b>
<b>[Analysis]</b><br />
This is a typical problem for Binary Index Tree (BIT). Another solution is to use a BST with a smaller counter in each node -- but this solution will make time complexity O(N*N) for sorted input array. BIT is still a better solution.<br />
<b><br /></b>
<b>[Solution]</b><br />
class BIT {<br />
vector<int> nodes;<br />
int lowbit(int x) { return -x & x; }<br />
public:<br />
BIT(int n) : nodes(n+1,0) {};<br />
<br />
void add(int pos, int val) {<br />
while (pos<nodes.size()) {<br />
nodes[pos]+=val;<br />
pos += lowbit( pos );<br />
}<br />
}<br />
<br />
int count(int pos) {<br />
int res =0;<br />
while (pos>0) {<br />
res += nodes[pos];<br />
pos -= lowbit( pos );<br />
}<br />
return res;<br />
}<br />
};<br />
<br />
typedef long long LL;<br />
<br />
class Solution {<br />
public:<br />
int reversePairs(vector<int>& nums) {<br />
vector<pair<LL,int> > sorted;<br />
for (int i=0; i<nums.size(); i++) {<br />
sorted.push_back({(LL)nums[i],i+1});<br />
sorted.push_back({(LL)nums[i]<<1, -i-1});<br />
}<br />
sort(sorted.begin(), sorted.end(), [](pair<LL,int>& a, pair<LL,int>& b) {<br />
return a.first< b.first || a.first==b.first && a.second>b.second;<br />
});<br />
<br />
unordered_map<LL,int> map;<br />
for (int i=0; i<sorted.size(); i++)<br />
map[sorted[i].second] = i;<br />
<br />
<br />
BIT tree(sorted.size());<br />
int res=0;<br />
for (int i=nums.size()-1; i>=0; i--) {<br />
res += tree.count(map[i+1]);<br />
tree.add(map[-i-1]+1,1);<br />
}<br />
return res;<br />
}<br />
};silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-11430010348625539752017-01-01T14:25:00.002-08:002017-01-01T14:27:02.556-08:00Evaluate Division -- LeetCode 399<b>[Question]</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Equations are given in the format <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">A / B = k</code>, where <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">A</code> and <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">B</code> are variables represented as strings, and <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">k</code> is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">-1.0</code>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example:</span><br />
Given <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">a / b = 2.0, b / c = 3.0.</code><br />
queries are: <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .</code><br />
return <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">[6.0, 0.5, -1.0, 1.0, -1.0 ].</code></div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
The input is: <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries </code>, where <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">equations.size() == values.size()</code>, and the values are positive. This represents the equations. Return <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">vector<double></code>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
According to the example above:</div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;">equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. </pre>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.</div>
<b>[Analysis]</b><br />
Consider each equation as an edge in a directed graph, each string is a vertex, then the problem becomes to find a path for each pair of strings in the queries array.<br />
<br />
Inspired by <a href="https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm">Floyd-Warshall</a> algorithm, using a 2-D matrix to represent vertex A to vertex path (if exists), A[i][j] = A[i][k]*A[k][j], for k=0,...|v|-1.<br />
<b><br /></b>
<b>[Solution]</b><br />
class Solution {<br />
public:<br />
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {<br />
set<string> nodes;<br />
unordered_map<string, int> inv;<br />
<br />
for (auto& e:equations) {<br />
nodes.insert(e.first);<br />
nodes.insert(e.second);<br />
}<br />
int i=0;<br />
for (auto it= nodes.begin(); it!=nodes.end(); it++, i++)<br />
inv[*it] = i;<br />
<br />
vector<vector<double>> equ(nodes.size(), vector<double>(nodes.size(),-1.0));<br />
for (int i=0; i< nodes.size(); i++)<br />
equ[i][i]= 1.0;<br />
<br />
for (int i=0; i< equations.size(); i++) {<br />
int x = inv[equations[i].first];<br />
int y = inv[equations[i].second];<br />
equ[x][y] = values[i];<br />
equ[y][x] = 1.0 / values[i];<br />
}<br />
<br />
for (int k=0; k<nodes.size(); k++) {<br />
for (int i=0; i<nodes.size(); i++) {<br />
for (int j=i+1; j<nodes.size(); j++) {<br />
if (equ[i][k]!=-1.0 && equ[k][j]!=-1.0) {<br />
equ[i][j] = equ[i][k] * equ[k][j];<br />
equ[j][i] = 1.0/ equ[i][j];<br />
}<br />
}<br />
}<br />
}<br />
<br />
vector<double> res;<br />
for (auto& q: queries) {<br />
if (nodes.count(q.first) && nodes.count(q.second)) {<br />
int x= inv[q.first], y= inv[q.second];<br />
res.push_back( equ[x][y] );<br />
}<br />
else res.push_back(-1.0);<br />
}<br />
return res;<br />
}<br />
<br />
};silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-43124368932091888152016-12-29T16:05:00.000-08:002017-04-30T16:57:44.231-07:00Range Sum Query - Mutable -- LeetCode 307<b>[Question]</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Given an integer array <i style="box-sizing: border-box;">nums</i>, find the sum of the elements between indices <i style="box-sizing: border-box;">i</i> and <i style="box-sizing: border-box;">j</i> (<i style="box-sizing: border-box;">i</i> ≤ <i style="box-sizing: border-box;">j</i>), inclusive.</div>
<span style="background-color: white; color: #333333; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;">The </span><i style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;">update(i, val)</i><span style="background-color: white; color: #333333; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;"> function modifies </span><i style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;">nums</i><span style="background-color: white; color: #333333; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;"> by updating the element at index </span><i style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;">i</i><span style="background-color: white; color: #333333; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;"> to </span><i style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;">val</i><span style="background-color: white; color: #333333; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;">.</span><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example:</span></div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;">Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
</pre>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Note:</span></div>
<ol style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px; margin-top: 0px;">
<li style="box-sizing: border-box;">The array is only modifiable by the <i style="box-sizing: border-box;">update</i> function.</li>
<li style="box-sizing: border-box;">You may assume the number of calls to <i style="box-sizing: border-box;">update</i> and <i style="box-sizing: border-box;">sumRange</i> function is distributed evenly.</li>
</ol>
<b><br /></b>
<b>[Analysis]</b><br />
By using brute force on array itself, the update() can be achieved in O(1) and the sumRange() in O(N). It is not optimal when sumRange() to be called more often.<br />
<br />
An alternative way is to use <a href="http://codeforces.com/blog/entry/18051?">Segment Tree</a>. The Segment Tree is heap like data structure. Both update() and sumRange() can be achieved in O(LogN). Extra O(N) space is used though.<br />
<br />
Another range sum problem is "<a href="http://slientcode.blogspot.com/2016/06/count-of-range-sum-leetcode.html">Count of Range Sum</a>".<br />
<b><br /></b>
<b>[Solution]</b><br />
//<br />
//-- Segment Tree --<br />
//<br />
class NumArray {<br />
vector<int> seg;<br />
int n;<br />
public:<br />
NumArray(vector<int> &nums) {<br />
n = nums.size();<br />
seg.resize(n<<1);<br />
for (int i=n; i< (n<<1); i++) seg[i] = nums[i-n];<br />
for(int i=n-1; i>0; i--) seg[i] = seg[i<<1] + seg[i<<1|1];<br />
}<br />
<br />
void update(int i, int val) {<br />
int diff = val-seg[i+n];<br />
for( i+=n; i>0; i>>=1 )<br />
seg[i] += diff;<br />
}<br />
<br />
int sumRange(int i, int j) {<br />
int res=0;<br />
for (i+=n, j+=n; i<=j; i>>=1, j>>=1) {<br />
if (i&1) res+=seg[i++];<br />
if (!(j&1)) res+=seg[j--];<br />
}<br />
return res;<br />
}<br />
};<br />
<div>
<br /></div>
silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-43252914576025298022016-12-20T14:13:00.004-08:002016-12-20T20:40:45.192-08:00Word Break -- LeetCode 139<b>[Quesion]</b><br />
Given a string <i>s</i> and a dictionary of words <i>dict</i>, determine if <i>s</i> can be segmented into a space-separated sequence of one or more dictionary words.
<br />
For example, given<br />
<i>s</i> = <code>"leetcode"</code>,<br />
<i>dict</i> = <code>["leet", "code"]</code>.
<br />
Return true because <code>"leetcode"</code> can be segmented as <code>"leet code"</code>.<br />
<br />
<b>[Analysis]</b><br />
Dynamic Programming: using one array A[n] to store whether first n letters of string <i>s </i>form a word sequence in dictionary, and A[0]= true, A[i+1] will be true if A[j] == true and substr(j, i-j+1) is also a word in dictionary (0<=j<=i). The time complexity is O(N^2), space complexity is O(N).<br />
<br />
DFS: try each prefix in dictionary recursively. Use a status memo to trim recursion branches.<br />
<br />
Suppose Trie is built upon the word dictionary, Trie can help to get A[] initialized faster.<br />
<br />
<b>[Solution]</b><br />
// -- Dynamic Programming --<br />
class Solution {<br />
public:<br />
bool wordBreak(string s, unordered_set<string>& wordDict) {<br />
vector<bool> res(s.size()+1, false);<br />
res[0]=true;<br />
for (int i=0; i<s.size(); i++)<br />
for (int j=i; j>=0; j--) //-- faster than moving forward --<br />
if (res[j] && wordDict.count(s.substr(j,i-j+1)) ) {<br />
res[i+1] = true;<br />
break;<br />
}<br />
return res.back();<br />
}<br />
};<br />
<br />
// -- DFS --<br />
class Solution {<br />
unordered_set<string> seen; // -- to record failed branches<br />
public:<br />
bool wordBreak(string s, unordered_set<string>& wordDict) {<br />
if (wordDict.count(s)) return true;<br />
for (int i=0; i<s.size(); i++) {<br />
if (wordDict.count(s.substr(0,i+1)) ) {<br />
string ss = s.substr(i+1);<br />
if (seen.count(ss) ) continue;<br />
if (wordBreak(ss, wordDict))<br />
return true;<br />
else seen.insert(ss);<br />
}<br />
}<br />
return false;<br />
}<br />
};silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-13162845565165981432016-12-17T23:24:00.000-08:002016-12-20T21:07:19.033-08:00House Robber ||| -- LeetCode 337<b>[Question]</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Determine the maximum amount of money the thief can rob tonight without alerting the police.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example 1:</span></div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;"> <span style="box-sizing: border-box; color: red;">3</span>
/ \
2 3
\ \
<span style="box-sizing: border-box; color: red;">3 1</span>
</pre>
<span style="background-color: white; color: #333333; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;">Maximum amount of money the thief can rob = </span><span style="background-color: white; box-sizing: border-box; color: red; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;">3</span><span style="background-color: white; color: #333333; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;"> + </span><span style="background-color: white; box-sizing: border-box; color: red; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;">3</span><span style="background-color: white; color: #333333; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;"> + </span><span style="background-color: white; box-sizing: border-box; color: red; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;">1</span><span style="background-color: white; color: #333333; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;"> = </span><span style="background-color: white; box-sizing: border-box; color: #333333; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px; font-weight: 700;">7</span><span style="background-color: white; color: #333333; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;">.</span><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example 2:</span></div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;"> 3
/ \
<span style="box-sizing: border-box; color: red;">4</span> <span style="box-sizing: border-box; color: red;">5</span>
/ \ \
1 3 1
</pre>
<span style="background-color: white; color: #333333; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;">Maximum amount of money the thief can rob = </span><span style="background-color: white; box-sizing: border-box; color: red; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;">4</span><span style="background-color: white; color: #333333; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;"> + </span><span style="background-color: white; box-sizing: border-box; color: red; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;">5</span><span style="background-color: white; color: #333333; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;"> = </span><span style="background-color: white; box-sizing: border-box; color: #333333; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px; font-weight: 700;">9</span><span style="background-color: white; color: #333333; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;">.</span><br />
<span style="background-color: white; color: #333333; font-family: "helvetica neue" , "helvetica" , "arial" , sans-serif; font-size: 14px;"><br /></span>
<b>[Analysis]</b><br />
This is different from previous questions in this "House Robber" series. Assume S(n) is the max amount of money the robber can get at House[n],<br />
S(n) = max( S(n->left)+ S(n->right),<br />
H[n] + S(n->left->left) + S(n->left->right) + S(n->right->left) + S(n->right->right) )<br />
<br />
So we can use DFS to accomplish this.<br />
<br />
<b>[Solution]</b><br />
/**<br />
* Definition for a binary tree node.<br />
* struct TreeNode {<br />
* int val;<br />
* TreeNode *left;<br />
* TreeNode *right;<br />
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}<br />
* };<br />
*/<br />
class Solution {<br />
int helper(TreeNode* root, int &lsum, int &rsum) {<br />
if (root==NULL) return 0;<br />
<br />
int ll=0, lr=0, rl=0, rr=0;<br />
lsum = helper(root->left, ll, lr);<br />
rsum = helper(root->right, rl, rr);<br />
return max( lsum+rsum, root->val+ll+lr+rl+rr );<br />
}<br />
public:<br />
int rob(TreeNode* root) {<br />
int lsum=0, rsum=0;<br />
return helper(root, lsum, rsum);<br />
}<br />
<br />
};silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-92009980737873249882016-12-17T22:37:00.002-08:002016-12-17T22:37:34.418-08:00House Robber II -- LeetCode 213<b>[Question]</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Note:</span> This is an extension of <a href="https://leetcode.com/problems/house-robber/" style="background-color: transparent; box-sizing: border-box; color: #0088cc; text-decoration: none;">House Robber</a>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are <span style="box-sizing: border-box; font-weight: 700;">arranged in a circle.</span> That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight <span style="box-sizing: border-box; font-weight: 700;">without alerting the police</span>.</div>
<b>[Analysis]</b><br />
Assume S(0, n) is the largest amount the thief can get from <b>circle </b>houses H[0,..n], and R(x,y) is the largest amount from <b>linear </b>houses H[x, x+1,...y], then<br />
S(0,n) = max( R(0,n-1), R(1, n-2) + H[n]).<br />
<br />
Since R(x,y) can be calculated using the solution in <a href="http://slientcode.blogspot.com/2016/12/house-robber-leetcode-198.html">House Robber</a>, S(0,n) is resolved.<br />
<b><br /></b>
<b>[Solution]</b><br />
//--- Solution #1 ---<br />
class Solution {<br />
int robber(vector<int>& n, int lf, int rt) {<br />
int a=0, b=0, c=0;<br />
for (int i=lf; i<rt; i++) {<br />
c = max(b, a+n[i]);<br />
a=b, b=c;<br />
}<br />
return c;<br />
}<br />
public:<br />
int rob(vector<int>& nums) {<br />
if (nums.empty()) return 0;<br />
int n= nums.size();<br />
return max( robber(nums, 0, n-1), robber(nums, 1, n-2)+ nums.back());<br />
}<br />
};<br />
<br />
//--- Solution #2 ---<br />
class Solution {<br />
public:<br />
int rob(vector<int>& nums) {<br />
if (nums.empty()) return 0;<br />
if (nums.size()==1) return nums[0];<br />
<br />
int a=0, b=nums[0], c=0;<br />
int x=0, y=0, z=0;<br />
int res;<br />
for (int i=1; i<nums.size(); i++) {<br />
c = max(b, a+nums[i]); //R0(i)->c, b->R0(i-1)<br />
z = max(y, x+nums[i]); //R1(i)->z, x->R1(i-2)<br />
<br />
res = max( x + nums[i], b);<br />
<br />
a=b, b=c; <br />
x=y, y=z;<br />
}<br />
return res;<br />
}<br />
<br />
};<br />
<br />
<br />silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-83049297864372864882016-12-17T21:20:00.002-08:002016-12-17T21:20:45.065-08:00House Robber -- LeetCode 198<b>[Question]</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and <span style="box-sizing: border-box; font-weight: 700;">it will automatically contact the police if two adjacent houses were broken into on the same night</span>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight <span style="box-sizing: border-box; font-weight: 700;">without alerting the police</span>.</div>
<b>[Analysis]</b><br />
Assume the S(n) is the largest amount the robber can get from H[0,1,...n],<br />
S(n) = max( S(n-1), S(n-2) + H[n] )<br />
<br />
Further, we can assume there are two additional house before H[0], with zero assets. Use dynamic programming from the beginning of the Houses, we can S(0),... S(n). S(n) is the answer.<br />
<b><br /></b>
<b>[Solution]</b><br />
class Solution {<br />
public:<br />
int rob(vector<int>& nums) {<br />
if (nums.empty()) return 0;<br />
<br />
int a=0, b=0, c=0;<br />
for (int i=0; i<nums.size(); i++) {<br />
c = max(b, a+nums[i]);<br />
a=b, b=c;<br />
} <br />
return c;<br />
}<br />
<br />
};silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-64584135667633318312016-12-15T23:44:00.000-08:002016-12-15T23:48:38.457-08:00Longest Repeating Character Replacement -- LeetCode 424<b>[Question]</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most <i style="box-sizing: border-box;">k</i> times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Note:</span><br />
Both the string's length and <i style="box-sizing: border-box;">k</i> will not exceed 10<span style="box-sizing: border-box; font-size: 10.5px; line-height: 0; position: relative; top: -0.5em; vertical-align: baseline;">4</span>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example 1:</span></div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;"><span style="box-sizing: border-box; font-weight: 700;">Input:</span>
s = "ABAB", k = 2
<span style="box-sizing: border-box; font-weight: 700;">Output:</span>
4
<span style="box-sizing: border-box; font-weight: 700;">Explanation:</span>
Replace the two 'A's with two 'B's or vice versa.
</pre>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example 2:</span></div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;"><span style="box-sizing: border-box; font-weight: 700;">Input:</span>
s = "AABABBA", k = 1
<span style="box-sizing: border-box; font-weight: 700;">Output:</span>
4
<span style="box-sizing: border-box; font-weight: 700;">Explanation:</span>
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.</pre>
<b>[Analysis]</b><br />
Use a sliding window [j,i] on the string. When the length of the window (i-j+1 - count of most repeating letters) <= k, move ending point i forward and the sub strings in the window are candidates. When the length - count of most repeating letters > k, move starting point j forward until the sub string in window contains the candidate.<br />
<b><br /></b>
Similar to the "<a href="http://slientcode.blogspot.com/2012/04/minimum-window-substring.html">Minimum Window Sub-String</a>" problem.<br />
<br />
<b>[Solution]</b><br />
class Solution {<br />
public:<br />
int characterReplacement(string s, int k) {<br />
vector<int> counters(26,0);<br />
int j=0, max_cnt=0;<br />
int res = 0;<br />
for (int i=0; i<s.size(); i++) {<br />
counters[s[i]-'A']++;<br />
max_cnt = max(max_cnt, counters[s[i]-'A']);<br />
while (i-j+1 -max_cnt > k) {<br />
counters[s[j]-'A']--, j++;<br />
max_cnt = *max_element(counters.begin(), counters.end());<br />
}<br />
res = max(res, i-j+1);<br />
}<br />
<br />
return res;<br />
}<br />
};silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-90501660237040660942016-12-08T17:14:00.003-08:002016-12-08T17:14:30.868-08:00Single Number III -- LeetCode<b>[Question]</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Given an array of numbers <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">nums</code>, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
For example:</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Given <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">nums = [1, 2, 1, 3, 2, 5]</code>, return <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">[3, 5]</code>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Note</span>:</div>
<ol style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px; margin-top: 0px;">
<li style="box-sizing: border-box;">The order of the result is not important. So in the above example, <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">[5, 3]</code> is also correct.</li>
<li style="box-sizing: border-box;">Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?</li>
</ol>
<b>[Analysis]</b><br />
By XOR all the elements, we can get the XOR result of the two single elements {A,B}. Since A!=B, there must one bit different between A and B. Therefore, divide all elements into two sets based on the bit value. XOR each set will give the two elements separately.<br />
<br />
<b>[Solution]</b><br />
class Solution {<br />
public:<br />
vector<int> singleNumber(vector<int>& nums) {<br />
int sum = accumulate (nums.begin(), nums.end(), 0, bit_xor<int>());<br />
int diff = sum & (-sum);<br />
<br />
vector<int> res = {0,0};<br />
for (auto n: nums) {<br />
if (n & diff) res[0]^=n;<br />
else res[1]^=n;<br />
}<br />
return res;<br />
}<br />
<br />
};silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-52176926510346964602016-12-02T22:21:00.000-08:002016-12-02T22:21:05.363-08:00Longest Increasing Path in a Matrix -- LeetCode<b>[Question]</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Given an integer matrix, find the length of the longest increasing path.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example 1:</span></div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;">nums = [
[<span style="box-sizing: border-box; color: red;">9</span>,9,4],
[<span style="box-sizing: border-box; color: red;">6</span>,6,8],
[<span style="box-sizing: border-box; color: red;">2</span>,<span style="box-sizing: border-box; color: red;">1</span>,1]
]
</pre>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Return <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">4</code><br />
The longest increasing path is <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">[1, 2, 6, 9]</code>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example 2:</span></div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;">nums = [
[<span style="box-sizing: border-box; color: red;">3</span>,<span style="box-sizing: border-box; color: red;">4</span>,<span style="box-sizing: border-box; color: red;">5</span>],
[3,2,<span style="box-sizing: border-box; color: red;">6</span>],
[2,2,1]
]
</pre>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Return <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">4</code><br />
The longest increasing path is <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">[3, 4, 5, 6]</code>. Moving diagonally is not allowed.</div>
<b><br /></b>
<b>[Analysis]</b><br />
Using DFS from each position of the matrix, travel on each possible paths, and get the maximum length that the position can reach. The length of path in each position can be reused. Therefore, an additional matrix is used to record the length information of each position. The time complexity and space complexity are both O(MxN), the size of matrix.<br />
<br />
<b>[Solution]</b><br />
class Solution {<br />
vector<pair<int,int>> dd={{-1,0},{1,0},{0,1},{0,-1}};<br />
<br />
int searchPath(vector<vector<int>>& matrix, int i, int j, vector<vector<int>>& lens) {<br />
if (lens[i][j]!=0) return lens[i][j];<br />
<br />
int len=0;<br />
int temp = matrix[i][j];<br />
matrix[i][j] = INT_MIN;<br />
for (auto&d : dd) {<br />
int x = i+d.first, y=j+d.second;<br />
if (x>=0 && x<matrix.size() && y>=0 && y<matrix[0].size() && matrix[x][y]>temp) {<br />
len = max(len, searchPath(matrix, x, y, lens));<br />
}<br />
}<br />
matrix[i][j] = temp;<br />
lens[i][j] = 1 + len;<br />
return 1+len;<br />
}<br />
public:<br />
int longestIncreasingPath(vector<vector<int>>& matrix) {<br />
if (matrix.empty()) return 0;<br />
vector<vector<int>> lens(matrix.size(), vector<int>(matrix[0].size(), 0));<br />
<br />
int res=1;<br />
for (int i=0; i<matrix.size(); i++) {<br />
for (int j=0; j< matrix[0].size(); j++) {<br />
res = max(res, searchPath(matrix, i, j, lens) );<br />
}<br />
}<br />
return res;<br />
}<br />
<br />
};silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-10561242231031378182016-11-27T14:57:00.000-08:002017-08-13T22:49:14.425-07:00Partition Equal Subset Sum -- LeetCode 416<b>[Question]</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Given a <span style="box-sizing: border-box; font-weight: 700;">non-empty</span> array containing <span style="box-sizing: border-box; font-weight: 700;">only positive integers</span>, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Note:</span></div>
<ol style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px; margin-top: 0px;">
<li style="box-sizing: border-box;">Each of the array element will not exceed 100.</li>
<li style="box-sizing: border-box;">The array size will not exceed 200.</li>
</ol>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example 1:</span></div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;">Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
</pre>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example 2:</span></div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;">Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.</pre>
<b><br /></b>
<b>[Analysis]</b><br />
<span style="font-family: "georgia" , "times new roman" , serif;">This is a simplified <a href="https://en.wikipedia.org/wiki/Knapsack_problem">Knapsack problem</a>. The typical dynamic programming solution is to define dp[i][j] as if first i elements can get a sum of j, dp[0][0] is apparently true. The question becomes whether dp[<i>n</i>][<i>m</i>] is true, where <i>n</i> is the size of the input array and <i>m</i> is the half of the sum of <i>n</i> numbers. Furthermore,</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> dp[i][j] = d[i-1][j] // if do not select the <i>i-th</i> element</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"> || d[i-1][j- nums[i] ] // if select the i-th element</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"><br /></span>
<span style="font-family: "georgia" , "times new roman" , serif;">Since the iteration of the dp calculation is along the <i>i</i> variable. The 2-dimension dp formula can be implemented by one dimensional array. Therefore, the space complexity is O(M), M is the sum of all numbers; the time complexity is O(NxM).</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"><br /></span>
<span style="font-family: "georgia" , "times new roman" , serif;">Interestingly, because of the assumption on array elements -- every element <=100 and the array size is <= 200 , the sum of whole array is less than 20,000. There is a faster solution using bit manipulation to calculate all subset of the array. The bit manipulation approach can achieve the time complexity O(N) and space complexity O(M).</span><br />
<span style="font-family: "georgia" , "times new roman" , serif;"><br /></span>
<span style="font-family: "georgia" , "times new roman" , serif;">Derived from the bit manipulation, there is brute force approach to calculate all subset's sum using set but the time complexity will be O(2^N), much slower.</span><br />
<br />
<b>[Solution]</b><br />
//-- Dynamic Programming O(NxM) --<br />
<span style="font-family: "times" , "times new roman" , serif;">class Solution {</span><br />
<span style="font-family: "times" , "times new roman" , serif;">public:</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> bool canPartition(vector<int>& nums) {</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> //dp[i, j] -- first i elements can make a sum of j</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> //dp[0,0]= true;</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> //dp[i, j] = dp[i-1, j] || dp[i-1, j-A[i-1] ];</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> int sum = accumulate(nums.begin(), nums.end(), 0);</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> if (sum%2) return false;</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> </span><br />
<span style="font-family: "times" , "times new roman" , serif;"> vector<bool> dp(sum/2+1, false);</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> dp[0] = true;</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> </span><br />
<span style="font-family: "times" , "times new roman" , serif;"> for (int i=0; i<nums.size(); i++)</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> <span style="color: magenta;"> </span><span style="color: blue;">for (int j=dp.size()-1; j>0; j--) // -- must be in reversed order. </span></span><br />
<span style="font-family: "times" , "times new roman" , serif;"> dp[j]= dp[j] || j>=nums[i] && dp[ j-nums[i] ];</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> return dp.back();</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> }</span><br />
<span style="font-family: "times" , "times new roman" , serif;">};</span><br />
<br />
//-- Back Tracking --<br />
<span style="font-family: "times" , "times new roman" , serif;">class Solution {</span><br />
<span style="font-family: "times" , "times new roman" , serif;">public:</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> bool canPartition(vector<int>& nums) {</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> int sum = 0;</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> for(int i =0;i<nums.size();i++){</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> sum+= nums[i];</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> }</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> if(sum%2) return false;</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> sum /= 2;</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> sort(nums.rbegin(),nums.rend());</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> return helper(nums, sum, 0);</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> }</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> bool helper(vector<int>& nums, int sum, int index){</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> if(sum == nums[index]) return true;</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> if(sum < nums[index]) return false;</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> return helper(nums,sum-nums[index],index+1) || helper(nums,sum,index+1);</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> }</span><br />
<span style="font-family: "times" , "times new roman" , serif;">};</span><br />
<br />
//-- Bit Manipulation O(N) --<br />
<span style="font-family: "times" , "times new roman" , serif;">class Solution {</span><br />
<span style="font-family: "times" , "times new roman" , serif;">public:</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> bool canPartition(vector<int>& nums) {</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> <span style="color: blue;"> bitset<10001> bits(1); // -- assume the max sum is 20,000.</span></span><br />
<span style="font-family: "times" , "times new roman" , serif;"> int sum = accumulate(nums.begin(), nums.end(), 0);</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> <span style="color: magenta;">f<span style="color: blue;">or (auto n : nums) bits |= bits << n; </span></span></span><br />
<span style="font-family: "times" , "times new roman" , serif;"> return !(sum & 1) && bits[sum >> 1];</span><br />
<span style="font-family: "times" , "times new roman" , serif;"> }</span><br />
<span style="font-family: "times" , "times new roman" , serif;">};</span><br />
<br />
//-- Brute Force --<br />
class Solution {<br />
public:<br />
bool canPartition(vector<int>& nums) {<br />
unordered_set<int> sub;<br />
sub.insert(0);<br />
<br />
int sum = accumulate(nums.begin(), nums.end(), 0);<br />
if ((sum %2) == 1) return false;<br />
<br />
for (auto n: nums) {<br />
unordered_set<int> temp;<br />
for (auto x:sub) {<br />
temp.insert(x+n);<br />
}<br />
sub.insert(temp.begin(), temp.end());<br />
}<br />
<br />
return sub.count(sum/2);<br />
}<br />
};silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-1838650409838857682016-11-25T21:30:00.000-08:002016-11-25T21:30:07.948-08:00Word Search II -- LeetCode<b>[Question]</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Given a 2D board and a list of words from the dictionary, find all words in the board.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
For example,<br style="box-sizing: border-box;" />Given <span style="box-sizing: border-box; font-weight: 700;">words</span> = <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">["oath","pea","eat","rain"]</code> and <span style="box-sizing: border-box; font-weight: 700;">board</span> =</div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;">[
['<span style="box-sizing: border-box; color: #dd7700;">o</span>','<span style="box-sizing: border-box; color: #dd7700;">a</span>','a','n'],
['e','<span style="box-sizing: border-box; color: #dd3300;">t</span>','<span style="box-sizing: border-box; color: #dd0000;">a</span>','<span style="box-sizing: border-box; color: #dd0000;">e</span>'],
['i','<span style="box-sizing: border-box; color: #dd7700;">h</span>','k','r'],
['i','f','l','v']
]
</pre>
<span style="background-color: white; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;">Return </span><code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">["eat","oath"]</code><span style="background-color: white; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px;">.</span><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Note:</span><br style="box-sizing: border-box;" />You may assume that all inputs are consist of lowercase letters <code style="background-color: #f9f2f4; border-radius: 4px; box-sizing: border-box; color: #c7254e; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 12.6px; padding: 2px 4px;">a-z</code>.</div>
<b><br /></b>
<b>[Analysis]</b><br />
This is a typical Back Tracking problem. Using DFS to explore every letter on the board. Trie can be used to trim the branches of DFS -- no need to travel on string path which is not a prefix of any words in the target set. The time complexity is O(MxNxL) L is the number of nodes in Trie.<br />
<br />
<b>[Solution]</b><br />
class TrieNode {<br />
public:<br />
bool isWord;<br />
vector<TrieNode *> letters;<br />
// Initialize your data structure here.<br />
TrieNode(): isWord(false) {<br />
letters.resize(26, NULL);<br />
}<br />
};<br />
<br />
class Trie {<br />
public:<br />
Trie() {<br />
root = new TrieNode();<br />
}<br />
<br />
// Inserts a word into the trie.<br />
void insert(string word) {<br />
TrieNode* p=root;<br />
for (auto c: word) {<br />
int i =c-'a';<br />
if (!p->letters[i])<br />
p->letters[i] = new TrieNode();<br />
p = p->letters[i];<br />
}<br />
p->isWord = true;<br />
}<br />
<br />
// Returns if the word is in the trie.<br />
bool search(string word) {<br />
TrieNode* p=root;<br />
for (auto c: word) {<br />
int i = c-'a';<br />
if (!p->letters[i]) return false;<br />
p = p->letters[i];<br />
}<br />
return p->isWord;<br />
}<br />
<br />
// Returns if there is any word in the trie<br />
// that starts with the given prefix.<br />
bool startsWith(string prefix) {<br />
TrieNode* p=root;<br />
for (auto c: prefix) {<br />
int i = c-'a';<br />
if (!p->letters[i]) return false;<br />
p = p->letters[i];<br />
}<br />
return true;<br />
}<br />
<br />
TrieNode* getRoot() {<br />
return root;<br />
}<br />
private:<br />
TrieNode* root;<br />
};<br />
<br />
class Solution {<br />
Trie trie;<br />
int limit;<br />
vector<pair<int,int>> dd = {{0,1},{0,-1},{1,0},{-1,0}}; <br />
<br />
void searchWords( vector<vector<char>>& b, int i, int j, string s, TrieNode* p, set<string>& res) {<br />
char cur = b[i][j];<br />
if (s.size() == limit) return;<br />
p = p->letters[cur-'a'];<br />
if (p==NULL) return;<br />
if (p->isWord) res.insert(s+cur);<br />
<br />
b[i][j] = ' ';<br />
for (auto& d : dd) {<br />
int x = i+d.first, y=j+d.second;<br />
if ( 0<=x && x<b.size() && 0<=y && y<b[0].size() && b[x][y]!=' ' )<br />
searchWords(b, x, y, s+cur, p, res);<br />
}<br />
b[i][j]= cur;<br />
}<br />
public:<br />
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {<br />
limit = 0;<br />
for (auto& w: words) {<br />
trie.insert(w);<br />
limit = max(limit, (int)w.size() );<br />
}<br />
<br />
set<string> res;<br />
for (int i=0; i<board.size(); i++)<br />
for (int j=0; j<board[0].size(); j++) {<br />
searchWords( board, i, j, "", trie.getRoot(), res);<br />
}<br />
return vector<string>(res.begin(), res.end());<br />
}<br />
<br />
};silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-66883216131611695092016-11-25T13:37:00.000-08:002016-11-25T13:39:59.309-08:00Elimination Game -- LeetCode<b>[Question]</b><br />
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
There is a list of sorted integers from 1 to <i style="box-sizing: border-box;">n</i>. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
We keep repeating the steps again, alternating left to right and right to left, until a single number remains.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
Find the last number that remains starting with a list of length <i style="box-sizing: border-box;">n</i>.</div>
<div style="background-color: white; box-sizing: border-box; color: #333333; font-family: "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px; margin-bottom: 10px;">
<span style="box-sizing: border-box; font-weight: 700;">Example:</span></div>
<pre style="background-color: whitesmoke; border-radius: 4px; border: 1px solid rgb(204, 204, 204); box-sizing: border-box; color: #333333; font-family: Menlo, Monaco, Consolas, "Courier New", monospace; font-size: 13px; line-height: 1.42857; margin-bottom: 10px; overflow: auto; padding: 9.5px; word-break: break-all; word-wrap: break-word;">Input:
n = 9,
<u style="box-sizing: border-box;">1</u> 2 <u style="box-sizing: border-box;">3</u> 4 <u style="box-sizing: border-box;">5</u> 6 <u style="box-sizing: border-box;">7</u> 8 <u style="box-sizing: border-box;">9</u>
2 <u style="box-sizing: border-box;">4</u> 6 <u style="box-sizing: border-box;">8</u>
<u style="box-sizing: border-box;">2</u> 6
6
Output:
6</pre>
<b>[Analysis]</b><br />
The value of the last remaining number is equal to the position of that number in the original array. Think the process in backward: assume x is in position <i>i </i>in round <i>n</i>, then what is the position of x should be in the previous round <i>n-1</i>?<br />
1) If <i>n-1</i> is odd, the x must be in 2*i position in round <i>n-1.</i><br />
<i> </i>2) If <i>n-1 </i>is even, and the count of number in round <i>n-1</i> is even, the position of x must be in 2*i-1 in round <i>n-1.</i><br />
<i> </i>3) If <i>n-1 </i>is even, and the count of number in round <i>n-1</i> is odd, the position of x must be in 2*i in round <i>n-1.</i><br />
<i><br /></i>
Therefore, we can trace backward from position 1 (last remaining) to the position of the number in original array. The time complexity is O(Log N), the space complexity is O(Log N) -- space can be reduced to O(1) as it is only needed for the count of numbers in each round.<br />
<b><br /></b>
<b>[Solution]</b><br />
class Solution {<br />
public:<br />
int lastRemaining(int n) {<br />
int res = 1;<br />
<br />
stack<int> nums;<br />
while (n>1) {<br />
nums.push(n);<br />
n/=2;<br />
}<br />
while (!nums.empty()) {<br />
if (nums.size() % 2==0 && nums.top()%2==0)<br />
res = res*2-1;<br />
else<br />
res *=2;<br />
nums.pop();<br />
}<br />
return res;<br />
}<br />
};silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0tag:blogger.com,1999:blog-8334514189887282796.post-74757201070709871732016-11-25T11:40:00.001-08:002016-11-25T11:40:24.098-08:00Random Numbers with Exceptions<b>[Question]</b><br />
Write a function to generate random numbers in [0, N-1], excluding numbers in a given list. For example, N=10, the excluding list is {4, 6, 9}, then a random number is valid when it is not 4, or 6, or 9.<br />
<br />
<b>[Analysis]</b><br />
This is another question that Reservior Sampling can be applied. The generator function will exclude the numbers in the range and give the equal possibility to the rest.<br />
<br />
When there is only one number is excluded, the solution can be as simple as, generate one number from [0, N-2], if the generated number is equal to the excluded number, return N-1. This is a special case of Reservior Sampling.<br />
<br />
[<b>Solution]</b><br />
int rand_except(int n, unordered_set<int>& exp) {<br />
int res=-1, count=0;<br />
for (int i=0; i<n; i++) {<br />
if (exp.count(i)>=0) continue;<br />
if ( rand()%(++count)==0 ) res = i;<br />
}<br />
return res;<br />
}silenthill - sghttp://www.blogger.com/profile/00739852899417172192noreply@blogger.com0