刷題是應屆生找工作不可缺少的部分,一種公認的刷題策略是按類別刷題,可是每個類別也有許多題,在有限的時間里到底該刷哪些題呢?個人根據LeetCode官方給出的每個題目的出現頻率,整理并收錄了每個類別里高頻出現的題目,對于官方統計頻率太低的題目,不予收錄。

整理了下力扣中字符串的高頻題目,題目名稱后面括號里的數字表示的是出現頻率,當時做題的時候順便把相似的題目也做了。有些題目思路確實不好想,需要多多思考。有些題目看了幾遍也沒有看懂,比如外觀序列這個,先放著。題目以后還會更新一些。

棧實現

20. 有效的括號(0.412)

??給定一個只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判斷字符串是否有效。

??有效字符串需滿足:

??左括號必須用相同類型的右括號閉合。 ??左括號必須以正確的順序閉合。 ??注意空字符串可被認為是有效字符串。

示例 1: 輸入: “()” 輸出: true 示例 2: 輸入: “()[]{}” 輸出: true 示例 3: 輸入: “(]” 輸出: false 示例 4: 輸入: “([)]” 輸出: false 示例 5: 輸入: “{[]}” 輸出: true

/*這是一道很簡單的題目,用?？梢院茌p松的實現當左括號出現的時候入棧,當右括號出現的出棧,如果匹配就繼續,不匹配就錯誤當字符串遍歷完成之后,棧內仍有字符串就錯誤用一個數組進行和一個記錄棧頂值的int進行了棧的模擬,代碼很簡單,很好理解(雖說題目也很簡單就是了)*/bool isValid(char * s){       int len = strlen(s);    char stack[3500];    int top = -1;    int i = 0;    for( i=0;i<len;i++)    {      if((s[i] == '(')||(s[i] == '{')||(s[i] == '['))        stack[++top] = s[i];      else        {               if(top<0)//出現了右括號,但數組為空,即沒有左括號與之匹配                return false;                if((s[i] == ')'))                {                     if(stack[top]!='(') return false;                     else top--;                }             if((s[i] == '}'))               {              if(stack[top]!='{') return false;               else top--;             }                    if((s[i] == ']'))              {              if(stack[top]!='[') return false;                else top--;            }        }       }    if(top>=0) //數組內仍有左括號,沒有右括號與之匹配        return false;        //這里一定要有返回值         return true;}

22. 括號生成

??數字 n 代表生成括號的對數,請你設計一個函數,用于能夠生成所有可能的并且 有效的 括號組合。

示例: 輸入:n = 3 輸出:[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]

回溯算法,以后再看

/** * Note: The returned array must be malloced, assume caller calls free(). *//** * Note: The returned array must be malloced, assume caller calls free(). */ void generate(char *item,int index,int left,int right,char **result,int *count,int n) {     if(left==0&&right==0)//已經全部插滿了        {            result[(*count)]=(char*)malloc(sizeof(char)*(2*n+1));            strcpy(result[(*count)++],item);            return;        }        //result[(*count)++][]=item;        item[index]='(';//插入左括號        item[index+1]='';        if(left>0)        generate(item,index+1,left-1,right,result,count,n);        if(right>left)//待插入右括號的個數多余待插入左括號的個數        {            item[index]=')';//插入右括號            generate(item,index+1,left,right-1,result,count,n);        } }char ** generateParenthesis(int n, int* returnSize){    //左右括號的總個數    int left=n,right=n;    int length=2*2*n;    int count=0;//記錄已經插入的個數    int index=0;//記錄當前插入元素的下標    char **result=(char **)malloc(sizeof(char *)*(5000));//創建二維數組    char *item=(char *)malloc(sizeof(char)*(2*n+1));//創建存儲數組    generate(item,index,left,right,result,&count,n);    *returnSize=count;    return result;}

1003. 檢查替換后的詞是否有效

??給定有效字符串 “abc”。

??對于任何有效的字符串 V,我們可以將 V 分成兩個部分 X 和 Y,使得 X + Y(X 與 Y 連接)等于 V。(X 或 Y 可以為空。)那么,X + “abc” + Y 也同樣是有效的。

??例如,如果 S = “abc”,則有效字符串的示例是:“abc”,“aabcbc”,“abcabc”,“abcabcababcc”。無效字符串的示例是:“abccba”,“ab”,“cababc”,“bac”。

??如果給定字符串 S 有效,則返回 true;否則,返回 false。

示例 1: 輸入:“aabcbc” 輸出:true 解釋: 從有效字符串 “abc” 開始。 然后我們可以在 “a” 和 “bc” 之間插入另一個 “abc”,產生 “a” + “abc” + “bc”,即 “aabcbc”。 示例 2: 輸入:“abcabcababcc” 輸出:true 解釋: “abcabcabc” 是有效的,它可以視作在原串后連續插入 “abc”。 然后我們可以在最后一個字母之前插入 “abc”,產生 “abcabcab” + “abc” + “c”,即 “abcabcababcc”。 示例 3: 輸入:“abccba” 輸出:false 示例 4: 輸入:“cababc” 輸出:false 提示: 1 <= S.length <= 20000 S[i] 為 ‘a’、‘b’、或 ‘c’

??題目有點繞,其實原理類似與消消樂,abc相遇會消去,看下最后的字符串是否都可以消完,能消除完全就返回true,不能則返回false。

??本題可以利用棧來解決,思路如下: ??如果字母不為c,則入棧;否則,判斷棧頂是否為ba,如果是則出棧,不是則返回false。當字符串整個處理結束時,判斷棧是否為空,不為空則返回false。

char* stack;int top;void Push(char val){    stack[++top] = val;}void Pop(){     top--;}char Gettop()  {    if(top>=0) return stack[top];    else return '0';}bool isValid(char * S){    int len = strlen(S);    stack = (char*)calloc(sizeof(char), len); top = -1;    for (int i = 0; i < len; i++) {        //入棧        if (S[i] != 'c') {            Push(S[i]);        } else {            //不為b則false            if (Gettop() != 'b')                return false;            Pop();             //不為b則false            if (Gettop() != 'a')                return false;            Pop();        }    }    //如果棧中沒有元素,則為true    if (top < 0)        return true;    return false;}

字符串的加減乘除

??注意要從低位開始進行計算,模擬進位的操作。將字符串的ascii碼-48就可以得到實際的數值。注意計算進位的時候要加上carry。三目運算符的運用可以減少代碼的復雜度。

415. 字符串相加(0.497)

??給定兩個字符串形式的非負整數 num1 和num2 ,計算它們的和。

注意: num1 和num2 的長度都小于 5100. num1 和num2 都只包含數字 0-9. num1 和num2 都不包含任何前導零。 你不能使用任何內建 BigInteger 庫, 也不能直接將輸入的字符串轉換為整數形式。

??因為最大可能就是兩個都是5100個9,進位最多產生2個位,因此加上末尾的’’那么夠多了。 ??注意:不能開函數體內,因為里面res[5103]棧內存,雖然這個夠小完全可以開,但是返回返回結束就小時,再次訪問可能是NULL或者報錯。解決辦法在函數體內用關鍵字static char res[5103],這跟下面代碼放在全局是一樣的。

char res[5103] = {''};char * addStrings(char * num1, char * num2){        short s1 = strlen(num1), s2 = strlen(num2), len = 5101, carry = 0;    for (s1--, s2--; s1 >= 0 || s2 >= 0 || carry;)     {        //長度為0時,數值取0        carry += (s1 >= 0 ? num1[s1--] - 48: 0) + (s2 >= 0 ? num2[s2--] - 48 : 0);  // 最長遍歷處理        res[len--] = carry % 10 + 48;        carry /= 10;    }    return &res[len+1];  // 返回指針,取地址}

67. 二進制求和

題目描述

??給你兩個二進制字符串,返回它們的和(用二進制表示)。 輸入為 非空 字符串且只包含數字 1 和 0。

示例 1: 輸入: a = “11”, b = “1” 輸出: “100” 示例 2: 輸入: a = “1010”, b = “1011” 輸出: “10101” 提示: 每個字符串僅由字符 ‘0’ 或 ‘1’ 組成。 1 <= a.length, b.length <= 10^4 字符串如果不是 “0” ,就都不含前導零。

解題思路

這種不管是十進制的加減還是二進制的加減本質都是一樣的,定義一個carry變量足夠了,只要注意下數組的邊界條件和結束條件,寫對沒問題。

代碼

char * addBinary(char * a, char * b){    int carry = 0;//進位int length = (strlen(a)>strlen(b)? strlen(a)+2:strlen(b)+2);char* result = (char*)malloc(sizeof(char)*length);//開辟空間result[length-1] = '';//多開辟兩個空間 一個存儲進位,一個存儲結束符for(int i = strlen(a)-1,j = strlen(b)-1,k = length -2; (i >=0)||(j >= 0); i--,j--,k--){int sum = carry;sum += (i >= 0? a[i]-'0':0);sum += (j >= 0? b[j]-'0':0);carry = sum /2;result[k] = '0'+ sum % 2;}if(carry == 0)  //最后無進位,直接返回//為什么result+1可以 result[0]+1會報錯return result+1;  else  result[0] = '1';    //有進位,補一個最高位return result;}

簡潔代碼

char * addBinary(char * a, char * b){    int len1 = strlen(a)-1;    int len2 = strlen(b)-1;    int carry = 0;    //多開辟了兩個空間存儲進位和結束符    char*res = (char*)malloc(sizeof(char)*10002);    //倒著開始存儲    int cnt = 10000;    res[10001] = '';    while(len1>=0||len2>=0||carry)    {        //注意判斷數組是否為空        carry +=(len1<0?0:a[len1]-'0')+(len2<0?0:b[len2]-'0');          res[cnt--] = carry%2+48;           carry = carry/2;        //注意判斷結束條件len1 len2        len1 = (len1>=0?len1-1:-1);        len2 = (len2>=0?len2-1:-1);    }        return &res[cnt+1];}

43. 字符串相乘(0.42)

題目描述

??給定兩個以字符串形式表示的非負整數 num1 和 num2,返回 num1 和 num2 的乘積,它們的乘積也表示為字符串形式。

示例 1: 輸入: num1 = “2”, num2 = “3” 輸出: “6” 示例 2: 輸入: num1 = “123”, num2 = “456” 輸出: “56088” 說明: num1 和 num2 的長度小于110。 num1 和 num2 只包含數字 0-9。 num1 和 num2 均不以零開頭,除非是數字 0 本身。 不能使用任何標準庫的大數類型(比如 BigInteger)或直接將輸入轉換為整數來處理。

解題思路

??這道題讓我們求兩個字符串數字的相乘,輸入的兩個數和返回的數都是以字符串格式儲存的,這樣做的原因可能是這樣可以計算超大數相乘,可以不受 int 或 long 的數值范圍的限制,那么該如何來計算乘法呢,小時候都學過多位數的乘法過程,都是每位相乘然后錯位相加,那么這里就是用到這種方法,舉個例子,比如 89 x 76,那么根據小學的算術知識,不難寫出計算過程如下:

    8 9  <- num2    7 6  <- num1-------    5 4  4 8  6 35 6-------6 7 6 4

再寫些例子出來,比如 125 x 48,計算過程如下:

      1 2 5  <- num2        8 8  <- num1-----------        4 0      1 6      8       4 0    1 6    8-----------  1 1 0 0 0

不難發現,以下三點:

??兩數相乘得到的乘積的長度不會超過兩個數字的長度之和,若num1長度為length1,num2 長度為lenght2,則 num1 x num2 的長度不會超過 length1 + length2 ??還有就是乘的時候需要錯位的原因,比如6 x 8得到的 48 為啥要跟6 x 9得到的 54 錯位相加,因為 8 是十位上的數字,其本身相當于80,所以錯開的一位實際上末尾需要補的0 num1 和 num2 中任意位置的兩個數字相乘,得到的兩位數在最終結果中的位置是確定的,比如 num1 中位置為i的數字乘以 num2 中位置為j的數字,那么得到的兩位數字的位置為 i+j 和 i+j+1,這也是由錯位相乘引起的 ??首先開辟兩個空間,一個用來存儲錯位相乘的中間結果,int類型,另外一個作為最終返回的結果,char類型。需要注意的是后一個指針需要比totalLength多一個字符用來在C語言當中指示字符串數組的結束,對于int類型的中間結果初始化為0。

??由于要從個位上開始相乘,所以從 num1 和 num2 字符串的尾部開始往前遍歷,分別提取出對應位置上的字符,將其轉為整型后相乘,將num1[i]與num[j]相乘的結果累加存儲在value[i+j+1]當中,注意這里是累加。以上面的 89 x 76 為例,num1[1] x num2[0]的結果 48 是需要與num1[0] x num2[1]的結果 63相加以后一并存儲在value[2]當中再進入下一步的處理工序的。

??在進入下一道工序之前,我們先看看下面這段代碼運行以后的結果:

for(int i = length1  - 1; i >= 0; i--){    for(int j = length2 - 1; j >= 0; j--)    {        value[i + j + 1] += (num1[i] - '0') * (num2[j] - '0');    }}

??依然以 89 x 76 為例,運行以后value數組的存儲結構如下:

   0     1     2     3 -----------------------|  0  |  56 | 111 |  54 | -----------------------

??后面就是要對value數組進行修改,改保留的保留,改相加的相加,改進位的進位 ,通過以下三行代碼:

   for(int i= totalLength - 1; i > 0; i--)                 //獲取每個位置上面的數字并處理進位   {       value[i - 1] += value[i] / 10;       value[i] %= 10;   }

??最終得到的value數組如下:

   0     1     2     3 -----------------------|  6  |  7  |  6  |  4  | -----------------------

??這三行代碼主要做了兩件事,首先依然從數組的尾部開始遍歷,將第i位的高位通過/累加到第i-1位,然后通過%求余獲得當前位的數字。

??后面在將數字轉化成字符拷貝到待返回的結果之前需要將多余的 0 去掉。

??具體的代碼如下:

代碼

char * multiply(char * num1, char * num2){    int length1 = strlen(num1);    int length2 = strlen(num2);    int totalLength = length1 + length2;                     //獲取相乘后字符串的總有效位數        int charIndex = 0;                                       //定義負責索引字段    int valueIndex = 0;        //int *value = (int *)malloc(sizeof(int) * totalLength);    //memset(value, 0, sizeof(int) * totalLength);    int *value = (int *)calloc(totalLength,sizeof(int));        //char *result = (char *)malloc(sizeof(char) * (totalLength + 1));    char *result =(char *)calloc(totalLength + 1,sizeof(char));            for(int i = length1  - 1; i >= 0; i--)    {        for(int j = length2 - 1; j >= 0; j--)        {            value[i + j + 1] += (num1[i] - '0') * (num2[j] - '0');        }    }     //獲取每個位置上面的數字并處理進位    for(int i= totalLength - 1; i > 0; i--)                    {    //后一個的進位要加到前一個 取商獲得進位        value[i - 1] += value[i] / 10;        //當前位置只保留余數        value[i] %= 10;    }        // //忽略掉前面多余的0,但是最高位也就是唯一的一位0不能忽略    //因為我們設置的最大長度為length1 + length2,并且初始化為了0,實際長度有可能沒有占滿,前面會有多于的0,處理掉    while(value[valueIndex] == 0 && valueIndex < totalLength -1 )     {        valueIndex++;                                           }    //將數值轉化為字符串    while(valueIndex < totalLength)    {        result[charIndex++] = value[valueIndex++] + '0';    }        result[charIndex] = '';                                //默認補上字符串的終止符        return result;        }

2. 兩數相加

??給出兩個 非空 的鏈表用來表示兩個非負的整數。其中,它們各自的位數是按照 逆序 的方式存儲的,并且它們的每個節點只能存儲 一位 數字。

??如果,我們將這兩個數相加起來,則會返回一個新的鏈表來表示它們的和。

??您可以假設除了數字 0 之外,這兩個數都不會以 0 開頭。

示例: 輸入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 輸出:7 -> 0 -> 8 原因:342 + 465 = 807

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     struct ListNode *next; * }; */struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){    struct ListNode* l3 = (struct ListNode*)malloc(sizeof(struct ListNode));    struct ListNode* p1 = l1;    struct ListNode* p2 = l2;     struct ListNode* q = l3;     int carry = 0;    int sum = 0;    while((p1!=NULL) ||(p2!=NULL))    {        sum = 0;        if(p1!=NULL)        {            sum += p1->val;            printf("sum:%drn",sum);        }        if(p2!=NULL)        {            sum += p2->val;            printf("sum:%drn",sum);        }                printf("sum:%d,carry:%drn",sum,carry);        struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));        temp->val = sum%10+carry;        carry = (sum>=10)? 1 : 0;        printf("temp->val:%drn",temp->val);         printf("rn");        temp->next = NULL;        q->next = temp;        q = temp;        p1 = p1->next;        p2 = p2->next;    }    return l3->next;}

最長序列

521. 最長特殊序列 Ⅰ

??給你兩個字符串,請你從這兩個字符串中找出最長的特殊序列。 ??「最長特殊序列」定義如下:該序列為某字符串獨有的最長子序列(即不能是其他字符串的子序列)。 ??子序列 可以通過刪去字符串中的某些字符實現,但不能改變剩余字符的相對順序?？招蛄袨樗凶址淖有蛄?任何字符串為其自身的子序列。 ??輸入為兩個字符串,輸出最長特殊序列的長度。如果不存在,則返回 -1。

示例 1: 輸入: “aba”, “cdc” 輸出: 3 解釋: 最長特殊序列可為 “aba” (或 “cdc”),兩者均為自身的子序列且不是對方的子序列。 示例 2: 輸入:a = “aaa”, b = “bbb” 輸出:3 示例 3: 輸入:a = “aaa”, b = “aaa” 輸出:-1 提示: 兩個字符串長度均處于區間 [1 - 100] 。 字符串中的字符僅含有 ‘a’~‘z’ 。

解題思路

??標簽:題意理解,本題題意難于理解 ??獨有指的是只有自己有,另一個字符串沒有 ??舉例說明,設兩個字符串變量名分別為 a 和 b ??a = ‘c’, b = ‘cd’,‘cd’ 是 b 獨有的,所以最長子序列為 ‘cd’,長度為 2 ??a = ‘cd’, b = ‘cd’, ‘cd’, ‘c’, ‘d’ 在兩個字符串中都有,所以不存在獨有的最長子序列,返回 -1 ??通過舉例分析,得出以下結論: ??如果兩個字符串長度不一樣,則較長的字符串本身不可能是短字符串的子序列,直接返回其長度即可 ??如果兩個字符串內容相等,那么他們獨有的最長子序列不存在,返回 -1

代碼

int findLUSlength(char * a, char * b){  int lenA=strlen(a),lenB=strlen(b);    if (strcmp(a,b)==0)return -1;        return lenA>lenB?lenA:lenB;}

522. 最長特殊序列 II

??給定字符串列表,你需要從它們中找出最長的特殊序列。最長特殊序列定義如下:該序列為某字符串獨有的最長子序列(即不能是其他字符串的子序列)。 ??子序列可以通過刪去字符串中的某些字符實現,但不能改變剩余字符的相對順序?？招蛄袨樗凶址淖有蛄?任何字符串為其自身的子序列。 ??輸入將是一個字符串列表,輸出是最長特殊序列的長度。如果最長特殊序列不存在,返回 -1 。

示例: 輸入: “aba”, “cdc”, “eae” 輸出: 3 提示: 所有給定的字符串長度不會超過 10 。 給定字符串列表的長度將在 [2, 50 ] 之間。

解題思路

思路分析: 請先翻閱 LeetCode 最長特殊序列I 由上一題我們知道判斷兩個字符串的最長特殊序列只要比較兩個字符串是否相等、長度即可, 但是在此道題并不能這樣判斷,因為長度大的字符串可能存在重復(重復了一定不能作為 整個字符串數組的最長特殊序列),長度短的字符串可能是長度大的字符串的子序列。 (比如“ab”是“acbd”的子序列)。所以我們的重新定義兩個字符串是否是子序列的問題。

算法如下: 第一步:將整個字符串數組按照長度降序排序 第二步:統計各個字符串出現的次數 第三步:尋找可以作為整個字符串數組的最長序列

代碼

// 按照字符串長度降序排序// 字符串比較:如果該字符串不是之前字符串的子序列,//而且與后面跟他長度相同的字符串不是相同的字符串,則該字符串本身為特殊序列// 如果跟后面字符串比較是重復的話,順序到不是重復的下一個字符串再進行判斷int cmp1(const void *a, const void *b){    return strlen(*(char **)b) - strlen(*(char **)a);}int cmp2(const void *a, const void *b){    return strcmp(*(char **)a, *(char **)b);}//a是不是b的子序列  a為當前序列 b為當前序列之前的序列bool isSequence(char *a, char *b){    int len1 = strlen(a);    int len2 = strlen(b);    printf("%d,%drn",len1,len2);    int count = 0;    int j = 0;    for (int i = 0; i < len1; i++) {        while (j < len2) {            if (a[i] == b[j++]) {                count++;                break;            }            // j++;        }    }    if (count == len1)        return true;    return false;}int findLUSlength(char ** strs, int strsSize){    bool flag = false;    qsort(strs, strsSize, sizeof(strs[0]), cmp2);    qsort(strs, strsSize, sizeof(strs[0]), cmp1);   // 向前查詢是否為子串     for (int i = 0; i < strsSize; i++) {        bool f1 = true, f2 = true;        //從第二個序列開始,往前查詢 之前的序列是否為當前序列的子序列        if (i >= 1) {            for (int j = 0; j < i; j++) {                //第二個序列strs[i] 是不是第一個序列strs[j]的子序列                if (isSequence(strs[i], strs[j])) {                    f1 = false;                    break;                }            }        }        // 向后查詢有無重復字符串        for (int k = i + 1; k < strsSize; k++) {            //長度不同 內容肯定不同 跳出循環,繼續往后比較            if (strlen(strs[k]) != strlen(strs[i]))                break;            //長度相同時,比較內容是否相同             if (strcmp(strs[k], strs[i]) == 0) {                f2 = false;                //內容不同時,將從此序列開始比較                 i = k;            }        }        if (f1 && f2)            return strlen(strs[i]);    }    return -1;}

反轉字符串

344. 反轉字符串(0.696)

題目描述

??編寫一個函數,其作用是將輸入的字符串反轉過來。輸入字符串以字符數組 char[] 的形式給出。

??不要給另外的數組分配額外的空間,你必須原地修改輸入數組、使用 O(1) 的額外空間解決這一問題。

??你可以假設數組中的所有字符都是 ASCII 碼表中的可打印字符。

示例 1: 輸入:[“h”,“e”,“l”,“l”,“o”] 輸出:[“o”,“l”,“l”,“e”,“h”] 示例 2: 輸入:[“H”,“a”,“n”,“n”,“a”,“h”] 輸出:[“h”,“a”,“n”,“n”,“a”,“H”]

解題思路

??常規題目,定義兩個變量,同時從開頭和結尾遍歷,交換字符即可

代碼

void swap(char *s,int start,int end){    while(start<end)    {        char temp;        temp = s[start];        s[start] = s[end];        s[end] = temp;        start++;        end--;    }}void reverseString(char* s, int sSize){        int start = 0;        int end = sSize-1;        swap(s,start,end);         }

541. 反轉字符串 II

??給定一個字符串 s 和一個整數 k,你需要對從字符串開頭算起的每隔 2k 個字符的前 k 個字符進行反轉。 ??如果剩余字符少于 k 個,則將剩余字符全部反轉。 ??如果剩余字符小于 2k 但大于或等于 k 個,則反轉前 k 個字符,其余字符保持原樣。

示例: 輸入: s = “abcdefg”, k = 2 輸出: “bacdfeg” 提示: 該字符串只包含小寫英文字母。 給定字符串的長度和 k 在 [1, 10000] 范圍內。

void swap(char *str,int start,int end){        while(start<end)    {              char temp = str[start];        str[start] = str[end];        str[end] = temp;        start++;        end--;    }}char * reverseStr(char * s, int k){   int len = strlen(s);    for (int i = 0; i < len; i += 2 * k) {        int start = i;        //如果剩余字符小于 2k 但大于或等于 k 個,則反轉前 k 個字符,其余字符保持原樣。        //如果剩余字符少于 k 個,則將剩余字符全部反轉。        int end = (len-start+1 >k ) ? i + k - 1 : len - 1; //是否超界?        swap(s,start,end);    }    return s;}

557. 反轉字符串中的單詞 III

??給定一個字符串,你需要反轉字符串中每個單詞的字符順序,同時仍保留空格和單詞的初始順序。

示例 1: 輸入: “Let’s take LeetCode contest” 輸出: “s’teL ekat edoCteeL tsetnoc” 注意:在字符串中,每個單詞由單個空格分隔,并且字符串中不會有任何額外的空格。

void swap(char *str,int start,int end){        while(start<end)    {              char temp = str[start];        str[start] = str[end];        str[end] = temp;        start++;        end--;    }}char * reverseWords(char * s){    int i = 0;    int start = 0;    int end = 0;    int len = strlen(s);    while(s[end++]!='')    {        //注意邊界條件        if(s[end] == ' ' || s[end] == '')        {                     swap(s,start,end-1);               start = end+1;        }    }        return s;}

345. 反轉字符串中的元音字母(0.495)

??編寫一個函數,以字符串作為輸入,反轉該字符串中的元音字母。

示例 1: 輸入: “hello” 輸出: “holle” 示例 2: 輸入: “leetcode” 輸出: “leotcede” 說明: 元音字母不包含字母"y"。

??和之前的反轉字符串差不多,只不過在反轉以前要判斷下是否是元音字母,注意大寫字母也要判斷。

void swap(char *str,int start,int end){               char temp = str[start];        str[start] = str[end];        str[end] = temp;}int vowel(char c){    if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||        c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U')        return 1;    else        return 0;}char * reverseVowels(char * s){    int i = 0    int j = strlen(s) - 1;    while(i < j)    {    //注意不要越界        while(i < j && !vowel(s[i]))            i++;        while(i < j && !vowel(s[j]))            j--;        swap(s,i,j);        i++;        j--;    }    return s;}

重復字符串

686. 重復疊加字符串匹配(0.337)

題目描述

??給定兩個字符串 A 和 B, 尋找重復疊加字符串A的最小次數,使得字符串B成為疊加后的字符串A的子串,如果不存在則返回 -1。

舉個例子,A = “abcd”,B = “cdabcdab”。 答案為 3, 因為 A 重復疊加三遍后為 “abcdabcdabcd”,此時 B 是其子串;A 重復疊加兩遍后為"abcdabcd",B 并不是其子串。 注意: A 與 B 字符串的長度在1和10000區間范圍內。

解題思路

??解題思路 ??構造新字符串,每次增加復制一次字符串A,判斷B是否為A的字串,直到多復制2次A之后如果B仍然不是A的子串,那么返回-1

??關于重復次數的解釋: ??當lenA>lenB,如果B是A的子串的話 ??1.B可能在A的中間 ??2.可能是在A的末尾和A的開頭組成的字符串,這種情況需要復制一次,類似AA. ??因此,我們要最少復制1次,newStr的空間大小max * lenA + 1,為才可以有2的情況。情況1不用復制就可以出現

??當lenA<lenB,如果B是A的子串的話 ??1.B不可能在A的中間 ??2.首先要保證lenA>lenB,所以最少復制的次數為lenB/lenA。 ??3.其次,如同上面的情況1,2

版權聲明:本文為博主原創文章,遵循 CC 4.0 BY-SA 版權協議,轉載請附上原文出處鏈接和本聲明。

代碼

int repeatedStringMatch(char * A, char * B){    int lenA = strlen(A);    int lenB = strlen(B);    //最大復制次數    int max = lenB / lenA + 2;    //空間大小的確定    char newStr[max * lenA + 1];    memset(newStr, 0, sizeof(newStr));    for (int i = 0; i < max; i++) {        strcat(newStr, A);        char *tmp = NULL;        if (strlen(newStr) >= strlen(B)) {            tmp = strstr(newStr, B);        }        if (tmp == NULL) {            continue;        } else {            return i + 1;        }    }    return -1;}

459. 重復的子字符串(0.459)

題目描述

??給定一個非空的字符串,判斷它是否可以由它的一個子串重復多次構成。給定的字符串只含有小寫英文字母,并且長度不超過10000。

示例 1: 輸入: “abab” 輸出: True 解釋: 可由子字符串 “ab” 重復兩次構成。 示例 2: 輸入: “aba” 輸出: False 示例 3: 輸入: “abcabcabcabc” 輸出: True 解釋: 可由子字符串 “abc” 重復四次構成。 (或者子字符串 “abcabc” 重復兩次構成。)

解題思路

如果一個字符串可以由多個重復子串構成,即具有循環節。設最小循環節用a來表示,他代表通過子串a重復多次可以構成s。 即s換成a來表示就是aa···aaa,由多少個最小循環節a構成s,那么就有幾個a。 找循環節一個一個對比比較麻煩,最簡單方法就是s+s就可以直接增加多一倍的循環節。 假設原來s=aaaa,那ss=s+s=aaaa aaaa 因為是不斷重復的循環節,可以通過簡單的屏蔽的第一個字符,然后再在ss中尋找s 。因為屏蔽第一個字符,即第一個最小循環節被破壞,所以找到的s應該是從第二個循環節開始 但倘若不是由一個子串重復構成 即s=abcd,那ss=abcd abcd=s+s 屏蔽掉第一個字符,又因不匹配,所以在ss中尋找s,一定是對應著新增s的位置,即s.size()處

代碼

bool repeatedSubstringPattern(char * s){   int len =strlen(s);   char *ch =(char *)malloc(sizeof(char)*(2*len -1));   //屏蔽掉第一個字符   strcpy(ch,s+1);   printf("%srn",ch);   //將len-1個字符連接到ch后面,即屏蔽掉最后一個   strncat(ch,s,len-1);  //返回非空,說明可以由循環節構成   return strstr(ch,s);}

28. 實現 strStr()

??實現 strStr() 函數。

??給定一個 haystack 字符串和一個 needle 字符串,在 haystack 字符串中找出 needle 字符串出現的第一個位置 (從0開始)。如果不存在,則返回 -1。

示例 1: 輸入: haystack = “hello”, needle = “ll” 輸出: 2 示例 2: 輸入: haystack = “aaaaa”, needle = “bba” 輸出: -1 說明: 當 needle 是空字符串時,我們應當返回什么值呢?這是一個在面試中很好的問題。 對于本題而言,當 needle 是空字符串時我們應當返回 0 。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符。

??對于本題可以使用kmp算法,不過kmp有點復雜。本人使用的是暴力解法,時間復雜度比較高,但是思路比較好理解。 ??本題整體的思路為:對于haystack字符串,要逐個遍歷,首頁比較haystack 和needle 中的第一個字符,如果相等,則繼續往下比較,移動haystack和needle 的位置。 ??這里要注意的是,在繼續往下比較之前,要記錄下首次相同的位置。同時重新定義一個變量進行haystack 的遍歷,遍歷時要記錄相等的元素的個數。當needle 遍歷完的的時候,比較記錄的元素個數和needle 長度是否相等。相等則返回之前記錄的haystack的起始位置。

int strStr(char * haystack, char * needle){    int n,n1,start=0;   //n,n1分別為字符串長度,start記錄正確匹配開始的位置。    n=strlen(haystack);    n1=strlen(needle);    if(n1==0)        return 0;    if(n<n1)        return -1;        for(int i=0;i<n;++i) //首先i為haystack數組的指針,遍歷該數組    {        //在遍歷過程中,找到haystack與needle數組第一個字符相同的位置,并且用haystack減去該位置             //(n-i)看是否大于needle數組的長度 如果不大于直接跳出,減少遍歷次數        if(needle[0]==haystack[i] && (n-i)>=n1)          {            int count=0;     //用來記錄下一個for循環匹配正確的次數            start=i;            int z=i;                               for(int j=0;j<n1;++j)            {                if(needle[j]==haystack[z])                {                    ++count;   //正確則加1                    ++z;       //并且haystack數組z指針后移                }            }            if(count==n1) //看匹配正確次數是否等于needle數組的長度                return start;        }         }    return -1;}

壓縮字符串

443. 壓縮字符串(0.396)

題目描述

給定一組字符,使用原地算法將其壓縮。 壓縮后的長度必須始終小于或等于原數組長度。 數組的每個元素應該是長度為1 的字符(不是 int 整數類型)。 在完成原地修改輸入數組后,返回數組的新長度。 進階: 你能否僅使用O(1) 空間解決問題? 示例 1: 輸入: [“a”,“a”,“b”,“b”,“c”,“c”,“c”] 輸出: 返回 6 ,輸入數組的前 6 個字符應該是:[“a”,“2”,“b”,“2”,“c”,“3”] 說明: “aa” 被 “a2” 替代?！癰b” 被 “b2” 替代?！癱cc” 被 “c3” 替代。 示例 2: 輸入: [“a”] 輸出: 返回 1 ,輸入數組的前 1 個字符應該是:[“a”] 解釋: 沒有任何字符串被替代。 示例 3: 輸入: [“a”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”] 輸出: 返回 4 ,輸入數組的前4個字符應該是:[“a”,“b”,“1”,“2”]。 解釋: 由于字符 “a” 不重復,所以不會被壓縮?！癰bbbbbbbbbbb” 被 “b12” 替代。 注意每個數字在數組中都有它自己的位置。

解題思路

??用start和end分別指向相同字符的終點與起點,當start的下一個與start不同,或者start指向最后一個字符時,保存start指向的字符與其出現次數,即start - end + 1,但要注意start == end時(即只出現一次時)不用保存次數。

代碼

int compress(char* chars, int charsSize){int start = 0, end = 0, k = 0, t, i, j;    for(; start < charsSize; start++){        if(start + 1 == charsSize || chars[start] != chars[start+1]){            chars[k++] = chars[end];    //chars 存下字符            if(start > end){            //連續次數大于1時保存次數                t = start - end + 1;    //相同字符出現的次數                i = k;              //次數轉為字符串時需要翻轉,用i保存翻轉的起點                while(t > 0){       //測試用例的次數最多兩位數,但我們要考慮多位數的情況                    chars[k++] = t % 10 + '0';  //chars 存下次數                    t /= 10;                }                for(j = 0; j < (k - i) / 2; j++){     //翻轉                    char tmp = chars[i + j];                    chars[i + j] = chars[k - 1 -j];                    chars[k - 1 -j] = tmp;                }            }            end = start + 1;        }    }    return k;}

38. 外觀數列(0.547)

給定一個正整數 n(1 ≤ n ≤ 30),輸出外觀數列的第 n 項。 注意:整數序列中的每一項將表示為一個字符串。 「外觀數列」是一個整數序列,從數字 1 開始,序列中的每一項都是對前一項的描述。前五項如下: 描述前一項,這個數是 1 即 “一個 1 ”,記作 11 描述前一項,這個數是 11 即 “兩個 1 ” ,記作 21 描述前一項,這個數是 21 即 “一個 2 一個 1 ” ,記作 1211 描述前一項,這個數是 1211 即 “一個 1 一個 2 兩個 1 ” ,記作 111221 示例 1: 輸入: 1 輸出: “1” 解釋:這是一個基本樣例。 示例 2: 輸入: 4 輸出: “1211” 解釋:當 n = 3 時,序列是 “21”,其中我們有 “2” 和 “1” 兩組,“2” 可以讀作 “12”,也就是出現頻次 = 1 而 值 = 2;類似 “1” 可以讀作 “11”。所以答案是 “12” 和 “11” 組合在一起,也就是 “1211”。

沒看懂。。。

回文字符串

125. 驗證回文串(0.43)

題目描述

??給定一個字符串,驗證它是否是回文串,只考慮字母和數字字符,可以忽略字母的大小寫。 說明:本題中,我們將空字符串定義為有效的回文串。

示例 1: 輸入: “A man, a plan, a canal: Panama” 輸出: true 示例 2: 輸入: “race a car” 輸出: false

解題思路

1、回文串判斷,首尾比較。忽略大小寫,可以都轉換為同一個基準,比如都是小寫 2、只考慮數字和字母,可以使用isalpha,isdigit(數字,字母返回非0,不是返回0)來過濾 3、考慮空指針或空串的場景

代碼

bool isPalindrome(char * s){  int len = strlen(s);  //空字符串定義為有效的回文串  if (len == 0) return true;  //單個字符定義為有效的回文串  if (len == 1) return true;  //兩個指針,一個指向開頭,一個指向結尾    char *p = s;    char *q = s+len-1;    //雙指針同時遍歷字符串      while(p<q)      {        //跳過非字符和非字母,注意每次判斷是否兩個指針相遇          while((!(isalpha(*p))&&!(isdigit(*p)))&&(p<q))        {            p++;        }        while((!(isalpha(*q))&&!(isdigit(*q)))&&(p<q))        {             q--;             }        //只要有一個不相等就返回false             if((tolower(*p)!=tolower(*q)))                 return false;        //下一個字符的比較            p++;            q--;        }        return true;}

680. 驗證回文字符串 Ⅱ(0.361)

題目描述

??給定一個非空字符串 s,最多刪除一個字符。判斷是否能成為回文字符串。

示例 1: 輸入: “aba” 輸出: True 示例 2: 輸入: “abca” 輸出: True 解釋: 你可以刪除c字符。 注意: 字符串只包含從 a-z 的小寫字母。字符串的最大長度是50000。

解題思路

??檢查到前后不一樣的字符,必須要刪掉一個且只能刪除一次(要么開頭,要么結尾)。刪掉之后檢查剩下的字符串是否為回文。 ??以"abdda"這個串為例,此時i指向’b’,j指向’d’,發現不對了。但是有一次刪除的機會,我們自己寫幾個case其實就能發現,此時子串范圍為(i+1, j)或(i, j-1)的倆子串只要有任意一個是回文串,則結果就是回文串,否則就不是。

代碼

bool isPalindrome (char* start, char* end)   //檢查s中一段是否為回文數{    while(start <= end) {        if(*start != * end) {            return false;        }        start++;        end--;    }    return true;}bool validPalindrome(char * s){    int flag = 0;    // 一次刪除機會    int len = strlen(s);    if (len <= 2) {   //單獨一字符或者兩字符肯定能變成回文        return true;    }    char* start = s;    char* end = s + len -1;    while (start <= end) {        if (*start != *end) {            //刪除左邊            if (isPalindrome(start+1, end)) {                return true;            }            //刪除右邊            if (isPalindrome(start, end - 1)) {                return true;            }            return false;        }        start++;        end--;    }    return true;}

統計字符串字符出現的次數

387. 字符串中的第一個唯一字符(0.44)

題目描述

??給定一個字符串,找到它的第一個不重復的字符,并返回它的索引。如果不存在,則返回 -1。

示例: s = “leetcode” 返回 0 s = “loveleetcode” 返回 2 提示:你可以假定該字符串只包含小寫字母。

解題思路

??設置一個輔助數組flag[26],兩次遍歷:第一遍統計各字符出現次數,第二遍找到第一個值為1的索引即為所求

代碼

//設置一個輔助數組flag[26],兩次遍歷:第一遍統計各字符出現次數,第二遍找到第一個值為1的索引即為所求int firstUniqChar(char * s){    int flag[26]={0};    int len=strlen(s);    int i;    for(i=0;i<len;i++){        flag[s[i]-'a']++;    }    for(i=0;i<len;i++){        if(flag[s[i]-'a']==1) return i;    }    return -1;}

451. 根據字符出現頻率排序(會看hash)

題目描述

??給定一個字符串,請將字符串里的字符按照出現的頻率降序排列。

示例 1: 輸入: “tree” 輸出: “eert” 解釋: 'e’出現兩次,'r’和’t’都只出現一次。 因此’e’必須出現在’r’和’t’之前。此外,"eetr"也是一個有效的答案。 示例 2: 輸入: “cccaaa” 輸出: “cccaaa” 解釋: 'c’和’a’都出現三次。此外,"aaaccc"也是有效的答案。 注意"cacaca"是不正確的,因為相同的字母必須放在一起。 示例 3: 輸入: “Aabb” 輸出: “bbAa” 解釋: 此外,"bbaA"也是一個有效的答案,但"Aabb"是不正確的。 注意’A’和’a’被認為是兩種不同的字符。

解題思路

??字符范圍為:0-128,利用數組去構建哈希表: ??1.首先對字符串進行遍歷,取得每個字符出現的次數保存在數組count中 ??2.循環遍歷count數組,每次找出最大值所對應的索引,將其值賦為0(這次下次就不會重復找到它),然后將索引所對應的字符賦值到字符串s中。

代碼

char * frequencySort(char * s){      int flag[128] = {0};    int len = strlen(s);    if (len <= 2)        return s;    for(int i = 0;i<len;i++)    {        printf("%d ",s[i]);        flag[s[i]]++;    }    int i ,j = 0;    while(i < len){int maxValue = 0;int maxIndex = 0;        //每次都找到最大值 記錄下最大值和下標for( j = 0; j < 128; j++){if (flag[j] > maxValue){maxValue = flag[j];maxIndex = j;}}        //把最大值對應的內容置0 表示已經打印了if (maxValue != 0){flag[maxIndex] = 0;}        //將當前的字符串中出現的最大頻率的字母放在s中for(j = 0; j < maxValue; j++){s[i++] = maxIndex;}}    return s;}

347. 前 K 個高頻元素

題目描述

??給定一個非空的整數數組,返回其中出現頻率前 k 高的元素。

示例 1: 輸入: nums = [1,1,1,2,2,3], k = 2 輸出: [1,2] 示例 2: 輸入: nums = [1], k = 1 輸出: [1] 提示: 你可以假設給定的 k 總是合理的,且 1 ≤ k ≤ 數組中不相同的元素的個數。 你的算法的時間復雜度必須優于 O(n log n) , n 是數組的大小。 題目數據保證答案唯一,換句話說,數組中前 k 個高頻元素的集合是唯一的。 你可以按任意順序返回答案。

解題思路

方法一: 此處撰寫解題思路 1、自己構建hash數據結構,記錄val和對應出現次數 2、然后根據cnt進行排序 3、將cnt中出現的非零元素靠前存放,有效減少排序的時間。 4、輸出排序后后K數據 方法二:使用uthash數據結構

代碼

#define Hash_SIZE 20001#define OFFSET 10000//對下標為負數進行偏移使數組下標>=0typedef struct {    int val;    int cnt;}HashTable;//結構體數組HashTable hash[Hash_SIZE];//比較函數,對cnt出現次數進行排序int comp(const void *a, const void *b) {    return (((HashTable *)a)->cnt - ((HashTable *)b)->cnt);}int* topKFrequent(int* nums, int numsSize, int k, int* returnSize){        memset(hash,0,sizeof(hash));//初始化sizeof(hash)個字節    int i=0,j=0;    for(i=0;i<numsSize;i++)//將nums數組的值和出現的次數放入hash表中    {        hash[(nums[i]+OFFSET)%Hash_SIZE].cnt++;        hash[(nums[i]+OFFSET)%Hash_SIZE].val=nums[i];    }        //對原hash表進行優化  把所有非零值靠前存放    for(i=0;i<Hash_SIZE;i++)    {        if(hash[i].cnt!=0)        {            hash[j].cnt=hash[i].cnt;            hash[j].val=hash[i].val;            j++;        }    }    //對hash表中的cnt進行快速排序,出現次數少的在前面,次數多的在后面    //hash[j-i-1]//注意sizeof里面是hashtable    qsort(hash,j,sizeof(HashTable),comp);    //輸出前k個高頻元素  從最后一個開始  j-0-1  j-1-1 j-2-1    for(i=0;i<k;i++)        nums[i]=hash[j-i-1].val;    *returnSize=k;    return nums;}

#include <uthash.h>struct Number {    int key;    int cnt;    UT_hash_handle hh;};static void CountNum(struct Number **hash, int num, int cnt){    struct Number *node = NULL;    HASH_FIND_INT(*hash, &num, node);    if (node != NULL) {        node->cnt++;        return;    }    node = malloc(sizeof(struct Number));    node->cnt = cnt;    node->key = num;    HASH_ADD_INT(*hash, key, node);}static void CountArray(struct Number **hash, int *array, int n){    for (int i = 0; i < n; i++) {        CountNum(hash, array[i], 1);    }}static void Release(struct Number **hash){    struct Number *node, *next;    HASH_ITER(hh, *hash, node, next) {        HASH_DEL(*hash, node);    }}static int Cmp(struct Number *a, struct Number *b){    return b->cnt - a->cnt;}int *topKFrequent(int *nums, int numsSize, int k, int *returnSize){    int *result = malloc(sizeof(int) * k);    assert(result != NULL);    *returnSize = k;    struct Number *ha = NULL;    CountArray(&ha, nums, numsSize);    HASH_SORT(ha, Cmp);        int index = 0;    struct Number *node = NULL;    struct Number *next = NULL;    HASH_ITER(hh, ha, node, next) {        result[index++] = node->key;        if (index == k) {            break;        }    }    Release(&ha);    return result;}

/** * Note: The returned array must be malloced, assume caller calls free(). *///哈希表#define MAX_NUM 50000typedef struct {    int num;    int cnt;    UT_hash_handle hh;}hash_entry;hash_entry* users = NULL;hash_entry hash_item[MAX_NUM];int g_cnt = 0;void add_users(int num) {    hash_entry* t = NULL;    HASH_FIND_INT(users,&num,t);    if(t == NULL) {        hash_item[g_cnt].num = num;        hash_item[g_cnt].cnt = 1;        t = &hash_item[g_cnt];        g_cnt++;        HASH_ADD_INT(users,num,t);        return;    }    t->cnt++;}int cmp(hash_entry* a,hash_entry* b) {    return b->cnt - a->cnt;}int* topKFrequent(int* nums, int numsSize, int k, int* returnSize){    users = NULL;    hash_entry* t = NULL;    for(int i = 0;i < numsSize;i++) {        add_users(nums[i]);    }    //對哈希表進行排序    HASH_SORT(users,cmp);    int* res = (int*)malloc(sizeof(int) * k);    int cnt = 0;    //遍歷哈希表    for(t = users;t != NULL;t = t->hh.next) {        if(cnt >= k) {            break;        }        res[cnt++] = t->num;    }    *returnSize = k;    return res;}

692. 前K個高頻單詞

題目描述

??給一非空的單詞列表,返回前 k 個出現次數最多的單詞。

??返回的答案應該按單詞出現頻率由高到低排序。如果不同的單詞有相同出現頻率,按字母順序排序。

示例 1: 輸入: [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2 輸出: [“i”, “love”] 解析: “i” 和 “love” 為出現次數最多的兩個單詞,均為2次。 注意,按字母順序 “i” 在 “love” 之前。 示例 2: 輸入: [“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”], k = 4 輸出: [“the”, “is”, “sunny”, “day”] 解析: “the”, “is”, “sunny” 和 “day” 是出現次數最多的四個單詞, 出現次數依次為 4, 3, 2 和 1 次。 注意: 假定 k 總為有效值, 1 ≤ k ≤ 集合元素數。 輸入的單詞均由小寫字母組成。 擴展練習: 嘗試以 O(n log k) 時間復雜度和 O(n) 空間復雜度解決。

解題思路

qsort的結構體的排序,注意字典序是如何排序的。

代碼

/** * Note: The returned array must be malloced, assume caller calls free(). */typedef struct node{    char word[20];    int num;}NODE;int cmp1(const NODE* a, const NODE* b){    return (b->num - a->num);}int cmp2(const NODE* a, const NODE* b){    return strcmp(a->word, b->word);}char ** topKFrequent(char ** words, int wordsSize, int k, int* returnSize){    NODE* node = calloc(wordsSize, sizeof(NODE));    char** ret = calloc(wordsSize, sizeof(char*));    int node_len = 0;    for (int i = 0; i < wordsSize; i++) {// 建立結構體數組,存儲出現次數        bool flag = false;        // 若前面出現過這個單詞,直接累加次數        for (int j = 0; j < node_len; j++) {            // printf("check : "%s" ", node[j].word);            // printf("compare with "%s"n", words[i]);            if (strcmp(words[i], node[j].word) == 0) {                node[j].num++;                flag = true;                // printf("node[%d].num++n", j);                break;            }        }        if (!flag) {// 若前面沒出現過,新增一個節點            strcpy(node[node_len].word, words[i]);            node[node_len].num = 1;            // printf("add node : "%s" %dn", node[node_len].word, node[node_len].num);            node_len++;            // puts("-----");        }    }    qsort(node, node_len, sizeof(NODE), cmp2);// 排序字符串    qsort(node, node_len, sizeof(NODE), cmp1);// 排序出現次數    for (int i = 0; i < k; i++) {        // printf("print node : "%s" %dn", node[i].word, node[i].num);        ret[i] = node[i].word;    }    *returnSize = k;    return ret;}

659. 分割數組為連續子序列

題目描述

??給你一個按升序排序的整數數組 num(可能包含重復數字),請你將它們分割成一個或多個子序列,其中每個子序列都由連續整數組成且長度至少為 3 。

??如果可以完成上述分割,則返回 true ;否則,返回 false 。

示例 1: 輸入: [1,2,3,3,4,5] 輸出: True 解釋: 你可以分割出這樣兩個連續子序列 : 1, 2, 3 3, 4, 5 示例 2: 輸入: [1,2,3,3,4,4,5,5] 輸出: True 解釋: 你可以分割出這樣兩個連續子序列 : 1, 2, 3, 4, 5 3, 4, 5 示例 3: 輸入: [1,2,3,4,4,5] 輸出: False 提示: 輸入的數組長度范圍為 [1, 10000]

解題思路

題目看不懂系列

代碼

215. 數組中的第K個最大元素

題目描述

??在未排序的數組中找到第 k 個最大的元素。請注意,你需要找的是數組排序后的第 k 個最大的元素,而不是第 k 個不同的元素。

示例 1: 輸入: [3,2,1,5,6,4] 和 k = 2 輸出: 5 示例 2: 輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4 輸出: 4 說明: 你可以假設 k 總是有效的,且 1 ≤ k ≤ 數組的長度。

解題思路

思路沒難度,將數組排序后輸出第k-1個就可以了。題目沒有限制,我們可以利用qsort直接排序,也可以手寫一個快速排序。

代碼

int cmp(const void*a, const void* b) {    return *(int*)b - *(int*)a;}int findKthLargest(int* nums, int numsSize, int k){    if(nums==NULL||numsSize==0) return 0;    qsort(nums, numsSize, sizeof(int), cmp);    return nums[k-1];}

手寫快排

void quickSort(int arr[], int low, int high){    int first = low;    int last  = high;    int key = arr[first];    if(first >= last)        return;    while(first < last)    {        while(first < last && arr[last] <= key)        {            last--;        }        //從后往前,找到一個比key大的和first指向的位置交換        arr[first] = arr[last];        while(first < last && arr[first] > key)        {            first++;        }        //從前往后,找到一個比key小的和last指向的位置交換        arr[last] = arr[first];    }    //最后跳出時 first == last first就是key的位置    arr[first] = key;    //繼續排序前半部分 和后半部分    quickSort(arr, low, first-1);    quickSort(arr, first+1, high);}int findKthLargest(int* nums, int numsSize, int k){        if(nums==NULL||numsSize==0) return 0;    quickSort(nums,0,numsSize-1);    //for(int i = 0;i<numsSize;i++)        //printf("%drn",nums[i]);    return nums[k-1];}

973. 最接近原點的 K 個點

題目描述

??我們有一個由平面上的點組成的列表 points。需要從中找出 K 個距離原點 (0, 0) 最近的點。

(這里,平面上兩點之間的距離是歐幾里德距離。)

??你可以按任何順序返回答案。除了點坐標的順序之外,答案確保是唯一的。

示例 1: 輸入:points = [[1,3],[-2,2]], K = 1 輸出:[[-2,2]] 解釋: (1, 3) 和原點之間的距離為 sqrt(10), (-2, 2) 和原點之間的距離為 sqrt(8), 由于 sqrt(8) < sqrt(10),(-2, 2) 離原點更近。 我們只需要距離原點最近的 K = 1 個點,所以答案就是 [[-2,2]]。 示例 2: 輸入:points = [[3,3],[5,-1],[-2,4]], K = 2 輸出:[[3,3],[-2,4]] (答案 [[-2,4],[3,3]] 也會被接受。) 提示: 1 <= K <= points.length <= 10000 -10000 < points[i][0] < 10000 -10000 < points[i][1] < 10000

解題思路

??方法一:qsort排序 ??方法二:另一種qsort排序 額外定義一個結構體存放坐標和距離的數值,然后對結構體內的距離值進行排序

代碼

方法一

int cmp(const void*a, const void*b){//將(int**)指針解一次引用再用索引訪問元素,解一次引用相當于一維數組int x1=(*(int**)a)[0], y1=(*(int**)a)[1];int x2=(*(int**)b)[0], y2=(*(int**)b)[1];return (x1*x1+y1*y1) - (x2*x2+y2*y2);}int** kClosest(int** a, int n, int* col, int k, int* returnSize, int** returnColumnSizes){qsort(a, n, sizeof(int**), cmp);*returnColumnSizes = (int*)calloc(k, sizeof(int));for (int i = 0; i < k; i++) {(*returnColumnSizes)[i] = 2;}*returnSize = k;return a;}/*************************************************************************//* qsort排序二維數組,cmp的每個元素都是一個獨立的 int 數組,也就是指針 */int cmp(const void* a, const void* b) {    // 解一次引用轉換為對應一維數組    int* arry1 = *(int**)a;    int* arry2 = *(int**)b;        // 解兩次引用 獲取對應arry1 的兩個元素    int x1 = *arry1;    int y1 = *(arry1 + 1);    int x2 = *arry2;    int y2 = *(arry2+1);    return (x1*x1 + y1*y1) - (x2*x2 + y2*y2);}int** kClosest(int** points, int pointsSize, int* pointsColSize, int K, int* returnSize, int** returnColumnSizes){    if(points==NULL || pointsSize==0 || K==0) return NULL;        qsort(points, pointsSize, sizeof(int)*pointsColSize[0], cmp);    /*   這里注意 qsort 的傳參,使用不當會報錯    Line 11: char 11: runtime error: load of misaligned address 0x602000000032 for type 'int *', which requires 8 byte alignment (solution.c)       0x602000000032: note: pointer points here    */    // 指定return輸出的二維數組是包含有幾個一維數組    *returnSize = pointsSize > K ? K : pointsSize;        *returnColumnSizes = (int*)malloc(sizeof(int*)*(*returnSize));    // 指定每個一維數組的 col     for(int i = 0; i< (*returnSize); i++) {        (*returnColumnSizes)[i] = 2;    }    return points;}

方法二

typedef struct node {int x, y;int d;} node_t;int cmp(const void*a, const void*b){node_t *a1 = (node_t *)a;node_t *b1 = (node_t *)b;return a1->d - b1->d;}int** kClosest(int** a, int n, int* col, int k, int* returnSize, int** returnColumnSizes){if (a == NULL || col == NULL || n == 0 || k == 0|| returnSize == NULL || returnColumnSizes== NULL) {return NULL;}*returnSize = k;*returnColumnSizes = (int*)calloc(k, sizeof(int));int **result = (int**)calloc(k, sizeof(int*));node_t *p = (node_t *)calloc(n, sizeof(node_t)); for (int i = 0; i < n; i++) {int x = a[i][0];int y = a[i][1];int d = x*x+y*y;p[i].x=x;p[i].y=y;p[i].d=d;// printf("(%d,%d)=%dn", x, y, d);}qsort(p, n, sizeof(node_t), cmp);/* for (int i = 0; i < n; i++) {printf("(%d,%d)=%dn", p[i].x, p[i].y, p[i].d);}*/for (int i = 0; i < k; i++) {(*returnColumnSizes)[i] = 2;result[i] = (int*)malloc(sizeof(int)*2); result[i][0] = p[i].x;result[i][1] = p[i].y; }free(p);return result;}

??方法2:堆排序法

typedef struct node{    int row;    int column;    int dist;}Node_t,*pNode_t;void adjustheap(pNode_t heap,int start,int end){    Node_t temp;    int dad=start;    int son=dad*2+1;    while(son<end)    {        if(son+1<end&&heap[son+1].dist>heap[son].dist)            son++;        if(heap[dad].dist>heap[son].dist)            return;        else        {            temp=heap[dad];            heap[dad]=heap[son];            heap[son]=temp;            dad=son;            son=dad*2+1;        }    }}

單詞個數

58. 最后一個單詞的長度(0.328)

題目描述

給定一個僅包含大小寫字母和空格 ’ ’ 的字符串 s,返回其最后一個單詞的長度。如果字符串從左向右滾動顯示,那么最后一個單詞就是最后出現的單詞。 如果不存在最后一個單詞,請返回 0 。 說明:一個單詞是指僅由字母組成、不包含任何空格字符的 最大子字符串。 示例: 輸入: “Hello World” 輸出: 5

解題思路

??因為只包含字母和空格,所以從結尾開始遍歷,直接使用庫函數isalpha判斷是否是字母就可以,當非字母的時候說明遇到了空格,跳出就可以。

代碼

int lengthOfLastWord(char * s){    int l;    int i;    int res = 0;    if(NULL == s)        return 0;    l = strlen(s);    for(i = l-1; i >=0; i--)    {        if(isalpha(s[i]))            res++;        //空格字符        else            if(res)                break;    }    return res;}

434. 字符串中的單詞數(0.342)

題目描述

. ??統計字符串中的單詞個數,這里的單詞指的是連續的不是空格的字符。

??請注意,你可以假定字符串里不包括任何不可打印的字符。

示例: 輸入: “Hello, my name is John” 輸出: 5 解釋: 這里的單詞是指連續的不是空格的字符,所以 “Hello,” 算作 1 個單詞。

解題思路

??統計前一個為空格且自身不是空格的數量即可。(注意s[0])

代碼

int countSegments(char * s){    if(s[0] == '') return 0;    int cnt=0;    int i = 0;    int len = strlen(s);    for(i =0; i < len; i++){        //注意第一個單詞的判斷 i == 0         if ((i == 0 || s[i-1] == ' ') && s[i] != ' ')        cnt++;    }    return cnt;}

13. 羅馬數字轉整數(0.611)

題目描述

羅馬數字包含以下七種字符: I, V, X, L,C,D 和 M。

字符          數值I             1V             5X             10L             50C             100D             500M             1000

??例如, 羅馬數字 2 寫做 II ,即為兩個并列的 1。12 寫做 XII ,即為 X + II 。 27 寫做 XXVII, 即為 XX + V + II 。

??通常情況下,羅馬數字中小的數字在大的數字的右邊。但也存在特例,例如 4 不寫做 IIII,而是 IV。數字 1 在數字 5 的左邊,所表示的數等于大數 5 減小數 1 得到的數值 4 。同樣地,數字 9 表示為 IX。這個特殊的規則只適用于以下六種情況:

??I 可以放在 V (5) 和 X (10) 的左邊,來表示 4 和 9。 ??X 可以放在 L (50) 和 C (100) 的左邊,來表示 40 和 90。 ??C 可以放在 D (500) 和 M (1000) 的左邊,來表示 400 和 900。 ??給定一個羅馬數字,將其轉換成整數。輸入確保在 1 到 3999 的范圍內。

示例 1: 輸入: “III” 輸出: 3 示例 2: 輸入: “IV” 輸出: 4 示例 3: 輸入: “IX” 輸出: 9 示例 4: 輸入: “LVIII” 輸出: 58 解釋: L = 50, V= 5, III = 3. 示例 5: 輸入: “MCMXCIV” 輸出: 1994 解釋: M = 1000, CM = 900, XC = 90, IV = 4.

解題思路

對于各種情況以此判斷,當出現I、X、C三個字符時,如果右邊是對應的特殊情況,就相應減法。

代碼

int romanToInt(char * s){      int count = 0;while (*s){if (*s == 'V')         count += 5;else if (*s == 'L')    count += 50;else if (*s == 'D')    count += 500;else if (*s == 'M')    count += 1000;else if (*s == 'I')//加多了減去,巧妙地規律判斷count = (*(s + 1) == 'V' || *(s + 1) == 'X') ? count - 1 : count + 1;else if (*s == 'X')count = (*(s + 1) == 'L' || *(s + 1) == 'C') ? count - 10 : count + 10;elsecount = (*(s + 1) == 'D' || *(s + 1) == 'M') ? count - 100 : count + 100;s++;}return count;}

551. 學生出勤記錄 I(0.51)

題目描述

??給定一個字符串來代表一個學生的出勤記錄,這個記錄僅包含以下三個字符:

??‘A’ : Absent,缺勤 ??‘L’ : Late,遲到 ??‘P’ : Present,到場 ??如果一個學生的出勤記錄中不超過一個’A’(缺勤)并且不超過兩個連續的’L’(遲到),那么這個學生會被獎賞。

??你需要根據這個學生的出勤記錄判斷他是否會被獎賞。

示例 1: 輸入: “PPALLP” 輸出: True 示例 2: 輸入: “PPALLL” 輸出: False

解題思路

思路 ??遍歷字符串統計字符出現的次數即可。注意,題目最多允許出現兩個連續的L,但不允許三個連續的L.這里判斷的時候用三個L作為邊界來判斷,只要滿足cntL條件就會+3,說明已經超過。不滿足條件((s[i] == 'L')&&(s[i+1])&&(s[i+1] == 'L')&&(s[i+2] == 'L')),說明小于三個連續L,cntL就會小于3,下面進行判斷的時候會判斷為true。當然也可以在for循環的時候判斷是否要終結循環也可以省一點時間。

代碼

bool checkRecord(char * s){    if (s[0] == '') return false;    int len = strlen(s);    int cntA = 0;    int cntL = 0;    //計數    for(int i = 0;i<len;i++)    {        if(s[i] == 'A')            cntA++;        //允許出現兩個連續的L,但不允許連續的三個L        //只要滿足cntL條件就會+3,說明已經超過。不滿足條件說明小于三個連續L,cntL就會小于3,下面進行判斷的時候會判斷為true。        if((s[i] == 'L')&&(s[i+1])&&(s[i+1] == 'L')&&(s[i+2] == 'L'))            cntL+=3;    }    if((cntA<=1)&&(cntL<=2))        return true;    else        return false;}}

14. 最長公共前綴(0.367)

題目描述

??編寫一個函數來查找字符串數組中的最長公共前綴。

??如果不存在公共前綴,返回空字符串 “”。

示例 1: 輸入: [“flower”,“flow”,“flight”] 輸出: “fl” 示例 2: 輸入: [“dog”,“racecar”,“car”] 輸出: “” 解釋: 輸入不存在公共前綴。 說明: 所有輸入只包含小寫字母 a-z 。

解題思路

??以第一個字符串為基準進行豎向掃描,將每個字符串的前col個字符進行依次比較。

代碼

char * longestCommonPrefix(char ** strs, int strsSize){    if(0==strsSize)return "";    char *s0= strs[0];  //首個字符串作為基準    for(int col=0; s0[col]!='' ;++col){   //s0的第col個字符作為基準        for(int row=1; row<strsSize; ++row){//掃描其他字符串,僅當所有字符串的第col個字符都同基準,才會正常結束循環            if(s0[col]!=strs[row][col]){    //不會越界!因為即將越界會有 ''停止符作為哨兵,此時馬上跳出。                s0[col]='';   // 用''表示結束,改短s0                return s0;              }        }//而且C語言即便越界,只要越的界沒有超出整個進程代碼段的地址空間,都不會報錯。    }return s0;     //其他字符串不存在或都包含s0的前綴}

657. 機器人能否返回原點(0.738)

題目描述

??在二維平面上,有一個機器人從原點 (0, 0) 開始。給出它的移動順序,判斷這個機器人在完成移動后是否在 (0, 0) 處結束。

??移動順序由字符串表示。字符 move[i] 表示其第 i 次移動。機器人的有效動作有 R(右),L(左),U(上)和 D(下)。如果機器人在完成所有動作后返回原點,則返回 true。否則,返回 false。

??注意:機器人“面朝”的方向無關緊要。 “R” 將始終使機器人向右移動一次,“L” 將始終向左移動等。此外,假設每次移動機器人的移動幅度相同。

示例 1: 輸入: “UD” 輸出: true 解釋:機器人向上移動一次,然后向下移動一次。所有動作都具有相同的幅度,因此它最終回到它開始的原點。因此,我們返回 true。 示例 2: 輸入: “LL” 輸出: false 解釋:機器人向左移動兩次。它最終位于原點的左側,距原點有兩次 “移動” 的距離。我們返回 false,因為它在移動結束時沒有返回原點。

解題思路

??直接統計字符串中RLUD的個數就好了,只要個數RL并且UD,他總是可以回到原點。

代碼

bool judgeCircle(char * moves){    int cntR = 0;    int cntL = 0;    int cntU = 0;    int cntD = 0;    int len = strlen(moves);    for(int i = 0;i<len;i++)    {        if(moves[i] == 'R')            cntR++;        else if(moves[i] == 'L')            cntL++;        else if(moves[i] == 'U')            cntU++;        else if(moves[i] == 'D')            cntD++;    }    if(((cntR == cntL))&&((cntU == cntD))) return true;        return false;}

929. 獨特的電子郵件地址(0.638)

題目描述

??每封電子郵件都由一個本地名稱和一個域名組成,以 @ 符號分隔。

??例如,在 alice@leetcode.com中, alice 是本地名稱,而 leetcode.com 是域名。除了小寫字母,這些電子郵件還可能包含 ‘.’ 或 ‘+’。

??如果在電子郵件地址的本地名稱部分中的某些字符之間添加句點(’.’),則發往那里的郵件將會轉發到本地名稱中沒有點的同一地址。例如,"alice.z@leetcode.com” 和 “alicez@leetcode.com” 會轉發到同一電子郵件地址。 (請注意,此規則不適用于域名。)

??如果在本地名稱中添加加號(’+’),則會忽略第一個加號后面的所有內容。這允許過濾某些電子郵件,例如 m.y+name@email.com 將轉發到 my@email.com。 (同樣,此規則不適用于域名。)可以同時使用這兩個規則。

??給定電子郵件列表 emails,我們會向列表中的每個地址發送一封電子郵件。實際收到郵件的不同地址有多少?

示例: 輸入:[“test.email+alex@leetcode.com”,“test.e.mail+bob.cathy@leetcode.com”,“testemail+david@lee.tcode.com”] 輸出:2 解釋:實際收到郵件的是 “testemail@leetcode.com” 和 “testemail@lee.tcode.com”。 提示: 1 <= emails[i].length <= 100 1 <= emails.length <= 100 每封 emails[i] 都包含有且僅有一個 ‘@’ 字符。

解題思路

??參考大佬的解法,自己加了注釋。 ??主要思路:利用strtok函數字符串以@為界限分割為first和last兩部分。將第一部分處理成標準的字符串,遇到.跳過,遇到+跳出,丟掉后面的。剩下的放進res數組中。最后將first和last兩部分合起來放進res即可。

??放進res的部分,需要判斷下是否和res當前已有的內容重復,如果重復,就清零即將放進的部分,否則就直接放入。

代碼

int numUniqueEmails(char **emails, int emailsSize){    //初始化    char **res = calloc(emailsSize, sizeof(char*));    for (int i = 0; i < emailsSize; i++) {        res[i] = calloc(101, sizeof(char));    }        char *first, *last;    int count1 = 0, count2 = 0, flag = 0;    for (int i = 0; i < emailsSize; i++) {        //以@為界限進行分割為first,last兩部分        //首次調用時,s必須指向要分解的字符串,隨后調用要把s設成NULL。        //https://blog.csdn.net/sxy19930313/article/details/78548174        first = strtok(emails[i], "@");        last = strtok(NULL, "@");        for (int j = 0; j < strlen(first); j++) {            //遇到 . 跳過,進行下一次循環            if (first[j] == '.')             {                continue;            }             //遇到+直接跳出循環,+后面的都不要            else if (first[j] == '+')            {                break;            }             //其余的都放進res數組            else            {                res[count1][count2++] = first[j];            }        }        //連接@ 和last部分        strcat(res[count1], "@");        strcat(res[count1], last);        flag = 1;        //比較res中已有內容res[j] 和目前的res[count1]的內容是否相同        for (int j = 0; j < count1; j++) {            //二者相同,flag置1 同時清空res[count1]            if (!strcmp(res[count1], res[j])) {                flag = 0;                memset(res[count1], 0, sizeof(char) * 101);                break;            }        }        //flag為1說明二者不等,count1++,進行下一個        if (flag == 1) {            count1++;        }        count2 = 0;    }    //最后count1的值就是不同的內容的個數    return count1;}

804. 唯一摩爾斯密碼詞(0.745)

題目描述

??國際摩爾斯密碼定義一種標準編碼方式,將每個字母對應于一個由一系列點和短線組成的字符串, 比如: “a” 對應 “.-”, “b” 對應 “-…”, “c” 對應 “-.-.”, 等等。

??為了方便,所有26個英文字母對應摩爾斯密碼表如下:

[".-","-…","-.-.","-…",".","…-.","–.","…","…",".—","-.-",".-…","–","-.","—",".–.","–.-",".-.","…","-","…-","…-",".–","-…-","-.–","–…"] ??給定一個單詞列表,每個單詞可以寫成每個字母對應摩爾斯密碼的組合。例如,“cab” 可以寫成 “-.-…–…”,(即 “-.-.” + “-…” + ".-"字符串的結合)。我們將這樣一個連接過程稱作單詞翻譯。

??返回我們可以獲得所有詞不同單詞翻譯的數量。

例如: 輸入: words = [“gin”, “zen”, “gig”, “msg”] 輸出: 2 解釋: 各單詞翻譯如下: “gin” -> “–…-.” “zen” -> “–…-.” “gig” -> “–…--.” “msg” -> “–…--.” 共有 2 種不同翻譯, “–…-.” 和 “–…--.”. 注意: 單詞列表words 的長度不會超過 100。 每個單詞 words[i]的長度范圍為 [1, 12]。 每個單詞 words[i]只包含小寫字母。

解題思路

??建立字符串數組morse,存放words中的字符串轉成莫爾斯密碼后的字符串,每次處理words中的字符串,如果不重復,就添加到morse里面,最終輸出morse中字符串的個數

代碼

int uniqueMorseRepresentations(char ** words, int wordsSize){      char dict[26][5] = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};    //5*12 = 60    char morse[100][60] = {0};    int count = 0;    for (int i = 0; i < wordsSize; i++) {        char tmp[60] = { 0 };        int flag = 0;        //每個字符串對應的摩斯碼放入tmp中        for (int j = 0; j < strlen(words[i]); j++) {            strcat(tmp, dict[words[i][j] - 'a']);        }        //定義flag分辨相同和不同,如果tmp和morse中的不同 就放入morse中        for (int k = 0; k < count; k++) {            if (strcmp(morse[k], tmp) == 0) {                flag = 1;                break;            }        }        //不同的話就放入morse中        if (flag == 0) {            strcpy(morse[count], tmp);            count++;        }    }    return count;}

606. 根據二叉樹創建字符串(0.527)

題目描述

??你需要采用前序遍歷的方式,將一個二叉樹轉換成一個由括號和整數組成的字符串。

??空節點則用一對空括號 “()” 表示。而且你需要省略所有不影響字符串與原始二叉樹之間的一對一映射關系的空括號對。

示例 1: 輸入: 二叉樹: [1,2,3,4] 1 / 2 3 / 4 輸出: “1(2(4))(3)” 解釋: 原本將是“1(2(4)())(3())”, 在你省略所有不必要的空括號對之后, 它將是“1(2(4))(3)”。 示例 2: 輸入: 二叉樹: [1,2,3,null,4] 1 / 2 3 4 輸出: “1(2()(4))(3)” 解釋: 和第一個示例相似, 除了我們不能省略第一個對括號來中斷輸入和輸出之間的一對一映射關系。

解題思路

日常題目難懂系列:題目的意思是子節點需要用()來包裹。舉例來說,二叉樹[root,left,right],則轉換為root(left)(right)。如果只有left為空節點,則輸出root()(right);如果只有right為空節點則可以忽略右節點的(),輸出為root(left)。

1.先把根節點寫入字符串 2.再判斷左子樹是否為空,不為空則先加左括號,再寫左子樹的值,最后加右括號–root(left)(right) 3.如果左子樹為空,再判斷右子樹是否為空,如果不為空,則直接添加一對括號–root()(right) 4.判斷右子樹是否為空,不為空則與不空的左子樹同樣處理–root(left) 5.右子樹為空則什么都不做

代碼

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     struct TreeNode *left; *     struct TreeNode *right; * }; */#define MAX_SIZE 50000void transfer_bitree(struct TreeNode* t, char *s, int *len){    if (t) {        *len += sprintf(s + *len, "%d", t->val);        if (t->left || t->right) {            *len += sprintf(s + *len, "%s", "(");            transfer_bitree(t->left, s, len);            *len += sprintf(s + *len, "%s", ")");        }        if (t->right) {            *len += sprintf(s + *len, "%s", "(");            transfer_bitree(t->right, s, len);            *len += sprintf(s + *len, "%s", ")");        }    }}char * tree2str(struct TreeNode* t){    char *str = malloc(MAX_SIZE);    int len = 0;    transfer_bitree(t, str, &len);    str[len] = '';    return str;}

383. 贖金信(0.521)

題目描述

??給定一個贖金信 (ransom) 字符串和一個雜志(magazine)字符串,判斷第一個字符串 ransom 能不能由第二個字符串 magazines 里面的字符構成。如果可以構成,返回 true ;否則返回 false。

??(題目說明:為了不暴露贖金信字跡,要從雜志上搜索各個需要的字母,組成單詞來表達意思。雜志字符串中的每個字符只能在贖金信字符串中使用一次。)

注意: 你可以假設兩個字符串均只含有小寫字母。 canConstruct(“a”, “b”) -> false canConstruct(“aa”, “ab”) -> false canConstruct(“aa”, “aab”) -> true

解題思路

??思路:題目抽象出來很簡單,就是判斷ransom字符串能不能由magazines 字符串的內容構成(magazines 中的字符只能使用一次)。 ??1.將magazines中的字符按照ascii碼為下標存儲在數組中,出現一次,對應的數組內容+1,這樣就可以知道出每個字母的出現次數了。 ??2.遍歷magazines一遍之后,magazines中的字母在count數組中已經有相應的位置,其中的內容不為0。ransom中同樣以ascii碼為下標遍歷,判斷對應的位置是否為0,如果為0,說明已經使用過了或者根本沒有對應的字母,則返回false。如果對應的位置是不為0,說明magazines中有對應的字母,對應的數組內容就直接- -。

代碼

bool canConstruct(char * ransomNote, char * magazine){    int count[26] = {0};//初始化為全零    int i;    char ch;    for(i = 0; (ch=magazine[i]) != ''; i++)        count[ch-'a']++;    for(i = 0; (ch=ransomNote[i])!= ''; i++){        if(count[ch-'a']==0) return false;        else count[ch-'a']--;    }    return true;}

696. 計數二進制子串(0.511)難想到的思路

??給定一個字符串 s,計算具有相同數量0和1的非空(連續)子字符串的數量,并且這些子字符串中的所有0和所有1都是組合在一起的。

??重復出現的子串要計算它們出現的次數。

示例 1 : 輸入: “00110011” 輸出: 6 解釋: 有6個子串具有相同數量的連續1和0:“0011”,“01”,“1100”,“10”,“0011” 和 “01”。 請注意,一些重復出現的子串要計算它們出現的次數。 另外,“00110011”不是有效的子串,因為所有的0(和1)沒有組合在一起。 示例 2 : 輸入: “10101” 輸出: 4 解釋: 有4個子串:“10”,“01”,“10”,“01”,它們具有相同數量的連續1和0。 注意: s.length 在1到50,000之間。 s 只包含“0”或“1”字符。

??由于0和1是分別組合在一起的,也就是說滿足要求的字符串(不會存在0和1混合的情況如:0101 1001) ??這個思路是這樣的, 假設最簡單的情況 000111, 先遍歷, 前面的 0 的數量為 curr = 3, 遍歷到 1 時, pre = curr 賦值為 3, 然后 curr = 1 表示現在 1 的個數, 只要 curr <= pre, 比如 curr = 1, 那么可以組成 01; curr = 2, 可以組成 0011, curr = 3, 組成 000111, 直到出現下一次 0, 然后那么 prev 就是 1 的個數, curr 表示 0001110…這個 1 后面 0 的個數, 不斷重復迭代下去, 不知道我說明白沒有.

int countBinarySubstrings(char * s){    int n = 0, pre = 0, curr = 1, len = strlen(s)-1;    for (int i = 0; i < len; ++i) {        if (s[i] == s[i+1]) ++curr;        else               {pre = curr; curr = 1;}        if (pre >= curr) ++n;    }    return n;}

520. 檢測大寫字母(0.549)

題目描述

??給定一個單詞,你需要判斷單詞的大寫使用是否正確。

??我們定義,在以下情況時,單詞的大寫用法是正確的:

??全部字母都是大寫,比如"USA"。 ??單詞中所有字母都不是大寫,比如"leetcode"。 ??如果單詞不只含有一個字母,只有首字母大寫, 比如 “Google”。 ??否則,我們定義這個單詞沒有正確使用大寫字母。

示例 1: 輸入: “USA” 輸出: True 示例 2: 輸入: “FlaG” 輸出: False 注意: 輸入是由大寫和小寫拉丁字母組成的非空單詞。

解題思路

??檢測大寫字母的個數即可, ??1.當字符串全為大寫字母或者沒有一個大寫字母,返回true。 ??2.當字符串第一個為大寫并且后面的不為大寫字母是,返回true。 ??3.其余情況返回false

代碼

bool detectCapitalUse(char * word){        int len = strlen(word);    int cnt = 0;    for(int i = 0;i<len;i++)    {        if((word[i] >='A' )&&(word[i] <='Z'))        cnt++;         }    //對應情況1和情況3    if((cnt == len)||(cnt == 0))        return true;    //對應情況2  要考慮到首字母    else if(((word[0]>='A')&&(word[0]<='Z')&&(cnt==1)))         return true;    else     return false;