ARTS 031
这是第31篇
ARTS是
由左耳朵耗子--陈皓发起的一个活动: 每周至少做一个leetcode的算法题、阅读并点评至少一篇英文技术文章、学习至少一个技术技巧、分享一篇有观点和思考的文章。（也就是Algorithm、Review、Tip、Share简称ARTS）。
Algorihm 算法题
9. 回文数
Difficulty: 简单
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶:
你能不将整数转为字符串来解决这个问题吗？
Solution
Language: C
bool isPalindrome(int x){
if (x < 0) {
return false;
}
int bak = x;
int tem = 0;
while (x !=0) {
tem = 10 *tem + x%10;
x = x / 10;
}
if (tem == bak) {
return true;
}
return false;
}
10. 正则表达式匹配
Difficulty: 困难
给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ，而不是部分字符串。
说明:
s可能为空，且只包含从a-z的小写字母。p可能为空，且只包含从a-z的小写字母，以及字符.和*。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。
示例 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。
示例 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。
示例 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false```
#### Solution
Language: **C**
方法1 超时：
```c
bool isMatch(char * s, char * p){
if (strlen(p) ==0)
return strlen(s) == 0;
if (strlen(p) == 1) {
return (strlen(s) == 1 && (s[0] == p[0] || p[0] == '.'));
}
if (p[1] != '*') {
if (strlen(s) == 0) return false;
return (s[0] == p[0] || p[0] == '.') && isMatch(s++, p++);
}
while ((strlen(s) != 0) && (s[0] == p[0] || p[0] == '.')) {
if (isMatch(s, p+2)) return true;
s = s + 1;
}
return isMatch(s, p+2);
}
方法2：
bool isMatch(char * s, char * p) {
if (strlen(p) == 0) return strlen(s) == 0;
if (strlen(p) > 1 && p[1] == '*') {
return isMatch(s, p+2) || ((strlen(s) != 0) && (s[0] == p[0] || p[0] == '.') && isMatch(s+1, p));
} else {
return (strlen(s) != 0) && (s[0] == p[0] || p[0] == '.') && isMatch(s+1, p+1);
}
}
方法3：
bool isMatch(char * s, char * p) {
int m = strlen(s), n = strlen(p);
int **dp = malloc((m + 1) * sizeof(int *));
for (int i = 0; i < m + 1; i++) {
int *table = malloc( (n + 1) * sizeof(int));
dp[i] = table;
}
for (int i = 0; i < m + 1; i++) {
for (int j = 0; j <n + 1; j++) {
dp[i][j] = false;
}
}
dp[0][0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (j > 1 && p[j - 1] == '*') {
dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);
} else {
dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
}
}
}
return dp[m][n];
}
11. 盛最多水的容器Copy for Markdown
Difficulty: 中等
给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49```
#### Solution
Language: **C**
方法1 最慢：
```c
int maxArea(int* height, int heightSize){
int max = 0;
for (int i = 0; i < heightSize; i++) {
int m = height[i];
for (int j = i+1; j < heightSize; j++) {
int n = height[j];
int min =m;
if (min>n) {
min = n;
}
int tmpmax = min * (j - i);
if (tmpmax > max) {
max = tmpmax;
}
}
}
return max;
}
方法2
//376 ms
int maxArea(int* height, int heightSize){
int max = 0;
int m = 0;
for (int i = 0; i < heightSize; i++) {
if (height[i] > m) {
m=height[i];
}
else{
continue;
}
for (int j = i+1; j < heightSize; j++) {
int n = height[j];
int min =m;
if (min>n) {
min = n;
}
int tmpmax = min * (j - i);
if (tmpmax > max) {
max = tmpmax;
}
}
}
return max;
}
方法3
执行用时为 4 ms 的范例
int maxArea(int* height, int heightSize) {
int maxarea=0,left=0,right=heightSize-1;
int area=0;
while(left<right)
{
if(height[left]<height[right])
{ area=height[left]*(right-left);
left++;
if(area>maxarea)
maxarea=area;
}else
{
area=height[right]*(right-left);
right--;
if(area>maxarea)
maxarea=area;
}
}
return maxarea;
}
方法4
执行用时为 8 ms 的范例
int maxArea(int* height, int heightSize)
{
int min = 0, max = heightSize - 1;
int area_max = 0;
while (min < max) {
int area = (max - min) * (height[min] < height[max] ? height[min] : height[max]);
area_max = area > area_max ? area : area_max;
if (height[min] < height[max]) {
while (++min < max && height[min] <= height[min - 1]) {
continue;
}
} else {
while (min < --max && height[max] <= height[max + 1]) {
continue;
}
}
}
return area_max;
}
12. 整数转罗马数字
Difficulty: 中等
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000```
例如， 罗马数字 2 写做 `II` ，即为两个并列的 1。12 写做 `XII` ，即为 `X` + `II` 。 27 写做 `XXVII`, 即为 `XX` + `V` + `II` 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 `IIII`，而是 `IV`。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 `IX`。这个特殊的规则只适用于以下六种情况：
* `I` 可以放在 `V` (5) 和 `X` (10) 的左边，来表示 4 和 9。
* `X` 可以放在 `L` (50) 和 `C` (100) 的左边，来表示 40 和 90。
* `C` 可以放在 `D` (500) 和 `M` (1000) 的左边，来表示 400 和 900。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。
**示例 1:**
输入: 3 输出: “III”```
示例 2:
输入: 4
输出: "IV"```
**示例 3:**
输入: 9 输出: “IX”```
示例 4:
输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.
示例 5:
输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.```
#### Solution
Language: **C**
```c
char * intToRoman(int num){
}
