【小白刷题之路Day30】leetcode5207. 尽可能使字符串相等（leetcode第156周周赛第二题）

• 周赛总结

1. 基础太差太差，主要是C++模板编程，基本语法与C语言相通，所以没问题，涉及到STL模板使用的，一脸蒙蔽，边百度边写，能做好个锤子！！！！

• vector模板： vector<int> nums(10, 0)  使用vector模板声明并初始化一维整数数组
  • • vector<vector<int>> dp(100, <vector<int>>(2, 0))  vector定义二维数组，100*2大小，初始化为0

　　　　为了这个二维数组浪费了起码二十分钟！！！

• 子串与子序列傻傻分不清，子串是连续的，子序列是不连续的，重要事情必须记住，我就不三遍了。

　　　　用子序列去做子串的题，起码也浪费了二十分钟。

• unordered_map，不知道查看一个key有没有在字典中，查了至少5分钟！！！

　　　　定义模板迭代器：unordered_map<int,int>::iterator it;

　　　　map.find()函数查看是否有该键：if (map1.find(arr[i]) == map1.end())

　　　　可以看出：若有该键返回该迭代器，没有该键返回map.end()

 

 　　　 map的遍历：it迭代器访问key, value:

　　　　　　　　　　it->first   it->second

• 滑动窗口法目前还不熟练，需要强化练习！！！

 

 

第一次通过：二维dp数组做的

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int max_len = 0;
        vector<int> nums(t.size(), 0);  // 一维数组
        vector<vector<int>> dp(t.size(), vector<int>(2, 0));   // 二维vector数组及初始化
        
        for (int i=0; i<s.size(); ++i){
            nums[i] = abs(s[i] - t[i]);            
        }
        
        // dp数组初始化   dp的初始化很重要，要细心！！！
        if (nums[0] <= maxCost){
            dp[0][0] = nums[0];
            dp[0][1] = 1;
            max_len = 1;
        }
        
        for (int i=1; i<s.size(); ++i){
            if (dp[i-1][0]+nums[i] <= maxCost){
                dp[i][0] = dp[i-1][0] + nums[i];
                dp[i][1] = dp[i-1][1] + 1;
            }
            else{
                int tmp = dp[i-1][0], j;
                for (j=i-dp[i-1][1]; j<=i; ++j){
                    tmp -= nums[j];
                    if (tmp+nums[i] <= maxCost)
                        break;
                }
                dp[i][0] = tmp+nums[i];
                dp[i][1] = i - j;                
            }
            max_len = max(max_len, dp[i][1]);            
        }
        
        return max_len;
    }
};

因为子串都是连续的，所以容易想到使用滑动窗口法来做，而且元素都>=0，滑动窗口不会往回返！！！

class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int max_len = 0;
        vector<int> nums(s.size(), 0);
        
        for (int i=0; i<s.size(); ++i)
            nums[i] = abs(s[i] - t[i]);
        
        int start = 0, end = 0, sum_tmp = 0;
        for (; end<s.size(); ++end){
            sum_tmp += nums[end];
            if (sum_tmp <= maxCost)
                continue;
            else{
                max_len = max(max_len, end-start);
                while (sum_tmp > maxCost){
                    sum_tmp -= nums[start];
                    ++start;
                }
            }            
        }

        return max(max_len, end-start);
    }
};

使用滑动窗口法显然更好，

思路清晰、代码简洁、时间空间复杂度有显著降低，简直完美！！！。