Leetcode Hot100 Day1

有感于最近太摆了，加上各个群天天力扣，来一个Hot 100打卡挑战，预期每天5题，共20天完成。之前做过的也写写思路好了。

T1 1. 两数之和](https://leetcode.cn/problems/two-sum/)

题干

给定一个整数数组 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)O(n^2) 的算法吗？

思路：

力扣第一题，典中典。第一次做想到的是先排序再二分， O(nlogn)O(nlogn) ，不过看答案后其实可以用哈希来解决。

本质是在一堆数字中找到一个符合要求的数字，很容易想到对原本的数字进行一些预处理，这样可以 O(1)O(1) 地进行查询。考虑最简单的双层循环暴力，一层 nn 的开销在遍历，另一层 nn 的开销在查询。使用哈希预处理就是在查询这一步变成了 O(1)O(1) ，实现了优化。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        for(int i = 0; i < nums.size(); i++) {
            auto x = hash.find(target - nums[i]);
            if(x != hash.end()) {
                return {x -> second, i};
            } else {
                hash[nums[i]] = i;
            }
        }
        return {};
    }
};

T2 49. 字母异位词分组

题干

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

字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。

示例 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] 仅包含小写字母

思路

拥有同样字母的归为一类塞在哈希的一个值里面，关键是怎么处理索引呢？

没啥很好的思路，抄的灵神题解：对每一项先拷贝再 sort ，把 sort 结果当作索引，牛

看评论区有一个超级抽象的索引处理方法： a-z 与前 26 个质数建立映射，生成每个单词的 index ，显然对不同的单词互不相同，估计是最优解。不过还得考虑下单词长度和索引会不会溢出，估计不会卡这个。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hash;
        for(auto& x : strs) {
            string idx = x;
            ranges::sort(idx);
            hash[idx].push_back(x); 
        }
        vector<vector<string>> res;
        res.reserve(hash.size());
        for(auto& it : hash) {
            res.push_back(it.second);
        }
        return res;
    }
};

特别注意一下 res 需要用 reserve 方法预分配一下空间。第二个遍历也可以用 cpp 最新最热特性

1
2
3
for(auto& [_, v] : hash) {
	res.push_back(v);
}

T3 128. 最长连续序列

题干

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109

思路

自己做没想出来。首先不能排序（复杂度为 O(nlogn)O(nlogn) ），关键在于如何处理哈希。这里应该充分应用哈希集合 O(1)O(1) 任意查询的优点，即对每一个递增序列开头元素向后查询并更新。多说无益，show the codes.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> set(nums.begin(), nums.end());
        int res = 0;
        for (const auto& v : set) {
            if (!set.contains(v - 1)){
                int length = 1;
                int target = v + 1;
                while (set.contains(target)){
                    length++;
                    target++;
                }
                res = max(res, length);
            }
        }
        return res;
    }
};

T4 283. 移动零

题目

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

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

示例 2:

1
2
输入: nums = [0]
输出: [0]

提示:

  • 1 <= nums.length <= 104
  • -231 <= nums[i] <= 231 - 1

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

思路

尽可能减少操作次数必然产生原数组内的覆盖，有两种思路：记录 0 和 非0。如果记录 0 的位置脑子要转一下，不如直接记录 非0 的个数，即原地栈。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int ptr = 0;
        for(auto x : nums) {
            if(x) {
                nums[ptr++] = x;
            }
        }
        fill(nums.begin() + ptr, nums.end(), 0);
    }
};

T5 11. 盛最多水的容器

题目

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明：**你不能倾斜容器。

示例 1：

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

示例 2：

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

提示：

  • n == height.length
  • 2 <= n <= 105
  • 0 <= height[i] <= 104

思路

暴力 O(N2)O(N^2) 肯定不行。考虑结果是一个乘积：底 乘 高，不如固定一个变量的走向，使另一个变量反向走向，然后去找最大值。显然底的最大值容易获取——两端，然后双指针操作两个端点，操作端点使得 min(height)min(height) 升高，去找最大值， O(N)O(N) 复杂度。

代码

做这题正好和朋友聊起来了压行，不赖，就是可读性一坨。

1
2
3
4
5
6
7
8
class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size(), res = 0, i = 0, j = n - 1;
        while(i < j) {res = max(res, (j - i) * min(height[i], height[j])), height[i] < height[j] ? i++ : j--;}
        return res;
    }
};

这个挑战是8.6开始的，但是因为各种原因一直拖延到了8.6凌晨才完成 day1 挑战。得重新开始打卡了