算法学习笔记（LeetCode OJ）

==================================

LeetCode的一些算法题，都是自己做的，欢迎提出改进~~

LeetCode：http://oj.leetcode.com

==================================

<Reverse Words in a String>-20140328

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

public class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        String[] str = s.split("\s{1,}");
        String tmp;
        int len = str.length;
        int halfLen = len/2;
        for(int i=0;i<halfLen;i++){
            tmp = str[i];
            str[i] = str[len-i-1];
            str[len-i-1] = tmp;
        }
        StringBuffer sb = new StringBuffer();
        String result;
        if(len==1){
            result = str[0];
        }else{
            for(String string:str){
                sb.append(string+" ");
            }
            result = sb.toString().trim();
        }
        return result;
    }
}

 C++: http://blog.csdn.net/feliciafay/article/details/20884583

一个空格的情况
多个空格在一起的情况
空串的情况
首尾空格的情况
一些测试数据：
“            ”
“a       ”
"       a"
"      a     "
"     a      b    "
"     a b     "
"     a  b"
"a  b       "

 <Evaluate Reverse Polish Notation>-20140329

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

public class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack();
        for(String str:tokens){
            if("+-*/".contains(str)){
                int b = stack.pop();
                int a = stack.pop();
                switch(str){
                    case "+":
                        stack.add(a+b);
                        break;
                    case "-":
                        stack.add(a-b);
                        break;
                    case "*":
                        stack.add(a*b);
                        break;
                    case "/":
                        stack.add(a/b);
                        break;
                }
            }else{
                stack.add(Integer.parseInt(str));
            }
        }
        return stack.pop();
    }
}

 <Max Points on a Line>-20140330

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

开始的实现：

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    private boolean judgment(Point a, Point b, Point third){
        return (a.y-third.y)*(b.x-third.x)==(b.y-third.y)*(a.x-third.x);
    }
    
    public int maxPoints(Point[] points) {
        int len = points.length;
        if(len<3){
            return len;
        }
        int[] mark = new int[len];
        for(int m=0;m<len;m++){
            mark[m] = 0;
        }
        int count = 2;
        for(int i=0;i<len;i++){
            int tmpCount = 2;
            for(int j=i+1;j<len;j++){
                if(mark[j]==1){
                    continue;
                }
                for(int k=j+1;k<len;k++){
                    if(mark[k]==1){
                        continue;
                    }
                    boolean judge = judgment(points[i],points[j],points[k]);
                    if(judge){
                        mark[k] = 1;
                        tmpCount++;
                    }
                }
            }
            if(tmpCount>count){
                count = tmpCount;
            }
        }
        return count;
    }
}

后来发现被坑了，它是有相同点出现这种情况的！！！开始我还傻傻地想为什么<5,6,18>三点共线而<0,5,6>却不共线，后来自己费了好大力气才明白过来。

然后，还有其他的问题，对此题无力了，还是先放放过几天头脑清醒再来弄吧T-T。

看看人家的思想先吧，不过我还是想先自己搞掂再看。

C++: http://blog.csdn.net/feliciafay/article/details/20704629

<Single Number>-20140414

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

public class Solution {
    public int singleNumber(int[] A) {
        int num = 0;
        for(int i : A){
            num ^= i;
        }
        return num;
    }
}