Leetcode初級アルゴリズム文字列C言語解答

Leetcode初級アルゴリズム文字列C言語解答

344. 反転文字列

7. 整数反転

387. 文字列の最初の一意文字

242. 有効なアルファベット異位語

125. 検証文字列

8. 文字列変換整数(atoi)

28. strStr()

を実現

344.文字列の反転

344.文字列の反転

アルゴリズム思想:本アルゴリズムは二重ポインタを採用し、文字列の頭文字と尾文字から始め、頭文字を交換し、配列を遍歴する.

アルゴリズム時間複雑度O(n)

void reverseString(char* s, int sSize) {
    int temp, i, j = sSize-1;
    for(i=0; i<j; i++, j--){
        temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }
    return s;
}

7.整数反転

7.整数反転

アルゴリズム思想:本アルゴリズムは公式の問題解を採用し、毎回最後の数を弾き出して発売し、肝心なのはオーバーフローの状況を判断することである.

アルゴリズム時間複雑度O(logn)

int reverse(int x) {
    int pop, rev = 0;
    while (x != 0) {
        pop = x % 10;
        x /= 10;
        if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7))
        	return 0;
        if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8))
        	return 0;
        rev = rev * 10 + pop;
    }
        return rev;
}

387.文字列の最初の一意の文字

387.文字列の最初の一意の文字

アルゴリズム思想:本アルゴリズムはLeetcode大男たちの解法を採用し、1つの大きさが26配列であることを定義し、「a」~「z」を象徴し、1回の文字列を遍歴し、現れなかったのは0で、1回の置1、複数回の置2が現れ、最後に1回の配列を遍歴して1回目の出現の位置を見る.

アルゴリズム時間複雑度O(n)

int firstUniqChar(char* s) {
    int d[26]={0};
    int temp, i;
    for(i=0; s[i]!='\0'; i++){
        temp = s[i] - 'a';
        d[temp]++;
    }
    for(i=0; s[i]!='\0'; i++){
        temp = s[i] - 'a';
        if(d[temp] == 1)
            return i;
    }
    return -1;
}

242.有効なアルファベット異位語

242.有効なアルファベット異位語

アルゴリズム思想:本アルゴリズムはLeetcode大男たちの解法を採用し、大きさ26配列を定義し、「a」~「z」を象徴し、文字列を2回遍歴し、語周波数を統計して比較する.

アルゴリズム時間複雑度O(n)

bool isAnagram(char* s, char* t) {
    int i, x[26] = { 0 }, y[26] = { 0 };
	for (i = 0; s[i] != '\0'; i++)
        x[s[i] - 'a']++;
	for (i = 0; t[i] != '\0'; i++)
        y[t[i] - 'a']++;
	for (i = 0; i < 26; i++)
		if (x[i] != y[i])
            return false;
	return true;	
}

125.検証文字列

125.検証文字列

アルゴリズム思想:本アルゴリズムは二重ポインタを採用し、首尾ポインタはビットで文字値を比較し始め、肝心なのは有効文字が0-9、a-z、A-Zであり、比較時に大文字と小文字に注意することである.

アルゴリズム時間複雑度O(n)

bool isPalindrome(char* s) {
    size_t i = 0;
    size_t j = strlen(s);
    while(i < j)
        if(s[i] < '0' || (s[i] > '9' && s[i] < 'A') || (s[i] > 'Z' && s[i] < 'a') || s[i] > 'z')
            i++;
        else if(s[j] < '0' || (s[j] > '9' && s[j] < 'A') || (s[j] > 'Z' && s[j] < 'a') || s[j] > 'z')
            j--;
        else
            if (tolower(s[i]) != tolower(s[j])){
                return false;                
            }

            else{
                i++;
                j--;
            }
    return true;
}

8.文字列変換整数(atoi)

8.文字列変換整数(atoi)

アルゴリズム思想:本アルゴリズムは主に各種シーン、開始のスペース、出現する可能性のある記号、後続の境界値判断を考慮する.

アルゴリズム時間複雑度O(n)

int myAtoi(char* str) {
    int i=0, flag=1;
    while (str[i]==' ')
        i++;
    if (str[i] == '-'){
        flag=-1;
        i++;
    }
    else if (str[i] == '+')
        i++;
    double temp = 0;
    while (str[i] != '\0'){
        if(str[i]<'0'||str[i]>'9')
            break;
        else
            temp = temp*10+str[i]-'0';
        i++;
    }
    if (temp > INT_MAX)
        if(flag==-1)
            return INT_MIN;
        else
            return INT_MAX;
    else
        return temp * flag;
}

28.strStr()の実装

28.strStr()の実装

アルゴリズムの思想:本アルゴリズムの実現は1つは暴力的な解読であり、アルゴリズムの実現は2つは有名なKMPアルゴリズムである.

暴力解読時間複雑度O(nm)、KMPアルゴリズム時間複雑度O(n+m)

int strStr(char* haystack, char* needle) {
    if(*needle=='\0')
        return 0;
    else if(*haystack=='\0')
        return -1;
    int a_len=strlen(haystack),b_len=strlen(needle),i=0,j=0;
    if(a_len<b_len)
        return -1;
    for(i=0;i<=a_len-b_len;i++){
        for(j=0;j<b_len;j++){
            if(*(haystack+i+j)==*(needle+j))
                continue;  
            else
                break;
        }
        if(j==b_len && *(haystack+i+j-1)==*(needle+j-1))
            return i;
    }
    
        return -1;
}

int strStr(char* haystack, char* needle) {
    if(*needle=='\0')
        return 0;
    else if(*haystack=='\0')
        return -1;
    int nlen = strlen(needle);
    int* next[nlen];
    cal_next(needle, next);
    return KMP(haystack, needle, next);
}

void cal_next(char* str, int* next){
    int i, j;
    int len = strlen(str);
    next[0] = -1;
  for(i = 1; i < len; i++){
    j = next[i - 1];
    while(str[j + 1] != str[i] && (j >= 0))
      j = next[j];
    if( str[i] == str[j + 1])
      next[i] = j + 1;
    else
      next[i] = -1;
  }
}
 
int KMP( char * str, char * ptr, int * next ){
    int s_i = 0, p_i = 0;
    int plen = strlen(ptr);
    int slen = strlen(str);
    while( s_i < slen && p_i < plen ){
        if( str[ s_i ] == ptr[ p_i ] ){
            s_i++;
             p_i++;
        }
        else{
            if( p_i == 0 )
                s_i++;
            else
                p_i = next[ p_i - 1 ] + 1;
        }
    }
    return ( p_i == plen ) ? ( s_i - plen ) : -1;
}