wordpress图片多选,seo是指什么岗位,公司内部网站规划,html5网站建站书专栏笔记#xff1a;https://blog.csdn.net/weixin_44949135/category_10335122.html 第三章 哈希表part01今日任务 ● 哈希表理论基础
● 242.有效的字母异位词
● 349. 两个数组的交集
● 202. 快乐数
● 1. 两数之和 详细布置 哈希表理论基础 建议#xff1a;大家要了… 专栏笔记https://blog.csdn.net/weixin_44949135/category_10335122.html 第三章 哈希表part01今日任务 ● 哈希表理论基础
● 242.有效的字母异位词
● 349. 两个数组的交集
● 202. 快乐数
● 1. 两数之和 详细布置 哈希表理论基础 建议大家要了解哈希表的内部实现原理哈希函数哈希碰撞以及常见哈希表的区别数组set 和map。 什么时候想到用哈希法当我们遇到了要快速判断一个元素是否出现集合里的时候就要考虑哈希法。 这句话很重要大家在做哈希表题目都要思考这句话。 文章讲解https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html 242.有效的字母异位词 建议 这道题目大家可以感受到 数组 用来做哈希表 给我们带来的遍历之处。 题目链接/文章讲解/视频讲解 https://programmercarl.com/0242.%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D.html 349. 两个数组的交集 建议本题就开始考虑 什么时候用set 什么时候用数组本题其实是使用set的好题但是后来力扣改了题目描述和 测试用例添加了 0 nums1[i], nums2[i] 1000 条件所以使用数组也可以了不过建议大家忽略这个条件。 尝试去使用set。 题目链接/文章讲解/视频讲解https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html 202. 快乐数 建议这道题目也是set的应用其实和上一题差不多就是 套在快乐数一个壳子 题目链接/文章讲解https://programmercarl.com/0202.%E5%BF%AB%E4%B9%90%E6%95%B0.html 1. 两数之和 建议本题虽然是 力扣第一题但是还是挺难的也是 代码随想录中 数组set之后使用map解决哈希问题的第一题。 建议大家先看视频讲解然后尝试自己写代码在看文章讲解加深印象。 题目链接/文章讲解/视频讲解https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html
目录
0242_有效的字母异位词
0349_两个数组的交集
0202_快乐数
0001_两数之和 0242_有效的字母异位词 int[] record new int[26]; for (int i 0; i s.length(); i) { record[s.charAt(i) - a]; //并不需要记住字符a的ASCII只要求出一个相对数值就可以了 } import java.util.Arrays;class Solution0242 {public boolean isAnagram(String s, String t) {if (s.length() ! t.length()) {return false;}char ss[] s.toCharArray();Arrays.sort(ss);char tt[] s.toCharArray();Arrays.sort(tt);for (int i 0; i ss.length; i) {if (ss[i] ! tt[i]) {return false;}}return true;}/*** 242. 有效的字母异位词 字典解法* 时间复杂度O(mn) 空间复杂度O(1)*/public boolean isAnagram2(String s, String t) {int[] record new int[26];for (int i 0; i s.length(); i) {record[s.charAt(i) - a];//并不需要记住字符a的ASCII只要求出一个相对数值就可以了}for (int i 0; i t.length(); i) {record[t.charAt(i) - a]--;}for (int count : record) {if (count ! 0) {//record数组如果有的元素不为零0说明字符串s和t中一定是谁多了字符或者谁少了字符。return false;}}return true;//record数组所有元素都为零0说明字符串s和t是字母异位词}
}
0349_两个数组的交集 取并集Union将两个集合中的所有元素合并在一起去除重复项。 SetInteger unionSet new HashSet(set1);unionSet.addAll(set2); 取差集Difference从第一个集合中移除与第二个集合相同的元素。 SetInteger differenceSet new HashSet(set1);differenceSet.removeAll(set2); 取交集Intersection仅保留两个集合中共同存在的元素。 SetInteger intersectionSet new HashSet(set1);intersectionSet.retainAll(set2); 将结果集合转为数组 int res[] set.stream().mapToInt(x - x).toArray();int res[] list.stream().mapToInt(Integer::intValue).toArray(); class Solution0349 {public int[] intersection1(int[] nums1, int[] nums2) {SetInteger set1 new HashSet();SetInteger set2 new HashSet();for (Integer i : nums1) {set1.add(i);}for (Integer i : nums2) {set2.add(i);}set1.retainAll(set2);int[] res new int[set1.size()];int index 0;for (Integer i : set1) {res[index] i;}return res;}public int[] intersection2(int[] nums1, int[] nums2) {HashSetInteger hashSet1 new HashSet();for (int i 0; i nums1.length; i) {hashSet1.add(nums1[i]);}HashSetInteger hashSet2 new HashSet();for (int i 0; i nums2.length; i) {hashSet2.add(nums2[i]);}ArrayListInteger list new ArrayList();for (int x : hashSet1) {for (int y : hashSet2) {if (x y) {list.add(x);}}}int res[] list.stream().mapToInt(Integer::intValue).toArray();return res;}
}
class Solution0349_2 {//版本一使用HashSetpublic int[] intersection(int[] nums1, int[] nums2) {if (nums1 null || nums1.length 0 || nums2 null || nums2.length 0) {return new int[0];}SetInteger set1 new HashSet();SetInteger resSet new HashSet();//遍历数组1for (int i : nums1) {set1.add(i);}//遍历数组2的过程中判断哈希表中是否存在该元素for (int i : nums2) {if (set1.contains(i)) {resSet.add(i);}}//方法1将结果集合转为数组return resSet.stream().mapToInt(x - x).toArray();//方法2另外申请一个数组存放setRes中的元素,最后返回数组int[] arr new int[resSet.size()];int j 0;for (int i : resSet) {arr[j] i;}return arr;}//版本二使用Hash数组public int[] intersection2(int[] nums1, int[] nums2) {int[] hash1 new int[1002];int[] hash2 new int[1002];for (int i : nums1)hash1[i];for (int i : nums2)hash2[i];ListInteger resList new ArrayList();for (int i 0; i 1002; i)if (hash1[i] 0 hash2[i] 0)resList.add(i);int index 0;int res[] new int[resList.size()];for (int i : resList)res[index] i;return res;}
}
0202_快乐数 while ((n execute(n)) ! 1) {...} import java.util.HashSet;
import java.util.Set;class Solution0202 {public boolean isHappy(int n) {int index 0;while (index 1000) {if (execute(n) 1) {return true;}n execute(n);}return false;}private int execute(int n) {int sum 0;while (n ! 0) {sum (n % 10) * (n % 10);n / 10;}return sum;}
}class Solution0202_2 {public boolean isHappy(int n) {int flag 0;while (execute(n) ! 1) {//n % 10 ! n//System.out.println(n n);n execute(n);flag;if (flag 100000) {return false;}}return true;}public int execute(int n) {int len (n ).length();int sum 0;while (len-- 0) {sum (n % 10) * (n % 10);n / 10;}//System.out.println(sum sum);return sum;}
}class Solution0202_3 {public boolean isHappy(int n) {int flag 0;while ((n execute(n)) ! 1) {flag;if (flag 100000) {return false;}}return true;}public int execute(int n) {int len (n ).length();int sum 0;while (len-- 0) {sum (n % 10) * (n % 10);n / 10;}return sum;}
}class Solution0202_4 {public boolean isHappy(int n) {SetInteger record new HashSet();while (n ! 1 !record.contains(n)) {record.add(n);n getNextNumber(n);}return n 1;}private int getNextNumber(int n) {int res 0;while (n 0) {int temp n % 10;res temp * temp;n n / 10;}return res;}
}
0001_两数之和 本题其实有四个重点 为什么会想到用哈希表哈希表为什么用map本题map是用来存什么的map中的key和value用来存什么的 把这四点想清楚了本题才算是理解透彻了。 System.arraycopy() 是 Java 中用于数组复制的方法。它允许你从一个源数组复制一个指定范围的元素到目标数组的指定位置上。 方法签名如下所示 public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length) 参数解释 src源数组。srcPos源数组中的起始位置。dest目标数组。destPos目标数组中的起始位置。length要复制的元素数量。 这个方法会将源数组 src 中从 srcPos 开始的 length 个元素复制到目标数组 dest 中从 destPos 开始的位置开始存放。源数组和目标数组可以是同一个数组但是复制的范围不可以重叠。 以下是一个示例用法 int[] sourceArray {1, 2, 3, 4, 5};
int[] destinationArray new int[5];// 将源数组 sourceArray 的前三个元素复制到目标数组 destinationArray 中
System.arraycopy(sourceArray, 0, destinationArray, 0, 3);// 输出目标数组的内容
for (int i : destinationArray) {System.out.println(i); // 输出1, 2, 3, 0, 0
} 这个例子将 sourceArray 中的前三个元素复制到 destinationArray 的起始位置所以 destinationArray 中的前三个位置变成了 sourceArray 中的元素。 import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;class Solution {public int[] twoSum(int[] nums, int target) {int[] index new int[2];for (int i 0; i nums.length; i) {for (int j 0; j nums.length; j) {if (nums[i] nums[j] target i ! j) {index[0] i;index[1] j;return index;}}}return index;}public int[] twoSum2(int[] nums, int target) {for (int i 0; i nums.length; i) {for (int j 0; j nums.length; j) {if (nums[i] nums[j] target i ! j) {//System.out.println(i j);return new int[]{i, j};}}}return new int[]{0, 1};}//使用哈希表public int[] twoSum3(int[] nums, int target) {int[] res new int[2];if (nums null || nums.length 0) {return res;}MapInteger, Integer map new HashMap();for (int i 0; i nums.length; i) {int temp target - nums[i];//遍历当前元素并在map中寻找是否有匹配的keyif (map.containsKey(temp)) {res[1] i;res[0] map.get(temp);break;}map.put(nums[i], i);//如果没找到匹配对就把访问过的元素和下标加入到map中}return res;}//使用双指针public int[] twoSum4(int[] nums, int target) {int m 0, n 0, k, board 0;int[] res new int[2];int[] tmp1 new int[nums.length];//备份原本下标的nums数组System.arraycopy(nums, 0, tmp1, 0, nums.length);//将nums排序Arrays.sort(nums);//双指针for (int i 0, j nums.length - 1; i j; ) {if (nums[i] nums[j] target)i;else if (nums[i] nums[j] target)j--;else if (nums[i] nums[j] target) {m i;n j;break;}}//找到nums[m]在tmp1数组中的下标for (k 0; k nums.length; k) {if (tmp1[k] nums[m]) {res[0] k;break;}}//找到nums[n]在tmp1数组中的下标for (int i 0; i nums.length; i) {if (tmp1[i] nums[n] i ! k)res[1] i;}return res;}
}
