算法练习二

发表于 | 分类于
  1. 无重复字符的最长子串

给定一个字符串，找出不含有重复字符的最长子串的长度。
示例：
给定 “abcabcbb” ，没有重复字符的最长子串是 “abc” ，那么长度就是3。
给定 “bbbbb” ，最长的子串就是 “b” ，长度是1。
给定 “pwwkew” ，最长子串是 “wke” ，长度是3。请注意答案必须是一个子串，”pwke” 是 子序列 而不是子串。

分析思路：

  1. 暴力法：取出所有的子串，校验没有重复的最大值，显然这种算法是有很多重复操作的。比如遍历abc的时候已经知道abc没有重复，后面没必要再进行这段的比对。
  2. 使用滑动窗口，初始窗口左值为0，右值为1，右值开始遍历字符串每个字符的同时，存入hash表，如果hash表中已经有了改字符的索引，那么久移动窗口的左值为该位置的下一个位置，继续滑动窗口，直到遍历完字符串，思路并不算复杂。时间复杂度和空间复杂度都是O(n)

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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;
    }
};
  1. 两个排序数组的中位数

给定两个大小为 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))

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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;
    }
};