算法——字符串（1）

2315. 统计星号

给你一个字符串 s ，每 两个 连续竖线 ‘|’ 为 一对 。换言之，第一个和第二个 ‘|’ 为一对，第三个和第四个 ‘|’ 为一对，以此类推。
返回 不在 竖线对之间，s 中 ‘*’ 的数目。
注意，每个竖线 ‘|’ 都会 恰好 属于一个对。

class Solution {
public:
    int countAsterisks(string s) {
      int cnt = 0;//count计数
      int ans = 0;
      for(int i = 0; i < s.size(); i++) {
        if(s[i] == '|') cnt++;
        else {
            if(cnt%2 == 0) {
                ans += (s[i] == '*' ? 1 : 0);//巧妙写法
            }
        } 
      }
      return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

收获：
①思维误区：在把奇数|和偶数|之间的*忽略后，在第一个|前的*and最后一个|后的*计数上出现了误区，不应该想提出来计数，
而是应该直接想对偶数|和奇数|之间的*进行计数操作，因为0也是偶数，就相当于默认-1位置上有个|；
②奇偶互换思维（eg：默认-1有xx，就能从奇数开始）如下：

class Solution {
public:
    int countAsterisks(string s) {
      int cnt = -1, ans = 0;
      for(int i = 0; i < s.size(); i++) {
        if(s[i] == '|') cnt++;
        else {
            if(cnt&1) {//某数和1进行&操作后若其值为0，该数为偶，否则，为奇。
                ans += s[i] == '*' ? 1 : 0;//注意优先级
            }
        } 
      }
      return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

459. 重复的子字符串
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例:
输入: s = “abab”
输出: true
解释: 可由子串 “ab” 重复两次构成。

class Solution {
    bool multiple(const string& s, int len) {
        int n = s.size();
        int cnt = n/len;
        for(int i = 0; i < cnt; i++) {
            for(int j = 0; j < len; j++) {
                if(s[i*len+j] != s[j])
                    return false;
            }
        }
        return true;
    }
public:
    bool repeatedSubstringPattern(string s) {
       int n = s.size();
       for(int i = 1; i < n; i++) {
           if(n%i == 0) {
               if(multiple(s, i)) {
                   return true;
               }
           }
       }
        return false;      
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

收获：
①思维误区：重复子串不能依据用a[0]和a[i]判断开头一致：

eg：abab此时ab与ab开头都是a 子串一致 可以判断为true
  abadabad 此时ab与ad开头都是a 子串不一致 但是不能就此判断为false
  不可以
1
2
3

而是直接用分段来研究，一段段比，一字字比；

---

1984. 学生分数的最小差值

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        int n = nums.size();//向量可以用c.size()数组不行
        //先排序，框起来的最右边的永远是max，左边永远是min
        sort(nums.begin(), nums.end());//c.begin(), c.end() 向量特有
        int ans = INT_MAX;//C/C++整型上下限INT_MAX, INT_MIN
        for (int i = 0; i + k - 1 < n; ++i) {
            ans = min(ans, nums[i + k - 1] - nums[i]);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

---