520. 检测大写字母
算法思想: 思路一： 1.首先判断第一个元素是否为大写字母，初始化ishave为false表示不含有大写字母，若有将其置为true 2.若第一个字母为大写字母 下一个字母为大写字母，那么接下来每个字母只能为大写字母 下一个字母为小写字母，那么接下来每个字母只能为小写字母 若第一个字母不为大写字母 接下来每个字符只能为空或小写字母 思路二： 思路二： 1.直接设置计数器up统计大写字母的个数 若未出现大写字母 遍历完成后则直接返回true 若大写字母个数小于等于下标时，则说明中间存在小写字母 直接返回false 2.结尾判断是否大写字母的个数等于字符串长度或小于等于1，若是返回true 否则返回false（说明存在末尾存在小写字符）
思路一（自己的想法） bool detectCapitalUse(char * str){ int i = 0; bool ishave = (str[i] >= 'A' && str[i] <='Z') ? true:false; if(ishave == false) //若不含有大写字母 { for(int i = 1;str[i] != '\0';i++) if(str[i] >= 'A' && str[i] <='Z') return false; } else { if(str[i+1] >= 'A' && str[i+1] <='Z') //若第二个字符仍为大写 for(int i = 1;str[i] != '\0';i++) //从第二个遍历到最后 若出现非大写则返回false { if(!(str[i] >= 'A' && str[i] <='Z')) return false; } else //若第二个字符为小写 for(int i = 1;str[i] != '\0';i++) //从第二个遍历到最后 若出现大写返回false { if(str[i] >= 'A' && str[i] <='Z') return false; } } return true; } 思路二 bool detectCapitalUse(char * str){ int up = 0; for(int i = 0; str[i] != '\0';i++) { if(str[i] >= 'A' && str[i] <='Z') { up++; if(up <= i) return false; } } if(up == strlen(str) || up <= 1) return true; else return false; }125. 验证回文串
算法思想： 1.设置双指针i,j分别指向字符串头和字符串尾 2.当表头与表尾指针i,j未相遇时，指针i向右遍历，直到遇到第一个字母或数字字符，指针j向左遍历，直至遇到第一个字母或数字字符 3.判断遍历到元素是否相等，若相等则指针继续相向前进
char Tolower (char a) //将字符转为小写，若本身已经是小写或是数字则直接返回 { if(a >= 'A' && a <= 'Z') return a+32; return a; } bool isNumOrChar (char a) //判断是否为字符或者数字 { if(a >= '0' && a <= '9') return true; else if(a >= 'a' && a <= 'z') return true; else if(a >= 'A' && a <= 'Z') return true; return false; } bool isPalindrome(char * s){ int len = strlen(s); if(len <= 1) return true; int i = 0, j = len - 1; while(i < j) { while(i < j && !(isNumOrChar(s[i]))) i++; //指针i向右遍历，直到遇到第一个字母或数字字符 while(i < j && !(isNumOrChar(s[j]))) j--; //指针j向左遍历，直至遇到第一个字母或数字字符 if(i < j && Tolower(s[i]) != Tolower(s[j])) return false; i++; j--; } return true; }14. 最长公共前缀
算法思想： 方法一：横向比较 1.初始化最长公共前缀为第一列，公共前缀的长度大小为num 2.从第二个字符串到最后一个字符串开始比较 将每个字符串的元素与第一个字符串进行比较 直到找到第一个不同的元素，此时下标更新为更小的 3.将第一个字符串中下标为num的字符置为’\0’，返回第一个字符串 方法二：纵向比较 1.比较每一列元素是否与第一列元素相同 2.直到找到第一个字符串元素不同的列，将其边界设为下标i，直接返回第一个字符串
本题采用方法二 char * longestCommonPrefix(char ** strs, int strsSize){ if(strsSize == 0) return ""; if(strsSize == 1) return strs[0]; for(int i = 0; i < strlen(strs[0]); i++) //遍历每列 { for(int j = 1; j < strsSize; j++) //遍历每个字符串 if(strs[j][i] != strs[0][i]) { strs[0][i] = '\0'; //直接退出循环并设置边界为i return strs[0]; } } return strs[0]; }434. 字符串中的单词数
算法思想： 1.遍历字符串，若前一个元素是空格当前元素不是空格，则单词个数加一 2.需要对第一个元素做特殊判断，若第一个元素不是空格，则单词个数加一
int countSegments(char * str){ int i = 0, count = 0; while(str[i] != '\0') { if((i == 0 || str[i-1] == ' ') && str[i] != ' ') count++; i++; } return count; }58. 最后一个单词的长度
算法思想： 1.初始化计数器count统计字符个数，从结尾开始遍历，遇到非空格元素时个数加一 2.若count == 0且当前元素为空格则继续前进（需要滤掉后面的空格） 若count != 0时且当前元素为空格则直接返回count 3.遍历结束返回count 则说明字符串长度就是字符个数
int lengthOfLastWord(char * str){ int len = strlen(str), count = 0; for(int i = len - 1; i >= 0; i--) { if(str[i] != ' ') //若遇到非空格元素 则更新count的个数 count++; else if(str[i] == ' ' && count == 0) //滤掉后面的空格 continue; else return count; } return count; }344. 反转字符串
算法思想：经典双指针思想，交换即可 void reverseString(char* str, int sSize){ if(sSize <= 1) return; for(int i = 0; i < sSize / 2; i++) { char temp = str[i]; str[i] = str[sSize - 1 - i]; str[sSize - 1 - i] = temp; } } 方法二实际上是方法一的更加好写的版本 void reverseString(char* str, int sSize){ int left = 0, right = sSize - 1; while(left < right) { char temp = str[left]; str[left] = str[right]; str[right] = temp; left++; right--; } }541. 反转字符串 II
算法思想： 1.先求出字符串的长度，然后从第一个字符开始，每隔2k个字符进行遍历 2.双指针法反转长度为k的字符串，left设置为当前下标i，判断i+k-1是否越界，若越界，right置为字符串长度，若未越界则right=i+k-1 3.每隔2k个长度的字符串，将前k个交换
char * reverseStr(char * str, int k){ int len = strlen(str); int left, right; for(int i = 0; i < len; i += 2 * k) { left = i; if(i + k - 1 <= len - 1) // 从位置i到i+k-1共计k个元素 若未越界 则令右指针为该下标 right = i + k - 1; else right = len - 1; //若已经越界 则令右指针为最后一个下标 while(left < right) { char temp = str[left]; str[left] = str[right]; str[right] = temp; left++; right--; } } return str; }557. 反转字符串中的单词 III
算法思想：结合字符串与单词的思想 1.遍历字符串，当遇到字符时，前一个不是字符或为第一个元素时，将left置为当前下标， 同时向后遍历，直到遇到空格或字符串结尾， 设置right为遍历结束前一个元素，若未遍历到结尾，则将下标加一 2.对遍历到的单词进行双指针法反转
char * reverseWords(char * str){ int i = 0, left, right; while(str[i] != '\0') { if((i == 0 || str[i - 1] == ' ') && str[i] != ' ') { left = i; //将左指针指向单词的第一个字母 while(str[i] != ' ' && str[i] != '\0')//找到第一个空格 i++; right = i -1; if(str[i] != '\0') i++; while(left < right) //反转字符串 { char temp = str[left]; str[left] = str[right]; str[right] = temp; left++; right--; } } } return str; }151. 翻转字符串里的单词
算法思想： 1.双指针思想的快慢指针思想，设置快指针i指向字符串尾部，从字符串尾部开始向前遍历寻找第一个非空格字符 2.当找到第一个非空格字符后，将慢指针j设置为该字符下标，然后让快指针i继续向前走，寻找第一个空格字符 3.将快指针i+1到慢指针j的元素复制到结果字符串中 4.结尾还需要对新创建的字符串增加’\0’结尾标志(去除最后一个无效的空格)
char * reverseWords(char * str){ int len = strlen(str); int i = len - 1, j, count = 0; char *result = (char*)malloc(sizeof(char) * (len+1)); while(i >= 0) { while(i >= 0 && str[i] == ' ' ) i--; //从后向前寻找第一个非空格 if(i >= 0) //若未遍历到第一个元素 则将j置为i j = i; //慢指针j设置为该字符下标 else //若遍历完就已经结束 break; while(i >= 0 && str[i] != ' ') i--; //寻找第一个空格 for(int k = i + 1; k <= j; k++) result[count++] = str[k]; result[count++] = ' '; //count } if(count == 0) result[0] = '\0'; //若无字母 直接第一个元素即为空 else result[count-1] = '\0'; //去除最后一个无效的空格 return result; }299. 猜数字游戏
算法思想：1.利用哈希表B，C统计未出现在对应位置的元素，bulls统计正确元素个数 2.遍历字符串，若secret[i]==guess[i],则将bull加一，否则让B[i]++，C[i]++ 3.扫描哈希表，统计重叠元素个数，即为cow的个数
int min (int a, int b) { if(a > b) return b; return a; } char * getHint(char * secret, char * guess){ int bull = 0, cow = 0; int B[10] = {0}, C[10] = {0}; for(int i = 0; secret[i] != '\0'; i++) { if(secret[i] == guess[i]) //secret[i]==guess[i],则将bull加一，否则让B[i]++，C[i]++ bull++; else { B[secret[i] - '0']++; C[guess[i] - '0']++; } } for(int i = 0; i < 10; i++) { cow += min(B[i],C[i]); } char *str = (char*)malloc(sizeof(char) * 10); sprintf(str, "%dA%dB", bull, cow); return str; }696. 计数二进制子串
算法思想：1.遍历字符串 统计出连续的数字个数 保存在数组count中 2.遍历count 连续子字符串的数量为 sum += min(count[i], count[i+1])
int min(int a, int b) { if(a < b) return a; return b; } int countBinarySubstrings(char * s){ int len = strlen(s); if(len <= 1) return 0; int* count = (int*)malloc(sizeof(int) * 50001); int pre = s[0], num = 0, k = 0; int sum = 0; for(int i = 0; i < len; i++) { if(pre == s[i]) //若与之前相同 num++; else //若不同则更新 { count[k++] = num; num = 1; pre = s[i]; } } count[k] = num; for(int i = 0; i < k; i++) sum += min(count[i], count[i+1]); return sum; }67. 二进制求和
算法思想： 1.比较两个字符串的大小，取较长的字符串长度+2为返回字符串的长度，因为可能需要进位1，且还需要将最后一位设置为\0 2.从最后一个元素开始向前遍历，直至两个字符串均遍历到结尾结束，将字符串a的数字与字符串数字b上的数字相加，若其中一个字符串遍历到0则将该 位置加0，将结果取余为该位数字，add为二者的进位 3.若需要进位，则直接将第一位设置为1，若无需进位，则将所有元素向前移动一个单位
char * addBinary(char * a, char * b){ int lena = strlen(a), lenb = strlen(b); int maxlen = lena > lenb ? lena+2 : lenb+2; char* result = (char*)malloc(sizeof(char) * (maxlen)); result[maxlen - 1] = '\0'; int add = 0; //用于表示进位 for(int i = lena - 1, j = lenb - 1, k = maxlen - 2; i >= 0 || j >= 0; i--, j--, k--) { int sum = add; if(i >= 0) sum += a[i] - '0'; if(j >= 0) sum += b[j] - '0'; result[k] = sum % 2 + '0'; //更新result数组的值 add = sum / 2; } if(add == 1) result[0] = '1'; //若需要进位，则直接将第一位设置为1 else //若无需进位，则将所有元素向前移动一个单位 { for(int i = 0; i < maxlen - 1; i++) result[i] = result[i + 1]; result[maxlen - 1] = '\0'; } return result; }同类型题415. 字符串相加
43. 字符串相乘
算法思想：1.初始化长为lena+lenb+1的int型数组result用于保存结果，让一个字符串的每一位与另一个字符串的另一位相乘，执行结果为 result[i+j] += (nums1[i]-‘0’) * (nums2[j] - ‘0’) 2.对result数组进行进位，用add保存向下一位的进位数 3.若进位结束后，add不为零，则需要将每个数字向后移动一位 4.将result的结果赋值给返回字符串res
char * multiply(char * num1, char * num2){ int lena = strlen(num1), lenb = strlen(num2); if(num1[0] == '0' || num2[0] == '0') //若第一项为0，直接返回0 { num1[0] = '0'; num1[1] = '\0'; return num1; } int maxlen = lena + lenb + 1; int* result = (int*)malloc(sizeof(int) * maxlen); char* res = (char*)malloc(sizeof(char) * maxlen); for(int i = 0; i <= maxlen-1; i++) //两位数相乘 不进位情况下最高的一位为lena+lenb-2 { result[i] = 0; } for(int i = lena - 1; i >= 0; i--) for(int j = lenb - 1; j >= 0; j--) { result[i + j] += (num1[i] - '0') * (num2[j] - '0'); } int add = 0; for(int i = lena + lenb - 2; i >= 0; i--) { result[i] += add; add = result[i] / 10; result[i] = result[i] % 10; } if(add == 0)//判断最后一项是否需要进位 { res[maxlen - 2] = '\0'; for(int i = 0; i < maxlen - 2; i++) res[i] = result[i] + '0'; } else { for(int i = maxlen - 2; i > 0; i--) { result[i] = result[i - 1]; } res[maxlen - 1] = '\0'; for(int i = 1; i <= maxlen - 2; i++) res[i] = result[i] + '0'; res[0] = add + '0'; } return res; }28. 实现 strStr()
算法思想：朴素模式匹配算法 1.从目标串字符开始出发，与比对字符串逐个字符比较 2.每次执行设置j=0，表示每次比对字符串走的步数，当j等于比对串的长度时，说明匹配成功，否则目标串向后移动一个单位
int strStr(char * haystack, char * needle){ int lena = strlen(haystack), lenb = strlen(needle); if(lena == 0 && lenb != 0) return -1; else if(lenb == 0) return 0; int i = 0; while(i <= lena - lenb) //若长度不足，则不再遍历 { int j = 0; while(haystack[i] == needle[j] && j < lenb) //从目标串字符开始出发，与比对字符串逐个字符比较 { i++; j++; } if(j == lenb) return i - j; i = i - j + 1; } return -1; }