LeetCode C言語版詳細(6-10)
27726 ワード
LeetCode C言語版詳細(6-10)
6 Z字反転
指定された文字列は、指定された行数に基づいて、上から下へ、左から右へZ字状に並べられます.
たとえば、入力文字列が「LEETCODEISHIRING」の行数が3の場合、以下のように並べられます.
その後、あなたの出力は左から右へ行を追って読み取り、「LCIRETOESIIIGEDHN」などの新しい文字列を生成する必要があります.
文字列を指定した行数変換する関数を実装してください.
string convert(string s, int numRows); 例1:
入力:s="LEETCODEISHIRING"、numRows=3出力:「LCIRETOESIIIGEDHN」例2:
入力:s=“LEETCODEISHIRING”,numRows=4出力:“LDREOEIECIHNTSG”解釈:
ネット上でまた法則を探して、私が使った値は最も暴力的で1つの2次元の配列の中で存在して、それから直接取得します
7整数反転
32ビットのシンボル付き整数を与えます.この整数の各ビットの数字を反転する必要があります.
例1:
入力:123出力:321例2:
入力:-123出力:-321例3:
入力:120出力:21注意:
我々の環境では32ビット以下の符号付き整数しか記憶できないと仮定すると,その数値範囲は[−231,231−1]である.この仮定に基づいて、反転後に整数がオーバーフローした場合は0を返します.
この問題は難しくありません.注意しなければならないのは反転後の整数オーバーフローがゼロに戻ることです.私はその時考えていませんでしたが、合格しませんでした.の
8文字列変換整数(atoi)
文字列を整数に変換できるようにatoi関数を実装してください.
まず、この関数は、必要に応じて、最初の非スペース文字が見つかるまで、不要な先頭スペース文字を破棄します.
私たちが探した最初の非空の文字が正または負の記号である場合、この記号を後面のできるだけ多くの連続数字と組み合わせて、整数の正負の記号とします.最初の空白以外の文字が数値である場合、その後の連続する数値文字と直接組み合わせて整数を形成します.
この文字列には、有効な整数部分に加えて、関数に影響を与えるべきではない無視できる余分な文字が存在する可能性があります.
注意:この文字列の最初の非スペース文字が有効な整数文字でない場合、文字列が空である場合、または文字列に空白文字のみが含まれている場合、関数を変換する必要はありません.
いずれの場合も、関数が有効な変換ができない場合は、0を返します.
説明:
我々の環境では32ビットサイズの符号付き整数しか記憶できないと仮定すると,その数値範囲は[−231,231−1]である.数値がこの範囲を超えた場合、qingはINT_を返します.MAX(231−1)またはINT_MIN (−231) .
例1:
入力:42出力:42例2:
入力:「-42」出力:-42解釈:最初の空白以外の文字は「-」で、マイナス記号です.負の記号をできるだけ後ろに連続して現れるすべての数字と組み合わせて、最後に-42を得ます.例3:
入力:“4193 with words”出力:4193解釈:変換は数字“3”に締め切られ、次の文字は数字ではないためである.例4:
入力:「words and 987」出力:0解釈:最初の非空文字は「w」ですが、数字や正、負の記号ではありません.したがって、有効な変換は実行できません.例5:
入力:「-9183472332」出力:-2174848648解釈:数字「-9183472332」が32ビットの符号付き整数範囲を超えた.よってINT_を返すMIN (−231) .
注意テストの例があります(あるだけでなく)
9回文数
整数が文数であるかどうかを判断します.回文数とは、正の順序(左から右へ)と逆の順序(右から左へ)が同じ整数です.
例1:
入力:121出力:true例2:
入力:-121出力:false解釈:左から右へ-121です.右から左に読むと121-.したがって、回文数ではありません.例3:
入力:10出力:false解釈:右から左へ、01です.したがって、回文数ではありません.
10正規表現の一致
文字列sと文字法則pをあげて、サポート'.'を実現してください.「*」の正規表現と一致します.
‘.’ 任意の単一文字'*'を一致させるゼロまたは複数の前の要素を一致させるいわゆる一致は、文字列s全体をカバーし、一部の文字列ではありません.
説明:
sは空であり、a−zからの小文字のみを含む可能性がある.pは空である可能性があり、a-zからの小文字と文字のみを含む.と*です.例1:
入力:s=「aa」p=「a」出力:false解釈:「a」は「aa」文字列全体に一致しません.例2:
入力:s=「aa」p=「a*」出力:true解釈:「*」はゼロまたは複数の前の要素に一致することができるため、ここで前の要素は「a」である.したがって、文字列「aa」は、「a」が1回繰り返されたものと見なすことができる.例3:
入力:s="ab"p="."出力:true解釈:"."0文字以上('*')の任意の文字('.')が一致することを示します.例4:
入力:s=「aab」p=「cab」出力:true解釈:「*」はゼロまたは複数を表すため、ここで「c」は0であり、「a」は1回繰り返される.したがって、文字列「aab」と一致することができます.例5:
入力:s="mississippi"p="misisp*."出力:falseという問題を半年見ました..やっと分かったのは主にダイナミックな計画を使って、しかも後から前へ計画しなければならない.s=「aaa」p=「aa」のような例があるからだ.このように前のaが番号でフィルタリングされたら、後に何個のaが残るか分からない.
6 Z字反転
指定された文字列は、指定された行数に基づいて、上から下へ、左から右へZ字状に並べられます.
たとえば、入力文字列が「LEETCODEISHIRING」の行数が3の場合、以下のように並べられます.
L C I R
E T O E S I I G
E D H N
その後、あなたの出力は左から右へ行を追って読み取り、「LCIRETOESIIIGEDHN」などの新しい文字列を生成する必要があります.
文字列を指定した行数変換する関数を実装してください.
string convert(string s, int numRows); 例1:
入力:s="LEETCODEISHIRING"、numRows=3出力:「LCIRETOESIIIGEDHN」例2:
入力:s=“LEETCODEISHIRING”,numRows=4出力:“LDREOEIECIHNTSG”解釈:
L D R
E O E I I
E C I H N
T S G
ネット上でまた法則を探して、私が使った値は最も暴力的で1つの2次元の配列の中で存在して、それから直接取得します
char * convert(char * s, int numRows){
if (numRows >= (int)strlen(s)) { return s; }//
if (numRows == 1) { return s; }//
int i = 0, j = 0, k = 0; //i ,j
char arr[1001][1001] = { 0 };//
char *arr1 = (char *)malloc(sizeof(char) * 1001);//
memset(arr1, 0, 1001);
while (s[k]) {//
while (i < numRows && s[k]) { arr[i++][j] = s[k++]; }// ,
i -= 2; // n-1
j++;
while (i && s[k]) { arr[i--][j++] = s[k++]; }
}
int ret = 0;
// ,
for (int m = 0; m < numRows; m++) {
for (int n = 0; n < j; n++) {
if (arr[m][n]) {
arr1[ret++] = arr[m][n];
}
}
}
return arr1;
}
7整数反転
32ビットのシンボル付き整数を与えます.この整数の各ビットの数字を反転する必要があります.
例1:
入力:123出力:321例2:
入力:-123出力:-321例3:
入力:120出力:21注意:
我々の環境では32ビット以下の符号付き整数しか記憶できないと仮定すると,その数値範囲は[−231,231−1]である.この仮定に基づいて、反転後に整数がオーバーフローした場合は0を返します.
この問題は難しくありません.注意しなければならないのは反転後の整数オーバーフローがゼロに戻ることです.私はその時考えていませんでしたが、合格しませんでした.の
int reverse(int x){
int num = 0;
while(x)
{
if ((num < INT_MIN/10 ) || (num > INT_MAX/10 ))//
{
return 0;
}
else
{
num *= 10;// , 10,
num += x%10;// x
x/=10;// x
}
}
return num;
}
8文字列変換整数(atoi)
文字列を整数に変換できるようにatoi関数を実装してください.
まず、この関数は、必要に応じて、最初の非スペース文字が見つかるまで、不要な先頭スペース文字を破棄します.
私たちが探した最初の非空の文字が正または負の記号である場合、この記号を後面のできるだけ多くの連続数字と組み合わせて、整数の正負の記号とします.最初の空白以外の文字が数値である場合、その後の連続する数値文字と直接組み合わせて整数を形成します.
この文字列には、有効な整数部分に加えて、関数に影響を与えるべきではない無視できる余分な文字が存在する可能性があります.
注意:この文字列の最初の非スペース文字が有効な整数文字でない場合、文字列が空である場合、または文字列に空白文字のみが含まれている場合、関数を変換する必要はありません.
いずれの場合も、関数が有効な変換ができない場合は、0を返します.
説明:
我々の環境では32ビットサイズの符号付き整数しか記憶できないと仮定すると,その数値範囲は[−231,231−1]である.数値がこの範囲を超えた場合、qingはINT_を返します.MAX(231−1)またはINT_MIN (−231) .
例1:
入力:42出力:42例2:
入力:「-42」出力:-42解釈:最初の空白以外の文字は「-」で、マイナス記号です.負の記号をできるだけ後ろに連続して現れるすべての数字と組み合わせて、最後に-42を得ます.例3:
入力:“4193 with words”出力:4193解釈:変換は数字“3”に締め切られ、次の文字は数字ではないためである.例4:
入力:「words and 987」出力:0解釈:最初の非空文字は「w」ですが、数字や正、負の記号ではありません.したがって、有効な変換は実行できません.例5:
入力:「-9183472332」出力:-2174848648解釈:数字「-9183472332」が32ビットの符号付き整数範囲を超えた.よってINT_を返すMIN (−231) .
注意テストの例があります(あるだけでなく)
:
:
"+1"
0
1
int myAtoi(char * str){
double result = 0;
int flag = 1;// ,
while(*str == ' ')//
str++;
if(*str == '-')//
{
flag = -1;
str++;
}
else if(*str == '+')// , 1, flag
{
str++;
}
while(*str <= '9' && *str >= '0')//
{
result = result * 10 + *(str++) - '0';//
}
if ( result > 2147483647 )//
{
if(flag == 1)
return 2147483647;
else
return 2147483648;
}
return flag * result;
}
9回文数
整数が文数であるかどうかを判断します.回文数とは、正の順序(左から右へ)と逆の順序(右から左へ)が同じ整数です.
例1:
入力:121出力:true例2:
入力:-121出力:false解釈:左から右へ-121です.右から左に読むと121-.したがって、回文数ではありません.例3:
入力:10出力:false解釈:右から左へ、01です.したがって、回文数ではありません.
bool isPalindrome(int x){
long long sum = 0;// ,
int temp = x;// x
if (x < 0)// , , false,
return false;
while(temp)//
{
sum = sum * 10 + ( temp % 10 );
temp = temp/10;
}
if (sum == x)//
{
return true;
}
else
{
return false;
}
}
10正規表現の一致
文字列sと文字法則pをあげて、サポート'.'を実現してください.「*」の正規表現と一致します.
‘.’ 任意の単一文字'*'を一致させるゼロまたは複数の前の要素を一致させるいわゆる一致は、文字列s全体をカバーし、一部の文字列ではありません.
説明:
sは空であり、a−zからの小文字のみを含む可能性がある.pは空である可能性があり、a-zからの小文字と文字のみを含む.と*です.例1:
入力:s=「aa」p=「a」出力:false解釈:「a」は「aa」文字列全体に一致しません.例2:
入力:s=「aa」p=「a*」出力:true解釈:「*」はゼロまたは複数の前の要素に一致することができるため、ここで前の要素は「a」である.したがって、文字列「aa」は、「a」が1回繰り返されたものと見なすことができる.例3:
入力:s="ab"p="."出力:true解釈:"."0文字以上('*')の任意の文字('.')が一致することを示します.例4:
入力:s=「aab」p=「cab」出力:true解釈:「*」はゼロまたは複数を表すため、ここで「c」は0であり、「a」は1回繰り返される.したがって、文字列「aab」と一致することができます.例5:
入力:s="mississippi"p="misisp*."出力:falseという問題を半年見ました..やっと分かったのは主にダイナミックな計画を使って、しかも後から前へ計画しなければならない.s=「aaa」p=「aa」のような例があるからだ.このように前のaが番号でフィルタリングされたら、後に何個のaが残るか分からない.
bool isMatch(char * s, char * p){
int sl = strlen(s);
int pl = strlen(p);
bool dp[sl + 1][pl + 1];
memset(dp, 0, sizeof(dp));
for (int i = sl; i > -1; --i)
{
for (int j = pl; j > -1; --j)
{
if (i == sl && j == pl)
{
dp[i][j] = true;
continue;
}
if (pl - j > 1 && p[j + 1] == '*')// *
{
dp[i][j] = dp[i][j + 2] || (i < sl && (p[j] == '.' || p[j] == s[i]) && dp[i + 1][j]);// * , , , , , . , true
}
else
{
dp[i][j] = i < sl && (p[j] == '.' || p[j] == s[i]) && dp[i + 1][j + 1];// , .
}
}
}
return dp[0][0];// , ,
}