ARTES #031
ARTES #031
##ARTES 031
este es el articulo 31
ARTES es una actividad iniciada por
由左耳朵耗子--陈皓: Haga al menos una pregunta sobre el algoritmo leetcode cada semana, lea y comente al menos un artículo técnico en inglés, aprenda al menos una habilidad técnica y comparta un artículo con opiniones y pensamientos. (Es decir, Algoritmo, Revisión, Consejo y Compartir se denominan ARTS).
Pregunta sobre el algoritmo del algoritmo
9. Número de palíndromos
Dificultad: Fácil
Determina si un número entero es un palíndromo. Un número palíndromo es un número entero que se lee igual en orden directo (de izquierda a derecha) y en orden inverso (de derecha a izquierda).
Ejemplo 1:
输入: 121
输出: true
Ejemplo 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
Ejemplo 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
Avanzado:
¿Puedes resolver este problema sin convertir el número entero en una cadena?
Solución
Idioma: 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. Coincidencia de expresiones regulares
Dificultad: Dificultad
Dada una cadena (s) y un patrón de caracteres (p). Implemente una coincidencia de expresiones regulares que admita '.' y '*'.
'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。
La coincidencia debe cubrir toda la cadena (s), no parte de ella.
Descripción:
spuede estar vacío y contener solo letras minúsculas dea-z.ppuede estar vacío y contener solo letras minúsculas dea-zy los caracteres.y*.
Ejemplo 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
Ejemplo 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。
Ejemplo 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。
Ejemplo 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。
Ejemplo 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false```
#### Solución
Idioma: **C**
Tiempo de espera del método 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);
}
Método 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);
}
}
Método 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. El contenedor que contiene más aguaCopiar para Markdown
Dificultad: Media
Dados n enteros no negativos a<sub style=“display: inline;”>1</sub>, a<sub style=“display: inline;”>2, </sub>…, a<sub style=“display: inline;”>n,</sub> cada número representa un punto en las coordenadas (i, a<sub style=“display: inline;”>i</sub>). Dibuja n líneas verticales dentro de las coordenadas. Los dos puntos finales de la línea vertical i son (i, a<sub style=“display: inline;”>i</sub>) y (i, 0). Encuentra las dos líneas tales que el recipiente que forman con el eje x pueda contener la mayor cantidad de agua.
Nota: No puedes inclinar el contenedor y el valor de n es al menos 2.
<small style=“display: inline;”>Las líneas verticales en la figura representan la matriz de entrada [1,8,6,2,5,4,8,3,7]. En este caso, el valor máximo de agua (que se muestra en azul) que puede contener el recipiente es 49. </small>
Ejemplo:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49```
#### Solución
Idioma: **C**
El método 1 es el más lento:
```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;
}
Método 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;
}
Método 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;
}
Método 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. Convertir número entero a número romano
Dificultad: Media
Los números romanos incluyen los siguientes siete caracteres: I, V, X, L, C, D y M.
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000```
Por ejemplo, el número romano 2 se escribe `II`, que son dos unos paralelos. 12 está escrito como `XII`, que es `X` + `II`. 27 está escrito como `XXVII`, que es `XX` + `V` + `II`.
Normalmente, los números más pequeños en números romanos están a la derecha de los números más grandes. Pero hay casos especiales. Por ejemplo, 4 no se escribe como `IIII`, sino como `IV`. El número 1 está a la izquierda del número 5 y representa un número igual al número mayor 5 menos el número menor 1 para obtener el número 4. Asimismo, el número 9 se representa como `IX`. Esta regla especial sólo se aplica a las seis situaciones siguientes:
* `I` se puede colocar en el lado izquierdo de `V` (5) y `X` (10) para representar 4 y 9.
* `X` se puede colocar en el lado izquierdo de `L` (50) y `C` (100) para representar 40 y 90.
* `C` se puede colocar en el lado izquierdo de `D` (500) y `M` (1000) para representar 400 y 900.
Dado un número entero, conviértalo a números romanos. Asegúrese de que la entrada esté en el rango de 1 a 3999.
**Ejemplo 1:**
输入: 3 输出: “III”```
Ejemplo 2:
输入: 4
输出: "IV"```
**Ejemplo 3:**
输入: 9 输出: “IX”```
Ejemplo 4:
输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.
Ejemplo 5:
输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.```
#### Solución
Idioma: **C**
```c
char * intToRoman(int num){
}
Revisión
Consejos
Compartir
What to read next
Want more posts about ARTS?
Posts in the same category are usually the best next step for reading more on this topic.
View same categoryWant to keep following #iOS?
Tags are useful for related tools, specific problems, and similar troubleshooting notes.
View same tagWant to explore another direction?
If you are not sure what to read next, return to the homepage and start from categories, topics, or latest updates.
Back home