当前位置: 首页> 娱乐> 八卦 > 代码随想录算法训练营第7天

代码随想录算法训练营第7天

时间:2025/7/10 5:38:34来源:https://blog.csdn.net/weixin_73795426/article/details/140307333 浏览次数:0次

454.四数相加

题目链接:454. 四数相加 II - 力扣(LeetCode)

视频/文档链接:代码随想录 (programmercarl.com)

第一想法

遍历数组num1,num2,计算其和出现的数量,放入map集合中,键为和,值为出现的次数。遍历num3,num4,0-若其和的值出现在Map集合中,则count+=该值即可。

可优化点

不熟悉调用mapAPI。

map.put(sum, map.getOrDefault(sum, 0) + 1);
res += map.getOrDefault(0 - i - j, 0);

代码

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int count = 0;Map<Integer, Integer> map = new HashMap<Integer, Integer>();for(int i : nums1){for(int j:nums2){int sum = i+j;map.put(sum,map.getOrDefault(sum,0)+1);}}for (int k : nums3) {for (int n : nums4) {int sum = k+n;if(map.containsKey(-sum)){count+=map.get(-sum);}}}return count;}
}

383.赎金信

 题目链接:383. 赎金信 - 力扣(LeetCode)

视频/文档链接:代码随想录 (programmercarl.com)

第一想法

这个题和力扣242题很像。

对于案例:ransomNote = "aa", magazine = "aab"

力扣242:字符串s和t每个字母出现的次数都必须一样。所以返回false

力扣383:只要求ransdomNote每个字母数量<=magazine,则返回true。

代码

一次过。

class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] ransdomArr = new int[26];int[] magazineArr = new int[26];for (int i = 0; i < ransomNote.length(); i++) {ransdomArr[ransomNote.charAt(i)-'a']++;}for (int j = 0; j < magazine.length(); j++) {magazineArr[magazine.charAt(j)-'a']++;}for (int i = 0; i < 26; i++) {if(ransdomArr[i]>magazineArr[i])return false;}return true;}
}

15.三数之和

题目链接:15. 三数之和 - 力扣(LeetCode)

文档/视频链接:代码随想录 (programmercarl.com)

第一想法

a+b+c = 0,直接暴力循环然后去重。
a从第1个元素遍历,b从i+1处遍历,然后c的值应为-(a+b),看map集合中是否存在。最终去除重复元素。

代码随想录想法

首先先将数组排序,一层for循环,i代表当前元素a,再定义left指针b和right指针c,

若相加之和>0,则right--,相加之和<0,left++,相加之和 = 0,则加入结果集。直到left = right终止循环,相等时无意义。

当去重a时需要判断 if(nums[i] != nums[i-1]),即当前元素与之前元素不同,那么第一个元素不是会报空指针异常么,怎么避免这个问题?按照这样就能避免对 i= 0 时进行判定了。

  if (i > 0 && nums[i] == nums[i - 1]) {  // 去重acontinue;}

每次遍历对第一个元素要都判断是否>0,所以nums[i]>0这个判断逻辑要加到循环里面。还有个细节是直接return,而不是continue了。因为已经排序的数组,一旦碰上正数,往后的也必须是正数。

关于b和c的去重

我在看视频的时候也想的是直接将去重逻辑提前。

 if (nums[i] + nums[left] + nums[right] > 0) {
        right--;
        // 去重 right
        while (left < right && nums[right] == nums[right + 1]) right--;
    } else if (nums[i] + nums[left] + nums[right] < 0) {
        left++;
        // 去重 left
        while (left < right && nums[left] == nums[left - 1]) left++;
    } else {
    }

但对提升效率没有帮助,反正去重也是一个一个减下去,在哪里减都是一样的。

索性放在else中,结构更好看一点。

同时去重时还要判断left<right,是为了防止指针越界需要加上。可以记小模版就是while(left<right)再套while循环,里面while条件要考虑加外层循环条件。

代码

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> endResult = new ArrayList<>();Arrays.sort(nums);//排序for (int i = 0; i < nums.length; i++) {if(nums[i]>0)return endResult;if(i>0&&nums[i]==nums[i-1])continue;//进入判断逻辑int left = i + 1;int right = nums.length - 1;while (left < right){if(nums[i]+nums[left]+nums[right]>0)right--;else if(nums[i]+nums[left]+nums[right]<0)left++;else{//将结果加入endResult中,这个语句是这样写的。endResult.add(Arrays.asList(nums[i],nums[left],nums[right]));//这里就需要去重了while (left<right&&nums[right-1]==nums[right])right--;//假设2,3,3,循环结束后right指的是最后一个重复元素3(第2个)while (left<right&&nums[left+1]==nums[left])left++;//同理right--;//这里才正真跳到最终不同的值上left++;}}}return endResult;}
}

18.四数之和

题目链接/文章讲解/视频讲解: 代码随想录

在三数之和基础上再套一层循环。

看完代码随想录的想法

剪枝的逻辑不能是nums[i]>0,因为此时目标是target,而target可能是负数,排序之后的数组可以是越加越小,即target = -5, nums = [-4,-1,0,0]。

但是我们依旧可以去做剪枝,逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。

 每次对第一个元素不做判断,所以第二层循环去重时j>i+1&&nums[j]==nums[j-1],而不应当惯性思维是j>0

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> endResult = new ArrayList<>();Arrays.sort(nums);for (int i = 0; i < nums.length; i++) {//剪枝if(nums[i]>target&&(nums[i]>0||target>0))return endResult;if(i>0&&nums[i]==nums[i-1])continue;for (int j = i + 1; j < nums.length - 1 - 1; j++) { //0,1,2,3,j<2,//去重if( j > i+1 &&nums[j] == nums [j-1]) //j为1时不应去重continue;int left = j+1;int right = nums.length-1;while (left<right){if(nums[i]+nums[j]+nums[left]+nums[right]>target)right--;else if(nums[i]+nums[j]+nums[left]+nums[right]<target)left++;else{endResult.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));while (left<right&&nums[right-1] ==nums[right])right--;while (left<right&&nums[left+1] == nums[left])left++;right--;left++;}}}}return endResult;}
}

关键字:代码随想录算法训练营第7天

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: