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()
Subscribe to:
Posts
(
Atom
)