LeetCode 刷题【74. 搜索二维矩阵、75. 颜色分类、76. 最小覆盖子串】

74. 搜索二维矩阵

自己做

解：二分查找

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row = 0;                //标记target所在行

        while(row < (int)matrix.size() && matrix[row][0] <= target) //找到target所在行的下一行
            row++;
        
        row--;

        if(row < 0)                 //连首行都不可能存在target
            return false;

        //二分查找
        int begin = 0;
        int end = (int)matrix[0].size() - 1;
        
        while(begin <= end){
            int mid = (begin + end) / 2;

            if(matrix[row][mid] == target)
                return true;
            
            if(matrix[row][mid] > target)        //偏大，往左边找
                end = mid - 1;
                            
            if(matrix[row][mid] < target)        //偏小，往右边找
                begin = mid + 1;
        }

        return false;

    }
};

75. 颜色分类

自己做

解：计数法

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int a = 0;
        int b = 0;
        int c = 0;

        int i;
        //计数
        for(i = 0; i < (int)nums.size(); i++){
            if(nums[i] == 0)
                a++;
            if(nums[i] == 1)
                b++;
            if(nums[i] == 2)
                c++;
        }   
    
        //赋值
        i = 0;
        
        while(a > 0){
            nums[i] = 0;
            a--;
            i++;
        }
    
        while(b > 0){
            nums[i] = 1;
            b--;
            i++;
        }

        while(c > 0){
            nums[i] = 2;
            c--;
            i++;
        }        


    }
};

76. 最小覆盖子串

自己做

解：滑动窗口

class Solution {
public:
    string minWindow(string s, string t) {
        //字符串t的初始计数
        map<char, int> t_num;

        //插入键值
        for(int i = 0; i < (int)t.size(); i++)
            t_num.insert(make_pair(t[i], 0));

        //记录个数
        for(int i = 0; i < (int)t.size(); i++)
            t_num[t[i]]++;

        //最终确定的子串
        int begin = 0;
        int end = (int)s.size();

        //过程中的子串
        int left = 0;
        int right = 0;

        //起始跳过非子串部分
        while(right < (int)s.size() && t_num.find(s[left]) == t_num.end()){        //跳过非子串元素
            left++;
            right++;
        }

        while(right < (int)s.size()){
            if(t_num.find(s[right]) != t_num.end()){                                       //子串元素
                t_num[s[right]]--;

                //判断是否取得一个子串
                bool is = true;
                map<char, int>::iterator p = t_num.begin();
                for(int i = 0; i < (int)t_num.size(); i++){
                    if(p->second > 0){               //还有缺少的元素
                        is = false;
                        break;
                    }
                    p++;
                }
                
                if(is){             //如果取得了一个子串
                    //对该子串再压缩（有多余元素的情况下）
                    while(t_num[s[left]] < 0){
                        t_num[s[left]]++;                    //还原
                        left++;
                        while(left < (int)s.size() && t_num.find(s[left]) == t_num.end())        //跳过非子串元素
                            left++;

                        if(left == (int)s.size())           //越界返回
                            break;                        
                    }

                    if(right - left < end - begin){     //更短的子串
                        begin = left;
                        end = right;
                    }

                    //确定下一个子串起始
                    t_num[s[left]]++;                    //还原
                    
                    left++;
                
                    while(left < (int)s.size() && t_num.find(s[left]) == t_num.end())        //跳过非子串元素
                        left++;

                    if(left == (int)s.size())           //越界返回
                        break;
                }
            
            }
            right++;
        }

        if(end == (int)s.size())           //找不到一个子串
            return "";

        string res;
        for(int i = begin; i <= end; i++)
            res.push_back(s[i]);
        
        return res;
    }
};