各大网站博客怎么做推广,东莞高端网站建设费,商丘雷光网络科技有限公司,设计装修leetcode hot 100 哈希1.字母异位词分组2.最长连续序列 双指针1.盛最多水的容器2.和为 K 的子数组 数组1.除自身以外数组的乘积 哈希
1.字母异位词分组
49. 字母异位词分组
方法一#xff1a;排序 由于互为字母异位词的两个字符串包含的字母相同#xff0c;因此对两个字符… leetcode hot 100 哈希1.字母异位词分组2.最长连续序列 双指针1.盛最多水的容器2.和为 K 的子数组 数组1.除自身以外数组的乘积 哈希
1.字母异位词分组
49. 字母异位词分组
方法一排序 由于互为字母异位词的两个字符串包含的字母相同因此对两个字符串分别进行排序之后得到的字符串一定是相同的故可以将排序之后的字符串作为哈希表的键。
unordered_mapstring, vectorstring 主要是理解key是排序后的字母序列value是vector存放了多个string
class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {int n strs.size();unordered_mapstring, vectorstring map;for (auto s : strs) {string tmp s;sort(tmp.begin(), tmp.end());map[tmp].emplace_back(s);}vectorvectorstring ans;for (unordered_mapstring, vectorstring::iterator it map.begin(); it ! map.end(); it) {ans.emplace_back(it-second);}return ans;}
};2.最长连续序列
128. 最长连续序列 重要的是思路 1.用set去除重复数 2.找到一个序列起点最小的数num开始在容器里while找num是否存在如果存在那么len 3.怎么找到最小数也不能说是最小数是一个连续数种的最小数num - 1如果存在那么他就不是连续的最小数
unordered_setint mp;
...
for (auto num: mp) {if (mp.count(num -1)) continue;int curnum num;int len 1;while (mp.count(curnum 1)) {curnum 1;len 1;}longestlen max(len, longestlen);
}class Solution {
public:int longestConsecutive(vectorint nums) {int res 0; // 记录最长连续序列的长度unordered_setint num_set(nums.begin(), nums.end()); // 记录nums中的所有数值int seqLen;for(int num: num_set){// 如果当前的数是一个连续序列的起点统计这个连续序列的长度if(!num_set.count(num - 1)){seqLen 1; // 连续序列的长度初始为1while(num_set.count(num))seqLen; // 不断查找连续序列直到num的下一个数不存在于数组中res max(res, seqLen); // 更新最长连续序列长度}}return res;}
};双指针
1.盛最多水的容器
11. 盛最多水的容器 两个for循环找最大值会超时那么就有小心机如果当前高度不比之前高那么答案一定小于之前的值就不必再循环了
class Solution {
public:int maxArea(vectorint height) {int left 0, ans 0, high 0;for (; left height.size() - 1; left) {if (height[left] high) high height[left];if (height[left] high) continue;for (int right left 1; right height.size(); right) {int tmp (right - left) * min(height[left], height[right]);ans max(ans, tmp); }}return ans;}
};正经的比较快的算法是两端向中间移动每次移动较小的边计算最大值
class Solution {
public:int maxArea(vectorint height) {int l 0, r height.size() - 1;int ans min(height[l], height[r]) * (r - l);while (l r) {if (height[l] height[r]) {l;} else {r--;}ans max(ans, (r - l) * min(height[l], height[r]));}return ans;}
};2.和为 K 的子数组
560. 和为 K 的子数组 题目需要注意的是和为K的子数组那么 1.用pre[i]表示num[0]到num[i]的和 2.num[i 1]到num[j]的和为 pre[j] - pre[i] 3.其和为k, 那么nums[j]位置需要找到和为pre[j] - k的前缀和
class Solution {
public:int subarraySum(vectorint nums, int k) {unordered_mapint, int mp;mp[0] 1;int pre 0, ans 0;for (auto c : nums) {pre c;if (mp.count(pre - k)) {ans mp[pre - k];}mp[pre];}return ans;}
};数组
1.除自身以外数组的乘积
238. 除自身以外数组的乘积 还是想用前缀和做计算num[i]的乘积就是计算pre[i -1] * 后缀和 但是超时了
class Solution {
public:vectorint productExceptSelf(vectorint nums) {vectorint ans;int pre 0;for (int i 0; i nums.size(); i) {if (i 0) pre 1;else pre * nums[i - 1];int tmp pre;for (int j i 1; j nums.size(); j) {tmp * nums[j];}ans.emplace_back(tmp);}return ans;}
};前缀和 后缀和 前缀和 1.i从0开始向后 2.ans[i] pre; 3.pre * nums[i]; 先把pre[i -1]放到ans[i]再乘
后缀和 1.i从size()-1开始向前 2.ans[i] * sum2; 3.sum2 * nums[i]; 前缀乘以back[i1]到back.end() - 1 https://blog.csdn.net/qq_43553082/article/details/118620364 vector在还没有分配任何空间时还不能像数组一样用下标形式去访问vector的v[0]也不行否则编译通过但报运行错误runtime error 如vector创建的时候是使用vectorint v; 或者vector还是[]的时候考虑官方测试数据的输入可能为[]的情况使用[ ]前需要判断一下是否为空会报错 如v[0]1、if(v[0])、v[0]等情况都会报错 这种情况需要先push_back()或v{12}等形式给其分配了空间后才能用【】形式访问 本题中 vectorint ans(nums.size()); class Solution {
public:vectorint productExceptSelf(vectorint nums) {vectorint ans(nums.size());int sum 1;for (int i 0; i nums.size(); i) {ans[i] sum;sum * nums[i];}int sum2 1;for (int i nums.size() - 1; i 0; i--) {ans[i] * sum2;sum2 * nums[i];}return ans;}
};
