ARTS #031

ARTS 031

This is article 31

ARTS is an activity initiated by 由左耳朵耗子--陈皓: Do at least one leetcode algorithm question every week, read and comment on at least one English technical article, learn at least one technical skill, and share an article with opinions and thoughts. (That is, Algorithm, Review, Tip, and Share are referred to as ARTS).

Algorihm algorithm question

9. Number of palindromes

Difficulty: Easy

Determine whether an integer is a palindrome. A palindrome number is an integer that reads the same in forward order (from left to right) and reverse order (from right to left).

Example 1:

输入: 121
输出: true

Example 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

Example 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

Advanced:

Can you solve this problem without converting the integer to a string?

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. Regular expression matching

Difficulty: Difficulty

Given a string (s) and a character pattern (p). Implement regular expression matching that supports '.' and '*'.

'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。

The match should cover the entire string (s), not part of it.

Description:

• s may be empty and contain only lowercase letters from a-z.
• p may be empty and contain only lowercase letters from a-z, and the characters . and *.

Example 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

Example 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。

Example 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。

Example 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。

Example 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false```


#### Solution

Language: **C**

Method 1 timeout:

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

​
​

Method 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);
    }
}
​
​

Method 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. The container holding the most waterCopy for Markdown

Difficulty: Medium

Given n non-negative integers a<sub style=“display: inline;”>1</sub>, a<sub style=“display: inline;”>2, </sub>…, a<sub style=“display: inline;”>n,</sub> each number represents a point in the coordinates (i, a<sub style=“display: inline;”>i</sub>). Draw n vertical lines within the coordinates. The two endpoints of the vertical line i are (i, a<sub style=“display: inline;”>i</sub>) and (i, 0). Find the two lines such that the container they form with the x axis can hold the most water.

Note: You cannot tilt the container and the value of n is at least 2.

<small style=“display: inline;”>The vertical lines in the figure represent the input array [1,8,6,2,5,4,8,3,7]. In this case, the maximum value of water (shown in blue) that the container can hold is 49. </small>

Example:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49```


#### Solution

Language: **C**


Method 1 is the slowest:

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

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

​

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


​

Method 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. Convert integer to Roman numeral

Difficulty: Medium

Roman numerals include the following seven characters: I, V, X, L, C, D and M.

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000```

For example, the Roman numeral 2 is written as `II`, which is two parallel 1s. 12 is written as `XII`, which is `X` + `II`. 27 is written as `XXVII`, which is `XX` + `V` + `II`.

Typically, smaller numbers in Roman numerals are to the right of larger numbers. But there are special cases. For example, 4 is not written as `IIII`, but as `IV`. The number 1 is to the left of the number 5 and represents a number equal to the larger number 5 minus the smaller number 1 to get the number 4 . Likewise, the number 9 is represented as `IX`. This special rule only applies to the following six situations:

* `I` can be placed on the left side of `V` (5) and `X` (10) to represent 4 and 9.
* `X` can be placed on the left side of `L` (50) and `C` (100) to represent 40 and 90. 
* `C` can be placed on the left side of `D` (500) and `M` (1000) to represent 400 and 900.

Given an integer, convert it to Roman numerals. Make sure the input is in the range 1 to 3999.

**Example 1:**

输入: 3 输出: “III”```

Example 2:

输入: 4
输出: "IV"```

**Example 3:**

输入: 9 输出: “IX”```

Example 4:

输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

Example 5:

输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.```


#### Solution

Language: **C**

```c
​
​
char * intToRoman(int num){
​
}
​
​

Review

Tips

Share