leetcode 6-10题题解 - dblank

leetcode 6-10题题解

在我的github同步代码

6. ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

题意:

将给定的字符串摆成__之__字型,问从左到右的顺序.

思路:

先画一个图,可以找规律.

AC代码:

class Solution
{
public:
    string convert(string s, int numRows)
    {
        int n = s.size();
        string ans = "";
        int row = 0, line = 0, x = numRows - 1, cnt =  0, id;
        if(numRows == 1)
            return s;
        while(row<numRows && cnt < n)
        {
            id = row;
            int flag = 0;
            while(id < n && cnt < n)
            {
                ans += s[id];
                if(row != 0 && row != numRows-1)
                {
                    if(!flag)
                        id += 2*x;
                    else id += 2*numRows - 2*x -2;
                    flag ^= 1;
                }
                else id += 2*(numRows - 1);
                cnt++;
            }
            x--, row++;

        }
        return ans;
    }
};

7. Reverse Integer

Total Accepted: 226202
Total Submissions: 943890
Difficulty: Easy
Contributor: LeetCode
Reverse digits of an integer.

Example: x = 123, return 321

Example2: x = -123, return -321

click to show spoilers.

Note:
The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

题意:

将一数反转

思路:

  • 注意负数
  • INT_MIN 取正数后会造成溢出,可以先转化为long long.

AC代码

class Solution {
public:
    int reverse(int x) {
        string MIN = "2147483648", MAX = "2147483647", rever = "";
        int flag = 0;
        if(x == INT_MIN) return 0;
        if(x < 0)
        flag = 1, x = -x;
        int ans = 0;
        while(x)
        {
            ans = x%10 + ans*10;
            rever += '0' + x%10;
            x /= 10;
        }
        if(flag == 1)
        {
            if(rever.size() > MIN.size() || rever.size() == MIN.size() && rever > MIN)
                return 0;
        }
        else
        {
            if(rever.size() > MAX.size() || rever.size() == MAX.size() && rever > MAX)
                return 0;
        }
        if(flag) return -ans;
        else return ans;
    }
};

8. String to Integer (atoi)

Implement atoi to convert a string to an integer.

__Hint__: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.

spoilers alert... click to show requirements for atoi.

Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

题意:

实现字符串到数字的转换,注意溢出问题

代码:

class Solution
{
public:
    int myAtoi(string str)
    {
        int flag = 0, mark = 0, i = 0;
        string MIN = "2147483648", MAX = "2147483647";
        int dmin = -2147483648, dmax = 2147483647;
        while(str[i] == ' ' && i<str.size())
            i++;
        if(i >= str.size())
            return 0;
        if(str[i] == '-')
            flag = 1;
        string digit = "";
        if(str[i] == '-' || str[i] == '+')
        {
            i++;
            //cout<<str[i]<<endl;
            while(str[i] == '0')
            {
                if(str[i] == '+' && flag == 1 || str[i] == '-' && flag == 0)
                    return 0;
                i++;
            }
        }
        while(i<str.size())
        {
            if(str[i]<='9' && str[i]>='0')
                digit += str[i];
            else break;
            i++;
        }
        if(flag == 1)
        {
            if(digit.size() > MIN.size() || digit.size() == MIN.size() && digit > MIN)
                return dmin;
        }
        else
        {
            if(digit.size() > MAX.size() || digit.size() == MAX.size() && digit > MAX)
                return dmax;
        }

        int ans = 0;
        for(int i = 0; i<digit.size(); i++)
            ans = ans*10 + digit[i] - '0';
        if(flag)
            ans *= -flag;
        return ans;
    }
};

9. Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

Some hints:
Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

题意:

判断一个数是不是回文数

思路:

如果之间反转的话,比如1999999999会造成溢出,所以可以得到一半看是和另一半回文.

AC代码:

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0 || x%10 == 0 && x != 0) return false;
        int res = 0;
        while(res<x)
        {
            res = res*10 + x%10;
            x /= 10;
        }
        return res == x || res/10 == x;
    }
};

10. Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

题意:

*好可以代表任意个它前面字符
.可以代表任意字符
问a串是否匹配b串

思路:

1、考虑特殊情况即*s字符串或者*p字符串结束。

(1)*s字符串结束,要求*p也结束或者间隔‘*’ (例如*p="a*b*c*……"),否则无法匹配

(2)*s字符串未结束,而*p字符串结束,则无法匹配
2、*s字符串与*p字符串均未结束

(1)*(p+1)字符不为'*',则只需比较*s字符与*p字符,若相等则递归到*(s+1)字符串与*(p+1)字符串的比较,否则无法匹配。

(2)*(p+1)字符为'*',则*p字符可以匹配*s字符串中从0开始任意多(记为i)等于*p的字符,然后递归到*(s+i+1)字符串与*(p+2)字符串的比较,

AC代码:

class Solution {
public:
    static const int FRONT=-1;
    bool isMatch(string s, string p) {
        return myMatch(s,s.length()-1,p,p.length()-1);
    }
    bool myMatch(string s, int i, string p,int j)
    {
        if(j == FRONT)
            if(i == FRONT)    return true;
        else return false;
        if(p[j] == '*')
        {
            if(i > FRONT && (p[j-1] == '.' || p[j-1] == s[i]))
                if(myMatch(s,i-1,p,j))
                    return true;
            return myMatch(s,i,p,j-2);
        }
        if(p[j] == '.' || p[j] == s[i])
            return myMatch(s,i-1,p,j-1);
        return false;
    }
};

发表新评论