单页网站编辑器,微信商户平台入口,长沙做网站zwnet,网站建设都包括哪些内容文章目录 1. 两数之和49. 字母异位词分组128. 最长连续序列283. 移动零11. 盛最多水的容器15. 三数之和42. 接雨水 题单链接#xff1a; LeetCode 热题 100
1. 两数之和
leetcode题目链接 题解1#xff1a;暴力枚举 时间复杂度#xff1a; O ( n 2 ) O(n^2) O(n2)
class … 文章目录 1. 两数之和49. 字母异位词分组128. 最长连续序列283. 移动零11. 盛最多水的容器15. 三数之和42. 接雨水 题单链接 LeetCode 热题 100
1. 两数之和
leetcode题目链接 题解1暴力枚举 时间复杂度 O ( n 2 ) O(n^2) O(n2)
class Solution {
public:vectorint twoSum(vectorint nums, int target) {vectorint v;for (int i 0; i nums.size() - 1; i ) {for (int j i 1; j nums.size(); j ) {if (nums[i] nums[j] target) {v.push_back(i), v.push_back(j);}}}return v;}
};题解2哈希表 时间复杂度 O ( n ) O(n) O(n)
使用hash表来存target - x的差值的下标。这里使用cpp里面的unordered_map它的查找效率为 O ( 1 ) O(1) O(1)
补充unordered_map 查找key的方法count() 如果存在某个key, 返回1如果不存在某个key返回0.
class Solution {
public:vectorint twoSum(vectorint nums, int target) {unordered_mapint, int heap; // heap存 差值 下标for (int i 0; i nums.size(); i ) {int r target - nums[i];if (heap.count(r)) { // count方法判断key存不存在return {heap[r], i};}heap[nums[i]] i; // 记录这个数的下标}return {};}
};49. 字母异位词分组
leetcode题目链接
题解 字母异位词的意思是某些字符串含有相同的字母并且每个字母出现的次数相同。字母异位词也可以理解为字符串排完序之后完全相同。
本题解利用后者排序进行处理如果两个字符串是字母异位词那么它们排完序之后一定相同。可以使用哈希表来维护一个string的vector记录排完序相同的字符串。时间瓶颈是在排序上排序的复杂度是 n l o g n nlogn nlogn。 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {unordered_mapstring, vectorstring hash;for(auto str: strs) {string nstr str; // nstr为排序过后的新字符串sort(nstr.begin(), nstr.end());hash[nstr].push_back(str);}vectorvectorstring res;for(auto item: hash) {res.push_back(item.second);}return res;}
};128. 最长连续序列
leetcode题目链接
题解哈希表 我们每次从一个序列的最小值开始枚举如果是连续的迭代器不停。比如最小值是x那么其后是x1, x2, …, y那么该连续序列的长度是多少呢是y - x 1 这么长。为了加快查找速度我们将所有元素存入哈希表unordered_set S中。还有一个问题如何确定一个序列的开始呢 如果哈希表S中存在x不存在x - 1那么我们就说x是一个序列的开始。
补充 unordered_set这个hash表会将元素去重并且不会排序可以通过元素的值快速检索出该元素。 时间复杂度 O ( n ) O(n) O(n)
class Solution {
public:int longestConsecutive(vectorint nums) {unordered_setint S;// 构造hash表将所有元素插入到set中for(auto x: nums) S.insert(x);int res 0;for(auto x : S) {// 枚举序列的最小值xif(S.count(x) !S.count(x - 1)) {int y x;// 如果是连续的序列y一直while(S.count(y 1)) {y ;}res max(res, y - x 1); // 更新序列长度}}return res;}
};283. 移动零
leetcode题目链接 题解双指针
前一个指针x从头开始遍历数组后一个指针k保存非零元素k从零开始逐渐加1。当所有的非零元素都移动到前面之后此时k指向第一个零的位置从此往后枚举补零即可。
时间复杂度 O ( n ) O(n) O(n)
class Solution {
public:void moveZeroes(vectorint nums) {int k 0; // k是后一个指针用于存放非零的数for (auto x : nums) {if (x) {nums[k] x;k ;}}// 把数组后面的位置补零while (k nums.size()) {nums[k] 0;k ;}}
};11. 盛最多水的容器
leetcode题目链接 题解双指针 两个指针i 和 j形成的水槽的面积由短板决定面积计算公式如下: S m i n ( h [ i ] , h [ j ] ) ∗ ( j − i ) S min(h[i], h[j]) * (j - i) Smin(h[i],h[j])∗(j−i)
每个状态下两个指针i和j向中间移动一格都会使得底边变短怎样才能使得面积变大呢 只有每次把短板向中间靠拢它向中间靠拢才可能使矩形的高变高面积才能变大。因为下一个状态的高度可能比短板高。移动的过程中每次记录下来面积的最大值。参考 leetcode题解
时间复杂度 O ( n ) O(n) O(n)
class Solution {
public:int maxArea(vectorint height) {int res 0;for (int i 0, j height.size() - 1; i j;) {res max(res, min(height[i], height[j]) * (j - i));// 每次短边向中间移动if (height[i] height[j]) i ;else j --;}return res;}
};15. 三数之和
leetcode题目链接
题解排序 双指针
对数组从小到大排序。开始遍历数组第一个下标 i i i 表示三个数中的第一个我们固定这个数然后使用双指针算法(枚举 j 和 k j和k j和k)找到另外两个数使得 n u m s [ i ] n u m s [ j ] n u m s [ k ] ≥ 0 , i j k nums[i] nums[j] nums[k] \ge 0, i j k nums[i]nums[j]nums[k]≥0,ijk,同时使得k尽可能的小k是最后一个指针指向三数中的最大值从右往左移动。在上述情况中找到三数之和等于0的情况。
另外需要确保没有枚举出来重复的情况比如 n u m s [ − 1 , − 1 , − 1 , − 1 , 2 ] nums [-1, -1, -1, -1, 2] nums[−1,−1,−1,−1,2]怎样才能做到只出现一次 [ − 1 , − 1 , 2 ] [-1, -1, 2] [−1,−1,2]在枚举的时候如果出现 n u m s [ i ] n u m s [ i − 1 ] nums[i] nums[i-1] nums[i]nums[i−1]我们就跳过直接 i i i, 直到 n u m s [ i ] ≠ n u m s [ i − 1 ] nums[i] \ne nums[i-1] nums[i]nums[i−1]。 n u m s [ j ] nums[j] nums[j]同理。
时间复杂度 O ( n 2 ) O(n^2) O(n2)排序是 O ( n l o g n ) , O(nlogn), O(nlogn), 外层循环 i i i是 O ( n ) O(n) O(n), 内层双指针循环 j 和 k j 和 k j和k 是 O ( n ) O(n) O(n)相乘是 O ( n 2 ) O(n^2) O(n2)。
参考题解acwing题解
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint res;if (nums.size() 3) return res;sort(nums.begin(), nums.end());for (int i 0; i nums.size(); i ) {if (i 0 nums[i] nums[i - 1]) continue;// 双指针j是头指针k是尾指针两者向中间靠拢for (int j i 1, k nums.size() - 1; j k; j ) {if (j i 1 nums[j] nums[j - 1]) continue;// 找到3数之和 ≥ 0 的最小的位置 k是3数之和≥0的最前面的位置while (j k - 1 nums[i] nums[j] nums[k - 1] 0) k --;if (nums[i] nums[j] nums[k] 0)res.push_back({nums[i], nums[j], nums[k]});}}return res;}
};42. 接雨水
leetcode题目链接
题解双指针计算总面积 - 陆地面积。计算总面积时是每行的面积进行累加。 数组求和使用cpp中的accumulate函数。 参考题解接雨水
class Solution {
public:int trap(vectorint height) {int length height.size();if (length 3) return 0;int l 0, r length - 1;// 前一次计算时的高度int preHeight 0;// 陆地 雨水的总面积int totalArea 0;// 陆地面积数组所有数求和int landArea 0;// accumulate 是cpp累加函数landArea accumulate(height.begin(), height.end(), 0);while (l r) {while (l r height[l] preHeight) l ;while(l r height[r] preHeight) r --;// 每一层的面积高度差 x 宽度totalArea (min(height[l], height[r]) - preHeight) * (r - l 1);preHeight min(height[l], height[r]);}return totalArea - landArea;}
};
