男女怎么做那个视频网站,天津招投标天津建设工程信息网,app开发与网站开发的区别,html网页制作简单代码本文代码思路来源于:
代码随想录
前言 希望大家在刷这部分题的时候先熟悉熟悉哈希结构的基本常用api,比较方便理解. LeetCode T454 四数之和
题目链接:454. 四数相加 II - 力扣#xff08;LeetCode#xff09; 题目思路 暴力解法仍然是遍历四个数组解决此题, 哈希的思路有…本文代码思路来源于:
代码随想录
前言 希望大家在刷这部分题的时候先熟悉熟悉哈希结构的基本常用api,比较方便理解. LeetCode T454 四数之和
题目链接:454. 四数相加 II - 力扣LeetCode 题目思路 暴力解法仍然是遍历四个数组解决此题, 哈希的思路有点类似于两数之和的解决方式,我们可以将四个数组分成两部分,数组1和数组2的和形成一个新数组(便于理解并没有去这样做,只是遍历两个数组),同理三四号数组也是一样, 1.首先我们创建一个HashMap,key放两数之和,value放和出现的次数 2.遍历数组1和数组2,将两数之和和出现次数放到map中 3.遍历数组3和数组4,在HashMap中查找是否存在0-前面的两数之和,存在就用res变量来记录 getOrDefault函数解释 代码示例
class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {MapInteger,Integer map new HashMap();int res 0;for(int i:nums1){for(int j:nums2){int sum ij;map.put(sum,map.getOrDefault(sum,0)1);}}for(int i:nums3){for(int j :nums4){resmap.getOrDefault(0-i-j,0);}}return res;}
}
LeetCode T383 赎金信
题目链接:383. 赎金信 - 力扣LeetCode 题目思路 这题乍一看有点像我们的相同字母的异序词那道题,那道题我们使用了哈希数组来实现,实际上这道题我们也能如法炮制,因为题目说了字符串全是小写字母,数量有限,很方便我们来映射,下面我们来说说基本步骤: 1.首先我们创建一个record数组用来当我们的哈希数组用来映射 2.然后我们将magazine字符串转成数组再用字符c遍历,c-a就是数组的下标,我们让这个位置的元素即可 3.接着同理用字符c遍历ransomNote遍历,执行--操作 4.for循环遍历数组record,判断是否有小于0的数字,如果有,就返回false,没有就返回true. 代码实现
class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] record new int[26];if(ransomNote.length()magazine.length()){return false;}for(char c:magazine.toCharArray()){record[c-a];}for(char c:ransomNote.toCharArray()){record[c-a]--;}for(int j: record){if(j 0){return false;}}return true;}
} LeetCode T15 三数之和
题目链接:15. 三数之和 - 力扣LeetCode 题目思路 使用双指针法,首先我们创建一个二维数组res,然后对数组进行排序.(降序排列) 总体思路是i指向第一个元素的下标,left指针指向i1的下标,right指针指向length-1的下标,然后for循环遍历数组,首先判断i下标的值是否小于0,如果小于0则直接返回数组元素,如果不是则进行判断,三数之和大于0的话,则应该让right向前走,反之则让left向后走,好了,剩下就是处理细节的去重操作了.也是本题的精华所在 去重逻辑的思考 首先这里我们知道,三数之和不能取重复的三元组,比如 {1,1,-1,0},这里的{1,-1,0}这个三元组只能取一次,那么我们就要进行去重,首先对nums[i]进行去重,这里有两种去重方式,第一种是nums[i]和nums[i1]进行比较,还有一种是nums[i]和nums[i-1]进行比较,我们到底选哪一种呢? 我们不妨就{-1,-1,2}这个例子来看,如果我们选择了第一种去重方式,那么我们就会发现,当遍历到第一个-1的时候,判断下一个也是-1,那这组数据就直接被pass了,这里强调一下我们要的三元组组内数据可以重复,但是三元组不能重复,例如{0,0,0}也是满足要求的一个三元组. 所以对于第一个去重操作,我们应该这样写: if (i 0 nums[i] nums[i - 1]) {continue;
} 接下来就是对nums[right]和nums[left]进行去重,我们知道数组是排好序的,如果三个数加起来是大于0的,我们就可以让right指针向前走,反之我们应该让left指针向后走. 但细想一下这种去重其实对提升程序运行效率是没有帮助的. 拿right去重为例即使不加这个去重逻辑依然根据 while (right left) 和 if (nums[i] nums[left] nums[right] 0) 去完成right-- 的操作。 多加了 while (left right nums[right] nums[right 1]) right--; 这一行代码其实就是把 需要执行的逻辑提前执行了但并没有减少 判断的逻辑。 最直白的思考过程就是right还是一个数一个数的减下去的所以在哪里减的都是一样的。 所以这种去重 是可以不加的。 仅仅是 把去重的逻辑提前了而已。 代码实现
class Solution {public ListListInteger threeSum(int[] nums) {List ListInteger res new ArrayList();Arrays.sort(nums);for(int i 0;inums.length;i){if(nums[i]0){return res;} if(i0 nums[i-1] nums[i]){continue;} int left i1;int right nums.length-1;while(leftright){int sum nums[i] nums[left] nums[right];if(sum 0){right--;}else if(sum0){left;}else{res.add(Arrays.asList(nums[i],nums[left],nums[right]));while(leftright nums[right] nums[right-1]){right--;}while(leftright nums[left] nums[left 1] ){left;}left;right--;}}}return res;}
}
LeetCode T18 四数之和
题目链接:18. 四数之和 - 力扣LeetCode 题目思路 本质上就是在三数之和,外面再套了一层for循环,重点就是这个去重的过程如何进行,下面我们来仔细分析一下去重的过程 去重的思路 有人可能上来就按照三数之和的思路上来就判断nums[i]和target的大小,这里就出问题了,首先三数之和保证了target是0,这里target不知道是多少,所以我们要保证我们的nums[i]0才可以,不然两个负数相加也可以越加越小啊,这明显不满足题目要求,我们注意这里虽然是排好序的数字,但是直接用nums[i]和target做判断未免太过武断,综上所述我们是这样操作的. if (nums[i] 0 nums[i] target) {return result;
} 然后进行和三数之和一样的去重操作 if(i0 nums[i] nums[i-1])
{continue;
} 接着第二层for循环,先剪枝去重,接着进行双指针 if(nums[i] nums[j]target nums[i]0){return result;}if(ji1 nums[j] nums[j-1]){continue;} 代码实现
class Solution {public ListListInteger fourSum(int[] nums, int target) {ListListInteger result new ArrayList();Arrays.sort(nums);for(int i 0;inums.length;i){//一级剪枝if(nums[i]target nums[i]0){return result;}if(i0 nums[i] nums[i-1]){continue;}for(int j i1;jnums.length;j){if(nums[i] nums[j]target nums[i]0){return result;}if(ji1 nums[j] nums[j-1]){continue;}int left j1;int right nums.length-1;while(rightleft){long sum nums[i] nums[j] nums[left] nums[right];if(sumtarget){right--;}else if(sum target){left;}else{result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));while(rightleft nums[left] nums[left1] ){left;}while(rightleft nums[right] nums[right-1]){right--;}left;right--;}}}}return result;}
}
