Tuesday, September 30, 2014
Sunday, September 14, 2014
Leetcode (Python): Populating Next Right Pointers in Each Node II
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
- You may only use constant extra space.
For example,
Given the following binary tree,
Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
Solution:
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None
class Solution:
# @param root, a tree node
# @return nothing
def connect(self, root):
firstNodeLevel = root
while firstNodeLevel != None:
firstNodeNextLevel = None
tempNextLevel = None
pointer = firstNodeLevel
while pointer != None:
if pointer.left != None:
if firstNodeNextLevel == None:
firstNodeNextLevel = pointer.left
else:
tempNextLevel.next = pointer.left
tempNextLevel = pointer.left
if pointer.right != None:
if firstNodeNextLevel == None:
firstNodeNextLevel = pointer.right
else:
tempNextLevel.next = pointer.right
tempNextLevel = pointer.right
pointer = pointer.next
firstNodeLevel = firstNodeNextLevel
Leetcode (Python): Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome."race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
Solution:
class Solution:
# @param s, a string
# @return a boolean
def isPalindrome(self, s):
start = 0;
end = len(s)-1
while start<end:
while start<end and not s[start].isalnum():
start +=1
while start<end and not s[end].isalnum():
end -=1
if start<end and s[start].lower() != s[end].lower():
return False
start +=1
end -= 1
return True
Leetcode: Valid Palindrome
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome."race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
Solution:
public class Solution {
public boolean isPalindrome(String s) {
int start = 0;
int end = s.length()-1;
while(start<end)
{
while(start<end && ! Character.isLetterOrDigit(s.charAt(start)))
start++;
while(start<end && ! Character.isLetterOrDigit(s.charAt(end)))
end--;
if (start<end && Character.toLowerCase(s.charAt(start))!= Character.toLowerCase(s.charAt(end)))
return false;
start++;
end--;
}
return true;
}
}
Leetcode (Python): Sum Root to Leaf Numbers
Given a binary tree containing digits from
0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path
1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2 3
The root-to-leaf path
The root-to-leaf path
1->2 represents the number 12.The root-to-leaf path
1->3 represents the number 13.
Return the sum = 12 + 13 =
25.Solution:
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return an integer
def sumNumbers(self, root):
self.sum = 0;
self.sumNumbersRec(root,0)
return self.sum
def sumNumbersRec(self, root, partialSum):
if root == None:
return
partialSum = partialSum *10 + root.val;
if root.left == None and root.right == None:
self.sum += partialSum
else:
self.sumNumbersRec(root.left, partialSum)
self.sumNumbersRec(root.right, partialSum)
Leetcode: Sum Root to Leaf Numbers
Given a binary tree containing digits from
0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path
1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2 3
The root-to-leaf path
The root-to-leaf path
1->2 represents the number 12.The root-to-leaf path
1->3 represents the number 13.
Return the sum = 12 + 13 =
25.Solution:
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
int sum;
public int sumNumbers(TreeNode root) {
sum = 0;
sumNumbers(root, 0);
return sum;
}
public void sumNumbers(TreeNode root, int partialSum)
{
if(root == null)
return;
partialSum = partialSum*10 + root.val;
if (root.left==null && root.right == null)
sum += partialSum;
else
{
sumNumbers(root.left, partialSum);
sumNumbers(root.right, partialSum);
}
}
}
Saturday, September 13, 2014
Leetcode (Python): Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree
Given binary tree
1
\
2
/
3
return
[1,2,3].Solution:
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return a list of integers
def preorderTraversal(self, root):
solution = []
stack = []
node = root
while node != None or len(stack)>0:
if node != None:
solution.append(node.val)
stack.append(node)
node = node.left
else:
node = stack.pop().right
return solution
Leetcode (Python): Insertion Sort List
Sort a linked list using insertion sort.
Solution:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param head, a ListNode
# @return a ListNode
def insertionSortList(self, head):
if not head:
return head
dummy = ListNode(0)
dummy.next = head
lastSorted = head
while lastSorted.next:
if lastSorted.next.val < lastSorted.val:
tmp = dummy
while tmp.next.val < lastSorted.next.val:
tmp = tmp.next
nextToSort = lastSorted.next
lastSorted.next = nextToSort.next
nextToSort.next = tmp.next
tmp.next = nextToSort
else:
lastSorted = lastSorted.next
return dummy.next
Thursday, September 11, 2014
Leetcode (Python): Evaluate Reverse Polish Notation
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are
+, -, *, /. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
Solution:
class Solution:
# @param tokens, a list of string
# @return an integer
def evalRPN(self, tokens):
if tokens == None:
return 0
stack = []
for token in tokens:
if token =="+" or token =="-" or token =="*" or token =="/":
operand2 = stack.pop()
operand1 = stack.pop()
if token == "+":
stack.append(operand1+operand2)
elif token == "-":
stack.append(operand1-operand2)
elif token == "*":
stack.append(operand1*operand2)
else:
stack.append(int(float(operand1)/operand2))
else:
stack.append(int(token))
return stack.pop()
Sunday, June 15, 2014
Leetcode (Python): Implement strStr()
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
Solution:
We first preprocess the needle, in such a way that we obtain the equivalent states, for instance:a a b a a b c 0 0 1 0 1 2 3That means that if we are have found aabaab, we have also found aab. When we process the haystack, when we arrive to a state that we cannot go on, we change to its previous equivalent state.
class Solution:
# @param haystack, a string
# @param needle, a string
# @return a string or None
def strStr(self, haystack, needle):
if len(needle)==0:
return haystack
equivalentState=[0]
previousState = 0;
for i in range(1,len(needle)):
equivalentState.append(previousState)
if needle[previousState] == needle [i]:
previousState += 1
else:
previousState = 0
position = 0
state = 0
while position < len(haystack):
if haystack[position] == needle[state]:
position += 1
state += 1
if state == len(needle):
return haystack[position-state:]
else:
if state == 0:
position +=1
else:
state = equivalentState[state]
return None
LeetCode (Python): Remove Duplicates from Sorted Array
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A =
Given input array A =
[1,1,2],
Your function should return length =
2, and A is now [1,2].Solution:
class Solution:
# @param a list of integers
# @return an integer
def removeDuplicates(self, A):
if len(A)==0:
return 0
end = 0;
for i in range(1,len(A)):
if A[i] != A[end]:
end += 1
self.swap(A,i,end)
return end + 1
def swap(self, A, pos1, pos2):
temp = A[pos1]
A[pos1] = A[pos2]
A[pos2] = temp
LeetCode (Python): Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree
Note: Recursive solution is trivial, could you do it iteratively?
For example:
Given binary tree
{1,#,2,3},
1
\
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
Solution
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return a list of integers
def inorderTraversal(self, root):
stack = []
node = root
solution = []
while node!= None or len(stack)>0:
if node != None:
stack.append(node)
node = node.left
else:
node = stack.pop()
solution.append(node.val)
node = node.right
return solution
Other solution:
This solution needs more space but is easier to understand.# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return a list of integers
def inorderTraversal(self, root):
stack = []
if root != None:
stack.append(root)
solution = []
used = set()
while len(stack)>0:
node = stack.pop()
if node in used:
solution.append(node.val)
else:
used.add(node)
if node.right != None:
stack.append(node.right)
stack.append(node)
if node.left != None:
stack.append(node.left)
return solution
LeetCode (Python): Best Time to Buy and Sell Stock III
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). Solution
We can calculate the solution to the problem for 1 transaction, so we use dynamic programming calculating the solution to which is the maximum benefit prior and posterior to certain day, afterwards we just have to iterate through the sum of both arrays finding the maximum.class Solution:
# @param prices, a list of integer
# @return an integer
def maxProfit(self, prices):
previousMin = float("infinity")
nextMax = float("-infinity")
maxProfitSellBefore = [0]
maxProfitBuyAfter = [0]
for i in range(0,len(prices)):
previousMin = min(previousMin, prices[i])
if i>0:
maxProfitSellBefore.append(max(maxProfitSellBefore[i-1], prices[i]-previousMin))
for i in range(len(prices)-1,-1,-1):
nextMax = max(nextMax, prices[i])
if i<len(prices)-1:
maxProfitBuyAfter.insert(0,max(maxProfitBuyAfter[0], nextMax-prices[i]))
maxBenefit = 0
for i in range(0,len(prices)):
maxBenefit = max(maxBenefit, maxProfitSellBefore[i] + maxProfitBuyAfter[i])
return maxBenefit
LeetCode (Python): Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Divide and Conquer solution
We merge lists by pairs till we have only one list. The complexity is $O(n log(k))$.# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param a list of ListNode
# @return a ListNode
def mergeKLists(self, lists):
if len(lists)==0:
return None
while len(lists)>1:
nextLists = []
for i in range(0,len(lists)-1,2):
nextLists.append(self.mergeLists(lists[i],lists[i+1]))
if len(lists)%2==1:
nextLists.append(lists[len(lists)-1])
lists = nextLists
return lists[0]
def mergeLists(self, list1, list2):
dummy = ListNode(0)
list = dummy
while list1 != None and list2 != None:
if list1.val < list2.val:
list.next = list1
list1 = list1.next
else:
list.next = list2
list2 = list2.next
list = list.next
if list1 == None:
list.next = list2
else:
list.next = list1
return dummy.next
Saturday, June 14, 2014
LeetCode: Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree
Note: Recursive solution is trivial, could you do it iteratively?
For example:
Given binary tree
{1,#,2,3},
1
\
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
Solution
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
ArrayDeque<TreeNode> stack = new ArrayDeque<TreeNode>();
List<Integer> solution = new ArrayList<Integer>();
TreeNode node = root;
while(!stack.isEmpty() || node !=null)
{
if (node != null)
{
stack.push(node);
node = node.left;
}
else
{
node = stack.pop();
solution.add(node.val);
node = node.right;
}
}
return solution;
}
}
Other solution:
This solution needs more space but is easier to understand./**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
ArrayDeque<TreeNode> stack = new ArrayDeque<TreeNode>();
List<Integer> solution = new ArrayList<Integer>();
HashSet<TreeNode> used = new HashSet<TreeNode>();
if(root!=null)
stack.push(root);
while(!stack.isEmpty())
{
TreeNode temp = stack.pop();
if(used.contains(temp))
{
solution.add(temp.val);
continue;
}
used.add(temp);
if (temp.right != null)
stack.push(temp.right);
stack.push(temp);
if (temp.left != null)
stack.push(temp.left);
}
return solution;
}
}
LeetCode (Python): Binary Tree Level Order Traversal II
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree
Given binary tree
{3,9,20,#,#,15,7}, 3
/ \
9 20
/ \
15 7
return its bottom-up level order traversal as:
[
[15,7]
[9,20],
[3],
]
Solution:
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param root, a tree node
# @return a list of lists of integers
def levelOrderBottom(self, root):
solution = []
thisLevel = []
if root != None:
thisLevel.append(root)
while len(thisLevel)>0:
levelNumbers = []
nextLevel = []
for node in thisLevel:
levelNumbers.append(node.val)
if node.left != None:
nextLevel.append(node.left)
if node.right != None:
nextLevel.append(node.right)
solution.insert(0,levelNumbers)
thisLevel = nextLevel
return solution
LeetCode (Python): Sudoku Solver
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character
You may assume that there will be only one unique solution.
Empty cells are indicated by the character
'.'.You may assume that there will be only one unique solution.
A sudoku puzzle...
...and its solution numbers marked in red.
Solution
class Solution:
# @param board, a 9x9 2D array
# Solve the Sudoku by modifying the input board in-place.
# Do not return any value.
def solveSudoku(self, board):
self.solveSudokuRec(board,0,0)
def solveSudokuRec(self, board,row,col):
if row == 9:
return True
if col == 8:
nextRow = row +1
nextCol = 0
else:
nextRow = row
nextCol = col+1
if board[row][col]!='.':
return self.solveSudokuRec(board,nextRow,nextCol)
for c in range(1,10):
if self.canPut(board,str(c),row,col):
board[row][col] = str(c)
if self.solveSudokuRec(board,nextRow,nextCol):
return True
board[row][col] = '.'
return False
def canPut(self, board, char, row, col):
for i in range(0,9):
if board[row][i] == char:
return False
if board[i][col] == char:
return False
rowGroup = (row//3) * 3
colGroup = (col//3) * 3
for i in range(rowGroup, rowGroup+3):
for j in range(colGroup, colGroup+3):
if board[i][j] == char:
return False
return True
LeetCode: Sudoku Solver
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character
You may assume that there will be only one unique solution.
Empty cells are indicated by the character
'.'.You may assume that there will be only one unique solution.
A sudoku puzzle...
...and its solution numbers marked in red.
Solution
public class Solution {
public void solveSudoku(char[][] board) {
solveSudoku(board, 0, 0);
}
public boolean solveSudoku(char[][] board, int row, int col)
{
if (row == 9)
return true;
int nextRow = col == 8 ? row+1 : row;
int nextCol = col == 8 ? 0 : col+1;
if (board[row][col] !='.')
return solveSudoku(board, nextRow, nextCol);
for (char c='1'; c<='9'; c++)
{
if (canPut(board, c, row, col))
{
board[row][col] = c;
if (solveSudoku(board, nextRow, nextCol))
return true;
board[row][col] = '.';
}
}
return false;
}
public boolean canPut(char[][] board, char c, int row, int col)
{
for(int i=0; i<9; i++)
{
if(board[row][i]==c)
return false;
if(board[i][col]==c)
return false;
}
int startRowGroup = (row/3)*3;
int startColGroup = (col/3)*3;
for(int i=startRowGroup; i<startRowGroup+3; i++)
{
for(int j=startColGroup; j<startColGroup+3; j++)
if(board[i][j]==c)
return false;
}
return true;
}
}
Subscribe to:
Posts
(
Atom
)