建设网站出现400错误,苏州做网站的企业,网站界面分析,网站备案有什么好处文章目录 454.四数相加II思路 383.赎金信思路 15.三数之和思路剪枝去重 18.四数之和思路剪枝去重复习#xff1a;C中的类型转换方法 总结 今天是哈希表专题的第二天 废话不多说#xff0c;直接上题目
454.四数相加II
建议#xff1a;本题是 使用map 巧妙解决的问题#x… 文章目录 454.四数相加II思路 383.赎金信思路 15.三数之和思路剪枝去重 18.四数之和思路剪枝去重复习C中的类型转换方法 总结 今天是哈希表专题的第二天 废话不多说直接上题目
454.四数相加II
建议本题是 使用map 巧妙解决的问题好好体会一下 哈希法 如何提高程序执行效率降低时间复杂度当然使用哈希法 会提高空间复杂度但一般来说我们都是舍空间 换时间 工业开发也是这样。
题目链接454. 四数相加 II - 力扣LeetCode
题目说明本题需要考虑四个数组如何组合加和为0。只需要计算有多少种组合而不需要写出具体的组合方式。同时本题认为对于数组中位置不同的元素a、b即使a与b的值相同(a b)a、b也被视为不同的元素所以我们不需要“去重”比如四个数组的元素都是n个0则认为有不只一个组合每个组合都是0000、0000···区别在于不同组合中的0取自数组的不同位置比如第一个组合的第一个0取自nums1[0]第二个组合的第一个0取自nums1[1]这是本题与后面的一道题目 18.四数之和 的不同之处
思路
这道题目解法很巧妙但是有迹可循前一篇文章day6中的最后一道题 1.两数之和 思路与本题相似我们可以参照 两数之和 中的思路
两数之和中需要在同一个数组中找到相匹配ab target)的元素a、b的下标思路是遍历一遍整个数组同时创建一个map映射作为哈希表记录遍历过的元素的值和下标。每遍历到一个元素a就从哈希表中查找是否有相匹配的元素b即auto it map.find(target-a)。若b在哈希表中则返回a和b的下标即return {i, it-second}遍历结束否则将元素a的 值和下标 作为键值对添加到map中继续遍历
我们把这个思路应用到这道题中首先遍历数组A、B使用map记录数组A、B的和(ab)然后双层for循环求数组C、D的和(cd)在 map中查找是否存在相匹配的ab相匹配指的是abcd 0即auto it map.find(0-(cd))。这是一个大概的思路我们接下来讨论一些细节问题 为什么不用数组或集合作为哈希表 数组作为哈希表乍一看可以但是本题中ab的值是没有大小限制的这就戳到了数组的痛点键的大小必须有大小限制因此不能使用数组作为哈希表 集合中只能存储键ab的值无法存储ab出现次数的信息因此也不能使用集合作为哈希表 map的键值是什么 题目需要求出abcd 0的组合数量而不用列出具体的组合的方式。如果0-(cd)在map中找到了即it ! map.end()那么it-second应该是abcd 0的组合数量这个组合的数量 等于 ab0-(cd)出现的次数用下面的例子解释 若当前c-1d2那么要从map中找到ab 0-(cd) -1。map中ab -1共出现了一次a1b-2所以当c-1d2时abcd 0这样的组合只有一个就是ab-1出现的次数 通过上述分析可知我们使用0-(cd)在map中寻找需要获得ab0-(cd)的出现次数因此map的键值对为**ab的值val abval的出现次数** 能不能只用A构建map然后再遍历B、C、D三个数组寻找0-(bcd) 可以但是时间复杂度是O(n3)而我们两两遍历时间复杂度是O(n2)因此还是用A、B构建map然后再遍历C、D更加合适 整体思路 首先遍历数组A、B使用map记录数组A、B的和(ab)key存放a和b两数之和value存放a和b两数之和出现的次数。然后遍历数组C、D求数组C、D的和(cd)在map中查找是否存在相匹配的ab相匹配指的是abcd 0即auto it map.find(0-(cd))。如果找到了即it ! map.end()那么count it-secondcount加上key对应的value统计这个组合的数量否则不做处理。遍历完C和D后返回count这个count就是四个数组中abcd 0的组合数量
代码实现
class Solution {
public:int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) {// 思路就是先进行两个数组A、B的加法得到一个哈希表key为ab的值value为这个值出现的次数// 然后双层for循环先对C、D做加法和为cd然后再哈希表中查找0-(cd)如果找到了则这个键对应的值是abcd0组合的出现次数std::unordered_mapint, int map;for(int a : nums1){for(int b : nums2){map[ab];}}int count 0;for(int c : nums3){for(int d : nums4){auto it map.find(0-(cd));if( it ! map.end()){count it-second; }}}return count;}
};时间复杂度: O(n2)空间复杂度: O(n2)最坏情况下A和B的值各不相同相加产生的数字个数为 n2
383.赎金信
本题 和 242.有效的字母异位词 是一个思路 算是拓展题
题目链接383. 赎金信 - 力扣LeetCode
思路
本题中两个字符串都是用小写字母组成key的大小是有限制的所以我们可以使用数组实现哈希表。数组的key是 字符串magazine中的各个字符-‘a’value是 字符串magazine中的各个字符出现的次数
由于map需要维护红黑树或者哈希表而且还要做哈希函数所以很费时而且map的空间消耗要比数组的大所以能用数组就不map使用数组更加简单有效
代码实现
class Solution {
public:bool canConstruct(string ransomNote, string magazine) {vectorint record(26, 0);if(ransomNote.size() magazine.size()){return false;}// 首先统计magazine中各个字出现的次数for(char c : magazine){record[c-a];}// 然后检查这些字符是否能组成ransomNotefor(char c : ransomNote){if(--record[c-a] 0) // 注意是--record不是record--要先减再判断{return false;}}return true;}
};时间复杂度: O(n)空间复杂度: O(1)
15.三数之和
建议本题虽然和 两数之和 很像也能用哈希法但用哈希法会很麻烦双指针法才是正解可以先看视频理解一下 双指针法的思路。
题目链接15. 三数之和 - 力扣LeetCode
这道题的测试用例有点癫
思路
本题的难点在于找到不重复的三元组这就需要去重本题与454.四数之和II是不同的
哈希法查找元素是没有顺序的去重的时候会很麻烦本题使用排序双指针法
排序双指针法 初始化首先将数组排序然后有一层for循环遍历数组下标i从0的开始同时定义一个下标left定义在i1的位置上定义下标right在数组末尾的位置上 寻找过程要在数组中找到三元组{a, b, c}使得abc 0这里a nums[i]bnums[left]cnums[right] 接下来如何移动left 和 right 呢有三种情况 如果a b c 0则说明nums[right]太大了right–如果a b c 0则说明nums[left]太小了left如果a b c 0则找到了一个三元组{a, b, c}我们将它用一个二维数组存放起来然后左右指针同时紧缩即依次做right-- 和 left 结束本次查找遍历下一个元素当left与right相遇时我们结束left和right的移动然后i移动到下一个元素继续进行上述步骤直至数组遍历完了
注意while循环终止条件是right left还是right left呢对于这样的边界条件我们可以设身处地的想一想当right left时nums[left]和nums[right]是同一个元素此时找到的abc 0的三元组没有意义因此循环条件是right left
执行过程如图所示 剪枝去重 剪枝排除后续元素全为正的数组每次遍历都需要先判断nums[i]是否大于0。如果nums[i] 0则说明数组的第i位后的所有元素都是正的不可能出现abc 0的情况 去重对a去重判断nums[i] nums[i-1]若成立则continue 比如有数组nums {-1, -1, 2, 2}当i1时nums[i] -1而nums[i-1] -1则说明-1在之前已经使用过了即本次查找的a 和 上一次查找的a重复了。由于 上一次查找的left和right范围{-1, 2, 2} 包含了 本次查找的left和right范围{2, 2}所以在a相同的情况下本次查找的三元组 是 上一次查找查找的三元组的子集这就出现了三元组的重复所以当nums[i] nums[i-1]成立时直接continuenums[i]指向下一个元素 去重对b和c去重每次找到一个三元组后判断。假设有数组nums {-2, -1, -1, 3, 3}当a-2时按照双指针法过程会得到两个三元组结果{-2, -1, 3}和{-2, -1, 3}。 为什么会出现重复呢分析来说第一次循环b、c的下标left1right4abc0然后left和right同时收缩。第二次循环b、c的下标left2right3abc0所以这个三元组也被存放到结果集中了。明显这两次的结果出现了重复原因就在于第一次循环中nums[right] nums[right1]nums[left] nums[left-1]因此left和right同时收缩后b和c的结果还是一样的。对b和c去重就要判断nums[right] nums[right1] 或 nums[left] nums[left-1]是否成立如果成立则需要对right-- 或 对left
代码实现
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint result;sort(nums.begin(), nums.end());int left, right;for(int i0; inums.size(); i){if(nums[i] 0){break;}// 去重aif(i 0 nums[i] nums[i-1]){continue;}left i1;right nums.size()-1;while(right left){if(nums[i] nums[left] nums[right] 0){right--;}else if(nums[i] nums[left] nums[right] 0){left;}else{result.push_back(vectorint{nums[i], nums[left], nums[right]});left;right--;// 去重b和cwhile(right left nums[right] nums[right1]){right--;}while(right left nums[left] nums[left-1]){left;}}}}return result;}
};时间复杂度: O(n^2)可以看到使用双指针减少了一层for循环时间复杂度降低了一个量级空间复杂度: O(1
18.四数之和
建议 要比较一下本题和 454.四数相加II 的区别为什么 454.四数相加II 会简单很多这个想明白了对本题理解就深刻了。 本题 思路整体和 三数之和一样的都是双指针但写的时候 有很多小细节需要注意建议先看视频
题目链接18. 四数之和 - 力扣LeetCode
思路
这道题和 三数之和 思路相同都是使用排序双指针法。注意这道题需要abcd target所以在剪枝上与 三数之和 有所不同。
整体思路首先对nums进行排序然后用两层for循环遍历数组nums获得a nums[i]和b nums[j]在第二层for循环中使用双指针left和right查找与a、b相匹配的c、d四个变量 加和为target去重操作与 三数之和 相同
剪枝去重
剪枝target可能为负值所以用a target剪枝是错误的还需要加上条件a 0因此剪枝条件为a target a 0。第2级for循环的剪枝条件为ab target ab 0去重与 三数之和 相同对a、b去重需要判断nums[i] nums[i-1]避免对重复的a、b进行查找对c、d去重需要判断 nums[left] nums[left-1] 以及 nums[right] nums[right1]若成立则left 或 right–
注意本题有溢出情况需要将sum转化为long long型再进行判断
代码实现
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint result;sort(nums.begin(), nums.end());int left, right;for(int i0; inums.size(); i){// 剪枝处理if(nums[i] target nums[i] 0){break;}// 对nums[i]去重if(i0 nums[i] nums[i-1]){continue;}for(int ji1; jnums.size(); j){// 2级剪枝处理if(nums[i] nums[j] target nums[i] nums[j] 0){break;}// 对nums[j]去重if(j i1 nums[j] nums[j-1]){continue;}left j1;right nums.size()-1;while(right left){// 测试用例中有溢出情况所以要用long long计算sumlong long sum static_castlong long(nums[i]) nums[j] nums[left] nums[right];if(sum target){right--;}else if(sum target){left;}else{result.push_back(vectorint{nums[i], nums[j], nums[left], nums[right]});// 找到答案时双指针同时收缩left;right--;// 双指针去重while(right left nums[right] nums[right1]){right--;}while(right left nums[left] nums[left-1]){left;}}}}}return result;}
};时间复杂度: O(n^3)空间复杂度: O(1)
复习C中的类型转换方法
static_cast
static_cast 是 C 中的一种类型转换运算符用于在编译时执行显式类型转换。它提供了一种安全且明确的方式来进行类型转换确保在转换过程中进行适当的检查除了基本数据类型之间的转换如int转换为double、指针类型之间的转换int* 转换为 double*外static_cast还可以进行类层次结构中的转换
假设有一个基类 Base 和一个派生类 Derived
class Base {
public:virtual void show() {std::cout Base class std::endl;}
};class Derived : public Base {
public:void show() override {std::cout Derived class std::endl;}
};Base* basePtr new Derived();
Derived* derivedPtr static_castDerived*(basePtr); // 将基类指针转换为派生类指针
derivedPtr-show(); // 输出 Derived classdynamic_cast
用于运行时类型检查和转换通常用于多态类型之间的转换。适用于具有继承关系的指针或引用类型之间的转换。
class Base {virtual void foo() {} // 必须有虚函数才能使用 dynamic_cast
};
class Derived : public Base {};Base* basePtr new Derived();
Derived* derivedPtr dynamic_castDerived*(basePtr); // 类层次结构中的转换
if (derivedPtr) {// 成功转换
} else {// 转换失败
}reinterpret_cast
用于在几乎所有类型之间进行位级别的转换适用于指针类型之间、整数类型与指针类型之间的转换。使用时需谨慎因为它可能导致未定义行为。
int a 10;
void* ptr reinterpret_castvoid*(a); // 将 int* 转换为 void*
int* intPtr reinterpret_castint*(ptr); // 将 vo感谢 chatgpt 总结
今天完成了四道题这四道题都比较难需要好好体会。四数相加II 使用的方法与 day6文章中的最后一题 两数之和 思想类似但是又有所不同主要体现在对map的键值对的设定。赎金信比较简单需要注意magazine的每个字符只能用一次。三数之和和四数之和是今天的重点这两道题的难点在于如何去重四数相加II不需要去重所以比这两道题简单。使用哈希法查找元素的时候查找的结果是无顺序的因此去重很麻烦这两道题使用哈希法就不合适了。这两道题更好的解法是排序双指针双指针降低了时间复杂度的数量级。用双指针替代两层for循环这是一个很巧妙的思想。同时要多体会两道题中的剪枝去重操作
双指针小结
截止目前文章中涉及到的双指针法有
27.移除元素(opens new window)15.三数之和(opens new window)18.四数之和(opens new window)
链表相关双指针题目
206.反转链表(opens new window)19.删除链表的倒数第N个节点(opens new window)面试题 02.07. 链表相交(opens new window)142题.环形链表II(opens new window)
双指针法在字符串题目中还有很多应用后面还会介绍到
