有经验的武进网站建设,高端品牌衣服,免费数据网站,wordpress dux1.4自适应哈希模块 哈希结构#xff1a; 哈希结构#xff0c;即hash table#xff0c;哈希表|散列表结构。 图摘自《代码随想录》 哈希表本质上表示的元素和索引的一种映射关系。 若查找某个数组中第n个元素#xff0c;有两种方法#xff1a; 1.从头遍历#xff0c;复杂度#xf…哈希模块 哈希结构 哈希结构即hash table哈希表|散列表结构。 图摘自《代码随想录》 哈希表本质上表示的元素和索引的一种映射关系。 若查找某个数组中第n个元素有两种方法 1.从头遍历复杂度O(n) 2.使用数组这种hash结构根据下标(索引)来查找复杂度O(1) 实现了快速判断元素是否出现在集合里。 哈希函数 哈希函数指根据映射关系构造hash表的方法 哈希碰撞 当根据映射方法进行映射构造hash表时出现两个元素抢占一个索引的现象叫做hash碰撞。 如hash函数 index(value%3) 则0和3所得索引都是0抢占同一索引0发生hash碰撞。 解决hash碰撞的两个方法拉链法和线性探测 拉链法:将冲突的元素串成链表放在被抢占的索引处。 线性探测将一个元素放入该索引顺找该索引往下找一个空位置存放另一个元素。 Leetcode 1. 两数之和 题意理解 给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。 给定一个数组和一个目标值target, 求数组中两个数和为target, 这两个数的下标。 解题思路 采用hash结构来解题目的是快速找到某个值 哈希法解题
public int[] twoSum(int[] nums, int target) {MapInteger,Integer numsMapnew HashMap();for(int i0;inums.length;i){if(!numsMap.isEmpty()numsMap.keySet().contains(nums[i])){return new int[]{i,numsMap.get(nums[i])};}numsMap.put(target-nums[i],i);}return null;}
复杂度分析 时间复杂度O(n), 遍历数组的开销 空间复杂度O(n), hash表的开销 Leetcode 49. 字母异位词分组 题意理解 给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 字母异位词本质上是元素一样的数组。 则所有异位字符串通过字母按从小到大的顺序重排得到的值是一样的。我们将其作为索引对应字母异位词本质上是哈希表的拉链法。 解题思路 将异位字符串通过字母按从小到大的顺序重排得到的值作为index 通过map进行收集index和以为字符串的映射关系。 主要是依赖了哈希结构index和value的对应关系。 哈希解题 public ListListString groupAnagrams(String[] strs) {MapString, ArrayListString mapnew HashMap();for(int i0;i strs.length;i){String indexrecombination(strs[i]);if(map.containsKey(index)){map.get(index).add(strs[i]);}else {ArrayListString newListnew ArrayList();newList.add(strs[i]);map.put(index,newList);}}return new ArrayList(map.values());}public String recombination(String str){char[] strArrstr.toCharArray();Arrays.sort(strArr);return String.valueOf(strArr);}
复杂度分析 时间复杂度O(nklogk), 遍历元素的时间n每个元素排序的世家klogk 空间复杂度O(nk), 字符数组的大小 n是元素个数k是字符串字母个数 Leetcode 128. 最长连续序列 题意理解 给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 即使用nums中的元素排序的话能够连续的最长序列是多少呢。 这里的要求是时间复杂度O(n) 尝试使用hash的方法来解题。 解题思路 hash解题的主要问题是如何构造索引和值的映射。 这里我们将最长序列的长度作为值。而index为当前元素。 1首先对数组进行重。set 2 在set中找一个序列的下界 nums[i] 且set不包含nums[i]-1 (3) 遍历长度。length (4)用result记录最长的长度 哈希解题
public int longestConsecutive(int[] nums) {int result0;SetInteger set new HashSet();for(int i0;i nums.length;i) set.add(nums[i]);for(int num:set){if(!set.contains(num-1)){int length0;while(set.contains(num)){length;num;}resultMath.max(result,length);}}return result;}
复杂度分析 时间复杂度O(n)所有元素仅遍历一遍 空间复杂度O(n)set的空间损耗 双指针模块 双指针 在遍历一个数组遍历过程中定义两个指针可以表示为快指针和慢指针、或左指针和右指针。 双指针法快慢指针法在数组和链表的操作中是非常常见的很多考察数组、链表、字符串等操作的面试题都使用双指针法。 摘自《代码随想录》 Leetcode 283. 移动零 题意理解 给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。请注意 必须在不复制数组的情况下原地对数组进行操作。 这道题目要求在不复制数组的情况下原地操作使所有的0移到数组末尾。 这里采用双指针来解决这道题目 解题思路 这里使用两个指针慢指针i用于寻找元素0快指针用于寻找0后的第一个非0元素 不断将非零元素和零元素进行互换将0元素全部移至数组末尾 特别的对于j的约束 j要小于等于nums.length,若j后续没有找到合适的非0元素则结束不操作。 双指针解题
public void moveZeroes(int[] nums) {for(int i0;inums.length;i){if(nums[i]0){//找到0元素时//查找后续非0元素j的指示int ji;while(jnums.lengthnums[j]0) j;//找到后续非0元素互换if(j nums.length){int tempnums[i];nums[i]nums[j];nums[j]temp;}else{//末尾无非0元素。inums.length;}}}}
复杂度分析 时间复杂度O(n) , 所有元素遍历一遍的时间复杂度 空间复杂度O(1) 在原数组操作仅有temp的空间消耗所以是O(1) Leetcode 11. 盛最多水的容器 题意理解 给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 这道题目要求求容器可以存储的最大水量储水量h*w 其中使用双指针来i指示左边界j指示右边界。 hmin(height[i],height[j]) wj-i 解题思路 选中一个左边界一个右边界计算S 保留尽可能高的边界以备更多的储水量所以对于两个边界中较矮的边界进行移动以期待获取一个比当前边界更大的边界。 初始化i0,jnums[len-1] 计算S 当height[i]height[j]时i; 否则j--,始终保持ij 计算所有可能的S使用maxS返回最大储水量。 双指针解题
public int maxArea(int[] height) {int i0,jheight.length-1,maxS0;while(ij){int SMath.min(height[i],height[j])*(j-i);maxSMath.max(maxS,S);if(height[i]height[j]){i;}else{j--;}}return maxS;}
复杂度分析 时间复杂度O(n), 所有元素遍历一遍的时间损耗 空间复杂度O(1)maxS的空间损耗 Leetcode 15. 三数之和 题意理解 给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意答案中不可以包含重复的三元组。 数组中取三个数使其和0每个元素每次只能去一次可以有多少种组合。 这里求的是组合数与顺序无关。 我们采用双指针方式来解题。 解题思路 首先对数组进行排序。 其中我们选中一个元素nums[i] 以i1为左边界leftlen-1为右边界right 查找符合规范的二元组找到则加入结果集。 特别的对于去重操作 已知数组有序且i确定的情况下nums[left]不取重left; nums[right]不取重right 对于nums[i]nums[i1]的情况下nums[i]已经包含了nums[i1]的方式所以nums[i1]时continue 1.双指针解题
public ListListInteger threeSum(int[] nums) {Arrays.sort(nums);ListListInteger resultnew ArrayList();for(int i0;i nums.length-1;i){if(i0nums[i]nums[i-1]) continue;int lefti1;int right nums.length-1;while(leftright){if(nums[i]nums[left]nums[right]0) right--;else if (nums[i]nums[left]nums[right]0) left;else {//去重result.add(Arrays.asList(nums[i],nums[left],nums[right]));while(leftrightnums[left1]nums[left]) left;while(leftrightnums[right-1]nums[right]) right--;left;right--;}}}return result;}
2.复杂度分析 时间复杂度O(n^2),遍历i的时间损耗*双指针操作时间损耗 空间复杂度O(n), 结果集存储元素的损耗 Leetcode 42. 接雨水 题意理解 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。 给定一个柱子的高度数组求这些柱子组成的形状中能积的水的量。 每个积水量的涉及Sw*h 其中左边界left,右边界right, 则wright-left-1 hmax(height[left],height[right]) 我们尝试使用双指针的方式解题。 解题思路 选中一个柱子作为左边界右边界为该柱子后第一个比它大的值底初始化为该柱子后第一个比它小的值。 则左边界一定满足height[i]height[i1] 注意特别的如4、2、3左边界高4时右边没有比4高的柱子则选择右边最高的柱子作为右边界。 1.双指针解题 public int trap(int[] height) {int S0;for(int i0;iheight.length-1;i){int bottomi1;if(height[i]height[bottom]){//找左边界只有一高一低才有可能存在储水左边界int ji1;int rightj;//右边最大的值while(jheight.length){//找储水有边界有两种情况 // 左边第一个比左边界大的柱子// 或右边最大的柱子右边没有比左边大的柱子//右边最大值if(height[j]height[right]){rightj;}//右边第一个比它大的值if(height[j]height[i]){rightj;break;}j;}//要使积水则右边界和左边界之间最少有一个位置的空隙保证j合法if(rightheight.lengthj-i1){//有左右边界及底//纵向计算该范围内的储水量while(bottomright){S(Math.min(height[i],height[right])-height[bottom])*1;//一个单位一个单位蓄水量累加bottom;}iright-1;}}}return S;}
2.复杂度分析 时间复杂度O(n^2) 空间复杂度O(1)
