[不太可能会坚持看完的很好的链接]

学习下KMP：
http://blog.csdn.net/v_july_v/article/details/7041827

设计模式：
http://zz563143188.iteye.com/blog/1847029

iOS常用第三方库：
http://www.imooc.com/article/1248

[LeetCode] Majority Element II

Problem:

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Thinking:

这道题和LintCode的Majority Number II很像，但是稍有不同，需要考虑一个特殊情况：

Input:
[1,2]
Expected:
[1,2]

When there are two different elements in the array, both of the two elements appear more than n/3 times.

Java Code (写得这么长T_T):

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        
        int candidate1 = 0;
        int candidate2 = 0;
        int count1 = 0;
        int count2 = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (count1 == 0) {
                candidate1 = nums[i];
            } else if (count2 == 0) {
                candidate2 = nums[i];
            }
            
            if (nums[i] == candidate1) {
                count1++;
            }
            else if (nums[i] == candidate2) {
                count2++;
            } else {
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == candidate1) {
                count1++;
            }else if (nums[i] == candidate2) {
                count2++;
            }
        }
        
        if (count1 > nums.length / 3) {
            result.add(candidate1);
        }
        if (count2 > nums.length / 3) {
            result.add(candidate2);
        }
        
        return result;
    }
}

[方法整理] 关于用Java8开发的webapp在EC2 instance上部署的问题

过程基本上与之前写过的Deploy war file on EC2 instance相同，但是java的版本不一样，所以需要如下操作：

（1）将EC2上默认安装的Java7升级到Java8
（reference:http://serverfault.com/questions/664643/how-can-i-upgrade-to-java-1-8-on-an-amazon-linux-server）：

sudo yum remove java-1.7.0-openjdk
sudo yum install java-1.8.0

（2）安装tomcat8：
（reference：http://stackoverflow.com/questions/26637550/how-to-install-tomcat-8-in-amazon-webservices-ec2）

yum install tomcat8-webapps tomcat8-admin-webapps

脑洞：关于EC2的security group的设定，今天又犯迷糊了，应该是这样的：

[笔记] UITabBarControllerDelegate

要使用UITabBarControllerDelegate，先来个视频链接（这个视频是iOS7的，如果在iOS8的话，有一些不同。）：

https://www.youtube.com/watch?v=QFPEaR-CLxM

（1）MyTabBarControllerDelegate.h文件里，需要加 #import <UIKit/UIKit.h>

（2）想要看Tab Bar Controller Scene的话，需要选择Editor --> Show Document Outline

[笔记] CLLocationManager

Demo上传到GitHub了：
https://github.com/1992chenlu/CLLocationManagerDemo

（1）开始以为很好用（但实际上还没有拿来抄的水平）的CLLocationManager的demo：
https://github.com/alienjun/CLLocationManager-iOS8

（2）真正可抄的Map + locationManager的代码（感觉代码很简洁）：
http://stackoverflow.com/questions/25848125/ios-8-mkmapview-user-location-request-failure
上面这个链接里的代码唯一的问题是少了一句这个（不加这一句的话，那个叫做didUpdateLocations的回调函数是不会被调用的）

[self.locationManager startUpdatingLocation];

（3）加Marker，抄的下面这个链接Marker部分的代码：
http://www.appcoda.com/ios-programming-101-drop-a-pin-on-map-with-mapkit-api/

// Add an annotation
    MKPointAnnotation *point = [[MKPointAnnotation alloc] init];
    point.coordinate = userLocation.coordinate;
    point.title = @"Where am I?";
    point.subtitle = @"I'm here!!!";
    
    [self.mapView addAnnotation:point];

另外，关于清空Marker：

[mapView removeAnnotations:mapView.annotations];

（4）用NSTimer实现每隔1秒钟向控制台输出一次当前位置：
NSTimer的资料：
http://stackoverflow.com/questions/6152963/how-to-display-seconds-using-nstimer
初始化一个这样的NSTimer变量：

_timer = [NSTimer scheduledTimerWithTimeInterval:1 target:self selector:@selector(timerFireMethod:) userInfo:nil repeats:YES];

再写一下这个函数里面：

- (void)timerFireMethod:(NSTimer*)theTimer {
    //remove a second from the display
    NSLog(@"Latitude:%f Longitude:%f", self.locationManager.location.coordinate.latitude, self.locationManager.location.coordinate.longitude);
}

就可以实现一秒钟输出一次当前的坐标了。

（5）给一个坐标，用Geocoder的reverseGeocodeLocation把它转换成对应的地址。

[LeetCode] Kth Largest Element in an Array

Problem:

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

Java Code:

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k > nums.length) {
            return -1;
        }
        
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

Explained Solutions: https://leetcode.com/discuss/36966/solution-explained

[LeetCode] Summary Ranges

Problem:

Given a sorted integer array without duplicates, return the summary of its ranges.
For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.


https://leetcode.com/problems/summary-ranges/

Java Code:

public class Solution {
    public List<String> summaryRanges(int[] nums) {
        List<String> result = new ArrayList<String>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        
        int pre = nums[0];
        int range = 0;
        
        for (int i = 1; i <= nums.length; i++) {
            if (i != nums.length && nums[i - 1] == nums[i] - 1) {
                range++;
            } else {
                if (range == 0) {
                    result.add(Integer.toString(pre));
                } else {
                    result.add(Integer.toString(pre) + "->" + Integer.toString(pre + range));
                }
                if (i != nums.length) {
                    pre = nums[i];
                    range = 0;
                }
            }
        }
        return result;
    }
}

[LeetCode] Maximum Product Subarray

Problem:

Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Java Code:

public class Solution {
    public int maxProduct(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        } else if (A.length == 1) {
            return A[0];
        }
        
        int length = A.length;
        int [] sMax = new int[length];
        int [] sMin = new int[length];
        int maxProduct = A[0];
        
        sMax[0] = A[0];
        sMin[0] = A[0];
        for (int i = 1; i < length; i++) {
            sMax[i] = Math.max(Math.max(sMax[i - 1] * A[i], sMin[i - 1] * A[i]), A[i]);
            sMin[i] = Math.min(Math.min(sMax[i - 1] * A[i], sMin[i - 1] * A[i]), A[i]);
            maxProduct = Math.max(maxProduct, sMax[i]);
        }
        
        return maxProduct;
    }
}

[LeetCode] Basic Calculator II

Problem:

Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, and / operators. The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
Note: Do not use the eval built-in library function.

Thinking:

和 #224 Basic Calculator思路基本一样，先转换为后缀式（postfix notation），然后计算后缀式的值，照抄了 #224 讨论区的一个支持*/的解法，那个链接的讲解很清楚。

（脑洞：这次是Leetcode全网第六个AC的，头一次排名这么靠前呢！虽然可以说是作弊了的T_T）

Java Code:

(ref:https://leetcode.com/discuss/39454/accepted-infix-postfix-based-solution-explaination-600ms)

public class Solution {
    int rank(char op){
        // the bigger the number, the higher the rank
        switch(op){
            case '+':return 1;
            case '-':return 1;
            case '*':return 2;
            case '/':return 2;
            default :return 0; // '(' 
        }
    }
    List<Object> infixToPostfix(String s) {
        Stack<Character> operators = new Stack<Character>();
        List<Object> postfix = new LinkedList<Object>();

        int numberBuffer = 0;
        boolean bufferingOperand = false;
        for (char c : s.toCharArray()) {
            if (c >= '0' && c <= '9') {
                numberBuffer = numberBuffer * 10 + c - '0';
                bufferingOperand = true;
            } else {
                if(bufferingOperand)
                    postfix.add(numberBuffer);
                numberBuffer = 0;
                bufferingOperand = false;

                if (c == ' '|| c == '\t')
                    continue;

                if (c == '(') {
                    operators.push('(');
                } else if (c == ')') {
                    while (operators.peek() != '(')
                        postfix.add(operators.pop());
                    operators.pop(); // popping "("
                } else { // operator
                    while (!operators.isEmpty() && rank(c) <= rank(operators.peek()))
                        postfix.add(operators.pop());
                    operators.push(c);
                }
            }

        }
        if (bufferingOperand)
            postfix.add(numberBuffer);

        while (!operators.isEmpty())
            postfix.add(operators.pop());

        return postfix;
    }

    int evaluatePostfix(List<Object> postfix) {
        Stack<Integer> operands = new Stack<Integer>();
        int a = 0, b = 0;
        for (Object s : postfix) {
            if(s instanceof Character){
                char c = (Character) s;
                b = operands.pop();
                a = operands.pop();
                switch (c) {
                    case '+': operands.push(a + b); break;
                    case '-': operands.push(a - b); break;
                    case '*': operands.push(a * b); break;
                    default : operands.push(a / b); 
                }
            }else { // instanceof Integer
                operands.push((Integer)s);
            }
        }
        return operands.pop();
    }

    public int calculate(String s) {
        return evaluatePostfix(infixToPostfix(s));
    }

}

[LeetCode] The Skyline Problem

Problem:

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

 

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

• The number of buildings in any input list is guaranteed to be in the range [0, 10000].
• The input list is already sorted in ascending order by the left x position Li.
• The output list must be sorted by the x position.
• There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]

Thinking:

(1) 自建一个名为Height的数据结构，保存一个building的index和height。约定，当height为负数时表示这个高度为height的building起始于index；height为正时表示这个高度为height的building终止于index。

(2) 对building数组进行处理，每一行[ Li, Ri, Hi ]，根据Height的定义，转换为两个Height的对象，即，Height(Li, -Hi) 和 Height(Ri, Hi)。 将这两个对象存入heights这个List中。

(3) 写个Comparator对heights进行升序排序，首先按照index的大小排序，若index相等，则按height大小排序，以保证一栋建筑物的起始节点一定在终止节点之前。

(4) 将heights转换为结果。使用PriorityQueue对高度值进行暂存。遍历heights，遇到高度为负值的对象时，表示建筑物的起始节点，此时应将这个高度加入PriorityQueue。遇到高度为正值的对象时，表示建筑物的终止节点，此时应将这个高度从PriorityQueue中除去。且在遍历的过程中检查，当前的PriorityQueue的peek()是否与上一个iteration的peek()值（prev）相同，若否，则应在结果中加入[当前对象的index, 当前PriorityQueue的peek()]，并更新prev的值。

思路是照抄这个链接的：http://www.cnblogs.com/easonliu/p/4531020.html
（脑洞：C++全忘光了，这个链接的代码好久才看懂，赶快补！）

Java Code:

public class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> result = new ArrayList<int[]>();
        if (buildings == null || buildings.length == 0 || buildings[0].length == 0) {
            return result;
        }
        
        List<Height> heights = new ArrayList<Height>();
        for (int[] building : buildings) {
            heights.add(new Height(building[0], -building[2]));
            heights.add(new Height(building[1], building[2]));
        }
        Collections.sort(heights, new Comparator<Height>() {
            @Override
            public int compare(Height h1, Height h2) {
                return h1.index != h2.index ? h1.index - h2.index : h1.height - h2.height;
            }
        });
        
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(1000, Collections.reverseOrder());
        pq.offer(0);
        int prev = 0;
        for (Height h : heights) {
            if (h.height < 0) {
                pq.offer(-h.height);
            } else {
                pq.remove(h.height);
            }
            int cur = pq.peek();
            if (cur != prev) {
                result.add(new int[]{h.index, cur});
                prev = cur;
            }
        }
        
        return result;
    }
    
    class Height {
        int index;
        int height;
        Height(int index, int height) {
            this.index = index;
            this.height = height;
        }
    }
}

[笔记] Objective-c 奇奇怪怪的地方

If you need to supply multiple parameters, the syntax is again quite different from C. Multiple parameters to a C function are specified inside the parentheses, separated by commas; in Objective-C, the declaration for a method taking two parameters looks like this:

- (void)someMethodWithFirstValue:(SomeType)value1 secondValue:(AnotherType)value2;

In this example, value1 and value2 are the names used in the implementation to access the values supplied when the method is called, as if they were variables.

(reference: http://stackoverflow.com/questions/722651/how-do-i-pass-multiple-parameters-in-objective-c)
Objective-C doesn't have named parameters, so everything on the left side of a colon is part of the method name. For example,

- (NSMutableArray *)getBusStops:(NSString *)busStop
                        forTime:(NSTimeInterval *)timeInterval

getBusStops: forTime:
is the name of the method. The name is broken up so it can be more descriptive. You could simply name your method

getBusStops: :

but that doesn't tell you much about the second parameter.

My question: Then, how can I call a method?

[LeetCode] Word Break

Problem:

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".

Java Code:

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        //f[i]: if s.substring(0,i) can be segmented
        //f[i] = f[x] + dict.contains(s.substring(x, i)), x>0 <i
        
        if (s == null || s.length() == 0 || dict == null || dict.size() == 0) {
            return false;
        }
        
        boolean[] f = new boolean[s.length() + 1];
        f[0] = true;
        
        for (int i = 1; i <= s.length(); i++) {
            if (dict.contains(s.substring(0, i))) {
                f[i] = true;
            } else {
                for (int j = 1; j <= i; j++) {
                    f[i] = f[i] || (f[j] && dict.contains(s.substring(j, i)));
                }
            }
        }
        
        return f[s.length()];
    }
}

[LeetCode] Repeated DNA Sequences

Problem:

All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
For example,
Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Java Code:

public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<String>();
        if (s.length() < 10) {
            return result;
        }
        
        HashMap<Integer, Integer> hs = new HashMap<Integer, Integer>();
        for (int i = 0; i <= s.length() - 10; i++) {
            int current = seqToInt(s.substring(i, i + 10));
            if (!hs.containsKey(current)) {
                hs.put(current, 1);
            } else if (hs.get(current) == 1){
                result.add(intToSeq(current));
                hs.put(current, 2);
            }
        }
        
        return result;
    }
    
    private int seqToInt(String seq) {
        //A-00 C-01 G-10 T-11
        int res = 0;
        for (int i = 0; i < seq.length(); i++) {
            char a = seq.charAt(i);
            if (a == 'A') {
                res += 0;
            } else if (a == 'C') {
                res += 1;
            } else if (a == 'G') {
                res += 2;
            } else {
                res += 3;
            }
            res = res << 2;
        }
        res = res >> 2;
        return res;
    }
    
    private String intToSeq(int seq) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 10; i++) {
            int cur = seq & 0x0003;
            if (cur == 0) {
                sb.insert(0, 'A');
            } else if (cur == 1) {
                sb.insert(0, 'C');
            } else if (cur == 2) {
                sb.insert(0, 'G');
            } else {
                sb.insert(0, 'T');
            }
            seq = seq >> 2;
        }
        return new String(sb);
    }
}

[LeetCode] Maximal Square

Problem:

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.

Solution:

Dynamic Programming, explanation: 
http://bookshadow.com/weblog/2015/06/03/leetcode-maximal-square/

Java Code:

public class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        
        int[][] dp = new int[matrix.length][matrix[0].length];
        int max = 0;
        
        for (int i = 0; i < matrix.length; i++) {
            dp[i][0] = matrix[i][0] == '1' ? 1 : 0;
            max = Math.max(max, dp[i][0]);
        }
        
        for (int j = 0; j < matrix[0].length; j++) {
            dp[0][j] = matrix[0][j] == '1' ? 1 : 0;
            max = Math.max(max, dp[0][j]);
        }
        
        
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                dp[i][j] = matrix[i][j] == '1' ? 
                Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1 : 0;
                max = Math.max(max, dp[i][j]);
            }
        }
        
        return (int)Math.pow(max, 2);
    }
}

[LeetCode] Count Complete Tree Nodes

Problem:

Given a complete binary tree, count the number of nodes.

Java Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int leftHeight = countLeftHeight(root);
        int rightHeight = countRightHeight(root);
        if (leftHeight == rightHeight) {
            return (int)Math.pow(2, leftHeight + 1) - 1;//Attn: Mistake ^ operator as power here.
        } 
        
        return 1 + countNodes(root.left) + countNodes(root.right);
        
    }
    
    private int countLeftHeight(TreeNode root) {
        if (root == null) {
            return -1;
        }
        return 1 + countLeftHeight(root.left);
    }
    
    private int countRightHeight(TreeNode root) {
        if (root == null) {
            return -1;
        }
        return 1 + countRightHeight(root.right);
    }
}

[LeetCode] Implement Stack using Queues

Problem:

Implement the following operations of a stack using queues.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
empty() -- Return whether the stack is empty.

Java Code:

class MyStack {
    Queue<Integer> q1 = new LinkedList<Integer>();
    Queue<Integer> q2 = new LinkedList<Integer>();
    int size = 0;
    // Push element x onto stack.
    public void push(int x) {
        q1.add(x);
        size++;
    }

    // Removes the element on top of the stack.
    public void pop() {
        if (size == 0) {
            return;
        }
        int i = size;
        while (i != 1) {
            q2.add(q1.poll());
            i--;
        }
        size--;
        q1.poll();
        Queue<Integer> tempQ = q1;
        q1 = q2;
        q2 = tempQ;
        return;
    }

    // Get the top element.
    public int top() {
        if (size == 0) {
            return 0;
        }
        int i = size;
        while (i != 1) {
            q2.add(q1.poll());
            i--;
        }
        int tmp = q1.peek();
        q2.add(q1.poll());
        Queue<Integer> tempQ = q1;
        q1 = q2;
        q2 = tempQ;
        return tmp;
    }

    // Return whether the stack is empty.
    public boolean empty() {
        return (q1.peek() == null) && (q2.peek() == null);
    }
}

[LeetCode] Invert Binary Tree

Problem:

凑个热闹～

Java Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        
        invertTree(root.left);
        invertTree(root.right);
        
        return root;
    }
}

[LeetCode] Word Ladder

Problem:

Given two words (beginWord and endWord), and a dictionary, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time
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.

Java Code:

public class Solution {
    public int ladderLength(String start, String end, Set<String> dict) {
        Queue<String> queue = new LinkedList<String>();
        queue.offer(start);
        dict.remove(start);
        int length = 1;
        while (queue.peek() != null) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String temp = queue.poll();
                for (char c = 'a'; c <= 'z'; c++) {
                    for (int j = 0; j < temp.length(); j++) {
                        if (c == temp.charAt(j)) {
                            continue;
                        }
                        char[] chars = temp.toCharArray();
                        chars[j] = c;
                        String cur = new String(chars);
                        if (cur.equals(end)) {
                            return length + 1;
                        }
                        if (dict.contains(cur)) {
                            queue.offer(cur);
                            dict.remove(cur);
                        }
                    }
                }
            }
            length++;
        }
        return 0;
    }
}

[LeetCode] Minimum Window Substring

Problem:

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".

Java Code:

public class Solution {
    public String minWindow(String S, String T) {
        String result = "";
        if (S == null || S.length() == 0 || T == null || T.length() == 0) {
            return result;
        }
        
        Map<Character, Integer> toFind = new HashMap<Character, Integer>();
        for (int i = 0; i < T.length(); i++) {
            if (toFind.containsKey(T.charAt(i))) {
                toFind.put(T.charAt(i), toFind.get(T.charAt(i)) + 1);
            } else {
                toFind.put(T.charAt(i), 1);
            }
        }
        
        Map<Character, Integer> found = new HashMap<Character, Integer>();
        int tCount = 0;
        int leftBound = 0;
        
        for (int i = 0; i < S.length(); i++) {
            char current = S.charAt(i);
            if (!toFind.containsKey(current)) {
                continue;
            }
            if (found.containsKey(current)) {
                found.put(current, found.get(current) + 1);
            } else {
                found.put(current, 1);
            }
            if (found.get(current) <= toFind.get(current)) {
                tCount++;
            }
            if (tCount == T.length()) {
                while (leftBound < S.length()) {
                    char current2 = S.charAt(leftBound);
                    if (!toFind.containsKey(current2)) {
                        leftBound++;
                        continue;
                    }
                    if (found.get(current2) > toFind.get(current2)) {
                        leftBound++;
                        found.put(current2, found.get(current2) - 1);
                        continue;
                    }
                    break;
                }
                if (result.equals("") || S.substring(leftBound, i + 1).length() < result.length()) {
                    result = S.substring(leftBound, i + 1);
                }
            }
        }
        
        return result;
    }
}

[LeetCode] Min Stack

Problem:

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

Java Code:

Paste your text here.class MinStack {
    Stack<Integer> s = new Stack<Integer>();
    Stack<Integer> min = new Stack<Integer>();
    
    public void push(int x) {
        s.push(x);
        if (min.empty() || min.peek() >= x) {
            min.push(x);
        }
    }

    public void pop() {
        int x = s.pop();
        if (x == min.peek()) {
            min.pop();
        }
    }

    public int top() {
        return s.peek();
    }

    public int getMin() {
        return min.peek();
    }
}

[LeetCode] Basic Calculator

Problem:

Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
You may assume that the given expression is always valid.
Some examples:
"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

思路：

输入的表达式可以被看作 infix notation，为了对括号进行处理，要先将 infix notation 转换成 postfix notation (也就是 Reverse Polish Notation)，然后再计算 postfix notation 的值即可，计算的方法就是LeetCode上的那道“Evaluate Reverse Polish Notation”。

注：将 infix notation 转换为  postfix notation 的算法：

http://cs.nyu.edu/courses/Fall12/CSCI-GA.1133-002/notes/InfixToPostfixExamples.pdf

-------------------------------------------------------------------

The input expression could be seen as an infix notation. To take the parentheses away, I choose to convert the infix notation to postfix notation (aka. Reverse Polish Notation). Then, calculate the value of the postfix notation, which has already been covered by the "Evaluate Reverse Polish Notation" problem on LeetCode.

The algorithm to convert infix notation to postfix notation:
http://cs.nyu.edu/courses/Fall12/CSCI-GA.1133-002/notes/InfixToPostfixExamples.pdf

Java Code:

public class Solution {
    public static int calculate(String s) {
        String ss = toRPN(s);
        String tokens[] = toRPN(s).split("\\s+");
        int returnValue = 0;
        
        String operators = "+-";
 
        Stack<String> stack = new Stack<String>();
 
        for(String t : tokens){
            if(!operators.contains(t)){
                stack.push(t);
            }else{
                int a = Integer.valueOf(stack.pop());
                int b = Integer.valueOf(stack.pop());
                int index = operators.indexOf(t);
                switch(index){
                    case 0:
                        stack.push(String.valueOf(a+b));
                        break;
                    case 1:
                        stack.push(String.valueOf(b-a));
                        break;
                }
            }
        }
 
        returnValue = Integer.valueOf(stack.pop());
 
        return returnValue;
    }
    
    public static String toRPN(String input) {
        char[] in = input.toCharArray();
        Stack<Character> stack = new Stack<Character>();
        StringBuilder out = new StringBuilder();

        for (int i = 0; i < in.length; i++)
            switch (in[i]) {
            case '+':
            case '-':
                while (!stack.empty() && stack.peek() != '(') {
                    out.append(' ');
                    out.append(stack.pop());
                }
                out.append(' ');
                stack.push(in[i]);
                break;
            case '(':
                stack.push(in[i]);
                break;
            case ')':
                while (!stack.empty() && stack.peek() != '(') {
                    out.append(' ');
                    out.append(stack.pop());
                }
                stack.pop();
                break;
            case ' ':
                break;
            default:
                out.append(in[i]);
                break;
            }

        while (!stack.isEmpty()) {
            out.append(' ');
            out.append(stack.pop());
            
        }
        return out.toString();
    }
}

[LeetCode] Reverse Linked List

Problem:

Reverse a singly linked list.

Java Code:(难得做出个一次AC的)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode p = head;
        
        while (p != null) {
            ListNode tmp = p.next;
            p.next = pre;
            pre = p;
            p = tmp;
        }
        
        return pre;
    }
}

[LeetCode] Rectangle Area

Problem:

Find the total area covered by two rectilinear rectangles in a 2D plane.Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.
Assume that the total area is never beyond the maximum possible value of int.

Java Code:

public class Solution {
    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        return (C - A)*(D - B) + (G - E)*(H - F) - (Math.min(C, G) - Math.max(A, E)) * (Math.min(D, H) - Math.max(B, F));
    }
}

[LeetCode] Excel Sheet Column Title

Problem:

Given a positive integer, return its corresponding column title as appear in an Excel sheet.
For example:
    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB

Java Code:

public class Solution {
    public String convertToTitle(int n) {
        StringBuilder result = new StringBuilder();
        while (n > 0) {
            char a = n % 26 == 0 ? 'Z' : (char)('A' - 1 + n % 26);
            result.insert(0, a);
            n = (n - 1) / 26;
        }
        return new String(result);
    }
}

[LeetCode] Rotate Array

Problem:

Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Java Code:

public class Solution {
    public void rotate(int[] nums, int k) {
        if (nums == null || nums.length < 2 || k <= 0 || k == nums.length) {
            return;
        }
        if (k > nums.length) {
            k = k % nums.length;
        }
        rotateIJ(nums, 0, nums.length - 1 - k);
        rotateIJ(nums, nums.length - k, nums.length - 1);
        rotateIJ(nums, 0, nums.length - 1);
    }
    
    public void rotateIJ(int[] nums, int i, int j) {
        while (i + 1 <= j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }
}

[LeetCode] Two Sum

Problem:

Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Java Code:

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        if (numbers == null || numbers.length < 2) {
            return result;
        }
        
        HashMap<Integer, ArrayList<Integer>> hs = new HashMap<Integer, ArrayList<Integer>>();
        
        for (int i = 0; i < numbers.length; i++) {
            if (hs.containsKey(numbers[i])) {
                hs.get(numbers[i]).add(i);
            } else {
                ArrayList<Integer> value = new ArrayList<Integer>();
                value.add(i);
                hs.put(numbers[i], value);
            }
        }
        
        for (int i = 0; i < numbers.length; i++) {
            int temp = target - numbers[i];
            if (hs.containsKey(temp)) {
                if (temp == numbers[i] && hs.get(temp).size() >= 2) {
                    result[0] = Math.min(hs.get(temp).get(0), hs.get(temp).get(1)) + 1;
                    result[1] = Math.max(hs.get(temp).get(0), hs.get(temp).get(1)) + 1;
                    break;
                } else if (temp != numbers[i]) {
                    result[0] = Math.min(i, hs.get(temp).get(0)) + 1;
                    result[1] = Math.max(i, hs.get(temp).get(0)) + 1;
                    break;
                }
            }
        }
        
        return result;
    }
}

[LeetCode] Word Break II

Problem:

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].

Java Code:

public class Solution {
    public ArrayList<String> wordBreak(String s, Set<String> dict) {
        ArrayList<String> result = new ArrayList<String>();
        if (s == null || s.length() == 0) {
            return result;
        }
        ArrayList<String> path = new ArrayList<String>();
        
        boolean[] f = new boolean[s.length() + 1];
        f[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            if (dict.contains(s.substring(0, i))) {
                f[i] = true;
            } else {
                for (int j = 0; j < i; j++) {
                    f[i] = f[i] || (f[j] && dict.contains(s.substring(j, i)));
                }
            }
        }
        
        if (f[s.length()] == false) {
            return result;
        } 
        helper(result, path, 0, s, dict);
        return result;
    }
    
    private void helper(ArrayList<String> result, ArrayList<String> path, int start, String s, Set<String> dict) {
        if (start == s.length()) {
            StringBuilder rst = new StringBuilder();
            for (String word : path) {
                rst.append(word);
                rst.append(" ");
            }
            result.add(new String(rst.substring(0, rst.length() - 1)));
            return;
        }
        for (int end = start + 1; end <= s.length(); end++) {
            if (dict.contains(s.substring(start, end))) {
                path.add(new String(s.substring(start, end)));
                helper(result, path, end, s, dict);
                path.remove(path.size() - 1);
            }
        }
    }
}

[LeetCode] Median of Two Sorted Arrays

Problem:

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Java Code:

public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        if (A == null || B == null) {
            return 0.0;
        }
        if ((A.length + B.length) % 2 == 1) {
            return findKthElement(A, B, 0, 0, (A.length + B.length) / 2 + 1) + 0.0;
        } else {
            return (findKthElement(A, B, 0, 0, (A.length + B.length) / 2) + findKthElement(A, B, 0, 0, (A.length + B.length) / 2 + 1)) / 2.0;
        }
    }
    
    private double findKthElement(int[] A, int[] B, int A_start, int B_start, int k) {
        if (A_start >= A.length) {
            return B[B_start + k - 1];
        }
        if (B_start >= B.length) {
            return A[A_start + k - 1];
        }
        if (k == 1) {
            return Math.min(A[A_start], B[B_start]);
        }
        int eleA;
        if (A_start + k / 2 - 1 < A.length) {
            eleA = A[A_start + k / 2 - 1];
        } else {
            eleA = Integer.MAX_VALUE;
        }
        int eleB;
        if (B_start + k / 2 - 1 < B.length) {
            eleB = B[B_start + k / 2 - 1];
        } else {
            eleB = Integer.MAX_VALUE;
        }
        if (eleA >= eleB) {
            return findKthElement(A, B, A_start, B_start + k / 2, k - k / 2);
        } else {
            return findKthElement(A, B, A_start + k / 2, B_start, k - k / 2);
        }
    }
}

[LeetCode] 3Sum

Problem:

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Java Code:

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (num == null || num.length == 0) {
            return result;
        }
        
        Arrays.sort(num);
        
        for (int i = 0; i < num.length; i++) {
            if (i != 0 && num[i] == num[i - 1]) {
                continue;
            }
            int start = i + 1;
            int end = num.length - 1;
            while (start < end) {
                if (num[i] + num[start] + num[end] == 0) {
                    ArrayList<Integer> temp = new ArrayList<Integer>();
                    temp.add(num[i]);
                    temp.add(num[start]);
                    temp.add(num[end]);
                    result.add(temp);
                    start++;
                    end--;
                    while (start < end && num[start] == num[start - 1]) {
                        start++;
                    }
                    while (start < end && num[end] == num[end + 1]) {
                        end--;
                    }
                } else if (num[i] + num[start] + num[end] > 0) {
                    end--;
                } else {
                    start++;
                }
            }
        }
        return result;
    }
}

[LeetCode] Decode Ways

Problem:

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.

Java Code:

public class Solution {
    public int numDecodings(String s) {
        //state: f[i] the number of decodings in s.substring(0, i)
        //f[i] = f[i - 1] + f[i - 2](if i >= 2 && decodable(s.substring(i - 1, i + 1)))
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        int[] dp = new int[s.length()];
        
        for (int i = 0; i < s.length(); i++) {
            int num2 = 0;
            if (i >= 1 && Integer.parseInt(s.substring(i - 1, i + 1)) <= 26 
                && Integer.parseInt(s.substring(i - 1, i + 1)) >= 10) {
                num2 = i >= 2 ? dp[i - 2] : 1;
            }
            int num1 = 0;
            if (Integer.parseInt(s.substring(i, i + 1)) >= 1) {
                num1 = i >= 1 ? dp[i - 1] : 1;
            }
            if (num1 == 0 && num2 == 0) {
                return 0;
            } else {
                dp[i] = num1 + num2;
            }
        }
        
        return dp[s.length() - 1];
    }
}

[LeetCode] Largest Number

Problem:

Given a list of non negative integers, arrange them such that they form the largest number. For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330. Note: The result may be very large, so you need to return a string instead of an integer.

Java Code:

public class Solution {
    public String largestNumber(int[] num) {
                StringBuilder result = new StringBuilder();
        
        if (num == null) {
            return new String(result);
        }
        
        Integer[] sorted = new Integer[num.length];
        for (int i = 0; i < num.length; i++) {
            sorted[i] = new Integer(num[i]);
        }
        
        Arrays.sort(sorted, new Comparator<Integer>(){
            @Override
            public int compare(Integer a, Integer b){
                if (a == 0 || b == 0) {
                    return a == 0 ? 1 : -1;
                }
                String s1 = a.toString() + b.toString();
                String s2 = b.toString() + a.toString();
                int i = 0;
                while (i < s1.length()) {
                    if (s1.charAt(i) > s2.charAt(i)) {
                        return -1;
                    }
                    if (s1.charAt(i) < s2.charAt(i)) {
                        return 1;
                    }
                    i++;
                }
                return 1;
            }
        });
        
        boolean flag = true;
        for (int i = 0; i < sorted.length; i++) {
            if (sorted[i] != 0) {
                flag = false;
            }
            result.append(Integer.toString(sorted[i]));
        }
        
        if (flag) {
            return "0";
        }
        
        return new String(result);
    }
    
}

[LeetCode] Reverse Words in a String

Problem:

Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".

Java Code:

public class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0)
            return s;
        
        ArrayList<String> wordList = new ArrayList<String>();
        
        StringBuilder subString = new StringBuilder();
        StringBuilder result = new StringBuilder();
        int index = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) != ' ')
                subString.append(s.charAt(i));
            else if (subString.length() != 0){
                if (result.length() != 0)
                    result.append(" ");
                result.append(subString.reverse());
                subString = new StringBuilder();
                index = i - 1;
            }
        }
        if (subString.length() != 0) {
            if (result.length() != 0)
                result.append(" ");
            result.append(subString.reverse());
        }
            
        
        return result.toString();
    }
}

[LeetCode] Contains Duplicate III

Problem:
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

Java Code:

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length <= 1 || t < 0) {
            return false;
        }
        TreeSet<Integer> tree = new TreeSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            Integer floor = tree.floor(nums[i] + t);
            Integer ceiling = tree.ceiling(nums[i] - t);
            if ((floor != null && floor >= nums[i]) || (ceiling != null && ceiling <= nums[i])) {
                return true;
            }
            tree.add(nums[i]);
            if (i >= k) {
                tree.remove(nums[i - k]);
            }
        }
        return false;
    }
}

[LeetCode] String to Integer (atoi)

Problem:

Implement atoi to convert a string to an integer.

Code:

public class Solution {
    public int atoi(String str) {
        if (str == null || str.length() < 1) {
            return 0;
        }
        str = str.trim();
        int i = 0;
        double result = 0;
        boolean isPositive = true;
        if (str.charAt(0) == '-') {
            isPositive = false;
            i = 1;
        } else if (str.charAt(0) == '+') {
            i = 1;
        }
        
        for (; i < str.length(); i++) {
            int tmp = charToInt(str.charAt(i));
            if (tmp == -1) {
                break;
            }
            result *= 10;
            result += tmp;
        }
        result = isPositive == false ? -result : result;
        if (result > Integer.MAX_VALUE) 
            return Integer.MAX_VALUE;
        else if (result < Integer.MIN_VALUE) 
            return Integer.MIN_VALUE;
        return (int)result;
    }
    
    public int charToInt(char a) {
        if (a >= '0' && a <= '9') 
            return a - '0';
        return -1;
    }
}

[杂] Servlet 文件上传

最近做项目，用eclipse J2EE写Servlet，想尝试在Servlet里面写一段代码，新建一个文件存到当前workspace本项目的文件夹下面。

    String file = "haha.txt";
    String path = session.getServletContext().getRealPath(""); 
    try {
        FileWriter outfile = new FileWriter( path + "/" + file);
        System.out.println(path);
        outfile.write(“HAHAHA!!“);
        outfile.close();
    } catch (IOException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();

    }

但是无论怎样尝试都做不出来，明明同样的代码当作Java Application跑就完全没有问题。问了大神，大神说这种事情是做不到的。本着钻研的精神，努橙决定仔细研究下。查了半天资料，找到一个在servlet中取得当前目录的方法。（https://community.oracle.com/thread/1849683）

先在servlet中get到session：

HttpSession session = request.getSession();

然后找当前目录：

String path = session.getServletContext().getRealPath(""); 

最后s.o.p出来的path长这样（什么鬼！）：

/Volumes/doc/workspace 1/.metadata/.plugins/org.eclipse.wst.server.core/tmp0/wtpwebapps/task14

和真正的本项目的目录（/Volumes/doc/workspace 1/task14）是两个样子嘛！所以才写不过去嘛！把path hardcode 成随便一个已知的目录，就完全可以新建文件！继续本着钻研的精神，努橙决定把task14这个项目部署到tomcat上，看看这次会不会可以写过去。于是乎，在/Users/.../Downloads/apache-tomcat-8.0.14/webapps/task14这个目录下面成功找到了haha.txt。以后可以研究一下webapp是怎么在eclipse的tomcat server上跑的。哈哈！