win7上能否做asp网站,模板网站建设教程视频教程,网站设计服务费做什么费用,推广系统建站76. 最小覆盖子串
76. 最小覆盖子串 - 力扣#xff08;LeetCode#xff09; 解法一#xff1a; 暴力枚举 哈希表
先定义left和right#xff0c;可以在随机位置 枚举一个位置向后找#xff0c;找到一个位置之后#xff0c;发现这段区间是一个最小的区间之后#xff0c…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 left0, right0, count0; rights.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(vectorint 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 求123...n
求123...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次从而完成累加。
