- 无重复字符的最长子串
给定一个字符串，找出不含有重复字符的最长子串的长度。
示例：
给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。
给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列 而不是子串。
分析思路：
- 暴力法：取出所有的子串，校验没有重复的最大值，显然这种算法是有很多重复操作的。比如遍历abc的时候已经知道abc没有重复，后面没必要再进行这段的比对。
- 使用滑动窗口，初始窗口左值为0，右值为1，右值开始遍历字符串每个字符的同时，存入hash表，如果hash表中已经有了改字符的索引，那么久移动窗口的左值为该位置的下一个位置，继续滑动窗口，直到遍历完字符串，思路并不算复杂。时间复杂度和空间复杂度都是O(n)
代码如下:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (s.empty()) {
return 0;
}
int left = 0,right =1, string_length = s.size(),max_length = 0;
unordered_map<char, int> hashMap;
hashMap[s[left]] = left;
max_length = 1;
while (right < string_length) {
auto it = hashMap.find(s[right]);
if (it == hashMap.end()) {
//没有重复
hashMap[s[right]] = right;
}
else{
//有重复
//更改滑动窗口的左值为重复值的索引+1，先判断下重复值是不是再当前left的右边
left = max(left, it->second+1);
hashMap[s[right]] = right;
}
max_length = max(max_length,right -left+1);
right++;
}
return max_length;
}
};
- 两个排序数组的中位数
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。
示例 1:
nums1 = [1, 3]
nums2 = [2]
中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
中位数是 (2 + 3)/2 = 2.5
分析核心思路，中位数的数学定义就是该位置左边的数和右边的数数量一致。我们抽象s1数组存在位置i，s2的数组存在位置j，s1的数组i左边的数加上s2数组j左边的数正好是两个数组总长度的一半。这样i和j就存在数学关系i+j= （m+n）/2。我们同时假设n是大于等于m的。这样我们再s1数组中搜索位置i，j的位置根据数学关系也是对应的，采用二分法搜索合适i的位置保证时间复杂度要求到O(log (m+n))
代码如下
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(),n = nums2.size();
//先确保m<=n 如果不是先交换一次指针
if (m>n) {
// 因为是C++引用，这里交换一下使用两个临时变量
vector<int> tem1 = nums1;
vector<int> tem2 = nums2;
nums2 = tem1;
nums1 = tem2;
int tmpValue = m; m = n; n = tmpValue;
}
//先确定好i的值和中值
int iMin = 0,iMax = m,halfLen = (m+n+1)/2;
//开始遍历
while (iMin <= iMax) {
//给定中值
int i = (iMin + iMax) / 2;
int j = halfLen -i; //对应关系 因为i + j = (m+n+1)/2;
if (i < iMax && nums2[j-1]>nums1[i] ) {
//i的值太小了，要加大i区间
iMin = iMin+1;
}
else if (i > iMin && nums1[i-1] >nums2[j]){
//i的值太大了，减少i区间
iMax = iMax-1;
}
else{
//完美匹配
int maxLeft = 0;
//边界值判断
if (i == 0) {
maxLeft = nums2[j-1];
}
else if(j == 0){
maxLeft = nums1[i-1];
}
else{
maxLeft = max(nums1[i-1], nums2[j-1]);
}
//奇数直接return左边边界值
if ( (m + n) % 2 == 1 ) { return maxLeft; }
int minRight = 0;
if (i == m) {
minRight = nums2[j];
}
else if (j == n){
minRight = nums1[i];
}
else {
minRight = min(nums2[j], nums1[i]);
}
return (maxLeft + minRight) / 2.0;
}
}
return 0.0f;
}
};
