查找2

ryluo 2020-08-24 09:55:46

两数之和(1)

image-20200826154509433

题目分析:

使用哈希表存储每个值对应的索引,查找的时候只需要查找target-nums[i]是否存在,若存在直接返回这两个数对应的下标即可。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> mp;
        for(int i = 0; i < nums.size(); i++){
            if(mp.count(target - nums[i])) return {mp[target - nums[i]], i};
            else mp[nums[i]] = i;
        }
        return {};
    }
};


三数之和(15)

image-20200826154833797

题目分析:

本题需要求解三个数的和等于某个数,返回这三个数。与两数之和看起来类似,但是却有很大的区别。两数之和返回的是满足条件的两个数的下标,并且最终返回的答案只有一种。但是对于三数之和,最终返回的结果可能有多个答案,并且还不能有重复的答案,所以这里在计算结果的时候,需要注意,如何使得最终的结果不会重复。

要使结果不重复其实很简单的一个操作就是提前给数组排好序,然后相同的数直接跳过,具体的算法流程如下:

  1. 使用第一层循环无重复的枚举第一个数字,然后接下来采用两头往里寻找的方式无重复的构造剩下的两个数,具体循环中:
    • 初始化l=i+1, r=n-1
    • 当l<r时,如果当前的nums[l] + nums[r] + nums[i] == 0,则将此时的这三个数作为一个解,同时将l和r都去除重复元素;否则根据nums[l] + nums[r] + nums[i]的取值判断移动l或者r
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());

        for(int i = 0; i < nums.size(); i++){
            while(i > 0 && i < nums.size() && nums[i] == nums[i-1]) i++;
            int l = i + 1, r = nums.size() - 1;

            while(l < r){
                if(nums[i] + nums[l] + nums[r] == 0){
                    ans.push_back({nums[i], nums[l], nums[r]});
                    do  l++;  while(l < r && nums[l] == nums[l - 1]);
                    do  r--;  while(l < r && nums[r] == nums[r + 1]); 
                }
                else if(nums[i] + nums[l] + nums[r] > 0){
                    do  r--;  while(l < r && nums[r] == nums[r + 1]);
                }else{
                    do  l++;  while(l < r && nums[l] == nums[l - 1]); 
                }
            }
        }
        return ans;
    }
};


四数之和(18)

image-20200826223857386

题目分析:

题目和三数之和基本上是一样的,只不过多一层循环以及多一层判重。

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        int len = nums.size();

        for(int i = 0; i < len; i++){
            while(i != 0 && i < len && nums[i] == nums[i - 1]) i ++;
            for(int j =  i + 1; j < len; j++){
                while(j != i + 1 && j < len && nums[j] == nums[j - 1]) j ++;

                int l = j + 1, r = len - 1;
                while(l < r){
                    int sum = nums[i] + nums[j] + nums[l] + nums[r];
                    if(sum == target){
                        ans.push_back({nums[i], nums[j], nums[l], nums[r]});
                        do l++; while(l < r && nums[l] == nums[l - 1]);
                        do r--; while(l < r && nums[r] == nums[r + 1]);
                    }else if(sum > target){
                        do r--; while(l < r && nums[r] == nums[r + 1]);
                    }else{
                        do l++; while(l < r && nums[l] == nums[l - 1]);
                    }
                }
            }
        }
        return ans;
    }
};


最接近的三个数之和(16)

image-20200826232407611

题目分析:

该题思路和三数之和的思路很类似,但是需要衡量当前三个数与之前三个数的和是否更加的接近了。注意,这里需要加绝对值。

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int ans = nums[0] + nums[1] + nums[2];
        int len = nums.size();

        for(int i = 0; i < len; i++){
            while(i != 0 && i < len && nums[i] == nums[i - 1]) i++;

            int l = i + 1, r = len - 1;
            while(l < r){
                if(abs(nums[i] + nums[l] + nums[r] - target) < abs( ans - target))
                    ans = nums[i] + nums[l] + nums[r];
                if(nums[i] + nums[l] + nums[r] == target) return target;
                else if(nums[i] + nums[l] + nums[r] > target) r--;
                else l ++;
            }
        }
        return ans;
    }
};


四数相加II(454)

image-20200826232617239

题目分析:

  1. 使用四层循环,依次对每个数组进行枚举,时间复杂度为$O(n^4)$
  2. 也可以使用三层循环再加上一个哈希表记录前三层循环中三个数的和,在遍历第四个数组的时候,查询$-D[i]$是否在哈希表中,复杂度为$O(n^3)$
  3. 使用两层循环加上一个哈希表,前两层循环记录两个数之和的所有可能情况,及不同和的次数,再遍历剩下的两个数组,在哈希表中查询$-C[i]-D[j]$是否存在,复杂度为$O(n^2)$
class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int, int> mp;
        int ans = 0;
        for(int i = 0; i < A.size(); i++)
            for(int j = 0; j < B.size(); j++)
                mp[A[i] + B[j]] ++;

        for(int i = 0; i < C.size(); i++)
            for(int j = 0; j < D.size(); j++)
                if(mp.count(-(C[i] + D[j]))) ans += mp[-(C[i] + D[j])];

        return ans; 
    }
};


字母异位次分组(49)

image-20200827122847907

题目分析:

本题需要含有相同字符的字符串放到一组,其实只需要对字符串进行排序,那么排序完的字符串就是相等的,然后将这些排序完的字符串作为key,其对应的原始字符就是这个key下面所有满足条件的结果,对于这些结果可以使用一个vector来存储。

下面代码中使用move是为了节省内存,直接将字符串的地址传过去,不需要额外的对字符串进行拷贝。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        vector<vector<string>> ans;
        for(int i = 0; i < strs.size(); i++){
            string k = strs[i];
            sort(k.begin(), k.end());
            mp[k].push_back(move(strs[i]));
        }

        for(auto &it: mp)
            ans.push_back(move(it.second));
        return ans;
    }
};


回镖的数量(447)

image-20200827192828909

题目分析:

选定一个点,计算其他所有点到该点的距离,然后将其他点按照距离进行分组,距离相同的点放到同一组。然后统计每组相同点构成回旋镖的数量,例如与选定点距离为d的点的个数为n,那么以改点为中间点能够构成的回旋镖的数量为$n*(n-1)$,因为在这一组具有相同距离的点中,以其中任意两个为三元组的起始位置和终止位置,选定点为中间点的这样的三元组就可以构成回旋镖,所以问题相当于在每一组距离相同的点中没有顺序的取两个数,第一个数取的种数为n第二个数选的种数为n-1.

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int ans = 0;
        for(int i = 0; i < points.size(); i++){
            unordered_map<int, int> mp;

            for(int j = 0; j < points.size(); j++){
                if(i == j) continue;
                int dx = points[j][0] - points[i][0];
                int dy = points[j][1] - points[i][1];

                int dis = dx * dx + dy *dy;
                mp[dis] ++;
            }

            for(auto &it: mp)
                ans += it.second * (it.second - 1);
        }

        return ans;
    }
};


直线上最多的点(149)

image-20200827203302851

题目分析:

下图来自leetcode官方题解中的图。

image-20200827203507807

选定一个点,计算该点与其他所有点的斜率,将其他点按照斜率进行分组,因为一个定点加上斜率可以唯一确定一条直线,所以不同的斜率分组中点的数量就是一条直线上点的数量,所有组中值最大的就是最终的答案。需要注意以下三点:

  1. 竖直的直线不存在斜率,按照斜率计算公式计算会得到inf值,与定点计算斜率得到的inf的值,其实就是说明这些点是在同一条竖直直线上,也可以认为是一组结果
  2. 与选定的点相同的点,其实是可以分到任何组中的,需要单独记录,然后在计算最终结果的时候每个分组的值都加上相同点的数量。
  3. 当只有一个点的时候,那么结果就等于相同点的数量。

为了避免计算精度带来的问题,这里计算斜率使用的是long double。

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        if(points.empty()) return 0;
        int ans = 0;
        for(int i = 0; i < points.size(); i++){
            unordered_map<long double, int> mp;
            int same_point = 0;
            for(int j = 0; j < points.size(); j++){
                if(points[i][0] == points[j][0] && points[i][1] == points[j][1]) 
                    same_point++;
                else{
                    long double dx = points[j][0] - points[i][0];
                    long double dy = points[j][1] - points[i][1];
                    mp[dx / dy] ++; 
                }
            }

            for(auto &it: mp)
                ans = max(ans, it.second + same_point);

            ans = max(ans, same_point);
        }
        return ans;
    }
};