抚宁建设局网站,怎样做电影下载网站,dede做购物网站,网站策划要遵循的原则哈希表算法章节
(1)
Ascall码文章推荐 给定两个字符串 s 和 t #xff0c;编写一个函数来判断 t 是否是 s 的字母异位词。注意#xff1a;若 s 和 t 中每个字符出现的次数都相同#xff0c;则称 s 和 t 互为字母异位词。 class Solution {public boolean isAnagram(String…哈希表算法章节
(1)
Ascall码文章推荐 给定两个字符串 s 和 t 编写一个函数来判断 t 是否是 s 的字母异位词。注意若 s 和 t 中每个字符出现的次数都相同则称 s 和 t 互为字母异位词。 class Solution {public boolean isAnagram(String s, String t) {//先说明一下字母异位词的定义//两个字符串的字母组成完全相同//这里使用哈希法//简单创建一个哈希数组int[] hashint hash[] new int[26];//默认初始化都为0//因为表示26个小写字母a到z//a-a0存储在hash[0], b-a1存储在hash[1]以此类推//开始分别遍历两个字符串for(int i0;is.length();i){hash[s.charAt(i)-a];}for(int j0;jt.length();j){hash[t.charAt(j)-a]--;}//检查hash数组中是否有不为0的元素for(int i0;ihash.length;i){if(hash[i]!0){return false;}}return true;}
}(2)
当我们需要存储一组元素并且要求元素不重复时可以使用Set集合。
Set是Java中的一个接口它的实现类有HashSet、TreeSet和LinkedHashSet。 HashSet使用哈希表实现不保证元素的顺序是最常用的Set实现类。TreeSet使用红黑树实现可以对元素进行排序但插入和查找操作的时间复杂度较高。LinkedHashSet使用链表和哈希表实现保证元素的插入顺序。 当我们向Set集合中添加元素时Set会根据元素的hashCode值来判断是否已存在相同的元素。 如果两个元素的hashCode值相等Set会调用它们的equals方法进行进一步比较。
具体步骤如下
创建两个Set集合分别用来存储两个数组的元素。遍历第一个数组将每个元素添加到第一个Set集合中。遍历第二个数组对于每个元素判断是否存在于第一个Set集合中。如果存在则将该元素添加到结果集合中。最后将结果集合转换为整数数组并返回。
class Solution {public int[] intersection(int[] nums1, int[] nums2) {// 创建两个Set集合用于存储数组元素SetInteger set1 new HashSet();SetInteger resultSet new HashSet();// 将nums1数组的元素添加到set1集合中for (int num : nums1) {set1.add(num);}// 遍历nums2数组判断元素是否存在于set1集合中for (int num : nums2) {if (set1.contains(num)) {resultSet.add(num);}}// 将结果集合转换为整数数组int[] resultArray new int[resultSet.size()];int index 0;for (int num : resultSet) {resultArray[index] num;index;}return resultArray;}
}3双指针法——快乐数
编写一个算法来判断一个数 n 是不是快乐数。「快乐数」定义为对于一个正整数每一次将该数替换为它每个位置上的数字的平方和然后重复这个过程直到这个数变为 1也可能是 无限循环但始终变不到 1。如果 可以变为 1那么这个数就是快乐数。如果 n 是快乐数就返回 True 不是则返回 False 。 解释一下快乐数 不是所有的正整数都会进入循环。事实上只有一部分正整数会进入循环而另一部分正整数最终会收敛到1。对于那些会进入循环的正整数它们的平方和计算过程会在某个特定的数值上循环而不是收敛到1。这些数被称为“不快乐数”。例如考虑数字4。计算过程如下4 - 16 - 37 - 58 - 89 - 145 - 42 - 20 - 4。可以看到进入了一个循环。因此4被认为是一个不快乐数因为它最终无法收敛到1。另一方面如果一个正整数最终收敛到1那么它被称为“快乐数”。例如数字19通过计算平方和的过程最终收敛到119 - 82 - 68- 100 - 1。因此19被认为是一个快乐数。 class Solution {public boolean isHappy(int n) {int slow n; // 慢指针从n开始int fast n; // 快指针从n开始do {slow calculateSquareSum(slow); // 慢指针每次计算平方和fast calculateSquareSum(calculateSquareSum(fast)); // 快指针每次计算两次平方和} while (slow ! fast); // 当慢指针和快指针相等时表示进入了循环return slow 1; // 如果最终平方和等于1说明是快乐数}private static int calculateSquareSum(int num) {int sum 0;while (num 0) {int digit num % 10; // 取出个位数sum digit * digit; // 平方和累加num / 10; // 去除个位数}return sum;}}以前觉得算法可无聊了突然发现这玩意挺上瘾啊虽然很菜但很解困啊
4两数之和 题目 给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。 class Solution {public int[] twoSum(int[] nums, int target) {// 创建一个HashMap用于存储数组元素与其下标的映射关系MapInteger, Integer map new HashMap();// 遍历数组for (int i 0; i nums.length; i) {int complement target - nums[i];// 判断当前元素的补数是否已经存在于HashMap中// 如果存在则返回对应的下标if (map.containsKey(complement)) {return new int[] {map.get(complement), i};}// 如果补数不存在于HashMap中则将当前元素与其下标存入HashMapmap.put(nums[i], i);}// 如果未找到符合条件的两个数则返回一个空数组return new int[0];}
}5四数相加 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) 使得 A[i] B[j] C[k] D[l] 0。为了使问题简单化所有的 A, B, C, D 具有相同的长度 N且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间最终结果不会超过 2^31 - 1 。 map.getOrDefault(sum, 0) 1
是Java中的一个表达式用于获取Map中指定键的值如果键不存在则返回默认值。在这个表达式中sum是作为键0是作为默认值。如果sum这个键存在于map中则返回与该键对应的值加1如果sum这个键不存在则返回默认值0加1。
class Solution {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;}
}6三数之和 给你一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 abc 使得 a b c 0请你找出所有满足条件且不重复的三元组。注意 答案中不可以包含重复的三元组。 class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger result new ArrayList();Arrays.sort(nums);for (int i 0; i nums.length - 2; i) {if (i 0 nums[i] nums[i-1]) {continue;}int left i 1;int right nums.length - 1;while (left right) {int sum nums[i] nums[left] nums[right];if (sum 0) {result.add(Arrays.asList(nums[i], nums[left], nums[right]));while (left right nums[left] nums[left1]) {left;}while (left right nums[right] nums[right-1]) {right--;}left;right--;} else if (sum 0) {left;} else {right--;}}}return result;}
}7四数之和 题意给定一个包含 n 个整数的数组 nums 和一个目标值 target判断 nums 中是否存在四个元素 abc 和 d 使得 a b c d 的值与 target 相等找出所有满足条件且不重复的四元组。注意答案中不可以包含重复的四元组。 class Solution {public ListListInteger fourSum(int[] nums, int target) {ListListInteger result new ArrayList();if (nums null || nums.length 4) {return result;}Arrays.sort(nums);for (int i 0; i nums.length - 3; i) {// 避免重复的元素if (i 0 nums[i] nums[i - 1]) {continue;}for (int j i 1; j nums.length - 2; j) {// 避免重复的元素if (j i 1 nums[j] nums[j - 1]) {continue;}int left j 1;int right nums.length - 1;while (left right) {int sum nums[i] nums[j] nums[left] nums[right];if (sum target) {result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));// 避免重复的元素while (left right nums[left] nums[left 1]) {left;}while (left right nums[right] nums[right - 1]) {right--;}left;right--;} else if (sum target) {left;} else {right--;}}}}return result;}
}
