Sunday, April 23, 2017

LeetCode Online Judge Questions Table

Leetcode (Finished)

# Title Difficulty Keyword
268 Missing Number Medium
267 Palindrome Permutation II Medium
266 Palindrome Permutation Easy
265 Paint House II Hard
264 Ugly Number II Medium
263 Ugly Number Easy
261 Graph Valid Tree Medium
260 Single Number III Medium
259 3Sum Smaller Medium
258 Add Digits Easy
257 Binary Tree Paths Easy
242 Valid Anagram Easy
241 Different Ways to Add Parentheses Medium
240 Search a 2D Matrix II Medium
239 Sliding Window Maximum Hard
238 Product of Array Except Self Medium
237 Delete Node in a Linked List Easy
236 Lowest Common Ancestor of a Binary Tree Medium
235 Lowest Common Ancestor of a Binary Search Tree Easy
234 Palindrome Linked List Easy
233 Number of Digit One Hard
232 Implement Queue using Stacks Easy
231 Power of Two Easy
230 Kth Smallest Element in a BST Medium
229 Majority Element II Medium
228 Summary Ranges Medium
227 Basic Calculator II Medium
226 Invert Binary Tree Easy
225 Implement Stack using Queues Easy
224 Basic Calculator Hard
223 Rectangle Area Easy
222 Count Complete Tree Nodes Medium
221 Maximal Square Medium
220 Contains Duplicate III Medium
219 Contains Duplicate II Easy
218 The Skyline Problem Hard
217 Contains Duplicate Easy
216 Combination Sum III Medium
215 Kth Largest Element in an Array Medium
214 Shortest Palindrome Hard
213 House Robber II Medium DP
212 Word Search II Hard
211 Add and Search Word - Data structure design Medium
210 Course Schedule II Medium
209 Minimum Size Subarray Sum Medium
208 Implement Trie (Prefix Tree) Medium
207 Course Schedule Medium
206 Reverse Linked List Easy
205 Isomorphic Strings Easy
204 Count Primes Easy
203 Remove Linked List Elements Easy
202 Happy Number Easy
201 Bitwise AND of Numbers Range Medium
200 Number of Islands Medium
199 Binary Tree Right Side View Medium
198 House Robber Easy
191 Number of 1 Bits Easy
190 Reverse Bits Easy
189 Rotate Array Easy
188 Best Time to Buy and Sell Stock IV Hard
187 Repeated DNA Sequences Medium
179 Largest Number Medium
174 Dungeon Game Hard
173 Binary Search Tree Iterator Medium
172 Factorial Trailing Zeroes Easy
171 Excel Sheet Column Number Easy
169 Majority Element Easy
168 Excel Sheet Column Title Easy
167 Two Sum II - Input array is sorted Medium
166 Fraction to Recurring Decimal Medium
165 Compare Version Numbers Easy
164 Maximum Gap Hard
162 Find Peak Element Medium
160 Intersection of Two Linked Lists Easy
155 Min Stack Easy
154 Find Minimum in Rotated Sorted Array II Hard
153 Find Minimum in Rotated Sorted Array Medium
152 Maximum Product Subarray Medium
151 Reverse Words in a String Medium
150 Evaluate Reverse Polish Notation Medium
149 Max Points on a Line Hard
148 Sort List Medium
147 Insertion Sort List Medium
146 LRU Cache Hard
145 Binary Tree Postorder Traversal Hard
144 Binary Tree Preorder Traversal Medium
143 Reorder List Medium
142 Linked List Cycle II Medium
141 Linked List Cycle Easy
140 Word Break II Hard
139 Word Break Medium
138 Copy List with Random Pointer Hard
137 Single Number II Medium
136 Single Number Easy
135 Candy Hard
134 Gas Station Medium
133 Clone Graph Medium
132 Palindrome Partitioning II Hard
131 Palindrome Partitioning Medium
130 Surrounded Regions Medium
129 Sum Root to Leaf Numbers Medium
128 Longest Consecutive Sequence Hard
127 Word Ladder Medium
126 Word Ladder II Hard
125 Valid Palindrome Easy
124 Binary Tree Maximum Path Sum Hard
123 Best Time to Buy and Sell Stock III Hard
122 Best Time to Buy and Sell Stock II Medium
121 Best Time to Buy and Sell Stock Easy
120 Triangle Medium
119 Pascal's Triangle II Easy
118 Pascal's Triangle Easy
117 Populating Next Right Pointers in Each Node II Hard
116 Populating Next Right Pointers in Each Node Medium
115 Distinct Subsequences Hard
114 Flatten Binary Tree to Linked List Medium
113 Path Sum II Medium
112 Path Sum Easy
111 Minimum Depth of Binary Tree Easy
110 Balanced Binary Tree Easy
109 Convert Sorted List to Binary Search Tree Medium
108 Convert Sorted Array to Binary Search Tree Medium
107 Binary Tree Level Order Traversal II Easy
106 Construct Binary Tree from Inorder and Postorder Traversal Medium
105 Construct Binary Tree from Preorder and Inorder Traversal Medium
104 Maximum Depth of Binary Tree Easy
103 Binary Tree Zigzag Level Order Traversal Medium
102 Binary Tree Level Order Traversal Easy
101 Symmetric Tree Easy
100 Same Tree Easy
99 Recover Binary Search Tree Hard
98 Validate Binary Search Tree Medium
97 Interleaving String Hard
96 Unique Binary Search Trees Medium
95 Unique Binary Search Trees II Medium
94 Binary Tree Inorder Traversal Medium
93 Restore IP Addresses Medium
92 Reverse Linked List II Medium
91 Decode Ways Medium
90 Subsets II Medium
89 Gray Code Medium
88 Merge Sorted Array Easy
87 Scramble String Hard
86 Partition List Medium
85 Maximal Rectangle Hard
84 Largest Rectangle in Histogram Hard
83 Remove Duplicates from Sorted List Easy
82 Remove Duplicates from Sorted List II Medium
81 Search in Rotated Sorted Array II Medium
80 Remove Duplicates from Sorted Array II Medium
79 Word Search Medium
78 Subsets Medium
77 Combinations Medium
76 Minimum Window Substring Hard
75 Sort Colors Medium
74 Search a 2D Matrix Medium
73 Set Matrix Zeroes Medium
72 Edit Distance Hard
71 Simplify Path Medium
70 Climbing Stairs Easy
69 Sqrt(x) Medium
68 Text Justification Hard
67 Add Binary Easy
66 Plus One Easy
65 Valid Number Hard
64 Minimum Path Sum Medium
63 Unique Paths II Medium
62 Unique Paths Medium
61 Rotate List Medium
60 Permutation Sequence Medium
59 Spiral Matrix II Medium
58 Length of Last Word Easy
57 Insert Interval Hard
56 Merge Intervals Hard
55 Jump Game Medium
54 Spiral Matrix Medium
53 Maximum Subarray Medium
52 N-Queens II Hard
51 N-Queens Hard
50 Pow(x, n) Medium
49 Group Anagrams Medium
48 Rotate Image Medium
47 Permutations II Medium
46 Permutations Medium
45 Jump Game II Hard
44 Wildcard Matching Hard
43 Multiply Strings Medium
42 Trapping Rain Water Hard
41 First Missing Positive Hard
40 Combination Sum II Medium
39 Combination Sum Medium
38 Count and Say Easy
37 Sudoku Solver Hard
36 Valid Sudoku Easy
35 Search Insert Position Medium
34 Search for a Range Medium
33 Search in Rotated Sorted Array Hard
32 Longest Valid Parentheses Hard
31 Next Permutation Medium
30 Substring with Concatenation of All Words Hard
29 Divide Two Integers Medium
28 Implement strStr() Easy
27 Remove Element Easy
26 Remove Duplicates from Sorted Array Easy
25 Reverse Nodes in k-Group Hard
24 Swap Nodes in Pairs Easy
23 Merge k Sorted Lists Hard
22 Generate Parentheses Medium
21 Merge Two Sorted Lists Easy
20 Valid Parentheses Easy
19 Remove Nth Node From End of List Easy
18 4Sum Medium
17 Letter Combinations of a Phone Number Medium
16 3Sum Closest Medium
15 3Sum Medium
14 Longest Common Prefix Easy
13 Roman to Integer Easy
12 Integer to Roman Medium
11 Container With Most Water Medium
10 Regular Expression Matching Hard
9 Palindrome Number Easy
8 String to Integer (atoi) Easy
7 Reverse Integer Easy
6 ZigZag Conversion Easy
5 Longest Palindromic Substring Medium
4 Median of Two Sorted Arrays Hard
3 Longest Substring Without Repeating Characters Medium
2 Add Two Numbers Medium
1 Two Sum Easy Hash Map

Wednesday, December 7, 2016

leetcode Question: Single Number III

Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

  1. The order of the result is not important. So in the above example, [5, 3] is also correct.
  2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Analysis:

From the previous questions we know that the bit manipulation would be a good start to go, same as this problem. The hard part is by XOR all the values in the array, we only have the XOR of the two numbers we have, say  x = a^b

From the figure I draw below, it is easy to see that:   the essential usage of XOR operation is to check whether the corresponding bits are same or not between two numbers. In other words, if there is any one bit between the two numbers is set to ‘1’  (e.g., any one bit in x is '1’), the two numbers (e.g., a and b) are impossible to be the same.

Let’s extend the above conclusion to this problem:
  1. We have a serise of numbers. 
  2. We have value x = a ^ b, but we don’t know which two numbers are a and b.
  3. But we know, there must be at least one bit in a and b are NOT the same. (because x is NOT 0, there must be at least one bit in x is 1)
  4. In other words, in a certain bit, say kth bit, a must be 0 and b must be 1, or vice versa.
  5. Look at the array, every number in the array may be a, or b.
  6. For every number in the array,look at the kth bit , it has only two possible values: 0 or 1.
  7. So if we divide the number in the arrary simplely by the kth bit, the array is divided into two part, and a and b must be in different part.
  8. For each part, except the number a (or b), all the other numbers must appear twice in the same part.
  9. Now the problem becomes the simple version of single number we have seen before.
  10. Done.
Therefore, we have successfully transit the problem into two sub problems, in which a simple loop with XOR operations will work well to solve.

Code (C++):

class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
vector<int> result(2,0);
int xor_res = 0;
for (int i = 0; i < nums.size();++i){
xor_res ^= nums[i];
}
int mask = xor_res ^ ( xor_res & (xor_res-1) );
int p=0;
int q=0;
for (int i=0;i<nums.size();++i){
if ( (nums[i] & mask) == 0){
p ^= nums[i];
}else{
q ^= nums[i];
}
}
result[0] = p;
result[1] = q;
return result;
}
};

Code (Python):

class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
r = 0
for num in nums:
r ^= num
mask = r ^ ( r & (r-1) )
p = 0
q = 0
for num in nums:
if (num & mask) == 0:
p ^= num
else:
q ^= num
return [p ,q]

leetcode Question: House Robber II

House Robber II

Note: This is an extension of House Robber.

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 arranged in a circle. 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.

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 without alerting the police.



Analysis:

Please read my previous post for the original version of the House Robber problem (link). 

In this problem, a new requirement is added :   the houses are in a circle.  In other words, previously we could rob the first house and it is OK to also rob the last one. But now since the last house and the first house are now adjacent, it is not allowed to rob those two houses at the same time. From the figure below, one can see that, different from previous version, now the path (arrows after house #4) has new connections to the front. 

Considering  the “states” in the last house, if we choose to rob it, when we go to the first house, now the only action we have is to NOT rob it. In other words, for the first house, we will never have the amount of money if we have robbed the last one. This can also be viewed as: We have never seen the first house, but search and rob houses from 2nd to the last. 

On the other hand, if we choose not to rob the last house, when we go to the first house, the actions are rob or not rob, which is common. Look at the last house, we are sure that we will NOT rob this house, then similarlly the probem becomes searching and robbing from 1st to the last -1 house. 

Obviously, in the above two cases, the larger result is the final value we want.

Code (C++):

class Solution {
public:
int rob(vector<int>& nums) {
int sz = nums.size();
int r = 0;
if (sz == 0) {return 0;}
if (sz < 4) {
for (int i=0;i<sz;i++){
r = max(r, nums[i]);
}
return r;
}
// From 0 to n-1
vector<int> res(sz,0);
res[0] = nums[0];
res[1] = max(nums[1],nums[0]);
int i=2;
while (i < sz-1){
res[i] = max(res[i-1], res[i-2] + nums[i]);
i++;
}
r = res[sz-2];
// From 1 to n
res.clear();
res[1] = nums[1];
res[2] = max(nums[1],nums[2]);
i = 3;
while (i<sz){
res[i] = max(res[i-1], res[i-2] + nums[i]);
i++;
}
return max(r, res[sz-1]);
}
};

Code (Python):

class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
sz = len(nums)
if sz == 0:
return 0
if sz < 4:
return max(nums)
res = [0 for x in range(sz)]
res[0] = nums[0]
res[1] = max(nums[0],nums[1])
r = 0
i = 2
while i < sz - 1:
res[i] = max(res[i-1], res[i-2] + nums[i])
i+=1
r = res[sz-2]
res = [0 for x in range(sz)]
res[1] = nums[1]
res[2] = max(nums[2],nums[1])
i = 3
while i < sz:
res[i] = max(res[i-1], res[i-2] + nums[i])
i+=1
return max(r, res[sz-1])