Using hashmap is much easier to implement the code.
O(n) time complexity and O(n) space
First, get the regular linked list and put the node pair in the hashmap
Second, set each node with correct random pointer.
public RandomListNode copyRandomList(RandomListNode head) {
Map<RandomListNode, RandomListNode> map = new HashMap<>();
RandomListNode p = head;
RandomListNode dummy = new RandomListNode(0);
RandomListNode q = dummy;
while (p!=null) {
q.next = new RandomListNode(p.label);
map.put(p, q.next);
p = p.next;
q = q.next;
}
p = head;
q = dummy;
while (p != null) {
q.next.random = map.get(p.random);
p = p.next;
q = q.next;
}
return dummy.next;
}
Better solution with O(n) time complexity and O(1) space.
public RandomListNode copyRandomList(RandomListNode head) {
RandomListNode p = head;
//copy the node in the list
while (p != null) {
RandomListNode next = p.next;
RandomListNode copy = new RandomListNode(p.label);
p.next = copy;
copy.next = next;
p = next;
}
//Set the random pointer correctly
p = head;
while (p != null) {
p.next.random = (p.random != null) ? p.random.next : null;
p = p.next.next;
}
//Reset the list to the original one
p = head;
RandomListNode headCopy = (p!=null) ? p.next : null;
while (p != null) {
RandomListNode copy = p.next;
p.next = copy.next;
p = p.next;
copy.next = (p != null) ? p.next : null;
}
return headCopy;
}
Tuesday, December 30, 2014
Monday, December 22, 2014
Compare Version Number LeetCode
Integer.valueOf("01") can handle conversion from string to integer.
public int compareVersion(String version1, String version2) {
String[] version1Res = version1.split("\\.");
String[] version2Res = version2.split("\\.");
int idx = Math.max(version1Res.length, version2Res.length);
int i=0;
while (i < idx) {
int c1 = i < version1Res.length ? Integer.valueOf(version1Res[i]):0;
int c2 = i < version2Res.length ? Integer.valueOf(version2Res[i]):0;
if (c1>c2) {
return 1;
} else if (c1<c2) {
return -1;
}
i++;
}
return 0;
}
public int compareVersion(String version1, String version2) {
String[] version1Res = version1.split("\\.");
String[] version2Res = version2.split("\\.");
int idx = Math.max(version1Res.length, version2Res.length);
int i=0;
while (i < idx) {
int c1 = i < version1Res.length ? Integer.valueOf(version1Res[i]):0;
int c2 = i < version2Res.length ? Integer.valueOf(version2Res[i]):0;
if (c1>c2) {
return 1;
} else if (c1<c2) {
return -1;
}
i++;
}
return 0;
}
Majority Element
Method 1: HashMap is always a quick solution for this kind of problems.
public int majorityElement(int[] num) {
Map<Integer,Integer> hm = new HashMap<Integer, Integer>();
for (int i=0; i<num.length; i++) {
if (!hm.containsKey(num[i])) {
hm.put(num[i], 1);
} else {
hm.put(num[i],hm.get(num[i])+1);
if (hm.get(num[i]) > num.length/2) {
return num[i];
}
}
}
return num[0];
}
Method 2: Bit Manipulation
It is similar to Single Number.
public int majorityElement(int[] num) {
//Bit manipulation
int[] countsPerBit = new int[32];
int result = 0;
for (int i=0; i<32; i++) {
int count = 0;
for (int j=0; j<num.length; j++) {
if((num[j]>>i&1) ==1) {
count++;
}
}
if (count > num.length/2) {
result |= (1<<i);
}
}
return result;
}
Method 3: Moore Voting Algorithm
This is super cool.
public int majorityElement(int[] num) {
//Moore voting algorithm
int elem = 0;
int count = 0;
for (int i=0; i<num.length; i++) {
if (count == 0) {
elem = num[i];
count = 1;
} else {
if (elem == num[i]) {
count++;
} else {
count--;
}
}
}
return elem;
}
Thursday, December 11, 2014
Evaluate Reverse Polish Notation LeetCode
Use stack to contain all the values. When we get the operators, we pop up two values for operation.
It's easy. It has lots of follow up question.
public int evalRPN(String[] tokens) {
if (tokens==null || tokens.length == 0) return 0;
if (tokens.length == 1) return Integer.valueOf(tokens[0]);
Stack<String> stack = new Stack<String>();
String operators = "+-*/";
for (int i=0; i<tokens.length; i++) {
if (!operators.contains(tokens[i])) {
stack.push(tokens[i]);
} else {
int a = Integer.valueOf(stack.pop());
int b = Integer.valueOf(stack.pop());
switch(tokens[i]) {
case "+" : stack.push(String.valueOf(a+b)); break;
case "-" : stack.push(String.valueOf(b-a)); break;
case "*" : stack.push(String.valueOf(a*b)); break;
case "/" : stack.push(String.valueOf(b/a)); break;
}
}
}
return Integer.valueOf(stack.pop());
}
It's easy. It has lots of follow up question.
public int evalRPN(String[] tokens) {
if (tokens==null || tokens.length == 0) return 0;
if (tokens.length == 1) return Integer.valueOf(tokens[0]);
Stack<String> stack = new Stack<String>();
String operators = "+-*/";
for (int i=0; i<tokens.length; i++) {
if (!operators.contains(tokens[i])) {
stack.push(tokens[i]);
} else {
int a = Integer.valueOf(stack.pop());
int b = Integer.valueOf(stack.pop());
switch(tokens[i]) {
case "+" : stack.push(String.valueOf(a+b)); break;
case "-" : stack.push(String.valueOf(b-a)); break;
case "*" : stack.push(String.valueOf(a*b)); break;
case "/" : stack.push(String.valueOf(b/a)); break;
}
}
}
return Integer.valueOf(stack.pop());
}
Intersection of Two LinkedList LeetCode (Important)
1. Find the length of each list
2. Scan from the same length of the short list in the longer list.
It should be O(n) time and O(1) space.
It is not easy for me :(
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
//Get the length 0f List A
int indexA = 0;
ListNode tempA = headA;
while (tempA != null) {
tempA = tempA.next;
indexA++;
}
//Get the length of List B
int indexB = 0;
ListNode tempB = headB;
while (tempB != null) {
tempB = tempB.next;
indexB++;
}
//Two pointers
ListNode longNode = (indexA > indexB) ? headA : headB;
ListNode shortNode = (longNode == headA) ? headB : headA;
int diff = Math.abs(indexA - indexB);
while (diff > 0) {
longNode = longNode.next;
diff--;
}
while (longNode != null) {
if (longNode.val == shortNode.val) {
return longNode;
}
longNode = longNode.next;
shortNode = shortNode.next;
}
return null;
}
Search 2D Matrix LeetCode (Important)
Very good question.
It can come with lots of follow up.
Step Wise method. I prefer this method. Easy to implement and very good for a quick solution during the interview.
public boolean searchMatrix(int[][] matrix, int target) {
int rowLen = matrix.length;
int colLen = matrix[0].length;
int row = 0;
int col = matrix[0].length-1;
if (matrix[0][0] > target || matrix[rowLen-1][colLen-1] < target) return false;
while (row < rowLen && col >= 0) {
if (matrix[row][col] > target) {
col--;
} else if (matrix[row][col] < target) {
row++;
} else {
return true;
}
}
return false;
}
Binary Search on row and column.
public boolean searchMatrix(int[][] matrix, int target) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int row = searchRow(matrix, 0, matrix.length, target);
int result = Arrays.binarySearch(matrix[row], target);
return result >= 0 ? true : false;
}
private int searchRow(int[][] matrix, int start, int end, int target) {
int mid = (start + end)/2;
if (start == mid) {
return mid;
}
if (matrix[mid][0] <= target) {
return searchRow(matrix, mid, end, target);
} else {
return searchRow(matrix, start, mid, target);
}
}
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix==null || matrix.length==0 || matrix[0].length==0) return false;
//Search the col
int l=0;
int r=matrix.length-1;
while (l<=r) {
int mid = (l+r)/2;
if (matrix[mid][0] == target) return true;
if (matrix[mid][0] > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
int row = r;
if (row < 0) return false;
//Search the row
l=0;
r=matrix[0].length-1;
while (l<=r) {
int mid = (l+r)/2;
if (matrix[row][mid] == target) return true;
if (matrix[row][mid] > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return false;
}
It can come with lots of follow up.
Step Wise method. I prefer this method. Easy to implement and very good for a quick solution during the interview.
public boolean searchMatrix(int[][] matrix, int target) {
int rowLen = matrix.length;
int colLen = matrix[0].length;
int row = 0;
int col = matrix[0].length-1;
if (matrix[0][0] > target || matrix[rowLen-1][colLen-1] < target) return false;
while (row < rowLen && col >= 0) {
if (matrix[row][col] > target) {
col--;
} else if (matrix[row][col] < target) {
row++;
} else {
return true;
}
}
return false;
}
Binary Search on row and column.
public boolean searchMatrix(int[][] matrix, int target) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int row = searchRow(matrix, 0, matrix.length, target);
int result = Arrays.binarySearch(matrix[row], target);
return result >= 0 ? true : false;
}
private int searchRow(int[][] matrix, int start, int end, int target) {
int mid = (start + end)/2;
if (start == mid) {
return mid;
}
if (matrix[mid][0] <= target) {
return searchRow(matrix, mid, end, target);
} else {
return searchRow(matrix, start, mid, target);
}
}
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix==null || matrix.length==0 || matrix[0].length==0) return false;
//Search the col
int l=0;
int r=matrix.length-1;
while (l<=r) {
int mid = (l+r)/2;
if (matrix[mid][0] == target) return true;
if (matrix[mid][0] > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
int row = r;
if (row < 0) return false;
//Search the row
l=0;
r=matrix[0].length-1;
while (l<=r) {
int mid = (l+r)/2;
if (matrix[row][mid] == target) return true;
if (matrix[row][mid] > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return false;
}
Sort Colors LeetCode
Two passes are easy to understand. Count and put all the numbers in.
public void sortColors(int[] A) {
// Note: The Solution object is instantiated only once and is reused by each test case.
if (A == null || A.length == 0) return;
int[] helper = new int[3];
for (int i=0; i<A.length; i++) {
helper[A[i]] ++;
}
int index = 0;
for (int j=0; j<3; j++) {
while (helper[j]-- > 0) {
A[index++] = j;
}
}
}
OK. Let's make it better.
ONE Pass.
index0 and index1 are two pointer for the current location of 0 and 1.
public void sortColors(int[] A) {
// Note: The Solution object is instantiated only once and is reused by each test case.
if (A==null||A.length==0) return;
int ind0 = 0;
int ind1 = 0;
for (int i=0; i<A.length; i++) {
if (A[i] == 0) {
A[i] = 2;
A[ind1++] = 1;
A[ind0++] = 0;
} else if (A[i] == 1) {
A[i] = 2;
A[ind1++] = 1;
}
}
}
public void sortColors(int[] A) {
// Note: The Solution object is instantiated only once and is reused by each test case.
if (A == null || A.length == 0) return;
int[] helper = new int[3];
for (int i=0; i<A.length; i++) {
helper[A[i]] ++;
}
int index = 0;
for (int j=0; j<3; j++) {
while (helper[j]-- > 0) {
A[index++] = j;
}
}
}
OK. Let's make it better.
ONE Pass.
index0 and index1 are two pointer for the current location of 0 and 1.
public void sortColors(int[] A) {
// Note: The Solution object is instantiated only once and is reused by each test case.
if (A==null||A.length==0) return;
int ind0 = 0;
int ind1 = 0;
for (int i=0; i<A.length; i++) {
if (A[i] == 0) {
A[i] = 2;
A[ind1++] = 1;
A[ind0++] = 0;
} else if (A[i] == 1) {
A[i] = 2;
A[ind1++] = 1;
}
}
}
Wednesday, December 10, 2014
Find Minimum in Rotated Sorted Array II LeetCode
Always separate the array for three conditions.
Put equal condition individually.
public int findMin(int[] num) {
int l = 0;
int r = num.length - 1;
int min = num[0];
while (l < r) {
int m = (l+r)/2;
if (num[l] < num[m]) {
min = Math.min(num[l], min);
l = m + 1;
} else if (num[l] > num[m]) {
min = Math.min(num[m], min);
r = m - 1;
} else {
min = Math.min(num[m], min);
l++;
}
}
min = Math.min(num[r], min);
min = Math.min(num[l], min);
return min;
}
Put equal condition individually.
public int findMin(int[] num) {
int l = 0;
int r = num.length - 1;
int min = num[0];
while (l < r) {
int m = (l+r)/2;
if (num[l] < num[m]) {
min = Math.min(num[l], min);
l = m + 1;
} else if (num[l] > num[m]) {
min = Math.min(num[m], min);
r = m - 1;
} else {
min = Math.min(num[m], min);
l++;
}
}
min = Math.min(num[r], min);
min = Math.min(num[l], min);
return min;
}
Search in Rotated Sorted Array LeetCode II
Only One situation need to be done.
When A[L] == A[mid].
public boolean search(int[] A, int target) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int L = 0;
int R = A.length-1;
while (L<=R) {
int mid = (L+R)/2;
if (A[mid] == target) return true;
// Example: 4 5 6 7 8 9 1 2 3
if (A[L] < A[mid]) {
if (A[L]<=target && target < A[mid]) {
R = mid - 1;
} else {
L = mid + 1;
}
}
// Example: 8 9 1 2 3 4 5 6 7
else if (A[L] > A[mid]) {
if (A[mid] < target && target <= A[R]) {
L = mid + 1;
} else {
R = mid - 1;
}
} else {
L++;
}
}
return false;
}
When A[L] == A[mid].
public boolean search(int[] A, int target) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int L = 0;
int R = A.length-1;
while (L<=R) {
int mid = (L+R)/2;
if (A[mid] == target) return true;
// Example: 4 5 6 7 8 9 1 2 3
if (A[L] < A[mid]) {
if (A[L]<=target && target < A[mid]) {
R = mid - 1;
} else {
L = mid + 1;
}
}
// Example: 8 9 1 2 3 4 5 6 7
else if (A[L] > A[mid]) {
if (A[mid] < target && target <= A[R]) {
L = mid + 1;
} else {
R = mid - 1;
}
} else {
L++;
}
}
return false;
}
Find Minimum in Rotate Array LeetCode
Search in Rotated sorted Array
中间值大于起始值,且起始值大于终止值
public int findMin(int[] num) {
int l = 0;
int r = num.length - 1;
int min = num[0];
while (l < r) {
int m = (l+r)/2;
if (num[l] < num[m]) {
min = Math.min(num[l], min);
l = m + 1;
} else if (num[l] > num[m]) {
min = Math.min(num[m], min);
r = m - 1;
} else {
min = Math.min(num[m], min);
l++;
}
}
min = Math.min(num[r], min);
min = Math.min(num[l], min);
return min;
}
Better solution:
public int findMin(int[] num) {
int l = 0;
int r = num.length - 1;
while (l < r) {
int m = (l+r)/2;
//中间值大于起始值,且起始值大于终止值
if (num[m] >= num[l] && num[l] > num[r]) {
l = m + 1;
} else {
r = m;
}
}
return num[l];
}
中间值大于起始值,且起始值大于终止值
public int findMin(int[] num) {
int l = 0;
int r = num.length - 1;
int min = num[0];
while (l < r) {
int m = (l+r)/2;
if (num[l] < num[m]) {
min = Math.min(num[l], min);
l = m + 1;
} else if (num[l] > num[m]) {
min = Math.min(num[m], min);
r = m - 1;
} else {
min = Math.min(num[m], min);
l++;
}
}
min = Math.min(num[r], min);
min = Math.min(num[l], min);
return min;
}
Better solution:
public int findMin(int[] num) {
int l = 0;
int r = num.length - 1;
while (l < r) {
int m = (l+r)/2;
//中间值大于起始值,且起始值大于终止值
if (num[m] >= num[l] && num[l] > num[r]) {
l = m + 1;
} else {
r = m;
}
}
return num[l];
}
Search in Rotated Sorted Array LeetCode
Binary search.
Two different cases:
3 4 5 6 7 8 9 1 2
8 9 1 2 3 4 5 6 7
Here is the solution:
public int search(int[] A, int target) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int L = 0;
int R = A.length-1;
while (L<=R) {
int mid = (L+R)/2;
if (A[mid] == target) return mid;
// Example: 4 5 6 7 8 9 1 2 3
if (A[L] <= A[mid]) {
if (A[L]<=target && target < A[mid]) {
R = mid - 1;
} else {
L = mid + 1;
}
}
// Example: 8 9 1 2 3 4 5 6 7
else {
if (A[mid] < target && target <= A[R]) {
L = mid + 1;
} else {
R = mid - 1;
}
}
}
return -1;
}
Two different cases:
3 4 5 6 7 8 9 1 2
8 9 1 2 3 4 5 6 7
Here is the solution:
public int search(int[] A, int target) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int L = 0;
int R = A.length-1;
while (L<=R) {
int mid = (L+R)/2;
if (A[mid] == target) return mid;
// Example: 4 5 6 7 8 9 1 2 3
if (A[L] <= A[mid]) {
if (A[L]<=target && target < A[mid]) {
R = mid - 1;
} else {
L = mid + 1;
}
}
// Example: 8 9 1 2 3 4 5 6 7
else {
if (A[mid] < target && target <= A[R]) {
L = mid + 1;
} else {
R = mid - 1;
}
}
}
return -1;
}
Monday, December 8, 2014
Container with most water LeetCode
Two pointer. Same idea with TwoSum.
public int maxArea(int[] height) {
int start = 0;
int end = height.length - 1;
int maxArea = 0;
while (start < end) {
maxArea = Math.max(maxArea, (end - start) * Math.min(height[start], height[end]));
if (height[start] > height[end]) {
end--;
} else {
start++;
}
}
return maxArea;
}
public int maxArea(int[] height) {
int start = 0;
int end = height.length - 1;
int maxArea = 0;
while (start < end) {
maxArea = Math.max(maxArea, (end - start) * Math.min(height[start], height[end]));
if (height[start] > height[end]) {
end--;
} else {
start++;
}
}
return maxArea;
}
Clone Graph LeetCode
- A queue is used to do breath first traversal.
- a map is used to store the visited nodes. It is the map between original node and copied node.
It would be helpful if you draw a diagram and visualize the problem.
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node == null)
return null;
LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
HashMap<UndirectedGraphNode, UndirectedGraphNode> map =
new HashMap<UndirectedGraphNode,UndirectedGraphNode>();
UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
queue.add(node);
map.put(node, newNode);
while (!queue.isEmpty()) {
UndirectedGraphNode curr = queue.pop();
List<UndirectedGraphNode> currNeighbors = curr.neighbors;
for (UndirectedGraphNode ngn : currNeighbors) {
if (!map.containsKey(ngn)) {
UndirectedGraphNode copy = new UndirectedGraphNode(ngn.label);
map.put(ngn, copy); //updating the mapping
map.get(curr).neighbors.add(copy); //updating the curr neighbors
queue.add(ngn); //updating the queue
} else {
map.get(curr).neighbors.add(map.get(ngn)); //adding the node from clone graph to the curr's neighbor
}
}
}
return newNode;
}
Remove duplicate from sorted list LeetCode
Check whether the duplicate is existing or not.
If so, prev.next = curr.next. If not, prev.next = curr;
public ListNode deleteDuplicates(ListNode head) {
// Note: The Solution object is instantiated only once and is reused by each test case.
if (head == null) return null;
ListNode dummy = new ListNode(-1);
dummy.next =head;
ListNode prev = dummy;
ListNode curr = head;
while (null != curr) {
while (curr.next != null && prev.next.val == curr.next.val) {
curr = curr.next;
}
if (prev.next == curr) {
prev = curr;
} else {
prev.next = curr.next;
}
curr = curr.next;
}
return dummy.next;
}
If so, prev.next = curr.next. If not, prev.next = curr;
public ListNode deleteDuplicates(ListNode head) {
// Note: The Solution object is instantiated only once and is reused by each test case.
if (head == null) return null;
ListNode dummy = new ListNode(-1);
dummy.next =head;
ListNode prev = dummy;
ListNode curr = head;
while (null != curr) {
while (curr.next != null && prev.next.val == curr.next.val) {
curr = curr.next;
}
if (prev.next == curr) {
prev = curr;
} else {
prev.next = curr.next;
}
curr = curr.next;
}
return dummy.next;
}
Gas Station LeetCode
Use two variables to get the index.
diff is checking whether the entire loop has enough gas for the cost.
remain is trying to find the best start location. If it is negative which means we could not start at any previously point. So we count it again from the next point.
public int canCompleteCircuit(int[] gas, int[] cost) {
int index = -1;
int diff = 0;
int remain = 0;
for (int i=0; i<gas.length; i++) {
diff += gas[i] - cost[i];
remain += gas[i] - cost[i];
if (remain < 0) {
index = i;
remain = 0;
}
}
return diff >= 0 ? index + 1: -1;
}
diff is checking whether the entire loop has enough gas for the cost.
remain is trying to find the best start location. If it is negative which means we could not start at any previously point. So we count it again from the next point.
public int canCompleteCircuit(int[] gas, int[] cost) {
int index = -1;
int diff = 0;
int remain = 0;
for (int i=0; i<gas.length; i++) {
diff += gas[i] - cost[i];
remain += gas[i] - cost[i];
if (remain < 0) {
index = i;
remain = 0;
}
}
return diff >= 0 ? index + 1: -1;
}
Partition List LeetCode
Create two listnodes for each list.
public ListNode partition(ListNode head, int x) {
ListNode root = new ListNode(-1);
ListNode pivot = new ListNode(x);
ListNode before = root;
ListNode after = pivot;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
if (curr.val < x) {
before.next = curr;
before = curr;
} else {
after.next = curr;
after = curr;
after.next = null;
}
curr = next;
}
before.next = pivot.next;
return root.next;
}
public ListNode partition(ListNode head, int x) {
ListNode root = new ListNode(-1);
ListNode pivot = new ListNode(x);
ListNode before = root;
ListNode after = pivot;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
if (curr.val < x) {
before.next = curr;
before = curr;
} else {
after.next = curr;
after = curr;
after.next = null;
}
curr = next;
}
before.next = pivot.next;
return root.next;
}
LeetCode Reverse Words in a String
After splitting, there may be some " " string in the string array.
For example "a b", the splitting result is "a", " ", "b".
public String reverseWords(String s) {
if (s==null ||s.length()==0) return "";
//split to words by space
String[] arr = s.trim().split(" ");
StringBuilder sb = new StringBuilder();
for (int i=arr.length-1; i >=0; i--) {
if (!"".equals(arr[i])) {
sb.append(arr[i]).append(" ");
}
}
return sb.length() == 0 ? "" : sb.substring(0, sb.length() - 1);
}
Also there is a alternative solution for two passes and O(1) space.
The condition is there no spaces at the beginning and the tail. Every word is separated by single space.
Algorithm.
Reverse entire sentence.
Reverse every word.
For example "a b", the splitting result is "a", " ", "b".
public String reverseWords(String s) {
if (s==null ||s.length()==0) return "";
//split to words by space
String[] arr = s.trim().split(" ");
StringBuilder sb = new StringBuilder();
for (int i=arr.length-1; i >=0; i--) {
if (!"".equals(arr[i])) {
sb.append(arr[i]).append(" ");
}
}
return sb.length() == 0 ? "" : sb.substring(0, sb.length() - 1);
}
Also there is a alternative solution for two passes and O(1) space.
The condition is there no spaces at the beginning and the tail. Every word is separated by single space.
Algorithm.
Reverse entire sentence.
Reverse every word.
LeetCode Gray Code
第n位的格雷码由两部分构成,一部分是n-1位格雷码,再加上 1<<(n-1)和n-1位格雷码的逆序的和
public List<Integer> grayCode(int n) {
if (n==0) {
List<Integer> result = new ArrayList<Integer>();
result.add(0);
return result;
}
List<Integer> prevList = grayCode(n-1);
int highestBit = 1 << (n-1);
List<Integer> result = new ArrayList<Integer>(prevList);
for (int i=prevList.size() - 1; i>=0; i--) {
result.add(highestBit + prevList.get(i));
}
return result;
}
public List<Integer> grayCode(int n) {
if (n==0) {
List<Integer> result = new ArrayList<Integer>();
result.add(0);
return result;
}
List<Integer> prevList = grayCode(n-1);
int highestBit = 1 << (n-1);
List<Integer> result = new ArrayList<Integer>(prevList);
for (int i=prevList.size() - 1; i>=0; i--) {
result.add(highestBit + prevList.get(i));
}
return result;
}
Friday, December 5, 2014
LeetCode SubSetsII
Add one variable to add duplicate number in the lists.
public List<List<Integer>> subsetsWithDup(int[] num) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
result.add(new ArrayList<Integer>());
Arrays.sort(num);
int startIndex = 0;
for (int i=0; i<num.length; i++) {
int size = result.size();
for (int j = startIndex; j < size; j++) {
List<Integer> sub = new ArrayList<Integer>();
sub.addAll(result.get(j));
sub.add(num[i]);
result.add(sub);
}
if (i<num.length-1 && num[i+1] == num[i]) {
startIndex = size;
} else {
startIndex = 0;
}
}
return result;
}
Subscribe to:
Posts (Atom)