LeetCode题目1~3

做了LeetCode前三题，感觉每道题目都挺麻烦啊。之前跟备哥聊天还以为题目都很水呢，看来被忽悠了？

意思是把输入的字符串中的多个单词顺序颠倒（不是单词本身逆序）。并且去掉前位置空格和尾部空格，单词之间仅保留一个空格。我是利用c++的stringstream来搞定。这题比较简单，代码如下：

class Solution {
public:
    void reverseWords(string &s) {
        string s1,s2;
    	stack<string> sstack;
    	istringstream is(s);
    	ostringstream os(s2);
    	while (is >> s1)
    		sstack.push(s1);
    	
    	while (!sstack.empty())
    	{
    		s2 += sstack.top();
    		sstack.pop();
    		if (sstack.size() > 0){
    			s2 += " ";
    		}
    	}
    	s=s2;
    }
};

第二题：Evaluate Reverse Polish Notation

逆波兰表达式。好吧，这题也不难，只是输入格式让我很纠结，自己实现了atoi和itoa（myatoi，myitoa），就当练手了。话说回来这题目至于这么麻烦么？是不是我忽略了什么？。。逆波兰表达式的求法，就是一个入栈和出栈的过程，基本上是数据结构stack的入门必知必会例题了~贴下我冗长代码：

class Solution {
public:
	int myatoi(string &s)
	{
		int start = 0;
		if (s[0] == '-')
			start++;
		int ret = 0;
		for (int i = start; i < s.size(); i++)
		{
			ret *= 10;
			ret += (s[i] - '0');
		}
		if (start)
			ret = -ret;
		return ret;
	}
	string myitoa(int i)
	{
		string ret;
		int ii = i;
		if (i < 0) i = -i;
		while (i)
		{
			int t = i % 10;
			char c = '0' + t;
			ret.push_back(c);
			i /= 10;
		}
		if (ii < 0)
			ret.push_back('-');
		reverse(ret.begin(), ret.end());
		return ret;
	}
	int evalRPN(vector<string> &tokens) {
		stack<string> sstack;
		if (tokens.size() < 2)
			return myatoi(tokens[0]);
		int i = 2;
		sstack.push(tokens[0]);
		sstack.push(tokens[1]);
		while (!sstack.empty())
		{
			if (i >= tokens.size())
				break;
			string str = tokens[i++];
			if ((str[0]<'0' || str[0]>'9') && str.size()== 1)
			{
				string str1 = sstack.top();
				sstack.pop();
				int i2 = myatoi(str1);
				string str2 = sstack.top();
				sstack.pop();
				int i1 = myatoi(str2);
				switch (str[0])
				{
				case '+':
					sstack.push(myitoa(i1 + i2));
					break;
				case '-':
					sstack.push(myitoa(i1 - i2));	
					break;
				case '*':
					sstack.push(myitoa(i1 * i2));
					break;
				case '/':
					sstack.push(myitoa(i1 / i2));
					break;
				}
			}
			else
			{
				sstack.push(str);
			}
		}
		return myatoi(sstack.top());
	}
};

第三题：Max Points on a Line

真心比较麻烦（还是我太水？？我不水谁水:)）。枚举每个点到其他点之间的斜率，每次统计当前点到其他点的斜率中最多的相同斜率值数目，这个数目就是与当前点共线的最多点数（不含当前点，所以最后+1），还要考虑两种情况：与当前点重合的情况，利用self统计，最后加到返回值中，还在索引中添加一项2*INF+X，值为0；斜率无限的情况，利用INF+X来标记索引。贴代码吧

struct Point {
   int x;
   int y;
   Point() : x(0), y(0) {}
   Point(int a, int b) : x(a), y(b) {}
};

class Solution {
public:

	int maxPoints(vector<Point> &points) {
		if (points.size() == 0)
			return 0;
		map<double, int> hmap;
		double index[1000];
		const double eps = 0.000001;
		const int M = 1000000;
		const double INF = 1000000000;
		int max = 0;
		for (int i = 0; i < points.size(); i++)
		{
			int k = 0;
			int self = 0;
			for (int j = 0; j < points.size(); j++)
			{
				if (j == i)
					continue;/**/
				if (points[j].y == points[i].y && points[j].x == points[i].x){
					self++;
					index[k++] = 2*INF + points[j].x*10+points[j].y;
					hmap[index[k]]=0;
					continue;
				}
				if (points[j].y != points[i].y && points[j].x == points[i].x)
				{
					hmap[INF + points[j].x]++;
					index[k++] = INF + points[j].x;
					continue;
				}
				double slide = (double)(points[j].y - points[i].y) / (double)(points[j].x - points[i].x);
				slide *= M;
				slide = (int)slide;
				slide = (double)slide / M;
				hmap[slide]++;
				index[k++] = slide;
			}
			for (int j = 0; j < k; j++)
			{
				int tmax = hmap[index[j]] + hmap[index[j] + eps] + hmap[index[j] - eps] + self;
				if (tmax>max)
					max = tmax;
			}
			hmap.clear();
		}
		return max + 1;
	}
};

OK，今天就差不多这样了~收获还是比较大，明天继续（我会说我被第四题卡了一下不想做了么）。