date: 2020/01/19

基本概念

image.png

image.png


242有效的字母异位词(简单)

https://leetcode-cn.com/problems/valid-anagram

计数即可,空间O(1)时间O(n)

bool isAnagram(string s, string t) {
    map<char, int> counter;

    for(int i = 0; i < s.size(); i++)
        counter[s[i]]++;
    for(int i = 0; i < t.size(); i++)
        counter[t[i]]--;

    for(map<char, int>::iterator it = counter.begin(); it != counter.end(); it++){
        if(it->second != 0)
            return false;
    }

    return true;
}


438找到字符串中所有字母异位词(中等)

https://leetcode-cn.com/problems/find-all-anagrams-in-a-string

242有效的字母异位词 的扩展

vector<int> findAnagrams(string s, string p) {
    vector<int> result;
    if(s.size() < p.size())
        return result;
    // 初始化哈希表
    unordered_map<char, int> t_map, p_map;
    for(int i = 0; i < p.size(); i++){
        t_map[s[i]]++;
        p_map[p[i]]++;
    }
    // 处理后续字符串
    for(int i = p.size(); i <= s.size(); i++){
        // 判断s[(i-p.size()):i]是否为p的异位词
        bool match = true;
        for(unordered_map<char, int>::iterator it = p_map.begin(); it != p_map.end(); it++){
            if(t_map[it->first] != it->second){
                match = false;
                break;
            }
        }
        if(match) 
            result.push_back(i - p.size());
        // 更新哈希表(最后一个循环溢出)
        if(i != s.size()){
            t_map[s[i - p.size()]]--;
            t_map[s[i]]++;
        }
    }
    return result;
}


049字母异位词分组(中等)

https://leetcode-cn.com/problems/group-anagrams

242有效的字母异位词 差不多,为了区别,这里只给出排序法的答案

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    vector<vector<string>> res;
    map<string, vector<string>> str_map;   // 用map作桶,收集排序后相等的字符串
    // 字符串排序,然后丢入桶中
    for(int i = 0; i < strs.size(); i++){
        string s = strs[i];
        sort(s.begin(), s.end());
        str_map[s].push_back(strs[i]);
    }
    // 整理输出结果
    for(map<string, vector<string>>::iterator it = str_map.begin(); 
        it != str_map.end(); it++){
        res.push_back(it->second);
    }
    return res;
}


001两数之和(简单)

https://leetcode-cn.com/problems/two-sum

vector<int> twoSum(vector<int>& nums, int target) {
    map<int, int> num_map;  // 数值 -> 索引
    map<int, int>::iterator it;
    vector<int> res;
    // 第一次遍历:构建哈希表
    for(int i = 0 ; i < nums.size(); i++)
        num_map[nums[i]] = i;
    // 第二次遍历
    for(int i = 0; i < nums.size(); i++){
        // 查找target - nums[i]
        it = num_map.find(target - nums[i]);
        // 如果存在,且不是相等的index
        if(it != num_map.end() && it->second != i){
            res = {i, it->second};
            return res;
        }
    }
    return res;
}


015三数之和(中等)

https://leetcode-cn.com/problems/3sum

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;
    // 极端情况
    if(nums.size() < 3)
        return result;
    // 从小到大排序,时间O(nlogn)
    sort(nums.begin(), nums.end());
    // 固定一个指针,转化为双指针搜索O(n^2)
    // 固定最左侧的指针k,双指针k+1和nums.size()-1,向中间靠拢
    // !!通过跳过重复值(指针之间独立),可以直接规避重复三元组的情况
    // !!当固定指针的数值大于0时可以提前退出——双指针都在固定指针右侧,即数值必定大于等于固定指针的数值
    for(int i = 0; nums[i] <= 0 && i < nums.size() - 2; i++){
        // 跳过数值重复的k指针
        if(i != 0 && nums[i-1] == nums[i])
            continue;
        // 双指针(移动左指针=>增大sum;移动右指针=>减小sum)
        int left = i + 1, right = nums.size() - 1;
        while(left < right){
            int sum = nums[i] + nums[left] + nums[right];
            if(sum == 0){
                vector<int> triple = {nums[i], nums[left], nums[right]};
                result.push_back(triple);
                // 移动左右指针,同时跳过重复数值的指针(注意防止指针越界)
                for(left++; left < right && nums[left-1] == nums[left]; left++);
                for(right--; left < right && nums[right+1] == nums[right]; right--);
            }else if(sum < 0){
                // 移动左指针,增大sum(这里即使不跳过重复数值的指针也可以得到正确答案)
                for(left++; left < right && nums[left-1] == nums[left]; left++);
            }else{
                // 移动右指针,减小sum(这里即使不跳过重复数值的指针也可以得到正确答案)
                for(right--; left < right && nums[right+1] == nums[right]; right--);
            }
        }
    }
    return result;
}


018四数之和(中等)

https://leetcode-cn.com/problems/4sum

没什么特殊的,在 15三数之和 的基础上行套个循环就行