当前位置: 首页> 房产> 家装 > 彭阳门户网站建设_什么是电子商务网站推广_百度竞价排名平台_域名停靠网页推广大全2023

彭阳门户网站建设_什么是电子商务网站推广_百度竞价排名平台_域名停靠网页推广大全2023

时间:2025/7/12 3:17:26来源:https://blog.csdn.net/Triple_3/article/details/145052253 浏览次数:0次
彭阳门户网站建设_什么是电子商务网站推广_百度竞价排名平台_域名停靠网页推广大全2023

哈希基础

  • 当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希。
  • 为了保证映射出来的索引数值都落在哈希表上,我们会在再次对数值做一个取模的操作。
  • 一般哈希碰撞有两种解决方法, 拉链法和线性探测法。
    拉链法:发生冲突的元素都被存储在链表中。
    线性探测法:使用线性探测法,一定要保证tableSize大于dataSize。冲突的位置,放了A,那么就向下找一个空位放置B。
  • 常见的三种哈希结构:
    数组:哈希的值比较小,范围也比较小,范围可控。空间有限。
    set(集合):哈希的值很大。空间无限,但是没法保存多余的信息。
    map(映射):k-v结构。空间无限,但是很占内存,效率比前两个都低。

1. 两数之和

题目讲解:LeetCode
重点:

  1. 用map哈希方便快速查找是否有diff值及diff的索引

思路:

  1. 从头遍历nums数组,一边遍历一边保存数值和索引进map,后面如果遇到差值刚好为前面的数值,则找到结果。

复杂度:

  • N 是元素数量。
  • 时间复杂度:O(N)。对于每一个元素 x,我们可以 O(1) 地寻找 target - x。
  • 空间复杂度:O(N)。主要为哈希表的开销。
public int[] twoSum(int[] nums, int target) {// 重点: 用map保存元素索引HashMap<Integer, Integer> numsMap = new HashMap<>();int[] result = new int[2];for (int i = 0; i < nums.length; i++) {int cur = nums[i];int diff = target - cur;if (numsMap.containsKey(diff)) {result[0] = numsMap.get(diff);result[1] = i;return result;} else {numsMap.put(cur, i);}}return result;
}

49. 字母异位词分组

题目讲解:LeetCode
重点:

  1. 用sort好的String当map的key。

思路:

  1. 遍历strs数组,把每个字符串toCharArray后sort转成String,检查map中是否有相同的String键,如果有加入List,没有则创建List。

复杂度:

  • n 是字符串的数量,k 是字符串的的最大长度。
  • 时间复杂度:需要遍历 n 个字符串,对于每个字符串,需要 O(klogk) 的时间进行排序以及 O(1) 的时间更新哈希表,因此总时间复杂度是 O(nklogk)。
  • 空间复杂度:O(nk)。需要用哈希表存储全部字符串。
public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> hashStrMap = new HashMap<>();for (String str : strs) {// 重点: 字母异位词sort之后肯定一致char[] charArray = str.toCharArray();Arrays.sort(charArray);String key = new String(charArray);List<String> value = hashStrMap.getOrDefault(key, new ArrayList<>());value.add(str);hashStrMap.put(key, value);}return new ArrayList<>(hashStrMap.values());
}

128. 最长连续序列

题目讲解:LeetCode
重点:

  1. 每个数都判断一次这个数是不是连续序列的开头那个数。

思路:

  1. 把nums数组存入Set中自动去重
  2. 遍历Set,判断当前元素是否是连续序列的开头元素,也就是判断Set中是否存在num - 1。如果存在,直接continue。如果不存在,说明是连续序列的开头。不断检测num + 1是否存在于Set中就能计算出该连续元素的长度。最后取最长的长度即可。

复杂度:

  • n 为数组的长度
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)
public int longestConsecutive(int[] nums) {Set<Integer> numsSet = new HashSet<>();for (int num : nums) {numsSet.add(num);}int result = 0;for (int num : numsSet) {// 重点: 判断是否是连续序列的开头元素if (numsSet.contains(num - 1)) {continue;}int cur = num;int curResult = 0;while (numsSet.contains(cur)) {curResult++;cur++;}result = Math.max(curResult, result);}return result;
}
关键字:彭阳门户网站建设_什么是电子商务网站推广_百度竞价排名平台_域名停靠网页推广大全2023

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: