SENI #031
SENI #031
SENI 031
Ini adalah pasal 31
SENI adalah kegiatan yang diprakarsai oleh
由左耳朵耗子--陈皓: Kerjakan setidaknya satu pertanyaan algoritma leetcode setiap minggu, baca dan komentari setidaknya satu artikel teknis berbahasa Inggris, pelajari setidaknya satu keterampilan teknis, dan bagikan artikel yang berisi opini dan pemikiran. (Artinya, Algoritma, Review, Tip, dan Share disebut sebagai SENI).
Pertanyaan algoritma algoritma
9. Jumlah palindrom
Kesulitan: Mudah
Tentukan apakah bilangan bulat termasuk palindrom. Bilangan palindrom adalah bilangan bulat yang bacaannya sama dalam urutan maju (dari kiri ke kanan) dan urutan terbalik (dari kanan ke kiri).
Contoh 1:
输入: 121
输出: true
Contoh 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
Contoh 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
Lanjutan:
Bisakah Anda menyelesaikan masalah ini tanpa mengubah bilangan bulat menjadi string?
Solusi
Bahasa: 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. Pencocokan ekspresi reguler
Kesulitan: Kesulitan
Diberikan string (s) dan pola karakter (p). Terapkan pencocokan ekspresi reguler yang mendukung '.' dan '*'.
'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。
Kecocokan harus mencakup seluruh string (s), bukan sebagian.
Deskripsi:
sboleh kosong dan hanya berisi huruf kecil daria-z.pboleh kosong dan hanya berisi huruf kecil daria-z, serta karakter.dan*.
Contoh 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
Contoh 2:
输入:
s = "aa"
p = "a*"
输出: true
解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。
Contoh 3:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。
Contoh 4:
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。
Contoh 5:
输入:
s = "mississippi"
p = "mis*is*p*."
输出: false```
#### Solusi
Bahasa: **C**
Batas waktu metode 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);
}
Metode 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);
}
}
Metode 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. Wadah yang menampung air paling banyakSalinan untuk Penurunan Harga
Kesulitan: Sedang
Diberikan n bilangan bulat non-negatif a<sub style=“display: inline;”>1</sub>, a<sub style=“display: inline;”>2, </sub>…, a<sub style=“display: inline;”>n,</sub> setiap bilangan mewakili sebuah titik pada koordinat (i, a<sub style=“display: inline;”>i</sub>). Gambarlah n garis vertikal di dalam koordinat. Dua titik ujung garis vertikal i adalah (i, a<sub style=“display: inline;”>i</sub>) dan (i, 0). Carilah dua garis sedemikian rupa sehingga wadah yang dibentuknya dengan sumbu x dapat menampung air paling banyak.
Catatan: Anda tidak dapat memiringkan wadah dan nilai n minimal 2.
<small style=“display: inline;”>Garis vertikal pada gambar mewakili array input [1,8,6,2,5,4,8,3,7]. Dalam hal ini, nilai maksimum air (ditunjukkan dengan warna biru) yang dapat ditampung wadah adalah 49. </small>
Contoh:
输入: [1,8,6,2,5,4,8,3,7]
输出: 49```
#### Solusi
Bahasa: **C**
Metode 1 adalah yang paling lambat:
```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;
}
Metode 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;
}
Metode 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;
}
Metode 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. Ubah bilangan bulat menjadi angka romawi
Kesulitan: Sedang
Angka Romawi mencakup tujuh karakter berikut: I, V, X, L, C, D dan M.
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000```
Misalnya, angka Romawi 2 ditulis `II`, yaitu dua angka 1 yang sejajar. 12 ditulis sebagai `XII`, yaitu `X` + `II`. 27 ditulis `XXVII`, yaitu `XX` + `V` + `II`.
Biasanya, angka yang lebih kecil pada angka romawi berada di sebelah kanan angka yang lebih besar. Tapi ada kasus khusus. Misalnya, 4 tidak ditulis sebagai `IIII`, tetapi sebagai `IV`. Angka 1 berada di sebelah kiri angka 5 dan mewakili angka yang sama dengan angka yang lebih besar 5 dikurangi angka yang lebih kecil 1 untuk mendapatkan angka 4 . Begitu pula dengan angka 9 yang direpresentasikan sebagai `IX`. Aturan khusus ini hanya berlaku pada enam situasi berikut:
* `I` dapat ditempatkan di sisi kiri `V` (5) dan `X` (10) untuk mewakili 4 dan 9.
* `X` dapat ditempatkan di sisi kiri `L` (50) dan `C` (100) untuk mewakili 40 dan 90.
* `C` dapat ditempatkan di sisi kiri `D` (500) dan `M` (1000) untuk mewakili 400 dan 900.
Jika diberi bilangan bulat, ubahlah menjadi angka Romawi. Pastikan inputnya berada pada rentang 1 hingga 3999.
**Contoh 1:**
输入: 3 输出: “III”```
Contoh 2:
输入: 4
输出: "IV"```
**Contoh 3:**
输入: 9 输出: “IX”```
Contoh 4:
输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.
Contoh 5:
输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.```
#### Solusi
Bahasa: **C**
```c
char * intToRoman(int num){
}
Ulasan
Kiat
Bagikan
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