网站建设实训该写哪些内容,青海省住房和城乡建设厅网站,高端网页游戏,百度一下电脑版网页哈希
128.最长连续序列
128. 最长连续序列 - 力扣#xff08;LeetCode#xff09;
这个题要求O(n)的时间复杂度#xff0c;我一开始想的是双指针算法#xff08;因为我并不是很熟悉set容器的使用#xff09;#xff0c;但是双指针算法有小部分数据过不了。
题解给的哈…哈希
128.最长连续序列
128. 最长连续序列 - 力扣LeetCode
这个题要求O(n)的时间复杂度我一开始想的是双指针算法因为我并不是很熟悉set容器的使用但是双指针算法有小部分数据过不了。
题解给的哈希算法太妙了简单来说就是通过unordered_set来去重然后对于序列中的每一个元素num使用count操作来查找序列中是否存在num-1不存在的话说明这个元素num是连续序列的首元素最后比较得到最大值就行。 set、multiset、map、multimap 特点底层是红黑树键值有序set 、 map 键不可重复multiset 和 multimap 可重复 复杂度插入、删除、查找都为O(logN) unordered_setunordered_mapunordered_multisetunordered_multimap 特点底层实现是哈希表键值无序unordered_set 和 unordered_map 键不可重复而另外两个可以重复 复杂度插入、删除、查找平均为O(1)最坏为O(N)空间换时间 C代码
class Solution {
public:int longestConsecutive(vectorint nums) {unordered_setintnum_set;for(auto num:nums)num_set.insert(num);int ans0;for(auto num:num_set){if(num_set.count(num-1)0){int curnum;int curans1;while(num_set.count(cur1)){cur1;curans1;}ansmax(ans,curans);}}return ans;}
};
python代码
class Solution:def longestConsecutive(self, nums: List[int]) - int:ans0num_setset(nums)for num in num_set:if num-1 not in num_set:cur_numnumcur_ans1while cur_num1 in num_set:cur_num1cur_ans1ansmax(ans,cur_ans)return ans 双指针
283.移动零
283. 移动零 - 力扣LeetCode
方法一用双指针算法把非0的元素移动到前面去最后补0
class Solution {
public:void moveZeroes(vectorint nums) {int j0;for(int i0;inums.size();i){if(nums[i]){nums[j]nums[i];}}for(int ij;inums.size();i){nums[i]0;}}
}; 方法二我也不知道题解怎么想出来的
class Solution {
public:void moveZeroes(vectorint nums) {int j0;for(int i0;inums.size();i){if(nums[i]){int tempnums[i];nums[i]nums[j];nums[j]temp;j;}}}
};
python代码
class Solution:def moveZeroes(self, nums: List[int]) - None:Do not return anything, modify nums in-place instead.j0for i in range(len(nums)):if nums[i]:nums[j],nums[i]nums[i],nums[j]j1
11.盛最多水的容器
11. 盛最多水的容器 - 力扣LeetCode 这道题的最优解法是左右双指针法。双指针法的难点在于难于想到难以证明。 AcWing 1575. 从暴力优化到双指针明明白白图解 - AcWing 移动短的一边是因为如果移动长的一边,宽已经由短的一边固定了,长度在不断缩减,所以以后的面积只会比现在小如果移动短的一边即使长度变短了,但是宽度和长度的乘积可能会变大最后就是将最大值返回
class Solution {
public:int maxArea(vectorint height) {int ans-1;int i0,jheight.size()-1;while(i!j){ansmax(ans,(j-i)*min(height[i],height[j]));if(height[i]height[j])i;else j--;}return ans;}
};
python
class Solution:def maxArea(self, height: List[int]) - int:ans-1i0jlen(height)-1while(i!j):ansmax(ans,(j-i)*min(height[i],height[j]))if(height[i]height[j]):i1else:j-1return ans 15.三数之和
15. 三数之和 - 力扣LeetCode
排序使用std::sort对数组进行排序。外层循环从第一个元素开始每次选择一个元素作为三元组的第一个数。内层循环使用两个指针left和right从中间开始向两边扩展寻找和为0的三元组。跳过重复元素在添加三元组到结果数组之前检查当前元素是否与前一个元素相同如果是则跳过当前元素避免重复。
定一找二变双指针
class Solution {
public:vectorvectorint threeSum(vectorint nums) {std::sort(nums.begin(), nums.end());vectorvectorint ans;int n nums.size();for (int i 0; i n - 2; i) {if (i nums[i] nums[i - 1]) continue; // 跳过重复的元素int left i 1, right n - 1;while (left right) {long long sum nums[i] nums[left] nums[right];if (sum 0) {ans.push_back({nums[i], nums[left], nums[right]});while (left right nums[left] nums[left 1]) left; // 跳过重复的元素while (left right nums[right] nums[right - 1]) right--; // 跳过重复的元素left;right--;} else if (sum 0) {left;} else {right--;}}}return ans;}
};
