• leetcode - 串联所有单词的子串 - 最小覆盖子串 - x 的平方根

    I30. 串联所有单词的子串 - 力扣（LeetCode）

    给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

     s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。

    • 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

    返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

    1. 示例 1：
    2.  
    3. 输入：s = "barfoothefoobarman", words = ["foo","bar"]
    4. 输出：[0,9]
    5. 解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
    6. 子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
    7. 子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
    8. 输出顺序无关紧要。返回 [9,0] 也是可以的。
    9. 示例 2：
    10.  
    11. 输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
    12. 输出：[]
    13. 解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
    14. s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
    15. 所以我们返回一个空数组。
    16. 示例 3：
    17.  
    18. 输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
    19. 输出：[6,9,12]
    20. 解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
    21. 子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
    22. 子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
    23. 子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

    这个题目就是 找到字符串中所有字母异位词 这个题目的升级版，具体可以看一下博客：
    leetcode 刷题 - 最大连续1的个数 - 将 x 减到 0 的最小操作数 - 水果成篮 - 找到字符串中所有字母异位词-CSDN博客

    其实就是把 找到字符串中所有字母异位词 这个题目 当中的 字符换成了 字符串。

    所以，其实基本思想还是和 找到字符串中所有字母异位词 这个题目 一样的，只不过，hash表不能再用 数组来模拟了，要使用 hash容器。

    而且，left 和 right 迭代器方式也不再是一步一步的向后移动了，而是一个子串的一个子串的移动。

    而且，在这个题目当中，滑动窗口的 起始位置可能不是 从数组的最开始位置开始的，可能从 第二，第三··· 都有可能，但是，如果超过了 words 数组当中一个子串的 大小，那么后续就会是重复的。

    所以，我们的滑动窗口，不能像 之前题目当中，只滑动一遍数组，而是要滑动 len 次数组（其实位置依次往后移一个字符），len就是words 当中子串的字符个数。

    完整代码：

    1. class Solution
    2. {
    3. public:
    4.     vector<int> findSubstring(string s, vector& words)
    5.     {
    6.         vector<int> ret;
    7.         unordered_mapint> hash1; // 保存 words ⾥⾯所有单词的频次
    8.         for (auto& s : words) hash1[s]++;
    9.         int len = words[0].size(), m = words.size();
    10.         for (int i = 0; i < len; i++) // 执⾏ len 次
    11.         {
    12.             unordered_mapint> hash2; // 维护窗⼝内单词的频次
    13.             for (int left = i, right = i, count = 0; right + len <= s.size();
    14.                 right += len)
    15.             {
    16.                 // 进窗⼝ + 维护 count
    17.                 string in = s.substr(right, len);
    18.                 hash2[in]++;
    19.                 if (hash1.count(in) && hash2[in] <= hash1[in]) count++;
    20.                 // 判断
    21.                 if (right - left + 1 > len * m)
    22.                 {
    23.                     // 出窗⼝ + 维护 count
    24.                     string out = s.substr(left, len);
    25.                     if (hash1.count(out) && hash2[out] <= hash1[out]) count--;
    26.                     hash2[out]--;
    27.                     left += len;
    28.                 }
    29.                 // 更新结果
    30.                 if (count == m) ret.push_back(left);
    31.             }
    32.         }
    33.         return ret;
    34.     }
    35. };

    I76. 最小覆盖子串 - 力扣（LeetCode）

    给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

    注意：

    • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
    • 如果 s 中存在这样的子串，我们保证它是唯一的答案。
    1. 示例 1：
    2.  
    3. 输入：s = "ADOBECODEBANC", t = "ABC"
    4. 输出："BANC"
    5. 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
    6. 示例 2：
    7.  
    8. 输入：s = "a", t = "a"
    9. 输出："a"
    10. 解释：整个字符串 s 是最小覆盖子串。
    11. 示例 3:
    12.  
    13. 输入: s = "a", t = "aa"
    14. 输出: ""
    15. 解释: t 中两个字符 'a' 均应包含在 s 的子串中，
    16. 因此没有符合条件的子字符串，返回空字符串。

     其实这个题目，和上述所说的两个题目是类似的，只不过在判断条件当中，上两个题目是 当 窗口不合法，然后出窗口，但是这个题目是 窗口合法，就更新结果，然后出窗口。

    同样的，使用 left 和 right 两个指针，从开始来进行遍历，用两个 hash 表分别存储 s 和 t 两个字符串当中 各个 字符的数量。

    right 依次向后走，把遍历的 每一个 s 当中的字符，记录在 自己 hash 表当中，也就是 hash 表当中计数器++。（进窗口）

    当 right 向后迭代，窗口合法，就更新结果，然后 循环 left++，向后迭代，同样的，left 遍历的过的字符 来 出窗口，在 hash 的计数器--。一直left++ 到 窗口不合法。

    判断两个 s 相对于 t 当中的在  t 当中在 s 当中存在的字符 的个数，要大于等于 t 当中对应字符的 数量，才称之为 s 当中的这个字符是 有效字符。

    当有效字符 等于 t 当中字符种类数量，才认为 当前窗口合法。

    判断 两个 hash 表 是否相等，可以使用上述 有效字符 的方式进行优化，具体就是：

    我们可以用一个 count 记录 有效字符。什么是 有效字符呢？就是在我们所寻找的子串当中，有多少 种类 的字符，是和 目标字符是 一样的。如果有一个 种类 是一样的，count++。

    所以，在 存储我们找出的子串当中 各个字符出现次数 的 hash 表当中，依旧按照 滑动窗口 当中的逻辑，进行 计数，只不过，如果是  和 目标字符 hash 当中有重复的，也就是当前的 计数器++ 的是 有效字符，那么就 count++。

    当 count == 目标子串.size() 之时，采取更新结果，否则，当前找出的 这个子串 就不满足条件。
     

    完整代码：

    1. class Solution {
    2. public:
    3.     string minWindow(string s, string t) {
    4.         char hash_s[128] = {0}; // 用于存储 s 字符串当中 各个字符出现的次数
    5.         char hash_t[128] = {0}; // 用于存储 t 字符串当中 各个字符出现的次数
    6.  
    7.     //记录t字符种类数量 当前最小长度       当前最小程度的子串在 s 当中的起始位置
    8.         int kinds = 0, minlen = INT_MAX, begin = -1;
    9.         for(auto& e : t) if(hash_t[e]++ == 0) kinds++;
    10.  
    11.         for(int left = 0, right = 0, count = 0; right < s.size();right++)
    12.         {
    13.             char right_str = s[right]; // 取出当前 right 指向的字符
    14.             hash_s[right_str]++;       // 哈希表计数器++
    15.             if(hash_s[right_str] == hash_t[right_str]) count++; // 如果在上述计数器++之后
    16.                                                                 // 满足条件，count++
    17.             // 如果当前 s 当中的有效字符 和 t 当中的 字符种类相等
    18.             // 说明当前窗口 合法
    19.             // 更新结果，循环一直 left++, 直到 窗口不再合法
    20.             while(count == kinds)
    21.             {
    22.                 if(right - left + 1 < minlen)
    23.                 {
    24.                     minlen = right - left + 1;
    25.                     begin = left;
    26.                 }
    27.                 
    28.                 char left_str = s[left++];// 取出当前 left 指向的字符，然后 left++
    29.                 if(hash_s[left_str] == hash_t[left_str]) count--; //如果left指向字符出窗口之后
    30.                                                                   // 当前字符个数不在和t相比是
    31.                                                                   // 大于等于 t 对应字符数量
    32.                 hash_s[left_str]--;
    33.             }
    34.         }
    35.  
    36.         if(begin == -1) return "";
    37.         else return s.substr(begin, minlen); // 如果有结果，就切割字符串，然后返回
    38.     }
    39. };

    I69. x 的平方根 - 力扣（LeetCode）

    给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

    由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

    注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

    1. 示例 1：
    2.  
    3. 输入：x = 4
    4. 输出：2
    5. 示例 2：
    6.  
    7. 输入：x = 8
    8. 输出：2
    9. 解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

     完整代码：
     

    1. class Solution {
    2. public:
    3.     int mySqrt(int x) {
    4.         if(x < 1) return 0; // 处理边界情况
    5.  
    6.         int left = 1, right = x;
    7.         while(left < right)
    8.         {
    9.             // 找到 left 和 right 的中间数值
    10.             long long mid = left +  (right - left + 1) / 2; //  long long防止 mid * mid 溢出
    11.             if(mid * mid <= x) left = mid;  // 刷新 左右区间
    12.             else right = mid -1;
    13.         }
    14.         return left;
    15.  
    16.     }
    17. };

    I【模板】前缀和_牛客题霸_牛客网 (nowcoder.com)

    描述

    给你一个 n 行 m 列的矩阵 A ，下标从1开始。

    接下来有 q 次查询，每次查询输入 4 个参数 x1 , y1 , x2 , y2

    请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和，

    输入描述：

    第一行包含三个整数n,m,q.

    接下来n行，每行m个整数，代表矩阵的元素

    接下来q行，每行4个整数x1, y1, x2, y2，分别代表这次查询的参数

     

    输出描述：

    输出q行，每行表示查询结果。

    1. 示例1
    2. 输入：
    3. 3 4 3
    4. 1 2 3 4
    5. 3 2 1 0
    6. 1 5 7 8
    7. 1 1 2 2
    8. 1 1 3 3
    9. 1 2 3 4
    10. 复制
    11. 输出：
    12. 8
    13. 25
    14. 32

    使用前缀和 -> 快速求出数组当中某一个连续区间的和。

    先要预处理出来一个前缀和数组（dp数组），dp[i] 元素存储的是 原数组当中，从起始位置，到 i 位置 这个连续区间当中 元素之和。

    所以，在以后 寻找的过程当中，只需要以 下标对应 dp 当中存储的和，相减即可。比如 ：给定区间 [1, 3] ，那么这个区间当中的和就等于 dp[3] - dp[1]。

    完整代码：

    1. #include 
    2. #include
    3. using namespace std;
    4.  
    5. int main() {
    6.     int n,q;
    7.     cin >> n >> q;
    8.     vector<int> arr(n + 1);
    9.     vector<long long> dp(n + 1, 0); // long long 防止溢出
    10.  
    11.     for(int i = 1;i <= n;i++) cin >> arr[i];
    12.     for(int i = 1;i <= n;i++) dp[i] = dp[i - 1] + arr[i];
    13.  
    14.     int l , r;
    15.     while(q--)
    16.     {
    17.         cin >> l >> r;
    18.         cout << dp[r] - dp[l - 1] << endl;
    19.     }
    20.  
    21.     return 0;
    22. }

    I【模板】二维前缀和_牛客题霸_牛客网 (nowcoder.com)

    描述

    给你一个 n 行 m 列的矩阵 A ，下标从1开始。

    接下来有 q 次查询，每次查询输入 4 个参数 x1 , y1 , x2 , y2

    请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和，

    输入描述：

    第一行包含三个整数n,m,q.

    接下来n行，每行m个整数，代表矩阵的元素

    接下来q行，每行4个整数x1, y1, x2, y2，分别代表这次查询的参数

    输出描述：

    输出q行，每行表示查询结果。

    1. 示例1
    2. 输入：
    3. 3 4 3
    4. 1 2 3 4
    5. 3 2 1 0
    6. 1 5 7 8
    7. 1 1 2 2
    8. 1 1 3 3
    9. 1 2 3 4
    10. 复制
    11. 输出：
    12. 8
    13. 25
    14. 32

    和上述一样，使用 前缀和 来解决上述的问题。

    dp[i][j] 表示，从 [1,1] 位置到 [i，j] 位置，这段区间当中所有的元素的和。

    但是，dp 这个二维数组不好求，如果我们直接遍历来一个一个求的话，时间复杂度很高。

    所以，其实 dp[i][j] 其实就是 A + B + C + D，这四个之和。单独求 A 其实很好求，找到 i -1 和 j -1 ，位置，就可以求出 dp[i-1][j-1] 就是 A 的面积。

    因为单独求 C 和 B 不好求。

     A + B + C + D = (A + B) + (A + C) + D - A

     上述 (A + B) 和 (A + C) 就可以求出。

     所以 ： dp[ i ][ j ] = dp[ i-1 ][ j ] + dp[ i ][ j-1 ] + arr[ i ][ j ] +dp[ i-1 ][ j-1 ]  

    所以：

    完整代码：

    1. #include 
    2. #include
    3. using namespace std;
    4.  
    5. int main() {
    6.     int n = 0, m = 0, q = 0;
    7.     cin >> n >> m >> q;
    8.     vectorint>> arr(n + 1, vector<int>(m + 1));
    9.     for(int i = 1; i <= n; i++)
    10.         for(int j = 1; i <= m ;j++)
    11.             cin >> arr[i][j];
    12.  
    13.     vectorlong long>> dp(n + 1, vector<long long>(m + 1));
    14.     for(int i = 1; i <= n; i++)
    15.         for(int j = 1; i <= m ;j++)
    16.             dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
    17.  
    18.     int x1 , y1 , x2 , y2;
    19.     while(q--)
    20.     {
    21.         cin >> x1 >> y1 >> x2 >> y2;
    22.         cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
    23.     }
    24.  
    25.     return 0;
    26. }

  • 相关阅读:
    OptiFDTD应用：纳米盘型谐振腔等离子体波导滤波器
    QT登录功能实现
    零基础自学SQL课程 | 相关子查询
    强化自主可控，润开鸿发布基于RISC-V架构的开源鸿蒙终端新品
    Kotlin变量与控制条件的基本用法
    难道企业真的需要私有区块链吗？
    对负采样（negative sampling）的一些理解
    C++模板与STL（六）：内存空间配置器及内存池技术模拟
    [python 刷题] 981 Time Based Key-Value Store
    C语言工程调用C++库解决方案
  • 原文地址：https://blog.csdn.net/chihiro1122/article/details/134420061