文章目录

• 3.无重复字符的最长子串
• 415.字符串相加
• 345.反转字符串中的元音字母
• 14.最长公共前缀
• 28.实现strStr()
• 58.最后一个单词的长度
• 67.二进制求和
• 38.外观数列
• 125.验证回文串
• 383.赎金信
• 387.字符串中的第一个唯一字符
• 434.字符串中的单词数
• 443.压缩字符串（没懂）
• 459.重复的子字符串
• 520.检测大写字母
• 521.最长特殊序列I
• 541.反转字符串II
• 551.学生出勤记录I
• 557.反转字符串中的单词III
• 680.验证回文字符串II
• 686.重复叠加字符串匹配
• 696.计数二进制子串
• 面试题 01.09.字符串轮转
• 面试题 01.06.字符串压缩
• 788.旋转数字
• 709.转换成小写字母
• 剑指Offer 58 - I.翻转单词顺序
• 819.最常见的单词（不懂 哈希映射）
• 917.仅仅反转字母
• 859.亲密字符串
• 336.回文对（一点不懂）
• 824，山羊拉丁文（没看）
• ---------------------8.8-----------------------------
• 1071.字符串的最大公因子
• 1170.比较字符串最小字母出现频次（看不懂啊）
• 1332.删除回文子序列
• 1446.连续字符
• 剑指Offer 58 - II.左旋转字符串（复习）
• 面试题 01.04. 回文排列
• 上升下降字符串（没写）
• --------------------8.9-------------------
• 93.复原IP地址（没看）
• 43.字符串相乘
• --------------8.13------------
• 1544.整理字符串
• 1507.转变日期格式
• 1455.检查单词是否为居中其他单词的前缀

3.无重复字符的最长子串

class Solution {public int lengthOfLongestSubstring(String s) {// 哈希集合，记录每个字符是否出现过Set<Character> occ = new HashSet<Character>();int n = s.length();// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动int rk = -1, ans = 0;for (int i = 0; i < n; ++i) {if (i != 0) {// 左指针向右移动一格，移除一个字符occ.remove(s.charAt(i - 1));}while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {// 不断地移动右指针occ.add(s.charAt(rk + 1));++rk;}// 第 i 到 rk 个字符是一个极长的无重复字符子串ans = Math.max(ans, rk - i + 1);}return ans;}
}

#define LEN 128 //ASCIIint lengthOfLongestSubstring(char * s) {int hset[LEN]; //存储数组下标int start = 0, count = 0, max = 0;memset(hset, -1, sizeof(hset)); //初始化for (int i = 0; i < strlen(s); i++) { //遍历字符串if (hset[s[i]] >= start) {start = hset[s[i]] + 1; // 更新为重复字符的下一个位置count = i - start; // 重置计数器}hset[s[i]] = i;count++;if (count > max) {max = count;}}return max;
}

415.字符串相加

思路：
借鉴初学加法时的列竖式计算

char* addStrings(char* num1, char* num2) {//i,j:两个相加的字符串各自的长度，add:进位int i = strlen(num1) - 1, j = strlen(num2) - 1, add = 0;//初始化"和"char* ans = (char*)malloc(sizeof(char) * (fmax(i, j) + 3));//定义"和"的长度int len = 0;while (i >= 0 || j >= 0 || add != 0) {int x = i >= 0 ? num1[i] - '0' : 0; //对位数较短的数补0int y = j >= 0 ? num2[j] - '0' : 0;int result = x + y + add;ans[len++] = '0' + result % 10; //储存每一位计算的结果add = result / 10; //储存进位i--, j--;}// 计算完以后的答案需要翻转过来for (int i = 0; 2 * i < len; i++) {int t = ans[i];ans[i] = ans[len - i - 1], ans[len - i - 1] = t;}ans[len++] = 0; //"和"字符串结束的标志return ans;
}

345.反转字符串中的元音字母

思路:
双指针法，遇到元音字母交换

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;elsereturn 0;
}char * reverseVowels(char * s){int i = 0, j = strlen(s) - 1;char t;while(i < j){while(i < j && !vowel(s[i])) //i++;while(i < j && !vowel(s[j]))j--;t = s[i];s[i] = s[j];s[j] = t;i++;j--;}return s;
}

14.最长公共前缀

class Solution {public String longestCommonPrefix(String[] strs) {if(strs.length == 0) return "";String ans = strs[0];for(int i =1;i<strs.length;i++) {int j=0;for(; j<ans.length()&&j < strs[i].length(); j++) { //ans.length?if(ans.charAt(j) != strs[i].charAt(j)) //charAt()返回指定索引处的字符break;}ans = ans.substring(0, j); //返回索引0~j-1处的字符if(ans.equals("")) //如果ans为空return ans;}return ans;}
}

28.实现strStr()

思路：
逐一比较

class Solution {public int strStr(String haystack, String needle) {int L = needle.length(), n = haystack.length();for (int start = 0; start < n - L + 1; ++start) {if (haystack.substring(start, start + L).equals(needle)) {return start;}}return -1;}
}

58.最后一个单词的长度

class Solution {public int lengthOfLastWord(String s) {int end = s.length() - 1;while(end >= 0 && s.charAt(end) == ' ') end--;if(end < 0) return 0;int start = end;while(start >= 0 && s.charAt(start) != ' ') start--;return end - start;}
}

67.二进制求和

class Solution {public String addBinary(String a, String b) {StringBuffer ans = new StringBuffer();int n = Math.max(a.length(), b.length()), carry = 0;for (int i = 0; i < n; ++i) {carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;ans.append((char) (carry % 2 + '0'));carry /= 2;}if (carry > 0) {ans.append('1');}ans.reverse();return ans.toString();}
}

相关知识点:
append()：创建了一个新的数组，扩大了长度，将需要添加的字符串给复制到这个新的数组中

JAVA中Stringbuffer有append( )方法：
而Stringbuffer是动态字符串数组，append( )是往动态字符串数组添加，跟“xxxx”+“yyyy”相当‘+’号。

跟String不同的是Stringbuffer是放一起的，String1+String2和Stringbuffer1.append(“yyyy”)虽然打印效果一样，但在内存中表示却不一样、

String1+String2 存在于不同的两个地址内存，Stringbuffer1.append(Stringbuffer2)放再一起。

StringBuffer是线程安全的，多用于多线程。

38.外观数列

思路：
递归，StringBuffer

Java解法：

class Solution {public String countAndSay(int n) {if (n == 1) {return "1";}StringBuffer res = new StringBuffer();String str = countAndSay(n - 1);  //递归   int length = str.length();int a = 0;for (int i = 1; i < length + 1; i++) {if (i == length) {return res.append(i - a).append(str.charAt(a)).toString();} else if (str.charAt(i) != str.charAt(a) ) {res.append(i - a).append(str.charAt(a));a = i;}}return res.toString(); //返回该对象的字符串表示}
}

125.验证回文串

思路：
方法二：
在原字符串上直接判断
我们可以对方法一中第二种判断回文串的方法进行优化，就可以得到只使用 O(1)O(1) 空间的算法。

我们直接在原字符串 ss 上使用双指针。在移动任意一个指针时，需要不断地向另一指针的方向移动，直到遇到一个字母或数字字符，或者两指针重合为止。也就是说，我们每次将指针移到下一个字母字符或数字字符，再判断这两个指针指向的字符是否相同。

class Solution {public boolean isPalindrome(String s) {int n = s.length();int left = 0, right = n - 1;while (left < right) {while (left < right && !Character.isLetterOrDigit(s.charAt(left))) { //Character.isLetterOrDigit():含有字母。字符串++left;}while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {--right;}if (left < right) {//Character.toLowerCase()将大写转换为小写if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {return false;}++left;--right;}}return true;}
}

383.赎金信

思路：
第一次遍历，记录ransonNote中字母出现的次数；
第二次遍历，记录magazine中字母出现的次数；
然后保证ransonNote中字母出现的次数 <= magazine中相应字母次数即可。

class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] letter1 = new int[128];int[] letter2 = new int[128];
//第一次遍历，记录ransonNote中字母出现的次数；for (int i = 0; i < ransomNote.length(); i++){letter1[ransomNote.charAt(i)]++;}
//第二次遍历，记录magazine中字母出现的次数for (int i = 0; i < magazine.length(); i++){letter2[magazine.charAt(i)]++;}
//保证ransonNote中字母出现的次数 <= magazine中相应字母次数for (int i = 0; i < ransomNote.length(); i++){if (letter1[ransomNote.charAt(i)] > letter2[ransomNote.charAt(i)]){return false;}}return true;}
}

387.字符串中的第一个唯一字符

思路
两个数组，一个记录字母出现次数，一个记录字母第一次出现的位置，遍历次数数组，次数为1的多个字母中，取最先出现的即索引值最小的

int firstUniqChar(char * s) {int count[26]={0};int firstIndex[26]={0};for(int i=0;s[i];++i){int c = s[i]-'a';count[c]++;if(firstIndex[c]==0){ //第一个不重复的字符的索引firstIndex[c]=i;}}int index = INT_MAX;for(int i=0;i<26;++i){if(count[i]==1&&firstIndex[i]<index){index = firstIndex[i];}}return index==INT_MAX?-1:index;
}

434.字符串中的单词数

思路：
简单说，要设立个flag来判断当前遇到的空格是否就是一个单词的分割符号。条件就是在这之前已经出现过非空格的单词了，flag置1。遇到空格就先判断flag是不是1， 是1就算一个单词，然后将flag置零。反之亦然。

int countSegments(char * s)
{int count = 0;char *p = s;int flag = 0; //判断当前空格是否就是一个单词的分隔符while (*p != '\0') {if (*p != ' ') { //在这之前是否出现非空格的单词flag = 1;}if (*p == ' ' && flag == 1) { //遇到空格就判断falg是否为1，是1就是一个单词，然后将falg清零count += 1;flag = 0; }p++;}return count + (flag == 1);
}

443.压缩字符串（没懂）

思路：
用指针anchor指向连续块的起始位置，用指针read指向不同于该连续块字符的第一个位置，用write指针更新字符数组。
read-anchor即为连续块长度，若为1，则不写入，一趟完成后让anchor指向read，即继续扫描下一连续块。

int compress(char* chars, int charsSize){int write = 0;char buf[1000];//anchor：连续块的起始位置，read:不同于该连续块字符的第一个位置,write：更新字符数组for(int read=0,anchor=0; read<charsSize; anchor=read){while(read<charsSize && chars[read]==chars[anchor]){read++; //记录多少个相同的连续字符}chars[write++] = chars[anchor];//若连续长度为1则不写入if(read-anchor==1){ continue;}sprintf(buf,"%d",read-anchor); //将buf作为字符串输出//strnlen()计算给定字符串的长度for(int i=0; i<strlen(buf); i++){ chars[write++] = buf[i];}}return write;
}

459.重复的子字符串

思路：
如果您的字符串S包含一个重复的子字符串，那么这意味着您可以多次“移位和换行”您的字符串，并使其与原始字符串匹配。
例如:abcabc
移位一次:cabcab
移位两次:bcabca
移位三次:abcabc

现在字符串和原字符串匹配了，所以可以得出结论存在重复的子串

基于这个思想，可以每次移动k个字符，直到匹配移动length - 1次。但是这样对于重复字符串很长的字符串，效率会非常低。在LeetCode中执行时间超时了。

为了避免这种无用的环绕，可以创建一个新的字符串str,它等于原来的字符串S再加上S自身，这样其实就包含了所有移动的字符串。

比如字符串：S = acd，那么str = S + S = acdacd

acd移动的可能：dac、cda。其实都包含在了str中了。就像一个滑动窗口

一开始acd (acd) ，移动一次ac(dac)d,移动两次a(cda)cd。循环结束

所以可以直接判断str中去除首尾元素之后，是否包含自身元素。如果包含。则表明存在重复子串。

class Solution {public boolean repeatedSubstringPattern(String s) {String str = s + s;return str.substring(1, str.length() - 1).contains(s);
}
}

暴力代码如下：（没看）（超出时间限制）

class Solution {//暴力代码
public  boolean repeatedSubstringPattern(String s) {for(int i = 1; i < s.length(); i++) {String str = rotate(s.toCharArray(),i);if(s.equals(str)) return true;}return false;}public  String rotate(char[] nums, int k) {k = k % nums.length;reverse(nums, 0, nums.length - 1);reverse(nums, 0, k - 1);reverse(nums, k, nums.length - 1);return String.valueOf(nums);}public  void reverse(char[] nums, int begin, int end) {int i = begin, j = end;while(i < j) {char temp = nums[i];nums[i++] = nums[j];nums[j--] = temp;}}}

520.检测大写字母

思路：
首先把字符串转变为我们熟悉的字符数组
1.分析：题目中给的三种情况我们可以转化一下思路
（1）全是大写字母：大写字母的个数 = 字符数组长度
（2）首字母大写：大写字母个数为1，并且下标为0
（3）全是小写字母：大写字母个数为0
其他情况均返回false
2.问题就转化为了遍历数组，并统计大写字母位置和下标位置（其中只有大写字母个数为1的时候需要用到下标的判断）
3.进行判断
Java：

class Solution {public boolean detectCapitalUse(String word) {char[] chars = word.toCharArray();int index = 0,count = 0;for(int i = 0;i < chars.length;i++){if('A' <= chars[i] && chars[i] <= 'Z'){count++;index = i;}}if(count == chars.length || (count == 1 && index == 0))return true;else if(count == 0)return true;elsereturn false; }
}

521.最长特殊序列I

public class Solution {public int findLUSlength(String a, String b) {if (a.equals(b))return -1;return Math.max(a.length(), b.length());}
}

541.反转字符串II

class Solution {public String reverseStr(String s, int k) {//将字符串中的字符转换为一个字符数组char[] a = s.toCharArray(); //每个块开始于2k的倍数，也就是0,2k,4k,6k,...。//注：如果没有足够的字符，则并不需要翻转这个块    for (int start = 0; start < a.length; start += 2 * k) {int i = start, j = Math.min(start + k - 1, a.length - 1);//为了翻转从i到j的字符块，我们可以交换位于i++和j--的字符while (i < j) { char tmp = a[i];a[i++] = a[j];a[j--] = tmp;}}return new String(a);}
}

551.学生出勤记录I

方法 1：
简单的解法 [Accepted]
解决这个问题最简单的方法就是同济字符串中 AA 的数目并检查 LLLLLL 是否是给定字符串的一个子串。如果 AA 的数目比 22 少且 LLLLLL 不是给定字符串的一个子串，那么返回 truetrue，否则返回 falsefalse。

Java 中indexOfindexOf 方法可以用来检查一个串是否是另一个串的子串。如果找不到子串，那么返回 -1，否则返回这个字符串第一次出现的位置。
Java：

public class Solution {public boolean checkRecord(String s) {int count=0;for(int i=0;i<s.length();i++)if(s.charAt(i)=='A')count++;return count<2 && s.indexOf("LLL")<0;}
}

方法 2：
优化的解法 [Accepted]
算法：
上述方法的一个优化是当 AA 的数目有 22 个的时候就中断循环。

public class Solution {public boolean checkRecord(String s) {int count=0;for(int i=0;i<s.length() && count<2;i++)if(s.charAt(i)=='A')count++;return count<2 && s.indexOf("LLL")<0;}
}

557.反转字符串中的单词III

思路：
1、找出空格并将空格前的单词翻转
2、最后一位的时候，将前面单词翻转

void swap(int left,int right,char *s){ //翻转函数char temp;while(left<right){temp=s[left];s[left]=s[right];s[right]=temp;left++;right--;}
}char * reverseWords(char * s){ //主int i=0,num=0;int len =strlen(s);for(;i<len;i++){if(s[i]==' '){swap(num,i-1,s);num=i+1;}if(i==len-1)swap(num,i,s);}return s;
}

680.验证回文字符串II

class Solution {public boolean validPalindrome(String s) {int low = 0, high = s.length() - 1;while (low < high) {char c1 = s.charAt(low), c2 = s.charAt(high);if (c1 == c2) {low++;high--;} else {boolean flag1 = true, flag2 = true;//删除右边的for (int i = low, j = high - 1; i < j; i++, j--) {char c3 = s.charAt(i), c4 = s.charAt(j);if (c3 != c4) {flag1 = false;break;}}//删除左边的for (int i = low + 1, j = high; i < j; i++, j--) {char c3 = s.charAt(i), c4 = s.charAt(j);if (c3 != c4) {flag2 = false;break;}}//只有满足其中一个为真则返回真return flag1 || flag2;}}return true;}
}

686.重复叠加字符串匹配

class Solution {public int repeatedStringMatch(String A, String B) {int sum=A.length();for(int i=0;i<10000;i++){A=A+A.charAt(i);}int number;//B中字符第一次出现的索引int num=A.indexOf(B); if(num==-1)return -1;//number:B最后一个字符在A中的索引number=num+B.length();if(number%sum==0) //！！！！return number/sum;elsereturn number/sum+1;}
}

696.计数二进制子串

class Solution {public int countBinarySubstrings(String s) {int[] groups = new int[s.length()];int t = 0;groups[0] = 1;for (int i = 1; i < s.length(); i++) {if (s.charAt(i-1) != s.charAt(i)) {groups[++t] = 1;} else {groups[t]++;}}int ans = 0;for (int i = 1; i <= t; i++) {ans += Math.min(groups[i-1], groups[i]);}return ans;}
}

面试题 01.09.字符串轮转

思路：
长度相等时，若s2是s1旋转而成的，那么把s2和自身拼接一次，s1就会出现在其中
“erbottlewat” + “erbottlewat” = erbottle waterbottle wat
如果s2不是s1旋转而成的，那么那么把s2和自身拼接一次，s1就肯定不会出现在其中

class Solution {public boolean isFlipedString(String s1, String s2) {// 长度不相等，肯定不符合要求if (s1.length() != s2.length()) {return false;}// 长度相等时，若s2是s1旋转而成的，那么把s2和自身拼接一次，s1就会出现在其中// "erbottlewat" + "erbottlewat" = erbottle waterbottle wat// 如果s2不是s1旋转而成的，那么那么把s2和自身拼接一次，s1就肯定不会出现在其中return (s2 + s2).indexOf(s1) != -1;}
}

面试题 01.06.字符串压缩

class Solution {/**
*前后双指针
*O(n)
*O(1)
*/
public String compressString(String S) {int len =S.length();if(S==null||len<=1) return S;//StringBuilder：一个可变的字符序列StringBuilder sb = new StringBuilder();  //快慢前后双指针int l=0,r=1;while(r<len){if(S.charAt(r)!=S.charAt(l)){//append()创建了一个新的数组，扩大了长度，将需要添加的字符串添加到这个新的数组中sb.append(S.charAt(l));sb.append((r-l)+"");l=r;r+=1;}else{r++;}}//最后一个相同的字符sb.append(S.charAt(l));sb.append((r-l)+"");//和原字符串比较长度return sb.length()>=len?S:sb.toString();
}}

788.旋转数字

class Solution {public int rotatedDigits(int N) { //主// Count how many n in [1, N] are good.int ans = 0;for (int n = 1; n <= N; ++n)if (good(n, false)) ans++;return ans;}// Return true if n is good.// The flag is true iff we have an occurrence of 2, 5, 6, 9.public boolean good(int n, boolean flag) {if (n == 0) return flag;int d = n % 10;if (d == 3 || d == 4 || d == 7) return false;if (d == 0 || d == 1 || d == 8) return good(n / 10, flag);return good(n / 10, true);}
}

709.转换成小写字母

思路1：

char * toLowerCase(char * str){char *returned=calloc(strlen(str)+1,sizeof(char));int i;for(i=0;i<strlen(str);i++){if(64<str[i]&&str[i]<97)returned[i]=str[i]+32;elsereturned[i]=str[i];}return returned;
}

思路2：
学习使用isupper和tolower函数，提高程序可读性

char *toLowerCase(char *str)
{int len = strlen(str);if (len < 1) {return NULL;}for (int i = 0; i < len; i++) {//isupper:检查所传字符是否为大写字母//tolower:把字母字符转换为小写字母，非字母字符不做处理isupper(str[i]) ? str[i] = tolower(str[i]) : ' ';}return str;
}

剑指Offer 58 - I.翻转单词顺序

PS:strim(),StringBuilder,append(),toString(),charAt()

class Solution {public String reverseWords(String s) {s = s.trim(); // 删除首尾空格int j = s.length() - 1, i = j;StringBuilder res = new StringBuilder();while(i >= 0) {while(i >= 0 && s.charAt(i) != ' ') i--; // 搜索首个空格//substring:返回字符串的子字符串res.append(s.substring(i + 1, j + 1) + " "); // 添加单词while(i >= 0 && s.charAt(i) == ' ') i--; // 跳过单词间空格j = i; // j 指向下个单词的尾字符}return res.toString().trim(); // 转化为字符串并返回}
}

819.最常见的单词（不懂 哈希映射）

class Solution {public String mostCommonWord(String paragraph, String[] banned) {paragraph += ".";Set<String> banset = new HashSet();for (String word: banned) banset.add(word);Map<String, Integer> count = new HashMap();String ans = "";int ansfreq = 0;StringBuilder word = new StringBuilder();for (char c: paragraph.toCharArray()) {if (Character.isLetter(c)) {word.append(Character.toLowerCase(c));} else if (word.length() > 0) {String finalword = word.toString();if (!banset.contains(finalword)) {count.put(finalword, count.getOrDefault(finalword, 0) + 1);if (count.get(finalword) > ansfreq) {ans = finalword;ansfreq = count.get(finalword);}}word = new StringBuilder();}}return ans;}
}

917.仅仅反转字母

**方法 1：**字母栈
想法和算法

将 s 中的所有字母单独存入栈中，所以出栈等价于对字母反序操作。（或者，可以用数组存储字母并反序数组。）

然后，遍历 s 的所有字符，如果是字母我们就选择栈顶元素输出

class Solution {public String reverseOnlyLetters(String S) {Stack<Character> letters = new Stack();for (char c: S.toCharArray()){//isLetter():判定自定字符是否为字母//push()：把对象压入堆栈的顶部if (Character.isLetter(c))letters.push(c);}StringBuilder ans = new StringBuilder();for (char c: S.toCharArray()) {if (Character.isLetter(c))//pop:从集合中把最后一个元素删除，并返回这个元素的值ans.append(letters.pop());elseans.append(c);}return ans.toString();}
}

859.亲密字符串

class Solution {public boolean buddyStrings(String A, String B) {if (A.length() != B.length()) return false;if (A.equals(B)) {int[] count = new int[26];for (int i = 0; i < A.length(); ++i)count[A.charAt(i) - 'a']++;for (int c: count) //？if (c > 1) return true;return false;} else {int first = -1, second = -1;for (int i = 0; i < A.length(); ++i) {if (A.charAt(i) != B.charAt(i)) {if (first == -1)first = i;else if (second == -1)second = i;elsereturn false;}}return (second != -1 && A.charAt(first) == B.charAt(second) &&A.charAt(second) == B.charAt(first));}}}

336.回文对（一点不懂）

涉及知识：
字典树，哈希表

824，山羊拉丁文（没看）

---------------------8.8-----------------------------

1071.字符串的最大公因子

图片解释

class Solution {public String gcdOfStrings(String str1, String str2) {// 假设str1是N个x，str2是M个x，那么str1+str2肯定是等于str2+str1的。if (!(str1 + str2).equals(str2 + str1)) {return "";}// 辗转相除法求gcd。return str1.substring(0, gcd(str1.length(), str2.length()));}private int gcd(int a, int b) {return b == 0? a: gcd(b, a % b);}
}

1170.比较字符串最小字母出现频次（看不懂啊）

1332.删除回文子序列

思路：
只有三种情况：
1.空字符串：删除0次
2.回文字符串：删除1次
3.非回文串 删除2次（一次全部删除a，一次全部删除b）

int removePalindromeSub(char * s){int len = strlen(s);if(len==0){return 0;}int low,hight = len - 1;for(low=0; hight; low++,hight--){if(s[low]!=s[hight]){return 2;}}return 1;
}

1446.连续字符

注：
子串：指的是串中任意个连续的字符组成的子序列，称为改串的子串
子序列：可以是不连续的

思路：
连续相同的字符确定一个区间[left,i)。
left是区间左边界。
i是当前遍历的字符。
当A[i] != A[left]时，表示区间[left,i)结束。i-left就是区间长度，就是可能的解之一。

容易错的地方在于最后一个区间[left,A.length)，没有处理。
当i == A.length时，循环结束。忘记统计此区间的长度，丢失解。

int maxPower(char *s)
{int i;int start;int max_len = 1;int temp_len = 1;start = 0;for (i = 1; i < strlen(s); i++) {if (s[i] == s[start]) {temp_len++;} else {start = i;if (temp_len > max_len) {max_len = temp_len;}temp_len = 1;}}// 最后一句很关键，把最后start直到末尾算出的temp_len和max_len比较一下// 例如“eettt”，计算出的max_len为2，但最后start直到末尾算出的temp_len为3return max_len > temp_len ? max_len : temp_len;
}

剑指Offer 58 - II.左旋转字符串（复习）

class Solution {public String reverseLeftWords(String s, int n) {return s.substring(n, s.length()) + s.substring(0, n);}
}

注：
收藏夹里 多种解法很有意义 还没有仔细看

面试题 01.04. 回文排列

思路：
构成回文的字符串，相同字符的个数中，最多有一个是奇数。超过一个，则不是回文串

bool canPermutePalindrome(char* s){int ascii[128] = {0};int oddSum = 0;for(int i=0;i<strlen(s);i++){ascii[s[i]]++;}for(int i=0;i<128;i++){//相同字符的个数中，最多有一个是奇数if(ascii[i]%2 != 0) {oddSum++;}if(oddSum>1){return false;}}return true;
}

上升下降字符串（没写）

--------------------8.9-------------------

93.复原IP地址（没看）

#define SEG_COUNT 4
int segments[SEG_COUNT];
char** ans;
int ans_len;void dfs(char* s, int segId, int segStart) {// 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案int len_s = strlen(s);if (segId == SEG_COUNT) {if (segStart == len_s) {char* ipAddr = (char*)malloc(sizeof(char) * (len_s + 4));int add = 0;for (int i = 0; i < SEG_COUNT; ++i) {int number = segments[i];if (number >= 100) {ipAddr[add++] = number / 100 + '0';}if (number >= 10) {ipAddr[add++] = number % 100 / 10 + '0';}ipAddr[add++] = number % 10 + '0';if (i != SEG_COUNT - 1) {ipAddr[add++] = '.';}}ipAddr[add] = 0;ans = realloc(ans, sizeof(char*) * (ans_len + 1));ans[ans_len++] = ipAddr;}return;}// 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯if (segStart == len_s) {return;}// 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0if (s[segStart] == '0') {segments[segId] = 0;dfs(s, segId + 1, segStart + 1);}// 一般情况，枚举每一种可能性并递归int addr = 0;for (int segEnd = segStart; segEnd < len_s; ++segEnd) {addr = addr * 10 + (s[segEnd] - '0');if (addr > 0 && addr <= 0xFF) {segments[segId] = addr;dfs(s, segId + 1, segEnd + 1);} else {break;}}
}char** restoreIpAddresses(char* s, int* returnSize) {ans = (char**)malloc(0);ans_len = 0;dfs(s, 0, 0);(*returnSize) = ans_len;return ans;
}

43.字符串相乘

class Solution {public String multiply(String num1, String num2) {  //主//两个字符串都为0if (num1.equals("0") || num2.equals("0")) {return "0";}String ans = "0";int m = num1.length(), n = num2.length();for (int i = n - 1; i >= 0; i--) {//存储和操作可扩充、修改的字符串StringBuffer curr = new StringBuffer();int add = 0;for (int j = n - 1; j > i; j--) {//创建一个新的数组，扩大了长度，将需要添加的字符串复制到这个新的数组中curr.append(0);}int y = num2.charAt(i) - '0';for (int j = m - 1; j >= 0; j--) {//返回索引中的字符int x = num1.charAt(j) - '0';int product = x * y + add;curr.append(product % 10);add = product / 10;}if (add != 0) {curr.append(add % 10);}ans = addStrings(ans, curr.reverse().toString());}return ans;}public String addStrings(String num1, String num2) {int i = num1.length() - 1, j = num2.length() - 1, add = 0;StringBuffer ans = new StringBuffer();while (i >= 0 || j >= 0 || add != 0) {int x = i >= 0 ? num1.charAt(i) - '0' : 0;int y = j >= 0 ? num2.charAt(j) - '0' : 0;int result = x + y + add;ans.append(result % 10);add = result / 10;i--;j--;}ans.reverse();return ans.toString();}
}

--------------8.13------------

1544.整理字符串

Java：
思路一：从头遍历，依次将字符串s的字符入栈，如果当前字符使栈顶字符对应的大小写，则将栈顶元素弹出即可

class Solution {public String makeGood(String s) {if(s.length() == 0 || s.length() == 1) return s;Stack<Character> stack = new Stack<>();//遍历sfor(int i = 0; i < s.length(); i++){char cur = s.charAt(i);//若栈为空，则直接压栈即可if(stack.isEmpty()){stack.push(s.charAt(i));continue;}//栈顶元素char tmp = stack.peek();//如果当前字母是栈顶元素对应的大写或小写，则弹出栈顶元素if(cur-tmp == 32 || cur-tmp == -32){stack.pop();}else{stack.push(cur);}}//将栈中元素依次弹出反转即可String res = "";while(!stack.isEmpty()){res += String.valueOf(stack.peek());stack.pop();}StringBuilder sb = new StringBuilder(res);return sb.reverse().toString();}
}

C：

// 判断是否满足题意的重叠，如果是并记录重叠开始的位置
bool is_overlap(char *s, int *index)
{if (strlen(s) == 0) {return false;}for (int i = 0; i < strlen(s) - 1; i++) {if (abs(s[i] - s[i + 1]) == 'a' - 'A') {*index = i;return true;}}return false;
}char *makeGood(char *s) //主
{int index;// 如果重叠,则删除重叠元素并进行下一次递归；如果最终精简为空串，则判断不重叠，直接返回空串if (is_overlap(s, &index)) {memmove(&s[index], &s[index + 2], (strlen(s) + 1) - (index + 2)); // 长度strlen(s) + 1表示把字符串结尾的'\0'也拷贝进来makeGood(s);}return s;
}

1507.转变日期格式

class Solution {public String reformatDate(String date) {String[] months = {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"};Map<String, Integer> s2month = new HashMap<String, Integer>();//字典映射的方式把月份的英文缩写转换成对应的数字for (int i = 1; i <= 12; i++) {s2month.put(months[i - 1], i);}String[] array = date.split(" ");int year = Integer.parseInt(array[2]);int month = s2month.get(array[1]);int day = Integer.parseInt(array[0].substring(0, array[0].length() - 2));return String.format("%d-%02d-%02d", year, month, day);}
}

1455.检查单词是否为居中其他单词的前缀

int isPrefixOfWord(char * sentence, char * searchWord){int i=0;if(*sentence==*searchWord)      //这个的作用是判断第一个是否符合要求，因为我是以空格为标志的{                               //而第一个单词前面是没有空格的while(searchWord[i]){if(searchWord[i]!=sentence[i]){break;}i++;}if(searchWord[i]==NULL)return 1;}int j=0;int count=1;                //count是计算的是第几个单词while(sentence[i])                //遇到空格就对后续进行判断{                                     if(sentence[i]==' '){i++;count++;while(searchWord[j]){if(searchWord[j]!=sentence[i+j]){break;}j++;}if(searchWord[j]==NULL){return count;}j=0;}i++;}return -1;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！