알고리즘 문제 총화

package yx.csdn.algorithm;

//          
/**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

    ：          ，       
  ：                          ，              ：
         ，           2        （              ），
          ，      。                      
 */
import java.util.Stack;

public class Test1 {

	public static void main(String[] args) {
		String[] tokens = new String[] {"4", "13", "5", "/", "+"};
		System.out.println(evalRPN(tokens));
	}
	
	public static int evalRPN(String[] tokens) {
		 
        int returnValue = 0;
 
        String operators = "+-*/";
 
        Stack<String> stack = new Stack<String>();
 
        for(String t : tokens){
            if(!operators.contains(t)){
                stack.push(t);
            }else{
                int a = Integer.valueOf(stack.pop());//    
                int b = Integer.valueOf(stack.pop());//    
                int index = operators.indexOf(t);
                switch(index){
                    case 0://+
                        stack.push(String.valueOf(a+b));
                        break;
                    case 1://-
                        stack.push(String.valueOf(b-a));
                        break;
                    case 2://*
                        stack.push(String.valueOf(a*b));
                        break;
                    case 3:// /
                        stack.push(String.valueOf(b/a));
                        break;
                }
            }
        }
 
        returnValue = Integer.valueOf(stack.pop());
 
        return returnValue;
 
    }

}

</pre><pre name="code" class="java">

package yx.csdn.algorithm;
//      
/**          ：     （   ）
 *                   ，        ，           。
 *          ，                         ，          ，
 *             ，    "abcba"，"abba"。   "abcba"      ，
 *         'c'      ，    "abba"      ，          。
 *       ，                            。
 *  
 */
public class Test2 {

	public static void main(String[] args) {
		
		fun3();
	}
	
	
	private static void fun3() {
		String s="ewewqewewjjdsjhqwewqsfhjidsfjidshfi";
		System.out.println(longestPalindrome3(s));
	}

	
	/**
	 *        
      	               ，          i   ， 2     i            ，      0 
		n-1        ，            。       ，            ， "abcba" "abba"2   ，
		              。
     	   int Palindromic ( string &s, int i ,int j)       i   j             ，   0 n-1   ，  2    ：
     	int lenOdd =  Palindromic( str, i, i )   int lenEven = Palindromic (str , i , j )，     i                。
     	    lenOdd lenEven           max    。
     	                O(n2)，           。
     	    ，      ~
	 */
	public static String longestPalindrome3(String s) {
		if (s.isEmpty()) {
			return null;
		}
	 
		if (s.length() == 1) {
			return s;
		}
	 
		String longest = s.substring(0, 1);
		for (int i = 0; i < s.length(); i++) {
			// get longest palindrome with center of i
			String tmp = helper(s, i, i);
			if (tmp.length() > longest.length()) {
				longest = tmp;
			}
	 
			// get longest palindrome with center of i, i+1
			tmp = helper(s, i, i + 1);
			if (tmp.length() > longest.length()) {
				longest = tmp;
			}
		}
	 
		return longest;
	}
	 
	// Given a center, either one letter or two letter, 
	// Find longest palindrome
	public static String helper(String s, int begin, int end) {
		while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
			begin--;
			end++;
		}
		return s.substring(begin + 1, end);
	}
}

package yx.csdn.algorithm;

import java.util.HashSet;
import java.util.Set;


/**
 * 
 *   ：      
 * 
 * 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" .
 * 
 *   ：
 * 
 *          ，          ，                  ，       ，           ，         。
 * 
 *     ：
 * 
 *      S，     N，  S   “    ”（dict）        ，          ：
 * 
 * F(0, N) = F(0, i) && F(i, j) && F(j, N);
 * 
 *    ，               Dict                        （     True,       False）
 *      boolean        ，   ，   boolean         F(0, N)  ，
 *  True       S  Dict      ，    ！
 * 
 *        http://www.tuicool.com/articles/Iv2QJf
 */
public class Test3 {

	
	public static void main(String[] args) {
		 String s = "leetcode";
		    Set<String> dict = new HashSet<String>();
		    dict.add("leet");
		    dict.add("code");
		    System.out.println(wordBreak2(s, dict));

	}

	//given s = "leetcode" , dict = ["leet", "code"]
	//[0 1 2 3 4 5 6 7 8] 
	//[1 0 0 0 1 0 0 0 1]
	public static boolean wordBreak2(String s, Set<String> dict) {
		int len = s.length();
		boolean[] arrays = new boolean[len + 1];
		arrays[0] = true;
		for (int i = 1; i <= len; ++i) {
			for (int j = 0; j < i; ++j) {
				if (arrays[j] && dict.contains(s.substring(j, i))) {
					// f(n) = f(0,i) + f(i,j) + f(j,n)
					arrays[i] = true;
					break;
				}
			}
		}
		return arrays[len];
	}

}

package yx.csdn.algorithm;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

//  
/**
 * 
 *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",
*return its length 5.
 *
 *
 *    ：http://www.programcreek.com/2012/12/leetcode-word-ladder/              
 */
public class Test4 {

	public static void main(String[] args) {
		String start="hit";
		String end="cog";
		Set<String> set=new HashSet<String>();
		set.add("hot");
		set.add("dot");
		set.add("dog");
		set.add("lot");
		set.add("log");
		System.out.println(ladderLength(start, end, set)+"");
		
	}
	
	public static int ladderLength(String start, String end, Set<String> dict) {
		 
        if (dict.size() == 0)  
            return 0; 
 
        LinkedList<String> wordQueue = new LinkedList<String>();
        LinkedList<Integer> distanceQueue = new LinkedList<Integer>();
 
        wordQueue.add(start);
        distanceQueue.add(1);
 
 
        while(!wordQueue.isEmpty()){
            String currWord = wordQueue.pop();
            Integer currDistance = distanceQueue.pop();
 
            for(int i=0; i<currWord.length(); i++){
                char[] currCharArr = currWord.toCharArray();
                for(char c='a'; c<='z'; c++){
                    currCharArr[i] = c;
 
                    String newWord = new String(currCharArr);
                    if(newWord.equals(end)){
                    	return currDistance+1;
                    }else if(dict.contains(newWord)){
                        wordQueue.add(newWord);
                        distanceQueue.add(currDistance+1);
                        dict.remove(newWord);
                    }
                }
            }
        }
 
        return 0;
    }

}

package yx.csdn.algorithm;

/**
 * This problem can be converted to the problem of finding kth element, k is (A's length + B' Length)/2.

If any of the two arrays is empty, then the kth element is the non-empty array's kth element.
If k == 0, the kth element is the first element of A or B.

For normal cases(all other cases), we need to move the pointer at the pace of half of an array length.
 * @author yixiang
 *     K    
 */
public class Test5 {
	public static void main(String[] args) {
		int ar1[] = {1, 12, 15, 26, 38};  
	    int ar2[] = {2, 13, 17, 30, 45};  
	    System.out.println(findMedianSortedArrays(ar1, ar2));
	}
	
	public static double findMedianSortedArrays(int A[], int B[]) {
		int m = A.length;
		int n = B.length;
	 
		if ((m + n) % 2 != 0) // odd
			return (double) findKth(A, B, (m + n) / 2, 0, m - 1, 0, n - 1);
		else { // even
			return (findKth(A, B, (m + n) / 2, 0, m - 1, 0, n - 1) 
				+ findKth(A, B, (m + n) / 2 - 1, 0, m - 1, 0, n - 1)) * 0.5;
		}
	}
	 
	//  K  
	public static int findKth(int A[], int B[], int k, 
		int aStart, int aEnd, int bStart, int bEnd) {
	 
		int aLen = aEnd - aStart + 1;
		int bLen = bEnd - bStart + 1;
	 
		// Handle special cases
		if (aLen == 0)
			return B[bStart + k];
		if (bLen == 0)
			return A[aStart + k];
		if (k == 0)
			return A[aStart] < B[bStart] ? A[aStart] : B[bStart];
	 
		int aMid = aLen * k / (aLen + bLen); // a's middle count
		int bMid = k - aMid - 1; // b's middle count
	 
		// make aMid and bMid to be array index
		aMid = aMid + aStart;
		bMid = bMid + bStart;
	 
		if (A[aMid] > B[bMid]) {
			k = k - (bMid - bStart + 1);
			aEnd = aMid;
			bStart = bMid + 1;
		} else {
			k = k - (aMid - aStart + 1);
			bEnd = bMid;
			aStart = aMid + 1;
		}
	 
		return findKth(A, B, k, aStart, aEnd, bStart, bEnd);
	}

}

package yx.csdn.algorithm;

/**
 * 
 * @author yixiang
 *'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") return false
isMatch("aa","aa") return true
isMatch("aaa","aa") return false
isMatch("aa", "a*") return true
isMatch("aa", ".*") return true
isMatch("ab", ".*") return true
isMatch("aab", "c*a*b") return true
 */
public class Test6 {

	public static void main(String[] args) {
		String s="aab";
		String p="aa.";
		System.out.println(isMatch(s, p));
	}
	
	public static boolean isMatch(String s, String p) {
		 
        if(p.length() == 0)
            return s.length() == 0;
 
        //p's length 1 is special case    
        if(p.length() == 1 || p.charAt(1) != '*'){
            if(s.length() < 1 || (p.charAt(0) != '.' && s.charAt(0) != p.charAt(0)))
                return false;
            return isMatch(s.substring(1), p.substring(1));    
 
        }else{
            int len = s.length();
 
            int i = -1; 
            while(i<len && (i < 0 || p.charAt(0) == '.' || p.charAt(0) == s.charAt(i))){
                if(isMatch(s.substring(i+1), p.substring(2)))
                    return true;
                i++;
            }
            return false;
        } 
    }

}

package yx.csdn.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 *     
 * @author yixiang
 *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].
 */
public class Test7 {

	public static void main(String[] args) {
		int[][] matrix=new int[][]{
				{1,2,3},
				{4,5,6},
				{7,8,9}
		};
		List<Integer> list=spiralOrder(matrix);
		for (Integer integer : list) {
			System.out.println(integer.toString());
		}
	}
	
	public static ArrayList<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> result = new ArrayList<Integer>();
 
        if(matrix == null || matrix.length == 0) return result;
 
        int m = matrix.length;
        int n = matrix[0].length;
 
        int x=0; 
        int y=0;
 
        while(m>0 && n>0){
 
            //if one row/column left, no circle can be formed
            if(m==1){
                for(int i=0; i<n; i++){
                    result.add(matrix[x][y++]);
                }
                break;
            }else if(n==1){
                for(int i=0; i<m; i++){
                    result.add(matrix[x++][y]);
                }
                break;
            }
 
            //below, process a circle
 
            //top - move right
            for(int i=0;i<n-1;i++){
                result.add(matrix[x][y++]);
            }
 
            //right - move down
            for(int i=0;i<m-1;i++){
                result.add(matrix[x++][y]);
            }
 
            //bottom - move left
            for(int i=0;i<n-1;i++){
                result.add(matrix[x][y--]);
            }
 
            //left - move up
            for(int i=0;i<m-1;i++){
                result.add(matrix[x--][y]);
            }
 
            x++;
            y++;
            m=m-2;
            n=n-2;
        }
 
        return result;
    }

}