安徽建设银行 招聘网站在线网站模板

当前位置： 首页 > news >正文

安徽建设银行 招聘网站,在线网站模板,网站建设与网页设计从入门到精通 pdf,杭州网站建设招聘数据结构——哈希表相关题目 242. 有效的字母异位词1.暴力解法2.排序后比较3.哈希表 383. 赎金信哈希解法 49. 字母异位词分组438. 找到字符串中所有字母异位词3. 无重复字符的最长子串76. 最小覆盖子串349. 两个数组的交集1.排序双指针2.哈希表 350. 两个数组的交集 II1.排序双… 数据结构——哈希表相关题目 242. 有效的字母异位词1.暴力解法2.排序后比较3.哈希表 383. 赎金信哈希解法 49. 字母异位词分组438. 找到字符串中所有字母异位词3. 无重复字符的最长子串76. 最小覆盖子串349. 两个数组的交集1.排序双指针2.哈希表 350. 两个数组的交集 II1.排序双指针2.哈希表 202. 快乐数1.哈希表2.快慢双指针 1. 两数之和哈希表 454. 四数相加 II哈希表 15. 三数之和哈希解法排序双指针 242. 有效的字母异位词

1. 有效的字母异位词 给定两个字符串 s 和 t 编写一个函数来判断 t 是否是 s 的字母异位词。注意若 s 和 t 中每个字符出现的次数都相同则称 s 和 t 互为字母异位词。 示例 1: 输入: s “anagram”, t “nagaram” 输出: true 示例 2: 输入: s “rat”, t “car” 输出: false 说明: 你可以假设字符串只包含小写字母。 1.暴力解法 两层for循环同时记录字符是否重复出现时间复杂度 O ( n 2 ) O(n^2) O(n2) 2.排序后比较 t 是 s 的异位词等价于「两个字符串排序后相等」。因此我们可以对字符串 s 和 t 分别排序看排序后的字符串是否相等即可判断。此外如果 s 和 t 的长度不同t 必然不是 s 的异位词。 时间复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn) 排序的时间复杂度为 O ( n log ⁡ n ) O(n\log n) O(nlogn)比较两个字符串是否相等时间复杂度为 O ( n ) O(n) O(n) 空间复杂度 O ( log ⁡ n ) O(\log n) O(logn) 排序需要 O ( log ⁡ n ) O(\log n) O(logn) 的空间复杂度 class Solution {public boolean isAnagram(String s, String t) {if (s.length() ! t.length()) {return false;}char[] str1 s.toCharArray();char[] str2 t.toCharArray();Arrays.sort(str1);Arrays.sort(str2);return Arrays.equals(str1, str2);} }3.哈希表 题目中字符串只有小写字符那么就可以定义一个数组来记录字符串s里字符出现的次数 定一个数组record大小为26 初始化为0因为字符a到字符z的ASCII也是26个连续的数值 字符串s “aee”, t “eae” 需要把字符映射到数组也就是哈希表的索引下标上因为字符a到字符z的ASCII是26个连续的数值所以字符a映射为下标0相应的字符z映射为下标25。 再遍历 字符串s的时候只需要将 s[i] - ‘a’ 所在的元素做1 操作即可并不需要记住字符a的ASCII只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数统计出来了。 检查字符串t中是否出现了这些字符同样在遍历字符串t的时候对t中出现的字符映射哈希表索引上的数值再做-1的操作。 最后检查record数组如果有的元素不为零0说明字符串s和t一定是谁多了字符或者谁少了字符return false。 最后如果record数组所有元素都为零0说明字符串s和t是字母异位词return true。 时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1)因为定义是的一个常量大小的辅助数组 class Solution {public boolean isAnagram(String s, String t) {int[] record new int[26];for (char c : s.toCharArray()) {record[c-a];}for (char c : t.toCharArray()) {record[c-a]–;}for (int i : record) {if (i!0)return false;}return true;} }383. 赎金信
2. 赎金信 给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成返回 true 否则返回 false。 (题目说明为了不暴露赎金信字迹要从杂志上搜索各个需要的字母组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。) 注意 你可以假设两个字符串均只含有小写字母。 canConstruct(“a”, “b”) - false canConstruct(“aa”, “ab”) - false canConstruct(“aa”, “aab”) - true 暴力解法两层for循环寻找 哈希解法 本题判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成但是这里需要注意两点。 第一点“为了不暴露赎金信字迹要从杂志上搜索各个需要的字母组成单词来表达意思” 这里说明杂志里面的字母不可重复使用。 第二点 “你可以假设两个字符串均只含有小写字母。” 说明只有小写字母这一点很重要 只有小写字母那可以采用空间换取时间的哈希策略 用一个长度为26的数组还记录magazine里字母出现的次数。 然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。 只需要满足字符串magazine 中的每个英文字母(’a’-’z’) 的统计次数都大于等于 ransomNote 中相同字母的统计次数即可 时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( 1 ) O(1) O(1) class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] record new int[26];for (char c : magazine.toCharArray()) {// 通过recode数据记录 magazine里各个字符出现次数record[c-a];}for (char c : ransomNote.toCharArray()) {// 遍历ransomNote在record里对应的字符个数做–操作record[c-a]–;// 如果小于零说明ransomNote里出现的字符magazine没有if (record[c-a]0) return false;}return true;} }49. 字母异位词分组
3. 字母异位词分组
4. 找到字符串中所有字母异位词
5. 找到字符串中所有字母异位词
6. 无重复字符的最长子串
7. 无重复字符的最长子串
8. 最小覆盖子串
9. 最小覆盖子串
10. 两个数组的交集
11. 两个数组的交集 给定两个数组 nums1 和 nums2 返回它们的交集 。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序 。 1.排序双指针 如果两个数组是有序的则可以使用双指针的方法得到两个数组的交集。 首先对两个数组进行排序然后使用两个指针遍历两个数组。可以预见的是加入答案的数组的元素一定是递增的为了保证加入元素的唯一性我们需要额外记录变量 pre 表示上一次加入答案数组的元素。 初始时两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字如果两个数字不相等则将指向较小数字的指针右移一位如果两个数字相等且该数字不等于 pre 将该数字添加到答案并更新 pre 变量同时将两个指针都右移一位。当至少有一个指针超出数组范围时遍历结束。 时间复杂度 O ( m log ⁡ m n log ⁡ n ) O(m\log m n\log n) O(mlogmnlogn)其中 m 和 n 分别是两个数组的长度 空间复杂度 O ( log ⁡ m log ⁡ n ) O(\log m \log n) O(logmlogn)取决于排序使用的额外空间 class Solution {public int[] intersection(int[] nums1, int[] nums2) {Arrays.sort(nums1);Arrays.sort(nums2);int length1 nums1.length, length2 nums2.length;int[] intersection new int[length1 length2];int index 0, index1 0, index2 0;while (index1 length1 index2 length2) {int num1 nums1[index1], num2 nums2[index2];if (num1 num2) {// 保证加入元素的唯一性if (index 0 || num1 ! intersection[index - 1]) {intersection[index] num1;}index1;index2;} else if (num1 num2) {index1;} else {index2;}}return Arrays.copyOfRange(intersection, 0, index);} }2.哈希表 不需排序不允许重复选用HashSet。 时间复杂度 O ( m n ) O(m n) O(mn)其中 m 和 n 分别是两个数组的长度 空间复杂度 O ( m n ) O( m n) O(mn)取决于两个集合 class Solution {public int[] intersection(int[] nums1, int[] nums2) {if (nums1null||nums2null) {return new int[0];}SetInteger set new HashSet();SetInteger resSet new HashSet();for (int i : nums1) {//遍历数组1set.add(i);}for (int i : nums2) {//遍历数组2判断哈希表中是否存在该元素if (set.contains(i))resSet.add(i);}int[] resArray new int[resSet.size()];int index 0;for (int i : resSet) {//将结果集合转为数组resArray[index] i;}return resArray;} }350. 两个数组的交集 II
12. 两个数组的交集 II 给你两个整数数组 nums1 和 nums2 请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数应与元素在两个数组中都出现的次数一致如果出现次数不一致则考虑取较小值。可以不考虑输出结果的顺序。 1.排序双指针 与上一题类似但不需要保证加入元素的唯一性。 时间复杂度 O ( m log ⁡ m n log ⁡ n ) O(m\log m n\log n) O(mlogmnlogn)其中 m 和 n 分别是两个数组的长度 空间复杂度 O ( m i n ( m , n ) ) O( min(m,n)) O(min(m,n))为返回值创建一个数组 intersection其长度为较短的数组的长度 class Solution {public int[] intersect(int[] nums1, int[] nums2) {Arrays.sort(nums1);Arrays.sort(nums2);int length1 nums1.length, length2 nums2.length;int[] intersection new int[Math.min(length1, length2)];int index1 0, index2 0, index 0;while (index1 length1 index2 length2) {if (nums1[index1] nums2[index2]) {index1;} else if (nums1[index1] nums2[index2]) {index2;} else {intersection[index] nums1[index1];index1;index2;index;}}return Arrays.copyOfRange(intersection, 0, index);} }2.哈希表 由于同一个数字在两个数组中都可能出现多次因此需要用哈希表存储每个数字出现的次数选用HashMap。对于一个数字其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。 为了降低空间复杂度首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数然后遍历较长的数组得到交集 时间复杂度 O ( m n ) O(m n) O(mn)其中 m 和 n 分别是两个数组的长度 空间复杂度 O ( m i n ( m , n ) ) O(min(m,n)) O(min(m,n))对较短的数组进行哈希表的操作哈希表的大小不会超过较短的数组的长度。为返回值创建一个数组 intersection其长度为较短的数组的长度。 class Solution {public int[] intersect(int[] nums1, int[] nums2) {HashMapInteger,Integer hashMap new HashMap();//先把数组nums1元素存入哈希表中for (int i:nums1)hashMap.put(i,hashMap.getOrDefault(i,0)1);//值为对应元素在nums1中出现的次数int[] ans new int[Math.min(nums1.length, nums2.length)];int index 0;for (int i 0; i nums2.length; i) {if (hashMap.containsKey(nums2[i]) hashMap.getOrDefault(nums2[i],0) 0){//nums2[i]存于哈希表且哈希表中该元素数量不为0ans[index] nums2[i];hashMap.put(nums2[i],hashMap.get(nums2[i])-1);}}return Arrays.copyOf(ans,index);} }或不创建新数组直接用nums1返回 class Solution {public int[] intersect(int[] nums1, int[] nums2) {MapInteger,Integer map new HashMap();for (int i : nums1) {map.put(i,map.getOrDefault(i,0) 1);}int index 0;for (int j : nums2) {if (map.containsKey(j)){nums1[index] j;Integer count map.get(j);if (count 1){map.remove(j);}else {map.put(j,–count);}} }return Arrays.copyOfRange(nums1,0,index);} }进阶 如果 nums2 的元素存储在磁盘上内存是有限的并且你不能一次加载所有的元素到内存中你该怎么办 如果 nums2的元素存储在磁盘上磁盘内存是有限的并且你不能一次加载所有的元素到内存中。那么就无法高效地对 nums2进行排序因此推荐使用HashMap而不是排序双指针。在方法2中nums2只关系到查询操作因此每次读取 nums2中的一部分数据并进行处理即可。
13. 快乐数
14. 快乐数 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」定义为对于一个正整数每一次将该数替换为它每个位置上的数字的平方和然后重复这个过程直到这个数变为 1也可能是无限循环 但始终变不到 1。如果 可以变为 1那么这个数就是快乐数。 如果 n 是快乐数就返回 True 不是则返回 False 。 示例 输入19 输出true 解释 1^2 9^2 82 8^2 2^2 68 6^2 8^2 100 1^2 0^2 0^2 1 1.哈希表 可能出现无限循环也就是说求和的过程中sum会重复出现 使用哈希法选用HashSet来判断这个sum是否重复出现如果重复了就是return false 否则一直找到sum为1为止 时间复杂度 O ( log ⁡ n ) O(\log n) O(logn) 空间复杂度 O ( log ⁡ n ) O(\log n) O(logn) 与时间复杂度密切相关的是衡量我们放入哈希集合中的数字以及它们有多大的指标。对于足够大的 n大部分空间将由 n 本身占用。我们可以很容易地优化到 O(243⋅3)O(1)方法是只保存集合中小于 243 的数字因为对于较高的数字无论如何都不可能返回到它们。 class Solution {public boolean isHappy(int n) {SetInteger set new HashSet();while (n!1!set.contains(n)) {set.add(n);n getSum(n);}//1是快乐数否则n重复无限循环falsereturn n1;}int getSum(int n) {int sum 0;while (n!0) {int temp n%10;sum temp*temp;n / 10;}return sum;} }2.快慢双指针 通过反复调用 getNext(n) 得到的链是一个隐式的链表。隐式意味着我们没有实际的链表节点和指针但数据仍然形成链表结构。起始数字是链表的头 “节点”链中的所有其他数字都是节点。next 指针是通过调用 getNext(n) 函数获得。 意识到我们实际有个链表那么这个问题就可以转换为检测一个链表是否有环如果重复了成环就是return false 否则一直找到元素为1为止。 由快慢指针跟踪链表中的两个值。在算法的每一步中慢指针在链表中前进 1 个节点快指针前进 2 个节点对 getNext(n) 函数的嵌套调用。 如果 n 是一个快乐数即没有循环那么快指针最终会比慢指针先到达数字 1。 如果 n 不是一个快乐数那么最终快指针和慢指针将在同一个数字上相遇。快指针超过慢指针一圈
    时间复杂度 O ( log ⁡ n ) O(\log n) O(logn) 时间复杂度 O ( 1 ) O(1) O(1) class Solution {public boolean isHappy(int n) {int slow n;int fast getNext(n);while (fast!1slow!fast) {slow getNext(slow);fast getNext(getNext(fast));}return fast1;}int getNext(int n) {int sum 0;while (n!0) {int temp n%10;sum temp*temp;n / 10;}return sum;} }1. 两数之和
15. 两数之和 给定一个整数数组 nums 和一个目标值 target请你在该数组中找出和为目标值的那 两个 整数并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是数组中同一个元素不能使用两遍。 示例: 给定 nums [2, 7, 11, 15], target 9 因为 nums[0] nums[1] 2 7 9 所以返回 [0, 1] 暴力解法两层for循环 O ( n 2 ) O(n^2) O(n2) 两数之和 不能使用双指针法因为两数之和要求返回的是索引下标 而双指针法一定要排序原数组是无序的一旦排序之后原数组的索引就被改变了。 如果两数之和要求返回的是数值的话就可以使用双指针法了。 数组无序时考虑排序双指针或使用哈希表HashMap / HashSet 也可以帮助我们处理无序数组相关的简单问。、
    哈希表 使用数组和set来做哈希法的局限 数组的大小是受限制的而且如果元素很少而哈希值太大会造成内存空间的浪费。set是一个集合里面放的元素只能是一个key而两数之和这道题目不仅要判断y是否存在而且还要记录y的下标位置因为要返回x 和 y的下标。所以set 也不能用。 此时就要选择另一种数据结构Map map是一种key-value的存储结构可以用key保存数值用value在保存数值所在的下标。 寻找target-nums[i]的值是否在map的key中找到则将该值和 i 一起存入数组中 时间复杂度 O ( n ) O(n) O(n) 空间复杂度 O ( n ) O(n) O(n) class Solution {public int[] twoSum(int[] nums, int target) {int[] res new int[2];if (numsnull||nums.length0) return res;MapInteger,Integer map new HashMap();for (int i0;inums.length;i) {int temp target-nums[i];if (map.containsKey(temp)) {res[1] i;res[0] map.get(temp);}map.put(nums[i],i);}return res;} }170两数之和III
16. 四数相加 II
17. 四数相加 II 给定四个包含整数的数组列表 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 。 例如: 输入: A [ 1, 2] B [-2,-1] C [-1, 2] D [ 0, 2] 输出: 2 解释: 两个元组如下: 1、(0, 0, 0, 1) - A[0] B[0] C[0] D[1] 1 (-2) (-1) 2 0 2、(1, 1, 0, 0) - A[1] B[1] C[0] D[0] 2 (-1) (-1) 0 0 哈希表 这道题目是四个独立的数组只要找到A[i] B[j] C[k] D[l] 0就可以不用考虑有重复的四个元素相加等于0的情况所以相对于题目18. 四数之和题目15.三数之和还是简单了不少 首先定义 一个HashMapkey放a和b两数之和value放a和b两数之和出现的次数。遍历大A和大B数组统计两个数组元素之和和出现的次数放到map中。定义int变量count用来统计 abcd 0 出现的次数。在遍历大C和大D数组找到如果 0-(cd) 在map中出现过的话就用count把map中key对应的value也就是出现次数统计出来。最后返回统计值 count 就可以了 时间复杂度 O ( n 2 ) O(n^2) O(n2) 空间复杂度 O ( n 2 ) O(n^2) O(n2)哈希映射需要使用的空间。在最坏的情况下A[i]B[j] 的值均不相同因此值的个数为 n^2 class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {MapInteger,Integer map new HashMap();int temp,res 0;//统计两个数组中的元素之和同时统计出现的次数放入mapfor (int i : nums1) {for (int j : nums2) {temp ij;if (map.containsKey(temp)) {map.put(temp,map.get(temp)1);} else {map.put(temp,1);}}}//统计剩余的两个元素的和在map中找是否存在相加为0的情况同时记录次数for (int i :nums3) {for (int j : nums4) {temp ij;if (map.containsKey(-temp)) {res map.get(-temp);}}}return res;} }15. 三数之和
18. 三数之和 给你一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 abc 使得 a b c 0 请你找出所有满足条件且不重复的三元组。 注意 答案中不可以包含重复的三元组。 示例 给定数组 nums [-1, 0, 1, 2, -1, -4] 满足要求的三元组集合为 [ [-1, 0, 1], [-1, -1, 2] ] 哈希解法 这道题目使用哈希法并不十分合适 两层for循环就可以确定 a 和b 的数值了可以使用哈希法来确定 0-(ab) 是否在 数组里出现过思路是正确的但是注意不可以包含重复的三元组。 把符合条件的三元组放进vector中然后再去重这样是非常费时的很容易超时。去重的过程不好处理。时间复杂度可以做到 O ( n 2 ) O(n^2) O(n2)但还是比较费时的因为不好做剪枝操作。 排序双指针 首先将数组排序然后有一层for循环i从下标0的地方开始同时定一个下标left 定义在i1的位置上定义下标right 在数组结尾的位置上。 依然还是在数组中找到 abc 使得a b c 0我们这里相当于 a nums[i]、 b nums[left] 、c nums[right]。 如果nums[i] nums[left] nums[right] 0 就说明 此时三数之和大了因为数组是排序后了所以right下标就应该向左移动这样才能让三数之和小一些。如果 nums[i] nums[left] nums[right] 0 说明 此时 三数之和小了left 就向右移动才能让三数之和大一些直到left与right相遇为止。 时间复杂度 O ( n 2 ) O(n^2) O(n2) class Solution {public ListListInteger threeSum(int[] nums) {ListListInteger res new ArrayList();Arrays.sort(nums);for (int i0;inums.length;i) {//排序之后若第一个元素已经大于零无论如何组合都不可能凑成三元组if (nums[i]0) {return res;}// 错误去重方法将会漏掉-1,-1,2 这种情况/if (nums[i] nums[i 1]) {continue;}/if (i0nums[i]nums[i-1]) {//正确去重continue;}int left i1;int right nums.length-1;while (rightleft) {//去重复逻辑如果放在这里000 的情况可能直接导致 rightleftint sum nums[i]nums[left]nums[right];if (sum0) {right–;}else if (sum0){left;}else {res.add(Arrays.asList(nums[i],nums[left],nums[right]));// 去重逻辑应该放在找到一个三元组之后while(rightleftnums[right]nums[right-1]) right–;while(rightleftnums[left]nums[left1]) left;//找到答案时双指针同时收缩left;right–;}}}return res;} }