leetcode 6-10题题解 - dblank

# 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.

## 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


*好可以代表任意个它前面字符
.可以代表任意字符

## 思路：

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;
}
};