Java算法OJ（10）哈希表练习
目录
1.前言
哈喽大家好吖，今天来分享几道哈希表相关的练习题，操作比较基础但是思想比较重要，另外有许多思路与解法都是学习参照题解中诸位大佬的做法，都很有思路对我们很有启发性，欢迎大家在评论区多多交流，废话不多说让我们直接开始吧。
2.正文
2.1俩数之和
提交链接：
https://leetcode.cn/problems/two-sum/description/?envType=problem-list-v2&envId=hash-table
这道题当然无脑遍历肯定能直接解出来，但既然要锻炼哈希表的熟练程度就用HashSet来完成：
- 先初始化该哈希表。
- 遍历，如果存在一个数组的数，满足目标值减去当下遍历到的这个数，那么存在解。
- 如果遍历到最后都没有返回，那么无解。
class Solution {
public int[] twoSum(int[] nums, int target) {
Map <Integer,Integer>hashMap = new HashMap<>();
for(int i = 0;i < nums.length;i++){
if(hashMap.containsKey(target - nums[i])){
return new int[]{hashMap.get(target - nums[i]),i};
}
hashMap.put(nums[i],i);
}
return new int[0];
}
}
时间复杂度：
- 遍历数组只需 O(n)O(n)O(n)。
- 哈希表的插入和查找操作平均时间复杂度是 O(1)O(1)O(1)。
- 总体时间复杂度：O(n)O(n)O(n)。
空间复杂度：
- 额外使用了一个哈希表存储数组中的元素和索引，最坏情况下需要存储 nnn 个元素。
- 空间复杂度：O(n)O(n)O(n)。
2.2无重复字符的最长子串
这道题运用了滑动窗口的思想，即有俩个左右指针通过移动，记录答案后找到满足题意的解。
窗口的定义：
- 滑动窗口是字符串的一个子串，窗口的两端由两个指针（
i和right）表示。- 窗口的内容始终保持无重复字符。
双指针移动规则：
- 右指针
right：用于扩展窗口，表示当前扫描到的位置。- 左指针
i：用于收缩窗口，解决窗口内出现重复字符的问题。用数据结构维护窗口状态：
- 使用一个
HashSet（或哈希表）存储窗口内的字符，快速判断窗口中是否已经包含某个字符。过程描述：
- 初始化窗口左右边界（
i和right），以及存储结果的变量（ans）。- 遍历字符串，用右指针逐步扩展窗口；如果窗口内出现重复字符，用左指针逐步缩小窗口，直到窗口重新无重复。
- 在每一步中，更新窗口的长度并维护最长子串的长度。
结束条件：
- 当右指针到达字符串末尾时，遍历结束，返回最长子串的长度。
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<Character>();
int right = 0;
int ans = 0;
for(int i = 0;i < s.length();i++){
if(i != 0){
set.remove(s.charAt(i - 1));//左指针
}
while(right < s.length() && !set.contains(s.charAt(right))){
set.add(s.charAt(right));
right++;
}
ans = Math.max(ans,(right - i));
}
return ans;
}
}
时间复杂度：
- 每个字符至多被访问两次（一次被左指针移除，一次被右指针添加）。
- 总时间复杂度为 O(n)O(n)O(n)。
空间复杂度：
- 使用了
HashSet存储字符，空间复杂度为 O(k)O(k)O(k)。
2.3罗马数字转整数
思路如下：
首先我们先认真读题，理解罗马数字的一些规则。
- 罗马数字使用字符表示数值：
I=1,V=5,X=10,L=50,C=100,D=500,M=1000。- 大部分情况下，罗马数字字符按照从左到右从大到小排列，并直接相加。
- 如：
VII = 5 + 1 + 1 = 7- 但在特定情况下，较小值的字符出现在较大值字符的左边时，表示减法。
- 如：
IV = 5 - 1 = 4，IX = 10 - 1 = 9。算法设计：
- 利用一个哈希表（
HashMap）存储罗马字符和整数值之间的映射关系。- 遍历字符串，每次提取当前字符的值，并判断是否需要减去还是加上该值。
- 如果当前字符的值小于下一个字符的值（
value < next_value），说明需要减去当前值。- 否则，将当前值加到结果中。
算法实现步骤
- 初始化映射表：将每个罗马字符对应的值存入一个哈希表中，便于快速查找。
- 遍历字符串：
- 当前字符值（
value）与下一个字符值（next_value）进行比较：
- 如果
value < next_value，结果减去当前值；- 否则，结果加上当前值。
- 循环直到字符串结束。
- 返回结果：遍历完成后，累积的结果即为整数值。
class Solution {
public int romanToInt(String s) {
Map<Character, Integer> map = new HashMap<Character, Integer>() {{
put('I', 1);
put('V', 5);
put('X', 10);
put('L', 50);
put('C', 100);
put('D', 500);
put('M', 1000);
}};
int ans = 0;
int n = s.length();
for(int i = 0;i < s.length();i++){
int value = map.get(s.charAt(i));
if(i < n - 1 && value < map.get(s.charAt(i + 1))){
ans -= value;
}
else {
ans += value;
}
}
return ans;
}
}
- 时间复杂度：O(n)O(n)O(n)，其中 nnn 是罗马数字字符串的长度，每个字符只访问一次。
- 空间复杂度：O(1)O(1)O(1)，哈希表的大小是固定的，与输入规模无关。
2.4整数转罗马数字
这道题比较关键的是把这个哈希表建立出来，题目中给的并不够，只罗列出关键的 7 种数字字符，加上 6 种特殊数字所对应的罗马数字，就足够了：
建立映射关系：
- 使用两个数组
values和symbols分别存储数值与对应的罗马符号，并按照数值从大到小排列。遍历处理：
- 从高到低依次处理每一个罗马数字的数值和符号。
- 如果当前数值可以被整数
num包含，减去该值，并将对应的罗马符号添加到结果字符串中。- 重复处理当前符号，直到
num小于该数值。提前结束：
- 如果整数
num减为 0，则提前退出循环以优化效率。返回结果：
- 最终拼接完成后返回结果字符串。
class Solution {
// 定义数值与罗马数字的对应关系
int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
public String intToRoman(int num) {
StringBuilder roman = new StringBuilder(); // 使用 StringBuilder 拼接字符串
for (int i = 0; i < values.length; ++i) {
while (num >= values[i]) {
num -= values[i]; // 减去当前数值
roman.append(symbols[i]); // 添加对应的罗马符号
}
if (num == 0) break; // 如果数字为 0，提前退出循环
}
return roman.toString(); // 返回最终罗马数字
}
}
时间复杂度：O(1)O(1)O(1)
罗马数字的种类和数量是固定的，因此算法的循环次数是常数，与输入大小无关。空间复杂度：O(1)O(1)O(1)
除了固定大小的数组和结果字符串外，额外的空间使用量与输入无关。
3.小结
今天的分享到这里就结束了，喜欢的小伙伴不要忘记点点赞点个关注，你的鼓励就是对我最大的支持，加油！
原文地址：https://blog.csdn.net/2301_81073317/article/details/144010792
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！