leetcode7-14

leetcode7

问题：逆序输出INTEGER
思路：分为正负，然后用模和除来一位位逆序输出

int reverse(int x) {
		//使用long long以方便边界处理
       long long i = x%10;
       int j = x;
       if(j==0)
           return i;
       while((j/=10)!=0)
       {	//从低位往高位运算结果
           i = i*10 + j%10;
       }
       //边界判断
       if(i>2147483647 || i<-2147483647)
           return 0;
       return i;
   }

leetcode8

问题：String to Integer(ATOI)

int myAtoi(string str) {
        int i=0;
        //遇到空格跳过
        while(str[i]==' ')
            i++;
        //区分正负
        int flag=1;
        if(str[i]=='+')
        {    flag = 1;
            i++;
        }
        else if(str[i]=='-')
        {    flag = -1;
            i++;
        }
        
        if(str[i]>='0'&&str[i]<='9')
        {
        	//用long long方便判断溢出
            long long res =0;
            res += (str[i]-'0');
            i++;
            //string转换成int
            while(str[i]>='0' && str[i]<='9')
            {
                res = res *10 +(str[i]-'0');
                i++;
                if(res>INT_MAX)
                {
                    return flag==1?INT_MAX:INT_MIN;
                }
            }
            res = res * flag;
            return res;
        }
        else{
             return 0;
        }
        return 0;
    }

leetcode9

问题：判断integer是否回文

bool isPalindrome(int x) {
		//不考虑负数
        if (x<0)
            return false;
        int div = 1; //最大除项
        while((x/div)>=10)
        {
            div*=10;
        }
        while(x>0)
        {
            int l = x /div;
            int r = x %10;
            if(l!=r)
                return false;
            //reduce left and right
            //如果一致，同时左右一起消去
            x = x%div / 10;
            div/=100;
        }
        return true;
    }

leetcode10

问题：正则匹配,.表示任意字母，*表示任意个数
作者回答
这个问题是正则匹配的问题，比较复杂，是一个状态机匹配的问题，可以用递归去求解。

 bool isMatch(string s, string p) {
 	//空串匹配
   if (p[0] == '\0')
	return s[0] == '\0';
//遇到的是非'*'
if (p[1] != '*'){
	//字符匹配或者匹配'.'
	return ((p[0] == s[0]) || (p[0] == '.' && s[0] != '\0')) && isMatch(s.substr(1, s.length() - 1), p.substr(1, p.length() - 1));
}
//遇到'*',使用while去递归尝试搜索每一种可能的情况
while ((p[0] == s[0]) || (p[0] == '.' && s[0] != '\0')){
	if (isMatch(s, p.substr(2,p.length()-2)))
		return true;
	s=s.substr(1,s.length()-1);
}
//跨过'*'的字符
return isMatch(s, p.substr(2,p.length()-2));
   }

leetcode11

问题：给一组正数数组，任意两个数组元素$a_i,a_j$,使得有最大面积$S=min(a_i,a_j)*(j-i)

//求出最大的装水面积
  int maxArea(vector<int>& height) {
       int start = 0;
       int end = height.size()-1;
       int maxV = INT_MIN;
       //从两边向中间收拢
       while(start<end){

           int contains = min(height[end],height[start]) * (end-start);
           maxV = max(maxV,contains);
           //左比右的板短，移动左边
           if(height[start]<height[end])
               start++;
           else
               end--;
               
       }
       return maxV;

leetcode12

问题：INTEGER TO ROMAN
思路：关键在于罗马数制和阿拉伯数制的映射，分为M,D,C,L,V,I。
由罗马字母的数值大小取模匹配。

string intToRoman(int num) {
    if (num > 0 && num < 4000)
	{
		string res = "";
		//建立映射
		string symbol[] = { "M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I" };
		int value[] = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
		while (num>0)
		{
			for (int i = 0; i < (sizeof(value)/sizeof(int)); i++)
			{	
				//将integer由罗马字母的大到小匹配，然后输出
				if (num / value[i]>0)
				{
					for (int j = 0; j < (num / value[i]); j++)
						res += symbol[i];
					num %= value[i];
				}
			}
		}
		return res;
		
	}
	return "";
    }

leetcode13

问题：ROMAN TO INTEGER
最简思路：罗马字母里，左比右小，则为右减左；左比右大，则为右加左。

//遍历罗马字串，左和右是指罗马字值M,D,C,X,V,I
if left<right:
	res+= res-2*left;
else
	res+= res+right;

//我的思路：先匹配两字的，再匹配一字的
int romanToInt(string s) {
	int res=0;
	string symbol[] = { "M", "CM", "D", "CD", "C","XC", "L", "XL", "X", "IX", "V", "IV", "I" };
	int value[] = { 1000, 900, 500, 400, 100, 90,50, 40, 10, 9, 5, 4, 1 };
	for (int i = 0; i < s.length(); i++)
	{
		bool flag = false;
		string match(s,i,2);
		//First find the two in advance
		for (int j = 0; j < (sizeof(symbol) / sizeof(symbol[0])); j++)
		{
			// match symbol
			if (match.compare(symbol[j]) == 0)
			{
				res += value[j];
				i++;
				flag = true;
				break;
			}
		}
		if (flag == true)
			continue;
		//find the one then
		string match1(s, i, 1);
		for (int j = 0; j < (sizeof(symbol) / sizeof(symbol[0])); j++)
		{
			if (match1.compare(symbol[j]) == 0)
			{
				res += value[j];
				break;
			}
		}
		

	}
	if (res > 0 && res < 4000)
	{
		return res;
	}
	return 0;

leetcode14

问题：Longest Common Prefix，求字符串组里面，公共有的前缀子串。
思路：这个是公共子串的特例，前缀子串，公共子串的学问很深，可以参考文章，里面使用一个个起始字符暴力匹配O(N^3),和DP的O(N^2)等。
这个问题也十分有用，可以判断字符串的相似度等等，经典的面试题。

string longestCommonPrefix(vector<string>& strs) {
	//判断边界条件
   	if (strs.size() == 0)
		return "";
	else if (strs.size() == 1)
		return strs[0];

	string com = "";
	string res = "";
	//先比较两串
	int len = strs[0].length() < strs[1].length() ? strs[0].length() : strs[1].length();
	for (int i = 0; i < len; i++)
	{
		if (strs[0][i] == strs[1][i])
			com += strs[0][i];
		else
		    break;
	}
	if (strs.size() == 2)
		return com;
	//用common串跟之后每一个串比较，common会越来越短
	for (int i=0; i < (strs.size()); i++)
	{
		res = "";
		int len = com.length()<strs[i].length() ? com.length() : strs[i].length();
		for (int j = 0; j < len; j++)
		{
			if (com[j] == strs[i][j])
				res += com[j];
			else 
			    break;
		}
		com = res;
		
	}
	return res;
    }