面试10大算法汇总

时间：2023-01-20 05:30:05

以下从Java角度解释面试常见的算法和数据结构：字符串，链表，树，图，排序，递归 vs. 迭代，动态规划，位操作，概率问题，排列组合，以及一些需要寻找规律的题目。


1. 字符串和数组


字符串和数组是最常见的面试题目类型，应当分配最大的时间。关于字符串，首先需要注意的是和C++不同，Java字符串不是char数组。没有IDE代码自动补全功能，应该记住下面的这些常用的方法。


toCharArray() //获得字符串对应的char数组
Arrays.sort()  //数组排序
Arrays.toString(char[] a) //数组转成字符串
charAt(int x) //获得某个索引处的字符
length() //字符串长度
length //数组大小
substring(int beginIndex) 
substring(int beginIndex, int endIndex)
Integer.valueOf() //string to integer
String.valueOf() /integer to string


字符串和数组本身很简单，但是相关的题目需要更复杂的算法来解决。比如说动态规划，搜索，等等。


经典题目：

1) Evaluate Reverse Polish Notation     

The problem:

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:
  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

思路：

This problem is simple. After understanding the problem, we should quickly realize that this problem can be solved by using a stack. We can loop through each element in the given array. When it is a number, push it to the stack. When it is an operator, pop two numbers from the stack, do the calculation, and push back the result.

面试10大算法汇总


解法1:

[java] view plaincopy
  1. public class Test {  
  2.    
  3.     public static void main(String[] args) throws IOException {  
  4.         String[] tokens = new String[] { "2", "1", "+", "3", "*" };  
  5.         System.out.println(evalRPN(tokens));  
  6.     }  
  7.    
  8.     public static int evalRPN(String[] tokens) {  
  9.         int returnValue = 0;  
  10.         String operators = "+-*/";  
  11.    
  12.         Stack<String> stack = new Stack<String>();  
  13.    
  14.         for (String t : tokens) {  
  15.             if (!operators.contains(t)) {  
  16.                 stack.push(t);  
  17.             } else {  
  18.                 int a = Integer.valueOf(stack.pop());  
  19.                 int b = Integer.valueOf(stack.pop());  
  20.                 switch (t) {  
  21.                 case "+":  
  22.                     stack.push(String.valueOf(a + b));  
  23.                     break;  
  24.                 case "-":  
  25.                     stack.push(String.valueOf(b - a));  
  26.                     break;  
  27.                 case "*":  
  28.                     stack.push(String.valueOf(a * b));  
  29.                     break;  
  30.                 case "/":  
  31.                     stack.push(String.valueOf(b / a));  
  32.                     break;  
  33.                 }  
  34.             }  
  35.         }  
  36.    
  37.         returnValue = Integer.valueOf(stack.pop());  
  38.    
  39.         return returnValue;  
  40.     }  
  41. }  

解法2:

[java] view plaincopy
  1. public class Solution {  
  2.     public int evalRPN(String[] tokens) {  
  3.    
  4.         int returnValue = 0;  
  5.    
  6.         String operators = "+-*/";  
  7.    
  8.         Stack<String> stack = new Stack<String>();  
  9.    
  10.         for(String t : tokens){  
  11.             if(!operators.contains(t)){  
  12.                 stack.push(t);  
  13.             }else{  
  14.                 int a = Integer.valueOf(stack.pop());  
  15.                 int b = Integer.valueOf(stack.pop());  
  16.                 int index = operators.indexOf(t);  
  17.                 switch(index){  
  18.                     case 0:  
  19.                         stack.push(String.valueOf(a+b));  
  20.                         break;  
  21.                     case 1:  
  22.                         stack.push(String.valueOf(b-a));  
  23.                         break;  
  24.                     case 2:  
  25.                         stack.push(String.valueOf(a*b));  
  26.                         break;  
  27.                     case 3:  
  28.                         stack.push(String.valueOf(b/a));  
  29.                         break;  
  30.                 }  
  31.             }  
  32.         }  
  33.    
  34.         returnValue = Integer.valueOf(stack.pop());  
  35.    
  36.         return returnValue;  
  37.    
  38.     }  
  39. }  

2) Longest Palindromic Substring

题目来源：

Finding the longest palindromic substring is a classic problem of coding interview. In this post, I will summarize 3 different solutions for this problem.

解法一：暴力算法

Naively, we can simply examine every substring and check if it is palindromic. The time complexity is O(n^3). If this is submitted to LeetCode onlinejudge, an error message will be returned - "Time Limit Exceeded". Therefore, this approach is just a start, we need a better algorithm.

[java] view plaincopy
  1. public static String longestPalindrome1(String s) {  
  2.    
  3.     int maxPalinLength = 0;  
  4.     String longestPalindrome = null;  
  5.     int length = s.length();  
  6.    
  7.     // check all possible sub strings  
  8.     for (int i = 0; i < length; i++) {  
  9.         for (int j = i + 1; j < length; j++) {  
  10.             int len = j - i;  
  11.             String curr = s.substring(i, j + 1);  
  12.             if (isPalindrome(curr)) {  
  13.                 if (len > maxPalinLength) {  
  14.                     longestPalindrome = curr;  
  15.                     maxPalinLength = len;  
  16.                 }  
  17.             }  
  18.         }  
  19.     }  
  20.    
  21.     return longestPalindrome;  
  22. }  
  23.    
  24. public static boolean isPalindrome(String s) {  
  25.    
  26.     for (int i = 0; i < s.length() - 1; i++) {  
  27.         if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {  
  28.             return false;  
  29.         }  
  30.     }  
  31.    
  32.     return true;  
  33. }  
解法二： 简单算法 [java] view plaincopy
  1. public String longestPalindrome(String s) {  
  2.     if (s.isEmpty()) {  
  3.         return null;  
  4.     }  
  5.    
  6.     if (s.length() == 1) {  
  7.         return s;  
  8.     }  
  9.    
  10.     String longest = s.substring(0, 1);  
  11.     for (int i = 0; i < s.length(); i++) {  
  12.         // get longest palindrome with center of i  
  13.         String tmp = helper(s, i, i);  
  14.         if (tmp.length() > longest.length()) {  
  15.             longest = tmp;  
  16.         }  
  17.    
  18.         // get longest palindrome with center of i, i+1  
  19.         tmp = helper(s, i, i + 1);  
  20.         if (tmp.length() > longest.length()) {  
  21.             longest = tmp;  
  22.         }  
  23.     }  
  24.    
  25.     return longest;  
  26. }  
  27.    
  28. // Given a center, either one letter or two letter,   
  29. // Find longest palindrome  
  30. public String helper(String s, int begin, int end) {  
  31.     while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {  
  32.         begin--;  
  33.         end++;  
  34.     }  
  35.     return s.substring(begin + 1, end);  
  36. }  

3) Word Break

题目：

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".

解法1:暴力

[java] view plaincopy
  1. public class Solution {  
  2.     public boolean wordBreak(String s, Set<String> dict) {  
  3.              return wordBreakHelper(s, dict, 0);  
  4.     }  
  5.    
  6.     public boolean wordBreakHelper(String s, Set<String> dict, int start){  
  7.         if(start == s.length())   
  8.             return true;  
  9.    
  10.         for(String a: dict){  
  11.             int len = a.length();  
  12.             int end = start+len;  
  13.    
  14.             //end index should be <= string length  
  15.             if(end > s.length())   
  16.                 continue;  
  17.    
  18.             if(s.substring(start, start+len).equals(a))  
  19.                 if(wordBreakHelper(s, dict, start+len))  
  20.                     return true;  
  21.         }  
  22.    
  23.         return false;  
  24.     }  
  25. }  
Time: O(n^2)

解法2: 动态规划

The key to solve this problem by using dynamic programming approach:

  • Define an array t[] such that t[i]==true => 0-(i-1) can be segmented using dictionary
  • Initial state t[0] == true
[java] view plaincopy
  1. public class Solution {  
  2.     public boolean wordBreak(String s, Set<String> dict) {  
  3.         boolean[] t = new boolean[s.length()+1];  
  4.         t[0] = true; //set first to be true, why?  
  5.         //Because we need initial state  
  6.    
  7.         for(int i=0; i<s.length(); i++){  
  8.             //should continue from match position  
  9.             if(!t[i])   
  10.                 continue;  
  11.    
  12.             for(String a: dict){  
  13.                 int len = a.length();  
  14.                 int end = i + len;  
  15.                 if(end > s.length())  
  16.                     continue;  
  17.    
  18.                 if(t[end]) continue;  
  19.    
  20.                 if(s.substring(i, end).equals(a)){  
  21.                     t[end] = true;  
  22.                 }  
  23.             }  
  24.         }  
  25.    
  26.         return t[s.length()];  
  27.     }  
  28. }  

Time: O(string length * dict size)

One tricky part of this solution is the case:

INPUT: "programcreek", ["programcree","program","creek"].
解法3: 正则表达式

[java] view plaincopy
  1. public static void main(String[] args) {  
  2.     HashSet<String> dict = new HashSet<String>();  
  3.     dict.add("go");  
  4.     dict.add("goal");  
  5.     dict.add("goals");  
  6.     dict.add("special");  
  7.    
  8.     StringBuilder sb = new StringBuilder();  
  9.    
  10.     for(String s: dict){  
  11.         sb.append(s + "|");  
  12.     }  
  13.    
  14.     String pattern = sb.toString().substring(0, sb.length()-1);  
  15.     pattern = "("+pattern+")*";  
  16.     Pattern p = Pattern.compile(pattern);  
  17.     Matcher m = p.matcher("goalspecial");  
  18.    
  19.     if(m.matches()){  
  20.         System.out.println("match");  
  21.     }  
  22. }  

表达式

说明

    |

多个子表达式之间取“或”的关系

     *    

表达式匹配0次或任意多次，相当于{0,}




4) Word Ladder

题目：

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, 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", the program should 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.

解法：广度优先搜索

So we quickly realize that this looks like a tree searching problem for which breath first guarantees the optimal solution.

Assuming we have some words in the dictionary, and the start is "hit" as shown in the diagram below.

面试10大算法汇总

We can use two queues to traverse the tree, one stores the nodes, the other stores the step numbers.

Updated on 2/27/2015.

[java] view plaincopy
  1. public int ladderLength(String start, String end, HashSet<String> dict) {  
  2.     if (dict.size() == 0)  
  3.         return 0;  
  4.    
  5.     dict.add(end);  
  6.    
  7.     LinkedList<String> wordQueue = new LinkedList<String>();  
  8.     LinkedList<Integer> distanceQueue = new LinkedList<Integer>();  
  9.    
  10.     wordQueue.add(start);  
  11.     distanceQueue.add(1);  
  12.    
  13.     //track the shortest path  
  14.     int result = Integer.MAX_VALUE;  
  15.     while (!wordQueue.isEmpty()) {  
  16.         String currWord = wordQueue.pop();  
  17.         Integer currDistance = distanceQueue.pop();  
  18.    
  19.         if (currWord.equals(end)) {  
  20.             result = Math.min(result, currDistance);  
  21.         }  
  22.    
  23.         for (int i = 0; i < currWord.length(); i++) {  
  24.             char[] currCharArr = currWord.toCharArray();  
  25.             for (char c = 'a'; c <= 'z'; c++) {  
  26.                 currCharArr[i] = c;  
  27.    
  28.                 String newWord = new String(currCharArr);  
  29.                 if (dict.contains(newWord)) {  
  30.                     wordQueue.add(newWord);  
  31.                     distanceQueue.add(currDistance + 1);  
  32.                     dict.remove(newWord);  
  33.                 }  
  34.             }  
  35.         }  
  36.     }  
  37.    
  38.     if (result < Integer.MAX_VALUE)  
  39.         return result;  
  40.     else  
  41.         return 0;  
  42. }  


5) Median of Two Sorted Arrays

6) Regular Expression Matching 

7) Merge Intervals

问题：

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
思路：

The key to solve this problem is defining a Comparator first to sort the arraylist of Intevals. And then merge some intervals.

The take-away message from this problem is utilizing the advantage of sorted list/array.

解法：
[java] view plaincopy
  1. class Interval {  
  2.     int start;  
  3.     int end;  
  4.    
  5.     Interval() {  
  6.         start = 0;  
  7.         end = 0;  
  8.     }  
  9.    
  10.     Interval(int s, int e) {  
  11.         start = s;  
  12.         end = e;  
  13.     }  
  14. }  
  15.    
  16. public class Solution {  
  17.     public ArrayList<Interval> merge(ArrayList<Interval> intervals) {  
  18.    
  19.         if (intervals == null || intervals.size() <= 1)  
  20.             return intervals;  
  21.    
  22.         // sort intervals by using self-defined Comparator  
  23.         Collections.sort(intervals, new IntervalComparator());  
  24.    
  25.         ArrayList<Interval> result = new ArrayList<Interval>();  
  26.    
  27.         Interval prev = intervals.get(0);  
  28.         for (int i = 1; i < intervals.size(); i++) {  
  29.             Interval curr = intervals.get(i);  
  30.    
  31.             if (prev.end >= curr.start) {  
  32.                 // merged case  
  33.                 Interval merged = new Interval(prev.start, Math.max(prev.end, curr.end));  
  34.                 prev = merged;  
  35.             } else {  
  36.                 result.add(prev);  
  37.                 prev = curr;  
  38.             }  
  39.         }  
  40.    
  41.         result.add(prev);  
  42.    
  43.         return result;  
  44.     }  
  45. }  
  46.    
  47. class IntervalComparator implements Comparator<Interval> {  
  48.     public int compare(Interval i1, Interval i2) {  
  49.         return i1.start - i2.start;  
  50.     }  
  51. }  

8) Insert Interval

问题：

Problem:

Given a set of non-overlapping & sorted intervals, insert a new interval into the intervals (merge if necessary).

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

解法：

[java] view plaincopy
  1. /** 
  2.  * Definition for an interval. 
  3.  * public class Interval { 
  4.  *     int start; 
  5.  *     int end; 
  6.  *     Interval() { start = 0; end = 0; } 
  7.  *     Interval(int s, int e) { start = s; end = e; } 
  8.  * } 
  9.  */  
  10. public class Solution {  
  11.     public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {  
  12.    
  13.         ArrayList<Interval> result = new ArrayList<Interval>();  
  14.    
  15.         for(Interval interval: intervals){  
  16.             if(interval.end < newInterval.start){  
  17.                 result.add(interval);  
  18.             }else if(interval.start > newInterval.end){  
  19.                 result.add(newInterval);  
  20.                 newInterval = interval;          
  21.             }else if(interval.end >= newInterval.start || interval.start <= newInterval.end){  
  22.                 newInterval = new Interval(Math.min(interval.start, newInterval.start), Math.max(newInterval.end, interval.end));  
  23.             }  
  24.         }  
  25.    
  26.         result.add(newInterval);   
  27.    
  28.         return result;  
  29.     }  
  30. }  

9) Two Sum

题目：

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.

For example:

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
解法1: [java] view plaincopy
  1. public static int[] twoSum(int[] numbers, int target) {  
  2.     int[] ret = new int[2];  
  3.     for (int i = 0; i < numbers.length; i++) {  
  4.         for (int j = i + 1; j < numbers.length; j++) {  
  5.             if (numbers[i] + numbers[j] == target) {  
  6.                 ret[0] = i + 1;  
  7.                 ret[1] = j + 1;  
  8.             }  
  9.         }  
  10.     }  
  11.     return ret;  
  12. }  

解法2: [java] view plaincopy
  1. public class Solution {  
  2.     public int[] twoSum(int[] numbers, int target) {  
  3.     HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();  
  4.     int[] result = new int[2];  
  5.    
  6.     for (int i = 0; i < numbers.length; i++) {  
  7.         if (map.containsKey(numbers[i])) {  
  8.             int index = map.get(numbers[i]);  
  9.             result[0] = index+1 ;  
  10.             result[1] = i+1;  
  11.             break;  
  12.         } else {  
  13.             map.put(target - numbers[i], i);  
  14.         }  
  15.     }  
  16.    
  17.     return result;  
  18.     }  
  19. }  

9) 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.

Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)
解法1:
[java] view plaincopy
  1. public class Solution {  
  2.     public ArrayList<ArrayList<Integer>> threeSum(int[] num) {  
  3.         //sort array  
  4.         Arrays.sort(num);  
  5.    
  6.         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();  
  7.         ArrayList<Integer> each = new ArrayList<Integer>();  
  8.         for(int i=0; i<num.length; i++){  
  9.             if(num[i] > 0) break;  
  10.    
  11.             for(int j=i+1; j<num.length; j++){  
  12.                 if(num[i] + num[j] > 0 && num[j] > 0) break;  
  13.    
  14.                 for(int k=j+1; k<num.length; k++){  
  15.                   if(num[i] + num[j] + num[k] == 0) {  
  16.    
  17.                       each.add(num[i]);  
  18.                       each.add(num[j]);  
  19.                       each.add(num[k]);  
  20.                       result.add(each);  
  21.                       each.clear();  
  22.                   }  
  23.                 }  
  24.             }  
  25.         }  
  26.    
  27.         return result;  
  28.     }  
  29. }  

解法2:
[java] view plaincopy
  1. public ArrayList<ArrayList<Integer>> threeSum(int[] num) {  
  2.     ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();  
  3.    
  4.     if (num.length < 3)  
  5.         return result;  
  6.    
  7.     // sort array  
  8.     Arrays.sort(num);  
  9.    
  10.     for (int i = 0; i < num.length - 2; i++) {  
  11.         // //avoid duplicate solutions  
  12.         if (i == 0 || num[i] > num[i - 1]) {  
  13.    
  14.             int negate = -num[i];  
  15.    
  16.             int start = i + 1;  
  17.             int end = num.length - 1;  
  18.    
  19.             while (start < end) {  
  20.                 //case 1  
  21.                 if (num[start] + num[end] == negate) {  
  22.                     ArrayList<Integer> temp = new ArrayList<Integer>();  
  23.                     temp.add(num[i]);  
  24.                     temp.add(num[start]);  
  25.                     temp.add(num[end]);  
  26.    
  27.                     result.add(temp);  
  28.                     start++;  
  29.                     end--;  
  30.                     //avoid duplicate solutions  
  31.                     while (start < end && num[end] == num[end + 1])  
  32.                         end--;  
  33.    
  34.                     while (start < end && num[start] == num[start - 1])  
  35.                         start++;  
  36.                 //case 2  
  37.                 } else if (num[start] + num[end] < negate) {  
  38.                     start++;  
  39.                 //case 3  
  40.                 } else {  
  41.                     end--;  
  42.                 }  
  43.             }  
  44.    
  45.         }  
  46.     }  
  47.    
  48.     return result;  
  49. }  

9) 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)
解法：
[java] view plaincopy
  1. public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {  
  2.     Arrays.sort(num);  
  3.    
  4.     HashSet<ArrayList<Integer>> hashSet = new HashSet<ArrayList<Integer>>();  
  5.     ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();  
  6.    
  7.     for (int i = 0; i < num.length; i++) {  
  8.         for (int j = i + 1; j < num.length; j++) {  
  9.             int k = j + 1;  
  10.             int l = num.length - 1;  
  11.    
  12.             while (k < l) {  
  13.                 int sum = num[i] + num[j] + num[k] + num[l];  
  14.    
  15.                 if (sum > target) {  
  16.                     l--;  
  17.                 } else if (sum < target) {  
  18.                     k++;  
  19.                 } else if (sum == target) {  
  20.                     ArrayList<Integer> temp = new ArrayList<Integer>();  
  21.                     temp.add(num[i]);  
  22.                     temp.add(num[j]);  
  23.                     temp.add(num[k]);  
  24.                     temp.add(num[l]);  
  25.    
  26.                     if (!hashSet.contains(temp)) {  
  27.                         hashSet.add(temp);  
  28.                         result.add(temp);  
  29.                     }  
  30.    
  31.                     k++;  
  32.                     l--;  
  33.                 }  
  34.             }  
  35.         }  
  36.     }  
  37.    
  38.     return result;  
  39. }  
Here is the hashCode method of ArrayList. It makes sure that if all elements of two lists are the same, then the hash code of the two lists will be the same. Since each element in the ArrayList is Integer, same integer has same hash code.


[java] view plaincopy
  1. int hashCode = 1;  
  2. Iterator<E> i = list.iterator();  
  3. while (i.hasNext()) {  
  4.       E obj = i.next();  
  5.       hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());  
  6. }  

10) 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).

解法：

[java] view plaincopy
  1. public class Solution {  
  2.     public int threeSumClosest(int[] num, int target) {  
  3.         int min = Integer.MAX_VALUE;  
  4.         int result = 0;  
  5.    
  6.         Arrays.sort(num);  
  7.    
  8.         for (int i = 0; i < num.length; i++) {  
  9.             int j = i + 1;  
  10.             int k = num.length - 1;  
  11.             while (j < k) {  
  12.                 int sum = num[i] + num[j] + num[k];  
  13.                 int diff = Math.abs(sum - target);  
  14.    
  15.                 if(diff == 0) return 0;  
  16.    
  17.                 if (diff < min) {  
  18.                     min = diff;  
  19.                     result = sum;  
  20.                 }  
  21.                 if (sum <= target) {  
  22.                     j++;  
  23.                 } else {  
  24.                     k--;  
  25.                 }  
  26.             }  
  27.         }  
  28.    
  29.         return result;  
  30.     }  
  31. }  

11) String to Integer

题目来源：

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Thoughts for This Problem

The vague description give us space to consider different cases.

1. null or empty string
2. white spaces
3. +/- sign
4. calculate real value
5. handle min & max
解法：
[java] view plaincopy
  1. public int atoi(String str) {  
  2.     if (str == null || str.length() < 1)  
  3.         return 0;  
  4.    
  5.     // trim white spaces  
  6.     str = str.trim();  
  7.    
  8.     char flag = '+';  
  9.    
  10.     // check negative or positive  
  11.     int i = 0;  
  12.     if (str.charAt(0) == '-') {  
  13.         flag = '-';  
  14.         i++;  
  15.     } else if (str.charAt(0) == '+') {  
  16.         i++;  
  17.     }  
  18.     // use double to store result  
  19.     double result = 0;  
  20.    
  21.     // calculate value  
  22.     while (str.length() > i && str.charAt(i) >= '0' && str.charAt(i) <= '9') {  
  23.         result = result * 10 + (str.charAt(i) - '0');  
  24.         i++;  
  25.     }  
  26.    
  27.     if (flag == '-')  
  28.         result = -result;  
  29.    
  30.     // handle max and min  
  31.     if (result > Integer.MAX_VALUE)  
  32.         return Integer.MAX_VALUE;  
  33.    
  34.     if (result < Integer.MIN_VALUE)  
  35.         return Integer.MIN_VALUE;  
  36.    
  37.     return (int) result;  
  38. }  

12) Merge Sorted Array

13) Valid Parentheses

题目来源：

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

解法1:

[java] view plaincopy
  1. public static boolean isValid(String s) {  
  2.     HashMap<Character, Character> map = new HashMap<Character, Character>();  
  3.     map.put('(', ')');  
  4.     map.put('[', ']');  
  5.     map.put('{', '}');  
  6.    
  7.     Stack<Character> stack = new Stack<Character>();  
  8.    
  9.     for (int i = 0; i < s.length(); i++) {  
  10.         char curr = s.charAt(i);  
  11.    
  12.         if (map.keySet().contains(curr)) {  
  13.             stack.push(curr);  
  14.         } else if (map.values().contains(curr)) {  
  15.             if (!stack.empty() && map.get(stack.peek()) == curr) {  
  16.                 stack.pop();  
  17.             } else {  
  18.                 return false;  
  19.             }  
  20.         }  
  21.     }  
  22.    
  23.     return stack.empty();  
  24. }  
解法2:

[java] view plaincopy
  1. public static boolean isValid(String s) {  
  2.     char[] charArray = s.toCharArray();  
  3.    
  4.     HashMap<Character, Character> map = new HashMap<Character, Character>();  
  5.     map.put('(', ')');  
  6.     map.put('[', ']');  
  7.     map.put('{', '}');  
  8.    
  9.     Stack<Character> stack = new Stack<Character>();  
  10.    
  11.     for (Character c : charArray) {  
  12.         if (map.keySet().contains(c)) {  
  13.             stack.push(c);  
  14.         } else if (map.values().contains(c)) {  
  15.             if (!stack.isEmpty() && map.get(stack.peek()) == c) {  
  16.                 stack.pop();  
  17.             } else {  
  18.                 return false;  
  19.             }  
  20.         }  
  21.     }  
  22.     return stack.isEmpty();  
  23. }  

14) Implement strStr()

题目来源：

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

思路：

First, need to understand the problem correctly, the pointer simply means a sub string.

Second, make sure the loop does not exceed the boundaries of two strings.

解法：

[java] view plaincopy
  1. public String strStr(String haystack, String needle) {  
  2.    
  3.     int needleLen = needle.length();  
  4.     int haystackLen = haystack.length();  
  5.    
  6.     if (needleLen == haystackLen && needleLen == 0)  
  7.         return "";  
  8.    
  9.     if (needleLen == 0)  
  10.         return haystack;  
  11.    
  12.     for (int i = 0; i < haystackLen; i++) {  
  13.         // make sure in boundary of needle  
  14.         if (haystackLen - i + 1 < needleLen)  
  15.             return null;  
  16.    
  17.         int k = i;  
  18.         int j = 0;  
  19.    
  20.         while (j < needleLen && k < haystackLen && needle.charAt(j) == haystack.charAt(k)) {  
  21.             j++;  
  22.             k++;  
  23.             if (j == needleLen)  
  24.                 return haystack.substring(i);  
  25.         }  
  26.    
  27.     }  
  28.    
  29.     return null;  
  30. }  

From Tia:

You have to check if a String == null before call length(), otherwise it will throw NullPointerException.



15) Set Matrix Zeroes

16) Search Insert Position 

题目来源：

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array.

Here are few examples.

[1,3,5,6], 5 -> 2
[1,3,5,6], 2 -> 1
[1,3,5,6], 7 -> 4
[1,3,5,6], 0 -> 0
解法1：
[java] view plaincopy
  1. public class Solution {  
  2.     public int searchInsert(int[] A, int target) {  
  3.    
  4.         if(A==null) return 0;  
  5.    
  6.         if(target <= A[0]) return 0;  
  7.    
  8.         for(int i=0; i<A.length-1; i++){  
  9.             if(target > A[i] && target <= A[i+1]){  
  10.                 return i+1;  
  11.             }  
  12.         }  
  13.    
  14.         return A.length;  
  15.     }  
  16. }  
解法2:
[java] view plaincopy
  1. public class Solution {  
  2.     public int searchInsert(int[] A, int target) {  
  3.         if(A==null||A.length==0)  
  4.             return 0;  
  5.    
  6.         return searchInsert(A,target,0,A.length-1);  
  7.     }  
  8.    
  9.     public int searchInsert(int[] A, int target, int start, int end){  
  10.         int mid=(start+end)/2;  
  11.    
  12.         if(target==A[mid])   
  13.             return mid;  
  14.         else if(target<A[mid])   
  15.             return start<mid?searchInsert(A,target,start,mid-1):start;  
  16.         else   
  17.             return end>mid?searchInsert(A,target,mid+1,end):(end+1);  
  18.     }  
  19. }  

17) Longest Consecutive Sequence 

问题来源：

Longest Consecutive Sequence Java

思路：

Thoughts

Because it requires O(n) complexity, we can not solve the problem by sorting the array first. Sorting takes at least O(nlogn) time.

解法: [java] view plaincopy
  1. public static int longestConsecutive(int[] num) {  
  2.     // if array is empty, return 0  
  3.     if (num.length == 0) {  
  4.         return 0;  
  5.     }  
  6.    
  7.     Set<Integer> set = new HashSet<Integer>();  
  8.     int max = 1;  
  9.    
  10.     for (int e : num)  
  11.         set.add(e);  
  12.    
  13.     for (int e : num) {  
  14.         int left = e - 1;  
  15.         int right = e + 1;  
  16.         int count = 1;  
  17.    
  18.         while (set.contains(left)) {  
  19.             count++;  
  20.             set.remove(left);  
  21.             left--;  
  22.         }  
  23.    
  24.         while (set.contains(right)) {  
  25.             count++;  
  26.             set.remove(right);  
  27.             right++;  
  28.         }  
  29.    
  30.         max = Math.max(count, max);  
  31.     }  
  32.    
  33.     return max;  
  34. }  

after an element is checked, it should be removed from the set. Otherwise, time complexity would be O(mn) in which m is the average length of all consecutive sequences.

To clearly see the time complexity, I suggest you use some simple examples and manually execute the program. For example, given an array {1,2,4,5,3}, the program time is m. m is the length of longest consecutive sequence.

We do have an extreme case here: If n is number of elements, m is average length of consecutive sequence, and m==n, then the time complexity is O(n^2). The reason is that in this case, no element is removed from the set each time. You can use this array to get the point: {1,3,5,7,9}.

18) Valid Palindrome

题目来源：

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example, "Red rum, sir, is murder" is a palindrome, while "Programcreek is awesome" is not.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

思路：

From start and end loop though the string, i.e., char array. If it is not alpha or number, increase or decrease pointers. Compare the alpha and numeric characters. The solution below is pretty straightforward.

解法1:

[java] view plaincopy
  1. public class Solution {  
  2.    
  3.     public  boolean isPalindrome(String s) {  
  4.    
  5.         if(s == null) return false;  
  6.         if(s.length() < 2) return true;  
  7.    
  8.         char[] charArray = s.toCharArray();  
  9.         int len = s.length();  
  10.    
  11.         int i=0;  
  12.         int j=len-1;  
  13.    
  14.         while(i<j){  
  15.             char left, right;  
  16.    
  17.             while(i<len-1 && !isAlpha(left) && !isNum(left)){  
  18.                 i++;  
  19.                 left =  charArray[i];  
  20.             }  
  21.    
  22.             while(j>0 && !isAlpha(right) && !isNum(right)){  
  23.                 j--;  
  24.                 right = charArray[j];  
  25.             }  
  26.    
  27.             if(i >= j)  
  28.                 break;  
  29.    
  30.             left =  charArray[i];  
  31.             right = charArray[j];  
  32.    
  33.             if(!isSame(left, right)){  
  34.                 return false;  
  35.             }  
  36.    
  37.             i++;  
  38.             j--;  
  39.         }  
  40.         return true;  
  41.     }  
  42.    
  43.     public  boolean isAlpha(char a){  
  44.         if((a >= 'a' && a <= 'z') || (a >= 'A' && a <= 'Z')){  
  45.             return true;  
  46.         }else{  
  47.             return false;  
  48.         }  
  49.     }  
  50.    
  51.     public  boolean isNum(char a){  
  52.         if(a >= '0' && a <= '9'){  
  53.             return true;  
  54.         }else{  
  55.             return false;  
  56.         }  
  57.     }  
  58.    
  59.     public  boolean isSame(char a, char b){  
  60.         if(isNum(a) && isNum(b)){  
  61.             return a == b;  
  62.         }else if(Character.toLowerCase(a) == Character.toLowerCase(b)){  
  63.             return true;  
  64.         }else{  
  65.             return false;  
  66.         }  
  67.     }  
  68. }  

解法2：

[java] view plaincopy
  1. public class Solution {  
  2.    
  3.     public  boolean isPalindrome(String s) {  
  4.    
  5.         if(s == null) return false;  
  6.         if(s.length() < 2) return true;  
  7.    
  8.         char[] charArray = s.toCharArray();  
  9.         int len = s.length();  
  10.    
  11.         int i=0;  
  12.         int j=len-1;  
  13.    
  14.         while(i<j){  
  15.             char left, right;  
  16.    
  17.             while(i<len-1 && !isAlpha(left) && !isNum(left)){  
  18.                 i++;  
  19.                 left =  charArray[i];  
  20.             }  
  21.    
  22.             while(j>0 && !isAlpha(right) && !isNum(right)){  
  23.                 j--;  
  24.                 right = charArray[j];  
  25.             }  
  26.    
  27.             if(i >= j)  
  28.                 break;  
  29.    
  30.             left =  charArray[i];  
  31.             right = charArray[j];  
  32.    
  33.             if(!isSame(left, right)){  
  34.                 return false;  
  35.             }  
  36.    
  37.             i++;  
  38.             j--;  
  39.         }  
  40.         return true;  
  41.     }  
  42.    
  43.     public  boolean isAlpha(char a){  
  44.         if((a >= 'a' && a <= 'z') || (a >= 'A' && a <= 'Z')){  
  45.             return true;  
  46.         }else{  
  47.             return false;  
  48.         }  
  49.     }  
  50.    
  51.     public  boolean isNum(char a){  
  52.         if(a >= '0' && a <= '9'){  
  53.             return true;  
  54.         }else{  
  55.             return false;  
  56.         }  
  57.     }  
  58.    
  59.     public  boolean isSame(char a, char b){  
  60.         if(isNum(a) && isNum(b)){  
  61.             return a == b;  
  62.         }else if(Character.toLowerCase(a) == Character.toLowerCase(b)){  
  63.             return true;  
  64.         }else{  
  65.             return false;  
  66.         }  
  67.     }  
  68. }  



解法3:


[java] view plaincopy
  1. public boolean isPalindrome(String s) {  
  2.     s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase();  
  3.    
  4.     int len = s.length();  
  5.     if (len < 2)  
  6.         return true;  
  7.    
  8.     Stack<Character> stack = new Stack<Character>();  
  9.    
  10.     int index = 0;  
  11.     while (index < len / 2) {  
  12.         stack.push(s.charAt(index));  
  13.         index++;  
  14.     }  
  15.    
  16.     if (len % 2 == 1)  
  17.         index++;  
  18.    
  19.     while (index < len) {  
  20.         if (stack.empty())  
  21.             return false;  
  22.    
  23.         char temp = stack.pop();  
  24.         if (s.charAt(index) != temp)  
  25.             return false;  
  26.         else  
  27.             index++;  
  28.     }  
  29.    
  30.     return true;  
  31. }  

19) Spiral Matrix

题目来源：

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example, given the following matrix:

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

You should return [1,2,3,6,9,8,7,4,5].

解法：

If more than one row and column left, it can form a circle and we process the circle. Otherwise, if only one row or column left, we process that column or row ONLY.

[java] view plaincopy
  1. public class Solution {  
  2.     public ArrayList<Integer> spiralOrder(int[][] matrix) {  
  3.         ArrayList<Integer> result = new ArrayList<Integer>();  
  4.    
  5.         if(matrix == null || matrix.length == 0) return result;  
  6.    
  7.         int m = matrix.length;  
  8.         int n = matrix[0].length;  
  9.    
  10.         int x=0;   
  11.         int y=0;  
  12.    
  13.         while(m>0 && n>0){  
  14.    
  15.             //if one row/column left, no circle can be formed  
  16.             if(m==1){  
  17.                 for(int i=0; i<n; i++){  
  18.                     result.add(matrix[x][y++]);  
  19.                 }  
  20.                 break;  
  21.             }else if(n==1){  
  22.                 for(int i=0; i<m; i++){  
  23.                     result.add(matrix[x++][y]);  
  24.                 }  
  25.                 break;  
  26.             }  
  27.    
  28.             //below, process a circle  
  29.    
  30.             //top - move right  
  31.             for(int i=0;i<n-1;i++){  
  32.                 result.add(matrix[x][y++]);  
  33.             }  
  34.    
  35.             //right - move down  
  36.             for(int i=0;i<m-1;i++){  
  37.                 result.add(matrix[x++][y]);  
  38.             }  
  39.    
  40.             //bottom - move left  
  41.             for(int i=0;i<n-1;i++){  
  42.                 result.add(matrix[x][y--]);  
  43.             }  
  44.    
  45.             //left - move up  
  46.             for(int i=0;i<m-1;i++){  
  47.                 result.add(matrix[x--][y]);  
  48.             }  
  49.    
  50.             x++;  
  51.             y++;  
  52.             m=m-2;  
  53.             n=n-2;  
  54.         }  
  55.    
  56.         return result;  
  57.     }  
  58. }  


20) Search a 2D Matrix

 题目来源：

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has properties:

1) Integers in each row are sorted from left to right. 2) The first integer of each row is greater than the last integer of the previous row.

For example, consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

解法：

This is a typical problem of binary search.

You may try to solve this problem by finding the row first and then the column. There is no need to do that. Because of the matrix's special features, the matrix can be considered as a sorted array. Your goal is to find one element in this sorted array by using binary search.

[java] view plaincopy
  1. public class Solution {  
  2.     public boolean searchMatrix(int[][] matrix, int target) {  
  3.         if(matrix==null || matrix.length==0 || matrix[0].length==0)   
  4.             return false;  
  5.    
  6.         int m = matrix.length;  
  7.         int n = matrix[0].length;  
  8.    
  9.         int start = 0;  
  10.         int end = m*n-1;  
  11.    
  12.         while(start<=end){  
  13.             int mid=(start+end)/2;  
  14.             int midX=mid/n;  
  15.             int midY=mid%n;  
  16.    
  17.             if(matrix[midX][midY]==target)   
  18.                 return true;  
  19.    
  20.             if(matrix[midX][midY]<target){  
  21.                 start=mid+1;  
  22.             }else{  
  23.                 end=mid-1;  
  24.             }  
  25.         }  
  26.    
  27.         return false;  
  28.     }  
  29. }  

21) Rotate Image

题目来源：

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has properties:

1) Integers in each row are sorted from left to right. 2) The first integer of each row is greater than the last integer of the previous row.

For example, consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

[java] view plaincopy
  1. public class Solution {  
  2.     public boolean searchMatrix(int[][] matrix, int target) {  
  3.         if(matrix==null || matrix.length==0 || matrix[0].length==0)   
  4.             return false;  
  5.    
  6.         int m = matrix.length;  
  7.         int n = matrix[0].length;  
  8.    
  9.         int start = 0;  
  10.         int end = m*n-1;  
  11.    
  12.         while(start<=end){  
  13.             int mid=(start+end)/2;  
  14.             int midX=mid/n;  
  15.             int midY=mid%n;  
  16.    
  17.             if(matrix[midX][midY]==target)   
  18.                 return true;  
  19.    
  20.             if(matrix[midX][midY]<target){  
  21.                 start=mid+1;  
  22.             }else{  
  23.                 end=mid-1;  
  24.             }  
  25.         }  
  26.    
  27.         return false;  
  28.     }  
  29. }  

22) Triangle

23) Distinct Subsequences Total

24) 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.

解法:

[java] view plaincopy
  1. public int maxSubArray(int[] A) {  
  2.       int newsum=A[0];  
  3.       int max=A[0];  
  4.       for(int i=1;i<A.length;i++){  
  5.           newsum=Math.max(newsum+A[i],A[i]);  
  6.           max= Math.max(max, newsum);  
  7.       }  
  8.       return max;  
  9.    }  


25) 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].

解法: [java] view plaincopy
  1. // Create an array with all unique elements  
  2. public static int[] removeDuplicates(int[] A) {  
  3.     if (A.length < 2)  
  4.         return A;  
  5.    
  6.     int j = 0;  
  7.     int i = 1;  
  8.    
  9.     while (i < A.length) {  
  10.         if (A[i] == A[j]) {  
  11.             i++;  
  12.         } else {  
  13.             j++;  
  14.             A[j] = A[i];  
  15.             i++;  
  16.         }  
  17.     }  
  18.    
  19.     int[] B = Arrays.copyOf(A, j + 1);  
  20.    
  21.     return B;  
  22. }  
  23.    
  24. public static void main(String[] args) {  
  25.     int[] arr = { 1, 2, 2, 3, 3 };  
  26.     arr = removeDuplicates(arr);  
  27.     System.out.println(arr.length);  
  28. }  


26) Remove Duplicates from Sorted Array II

题目来源：

Follow up for "Remove Duplicates": What if duplicates are allowed at most twice?

For example, given sorted array A = [1,1,1,2,2,3], your function should return length = 5, and A is now [1,1,2,2,3].

解法：

[java] view plaincopy
  1. public class Solution {  
  2.     public int removeDuplicates(int[] A) {  
  3.         if (A.length <= 2)  
  4.             return A.length;  
  5.    
  6.         int prev = 1; // point to previous  
  7.         int curr = 2; // point to current  
  8.    
  9.         while (curr < A.length) {  
  10.             if (A[curr] == A[prev] && A[curr] == A[prev - 1]) {  
  11.                 curr++;  
  12.             } else {  
  13.                 prev++;  
  14.                 A[prev] = A[curr];  
  15.                 curr++;  
  16.             }  
  17.         }  
  18.    
  19.         return prev + 1;  
  20.     }  
  21. }  


27) Longest Substring Without Repeating Characters

题目来源：
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

解法1：

The first solution is like the problem of "determine if a string has all unique characters" in CC 150. We can use a flag array to track the existing characters for the longest substring without repeating characters.

[java] view plaincopy
  1. public int lengthOfLongestSubstring(String s) {  
  2.     boolean[] flag = new boolean[256];  
  3.    
  4.     int result = 0;  
  5.     int start = 0;  
  6.     char[] arr = s.toCharArray();  
  7.    
  8.     for (int i = 0; i < arr.length; i++) {  
  9.         char current = arr[i];  
  10.         if (flag[current]) {  
  11.             result = Math.max(result, i - start);  
  12.             // the loop update the new start point  
  13.             // and reset flag array  
  14.             // for example, abccab, when it comes to 2nd c,  
  15.             // it update start from 0 to 3, reset flag for a,b  
  16.             for (int k = start; k < i; k++) {  
  17.                 if (arr[k] == current) {  
  18.                     start = k + 1;   
  19.                     break;  
  20.                 }  
  21.                 flag[arr[k]] = false;  
  22.             }  
  23.         } else {  
  24.             flag[current] = true;  
  25.         }  
  26.     }  
  27.    
  28.     result = Math.max(arr.length - start, result);  
  29.    
  30.     return result;  
  31. }  
解法2:

This solution is from Tia. It is easier to understand than the first solution.

The basic idea is using a hash table to track existing characters and their position. When a repeated character occurs, check from the previously repeated character. However, the time complexity is higher - O(n^3).

[java] view plaincopy
  1. public static int lengthOfLongestSubstring(String s) {  
  2.    
  3.     char[] arr = s.toCharArray();  
  4.     int pre = 0;  
  5.    
  6.     HashMap<Character, Integer> map = new HashMap<Character, Integer>();  
  7.    
  8.     for (int i = 0; i < arr.length; i++) {  
  9.         if (!map.containsKey(arr[i])) {  
  10.             map.put(arr[i], i);  
  11.         } else {  
  12.             pre = Math.max(pre, map.size());  
  13.             i = map.get(arr[i]);  
  14.             map.clear();  
  15.         }  
  16.     }  
  17.    
  18.     return Math.max(pre, map.size());  
  19. }  


28) Longest Substring that contains 2 unique characters

题目来源：

This is a problem asked by Google.

Problem

Given a string, find the longest substring that contains only two unique characters. For example, given "abcbbbbcccbdddadacb", the longest substring that contains 2 unique character is "bcbbbbcccb".

解法：

[java] view plaincopy
  1. public static String subString(String s) {  
  2.     // checking  
  3.    
  4.     char[] arr = s.toCharArray();  
  5.     int max = 0;  
  6.     int j = 0;  
  7.     int m = 0, n = 0;  
  8.    
  9.     HashSet<Character> set = new HashSet<Character>();  
  10.     set.add(arr[0]);  
  11.    
  12.     for (int i = 1; i < arr.length; i++) {  
  13.         if (set.add(arr[i])) {  
  14.             if (set.size() > 2) {  
  15.                 String str = s.substring(j, i);  
  16.    
  17.                 //keep the last character only  
  18.                 set.clear();  
  19.                 set.add(arr[i - 1]);  
  20.    
  21.                 if ((i - j) > max) {  
  22.                     m = j;  
  23.                     n = i - 1;  
  24.                     max = i - j;  
  25.                 }  
  26.    
  27.                 j = i - helper(str);  
  28.             }  
  29.         }  
  30.     }  
  31.    
  32.     return s.substring(m, n + 1);  
  33. }  
  34.    
  35. // This method returns the length that contains only one character from right side.   
  36. public static int helper(String str) {  
  37.     // null & illegal checking here  
  38.     if(str == null){  
  39.         return 0;  
  40.     }  
  41.    
  42.     if(str.length() == 1){  
  43.         return 1;  
  44.     }  
  45.    
  46.     char[] arr = str.toCharArray();  
  47.     char p = arr[arr.length - 1];  
  48.     int result = 1;  
  49.    
  50.     for (int i = arr.length - 2; i >= 0; i--) {  
  51.         if (p == arr[i]) {  
  52.             result++;  
  53.         } else {  
  54.             break;  
  55.         }  
  56.     }  
  57.    
  58.     return result;  
  59. }  


29) Palindrome Partitioning 

30) Reverse Words in a String 

题目来源：

Given an input string, reverse the string word by word.

For example, given s = "the sky is blue", return "blue is sky the".

解：
[java] view plaincopy
  1. class Solution {  
  2.     public String reverseWords(String s) {  
  3.         if (s == null || s.length() == 0) {  
  4.             return "";  
  5.         }  
  6.    
  7.         // split to words by space  
  8.         String[] arr = s.split(" ");  
  9.         StringBuilder sb = new StringBuilder();  
  10.         for (int i = arr.length - 1; i >= 0; --i) {  
  11.             if (!arr[i].equals("")) {  
  12.                 sb.append(arr[i]).append(" ");  
  13.             }  
  14.         }  
  15.         return sb.length() == 0 ? "" : sb.substring(0, sb.length() - 1);  
  16.     }  
  17. }  

31) Find Minimum in Rotated Sorted Array

32) 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.

解：
[java] view plaincopy
  1. public class Solution {  
  2.     public int findPeakElement(int[] num) {  
  3.         int max = num[0];  
  4.         int index = 0;  
  5.         for(int i=1; i<=num.length-2; i++){  
  6.             int prev = num[i-1];  
  7.             int curr = num[i];  
  8.             int next = num[i+1];  
  9.    
  10.             if(curr > prev && curr > next && curr > max){  
  11.                 index = i;  
  12.                 max = curr;  
  13.             }  
  14.         }  
  15.    
  16.         if(num[num.length-1] > max){  
  17.             return num.length-1;  
  18.         }  
  19.    
  20.         return index;  
  21.     }  
  22. }  

33) Min Stack

34) Majority Element

题目来源：

Problem:

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.

解法1:
We can sort the array first, which takes time of nlog(n). Then scan once to find the longest consecutive substrings.
 [java] view plaincopy
  1. public class Solution {  
  2.     public int majorityElement(int[] num) {  
  3.         if(num.length==1){  
  4.             return num[0];  
  5.         }  
  6.    
  7.         Arrays.sort(num);  
  8.    
  9.         int prev=num[0];  
  10.         int count=1;  
  11.         for(int i=1; i<num.length; i++){  
  12.             if(num[i] == prev){  
  13.                 count++;  
  14.                 if(count > num.length/2) return num[i];  
  15.             }else{  
  16.                 count=1;  
  17.                 prev = num[i];  
  18.             }  
  19.         }  
  20.    
  21.         return 0;  
  22.     }  
  23. }  

解法2:
Thanks to SK. His/her solution is much efficient and simpler.
Since the majority always take more than a half space, the middle element is guaranteed to be the majority. Sorting array takes nlog(n). So the time complexity of this solution is nlog(n). Cheers!
 [java] view plaincopy
  1. public int majorityElement(int[] num) {  
  2.     if (num.length == 1) {  
  3.         return num[0];  
  4.     }  
  5.    
  6.     Arrays.sort(num);  
  7.     return num[num.length / 2];  
  8. }  

35) Combination Sum (DFS)

题目来源：

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times.

Note:

All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 2,3,6,7 and target 7, 
A solution set is: 
[7] 
[2, 2, 3]
解法：

The first impression of this problem should be depth-first search(DFS). To solve DFS problem, recursion is a normal implementation.

Note that the candidates array is not sorted, we need to sort it first.

[java] view plaincopy
  1. public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {  
  2.     ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();  
  3.    
  4.     if(candidates == null || candidates.length == 0) return result;  
  5.    
  6.     ArrayList<Integer> current = new ArrayList<Integer>();  
  7.     Arrays.sort(candidates);  
  8.    
  9.     combinationSum(candidates, target, 0, current, result);  
  10.    
  11.     return result;  
  12. }  
  13.    
  14. public void combinationSum(int[] candidates, int target, int j, ArrayList<Integer> curr, ArrayList<ArrayList<Integer>> result){  
  15.    if(target == 0){  
  16.        ArrayList<Integer> temp = new ArrayList<Integer>(curr);  
  17.        result.add(temp);  
  18.        return;  
  19.    }  
  20.    
  21.    for(int i=j; i<candidates.length; i++){  
  22.        if(target < candidates[i])   
  23.             return;  
  24.    
  25.        curr.add(candidates[i]);  
  26.        combinationSum(candidates, target - candidates[i], i, curr, result);  
  27.        curr.remove(curr.size()-1);   
  28.    }  
  29. }  

36) 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.

解法1:

[java] view plaincopy
  1. public int maxProfit(int[] prices) {  
  2.     if(prices == null || prices.length < 2){  
  3.         return 0;  
  4.     }  
  5.    
  6.     int profit = Integer.MIN_VALUE;  
  7.     for(int i=0; i<prices.length-1; i++){  
  8.         for(int j=0; j< prices.length; j++){  
  9.             if(profit < prices[j] - prices[i]){  
  10.                 profit = prices[j] - prices[i];  
  11.             }  
  12.         }  
  13.     }  
  14.     return profit;  
  15. }  
解法2:

[java] view plaincopy
  1. public int maxProfit(int[] prices) {  
  2.     int profit = 0;  
  3.     int minElement = Integer.MAX_VALUE;  
  4.     for(int i=0; i<prices.length; i++){  
  5.        profit = Math.max(profit, prices[i]-minElement);  
  6.        minElement = Math.min(minElement, prices[i]);  
  7.     }  
  8.     return profit;  
  9. }  

36) Best Time to Buy and Sell Stock II

题目来源：

Say you have an array for which the ith 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).

思路：

This problem can be viewed as finding all ascending sequences. For example, given {5, 1, 2, 3, 4}, buy at 1 & sell at 4 is the same as buy at 1 &sell at 2 & buy at 2& sell at 3 & buy at 3 & sell at 4.

We can scan the array once, and find all pairs of elements that are in ascending order.

解：
[java] view plaincopy
  1. public int maxProfit(int[] prices) {  
  2.     int profit = 0;  
  3.     for(int i=1; i<prices.length; i++){  
  4.         int diff = prices[i]-prices[i-1];  
  5.         if(diff > 0){  
  6.             profit += diff;  
  7.         }  
  8.     }  
  9.     return profit;  
  10. }  

36) Best Time to Buy and Sell Stock III (DP) 


2. 链表


在Java中，链表的实现非常简单，每个节点Node都有一个值val和指向下个节点的链接next。


class Node {
int val;
Node next;

Node(int x) {
val = x;
next = null;
}
}


链表两个著名的应用是栈Stack和队列Queue。在Java标准库都都有实现，一个是Stack,另一个是LinkedList(Queue是它实现的接口)。


经典题目：

1) Add Two Numbers

2) Reorder List

题目来源：

The problem:

Given a singly linked list L: L0→L1→ ... →Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→...

For example, given {1,2,3,4}, reorder it to {1,4,2,3}. You must do this in-place without altering the nodes' values.

思路：

This problem is not straightforward, because it requires "in-place" operations. That means we can only change their pointers, not creating a new list.

This problem can be solved by doing the following:

  1. Break list in the middle to two lists (use fast & slow pointers)
  2. Reverse the order of the second list
  3. Merge two list back together
解：
[java] view plaincopy
  1. //Class definition of ListNode  
  2. class ListNode {  
  3.     int val;  
  4.     ListNode next;  
  5.    
  6.     ListNode(int x) {  
  7.         val = x;  
  8.         next = null;  
  9.     }  
  10. }  
  11.    
  12. public class ReorderList {  
  13.    
  14.     public static void main(String[] args) {  
  15.         ListNode n1 = new ListNode(1);  
  16.         ListNode n2 = new ListNode(2);  
  17.         ListNode n3 = new ListNode(3);  
  18.         ListNode n4 = new ListNode(4);  
  19.         n1.next = n2;  
  20.         n2.next = n3;  
  21.         n3.next = n4;  
  22.    
  23.         printList(n1);  
  24.    
  25.         reorderList(n1);  
  26.    
  27.         printList(n1);  
  28.     }  
  29.    
  30.     public static void reorderList(ListNode head) {  
  31.    
  32.         if (head != null && head.next != null) {  
  33.    
  34.             ListNode slow = head;  
  35.             ListNode fast = head;  
  36.    
  37.             //use a fast and slow pointer to break the link to two parts.  
  38.             while (fast != null && fast.next != null && fast.next.next!= null) {  
  39.                 //why need third/second condition?  
  40.                 System.out.println("pre "+slow.val + " " + fast.val);  
  41.                 slow = slow.next;  
  42.                 fast = fast.next.next;  
  43.                 System.out.println("after " + slow.val + " " + fast.val);  
  44.             }  
  45.    
  46.             ListNode second = slow.next;  
  47.             slow.next = null;// need to close first part  
  48.    
  49.             // now should have two lists: head and fast  
  50.    
  51.             // reverse order for second part  
  52.             second = reverseOrder(second);  
  53.    
  54.             ListNode p1 = head;  
  55.             ListNode p2 = second;  
  56.    
  57.             //merge two lists here  
  58.             while (p2 != null) {  
  59.                 ListNode temp1 = p1.next;  
  60.                 ListNode temp2 = p2.next;  
  61.    
  62.                 p1.next = p2;  
  63.                 p2.next = temp1;          
  64.    
  65.                 p1 = temp1;  
  66.                 p2 = temp2;  
  67.             }  
  68.         }  
  69.     }  
  70.    
  71.     public static ListNode reverseOrder(ListNode head) {  
  72.    
  73.         if (head == null || head.next == null) {  
  74.             return head;  
  75.         }  
  76.    
  77.         ListNode pre = head;  
  78.         ListNode curr = head.next;  
  79.    
  80.         while (curr != null) {  
  81.             ListNode temp = curr.next;  
  82.             curr.next = pre;  
  83.             pre = curr;  
  84.             curr = temp;  
  85.         }  
  86.    
  87.         // set head node's next  
  88.         head.next = null;  
  89.    
  90.         return pre;  
  91.     }  
  92.    
  93.     public static void printList(ListNode n) {  
  94.         System.out.println("------");  
  95.         while (n != null) {  
  96.             System.out.print(n.val);  
  97.             n = n.next;  
  98.         }  
  99.         System.out.println();  
  100.     }  
  101. }  


3) Linked List Cycle

题目来源：Given a linked list, determine if it has a cycle in it.

解：

The problem can be demonstrated in the following diagram:
面试10大算法汇总

Use fast and low pointer. The advantage about fast/slow pointers is that when a circle is located, the fast one will catch the slow one for sure.

[java] view plaincopy
  1. public class Solution {  
  2.     public boolean hasCycle(ListNode head) {  
  3.         ListNode fast = head;  
  4.         ListNode slow = head;  
  5.    
  6.         if(head == null)  
  7.             return false;  
  8.    
  9.         if(head.next == null)  
  10.             return false;  
  11.    
  12.         while(fast != null && fast.next != null){  
  13.             slow = slow.next;  
  14.             fast = fast.next.next;  
  15.    
  16.             if(slow == fast)  
  17.                 return true;  
  18.         }  
  19.    
  20.         return false;  
  21.     }  
  22. }  


4) Copy List with Random Pointer

5) Merge Two Sorted Lists

题目来源：
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

解：

Key to solve this problem

The key to solve the problem is defining a fake head. Then compare the first elements from each list. Add the smaller one to the merged list. Finally, when one of them is empty, simply append it to the merged list, since it is already sorted.

[java] view plaincopy
  1. /** 
  2.  * Definition for singly-linked list. 
  3.  * public class ListNode { 
  4.  *     int val; 
  5.  *     ListNode next; 
  6.  *     ListNode(int x) { 
  7.  *         val = x; 
  8.  *         next = null; 
  9.  *     } 
  10.  * } 
  11.  */  
  12. public class Solution {  
  13.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {  
  14.    
  15.         ListNode p1 = l1;  
  16.         ListNode p2 = l2;  
  17.    
  18.         ListNode fakeHead = new ListNode(0);  
  19.         ListNode p = fakeHead;  
  20.    
  21.         while(p1 != null && p2 != null){  
  22.           if(p1.val <= p2.val){  
  23.               p.next = p1;  
  24.               p1 = p1.next;  
  25.           }else{  
  26.               p.next = p2;  
  27.               p2 = p2.next;  
  28.           }  
  29.    
  30.           p = p.next;  
  31.         }  
  32.    
  33.         if(p1 != null)  
  34.             p.next = p1;  
  35.         if(p2 != null)  
  36.             p.next = p2;  
  37.    
  38.         return fakeHead.next;  
  39.     }  
  40. }  

6) Merge k Sorted Lists *

题目来源：
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

解：

The simplest solution is using PriorityQueue. The elements of the priority queue are ordered according to their natural ordering, or by a comparator provided at the construction time (in this case).

[java] view plaincopy
  1. import java.util.ArrayList;  
  2. import java.util.Comparator;  
  3. import java.util.PriorityQueue;  
  4.    
  5. //  Definition for singly-linked list.  
  6. class ListNode {  
  7.     int val;  
  8.     ListNode next;  
  9.    
  10.     ListNode(int x) {  
  11.         val = x;  
  12.         next = null;  
  13.     }  
  14. }  
  15.    
  16. public class Solution {  
  17.     public ListNode mergeKLists(ArrayList<ListNode> lists) {  
  18.         if (lists.size() == 0)  
  19.             return null;  
  20.    
  21.         //PriorityQueue is a sorted queue  
  22.         PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(lists.size(),  
  23.                 new Comparator<ListNode>() {  
  24.                     public int compare(ListNode a, ListNode b) {  
  25.                         if (a.val > b.val)  
  26.                             return 1;  
  27.                         else if(a.val == b.val)  
  28.                             return 0;  
  29.                         else   
  30.                             return -1;  
  31.                     }  
  32.                 });  
  33.    
  34.         //add first node of each list to the queue  
  35.         for (ListNode list : lists) {  
  36.             if (list != null)  
  37.                 q.add(list);  
  38.         }  
  39.    
  40.         ListNode head = new ListNode(0);  
  41.         ListNode p = head; // serve as a pointer/cursor  
  42.    
  43.         while (q.size() > 0) {  
  44.             ListNode temp = q.poll();  
  45.             //poll() retrieves and removes the head of the queue - q.   
  46.             p.next = temp;  
  47.    
  48.             //keep adding next element of each list  
  49.             if (temp.next != null)  
  50.                 q.add(temp.next);  
  51.    
  52.             p = p.next;  
  53.         }  
  54.    
  55.         return head.next;  
  56.     }  
  57. }  


7) Remove Duplicates from Sorted List

题目来源：

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,

Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
解法1:
[java] view plaincopy
  1. /** 
  2.  * Definition for singly-linked list. 
  3.  * public class ListNode { 
  4.  *     int val; 
  5.  *     ListNode next; 
  6.  *     ListNode(int x) { 
  7.  *         val = x; 
  8.  *         next = null; 
  9.  *     } 
  10.  * } 
  11.  */  
  12. public class Solution {  
  13.     public ListNode deleteDuplicates(ListNode head) {  
  14.         if(head == null || head.next == null)  
  15.             return head;  
  16.    
  17.         ListNode prev = head;      
  18.         ListNode p = head.next;  
  19.    
  20.         while(p != null){  
  21.             if(p.val == prev.val){  
  22.                 prev.next = p.next;  
  23.                 p = p.next;  
  24.                 //no change prev  
  25.             }else{  
  26.                 prev = p;  
  27.                 p = p.next;   
  28.             }  
  29.         }  
  30.    
  31.         return head;  
  32.     }  
  33. }  

解法2:


[java] view plaincopy
  1. public class Solution {  
  2.     public ListNode deleteDuplicates(ListNode head) {  
  3.         if(head == null || head.next == null)  
  4.             return head;  
  5.    
  6.         ListNode p = head;  
  7.    
  8.         while( p!= null && p.next != null){  
  9.             if(p.val == p.next.val){  
  10.                 p.next = p.next.next;  
  11.             }else{  
  12.                 p = p.next;   
  13.             }  
  14.         }  
  15.    
  16.         return head;  
  17.     }  
  18. }  

8) 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.

解：
[java] view plaincopy
  1. public class Solution {  
  2.     public ListNode partition(ListNode head, int x) {  
  3.         if(head == null) return null;  
  4.    
  5.         ListNode fakeHead1 = new ListNode(0);  
  6.         ListNode fakeHead2 = new ListNode(0);  
  7.         fakeHead1.next = head;  
  8.    
  9.         ListNode p = head;  
  10.         ListNode prev = fakeHead1;  
  11.         ListNode p2 = fakeHead2;  
  12.    
  13.         while(p != null){  
  14.             if(p.val < x){  
  15.                 p = p.next;  
  16.                 prev = prev.next;  
  17.             }else{  
  18.    
  19.                 p2.next = p;  
  20.                 prev.next = p.next;  
  21.    
  22.                 p = prev.next;  
  23.                 p2 = p2.next;  
  24.             }   
  25.         }  
  26.    
  27.         // close the list  
  28.         p2.next = null;  
  29.    
  30.         prev.next = fakeHead2.next;  
  31.    
  32.         return fakeHead1.next;  
  33.     }  
  34. }  


3. 树


这里的树通常是指二叉树，每个节点都包含一个左孩子节点和右孩子节点，像下面这样：


class TreeNode{
int value;
TreeNode left;
TreeNode right;
}


下面是与树相关的一些概念：

二叉搜索树：左结点 <= 中结点 <= 右结点

平衡 vs. 非平衡：平衡二叉树中，每个节点的左右子树的深度相差至多为1（1或0）。

满二叉树（Full Binary Tree）：除叶子节点以为的每个节点都有两个孩子。

完美二叉树（Perfect Binary Tree）：是具有下列性质的满二叉树：所有的叶子节点都有相同的深度或处在同一层次，且每个父节点都必须有两个孩子。

完全二叉树（Complete Binary Tree）：二叉树中，可能除了最后一个，每一层都被完全填满，且所有节点都必须尽可能想左靠。


经典题目：

1) Binary Tree Preorder Traversal

题目来源：

Preorder binary tree traversal is a classic interview problem about trees. The key to solve this problem is to understand the following:

  1. What is preorder? (parent node is processed before its children)
  2. Use Stack from Java Core library

It is not obvious what preorder for some strange cases. However, if you draw a stack and manually execute the program, how each element is pushed and popped is obvious.

The key to solve this problem is using a stack to store left and right children, and push right child first so that it is processed after the left child.

解：
[java] view plaincopy
  1. public class TreeNode {  
  2.     int val;  
  3.     TreeNode left;  
  4.     TreeNode right;  
  5.     TreeNode(int x) { val = x; }  
  6. }  
  7.    
  8. public class Solution {  
  9.     public ArrayList<Integer> preorderTraversal(TreeNode root) {  
  10.         ArrayList<Integer> returnList = new ArrayList<Integer>();  
  11.    
  12.         if(root == null)  
  13.             return returnList;  
  14.    
  15.         Stack<TreeNode> stack = new Stack<TreeNode>();  
  16.         stack.push(root);  
  17.    
  18.         while(!stack.empty()){  
  19.             TreeNode n = stack.pop();  
  20.             returnList.add(n.val);  
  21.    
  22.             if(n.right != null){  
  23.                 stack.push(n.right);  
  24.             }  
  25.             if(n.left != null){  
  26.                 stack.push(n.left);  
  27.             }  
  28.    
  29.         }  
  30.         return returnList;  
  31.     }  
  32. }  

2) Binary Tree Inorder Traversal

题目来源：

The key to solve inorder traversal of binary tree includes the following:

  1. The order of "inorder" is: left child -> parent -> right child
  2. Use a stack to track nodes
  3. Understand when to push node into the stack and when to pop node out of the stack

面试10大算法汇总

解：
[java] view plaincopy
  1. public class TreeNode {  
  2.      int val;  
  3.      TreeNode left;  
  4.      TreeNode right;  
  5.      TreeNode(int x) { val = x; }  
  6.  }  
  7.    
  8. public class Solution {  
  9.     public ArrayList<Integer> inorderTraversal(TreeNode root) {  
  10.         // IMPORTANT: Please reset any member data you declared, as  
  11.         // the same Solution instance will be reused for each test case.  
  12.          ArrayList<Integer> lst = new ArrayList<Integer>();  
  13.    
  14.         if(root == null)  
  15.             return lst;   
  16.    
  17.         Stack<TreeNode> stack = new Stack<TreeNode>();  
  18.         //define a pointer to track nodes  
  19.         TreeNode p = root;  
  20.    
  21.         while(!stack.empty() || p != null){  
  22.    
  23.             // if it is not null, push to stack  
  24.             //and go down the tree to left  
  25.             if(p != null){  
  26.                 stack.push(p);  
  27.                 p = p.left;  
  28.    
  29.             // if no left child  
  30.             // pop stack, process the node  
  31.             // then let p point to the right  
  32.             }else{  
  33.                 TreeNode t = stack.pop();  
  34.                 lst.add(t.val);  
  35.                 p = t.right;  
  36.             }  
  37.         }  
  38.    
  39.         return lst;  
  40.     }  
  41. }  

3) Binary Tree Postorder Traversal 

题目来源：

The key to to iterative postorder traversal is the following:

  1. The order of "Postorder" is: left child -> right child -> parent node.
  2. Find the relation between the previously visited node and the current node
  3. Use a stack to track nodes

As we go down the tree, check the previously visited node. If it is the parent of the current node, we should add current node to stack. When there is no children for current node, pop it from stack. Then the previous node become to be under the current node for next loop.

解：
[java] view plaincopy
  1. public class TreeNode {  
  2.     int val;  
  3.     TreeNode left;  
  4.     TreeNode right;  
  5.     TreeNode(int x) { val = x; }  
  6. }  
  7.    
  8.    
  9. public class Solution {  
  10.     public ArrayList<Integer> postorderTraversal(TreeNode root) {  
  11.    
  12.         ArrayList<Integer> lst = new ArrayList<Integer>();  
  13.    
  14.         if(root == null)  
  15.             return lst;   
  16.    
  17.         Stack<TreeNode> stack = new Stack<TreeNode>();  
  18.         stack.push(root);  
  19.    
  20.         TreeNode prev = null;  
  21.         while(!stack.empty()){  
  22.             TreeNode curr = stack.peek();  
  23.    
  24.             // go down the tree.  
  25.             //check if current node is leaf, if so, process it and pop stack,  
  26.             //otherwise, keep going down  
  27.             if(prev == null || prev.left == curr || prev.right == curr){  
  28.                 //prev == null is the situation for the root node  
  29.                 if(curr.left != null){  
  30.                     stack.push(curr.left);  
  31.                 }else if(curr.right != null){  
  32.                     stack.push(curr.right);  
  33.                 }else{  
  34.                     stack.pop();  
  35.                     lst.add(curr.val);  
  36.                 }  
  37.    
  38.             //go up the tree from left node      
  39.             //need to check if there is a right child  
  40.             //if yes, push it to stack  
  41.             //otherwise, process parent and pop stack  
  42.             }else if(curr.left == prev){  
  43.                 if(curr.right != null){  
  44.                     stack.push(curr.right);  
  45.                 }else{  
  46.                     stack.pop();  
  47.                     lst.add(curr.val);  
  48.                 }  
  49.    
  50.             //go up the tree from right node   
  51.             //after coming back from right node, process parent node and pop stack.   
  52.             }else if(curr.right == prev){  
  53.                 stack.pop();  
  54.                 lst.add(curr.val);  
  55.             }  
  56.    
  57.             prev = curr;  
  58.         }  
  59.    
  60.         return lst;  
  61.     }  
  62. }  

4) Word Ladder 

题目来源：

The problem:

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, 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", the program should 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.

This problem is a classic problem that has been asked frequently during interviews. The following are two Java solutions.

解：

So we quickly realize that this looks like a tree searching problem for which breath first guarantees the optimal solution.

Assuming we have some words in the dictionary, and the start is "hit" as shown in the diagram below.

面试10大算法汇总

[java] view plaincopy
  1. public int ladderLength(String start, String end, HashSet<String> dict) {  
  2.     if (dict.size() == 0)  
  3.         return 0;  
  4.    
  5.     dict.add(end);  
  6.    
  7.     LinkedList<String> wordQueue = new LinkedList<String>();  
  8.     LinkedList<Integer> distanceQueue = new LinkedList<Integer>();  
  9.    
  10.     wordQueue.add(start);  
  11.     distanceQueue.add(1);  
  12.    
  13.     //track the shortest path  
  14.     int result = Integer.MAX_VALUE;  
  15.     while (!wordQueue.isEmpty()) {  
  16.         String currWord = wordQueue.pop();  
  17.         Integer currDistance = distanceQueue.pop();  
  18.    
  19.         if (currWord.equals(end)) {  
  20.             result = Math.min(result, currDistance);  
  21.         }  
  22.    
  23.         for (int i = 0; i < currWord.length(); i++) {  
  24.             char[] currCharArr = currWord.toCharArray();  
  25.             for (char c = 'a'; c <= 'z'; c++) {  
  26.                 currCharArr[i] = c;  
  27.    
  28.                 String newWord = new String(currCharArr);  
  29.                 if (dict.contains(newWord)) {  
  30.                     wordQueue.add(newWord);  
  31.                     distanceQueue.add(currDistance + 1);  
  32.                     dict.remove(newWord);  
  33.                 }  
  34.             }  
  35.         }  
  36.     }  
  37.    
  38.     if (result < Integer.MAX_VALUE)  
  39.         return result;  
  40.     else  
  41.         return 0;  
  42. }  

5) Validate Binary Search Tree

题目来源：

Given a binary tree, determine if it is a valid binary search tree (BST).

解：
All values on the left sub tree must be less than root, and all values on the right sub tree must be greater than root.


[java] view plaincopy
  1. //  Definition for binary tree  
  2. class TreeNode {  
  3.     int val;  
  4.     TreeNode left;  
  5.     TreeNode right;  
  6.    
  7.     TreeNode(int x) {  
  8.         val = x;  
  9.     }  
  10. }  
  11.    
  12. public class Solution {  
  13.    
  14.     public static boolean isValidBST(TreeNode root) {  
  15.         return validate(root, Integer.MIN_VALUE, Integer.MAX_VALUE);  
  16.     }  
  17.    
  18.     public static boolean validate(TreeNode root, int min, int max) {  
  19.         if (root == null) {  
  20.             return true;  
  21.         }  
  22.    
  23.         // not in range  
  24.         if (root.val <= min || root.val >= max) {  
  25.             return false;  
  26.         }  
  27.    
  28.         // left subtree must be < root.val && right subtree must be > root.val  
  29.         return validate(root.left, min, root.val) && validate(root.right, root.val, max);  
  30.     }  
  31. }  

6) Flatten Binary Tree to Linked List

题目来源：

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

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6
解：
Go down through the left, when right is not null, push right to stack.

[java] view plaincopy
  1. /** 
  2.  * Definition for binary tree 
  3.  * public class TreeNode { 
  4.  *     int val; 
  5.  *     TreeNode left; 
  6.  *     TreeNode right; 
  7.  *     TreeNode(int x) { val = x; } 
  8.  * } 
  9.  */  
  10. public class Solution {  
  11.     public void flatten(TreeNode root) {  
  12.         Stack<TreeNode> stack = new Stack<TreeNode>();  
  13.         TreeNode p = root;  
  14.    
  15.         while(p != null || !stack.empty()){  
  16.    
  17.             if(p.right != null){  
  18.                 stack.push(p.right);  
  19.             }  
  20.    
  21.             if(p.left != null){  
  22.                 p.right = p.left;  
  23.                 p.left = null;  
  24.             }else if(!stack.empty()){  
  25.                 TreeNode temp = stack.pop();  
  26.                 p.right=temp;  
  27.             }  
  28.    
  29.             p = p.right;  
  30.         }  
  31.     }  
  32. }  

7) Path Sum

题目来源：

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.

解法1:

Add all node to a queue and store sum value of each node to another queue. When it is a leaf node, check the stored sum value.

For the tree above, the queue would be: 5 - 4 - 8 - 11 - 13 - 4 - 7 - 2 - 1. It will check node 13, 7, 2 and 1. This is a typical breadth first search(BFS) problem.

[java] view plaincopy
  1. /** 
  2.  * Definition for binary tree 
  3.  * public class TreeNode { 
  4.  *     int val; 
  5.  *     TreeNode left; 
  6.  *     TreeNode right; 
  7.  *     TreeNode(int x) { val = x; } 
  8.  * } 
  9.  */  
  10. public class Solution {  
  11.     public boolean hasPathSum(TreeNode root, int sum) {  
  12.         if(root == null) return false;  
  13.    
  14.         LinkedList<TreeNode> nodes = new LinkedList<TreeNode>();  
  15.         LinkedList<Integer> values = new LinkedList<Integer>();  
  16.    
  17.         nodes.add(root);  
  18.         values.add(root.val);  
  19.    
  20.         while(!nodes.isEmpty()){  
  21.             TreeNode curr = nodes.poll();  
  22.             int sumValue = values.poll();  
  23.    
  24.             if(curr.left == null && curr.right == null && sumValue==sum){  
  25.                 return true;  
  26.             }  
  27.    
  28.             if(curr.left != null){  
  29.                 nodes.add(curr.left);  
  30.                 values.add(sumValue+curr.left.val);  
  31.             }  
  32.    
  33.             if(curr.right != null){  
  34.                 nodes.add(curr.right);  
  35.                 values.add(sumValue+curr.right.val);  
  36.             }  
  37.         }  
  38.    
  39.         return false;  
  40.     }  
  41. }  

解法2:
Java Solution 2 - Recursion

[java] view plaincopy
  1. public boolean hasPathSum(TreeNode root, int sum) {  
  2.     if (root == null)  
  3.         return false;  
  4.     if (root.val == sum && (root.left == null && root.right == null))  
  5.         return true;  
  6.    
  7.     return hasPathSum(root.left, sum - root.val)  
  8.             || hasPathSum(root.right, sum - root.val);  
  9. }  

8) Construct Binary Tree from Inorder and Postorder Traversal

题目来源：

Given inorder and postorder traversal of a tree, construct the binary tree.

Throughts

This problem can be illustrated by using a simple example.

in-order:   4 2 5  (1)  6 7 3 8
post-order: 4 5 2  6 7 8 3  (1)

From the post-order array, we know that last element is the root. We can find the root in in-order array. Then we can identify the left and right sub-trees of the root from in-order array.

Using the length of left sub-tree, we can identify left and right sub-trees in post-order array. Recursively, we can build up the tree.

解：
[java] view plaincopy
  1. //Definition for binary tree  
  2.  public class TreeNode {  
  3.      int val;  
  4.      TreeNode left;  
  5.      TreeNode right;  
  6.      TreeNode(int x) { val = x; }  
  7.  }  
  8.    
  9. public class Solution {  
  10.     public TreeNode buildTree(int[] inorder, int[] postorder) {  
  11.         int inStart = 0;  
  12.         int inEnd = inorder.length-1;  
  13.         int postStart =0;  
  14.         int postEnd = postorder.length-1;  
  15.    
  16.         return buildTree(inorder, inStart, inEnd, postorder, postStart, postEnd);  
  17.     }  
  18.    
  19.     public TreeNode buildTree(int[] inorder, int inStart, int inEnd,   
  20.                             int[] postorder, int postStart, int postEnd){  
  21.         if(inStart > inEnd || postStart > postEnd)  
  22.             return null;  
  23.    
  24.         int rootValue = postorder[postEnd];  
  25.         TreeNode root = new TreeNode(rootValue);  
  26.    
  27.         int k=0;  
  28.         for(int i=0; i< inorder.length; i++){  
  29.             if(inorder[i]==rootValue){  
  30.                 k = i;  
  31.                 break;  
  32.             }  
  33.         }  
  34.    
  35.         root.left = buildTree(inorder, inStart, k-1, postorder, postStart, postStart+k-(inStart+1));  
  36.         // Becuase k is not the length, it it need to -(inStart+1) to get the length  
  37.         root.right = buildTree(inorder, k+1, inEnd, postorder, postStart+k-inStart, postEnd-1);  
  38.         // postStart+k-inStart = postStart+k-(inStart+1) +1  
  39.    
  40.         return root;  
  41.     }  
  42. }  

9) Convert Sorted Array to Binary Search Tree

题目来源：
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

解：

[java] view plaincopy
  1. // Definition for binary tree  
  2. class TreeNode {  
  3.     int val;  
  4.     TreeNode left;  
  5.     TreeNode right;  
  6.    
  7.     TreeNode(int x) {  
  8.         val = x;  
  9.     }  
  10. }  
  11.    
  12. public class Solution {  
  13.     public TreeNode sortedArrayToBST(int[] num) {  
  14.         if (num.length == 0)  
  15.             return null;  
  16.    
  17.         return sortedArrayToBST(num, 0, num.length - 1);  
  18.     }  
  19.    
  20.     public TreeNode sortedArrayToBST(int[] num, int start, int end) {  
  21.         if (start > end)  
  22.             return null;  
  23.    
  24.         int mid = (start + end) / 2;  
  25.         TreeNode root = new TreeNode(num[mid]);  
  26.         root.left = sortedArrayToBST(num, start, mid - 1);  
  27.         root.right = sortedArrayToBST(num, mid + 1, end);  
  28.    
  29.         return root;  
  30.     }  
  31. }  

10) Convert Sorted List to Binary Search Tree

11) Minimum Depth of Binary Tree

题目来源：

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

解：
Need to know LinkedList is a queue. add() and remove() are the two methods to manipulate the queue.

[java] view plaincopy
  1. /** 
  2.  * Definition for binary tree 
  3.  * public class TreeNode { 
  4.  *     int val; 
  5.  *     TreeNode left; 
  6.  *     TreeNode right; 
  7.  *     TreeNode(int x) { val = x; } 
  8.  * } 
  9.  */  
  10. public class Solution {  
  11.     public int minDepth(TreeNode root) {  
  12.         if(root == null){  
  13.             return 0;  
  14.         }  
  15.    
  16.         LinkedList<TreeNode> nodes = new LinkedList<TreeNode>();  
  17.         LinkedList<Integer> counts = new LinkedList<Integer>();  
  18.    
  19.         nodes.add(root);  
  20.         counts.add(1);  
  21.    
  22.         while(!nodes.isEmpty()){  
  23.             TreeNode curr = nodes.remove();  
  24.             int count = counts.remove();  
  25.    
  26.             if(curr.left != null){  
  27.                 nodes.add(curr.left);  
  28.                 counts.add(count+1);  
  29.             }  
  30.    
  31.             if(curr.right != null){  
  32.                 nodes.add(curr.right);  
  33.                 counts.add(count+1);  
  34.             }  
  35.    
  36.             if(curr.left == null && curr.right == null){  
  37.                 return count;  
  38.             }  
  39.         }  
  40.    
  41.         return 0;  
  42.     }  
  43. }  


12) Binary Tree Maximum Path Sum *

题目来源：

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

解：

1) Recursively solve this problem
2) Get largest left sum and right sum
2) Compare to the stored maximum

[java] view plaincopy
  1. // Definition for binary tree  
  2. class TreeNode {  
  3.     int val;  
  4.     TreeNode left;  
  5.     TreeNode right;  
  6.    
  7.     TreeNode(int x) {  
  8.         val = x;  
  9.     }  
  10. }  
  11.    
  12. public class Solution {  
  13.     //store max value  
  14.     int max;   
  15.    
  16.     public int maxPathSum(TreeNode root) {  
  17.         max = (root == null) ? 0 : root.val;  
  18.         findMax(root);  
  19.         return max;  
  20.     }  
  21.    
  22.     public int findMax(TreeNode node) {  
  23.         if (node == null)  
  24.             return 0;  
  25.    
  26.         // recursively get sum of left and right path  
  27.         int left = Math.max(findMax(node.left), 0);  
  28.         int right = Math.max(findMax(node.right), 0);  
  29.    
  30.         //update maximum here  
  31.         max = Math.max(node.val + left + right, max);  
  32.    
  33.         // return sum of largest path of current node  
  34.         return node.val + Math.max(left, right);  
  35.     }  
  36. }  

13) Balanced Binary Tree

题目来源：

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

解：

[java] view plaincopy
  1. // Definition for binary tree  
  2. class TreeNode {  
  3.     int val;  
  4.     TreeNode left;  
  5.     TreeNode right;  
  6.    
  7.     TreeNode(int x) {  
  8.         val = x;  
  9.     }  
  10. }  
  11.    
  12. public class Solution {  
  13.     public boolean isBalanced(TreeNode root) {  
  14.         if (root == null)  
  15.             return true;  
  16.    
  17.         if (getHeight(root) == -1)  
  18.             return false;  
  19.    
  20.         return true;  
  21.     }  
  22.    
  23.     public int getHeight(TreeNode root) {  
  24.         if (root == null)  
  25.             return 0;  
  26.    
  27.         int left = getHeight(root.left);  
  28.         int right = getHeight(root.right);  
  29.    
  30.         if (left == -1 || right == -1)  
  31.             return -1;  
  32.    
  33.         if (Math.abs(left - right) > 1) {  
  34.             return -1;  
  35.         }  
  36.    
  37.         return Math.max(left, right) + 1;  
  38.    
  39.     }  
  40. }  


4. 图


图相关的问题主要集中在深度优先搜索（depth first search）和广度优先搜索（breath first search）。深度优先搜索很简单，广度优先要注意使用queue. 下面是一个简单的用队列Queue实现广度优先搜索。

public class GraphTest {
public static void breathFirstSearch(GraphNode root, int x){
if(root.val == x)
System.out.println("find in root");

Queue queue = new Queue();
root.visited = true;
queue.enqueue(root);

while(queue.first != null){
GraphNode c = (GraphNode) queue.dequeue();
for(GraphNode n: c.neighbors){

if(!n.visited){
System.out.print(n + " ");
n.visited = true;
if(n.val == x)
System.out.println("Find "+n);
queue.enqueue(n);
}
}
}
}
}


经典题目：

复制图(Clone Graph)

题目来源：

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

面试10大算法汇总

Key to Solve This Problem

  • A queue is used to do breath first traversal.
  • a map is used to store the visited nodes. It is the map between original node and copied node.

It would be helpful if you draw a diagram and visualize the problem.

面试10大算法汇总

解：
[java] view plaincopy
  1. /** 
  2.  * Definition for undirected graph. 
  3.  * class UndirectedGraphNode { 
  4.  *     int label; 
  5.  *     ArrayList<UndirectedGraphNode> neighbors; 
  6.  *     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } 
  7.  * }; 
  8.  */  
  9. public class Solution {  
  10.     public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {  
  11.         if(node == null)  
  12.             return null;  
  13.    
  14.         LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();  
  15.         HashMap<UndirectedGraphNode, UndirectedGraphNode> map =   
  16.                                    new HashMap<UndirectedGraphNode,UndirectedGraphNode>();  
  17.    
  18.         UndirectedGraphNode newHead = new UndirectedGraphNode(node.label);  
  19.    
  20.         queue.add(node);  
  21.         map.put(node, newHead);  
  22.    
  23.         while(!queue.isEmpty()){  
  24.             UndirectedGraphNode curr = queue.pop();  
  25.             ArrayList<UndirectedGraphNode> currNeighbors = curr.neighbors;   
  26.    
  27.             for(UndirectedGraphNode aNeighbor: currNeighbors){  
  28.                 if(!map.containsKey(aNeighbor)){  
  29.                     UndirectedGraphNode copy = new UndirectedGraphNode(aNeighbor.label);  
  30.                     map.put(aNeighbor,copy);  
  31.                     map.get(curr).neighbors.add(copy);  
  32.                     queue.add(aNeighbor);  
  33.                 }else{  
  34.                     map.get(curr).neighbors.add(map.get(aNeighbor));  
  35.                 }  
  36.             }  
  37.    
  38.         }  
  39.         return newHead;  
  40.     }  
  41. }  

5. 排序


下面是不同排序算法的时间复杂度，你可以去wiki看一下这些算法的基本思想。

Algorithm Average Time Worst Time Space
冒泡排序(Bubble sort) n^2 n^2 1
选择排序(Selection sort) n^2 n^2 1
插入排序(Insertion sort) n^2 n^2  
快速排序(Quick sort) n log(n) n^2  
归并排序(Merge sort) n log(n) n log(n) depends

* 另外还有BinSort, RadixSort和CountSort 三种比较特殊的排序。

 经典题目： Mergesort, Quicksort, InsertionSort. 

快速排序：

Quicksort is a divide and conquer algorithm. It first divides a large list into two smaller sub-lists and then recursively sort the two sub-lists. If we want to sort an array without any extra space, Quicksort is a good option. On average, time complexity is O(n log(n)).

The basic step of sorting an array are as follows:

  1. Select a pivot, normally the middle one
  2. From both ends, swap elements and make all elements on the left less than the pivot and all elements on the right greater than the pivot
  3. Recursively sort left part and right part
解：
[java] view plaincopy
  1. package algorithm.sort;  
  2.    
  3. public class QuickSort {  
  4.    
  5.     public static void main(String[] args) {  
  6.         int[] x = { 9, 2, 4, 7, 3, 7, 10 };  
  7.         printArray(x);  
  8.    
  9.         int low = 0;  
  10.         int high = x.length - 1;  
  11.    
  12.         quickSort(x, low, high);  
  13.         printArray(x);  
  14.     }  
  15.    
  16.     public static void quickSort(int[] arr, int low, int high) {  
  17.    
  18.         if (arr == null || arr.length == 0)  
  19.             return;  
  20.    
  21.         if (low >= high)  
  22.             return;  
  23.    
  24.         //pick the pivot  
  25.         int middle = low + (high - low) / 2;  
  26.         int pivot = arr[middle];  
  27.    
  28.         //make left < pivot and right > pivot  
  29.         int i = low, j = high;  
  30.         while (i <= j) {  
  31.             while (arr[i] < pivot) {  
  32.                 i++;  
  33.             }  
  34.    
  35.             while (arr[j] > pivot) {  
  36.                 j--;  
  37.             }  
  38.    
  39.             if (i <= j) {  
  40.                 int temp = arr[i];  
  41.                 arr[i] = arr[j];  
  42.                 arr[j] = temp;  
  43.                 i++;  
  44.                 j--;  
  45.             }  
  46.         }  
  47.    
  48.         //recursively sort two sub parts  
  49.         if (low < j)  
  50.             quickSort(arr, low, j);  
  51.    
  52.         if (high > i)  
  53.             quickSort(arr, i, high);  
  54.     }  
  55.    
  56.     public static void printArray(int[] x) {  
  57.         for (int a : x)  
  58.             System.out.print(a + " ");  
  59.         System.out.println();  
  60.     }  
  61. }  

6. 递归 vs. 迭代


对程序员来说，递归应该是一个与生俱来的思想（a built-in thought），可以通过一个简单的例子来说明。问题：

有n步台阶，一次只能上1步或2步，共有多少种走法。

步骤1:找到走完前n步台阶和前n-1步台阶之间的关系。为了走完n步台阶，只有两种方法：从n-1步台阶爬1步走到或从n-2步台阶处爬2步走到。如果f(n)是爬到第n步台阶的方法数，那么f(n) = f(n-1) + f(n-2)。步骤2: 确保开始条件是正确的。f(0) = 0;f(1) = 1;


public static int f(int n){
if(n <= 2) return n;
int x = f(n-1) + f(n-2);
return x;
}


递归方法的时间复杂度是指数级，因为有很多冗余的计算：

f(5)f(4) + f(3)f(3) + f(2) + f(2) + f(1)f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)f(1) + f(0) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)

直接的想法是将递归转换为迭代：


public static int f(int n) {
if (n <= 2){
return n;
}

int first = 1, second = 2;
int third = 0;
for (int i = 3; i <= n; i++) {
third = first + second;
first = second;
second = third;
}
return third;
}


这个例子迭代花费的时间更少，你可能复习一个两者的区别Recursion vs Iteration。


7. 动态规划


动态规划是解决下面这些性质类问题的技术：

  1. 一个问题可以通过更小子问题的解决方法来解决，或者说问题的最优解包含了其子问题的最优解
  2. 有些子问题的解可能需要计算多次
  3. 子问题的解存储在一张表格里，这样每个子问题只用计算一次
  4. 需要额外的空间以节省时间
爬台阶问题完全符合上面的四条性质，因此可以用动态规划法来解决。 
public static int[] A = new int[100];

public static int f3(int n) {
if (n <= 2)
A[n]= n;

if(A[n] > 0)
return A[n];
else
A[n] = f3(n-1) + f3(n-2);//store results so only calculate once!
return A[n];
}


经典题目：

1) Edit Distance

2) Longest Palindromic Substring

题目来源：

Finding the longest palindromic substring is a classic problem of coding interview. In this post, I will summarize 3 different solutions for this problem.

动态规划：

Let s be the input string, i and j are two indices of the string.

Define a 2-dimension array "table" and let table[i][j] denote whether substring from i to j is palindrome.

Start condition:

table[i][i] == 1;
table[i][i+1] == 1  => s.charAt(i) == s.charAt(i+1)

Changing condition:

table[i+1][j-1] == 1 && s.charAt(i) == s.charAt(j)
=>
table[i][j] == 1

Time O(n^2) Space O(n^2)

[java] view plaincopy
  1. public static String longestPalindrome2(String s) {  
  2.     if (s == null)  
  3.         return null;  
  4.    
  5.     if(s.length() <=1)  
  6.         return s;  
  7.    
  8.     int maxLen = 0;  
  9.     String longestStr = null;  
  10.    
  11.     int length = s.length();  
  12.    
  13.     int[][] table = new int[length][length];  
  14.    
  15.     //every single letter is palindrome  
  16.     for (int i = 0; i < length; i++) {  
  17.         table[i][i] = 1;  
  18.     }  
  19.     printTable(table);  
  20.    
  21.     //e.g. bcba  
  22.     //two consecutive same letters are palindrome  
  23.     for (int i = 0; i <= length - 2; i++) {  
  24.         if (s.charAt(i) == s.charAt(i + 1)){  
  25.             table[i][i + 1] = 1;  
  26.             longestStr = s.substring(i, i + 2);  
  27.         }     
  28.     }  
  29.     printTable(table);  
  30.     //condition for calculate whole table  
  31.     for (int l = 3; l <= length; l++) {  
  32.         for (int i = 0; i <= length-l; i++) {  
  33.             int j = i + l - 1;  
  34.             if (s.charAt(i) == s.charAt(j)) {  
  35.                 table[i][j] = table[i + 1][j - 1];  
  36.                 if (table[i][j] == 1 && l > maxLen)  
  37.                     longestStr = s.substring(i, j + 1);  
  38.             } else {  
  39.                 table[i][j] = 0;  
  40.             }  
  41.             printTable(table);  
  42.         }  
  43.     }  
  44.    
  45.     return longestStr;  
  46. }  
  47. public static void printTable(int[][] x){  
  48.     for(int [] y : x){  
  49.         for(int z: y){  
  50.             System.out.print(z + " ");  
  51.         }  
  52.         System.out.println();  
  53.     }  
  54.     System.out.println("------");  
  55. }  

Given an input, we can use printTable method to examine the table after each iteration. For example, if input string is "dabcba", the final matrix would be the following:

1 0 0 0 0 0 
0 1 0 0 0 1 
0 0 1 0 1 0 
0 0 0 1 0 0 
0 0 0 0 1 0 
0 0 0 0 0 1

From the table, we can clear see that the longest string is in cell table[1][5].

3) Word Break

题目来源：

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".

动态规划：

The key to solve this problem by using dynamic programming approach:

  • Define an array t[] such that t[i]==true => 0-(i-1) can be segmented using dictionary
  • Initial state t[0] == true
[java] view plaincopy
  1. public class Solution {  
  2.     public boolean wordBreak(String s, Set<String> dict) {  
  3.         boolean[] t = new boolean[s.length()+1];  
  4.         t[0] = true; //set first to be true, why?  
  5.         //Because we need initial state  
  6.    
  7.         for(int i=0; i<s.length(); i++){  
  8.             //should continue from match position  
  9.             if(!t[i])   
  10.                 continue;  
  11.    
  12.             for(String a: dict){  
  13.                 int len = a.length();  
  14.                 int end = i + len;  
  15.                 if(end > s.length())  
  16.                     continue;  
  17.    
  18.                 if(t[end]) continue;  
  19.    
  20.                 if(s.substring(i, end).equals(a)){  
  21.                     t[end] = true;  
  22.                 }  
  23.             }  
  24.         }  
  25.    
  26.         return t[s.length()];  
  27.     }  
  28. }  

4) 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.

动态规划：

[java] view plaincopy
  1. public class Solution {  
  2.     public int maxSubArray(int[] A) {  
  3.         int max = A[0];  
  4.         int[] sum = new int[A.length];  
  5.         sum[0] = A[0];  
  6.    
  7.         for (int i = 1; i < A.length; i++) {  
  8.             sum[i] = Math.max(A[i], sum[i - 1] + A[i]);  
  9.             max = Math.max(max, sum[i]);  
  10.         }  
  11.    
  12.         return max;  
  13.     }  
  14. }  

5) Palindrome Partitioning

题目来源：

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]
动态规划：

The dynamic programming approach is very similar to the problem of longest palindrome substring.


[java] view plaincopy
  1. public static List<String> palindromePartitioning(String s) {  
  2.    
  3.     List<String> result = new ArrayList<String>();  
  4.    
  5.     if (s == null)  
  6.         return result;  
  7.    
  8.     if (s.length() <= 1) {  
  9.         result.add(s);  
  10.         return result;  
  11.     }  
  12.    
  13.     int length = s.length();  
  14.    
  15.     int[][] table = new int[length][length];  
  16.    
  17.     // l is length, i is index of left boundary, j is index of right boundary  
  18.     for (int l = 1; l <= length; l++) {  
  19.         for (int i = 0; i <= length - l; i++) {  
  20.             int j = i + l - 1;  
  21.             if (s.charAt(i) == s.charAt(j)) {  
  22.                 if (l == 1 || l == 2) {  
  23.                     table[i][j] = 1;  
  24.                 } else {  
  25.                     table[i][j] = table[i + 1][j - 1];  
  26.                 }  
  27.                 if (table[i][j] == 1) {  
  28.                     result.add(s.substring(i, j + 1));  
  29.                 }  
  30.             } else {  
  31.                 table[i][j] = 0;  
  32.             }  
  33.         }  
  34.     }  
  35.    
  36.     return result;  
  37. }  


8. 位操作


常用位操作符：

OR (|) AND (&) XOR (^) Left Shift (<<) Right Shift (>>) Not (~)
1|0=1 1&0=0 1^0=1 0010<<2=1000 1100>>2=0011 ~1=0

用一个题目来理解这些操作 －

获得给定数字n的第i位：(i从0计数并从右边开始) 
public static boolean getBit(int num, int i){
int result = num & (1<<i);

if(result == 0){
return false;
}else{
return true;
}
例如，获得数字10的第2位： i=1, n=101<<1= 101010&10=1010 is not 0, so return true;

9. 概率问题


解决概率相关的问题通常需要先分析问题，下面是一个这类问题的简单例子：

一个房间里有50个人，那么至少有两个人生日相同的概率是多少？（忽略闰年的事实，也就是一年365天）
计算某些事情的概率很多时候都可以转换成先计算其相对面。在这个例子里，我们可以计算所有人生日都互不相同的概率，也就是：365/365 * 364/365 * 363/365 * … * (365-49)/365，这样至少两个人生日相同的概率就是1 – 这个值。 
public static double caculateProbability(int n){
double x = 1; 

for(int i=0; i<n; i++){
x *=  (365.0-i)/365.0;
}

double pro = Math.round((1-x) * 100);
return pro/100;
}
calculateProbability(50) = 0.97

经典题目：桶中取球


10. 排列组合


组合和排列的区别在于次序是否关键。例1：

1、2、3、4、5这5个数字，用java写一个方法，打印出所有不同的排列， 如：51234、41235等。要求："4"不能在第三位，"3"与"5"不能相连。
例2：
5个香蕉，4个梨子，3个苹果。同一种水果都是一样的，这个些水果排列成不同的组合有多少情况？


11. 其他类型的题目


主要是不能归到上面10大类的。需要寻找规律，然后解决问题的。 经典题目: Reverse Integer




转自：http://blog.csdn.net/xiaoranlr/article/details/43963933

标签：

相关文章