文章目錄

• 3.無(wú)重復(fù)字符的最長(zhǎng)子串
• 415.字符串相加
• 345.反轉(zhuǎn)字符串中的元音字母
• 14.最長(zhǎng)公共前綴
• 28.實(shí)現(xiàn)strStr()
• 58.最后一個(gè)單詞的長(zhǎng)度
• 67.二進(jìn)制求和
• 38.外觀數(shù)列
• 125.驗(yàn)證回文串
• 383.贖金信
• 387.字符串中的第一個(gè)唯一字符
• 434.字符串中的單詞數(shù)
• 443.壓縮字符串（沒懂）
• 459.重復(fù)的子字符串
• 520.檢測(cè)大寫字母
• 521.最長(zhǎng)特殊序列I
• 541.反轉(zhuǎn)字符串II
• 551.學(xué)生出勤記錄I
• 557.反轉(zhuǎn)字符串中的單詞III
• 680.驗(yàn)證回文字符串II
• 686.重復(fù)疊加字符串匹配
• 696.計(jì)數(shù)二進(jìn)制子串
• 面試題 01.09.字符串輪轉(zhuǎn)
• 面試題 01.06.字符串壓縮
• 788.旋轉(zhuǎn)數(shù)字
• 709.轉(zhuǎn)換成小寫字母
• 劍指Offer 58 - I.翻轉(zhuǎn)單詞順序
• 819.最常見的單詞（不懂 哈希映射）
• 917.僅僅反轉(zhuǎn)字母
• 859.親密字符串
• 336.回文對(duì)（一點(diǎn)不懂）
• 824，山羊拉丁文（沒看）
• ---------------------8.8-----------------------------
• 1071.字符串的最大公因子
• 1170.比較字符串最小字母出現(xiàn)頻次（看不懂啊）
• 1332.刪除回文子序列
• 1446.連續(xù)字符
• 劍指Offer 58 - II.左旋轉(zhuǎn)字符串（復(fù)習(xí)）
• 面試題 01.04. 回文排列
• 上升下降字符串（沒寫）
• --------------------8.9-------------------
• 93.復(fù)原IP地址（沒看）
• 43.字符串相乘
• --------------8.13------------
• 1544.整理字符串
• 1507.轉(zhuǎn)變?nèi)掌诟袷?/li>
• 1455.檢查單詞是否為居中其他單詞的前綴

3.無(wú)重復(fù)字符的最長(zhǎng)子串

class Solution {public int lengthOfLongestSubstring(String s) {// 哈希集合，記錄每個(gè)字符是否出現(xiàn)過Set<Character> occ = new HashSet<Character>();int n = s.length();// 右指針，初始值為 -1，相當(dāng)于我們?cè)谧址淖筮吔绲淖髠?cè)，還沒有開始移動(dòng)int rk = -1, ans = 0;for (int i = 0; i < n; ++i) {if (i != 0) {// 左指針向右移動(dòng)一格，移除一個(gè)字符occ.remove(s.charAt(i - 1));}while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {// 不斷地移動(dòng)右指針occ.add(s.charAt(rk + 1));++rk;}// 第 i 到 rk 個(gè)字符是一個(gè)極長(zhǎng)的無(wú)重復(fù)字符子串ans = Math.max(ans, rk - i + 1);}return ans;} } #define LEN 128 //ASCIIint lengthOfLongestSubstring(char * s) {int hset[LEN]; //存儲(chǔ)數(shù)組下標(biāo)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; // 更新為重復(fù)字符的下一個(gè)位置count = i - start; // 重置計(jì)數(shù)器}hset[s[i]] = i;count++;if (count > max) {max = count;}}return max; }

415.字符串相加

思路：
借鑒初學(xué)加法時(shí)的列豎式計(jì)算

char* addStrings(char* num1, char* num2) {//i,j:兩個(gè)相加的字符串各自的長(zhǎng)度，add:進(jìn)位int i = strlen(num1) - 1, j = strlen(num2) - 1, add = 0;//初始化"和"char* ans = (char*)malloc(sizeof(char) * (fmax(i, j) + 3));//定義"和"的長(zhǎng)度int len = 0;while (i >= 0 || j >= 0 || add != 0) {int x = i >= 0 ? num1[i] - '0' : 0; //對(duì)位數(shù)較短的數(shù)補(bǔ)0int y = j >= 0 ? num2[j] - '0' : 0;int result = x + y + add;ans[len++] = '0' + result % 10; //儲(chǔ)存每一位計(jì)算的結(jié)果add = result / 10; //儲(chǔ)存進(jìn)位i--, j--;}// 計(jì)算完以后的答案需要翻轉(zhuǎn)過來(lái)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; //"和"字符串結(jié)束的標(biāo)志return ans; }

345.反轉(zhuǎn)字符串中的元音字母

思路:
雙指針法，遇到元音字母交換

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.最長(zhǎng)公共前綴

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.實(shí)現(xiàn)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.最后一個(gè)單詞的長(zhǎng)度

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.二進(jìn)制求和

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();} }

相關(guān)知識(shí)點(diǎn):
append()：創(chuàng)建了一個(gè)新的數(shù)組，擴(kuò)大了長(zhǎng)度，將需要添加的字符串給復(fù)制到這個(gè)新的數(shù)組中

JAVA中Stringbuffer有append( )方法：
而Stringbuffer是動(dòng)態(tài)字符串?dāng)?shù)組，append( )是往動(dòng)態(tài)字符串?dāng)?shù)組添加，跟“xxxx”+“yyyy”相當(dāng)‘+’號(hào)。

跟String不同的是Stringbuffer是放一起的，String1+String2和Stringbuffer1.append(“yyyy”)雖然打印效果一樣，但在內(nèi)存中表示卻不一樣、

String1+String2 存在于不同的兩個(gè)地址內(nèi)存，Stringbuffer1.append(Stringbuffer2)放再一起。

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

38.外觀數(shù)列

思路：
遞歸，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(); //返回該對(duì)象的字符串表示} }

125.驗(yàn)證回文串

思路：
方法二：
在原字符串上直接判斷
我們可以對(duì)方法一中第二種判斷回文串的方法進(jìn)行優(yōu)化，就可以得到只使用 O(1)O(1) 空間的算法。

我們直接在原字符串 ss 上使用雙指針。在移動(dòng)任意一個(gè)指針時(shí)，需要不斷地向另一指針的方向移動(dòng)，直到遇到一個(gè)字母或數(shù)字字符，或者兩指針重合為止。也就是說(shuō)，我們每次將指針移到下一個(gè)字母字符或數(shù)字字符，再判斷這兩個(gè)指針指向的字符是否相同。

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()將大寫轉(zhuǎn)換為小寫if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {return false;}++left;--right;}}return true;} }

383.贖金信

思路：
第一次遍歷，記錄ransonNote中字母出現(xiàn)的次數(shù)；
第二次遍歷，記錄magazine中字母出現(xiàn)的次數(shù)；
然后保證ransonNote中字母出現(xiàn)的次數(shù) <= magazine中相應(yīng)字母次數(shù)即可。

class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] letter1 = new int[128];int[] letter2 = new int[128]; //第一次遍歷，記錄ransonNote中字母出現(xiàn)的次數(shù)；for (int i = 0; i < ransomNote.length(); i++){letter1[ransomNote.charAt(i)]++;} //第二次遍歷，記錄magazine中字母出現(xiàn)的次數(shù)for (int i = 0; i < magazine.length(); i++){letter2[magazine.charAt(i)]++;} //保證ransonNote中字母出現(xiàn)的次數(shù) <= magazine中相應(yīng)字母次數(shù)for (int i = 0; i < ransomNote.length(); i++){if (letter1[ransomNote.charAt(i)] > letter2[ransomNote.charAt(i)]){return false;}}return true;} }

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

思路
兩個(gè)數(shù)組，一個(gè)記錄字母出現(xiàn)次數(shù)，一個(gè)記錄字母第一次出現(xiàn)的位置，遍歷次數(shù)數(shù)組，次數(shù)為1的多個(gè)字母中，取最先出現(xiàn)的即索引值最小的

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){ //第一個(gè)不重復(fù)的字符的索引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.字符串中的單詞數(shù)

思路：
簡(jiǎn)單說(shuō)，要設(shè)立個(gè)flag來(lái)判斷當(dāng)前遇到的空格是否就是一個(gè)單詞的分割符號(hào)。條件就是在這之前已經(jīng)出現(xiàn)過非空格的單詞了，flag置1。遇到空格就先判斷flag是不是1， 是1就算一個(gè)單詞，然后將flag置零。反之亦然。

int countSegments(char * s) {int count = 0;char *p = s;int flag = 0; //判斷當(dāng)前空格是否就是一個(gè)單詞的分隔符while (*p != '\0') {if (*p != ' ') { //在這之前是否出現(xiàn)非空格的單詞flag = 1;}if (*p == ' ' && flag == 1) { //遇到空格就判斷falg是否為1，是1就是一個(gè)單詞，然后將falg清零count += 1;flag = 0; }p++;}return count + (flag == 1); }

443.壓縮字符串（沒懂）

思路：
用指針anchor指向連續(xù)塊的起始位置，用指針read指向不同于該連續(xù)塊字符的第一個(gè)位置，用write指針更新字符數(shù)組。
read-anchor即為連續(xù)塊長(zhǎng)度，若為1，則不寫入，一趟完成后讓anchor指向read，即繼續(xù)掃描下一連續(xù)塊。

int compress(char* chars, int charsSize){int write = 0;char buf[1000];//anchor：連續(xù)塊的起始位置，read:不同于該連續(xù)塊字符的第一個(gè)位置,write：更新字符數(shù)組for(int read=0,anchor=0; read<charsSize; anchor=read){while(read<charsSize && chars[read]==chars[anchor]){read++; //記錄多少個(gè)相同的連續(xù)字符}chars[write++] = chars[anchor];//若連續(xù)長(zhǎng)度為1則不寫入if(read-anchor==1){ continue;}sprintf(buf,"%d",read-anchor); //將buf作為字符串輸出//strnlen()計(jì)算給定字符串的長(zhǎng)度for(int i=0; i<strlen(buf); i++){ chars[write++] = buf[i];}}return write; }

459.重復(fù)的子字符串

思路：
如果您的字符串S包含一個(gè)重復(fù)的子字符串，那么這意味著您可以多次“移位和換行”您的字符串，并使其與原始字符串匹配。
例如:abcabc
移位一次:cabcab
移位兩次:bcabca
移位三次:abcabc

現(xiàn)在字符串和原字符串匹配了，所以可以得出結(jié)論存在重復(fù)的子串

基于這個(gè)思想，可以每次移動(dòng)k個(gè)字符，直到匹配移動(dòng)length - 1次。但是這樣對(duì)于重復(fù)字符串很長(zhǎng)的字符串，效率會(huì)非常低。在LeetCode中執(zhí)行時(shí)間超時(shí)了。

為了避免這種無(wú)用的環(huán)繞，可以創(chuàng)建一個(gè)新的字符串str,它等于原來(lái)的字符串S再加上S自身，這樣其實(shí)就包含了所有移動(dòng)的字符串。

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

acd移動(dòng)的可能：dac、cda。其實(shí)都包含在了str中了。就像一個(gè)滑動(dòng)窗口

一開始acd (acd) ，移動(dòng)一次ac(dac)d,移動(dòng)兩次a(cda)cd。循環(huán)結(jié)束

所以可以直接判斷str中去除首尾元素之后，是否包含自身元素。如果包含。則表明存在重復(fù)子串。

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

暴力代碼如下：（沒看）（超出時(shí)間限制）

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.檢測(cè)大寫字母

思路：
首先把字符串轉(zhuǎn)變?yōu)槲覀兪煜さ淖址麛?shù)組
1.分析：題目中給的三種情況我們可以轉(zhuǎn)化一下思路
（1）全是大寫字母：大寫字母的個(gè)數(shù) = 字符數(shù)組長(zhǎng)度
（2）首字母大寫：大寫字母?jìng)€(gè)數(shù)為1，并且下標(biāo)為0
（3）全是小寫字母：大寫字母?jìng)€(gè)數(shù)為0
其他情況均返回false
2.問題就轉(zhuǎn)化為了遍歷數(shù)組，并統(tǒng)計(jì)大寫字母位置和下標(biāo)位置（其中只有大寫字母?jìng)€(gè)數(shù)為1的時(shí)候需要用到下標(biāo)的判斷）
3.進(jìn)行判斷
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.最長(zhǎng)特殊序列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.反轉(zhuǎn)字符串II

class Solution {public String reverseStr(String s, int k) {//將字符串中的字符轉(zhuǎn)換為一個(gè)字符數(shù)組char[] a = s.toCharArray(); //每個(gè)塊開始于2k的倍數(shù)，也就是0,2k,4k,6k,...。//注：如果沒有足夠的字符，則并不需要翻轉(zhuǎn)這個(gè)塊 for (int start = 0; start < a.length; start += 2 * k) {int i = start, j = Math.min(start + k - 1, a.length - 1);//為了翻轉(zhuǎn)從i到j(luò)的字符塊，我們可以交換位于i++和j--的字符while (i < j) { char tmp = a[i];a[i++] = a[j];a[j--] = tmp;}}return new String(a);} }

551.學(xué)生出勤記錄I

方法 1：
簡(jiǎn)單的解法 [Accepted]
解決這個(gè)問題最簡(jiǎn)單的方法就是同濟(jì)字符串中 AA 的數(shù)目并檢查 LLLLLL 是否是給定字符串的一個(gè)子串。如果 AA 的數(shù)目比 22 少且 LLLLLL 不是給定字符串的一個(gè)子串，那么返回 truetrue，否則返回 falsefalse。

Java 中indexOfindexOf 方法可以用來(lái)檢查一個(gè)串是否是另一個(gè)串的子串。如果找不到子串，那么返回 -1，否則返回這個(gè)字符串第一次出現(xiàn)的位置。
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：
優(yōu)化的解法 [Accepted]
算法：
上述方法的一個(gè)優(yōu)化是當(dāng) AA 的數(shù)目有 22 個(gè)的時(shí)候就中斷循環(huán)。

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.反轉(zhuǎn)字符串中的單詞III

思路：
1、找出空格并將空格前的單詞翻轉(zhuǎn)
2、最后一位的時(shí)候，將前面單詞翻轉(zhuǎn)

void swap(int left,int right,char *s){ //翻轉(zhuǎn)函數(shù)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.驗(yàn)證回文字符串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;}}//只有滿足其中一個(gè)為真則返回真return flag1 || flag2;}}return true;} }

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

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中字符第一次出現(xiàn)的索引int num=A.indexOf(B); if(num==-1)return -1;//number:B最后一個(gè)字符在A中的索引number=num+B.length();if(number%sum==0) //！！！！return number/sum;elsereturn number/sum+1;} }

696.計(jì)數(shù)二進(jìn)制子串

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.字符串輪轉(zhuǎn)

思路：
長(zhǎng)度相等時(shí)，若s2是s1旋轉(zhuǎn)而成的，那么把s2和自身拼接一次，s1就會(huì)出現(xiàn)在其中
“erbottlewat” + “erbottlewat” = erbottle waterbottle wat
如果s2不是s1旋轉(zhuǎn)而成的，那么那么把s2和自身拼接一次，s1就肯定不會(huì)出現(xiàn)在其中

class Solution {public boolean isFlipedString(String s1, String s2) {// 長(zhǎng)度不相等，肯定不符合要求if (s1.length() != s2.length()) {return false;}// 長(zhǎng)度相等時(shí)，若s2是s1旋轉(zhuǎn)而成的，那么把s2和自身拼接一次，s1就會(huì)出現(xiàn)在其中// "erbottlewat" + "erbottlewat" = erbottle waterbottle wat// 如果s2不是s1旋轉(zhuǎn)而成的，那么那么把s2和自身拼接一次，s1就肯定不會(huì)出現(xiàn)在其中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：一個(gè)可變的字符序列StringBuilder sb = new StringBuilder(); //快慢前后雙指針int l=0,r=1;while(r<len){if(S.charAt(r)!=S.charAt(l)){//append()創(chuàng)建了一個(gè)新的數(shù)組，擴(kuò)大了長(zhǎng)度，將需要添加的字符串添加到這個(gè)新的數(shù)組中sb.append(S.charAt(l));sb.append((r-l)+"");l=r;r+=1;}else{r++;}}//最后一個(gè)相同的字符sb.append(S.charAt(l));sb.append((r-l)+"");//和原字符串比較長(zhǎng)度return sb.length()>=len?S:sb.toString(); }}

788.旋轉(zhuǎn)數(shù)字

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.轉(zhuǎn)換成小寫字母

思路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：
學(xué)習(xí)使用isupper和tolower函數(shù)，提高程序可讀性

char *toLowerCase(char *str) {int len = strlen(str);if (len < 1) {return NULL;}for (int i = 0; i < len; i++) {//isupper:檢查所傳字符是否為大寫字母//tolower:把字母字符轉(zhuǎn)換為小寫字母，非字母字符不做處理isupper(str[i]) ? str[i] = tolower(str[i]) : ' ';}return str; }

劍指Offer 58 - I.翻轉(zhuǎn)單詞順序

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--; // 搜索首個(gè)空格//substring:返回字符串的子字符串res.append(s.substring(i + 1, j + 1) + " "); // 添加單詞while(i >= 0 && s.charAt(i) == ' ') i--; // 跳過單詞間空格j = i; // j 指向下個(gè)單詞的尾字符}return res.toString().trim(); // 轉(zhuǎn)化為字符串并返回} }

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.僅僅反轉(zhuǎn)字母

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

將 s 中的所有字母單獨(dú)存入棧中，所以出棧等價(jià)于對(duì)字母反序操作。（或者，可以用數(shù)組存儲(chǔ)字母并反序數(shù)組。）

然后，遍歷 s 的所有字符，如果是字母我們就選擇棧頂元素輸出

class Solution {public String reverseOnlyLetters(String S) {Stack<Character> letters = new Stack();for (char c: S.toCharArray()){//isLetter():判定自定字符是否為字母//push()：把對(duì)象壓入堆棧的頂部if (Character.isLetter(c))letters.push(c);}StringBuilder ans = new StringBuilder();for (char c: S.toCharArray()) {if (Character.isLetter(c))//pop:從集合中把最后一個(gè)元素刪除，并返回這個(gè)元素的值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.回文對(duì)（一點(diǎn)不懂）

涉及知識(shí)：
字典樹，哈希表

824，山羊拉丁文（沒看）

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

1071.字符串的最大公因子

圖片解釋

class Solution {public String gcdOfStrings(String str1, String str2) {// 假設(shè)str1是N個(gè)x，str2是M個(gè)x，那么str1+str2肯定是等于str2+str1的。if (!(str1 + str2).equals(str2 + str1)) {return "";}// 輾轉(zhuǎn)相除法求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.比較字符串最小字母出現(xiàn)頻次（看不懂啊）

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.連續(xù)字符

注：
子串：指的是串中任意個(gè)連續(xù)的字符組成的子序列，稱為改串的子串
子序列：可以是不連續(xù)的

思路：
連續(xù)相同的字符確定一個(gè)區(qū)間[left,i)。
left是區(qū)間左邊界。
i是當(dāng)前遍歷的字符。
當(dāng)A[i] != A[left]時(shí)，表示區(qū)間[left,i)結(jié)束。i-left就是區(qū)間長(zhǎng)度，就是可能的解之一。

容易錯(cuò)的地方在于最后一個(gè)區(qū)間[left,A.length)，沒有處理。
當(dāng)i == A.length時(shí)，循環(huán)結(jié)束。忘記統(tǒng)計(jì)此區(qū)間的長(zhǎng)度，丟失解。

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;}}// 最后一句很關(guān)鍵，把最后start直到末尾算出的temp_len和max_len比較一下// 例如“eettt”，計(jì)算出的max_len為2，但最后start直到末尾算出的temp_len為3return max_len > temp_len ? max_len : temp_len; }

劍指Offer 58 - II.左旋轉(zhuǎn)字符串（復(fù)習(xí)）

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

注：
收藏夾里 多種解法很有意義 還沒有仔細(xì)看

面試題 01.04. 回文排列

思路：
構(gòu)成回文的字符串，相同字符的個(gè)數(shù)中，最多有一個(gè)是奇數(shù)。超過一個(gè)，則不是回文串

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++){//相同字符的個(gè)數(shù)中，最多有一個(gè)是奇數(shù)if(ascii[i]%2 != 0) {oddSum++;}if(oddSum>1){return false;}}return true; }

上升下降字符串（沒寫）

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

93.復(fù)原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 地址就已經(jīng)遍歷完了字符串，那么提前回溯if (segStart == len_s) {return;}// 由于不能有前導(dǎo)零，如果當(dāng)前數(shù)字為 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) { //主//兩個(gè)字符串都為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--) {//存儲(chǔ)和操作可擴(kuò)充、修改的字符串StringBuffer curr = new StringBuffer();int add = 0;for (int j = n - 1; j > i; j--) {//創(chuàng)建一個(gè)新的數(shù)組，擴(kuò)大了長(zhǎng)度，將需要添加的字符串復(fù)制到這個(gè)新的數(shù)組中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的字符入棧，如果當(dāng)前字符使棧頂字符對(duì)應(yīng)的大小寫，則將棧頂元素彈出即可

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();//如果當(dāng)前字母是棧頂元素對(duì)應(yīng)的大寫或小寫，則彈出棧頂元素if(cur-tmp == 32 || cur-tmp == -32){stack.pop();}else{stack.push(cur);}}//將棧中元素依次彈出反轉(zhuǎn)即可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;// 如果重疊,則刪除重疊元素并進(jìn)行下一次遞歸；如果最終精簡(jiǎn)為空串，則判斷不重疊，直接返回空串if (is_overlap(s, &index)) {memmove(&s[index], &s[index + 2], (strlen(s) + 1) - (index + 2)); // 長(zhǎng)度strlen(s) + 1表示把字符串結(jié)尾的'\0'也拷貝進(jìn)來(lái)makeGood(s);}return s; }

1507.轉(zhuǎn)變?nèi)掌诟袷?/h1>

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>();//字典映射的方式把月份的英文縮寫轉(zhuǎn)換成對(duì)應(yīng)的數(shù)字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) //這個(gè)的作用是判斷第一個(gè)是否符合要求，因?yàn)槲沂且钥崭駷闃?biāo)志的{ //而第一個(gè)單詞前面是沒有空格的while(searchWord[i]){if(searchWord[i]!=sentence[i]){break;}i++;}if(searchWord[i]==NULL)return 1;}int j=0;int count=1; //count是計(jì)算的是第幾個(gè)單詞while(sentence[i]) //遇到空格就對(duì)后續(xù)進(jìn)行判斷{ 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; }

總結(jié)

以上是生活随笔為你收集整理的LeetCode_字符串类的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。