深圳微网站,网站高端设计公司,网页设计欣赏英文翻译,公众号开发主要做什么无重复的最长字串
题目描述
给定一个字符串#xff0c;请你找出其中不含有重复字符的 最长子串 的长度。
解题思路
看到这道题#xff0c;其实就两个步骤#xff0c;遍历字符串#xff0c;记录当前字符有没有重复。 重复一般解决就是哈希#xff0c;这里用个数组表示…无重复的最长字串
题目描述
给定一个字符串请你找出其中不含有重复字符的 最长子串 的长度。
解题思路
看到这道题其实就两个步骤遍历字符串记录当前字符有没有重复。 重复一般解决就是哈希这里用个数组表示。 这里找最长的字串就是一个滑动窗口我们在这里用两个下标表示一个为左边界一个为右边界 初始值left 0right -1 滑动窗口的滑动就是右边界扩大左边界缩小 拿abcabcbb举例
先扩大右边界看有没有越界rights.size() 然后要看当前字符a在哈希表中有没有重复出现count[s[right1]] 0,如果没有那么count[s[right]]; 就是右边界可以扩大并且标记a已重复第一步完成后right 0left 0 重复上述步骤判断right1sizecount[s[right1]] 0,成功后b也没有重复那么右边界再往右扩一个第二步完成后right 1left 0,再重复上述步骤判断rihgt1sizecount[s[right1]] 0, c也没有重复右边界再往右扩一个第三部完成后right 2left 0再重复上述步骤判断right1sizecount[s[right1]] 0,此时又判断到了a那么count[s[left]] --,缩小左边界同时把哈希中的值更改。。。。。往后重复此操作每一步操作都要比较旧窗口大小和新窗口大小就是max(旧的新的)找出最大值
代码实现
class Solution {
public:int lengthOfLongestSubstring(string s) {int count[256] {0}; //哈希int right -1; //右边界int left 0;//左边界int res 0; //窗口大小while(lefts.size()){if(right1s.size()count[s[right1]] 0)count[s[right]] ;elsecount[s[left]]--;res max(res,right-left1);}return res;}
};有序数组中的中位数
题目描述
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数并且要求算法的时间复杂度为 O(log(m n))。
你可以假设 nums1 和 nums2 不会同时为空。 解题思路
所有的数据结构的中位数都可以用两个函数解决就是剑指offer中的数据流中的中位数 具体思路点这里
代码实现
class Solution {priority_queueint,vectorint,lessint max;priority_queueint,vectorint,greaterint min;
public:void Insert(int num){if(max.empty() || num max.top())max.push(num);elsemin.push(num);//保证两个堆的元素个数之差小于1if(max.size() min.size()2){min.push(max.top());max.pop();}if(max.size()1 min.size()){max.push(min.top()); min.pop();}}double GetMedian(){ return max.size() min.size() ? (max.top()min.top())/2.0 : max.top();}double findMedianSortedArrays(vectorint nums1, vectorint nums2) {for(int i 0; inums1.size();i){Insert(nums1[i]);}for(int i 0;inums2.size();i){Insert(nums2[i]);}double res GetMedian();return res;}
};
