58.最后一个单词的长度

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

KMP有点难理解了对我而言…看不懂就放两天继续钻，再多看看大佬博客的不同理解，效果会更好。

解题思路

• 参考链接：
  1️⃣
  2️⃣

---

朴素模式匹配BF

首先来个暴力方法：不匹配模式串就右挪一位。

//暴力模式匹配
int 主串位置i；
int 模式串位置j；
int 主串长度；
int 子串长度；

当（主串位置 <= 主串长度 && 模式串位置<模式串长度）:
    如果（该主串位置的主串字符 == 该模式串位置的模式串字符）：
        i++；
        j++；
    否则：
        i后退至上一轮匹配开始位置的后一位；
        j归零；
如果（模式串位置 == 模式串长度）：
    匹配成功，返回出现位置；
否则
    匹配失败，返回-1；

优化模式匹配KMP

即利用已经部分匹配这个信息，保持i指针不回溯，并通过j指针让模式串尽可能移动到更有效的位置。

那么有几个要点：

• 前缀(Prefix)和后缀（Suffix）
  举个🌰，给定一个字符串s:“abcab”,那么:

  s的子串	前缀	后缀
  a	无	无
  ab	a	b
  abc	a,ab	c,bc
  abca	a,ab,abc	a,ca,bca
  abcab	a,ab,abc,abca	b,ab,cab,bcab

• 公共前后缀最长长度
  从上面的前后缀不难看出，对于s的子串，存在部分前后缀重复的情况，我们需要的正是重复子串的最大长度。

  s的子串	前缀	后缀	公共前后缀最长长度
  a	无	无	无
  ab	a	b	无
  abc	a,ab	c,bc	无
  abca	a,ab,abc	a,ca,bca	1
  abcab	a,ab,abc,abca	b,ab,cab,bcab	2

• next数组（部分匹配表）
  KMP的next数组告诉我们：当模式串中的某个字符跟主串中的某个字符失配时，模式串下一步应该跳到哪个位置。

对于s的每个字符而言，当这个字符作为子串的最后一位时，公共前后缀最长长度为：

字符（标红部分）	公共前后缀最长长度
abcab	0
abcab	0
abcab	0
abcab	1
abcab	2

那么全部右移一位，令next[0]=-1：

字符	i	next[i]
a	0	-1
b	1	0
c	2	0
a	3	0
b	4	1

实际匹配过程中，j移动到子串p的next[j]位置，p相对s向右移动j-next[j]位置。

• 迭代法求p的next数组
  我们知道：

next[0]=-1;
next[1]=0;

并且next[j]代表p[0…j-1]的子串公共前后缀最长长度。
∴ 变量定义如下：
j：当前子串指针
k：当前匹配的前后缀长度（=next[j-1]）
next[j]=k：next[0]=-1 即当p[0]都匹配失败时，只能回到j=0重新匹配。

void GetNext(char p[], int next[])
{
    int j = 0, k = -1;
    next[j] = k;
    while (p[j] != '\0')             //遍历整个子串p
    {
        if (k == -1 || p[j] == p[k]) //匹配成功😀或者k=-1（刚匹配到字串的第一个）
        {
            j++;                     //j指针后移
            k++;
            next[j] = k;             //记录当前前后缀匹配长度
        } 
        else 
        {
            k = next[k];             //匹配失败😭，回溯到next[k]寻找更短的前后缀
        }
    }
}

• KMP主算法
  得到next数组的方法GetNext()，就可以完整的写出KMP函数。这里写成一个函数：

int KMP(string s,string p){
    int m=s.size();
    int n=p.size();
    if(m==0){
        return 0;
    }
    //⬇️计算next数组
    vector<int>next;
    int j=0;
    for(int i=0;i<n;i++){
        while(j>0 && p[i]!=p[j]){
            j=next[j-1];
        }
        if(p[i]==p[j]){
            j++;
        }
        next[i]=j;
    }
    //⬇️KMP搜索匹配
    int j=0;
    for(int i=0;i<m;i++){
        while(j>0 && s[i]!=p[j]){
            j=next[j-1];
        }
        if(s[i]==p[j]){
            j++;
        }
        if(j==n){
            return i-n+1;
        }
    }
    return -1;
}

说实话，后半部分现在不能完全理解，让我再多磕几天。

完整代码

class Solution {
public:
    int lengthOfLastWord(string s) {
        int len=s.length();
        int m=0,n=0;
        for(int i=len-1;i>0;i--){
            if(s[i]!=' ' && (s[i+1]==' ' || s[i+1]=='\0')){
                m=i;
            }
            if((s[i-1]==' ' || s[i-1]=='\0') && s[i]!=' '){
                n=i;
                break;
            }
        }
        return m-n+1;
    }
};

1021.删除最外层的括号

有效括号字符串为空 “”、”(“ + A + “)” 或 A + B ，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。
例如，””，”()”，”(())()” 和 “(()(()))” 都是有效的括号字符串。
如果有效字符串 s 非空，且不存在将其拆分为 s = A + B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。
给出一个非空有效字符串 s，考虑将其进行原语化分解，使得：s = P_1 + P_2 + … + P_k，其中 P_i 是有效括号字符串原语。
对 s 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 s 。

提示：

• 1 <= s.length <= 105
• s[i] 为 ‘(‘ 或 ‘)’
• s 是一个有效括号字符串

解题思路

引用官方题解的话：
遍历 s，并用一个栈来表示括号的深度。遇到 ‘(’ 则将字符入栈，遇到 ‘)’ 则将栈顶字符出栈。栈从空到下一次空的过程，则是扫描了一个原语的过程。

完整代码

class Solution {
public:
    string removeOuterParentheses(string s) {
        string res;
        int cnt=0;
        for(char ch:s){
            if(ch==')'){
                cnt--;
            }
            if(cnt>0){
                res.push_back(ch);
            }
            if(ch=='('){
                cnt++;
            }
        }
        return res;
    }
};

859.亲密字符串

给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。
交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。

• 例如，在 “abcd” 中交换下标 0 和下标 2 的元素可以生成 “cbad” 。

提示：

• 1 <= s.length, goal.length <= 2 * 104
• s 和 goal 由小写英文字母组成

解题思路

都去给我关注三叶大佬！
既然交换s中的两个字母==goal，即为亲密。那么：

1. 不亲密
   s与goal长度不同 或 词频不同
2. 亲密

• s与goal不同的的字符串数量为2
  或
• s与goal不同的字符串数量为0 并且 s中存在出现次数>2的字符

PS: 这里评论区特好玩😂“我真傻，真的，”我抬起我没有神采的眼睛来，接着说。“我单知道两个不同的字符互相交换，会生成一个亲密字符串；我不知道相同的字符也会互相换着玩。……” 我接着但是呜咽，说不出成句的话来。（

所以注意：即使一开始s==goal，但是s怎么交换2字符都不能再==goal，也不算亲密。

3. 还有一个代码小细节：为什么是26？
   字符'a' - 'z'共26个。因为题目限定了输入字符串只包含小写字母，所以最多只需要存储26个字符的频次。

完整代码

class Solution {
public:
    bool buddyStrings(string s, string goal) {
        if(s.size()!=goal.size()){
            return false;
        }
        if(s==goal){
            vector<int> cnt(26);
            for(int i=0;i<s.size();i++){
                cnt[s[i]-'a']++;
                if(cnt[s[i]-'a']>1){
                    return true;
                }
            }
            return false;
        }
        else{//记录s和goal不相同的字符位置
            int first,second;
            first=-1;
            second=-1;
            for(int i=0;i<s.size();i++){
                if(s[i]!=goal[i]){
                    if(first==-1){
                        first=i;
                    }
                    else if(second==-1){
                        second=i;
                    }
                    else{
                        return false;
                    }
                }
            }
        //检查是否可以交换
        return (second!=-1 && s[first]==goal[second] && s[second]==goal[first]);
        }
    }
};

3304.找出第K个字符Ⅰ

Alice 和 Bob 正在玩一个游戏。最初，Alice 有一个字符串 word = “a”。
给定一个正整数 k。
现在 Bob 会要求 Alice 执行以下操作 无限次 :

• 将 word 中的每个字符 更改 为英文字母表中的 下一个 字符来生成一个新字符串，并将其 追加 到原始的 word。
  例如，对 “c” 进行操作生成 “cd”，对 “zb” 进行操作生成 “zbac”。
  在执行足够多的操作后， word 中 至少 存在 k 个字符，此时返回 word 中第 k 个字符的值。
  注意，在操作中字符 ‘z’ 可以变成 ‘a’。

提示：

• 1 <= k <= 500

解题思路

主打一个模拟：

1. 构造字符串s

• 初始值为"a"
• 每轮迭代，生成s的副本t，然后每个字符变成它的下一个字母：((word[i]-'a'+1)%26+'a')

  这里用ASCII码运算，因为’a’‘z’为98233,所以word[i]-'a'计算word[i]相对与a的偏移量，即字符word[i]是字母表中的第word[i]-'a'个字母，+1即为后一个字符；
  %26+'a'的原因是：当word[i]为'z'时,让26变回0，所以%26取模。

• 将t拼接回s

2. 终止条件

• 当s.size()>=k时，直接返回s[k-1]

完整代码

c=word[i]

class Solution {
public:
    char kthCharacter(int k) {
        string word="a";
        while(word.size()<k){
            string t;
            for(char c:word){
                t.push_back((c-'a'+1)%26+'a');
            }
            word+=t;
        }
        return word[k-1];
    }
};

1544.整理字符串

给你一个由大小写英文字母组成的字符串 s 。
一个整理好的字符串中，两个相邻字符 s[i] 和 s[i+1]，其中 0<= i <= s.length-2 ，要满足如下条件:

• 若 s[i] 是小写字符，则 s[i+1] 不可以是相同的大写字符。
• 若 s[i] 是大写字符，则 s[i+1] 不可以是相同的小写字符。
  请你将字符串整理好，每次你都可以从字符串中选出满足上述条件的 两个相邻 字符并删除，直到字符串整理好为止。
  请返回整理好的 字符串 。题目保证在给出的约束条件下，测试样例对应的答案是唯一的。
  注意：空字符串也属于整理好的字符串，尽管其中没有任何字符。

提示：

• 1 <= s.length <= 100
• s 只包含小写和大写英文字母

解题思路

一开始直接用erase删符合条件的字符，而且删除后索引没有回退，报错显示 std::out_of_range。
后来用栈来解决：

1. 迭代字符串s，删除互为大小写的字符，其他的正常压栈
2. abs(stk.back() - ch) == 32 栈顶字符和当前字符互为大小写（用abs确保大小写前后顺序都可）

完整代码

class Solution {
public:
    string makeGood(string s) {
        string stk;
        for(char ch:s){
            if(!stk.empty() && abs(stk.back()-ch)==32){
                stk.pop_back();
            }
            else{
                stk.push_back(ch);
            }
        }
        return stk;
    }
};

2116.判断一个括号字符串是否有效

一个括号字符串是只由 ‘(‘ 和 ‘)’ 组成的 非空 字符串。如果一个字符串满足下面 任意一个条件，那么它就是有效的：

• 字符串为 ().
• 它可以表示为 AB（A 与 B 连接），其中A 和 B 都是有效括号字符串。
• 它可以表示为 (A) ，其中 A 是一个有效括号字符串。
  给你一个括号字符串 s 和一个字符串 locked ，两者长度都为 n 。locked >是一个二进制字符串，只包含 ‘0’ 和 ‘1’ 。对于 locked 中 每一个 下标 i ：
• 如果 locked[i] 是 ‘1’ ，你 不能 改变 s[i] 。
• 如果 locked[i] 是 ‘0’ ，你 可以 将 s[i] 变为 ‘(‘ 或者 ‘)’ 。
  如果你可以将s变为有效括号字符串，请你返回true，否则返回false。

提示：

• n == s.length == locked.length
• 1 <= n <= 105
• s[i] 要么是 ‘(‘ 要么是 ‘)’ 。
• locked[i] 要么是 ‘0’ 要么是 ‘1’ 。

解题思路

做到好几个括号匹配问题了，浅总结一下：

👉️括号平衡的核心规则
任何前缀都不能有多余的右括号 & 任何后缀都不能有多余的左括号

❔️为什么要检查前/后缀而不是整个括号字符串？
因为括号是从左到右依次匹配的。一旦前面某个位置出现错误，后面就绝对无法补救。

✅️关键思路

• 前缀遍历判断防止提前失配；后缀遍历防止无法闭合
• 两边遍历保证整体匹配
• 最终判断是否可以调整（locked[i])使其符合匹配规则
• 注意locked也是字符串不是int

完整代码

用时21ms，还有优化空间。

class Solution {
public:
    bool canBeValid(string s, string locked) {
        if(s.size()%2!=0){
            return false;
        }
        int left,right;
        left=right=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='(' || locked[i]=='0'){
                left++;
            }
            else{
                right++;
            }
            if(right>left){
                return false;
            }
        }
        left=right=0;
        for(int i=s.size()-1;i>=0;i--){
            if(s[i]==')' || locked[i]=='0'){
                right++;
            }
            else{
                left++;
            }
            if(left>right){
                return false;
            }
        }
        return true;
    }
};

2255.统计是给定字符串前缀的字符串数目

给你一个字符串数组 words 和一个字符串 s ，其中 words[i] 和 s 只包含 小写英文字母 。
请你返回 words 中是字符串 s 前缀 的 字符串数目 。
一个字符串的 前缀 是出现在字符串开头的子字符串。子字符串 是一个字符串中的连续一段字符序列。

提示：

• 1 <= words.length <= 1000
• 1 <= words[i].length, s.length <= 10
• words[i] 和 s 只 包含小写英文字母。

解题思路

暴力双循环嵌套，第一个substr得子串，第二个判断子串是否与words[i]相等。

完整代码

class Solution {
public:
    int countPrefixes(vector<string>& words, string s) {
        string ch;
        int cnt=0;
        for(int i=0;i<=s.length();i++){
            ch=s.substr(0,i);
            for(int j=0;j<words.size();j++){
                if(words[j]==ch){
                    cnt++;
                }
            }
        }
        return cnt;
    }
};

2716.最小化字符串长度

给你一个下标从 0 开始的字符串 s ，重复执行下述操作 任意 次：
给你一个下标从 0 开始的字符串 s ，重复执行下述操作 任意 次：

• 在字符串中选出一个下标 i ，并使 c 为字符串下标 i 处的字符。并在 i 左侧（如果有）和 右侧（如果有）各 删除 一个距离 i 最近 的字符 c 。
  请你通过执行上述操作任意次，使 s 的长度 最小化 。
  返回一个表示 最小化 字符串的长度的整数。

提示：

• 1 <= s.length <= 100
• s 仅由小写英文字母组成

解题思路

题目这么长，其实就是字符串去重😂

完整代码

1. 我的方法

class Solution {
public:
    int minimizedStringLength(string s) {
        unordered_set<int> num;
        for(char ch:s){
            if(num.find(ch)==num.end()){
                num.insert(ch);
            }
        }
        return num.size();
    }
};

2. 更简洁的方法
   看到题解，发现也可以直接写成一行：

• unordered_set<char>(s.begin(), s.end())
  直接用s.begin()和s.end()构造一个unordered_set，会自动去重字符串中的字符
• .size()
  计算去重后的字符个数

return unoredered_set(s.begin(),s.end().size());

2109.最小化字符串长度

给你一个下标从 0 开始的字符串 s ，以及一个下标从 0 开始的整数数组 spaces 。
数组 spaces 描述原字符串中需要添加空格的下标。每个空格都应该插入到给定索引处的字符值 之前 。

• 例如，s = “EnjoyYourCoffee” 且 spaces = [5, 9] ，那么我们需要在 ‘Y’ 和 ‘C’ 之前添加空格，这两个字符分别位于下标 5 和下标 9 。因此，最终得到 “Enjoy Your Coffee” 。
  请你添加空格，并返回修改后的字符串。

提示：

• 1 <= s.length <= 3 * 105
• s 仅由大小写英文字母组成
• 1 <= spaces.length <= 3 * 105
• 0 <= spaces[i] <= s.length - 1
• spaces 中的所有值严格递增

解题思路

咳咳，虽然用时击败5%，但是自己写出来中等题而且没超时已经很棒了！夸夸自己😂

完整代码

class Solution {
public:
    string addSpaces(string s, vector<int>& spaces) {
        int idx=0,cnt=0;
        for(int i=0;i<s.size();i++){
            while(idx<spaces.size()){
                s.insert(spaces[idx]+cnt," ");
                idx++;
                cnt++;
            }
        }
        return s;
    }
};

2278.字母在字符串中的百分比

给你一个字符串s和一个字符 letter，返回在s中等于letter字符所占的百分比，向下取整到最接近的百分比。

解题思路

我写的时候还很疑惑为什么返回的全是0😅然后意识到：
return (cnt/s.size())*100这样合乎逻辑的写法实际上在这里是错误的。因为cnt/s.size()是整数除法（会直接去掉小数部分），那就必=0，然后0*100还是0，返回的也是0😂

完整代码

class Solution {
public:
    int percentageLetter(string s, char letter) {
        int cnt = 0;
        for (char ch : s) {
            if (ch == letter) {
                cnt++;
            }
        }
        return (cnt * 100) / s.size();  // 先乘 100 再除，确保整数除法不会丢失精度
    }
};

168.Execl表列名称

给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。

解题思路

上来看不明白这题，于是跑去看题解。

这道题其实是一道类似于26进制的数字系统模拟。

1. 列名的构成
   每个列名由字母组成，并且字母的排列规则类似于进制。比如 A 对应 1，B 对应 2，…，Z 对应 26。接着，列名会继续循环，例如 AA 对应 27，AB 对应 28，…

2. 对应关系

• 第 1 列是 A（即 1）
• 第 2 列是 B（即 2）
• …
• 第 26 列是 Z（即 26）
• 第 27 列是 AA（即 27），可以看做是从 A（1）到 Z（26）循环一次

3. 解题思路

• 每次从最右边的字符开始计算
• 注意 Excel 列名从A开始（1），而不是从0开始。所以每次取余的时-1。
  1️⃣模拟进制转换
• 每次对26取余，然后将结果映射到 A-Z
• 然后columnNumber-1，类似于进制中的进位操作
  2️⃣构建列名
• 每次获得一个字符，将其加入列名的最前面，直到 columnNumber=0

完整代码

class Solution {
public:
    string convertToTitle(int columnNumber) {
        string res="";
        while(columnNumber>0){
            columnNumber--;
            res=char(columnNumber%26+'A')+res;
            columnNumber/=26;
        }
        return res;
    }
};

3396.使数组元素互不相同所需的最少操作次数

给你一个整数数组 nums，你需要确保数组中的元素 互不相同 。为此，你可以执行以下操作任意次：
从数组的开头移除 3 个元素。如果数组中元素少于 3 个，则移除所有剩余元素。
注意：空数组也视作为数组元素互不相同。返回使数组元素互不相同所需的 最少操作次数 。

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

解题思路

说实话这道题真难到我了，虽然是道简单题。

1️⃣错误解法注意一开始for循环遍历的同时修改容器：
for(int num:nums)是range-based for loop（基于拷贝值的遍历），是基于nums的快照。但是我在遍历里用了nums.erase(nums.begin(),nums.begin()+3)会导致迭代器失效😂

2️⃣修改方案：

1. 使用无限循环
   直到剩下的数组已经互不相同（flag=false）时跳出。

2. bool flag
   表示当前数组是否有重复元素，初始值为false。

3. 遍历nums
   unordered_set一个arr用来判断重复元素。这部分老操作了，上面有几道也是类似的做法。

   额外的就是要记得有重复元素时flag置为true

4. 进行一次移除操作，计数器加一

• 剩余元素不足三个，直接清空nums
• 否则删除begin()~begin()+3

5. 返回cnt

完整代码

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int cnt=0;
        while(true){
            unordered_set<int> arr;
            bool flag=false;
            for(int num:nums){
                if(arr.find(num)!=arr.end()){
                    flag=true;
                    break;
                }
                arr.insert(num);
            }
            if(flag==false){
                break;
            }
            if(nums.size()<=3){
                nums.clear();
            }
            else{
                nums.erase(nums.begin(),nums.begin()+3);
            }
            cnt++;
        }
        return cnt;
    }
};

594.最长和谐子序列

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。
给你一个整数数组nums，请你在所有可能的子序列中找到最长的和谐子序列的长度。
数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

提示：

• 1 <= nums.length <= 2 * 104
• 109 <= nums[i] <= 109

解题思路

思路非原创。因为我一开始不知道子序列怎么得，所以跑去看题解了，官方这里讲的很明了👍

1. 从小到大排序（直接sort即可）
2. begin/end控制头尾元素下标（我这里用的head/tail）
3. 子序列长度end-begin+1

完整代码

class Solution {
public:
    int findLHS(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int head=0,tail=0,ans=0;
        while(tail<nums.size()){
            while(nums[tail]-nums[head]>1){
                head++;
            }
            if(nums[tail]-nums[head]==1){
                ans=max(ans,tail-head+1);
            }
            tail++;
        }
        return ans;
    }
};