字符串专题 2016-08-15

[wolfogre]

8 String to Integer (atoi)

第一题写两种做法，一种是利用各语言的标准工具做转换，一种是徒手转换。

151 Reverse Words in a String

[wolfogre]

C++ 用工具

// [AC] 8 String to Integer (atoi)
#include <sstream>
class Solution {
public:
    int myAtoi(string str) {
        stringstream sstr;
        sstr << str;
        int result = 0;
        sstr >> result;
        return result;
    }
};

[wolfogre]

C++ 徒手

// [AC] 8 String to Integer (atoi)
class Solution {
public:
    int myAtoi(string str) {
        long result = 0;
        int sign = 1;
        int i = 0;

        while(str[i] == ' ' || str[i] == '\t'){
            ++i;
        }

        //我觉得应该是while
        if(str[i] == '-' || str[i] == '+'){
            if(str[i] == '-')
                sign = -sign;
            ++i;
        }

        for(; i < str.length() && str[i] >= '0' && str[i] <= '9'; ++i){
            result = result * 10 + str[i] - '0';
            if(result > INT_MAX) { 
                if(sign == 1)
                    return INT_MAX;
                else
                    return INT_MIN;
            }
        }
        return result * sign;
    }
};

[wolfogre]

// [AC] 151 Reverse Words in a String
public class Solution {
    public String reverseWords(String s) {
        String[] result = s.split(" ");
        StringBuilder sb = new StringBuilder();
        for(int i = result.length - 1; i >= 0; --i){
            if(!result[i].isEmpty())
                sb.append(result[i] + " ");
        }
        if(sb.length() > 0 && sb.charAt(sb.length() - 1) == ' ')
            sb.delete(sb.length() - 1, sb.length());
        return sb.toString();
    }
}

[dayang]

/**
 * [AC] 8 String to Integer (atoi)
 * @param {string} str
 * @return {number}
 */
var myAtoi = function(str) {
    var res = 0;
    var sign = 1,i = 0;
    while(str[i] === ' ') i++;
    if(str[i] === '+')
        i++;
    else if(str[i] === '-'){
        sign = -1;
        i++;
    }

    for(; i < str.length ; i++){
        if(str[i] >= '0' && str[i] <= '9'){
            res = res * 10 + Number(str[i]);
            if( sign === 1 && res > 2147483647){
                return 2147483647;
            }else if(sign === -1 && res > 2147483648){
                return -2147483648;
            }
        }else{
            break;
        }
    }
    return res * sign;
};

[dayang]

/**
 * [AC] 151 Reverse Words in a String
 * @param {string} str
 * @returns {string}
 */
var reverseWords = function(str) {
    return str.trim().split(/\s+/).reverse().join(' ');
};

[SnackMen]

/*
*[AC] 8 String to Integer (atoi)
*需要考虑的问题：
*1.字符串中存在空格
*2.字符串中有多个正负号
*3.超出Integer类型最大最小范围
*4.字符串间存在字母等非数字
*/
public class Solution {
    public int myAtoi(String str) {
        if(str.length()==0 || str==null)
            return 0;
        str=str.trim();
        boolean isPositive=true;
        int i=0;
        if(str.charAt(0)=='+'){
            i++;
        }else if(str.charAt(0)=='-'){
            isPositive=false;
            i++;
        }
        double temp=0;
        while(i<str.length()){
            int firstDigit=str.charAt(i)-'0';
            if(firstDigit<0 || firstDigit>9)
                break;
            if(isPositive){
                temp=10*temp+firstDigit;
                if(temp>Integer.MAX_VALUE)
                    return Integer.MAX_VALUE;
            }else{
                temp=10*temp-firstDigit;
                if(temp<Integer.MIN_VALUE)
                    return Integer.MIN_VALUE;
            }
            i++;
        }
        int num=(int)temp;
        return num;
    }
}

[SnackMen]

/*
*[AC] 151 Reverse Words in a String
*《剑指offer》  面试题 42 ：翻转单词顺序 VS 左旋转字符串
*/
public class Solution {
    public String reverseWords(String s) {
        if(s.length()==0 || s==null)
            return "";
        s=s.trim();
        String []strs = s.split("\\s+");//因为字符串中空格存在一个或多个的情况，如果这里使用split(" ")将会报错
        StringBuffer sb = new StringBuffer();

        for(int i=strs.length-1;i>=0;i--){
            sb.append(strs[i]+" ");
        }
        return sb.toString().trim();
    }
}

[zhaokuohaha]

8 -C# - 总感觉不太对

public class Solution
{
    public int MyAtoi(string str)
    {
        if (String.IsNullOrEmpty(str)) return 0;
        str = str.Trim().Split(' ')[0];
        int i = 0, sign = 1;
        long res =0;
        if (str[0] == '+' || str[0] == '-')
        {
            sign = str[0] == '+' ? 1 : -1;
            i++;
        }
        while (i < str.Length)
        {
            if(str[i]>='0' && str[i] <= '9')
            {
                if (sign == 1)
                {
                    res = res * 10 + (str[i] - '0');
                    if (res > int.MaxValue) return int.MaxValue;
                }
                else
                {
                    res = res * 10 - ( str[i] - '0');
                    if (res < int.MinValue) return int.MinValue;
                }
            }
            else
            {
                break;
            }
            i++;
        }
        return (int)res;
    }
}

[zhaokuohaha]

151 - C# - 默认没有using System.Text.RegularExpressions

public class Solution
{
    public string ReverseWords(string s)
    {
        if (String.IsNullOrEmpty(s)) return s;
        string[] strs = System.Text.RegularExpressions.Regex.Split(s.Trim(), "\\s+");
        StringBuilder sb = new StringBuilder();
        for(int i=strs.Length-1; i>=0; i--)
        {
            sb.Append(strs[i] + " ");
        }
        return sb.ToString().Trim();
    }
}

大神代码 - 直接遍历 - 速度极快

public class Solution
    {
        public string ReverseWords(string s)
        {
            s = s.Trim();
            int left, right;
            left = right = s.Length - 1;
            StringBuilder sb = new StringBuilder();
            while (right >= 0)
            {
                if (s[right] == ' ')
                {
                    sb.Append(s.Substring(right + 1, left - right)+" ");
                    while (s[right] == ' ') right--;
                    left = right;
                }
                else right--;
            }
            sb.Append(s.Substring(right + 1, left - right));
            return sb.ToString();
        }
    }