Best Time to Buy and Sell Stock II

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.

Solution: The difference of this problem with previous one is that you can buy and sell stocks several times, instead of buying and selling for just once. Then how to find the purchasing and selling points? When you buy the stock, the time should be the day when the price is the lowest after the last selling transaction. When you sell the stock, the time should be the day when the price is the highest after the most recent purchasing time. Therefore, the idea is to find the last element of the non-decreasing sequence and choose it as the purchasing time (min), set the last element of non-increasing sequence after min as max, which is the selling time. Add the difference of max and min to sum, and set min to the value of max, and update it in the next iteration. Pay attention to the condition in the while loop, prevent i to be larger than or equal to the length of the array -1, otherwise you will get array out of bound exception and cause the run-time error.

01 public int maxProfit(int[] prices) {
02     if(prices.length<=1)
03     {
04         return 0;
05     }
06   
07     int min=prices[0];
08     int max=prices[0];
09     int i=0;
10     int sum=0;
11   
12     while(i<prices.length-1)
13     {
14         while(i<prices.length-1 && prices[i+1]<=prices[i])
15         {
16             i++;
17           
18         }
19         min=prices[i];
20         max=prices[i];
21         while(i<prices.length-1 && prices[i+1]>=prices[i])
22         {
23             i++;
24         }
25         max=prices[i];
26         sum+=max-min;
27         min=prices[i];
28     }
29   
30     return sum;
31 }

Best Time to Buy and Sell Stock

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.

Solution: keep track of the current min value at each day.  Subtract the price at each day with the current min value as the max. Update the value of max if the difference is larger than max.

01 public int maxProfit(int[] prices) {
02     if(prices.length<=1)
03     {
04         return 0;
05     }
06     int min=prices[0];
07     int max=0;
08     for(int i=1;i<prices.length;i++)
09     {
10         if(prices[i]<min)
11         {
12             min=prices[i];  
13         }
14       
15         int diff=prices[i]-min;
16         if(diff>max)
17         {
18             max=diff;
19         }
20     }
21     return max;
22 }

Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

01 public ListNode swapPairs(ListNode head) {
02     if(head==null || head.next==null)
03         return head;
04     ListNode first=head;
05     ListNode second=head.next;              
06     first.next=second.next;
07     second.next=first;
08     head=second;
09     ListNode prev=first;
10     first=first.next;
11   
12     while(first!=null && first.next!=null)
13     {
14         second=first.next;
15         first.next=second.next;
16         second.next=first;
17         prev.next=second;
18                   
19         prev=first;
20         first=first.next;
21     }
22     return head;
23 }

Sort Colors

 Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?

01 public void sortColors(int[] A) {
02     int []size=new int[3];
03     for(int i=0;i<A.length;i++)
04     {
05         size[A[i]]++;
06     }
07     int j=0;
08     while(j<size[0])
09     {
10         A[j]=0;
11         j++;
12     }
13     while(j<size[0]+size[1])
14     {
15         A[j]=1;
16         j++;
17     }
18     while(j<A.length)
19     {
20         A[j]=2;
21         j++;
22     }
23 }

Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Note: the idea is to build two separate linked list, left and right. The left list stores the nodes which values are less than the given value, and the right list stores the nodes which values are greater than or equal to the given value. Insert the nodes to the corresponding lists one by one, then your program becomes easy to read!

01 public ListNode partition(ListNode head, int x) {
02     ListNode left=null;
03     ListNode leftEnd=null;
04     ListNode right=null;
05     ListNode rightEnd=null;
06     ListNode curr=head;
07     while(curr!=null)
08     {
09         ListNode next=curr.next;
10         curr.next=null;
11         if(curr.val<x)
12         {
13             if(left==null)
14             {
15                 left=curr;
16                 leftEnd=left;
17             }
18             else
19             {
20                 leftEnd.next=curr;
21                 leftEnd=leftEnd.next;
22             }
23         }
24         else
25         {
26             if(right==null)
27             {
28                 right=curr;
29                 rightEnd=right;
30             }
31             else
32             {
33                 rightEnd.next=curr;
34                 rightEnd=rightEnd.next;
35             }
36         }
37         curr=next;
38     }
39     if(left!=null)
40     {
41         leftEnd.next=right;
42         return left;
43     }
44     else
45     {
46         return right;
47     }
48 }

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 = [1,1,2],

Your function should return length = 2, and A is now [1,2].

01 public int removeDuplicates(int[] A) {
02     if(A.length<=1)
03         return A.length;
04     //current value    
05     int curr=A[0];
06   
07     //current index;
08     int i=1;
09   
10     //index without duplicates
11     int index=1;
12     int length=A.length;
13     while(i<A.length)
14     {
15         while(i<A.length && A[i]==curr)
16         {
17             i++;
18             length--;
19         }
20       
21         //replace duplicates
22         if(i<A.length)
23         {
24             A[index]=A[i];
25             curr=A[i];
26             i++;
27             index++;
28         }
29     }
30     return length;
31 }

Permutation

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Hint: Select a number from beginning to the end, then permute the remaining numbers recursively. Tips: use a boolean array used[ ] to track which numbers have been selected in the current permutation sequence.

01 public ArrayList<ArrayList<Integer>> permute(int[] num) {
02     boolean []used=new boolean[num.length];
03     ArrayList<Integer>temp=new ArrayList<Integer>();
04     ArrayList<ArrayList<Integer>>result=new ArrayList<ArrayList<Integer>>();
05     doPermute(num,result,temp,used,0);
06     return result;
07   
08 }
09 public void doPermute(int []num, ArrayList<ArrayList<Integer>>result,ArrayList<Integer>temp,boolean[]used, int level)
10 {
11     if(level==num.length)
12     {
13         ArrayList<Integer> out=new ArrayList<Integer>();
14         for(int i=0;i<temp.size();i++)
15         {
16             out.add(temp.get(i));
17         }
18         result.add(out);
19         return;
20     }
21   
22     for(int i=0;i<num.length;i++)
23     {
24         if(!used[i])
25         {
26             temp.add(num[i]);
27             used[i]=true;
28             doPermute(num,result,temp,used,level+1);
29             used[i]=false;
30             int size=temp.size();
31             if(size>0)
32             {
33                 temp.remove(size-1);
34             }
35         }
36     }
37 
38 }

Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

To solve it recursively is easy.

01 public boolean isSymmetric(TreeNode root) {

02     if(root==null)

03         return true;      

04     return isMirror(root.left,root.right);

05 }

06 

07 public boolean isMirror(TreeNode t1, TreeNode t2)

08 {

09     if(t1==null)

10     {

11         if(t2==null)

12             return true;

13         else

14             return false;

15     }

16     if(t2==null && t1!=null)

17         return false;

18     if(t1.val==t2.val)

19     {

20         return isMirror(t1.left,t2.right) && isMirror(t1.right,t2.left);

21     }

22     else

23         return false;

24 }

To solve it without recursion, we should use BFS, with the help of a queue structure. As there is no depth field of each node, we should use an additional queue to keep track of the levels of nodes.

01 public boolean isSymmetric(TreeNode root) {
02     if(root==null)
03         return true;
04   
05     ArrayList<TreeNode> trees=new ArrayList<TreeNode>();
06     ArrayList<Integer> depth=new ArrayList<Integer>();
07     trees.add(root);
08     depth.add(1);
09     while(!trees.isEmpty())
10     {
11         TreeNode parent=trees.remove(0);
12         int curr_depth=depth.remove(0);
13         if(parent!=null)
14         {
15             trees.add(parent.left);
16             depth.add(curr_depth+1);          
17             trees.add(parent.right);
18             depth.add(curr_depth+1);
19         }
20       
21       
22         int size=depth.size();
23       
24         if( !depth.isEmpty() && curr_depth==depth.get(0)-1 && depth.get(0)==depth.get(size-1) )
25         {
26             int i=0;
27             int j=size-1;
28           
29             while(i<j)
30             {
31                 if(trees.get(i)==null)
32                 {
33                     if(trees.get(j)==null)
34                     {
35                         i++;
36                         j--;
37                     }
38                     else
39                         return false;
40                 }
41                 else if(trees.get(i)!=null && trees.get(j)==null)
42                 {
43                     return false;
44                 }                  
45                 else if(trees.get(i).val==trees.get(j).val)
46                 {
47                     i++;
48                     j--;
49                 }
50                 else
51                 {
52                     return false;
53                 }
54               
55             }
56 
57         }
58       
59     }
60   
61     return true;
62 }

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

01 public int maxSubArray(int[] A) {
02     int sum=0;
03     int maxSum=A[0];
04     for(int i=0;i<A.length;i++)      
05     {
06         sum+=A[i];
07         if(sum>maxSum)
08         {
09             maxSum=sum;
10         }
11         if(sum<0)
12         {
13             sum=0;
14         }
15     }
16     return maxSum;
17 }