1. 估算算法的时间复杂度的时候一般低于10^7 次操作每秒为佳
    sort 的时间复杂度与编译器具体实现相关，简单考虑成快速排序nlogn

哈希

1.两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：

  • 输入：nums = [2,7,11,15], target = 9
  • 输出：**[0,1]
  • 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

  • 输入：nums = [3,2,4], target = 6
  • 输出：**[1,2]

示例 3：

  • 输入：nums = [3,3], target = 6
  • 输出：[0,1]

提示：

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

**进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
//map[数，索引]，构建反向索引，便于查找
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        for(size_t i = 0 ; i < nums.size(); i++){
            if(map.contains(target-nums[i])){
                vector<int> ret;
                ret.push_back(map[target-nums[i]]);
                ret.push_back(i);
                return ret;
            }
            map[nums[i]] = i;
        }
        return vector<int>();
    }
};

2.字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
解释：
在 strs 中没有字符串可以通过重新排列来形成 “bat”。
字符串 “nat” 和 “tan” 是字母异位词，因为它们可以重新排列以形成彼此。
字符串 “ate” ，”eat” 和 “tea” 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2:
输入: strs = [“”]
输出: [[“”]]
示例 3:
输入: strs = [“a”]
输出: [[“a”]]

提示：
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    //排序s，原始序列相同的作为hash表的key
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> group_strs;
        for(auto& s : strs){
            string sorted_s  = s;
            ranges::sort(sorted_s);
            group_strs[sorted_s].push_back(s);
        }
        vector<vector<string>> ans;
        ans.reserve(group_strs.size());
        for(auto& [_,value] : group_strs){
            ans.push_back(value);
        }
        return ans;
    }
};

3.最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

示例 3：
输入：nums = [1,0,1,2]
输出：3

提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109

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
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        //排序+o(n)
        if(nums.size() < 2) return nums.size();
        sort(nums.begin(), nums.end());
        int ans = 1;
        int start = 0;
        int cur = 1;
        for(int i = 1; i < nums.size(); i++)
        {
            if(nums[i] == nums[i - 1])  continue;
            if(nums[i] - nums[i - 1] == 1)
            {
                cur++;
                ans = max(cur, ans);
            }
            else
            {
                start = i;
                cur = 1;
            }
        }
        return ans;
    }
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> num_set;
        for(const int & num : nums){
            num_set.insert(num);
        }
        //也是O(n)
        int longestStreak = 0;
        for(auto& num : num_set){
            if(!num_set.count(num - 1)){
                int currentNum = num;
                int currentStreak = 1;
                while( num_set.count(currentNum + 1)){
                    currentNum += 1;
                    currentStreak += 1;
                }
                longestStreak = max(longestStreak,currentStreak);
            }
        }
        return longestStreak;
    }
};

双指针

4.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:
输入: nums = [0]
输出: [0]

提示:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

进阶：你能尽量减少完成的操作次数吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        //快指针往前走，往慢指针搬数据，只搬非0值
        //o(n)
        int n = nums.size(),left = 0 , right = 0 ;
        while(right < n){
            if(nums[right]){
                swap(nums[left],nums[right]);
                left++;
            }
            right++;
        }
    }
};

5.盛水最多的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：
输入：height = [1,1]
输出：1

提示：
n == height.length
2 <= n <= 105
0 <= height[i] <= 104

题解：https://leetcode.cn/problems/container-with-most-water/solutions/207215/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/?envType=study-plan-v2&envId=top-100-liked
关键：
接水量=两个指针指向的数字中较小值∗指针之间的距离
双指针中靠时，后者减少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxArea(vector<int>& height) {
        int low = 0 , n = height.size(),high = n-1;
        int max_container = 0;
        while(low < high){
            int container = ( high - low ) * min(height[low],height[high]);
            max_container = max(max_container,container);
            if(height[low] < height[high]){
                low++;
            }else{
                high--;
            }
        }
        return max_container;
    }
};

6.三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：
3 <= nums.length <= 3000
-105 <= nums[i] <= 105

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
class Solution {
public:
    //注意不重复指三元组不重复，不是其中的元素不重复，所以每个位置都判断一次即可
    //但是对于第一个元素，如果采用for循环判断，000的情况要注意啊

    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(),nums.end());
        for(int i = 0 ; i < nums.size() - 2; i++ ){
            if(i > 0 && nums[i] == nums[i-1]){
                //核心点，不能使用nums[i] == nums[i+1];会缺失值；仔细对比两者的区别
                continue;
            }
            if(nums[i] > 0){
                break;
            }
            int l = i + 1 , r = nums.size()-1 ;
            while(l < r ){
                int sum = nums[l]+nums[r]+nums[i];
                if(sum < 0){
                    l++;
                }else if(sum > 0){
                    r--;
                }else{
                    ans.push_back({nums[i],nums[l],nums[r]});
                    while(l < r && nums[l] == nums[l+1]){
                        l++;
                    }
                    while(l < r && nums[r] == nums[r-1]){
                        r--;
                    }
                    l++;r--;
                }
            }
        }
        return ans;
    }
};

6.接雨水

定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

提示：
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

题解

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
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
public:
    int trap(vector<int>& height) {
        //dp
        int total_sum = 0;
        vector<int> dp_l_max;
        vector<int>  dp_r_max;
        dp_l_max.reserve(height.size());
        dp_r_max.reserve(height.size());
        dp_l_max[0] = 0;
        int n = height.size();
        dp_r_max[n-1] = 0;
        for(int i = 0 ; i < height.size() - 1 ; i++)
        {

            dp_l_max[i+1] = max(dp_l_max[i],height[i]);
            dp_r_max[n-i-2] = max(dp_r_max[n-1-i],height[n-i-1]);

        }
        for(int i = 0 ; i < height.size(); i++){
            int max_l = dp_l_max[i], max_r = dp_r_max[i];
            if(max_r > height[i] && max_l > height[i]){
                total_sum += min(max_r,max_l) - height[i];
            }            
        }
        return total_sum;
    }

    int trap(vector<int>& height) {
        //    单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 height 中的元素递减
        int ans = 0;
        stack<int> stk;
        int n = height.size();
        for (int i = 0; i < n; ++i) {
            while (!stk.empty() && height[i] > height[stk.top()]) {
                int top = stk.top();
                stk.pop();
                if (stk.empty()) {
                    break;
                }
                int left = stk.top();
                int currWidth = i - left - 1;
                int currHeight = min(height[left], height[i]) - height[top];
                ans += currWidth * currHeight;
            }
            stk.push(i);
        }
        return ans;
    }

    int trap(vector<int>& height) {
        //  双指针 存水量只取决于短的柱子 只只关心两者中的较小值，是不是所以没有遍历到的最大值不影响
       int n = height.size();
       if (n<=2)   return 0;
       int l=0,r=n-1;
       int leftmax=height[l], rightmax=height[r];
       int res=0;
       while (l<r) {
           if (leftmax < rightmax) {
               res += leftmax-height[l];
               l++;
               leftmax = max(height[l], leftmax);
           }
           else {
               res += rightmax-height[r];
               r--;
               rightmax = max(height[r], rightmax);
           }
       }
       return res;
   }

};

快来参与讨论吧~

本站由 Zane Jiang 使用 Stellar 1.33.1 主题创建，一款很棒的 Hexo 主题！

总访问 次 || 本页访问 次
总访客 人 || 本页访客 人