Leetcode刷题笔记5
76. 最小覆盖子串
76. 最小覆盖子串 - 力扣（LeetCode）
解法一： 暴力枚举 + 哈希表
先定义left和right，可以在随机位置
枚举一个位置向后找，找到一个位置之后，发现这段区间是一个最小的区间之后，让left移动一格
然后right继续从left开始向后找
输入：s = "ADOBECODEBANC", t = "ABC"
hash1:
在t中A出现1次，B出现1次，C出现1次
hash2：
在s中，记录ABC出现几次
只要在hash2中，字符统计出现的次数大于等于hash1，那么就是一个有效的枚举
优化：
符合要求
s = "-----------------------------"
[L R]
当left向左移动一步时，会有两种情况
1：依旧符合要求
right不动
2：不符合要求
right向右移动，找符合要求的位置
两个指针是同向运动的，所以单调性，所以可以使用滑动窗口
解法二：滑动窗口 + 哈希表
s = "A D O B E C O D E B A N C", t = "ABC"
L
R
1. left = 0, right = 0
2. 进窗口 -> hash2[in]++
3. 判断，当窗口刚好合法时出窗口 -> check(hash1, hash2)
更新结果 -> 起始位置、最终的最短长度
出窗口 -> hash2(out)--
判断成立先更新结果，再出窗口然后继续判断
优化：判断条件
使用变量count标记有效字符的“种类”
1. 进窗口 -> 进之后，当hash2(in) == hash1(in), count++
只要hash2里面A的个数与hash1里面A的个数相等时统计
2. 出窗口 -> 出之前，当hash2(out) == hash1(out), count--
比如出窗口后，hash2里面A的个数从1变成了0，然后hash1里面A为1，成为了无效字符，那么count--
3. 判断条件 -> count == hash1.szie()
代码：C++
class Solution {
public:string minWindow(string s, string t) {// 数组模拟哈希表，因为全是英文字符int hash1[128] = {0}; // 统计字符串t中每个字符的频次int hash2[128] = {0}; // 统计窗口内每个字符的频次int kinds = 0; // 统计有效字符有多少种for(auto ch : t) {// if(hash[ch] == 0) kinds++;// hash[ch]++;// 同上if(hash1[ch]++ == 0) kinds++; // 加之前如果等于0，说明找到一个有效字符，所以kinds++}int minlen = INT_MAX, begin = -1; // minlen是最小覆盖子串长度，begin存的是起始位置for(int left=0, right=0, count=0; right<s.size(); right++){char in = s[right];// hash2[in]++;// if(hash2[in] == hash1[in])// {// count++;// }// 同上if(++hash2[in] == hash1[in]) count++; // 进窗口+维护count变量while(count == kinds) // 判断条件{// 只要窗口长度小于minlenif(right - left + 1 < minlen) // 更新结果{minlen = right - left + 1;begin = left;}// 出窗口char out = s[left++];// if(hash2[out] == hash1[out]) count--;// hash2[out]--;// 同上if(hash2[out]-- == hash1[out]) count--; // 说明此时有效字符的种类要减少}}if(begin == -1) return ""; // 如果等于-1说明没有找到一个子串，返回空串else return s.substr(begin, minlen); // 找到了就把它裁出来}
};704. 二分查找
704. 二分查找 - 力扣（LeetCode）
原理：
[1, 2, 3, 4, 5, 6, 7, 8], t = 5
解法一：暴力解法 -> O(N)
从左往右依次用t跟数组的元素对比
比如选择4，那么在升序数组中，4和4左边区间的元素肯定比5小
解法二：二分查找算法“二段性”
当数组有二段性的时候就可以用二分查找算法
二段性：
当我们发现一个规律，然后根据这个规律选取某一个点后，能把这个数组分成两部分
然后根据规律可以有选择性的舍去一部分，然后根据这个规律在另一个部分里面继续查找的时候就可以用二分查找
选择中间点，时间复杂度最优
M
[ x ], t
L R
L = left, R = right, M = mid
朴素版本二分查找算法的核心：
第一种情况：x < t，删除左区间 -> left = mid + 1 -> 然后再在更新之后的[left, right]区间寻找结果
第二种情况：x > t，删除右区间 -> right = mid - 1 -> 然后再在更新之后的[left, right]区间寻找结果
第三种情况：x = t，直接返回结果
细节问题：
1. 循环结束的条件 -> left > right
2. 为什么是正确的
3. 时间复杂度
循环1次：
2次：
3次：
...
x次：1 -> ->
= n -> x = logN
代码实现：C++
class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while(left <= right){// int mid = (left + right) / 2; // 有溢出风险int mid = left + (right - left)/2; // 防止溢出if(nums[mid] < target) left = mid + 1;else if(nums[mid] > target) right = mid - 1;else return mid;}return -1;}
};二分查找的朴素版本模版：
// 朴素二分模版
// int left = 0, right = nums.size() - 1;while (left <= right){int mid = left + (right - left) / 2; if (......) left = mid + 1;else if (......) right = mid - 1;else return ......;}JZ64 求1+2+3+...+n
求1+2+3+...+n_牛客题霸_牛客网 (nowcoder.com)
由于题目限制了常规的控制语句和条件判断，不能使用典型的循环或递归方法，我们需要找到一种绕开这些限制的方法来实现累加。
可以先定义一个类，在其构造函数中实现累加操作。
构造函数Sum()：每次创建Sum类的对象时，构造函数会执行一次，将当前的i值加到sum中，并将i自增1
int i = 1; // 初始化一个全局变量 i，初始值为 1，从1开始累加
int sum = 0; class Sum {
public:Sum() {sum += i; // 在构造函数中，将当前的 i 值加到 sum 上++i; // 将 i 自增 1}
};
在主函数里面调用这个函数
class Solution {
public:int Sum_Solution(int n) {Sum a[n]; // 创建一个 Sum 类的对象数组 a，大小为 nreturn sum; // 返回全局变量 sum 的值}
};
每次创建Sum类的对象时，构造函数会自动执行累加操作。通过创建一个包含n个对象的数组，可以自动调用构造函数n次。
在C++中，创建一个类对象数组会自动调用数组中每个对象的构造函数。通过创建一个包含n个对象的数组，可以确保构造函数被调用n次，从而完成累加。