leetcode 刷题日志 2018-03-26

58. 最后一个单词的长度

分析：找最后一个非空格，向前找

int lengthOfLastWord(string s) {

        int i = s.find_last_not_of(' ');

        int j = i;

        for(;j >= ; j--){

            if(s[j] == ' ')

                break;

        }

        return i - j;

    }

7. 颠倒整数

分析：注意题意，超范围 LL ，结尾去0

int reverse(int x) {

        long long res = ;

        if(x!=){

            while(!x%){

                x /= ;

            }

        }

        while(x){

            res *= ;

            res += x % ;

            x /= ;

        }

        if(res> INT_MAX || res < -INT_MAX){

            res = ;

        }

        return res;

    }

13. 罗马数字转整数

分析：罗马数字共有7个，即Ⅰ（1）、Ⅴ（5）、Ⅹ（10）、Ⅼ（50）、Ⅽ（100）、Ⅾ（500）和Ⅿ（1000）。按照下述的规则可以表示任意正整数。需要注意的是罗马数字中没有“0”，与进位制无关。一般认为罗马数字只用来记数，而不作演算。

字母对应数字相加，后面字母比前面字母大代表前面字母需要减去

被减的字母最多一个！

int singleCharToInt(char x){

        int num = -;

        if(x == 'i')

            num = ;

        else if(x == 'v')

            num = ;

        else if(x == 'x')

            num = ;

        else if(x == 'l')

            num = ;

        else if(x == 'c')

            num = ;

        else if(x == 'd')

            num = ;

        else if(x == 'm')

            num = ;

        return num;

    }

    int romanToInt(string s) {

        int len = s.size();

        transform(s.begin(), s.end(), s.begin(), ::tolower);

        int res = ;

        for(int i=;i<len;i++){

            int num=singleCharToInt(s[i]);

            if(singleCharToInt(s[i+]) > num){

                num=(-)*num;

            }

            res += num;

        }

        return res;

    }

38. 数数并说

分析：步步迭代

整数字符串转换

string fun(string s){

    string tmp = "";

    int len = s.size();

    int con =;

    char t ;

    for(int i=;i<len;){

        t=s[i++];con = ;

        while(s[i] == t){

            con++; i++;

        }

        ostringstream stream;

        stream<<con;  //n为int类型

        tmp =tmp + stream.str();

        tmp+=t;

    }

    return tmp;

}

string countAndSay(int n) {

    string s="";

    int en = s.size();

    int con =;

    while(--n){

        s=fun(s);

        //cout<<s<<endl;

    }

    return s;

}

67. 二进制求和

分析：对齐，相加，首位进位处理

string addBinary(string a, string b) {

        //对齐

        int lena = a.size(), lenb = b.size();

        int n = abs(lena - lenb);

        string tmp(n,'');

        if(lena < lenb) { a = tmp + a; }

        if(lena > lenb) { b = tmp + b; }

        //加法

        int len = a.size();

        int x = , c = ; // 计算结果，进位标记

        for(int i = len - ; i >= ; --i){

            x = a[i] - '' + b[i] -'' + c;

            if( x > ){

                c = ;

                x -= ;

            }

            else{

                c = ;

            }

            a[i] = (char)('' + x );

        }

        if(c) //首部进位

            a = "" + a;

        return a;

    }

14. 最长公共前缀

分析：拿第一个字符串作为标准，遍历所有字符串，期间不断缩小条件

string longestCommonPrefix(vector<string>& strs) {

        int len = strs.size(),lenS = ;

        if( == len)

            return "";

        string s = strs[];

        for(int i=; i<len; ++i){

            lenS = s.length();

            for(int j=; j<lenS; ++j){

                if(s[j] != strs[i][j]){

                    s = s.substr( , j); //对比所有字符串，不断缩减条件

                    break;

                }

            }

        }

        return s;

    }

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

括号必须以正确的顺序关闭，"()" 和 "()[]{}" 是有效的但是 "(]" 和 "([)]" 不是。

分析：栈的应用

我用的比较别扭

每次压入一个字符，深入栈内看是否还有配对成功的括号可以弹出

最终所有配对成功的话，栈为空

bool isValid(string s) {

    stack<char> stack_tmp;

    int len = s.length();

    char x,y;

    stack_tmp.push(s[]);

    for(int i=; i<len; i++){

        stack_tmp.push(s[i]);

        while(stack_tmp.size()>=){ //要想配对成功，至少有两个

            y = stack_tmp.top();

            stack_tmp.pop();

            x = stack_tmp.top(); //取两数

            if(')' == y && x == '('){

                stack_tmp.pop();

            }

            else if('}' == y && x == '{'){

                stack_tmp.pop();

            }

            else if(']' == y && x == '['){

                stack_tmp.pop();

            }

            else{

                stack_tmp.push(y); //不行，再压回去

                break;

            }

        }

    }

    return stack_tmp.empty();

}

29. 两数相除

不使用乘号，除号和取模符号将两数相除。如果溢出返回 MAX_INT。

感谢：https://www.liuchuo.net/archives/3140

//1. 利用 a/b = exp(log(a)-log(b))  //注意定义域>0 需取绝对值，并抽取符号位（抑或运算用的巧妙）
//2. 注意越界情况，可能分母==0 可能负数反号
int divide(int dividend, int divisor) {

    if(divisor ==  || dividend == INT_MIN && divisor == -) return INT_MAX; //溢出两种情况

    int sign = ((dividend >> ) ^ (divisor >> )) ==  ?  : -; //符号位 判断

    long a = abs((long)dividend);

    long b = abs((long)divisor);

    double c = exp(log(a) - log(b)) + 0.0000000001;

    return (int)(sign * c);

}

125. 验证回文字符串

给定一个字符串，确定它是否是回文，只考虑字母数字字符和忽略大小写。

例如：
"A man, a plan, a canal: Panama" 是回文字符串。
"race a car" 不是回文字符串。

注意:
你有考虑过这个字符串可能是空的吗？在面试中这是一个很好的问题。

针对此题目，我们将空字符串定义为有效的回文字符串。

分析：空串处理、提取主要字符串、双向搜索判断

bool isPalindrome(string s) {

    if (""== s) return true; //1. deal with empty string

    int len = s.length();

    string tmp="";

    for(int i=; i <len; i++){  //2. filter string

        if(s[i]>='A' &&s[i]<='Z'){

            tmp +=s[i] +;

        }

        if((s[i]>='a'&& s[i]<='z') ||(s[i] >='' &&s[i] <='')){

            tmp +=s[i];

        }

    }

    len = tmp.length();

    int m = (len +)/;

    for (int i=; i <= m; i++) { //3. Bidirectional search

        if(tmp[i] != tmp[len -i -])

            return false;

    }

    return true;

}

巴特西

leetcode 刷题日志 2018-03-26

最新文章

热门文章