Pascal's Triangle II Java+Python

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

	class Solution:
	# @return a list of integers
	def getRow(self, rowIndex):
	if rowIndex<0:
	return None
	result=[0]*(rowIndex+1)
	result[0]=1
	for i in range(1,len(result)):
	result[i]=1
	for j in range(i-1, 0, -1):
	result[j]=result[j]+result[j-1]
	return result

view raw Pascal's TriangleII.py hosted with ❤ by GitHub

	/*
	Given an index k, return the kth row of the Pascal's triangle.
	For example, given k = 3,
	Return [1,3,3,1].
	Note:
	Could you optimize your algorithm to use only O(k) extra space?
	*/
	//6/2014
	public class Solution {
	public List<Integer> getRow(int rowIndex) {
	if (rowIndex<0){
	return null;
	}
	LinkedList<Integer> current=new LinkedList<Integer>();
	LinkedList<Integer> next=new LinkedList<Integer>();
	current.add(1);
	int start=0;
	while (start<rowIndex){
	current.addFirst(0);
	current.add(0);
	calculateNext(current, next);
	LinkedList<Integer> temp=next;
	next=current;
	current=temp;
	start++;
	}
	return current;
	}
	private void calculateNext(LinkedList<Integer> current, LinkedList<Integer> next){
	if (current==null){
	return;
	}
	while (current.size()>1){
	int num1=current.pop();
	int num2=current.peek();
	next.add(num1+num2);
	}
	current.clear();
	}
	}
	// 3/2014
	public class Solution {
	/*
	[
	[1],
	[1,1],
	[1,2,1],
	[1,3,3,1],
	[1,4,6,4,1]
	]
	*/
	/*
	[1,0,0,0]
	[1,1,0,0]
	[1,2,1,0]
	[1,3,3,1]
	pN=pCValue+pCLeftValue;
	*/
	public ArrayList<Integer> getRow(int rowIndex) {
	if (rowIndex<0){
	return null;
	}
	ArrayList<Integer> current=new ArrayList<Integer>();
	ArrayList<Integer> next=new ArrayList<Integer>();
	current.add(1);
	int level=0;
	while (level<rowIndex){
	level++;
	next.add(1);
	for (int i=1; i<current.size(); i++){
	next.add(current.get(i)+current.get(i-1));
	}
	next.add(1);
	current=next;
	next=new ArrayList<Integer>();
	}
	return current;
	}
	}
	// 1/2014
	public class Solution {
	public ArrayList<Integer> getRow(int rowIndex) {
	if (rowIndex<0){
	return null;
	}
	ArrayList<Integer> result=new ArrayList<Integer>(rowIndex+1);
	for (int i=0; i<=rowIndex; i++){
	result.add(0);
	}
	result.set(0, 1);
	for (int i=1; i<=rowIndex; i++){
	result.set(i, 1);
	for (int j=i-1; j>0; j--){
	result.set(j, result.get(j)+result.get(j-1));
	}
	}
	return result;
	}
	}

view raw Pascal'sTriangleII.java hosted with ❤ by GitHub

Path Sum (Java and Python)

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

	Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
	For example:
	Given the below binary tree and sum = 22,
	5
	/ \
	4 8
	/ / \
	11 13 4
	/ \ \
	7 2 1
	return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
	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
	# @param sum, an integer
	# @return a boolean
	def hasPathSum(self, root, sum):
	if root==None:
	return False
	if root.val==sum and root.left==None and root.right==None:
	return True
	return self.hasPathSum(root.left, sum-root.val)or self.hasPathSum(root.right, sum-root.val)

view raw PathSum.py hosted with ❤ by GitHub

	Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
	For example:
	Given the below binary tree and sum = 22,
	5
	/ \
	4 8
	/ / \
	11 13 4
	/ \ \
	7 2 1
	return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public boolean hasPathSum(TreeNode root, int sum) {
	if (root==null){
	return false;
	}
	if (root.val==sum && root.left==null && root.right==null){
	return true;
	}
	return hasPathSum(root.left, sum-root.val)||hasPathSum(root.right, sum-root.val);
	}
	}

view raw PathSum.java hosted with ❤ by GitHub