Wednesday, February 25, 2015

Best Time to Buy and Sell Stock


Say you have an array for which the ith 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: 
一次扫描完成。只需要找到最大增长即可。
从前往后,用当前价格减去此前最低价格,就是在当前点卖出股票能获得的最高利润。
扫描的过程中更新最大利润和最低价格就行了。
time complexity is O(n). constant space.
public class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length <= 1)
            return 0;
            
        int minprice = prices[0];
        int result = 0;
        
        for(int i = 1; i < prices.length; i++) {
            minprice = Math.min(prices[i], minprice);
            int diff = prices[i] - minprice;
            if(result < diff)
                result = diff;
        }
        return result;
    }
}

Find Peak Element

A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

Note:
Your solution should be in logarithmic complexity.
Solution: Binary search
如果中间元素大于其相邻后续元素,则中间元素左侧(包含该中间元素)必包含一个局部最大值。如果中间元素小于其相邻后续元素,则中间元素右侧必包含一个局部最大值。
时间复杂度O(logN), constant space.
public class Solution {
    public int findPeakElement(int[] num) {
        if(num == null)
            return 0;
        
        int L = 0, R = num.length - 1;
        while(L <= R) {
            if(L == R)
                return L;
                
            int mid = (L + R) / 2;
            if(num[mid] <= num[mid + 1]) {  
                L = mid + 1;  //if num[mid]<=num[mid + 1], peak element must on the right side
            }else { 
                R = mid;  //otherwise, peak element must on the left side
            }
        }
        return 0;
    }
}
Or:
public class Solution {
    public int findPeakElement(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }
        
        int left = 0;
        int right = nums.length - 1;
        while(left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
}

Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
Solution: Recursion
依次读取数字,然后把数字可以代表的字符依次加到当前的所有结果中,然后进入下一次迭代。
假设总共有n个digit,每个digit可以代表k个字符,那么时间复杂度是O(k^n),就是结果的数量,空间复杂度也是一样。
Run time complexity is O(3^n)
public class Solution {
    public ArrayList letterCombinations(String digits) {
        ArrayList result = new ArrayList();
        if(digits == null || digits.length() == 0) {
            return result;
        }
        
        String[] letter = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        StringBuilder str = new StringBuilder();
        select(digits, letter, digits.length(), result, str);
        return result;
    }
    
    public void select(String digits, String[] letter, int remain, ArrayList result, StringBuilder str) {
        if(remain == 0) {  //说明对digits遍历结束
            result.add(str.toString());
            return;
        }
        
        String s = letter[digits.charAt(0) - '0']; //得到digits[0]对应的string s 
        
        for(int i = 0; i < s.length(); i++) {  //DFS
            str = str.append(s.charAt(i));
            select(digits.substring(1), letter, remain - 1, result, str);
            str.deleteCharAt(str.length() - 1);  //恢复现场
        }
    }
}

Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.
Solution: BFS
用图的方法。我们先给题目进行图的映射,顶点则是每个字符串,然后两个字符串如果相差一个字符则我们进行连边。接下来看看这个方法的优势,注意到我们的字符集只有小写字母,而且字符串长度固定,假设是L。那么可以注意到每一个字符可以对应的边则有25个(26个小写字母减去自己),那么一个字符串可能存在的边是25*L条。接下来就是检测这些边对应的字符串是否在字典里,就可以得到一个完整的图的结构了。根据题目的要求,等价于求这个图一个顶点到另一个顶点的最短路径,一般我们用广度优先搜索(不熟悉搜索的朋友可以看看Clone Graph)即可。这个算法中最坏情况是把所有长度为L的字符串都看一下,或者把字典中的字符串都看一下,而长度为L的字符串总共有26^L,所以时间复杂度是O(min(26^L, size(dict)),空间上需要存储访问情况,也是O(min(26^L, size(dict))。
public class Solution {
    public int ladderLength(String start, String end, Set dict) {
        if(dict.size() == 0)
            return 0;
        
        LinkedList curWord = new LinkedList();
        LinkedList count = new LinkedList();
        curWord.add(start);
        count.add(1);
        
        while(!curWord.isEmpty()) {
            String cur = curWord.pop();
            Integer step = count.pop();
            
            if(cur.equals(end)) {
                return step;
            }
            
            for(int i = 0; i < cur.length(); i++) {
                char[] charInCur = cur.toCharArray();
                for(char c = 'a'; c <= 'z'; c++) {
                    charInCur[i] = c;
                    String newWord = new String(charInCur);
                    if(dict.contains(newWord)) {
                        curWord.add(newWord);
                        count.add(step + 1);
                        dict.remove(newWord);
                    }
                }
            }
        }
        return 0;
    }
}

4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
  • Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
  • The solution set must not contain duplicate quadruplets.
    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

Solution1:
A typical k-sum problem. Time is N to the poser of (k-1).
Run time complexity is O(n^3), solution based on 3sum
the efficiency of the best solution for m sum is O(n^(m-1)) 
public class Solution {
    public ArrayList> fourSum(int[] num, int target) {
        ArrayList> result = new ArrayList>();
        HashSet> check = new HashSet>();
        Arrays.sort(num);
        
        if(num.length < 4)
            return result;
        
        for(int i = 0; i < num.length; i++) {
            //3 sum
            for(int j = i + 1; j < num.length; j++) {
                int start = j + 1;
                int end = num.length - 1;
                //2 sum
                while(start < end) {
                    int sum = num[i] + num[j] + num[start] + num[end];
                    ArrayList temp = new ArrayList();
                    if(sum == target) {
                        temp.add(num[i]);
                        temp.add(num[j]);
                        temp.add(num[start]);
                        temp.add(num[end]);
                        
                        if(!check.contains(temp)) {
                            result.add(temp);
                            check.add(temp);
                        }
                        start++;
                        end--;
                    }else if(sum < target) {
                        start++;
                    }else {
                        end--;
                    }
                }
            }
        }
        return result;
    }
}

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
Solution1: hashmap
要求复制一个链表,不过链表的每个结点带有一个随机指针,指向某一个结点。
先按照复制一个正常链表的方式复制,复制的时候把复制的结点做一个HashMap,以旧结点为key,新节点为value。这么做的目的是为了第二遍扫描的时候我们按照这个哈希表把结点的随机指针接上。需要一个哈希表的原因是当我们访问一个结点时可能它的随机指针指向的结点还没有访问过,结点还没有创建,所以我们需要线性的额外空间。
总共要进行两次扫描,所以时间复杂度是O(2*n)=O(n)。空间上需要一个哈希表来做结点的映射,所以空间复杂度也是O(n)。
/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null)
            return head;
        
        RandomListNode newHead = new RandomListNode(head.label);
        
        //key is original node, value is new node
        HashMap map = new HashMap();
        map.put(head, newHead);
        
        RandomListNode pre = newHead;
        RandomListNode node = head.next;
        
        //first loop, store node and newNode as key/value pair in hashmap
        while(node != null) {
            RandomListNode newNode = new RandomListNode(node.label);
            map.put(node, newNode);
            pre.next = newNode;
            pre = newNode;
            node = node.next;
        }
        
        node = head;
        RandomListNode copyNode = newHead;
        
        //second loop, copy the random pointer with help of the hashmap
        while(node != null) {
            copyNode.random = map.get(node.random);
            copyNode = copyNode.next;
            node = node.next;
        }
        
        return newHead;
    }
}

Solution2: 
对链表进行三次扫描,
第一次扫描对每个结点进行复制,然后把复制出来的新节点接在原结点的next,也就是让链表变成一个重复链表,就是新旧更替;
第二次扫描中我们把旧结点的随机指针赋给新节点的随机指针,因为新结点都跟在旧结点的下一个,所以赋值比较简单,就是node.next.random = node.random.next,其中node.next就是新结点,因为第一次扫描我们就是把新结点接在旧结点后面。
现在我们把结点的随机指针都接好了,最后一次扫描我们把链表拆成两个,第一个还原原链表,而第二个就是我们要求的复制链表。因为现在链表是旧新更替,只要把每隔两个结点分别相连,对链表进行分割即可。
这个方法总共进行三次线性扫描,所以时间复杂度是O(n)。而这里并不需要额外空间,所以空间复杂度是O(1)。

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null)
            return head;
        
        RandomListNode node = head;
        
        //first loop, copy node and put the new node next the original node
        while(node != null) {
            RandomListNode newNode = new RandomListNode(node.label); 
            newNode.next = node.next;
            node.next = newNode;
            node = newNode.next;
        }
        
        //second loop, assign the original random pointer to new node
        node = head;
        while(node != null) {
            if(node.random != null) {
                node.next.random = node.random.next; //node.next is the new copied node
            }
            node = node.next.next;
        }
        
        //third loop, break the list
        RandomListNode newHead = head.next;
        node = head;
        while(node != null) {
            RandomListNode newNode = node.next;
            node.next = newNode.next;
            if(newNode.next != null) {
                newNode.next = newNode.next.next;
            }
            node = node.next;
        }
        return newHead;
    }
}

3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Solution:
This problem is similar with 3 Sum. This kind of problem can be solve by using similar approach, i.e., two pointers from both left and right.
总的时间复杂度为O(n^2+nlogn)=(n^2),空间复杂度是O(n)
public class Solution {
    public int threeSumClosest(int[] num, int target) {
        int min = Integer.MAX_VALUE;
        int res = 0;
        int diff = 0;
        Arrays.sort(num);

        for(int i = 0; i < num.length; i++) {
            int j = i + 1;
            int k = num.length - 1;
            while(j < k) {
                int sum = num[i] + num[j] + num[k];
                diff = Math.abs(target - sum);

                if(diff < min) {
                    min = diff;
                    res = sum;
                }
                
                if(sum <= target)
                    j++;
                else
                    k--;
            }
        }
        return res;
    }
}