如何修改网站,企业网项目建设实践,茌平做网站,网站建设要学多久代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客 第三章 哈希表part02 今日任务 ● 454.四数相加II
● 383. 赎金信
● 15. 三数之和
● 18. 四数之和
● 总结 详细布置 454.四数相加II 建议#xff1a;本题是 使用map 巧妙解决的问题#xff0c;好好体会一下 … 代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客 第三章 哈希表part02 今日任务 ● 454.四数相加II
● 383. 赎金信
● 15. 三数之和
● 18. 四数之和
● 总结 详细布置 454.四数相加II 建议本题是 使用map 巧妙解决的问题好好体会一下 哈希法 如何提高程序执行效率降低时间复杂度当然使用哈希法 会提高空间复杂度但一般来说我们都是舍空间 换时间 工业开发也是这样。题目链接/文章讲解/视频讲解https://programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html 383. 赎金信 建议本题 和 242.有效的字母异位词 是一个思路 算是拓展题 题目链接/文章讲解https://programmercarl.com/0383.%E8%B5%8E%E9%87%91%E4%BF%A1.html 15. 三数之和 建议本题虽然和 两数之和 很像也能用哈希法但用哈希法会很麻烦双指针法才是正解可以先看视频理解一下 双指针法的思路文章中讲解的没问题 哈希法很麻烦。 题目链接/文章讲解/视频讲解https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html 18. 四数之和 建议 要比较一下本题和 454.四数相加II 的区别为什么 454.四数相加II 会简单很多这个想明白了对本题理解就深刻了。 本题 思路整体和 三数之和一样的都是双指针但写的时候 有很多小细节需要注意建议先看视频。 题目链接/文章讲解/视频讲解https://programmercarl.com/0018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C.html
目录
0454_四数相加II
0383_赎金信
0015_三数之和
0018_四数之和
总结-map常用方法 0454_四数相加II 本题解题步骤 首先定义 一个unordered_mapkey放a和b两数之和value 放a和b两数之和出现的次数。遍历大A和大B数组统计两个数组元素之和和出现的次数放到map中。定义int变量count用来统计 abcd 0 出现的次数。在遍历大C和大D数组找到如果 0-(cd) 在map中出现过的话就用count把map中key对应的value也就是出现次数统计出来。最后返回统计值 count 就可以了。 V put(K key, V value)default V getOrDefault(Object key, V defaultValue) 时间复杂度: O(n^2)空间复杂度: O(n^2)最坏情况下A和B的值各不相同相加产生的数字个数为 n^2 class Solution0454 {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res 0;MapInteger, Integer map new HashMapInteger, Integer();//统计两个数组中的元素之和同时统计出现的次数放入mapfor (int i : nums1) {for (int j : nums2) {int sum i j;map.put(sum, map.getOrDefault(sum, 0) 1);}}//统计剩余的两个元素的和在map中找是否存在相加为0的情况同时记录次数for (int i : nums3) {for (int j : nums4) {res map.getOrDefault(0 - i - j, 0);}}return res;}
}
0383_赎金信
class Solution0383 {public boolean canConstruct(String ransomNote, String magazine) {char[] charArray1 ransomNote.toCharArray();int[] letter1 new int[26];for (int i 0; i charArray1.length; i) {letter1[charArray1[i] - a];}char[] charArray2 magazine.toCharArray();int[] letter2 new int[26];for (int i 0; i charArray2.length; i) {letter2[charArray2[i] - a];}for (int i 0; i 26; i) {if (letter1[i] ! 0 letter2[i] 0) {return false;}if (letter1[i] letter2[i]) {return false;}}return true;}public boolean canConstruct2(String ransomNote, String magazine) {int[] record new int[26];if (ransomNote.length() magazine.length()) {return false;}for (int i 0; i magazine.length(); i) {//通过 record 数据记录 magazine 里各个字符出现次数record[magazine.charAt(i) - a];}for (int j 0; j ransomNote.length(); j) {//遍历 ransomNote在 record 里对应的字符个数做--操作record[ransomNote.charAt(j) - a]--;//如果小于零说明 ransomNote 里出现的字符magazine 没有if (record[ransomNote.charAt(j) - a] 0) {return false;}}return true;}public boolean canConstruct3(String ransomNote, String magazine) {//shortcutif (ransomNote.length() magazine.length()) {return false;}//定义一个哈希映射数组int[] record new int[26];//遍历for (char c : magazine.toCharArray()) {record[c - a] 1;}for (char c : ransomNote.toCharArray()) {record[c - a] - 1;}//如果数组中存在负数说明ransomNote字符串总存在magazine中没有的字符for (int i : record) {if (i 0) {return false;}}return true;}
}
0015_三数之和
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;class Solution0015 {//版本一双指针public ListListInteger threeSum(int[] nums) {ListListInteger result new ArrayList();Arrays.sort(nums);//找出a b c 0//a nums[i], b nums[left], c nums[right]for (int i 0; i nums.length; i) {//排序之后如果第一个元素已经大于零那么无论如何组合都不可能凑成三元组直接返回结果就可以了if (nums[i] 0) {return result;}//错误去重a方法将会漏掉-1,-1,2 这种情况/*if (nums[i] nums[i 1]) {continue;}*///正确去重a方法if (i 0 nums[i] nums[i - 1]) {//去重acontinue;}int left i 1;int right nums.length - 1;while (right left) {//去重复逻辑如果放在这里000的情况可能直接导致rightleft了从而漏掉了0,0,0这种三元组/*while (right left nums[right] nums[right - 1]) right--;while (right left nums[left] nums[left 1]) left;*/int sum nums[i] nums[left] nums[right];if (sum 0) {right--;} else if (sum 0) {left;} else {result.add(Arrays.asList(nums[i], nums[left], nums[right]));//去重逻辑应该放在找到一个三元组之后对b和c去重while (right left nums[right] nums[right - 1]) right--;while (right left nums[left] nums[left 1]) left;//找到答案时双指针同时收缩right--;left;}}}return result;}
}class Solution0015_2 {//版本二使用哈希集合public ListListInteger threeSum(int[] nums) {ListListInteger result new ArrayList();Arrays.sort(nums);for (int i 0; i nums.length; i) {//如果第一个元素大于零不可能凑成三元组if (nums[i] 0) {return result;}//三元组元素a去重if (i 0 nums[i] nums[i - 1]) {continue;}HashSetInteger set new HashSet();for (int j i 1; j nums.length; j) {//三元组元素b去重if (j i 2 nums[j] nums[j - 1] nums[j - 1] nums[j - 2]) {continue;}int c -nums[i] - nums[j];if (set.contains(c)) {result.add(Arrays.asList(nums[i], nums[j], c));set.remove(c);//三元组元素c去重} else {set.add(nums[j]);}}}return result;}
}
0018_四数之和
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;class Solution0018 {public ListListInteger fourSum(int[] nums, int target) {ListListInteger result new ArrayList();Arrays.sort(nums);for (int i 0; i nums.length; i) {// nums[i] target 直接返回, 剪枝操作if (nums[i] 0 nums[i] target) {return result;}if (i 0 nums[i - 1] nums[i]) {//对nums[i]去重continue;}for (int j i 1; j nums.length; j) {if (j i 1 nums[j - 1] nums[j]) {//对nums[j]去重continue;}int left j 1;int right nums.length - 1;while (right left) {//nums[k] nums[i] nums[left] nums[right] targetint会溢出long sum (long) nums[i] nums[j] nums[left] nums[right];if (sum target) {right--;} else if (sum target) {left;} else {result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));//对nums[left]和nums[right]去重while (right left nums[right] nums[right - 1]) right--;while (right left nums[left] nums[left 1]) left;left;right--;}}}}return result;}
}
总结-map常用方法 在 Java 中Map 接口提供了多种常用方法来操作键值对。Map 接口中一些常用的方法及其功能描述它们在 Java 中被广泛使用。 这些方法使得对键值对进行增加、获取、删除、判断是否包含等操作变得十分方便。 这些方法的详细说明如下 put(K key, V value): 将指定的键与指定的值关联并返回与键关联的先前值如果存在。 get(Object key): 返回指定键所映射的值如果 Map 中不包含该键则返回 null。 getOrDefault(Object key, V defaultValue): 返回指定键所映射的值如果 Map 中不包含该键则返回指定的默认值。 containsKey(Object key): 如果 Map 包含指定键的映射关系则返回 true。 containsValue(Object value): 如果 Map 将一个或多个键映射到指定值则返回 true。 remove(Object key): 如果存在键的映射关系则将其从 Map 中删除并返回与该键关联的值。 size(): 返回 Map 中键值对的数量。 isEmpty(): 如果 Map 中没有键值对则返回 true。 keySet(): 返回一个包含 Map 中所有键的 Set 集合。 values(): 返回一个包含 Map 中所有值的 Collection 集合。 entrySet(): 返回一个包含 Map 中所有键值对的 Set 集合每个元素都是一个 Map.Entry 对象。 这些是 Map 接口中最常用的方法可以用来执行键值对的增加、获取、删除、判断是否包含等操作。 package com.question.solve.test;import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;public class _001_MapMethod {public static void main(String[] args) {//方法一在for-each循环中使用entries来遍历MapInteger, Integer map new HashMapInteger, Integer();for (Map.EntryInteger, Integer entry : map.entrySet()) {System.out.println(Key entry.getKey() , Value entry.getValue());}//方法二在for-each循环中遍历keys或values。MapInteger, Integer map2 new HashMapInteger, Integer();//遍历map中的键for (Integer key : map2.keySet()) {System.out.println(Key key);}//遍历map中的值for (Integer value : map2.values()) {System.out.println(Value value);}//方法三使用Iterator遍历MapInteger, Integer map3 new HashMapInteger, Integer();IteratorMap.EntryInteger, Integer entries map3.entrySet().iterator();while (entries.hasNext()) {Map.EntryInteger, Integer entry entries.next();System.out.println(Key entry.getKey() , Value entry.getValue());}//方法四通过键找值遍历效率低MapInteger, Integer map4 new HashMapInteger, Integer();for (Integer key : map4.keySet()) {Integer value map4.get(key);System.out.println(Key key , Value value);}}
}
