算法闭关修炼百题计划（八）

1.最大连续1的个数II

给定一个二进制数组nums，如果最多可以翻转一个0，则返回数组中连续1的最大个数

之前是Window，其实这个更简单，因为只有0和1，所以求sum就可以直到01的分布了

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int left = 0, right = 0;
        int res = 0, sum = 0;
        while(right < nums.size()){
            sum += nums[right++];
            while(sum < right - left - 1){
                sum -= nums[left++];
            }
            res = max(res, right - left);
        }
        return res;
    }
};

2.长度为k的无重复字符子串

给你一个字符串 S，找出所有长度为 K 且不含重复字符的子串，请你返回全部满足要求的子串的 数目。

以window[c]>1为缩小窗口的条件，而不是长度大于k为缩小窗口的条件，因为如果以无重复为条件的话，当长度为k的时候，无重复的字符也自然为k，这样逻辑清晰简洁。
另外最后找到一个窗口之后必须移动left，不能启动先在while中移动right来被动推动left的移动，因为这样会存在不必要的风险。

class Solution {
public:
    int numKLenSubstrNoRepeats(string s, int k) {
        unordered_map<char, int> window;
        int left = 0, right = 0;
        int ans = 0;
        while(right < s.size()){
            char c = s[right++];
            window[c]++;
            while(window[c] > 1){
                char d = s[left++];
                window[d]--;
            }
            if(right - left == k){
                ans++;
                window[s[left++]]--;
            }
        }
        return ans;
    }
};

3.句子的相似性

输入:
sentence1 = [“great”,“acting”,“skills”],
sentence2 = [“fine”,“drama”,“talent”],
similarPairs = [[“great”,“fine”],[“drama”,“acting”],[“skills”,“talent”]]
输出: true
解释: 这两个句子长度相同，每个单词都相似。

用unordered_map<string, unordered_set< string >>来处理，因为相似的可能是很多个字符串

class Solution {
public:
    bool areSentencesSimilar(vector<string>& sentence1, vector<string>& sentence2, vector<vector<string>>& similarPairs) {
        if(sentence1 == sentence2) return true;
        if(sentence1.size() != sentence2.size()) return false;
        unordered_map<string, unordered_set<string>> similarityMap;
        for(auto & similar : similarPairs){
            similarityMap[similar[0]].insert(similar[1]);
            similarityMap[similar[1]].insert(similar[0]);
        }
        for(int i = 0; i < sentence1.size(); i ++){
            string word1 = sentence1[i];
            string word2 = sentence2[i];
            if(word1 != word2 && !similarityMap[word1].count(word2)) return false;
        }
        return true;
    }
};

4.移位字符串分组

示例 1：
输入：strings = [“abc”,“bcd”,“acef”,“xyz”,“az”,“ba”,“a”,“z”]
输出：[[“acef”],[“a”,“z”],[“abc”,“bcd”,“xyz”],[“az”,“ba”]]

示例 2：
输入：strings = [“a”]
输出：[[“a”]]

分析：
给定一个字符串数组 strings，需要将具有相同“移位序列”的字符串分组。所谓“移位序列”指的是，通过多次“左移”或“右移”操作可以变为相同的字符串。例如，“abc”可以通过连续的右移变为“bcd”、“cde”……，也可以通过左移变为“zab”等。因此，“abc”、“bcd”、“xyz”等字符串具有相同的“移位序列”。

解题思路：
我们可以通过将每个字符串移位的标准化（比如转换到以‘a’开头的形式）来表示“移位序列”。
将转换后的标准形式作为键，使用哈希表存储相同“移位序列”的字符串。

class Solution {
public:
    // Helper function to get the shifted version of a string to a common form
    string shiftToA(const string& s) {
        int offset = s[0] - 'a';
        string shifted;
        for (char c : s) {
            char new_char = (c - offset + 26) % 26 + 'a'; // Circular shift
            shifted += new_char;
        }
        return shifted;
    }
    vector<vector<string>> groupStrings(vector<string>& strings) {
        unordered_map<string, vector<string>> map;
        for (const string& s : strings) {
            string key = shiftToA(s); // Shift string to normalized form
            map[key].push_back(s);
        }

        vector<vector<string>> result;
        for (auto& entry : map) {
            result.push_back(entry.second);
        }
        return result;
    }
};

5.x的平方根

给你一个非负整数x，计算并返回x的算术平方根
由于返回的类型是整数，结果只保留整数部分，小数部分会被舍去
注意：不允许使用任何内置指数函数和算符

思路
对于一个给定的非负整数 x，我们想找到一个整数 y，使得 y * y <= x 并且 (y + 1) * (y + 1) > x。这样 y 就是 x 的整数部分平方根。

二分查找方法
设置左右边界 left = 0 和 right = x。
每次取中点 mid = (left + right) / 2。
检查 mid * mid 与 x 的关系：
如果 mid * mid 等于 x，则 mid 就是平方根，直接返回。
如果 mid * mid 小于 x，说明平方根在 mid 的右边，所以将 left 更新为 mid + 1。
如果 mid * mid 大于 x，说明平方根在 mid 的左边，所以将 right 更新为 mid - 1。
当 left 超过 right 时，right 就是整数部分的平方根。

class Solution {
public:
    int mySqrt(int x) {
        if (x < 2) return x;  // 对于 x = 0 或 1，平方根就是 x 本身

        int left = 1, right = x / 2, result = 0;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid <= x / mid) {  // 防止 mid * mid 溢出，用 x / mid 替代
                result = mid;  // 更新结果
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
};

6.Z字形变换

题目写的很那理解，跟Z几乎没有关系，个人认为是一个无限延长的W，一个字符串s，如果给的行数是4，那么s中每一个字符的行就是1234321234321…

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;  // 如果只有一行，直接返回

        vector<string> rows(min(numRows, int(s.size())));  // 创建一个有 numRows 行的 vector
        int curRow = 0;  // 当前行
        bool goingDown = false;  // 方向标志

        for (char c : s) {
            rows[curRow] += c;  // 将字符添加到当前行
            // 若到达顶部或底部，反转方向
            if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
            // 根据方向更新当前行
            // 如果goingDown是true,就返回1,否则返回-1
            curRow += goingDown ? 1 : -1;
        }

        // 拼接所有行的字符串
        string result;
        for (string row : rows) result += row;
        return result;
    }
};