ARTES #031
ARTES #031
ARTES 031
Este é o artigo 31
ARTS é uma atividade iniciada por
由左耳朵耗子--陈皓: Faça pelo menos uma pergunta sobre o algoritmo leetcode toda semana, leia e comente pelo menos um artigo técnico em inglês, aprenda pelo menos uma habilidade técnica e compartilhe um artigo com opiniões e pensamentos. (Ou seja, Algoritmo, Revisão, Dica e Compartilhamento são chamados de ARTS).
Pergunta sobre algoritmo de algoritmo
9. Número de palíndromos
Dificuldade: Fácil
Determine se um número inteiro é um palíndromo. Um número palíndromo é um número inteiro que lê o mesmo na ordem direta (da esquerda para a direita) e na ordem inversa (da direita para a esquerda).
Exemplo 1:
输入: 121
输出: true
Exemplo 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
Exemplo 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
Avançado:
Você pode resolver esse problema sem converter o número inteiro em uma string?
Solução
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. Correspondência de expressão regular
Dificuldade: Dificuldade
Dada uma string (s) e um padrão de caracteres (p). Implemente a correspondência de expressões regulares compatível com '.' e '*'.
'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。
A correspondência deve cobrir toda a string (s), e não parte dela.
Descrição:
spode estar vazio e conter apenas letras minúsculas dea-z.ppode estar vazio e conter apenas letras minúsculas dea-ze os caracteres.e*.
Exemplo 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
Exemplo 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。
Exemplo 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。
Exemplo 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。
Exemplo 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false```
#### Solução
Idioma: **C**
Tempo limite do 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. O contêiner que contém mais águaCópia para Markdown
Dificuldade: Média
Dados n inteiros não 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 um ponto nas coordenadas (i, a<sub style=“display: inline;”>i</sub>). Desenhe n linhas verticais dentro das coordenadas. Os dois pontos finais da linha vertical i são (i, a<sub style=“display: inline;”>i</sub>) e (i, 0). Encontre as duas linhas de modo que o recipiente que elas formam com o eixo x possa reter mais água.
Observação: Você não pode inclinar o contêiner e o valor de n é pelo menos 2.
<small style=“display: inline;”>As linhas verticais na figura representam a matriz de entrada [1,8,6,2,5,4,8,3,7]. Neste caso, o valor máximo de água (mostrado em azul) que o recipiente pode conter é 49. </small>
Exemplo:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49```
#### Solução
Idioma: **C**
O método 1 é o mais 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. Converter número inteiro em algarismo romano
Dificuldade: Média
Os algarismos romanos incluem os seguintes sete caracteres: I, V, X, L, C, D e M.
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000```
Por exemplo, o numeral romano 2 é escrito como `II`, que são dois 1s paralelos. 12 é escrito como `XII`, que é `X` + `II`. 27 é escrito como `XXVII`, que é `XX` + `V` + `II`.
Normalmente, os números menores em algarismos romanos estão à direita dos números maiores. Mas existem casos especiais. Por exemplo, 4 não é escrito como `IIII`, mas como `IV`. O número 1 está à esquerda do número 5 e representa um número igual ao número maior 5 menos o número menor 1 para obter o número 4. Da mesma forma, o número 9 é representado como `IX`. Esta regra especial aplica-se apenas às seguintes seis situações:
* `I` pode ser colocado no lado esquerdo de `V` (5) e `X` (10) para representar 4 e 9.
* `X` pode ser colocado no lado esquerdo de `L` (50) e `C` (100) para representar 40 e 90.
* `C` pode ser colocado no lado esquerdo de `D` (500) e `M` (1000) para representar 400 e 900.
Dado um número inteiro, converta-o em algarismos romanos. Certifique-se de que a entrada esteja no intervalo de 1 a 3999.
**Exemplo 1:**
输入: 3 输出: “III”```
Exemplo 2:
输入: 4
输出: "IV"```
**Exemplo 3:**
输入: 9 输出: “IX”```
Exemplo 4:
输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.
Exemplo 5:
输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.```
#### Solução
Idioma: **C**
```c
char * intToRoman(int num){
}
Revisão
Dicas
Compartilhar
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