LeetCode-Best Time to Buy and Sell Stock II

发表于 2014-07-04

Problem:
Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

public class Solution {
    public int maxProfit(int[] prices) {
        int ret=0,
            leftValue=0,
            length=prices.length,
            state=-1;//-1=buy,1=sale
        
        for(int i=0;i<length;i++)
        {
            if(state==-1)
            {
                if(i+1<length && prices[i]<prices[i+1])
                {
                    leftValue=prices[i];
                    state=1;
                }
            }else{
                if((i==length-1 && prices[i]>leftValue) || prices[i]>prices[i+1])
                {
                    ret+=prices[i]-leftValue;
                    state=-1;
                }
            }
        }
        
        return ret;
    }
}

LeetCode-Best Time to Buy and Sell Stock

By Kubi Code

发表于 2014-07-03

Problem:
Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

public class Solution {
    public int maxProfit(int[] prices) {
         int ret=0,
            leftValue=Integer.MAX_VALUE,
            rightPos=0,
            length=prices.length;
        
        for(int i=0;i<length-1;i++)
        {
            if(prices[i]>leftValue)
                continue;
            
            for(int j=i+1;j<length;j++)
            {
                if(prices[j]-prices[i]>ret)
                {
                    ret=prices[j]-prices[i];
                    leftValue=prices[i];
                }
            }
        }
        
        
        return ret;
    }
}

thr runtime is 1548ms -_-!

public class Solution {
    public int maxProfit(int[] prices) {
        int ret=0,
            buy=0,
            length=prices.length;
        
        if(prices.length<2)
            return ret;
        
        buy=prices[0];
        for(int i=1;i<length;i++)
        {
            if(prices[i]-buy>ret)
            {
                ret=prices[i]-buy;
            }
            
            if(prices[i]<buy)
            {
                buy=prices[i];
            }
        }
        
        
        return ret;
    }
}

thr runtime is 376ms

LeetCode-Pascal's Triangle

By Kubi Code

发表于 2014-07-02

Problem:
Given numRows, generate the first numRows of Pascal’s triangle.

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list=new ArrayList<List<Integer>>();
        
        if(numRows==0)
            return list;
        
        list.add(Arrays.asList(1));
        
        for(int i=1;i<numRows;i++)
        {
            List<Integer> rows=new ArrayList<Integer>();
            rows.add(1);
            for(int j=1;j<i;j++)
            {
                rows.add(list.get(i-1).get(j-1)+list.get(i-1).get(j));
            
            }
            rows.add(1);
            list.add(rows);
        }
        
        return list;
    }
}

LeetCode-Pascal's Triangle II

By Kubi Code

发表于 2014-07-01

Problem:
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?

public class Solution {
    public List<Integer> getRow(int rowIndex) {
        Integer[] ret=new Integer[rowIndex+1];
        
        for(int i=0;i<ret.length;i++)
        {
            ret[i]=0;
        }
        ret[0]=1;
        for(int i=1;i<rowIndex+1;i++)
        {
            for(int j=i;j>0;j--)
            {
                ret[j]+=ret[j-1];
            }
        }
        
        return Arrays.asList(ret);
    }
}

LeetCode-Triangle

By Kubi Code

发表于 2014-07-01

Problem:
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
		int[][] sums=new int[triangle.size()][triangle.size()];
		List<Integer> rows;
        int ret=0,column;
        
        
        if(triangle.size()>0)
	    {
        	for(int i=triangle.size()-1;i>=0;i--)
        	{
        		rows=triangle.get(i);
        		
        		if(i==triangle.size()-1)
        		{
        			//the last rows
        			for(int j=0;j<rows.size();j++)
        			{
        				sums[i][j]=rows.get(j);
        			}
        		}else{
        			
        			for(int j=0;j<rows.size();j++)
        			{
        				
        				sums[i][j]=this.getMin(rows.get(j)+sums[i+1][j],rows.get(j)+sums[i+1][j+1]);
        			}
        		}
        		
        	}
        	
        	ret=sums[0][0];
	    }
        
        return ret;
        
    }
	
	public Integer getMin(Integer a,Integer b)
	{
		return a>b?b:a;
	}
}

LeetCode-LRU Cache

By Kubi Code

发表于 2014-06-30

Problem:
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

public class LRUCache {
    
    private HashMap<Integer,Integer> _cache;
	
	private int _capacity;
	
	private Node _head=null;
	
	private Node _end=null;
	
	public LRUCache(int capacity) {
		
		this._head=new Node();
		this._end=new Node();
		
		this._head.next=this._end;
		this._end.next=null;
		
		this._capacity=capacity;
		this._cache=new HashMap<Integer,Integer>(capacity);
    }
    
    public int get(int key) {
    	int ret=-1;
    	
        if(this._cache.containsKey(key))
        {
        	ret=this._cache.get(key);
        	this.moveToFirst(key);
        }
        	
        	
        return ret;
    }
    
    public void set(int key, int value) {
        if(!this._cache.containsKey(key))
        {
        	if(_cache.size()>=this._capacity)
        	{
        		this._cache.remove(this.popKey());
        	}
        	
        	this.insertToFirst(key);
         }else{
        	this.moveToFirst(key);
         }
        
        this._cache.put(key, value);
    }
    
    private void moveToFirst(Integer key)
    {
    	Node node=this._head;
    	Node node2=null;
    	
    	while(node.next!=null)
    	{
    		
    		if(key.equals(node.key))
    		{
    			break;
    		}
    		node2=node;
    		node=node.next;
    	}
    	
    	node2.next=node.next;
    	node.next=this._head.next;
    	this._head.next=node;
    }
    
    private void insertToFirst(Integer key)
    {
    	Node node=new Node(key);
    	node.next=this._head.next;
    	this._head.next=node;
    	
    }
    
    
    private Integer popKey()
    {
    	int key=-1;
    	Node node=this._head;
    	Node node2=null;
    	
    	while(node.next!=this._end)
    	{
    		node2=node;
    		node=node.next;
    	}
    	
    	key=node.key;
    	node2.next=this._end;
    	
    	return key;
    }
    
    
    
    
    class Node{
    	public Integer key;
    	    	
    	public Node next;
    	
    	public Node()
    	{
    		
    	}
    	
    	public Node(Integer key)
    	{
    		this.key=key;
    	}
    	
    	public Node clone(){
    		Node node=new Node();
    		node.key=this.key;
    		node.next=this.next;
    		
    		return node;
    	}
    }
}

其实在Java中最方便实现LRUCache的方法就是使用LinkedHashMap，天然的集成了该功能，但是LeetCode在这题中并没有引用LinkedHashMap的包，-_-

public class LRUCache extends LinkedHashMap<Integer,Integer> {
    private int maxCacheNum=10;
	
	public LRUCache(int capacity)
	{
		super(capacity,0.75f,true);//这里第三个参数一定要为true，这样就表示该LinkedHashMap是使用了访问速度来链表
		this.maxCacheNum=capacity;
	}
	
	public int get(int key) {
        if(super.containsKey(key))
        {
        	return super.get(key);
        }else{
        	return -1;
        }
    }
    
    public void set(int key, int value) {
        super.put(key, value);
    }
	
	/**
	 * 重写删除最少用元素的方法
	 */
	@Override 
	protected boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest) {
        return this.size()>maxCacheNum;
    }
}

LeetCode-Flatten Binary Tree to Linked List

By Kubi Code

发表于 2014-06-29

Problem:
Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

The flattened tree should look like:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        if(root==null)
			return ;
			
		flatten(root.left);
		
		flatten(root.right);
		
		if(root.left!=null)
		{
			//move the left leaf to the right
			TreeNode tempNode=root.left;
			while(tempNode.right!=null)
			{
				tempNode=tempNode.right;
			}
			
			
			tempNode.right=root.right;
	        root.right=root.left;
	        root.left=null;
		}
    }
}

LeetCode-Path Sum II

By Kubi Code

发表于 2014-06-28

Problem:
Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

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

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

return

[
   [5,4,11,2],
   [5,8,4,5]
]

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
		
		List<List<Integer>> pathList=new ArrayList<List<Integer>>();
		
		if(root!=null)
			pathSearch(pathList,new Stack<Integer>(),root,sum);
		
		return pathList;
    }
	
	public void pathSearch(List<List<Integer>> pathList,Stack<Integer> curPath,TreeNode node,int sum)
	{
		if(node!=null)
		{
			curPath.push(node.val);
			sum-=node.val;
			
			if(node.left==null && node.right==null&&sum==0)
			{
				pathList.add(Collections.list(((Stack<Integer>)curPath.clone()).elements()));
			}
		
			pathSearch(pathList,curPath,node.left,sum);
			pathSearch(pathList,curPath,node.right,sum);
			curPath.pop();

			
		}
	}
}

LeetCode-Path Sum

By Kubi Code

发表于 2014-06-27

Problem:
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;
		 	
		 	sum-=root.val;
		 	
		 	if(root.left ==null && root.right==null)
		 		return sum==0;
		 	else
		 		return hasPathSum(root.left,sum) || hasPathSum(root.right,sum);
	 }
	 
	 
}

LeetCode-Max Points on a Line

By Kubi Code

发表于 2014-06-26

Problem:
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {

		if(points.length<=1)
		{
			return points.length;
		}
		
		int[] pointNum=new int[points.length];//the number in average group
		Point[] pointGroup=new Point[points.length];
		int groupLength=0;
		boolean flagAdd=false;
		for(Point point:points)
		{
			flagAdd=false;
			for(int i=0;i<groupLength;i++)
			{
				if(pointGroup[i].x==point.x && pointGroup[i].y==point.y)
				{
					pointNum[i]++;
					flagAdd=true;
					break;
				}
			}
			
			if(!flagAdd)
			{
				pointGroup[groupLength]=point;
				pointNum[groupLength]=1;
				groupLength++;
			}
		}
		
		int maxNum=pointNum[0],tempNum=0;
		HashMap<Straight,Integer> straightMap=new HashMap<Straight,Integer>();
		
		for(int i=0;i<groupLength;i++)
		{
			for(int j=i+1;j<groupLength;j++)
			{
				tempNum=pointNum[i]+pointNum[j];
				Straight straight=new Straight(pointGroup[i],pointGroup[j]);
				
				if(straightMap.containsKey(straight))
				{
					continue;
				}else{
					straightMap.put(straight, 1);
				}
				
				for(int k=j+1;k<groupLength;k++)
				{
					if(straight.isIn(pointGroup[k]))
					{
						tempNum+=pointNum[k];
					}
				}
				
				if(maxNum<tempNum)
				{
					maxNum=tempNum;
				}
			}
		}
		
		return maxNum;
    }
	
	class Straight{
		
		private double _gradient;
		private double _intercept;
		
		public Straight(Point p1,Point p2)
		{
			if(p1.x==p2.x)
			{
				this._gradient=Double.NaN;
				
				this._intercept=p1.x;
				
				
			}else{
				this._gradient=(p2.y-p1.y)/(double)(p2.x-p1.x);
				this._intercept=p1.y-this._gradient*p1.x;
			}
		}
		
		public Straight(double gradient,double intercept)
		{
			this._gradient=gradient;
			this._intercept=intercept;
		}
		
		/**
		 * judge this point whether in this straight
		 * @param point
		 * @return
		 */
		public boolean isIn(Point point)
		{
			
			if(Double.isNaN(this._gradient))
			{
				return this._intercept==point.x;
			}
			return Math.abs(point.y-(this._gradient*point.x+this._intercept))<=1e-7;
		}
		
	}
}

Kubi Code'Blog

The palest ink is better than the best memory.

LeetCode-Best Time to Buy and Sell Stock II

LeetCode-Best Time to Buy and Sell Stock

LeetCode-Pascal's Triangle

LeetCode-Pascal's Triangle II

LeetCode-Triangle

LeetCode-LRU Cache

LeetCode-Flatten Binary Tree to Linked List

LeetCode-Path Sum II

LeetCode-Path Sum

LeetCode-Max Points on a Line