|
Java里使用HashMap类就不戳。
在这之前先回顾一下哈希表：将数据映射到数组中对应的位置。
解决哈希冲突：?
- 线性寻址
- 拉链
?线性寻址就是说如果某个数据经过散列函数以后，它对应的位置已经被占用了，那么就顺着往下找第一个没有被占用的位置存放它。缺点在于删除需要设置一个删除标记位，免得查找出错；冲突过多的时候哈希查找可能会变成跟遍历差不多。
拉链法遍历慢。
JDK1.7解决哈希冲突就是使用的拉链。
JDK1.8以后引入了红黑树，在链表>8时使用红黑树。
然后看几个HashMap提供的方法：
首选引入HashMap
import java.util.HashMap;
创建key类型为char，value类型为int的Hashmap对象：
HashMap<Character,Integer> Sites = new HashMap<Integer, String>();
其他HashMap方法（该表来自菜鸟教程Java HashMap）：?
| 方法 | 描述 | | clear() | 删除 hashMap 中的所有键/值对 | | clone() | 复制一份 hashMap | | isEmpty() | 判断 hashMap 是否为空 | | size() | 计算 hashMap 中键/值对的数量 | | put() | 将键/值对添加到 hashMap 中 | | putAll() | 将所有键/值对添加到 hashMap 中 | | putIfAbsent() | 如果 hashMap 中不存在指定的键，则将指定的键/值对插入到 hashMap 中。 | | remove() | 删除 hashMap 中指定键 key 的映射关系 | | containsKey() | 检查 hashMap 中是否存在指定的 key 对应的映射关系。 | | containsValue() | 检查 hashMap 中是否存在指定的 value 对应的映射关系。 | | replace() | 替换 hashMap 中是指定的 key 对应的 value。 | | replaceAll() | 将 hashMap 中的所有映射关系替换成给定的函数所执行的结果。 | | get() | 获取指定 key 对应对 value | | getOrDefault() | 获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值 | | forEach() | 对 hashMap 中的每个映射执行指定的操作。 | | entrySet() | 返回 hashMap 中所有映射项的集合集合视图。 | | keySet() | 返回 hashMap 中所有 key 组成的集合视图。 | | values() | 返回 hashMap 中存在的所有 value 值。 | | merge() | 添加键值对到 hashMap 中 | | compute() | 对 hashMap 中指定 key 的值进行重新计算 | | computeIfAbsent() | 对 hashMap 中指定 key 的值进行重新计算，如果不存在这个 key，则添加到 hasMap 中 | | computeIfPresent() | 对 hashMap 中指定 key 的值进行重新计算，前提是该 key 存在于 hashMap 中。 |
然后开始刷题！
import java.util.HashMap;
public class Solution {
public int lengthOfLongestSubstring(String s){
if(s.length() == 0){
return 0;
}
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
int max = 0;
int left = 0;
for(int i=0;i<s.length();i++){
if(map.containsKey(s.charAt(i))){
left = Math.max(left,map.get(s.charAt(i)) + 1);
/*
这里我第一次提交的时候直接left = map.get(s.charAt(i)) + 1；
当输入是“abba”时报错；
手算了一下确实……
不对left进行只能增加的限制的话，在放入最后一个a的时候，left直接回到开头了
离大谱，我呆比了
*/
}
map.put(s.charAt(i),i);
max = Math.max(max,i-left+1);
}
return max;
}
}
import javax.swing.text.html.MinimalHTMLWriter;
import java.util.HashMap;
public class Solution {
public static String minWindow(String s, String t) {
HashMap<Character,Integer> maps = new HashMap<Character,Integer>();
HashMap<Character,Integer> mapt = new HashMap<Character,Integer>();
//构造mapt，统计t中出现过的字符key以及出现次数value；构造maps,初始value均为0；
for(int i = 0;i<t.length();i++){
if(mapt.containsKey(t.charAt(i))){
mapt.replace(t.charAt(i), mapt.get(t.charAt(i))+1);
}else{
mapt.put(t.charAt(i),1);
maps.put(t.charAt(i),0);
}
}
//定义left、right指针和暂时最优解templeft=0,tempright=s.length存放左右边界的索引
int left = 0,right = 0;
int templeft = 0,tempright = s.length();
//遍历s，right指针向前移动
while(right<s.length()){
// 当查询到t中字符时，maps中对应字符value值+1
if(mapt.containsKey(s.charAt(right))){
maps.replace(s.charAt(right), maps.get(s.charAt(right))+1);
// 若此时maps中已经没有value为0的key
boolean have0 = find0(maps);
if(have0 == false){
//则将right-left与tempright-templeft对比，更小则替换
// 然后left指针向右移动，查询到t中字符并将value-1
while (left <= right){
if(mapt.containsKey(s.charAt(left))){
if(maps.get(s.charAt(left)) <= mapt.get(s.charAt(left))){
break;
}else{
maps.replace(s.charAt(left), maps.get(s.charAt(left))-1);
left++;
}
}else{
left++;
}
}
if((right-left) < (tempright-templeft)){
templeft = left;
tempright = right;
}
}
right++;
}else{
right++;
}
}
//最终结果是templeft-tempright之间的字段
String res = s.substring(templeft,tempright+1);
return res;
}
//查询maps中是否还有value为0的key
public static boolean find0(HashMap<Character,Integer> map){
return map.containsValue(0);
}
}
上面是我自己写的，写完跑了一下发现报错，然后想起来，哦豁，没考虑s中如果不存在t这样的子串的情况！
然后试改了几版也没成功，按照我这思路好像不太好求不存在的情况，有点太麻烦了。
最后参考了大佬的思路，不愧是大佬，简单明了的思路，实现起来也不复杂
public class Solution {
public static String minWindow(String s, String t) {
if (s == null || s.length() == 0 || t == null || t.length() == 0){
return "";
}
//need记录需要的字符个数，字母转化为ASCII码对应下标
int[] need = new int[128];
for(int i = 0;i < t.length();i++){
need[t.charAt(i)]++;
}
//设置指针left，right，窗口大小size，起始位置begin，总共需要的字符数count
int left = 0,right = 0;
int size = Integer.MAX_VALUE;
int begin = 0;
int count = t.length();
//移动right遍历s
while(right < s.length()){
//如果需要该字符，则count-1，并修改对应need数组
char c = s.charAt(right);
if(need[c] > 0){
count--;
}
need[c]--;
//如果count=0则窗口已经包含所有需要的字符
if(count == 0){
//向前移动left，如果left对应的字符并不是需要的字符，则left继续向前移动并修改对应need数组，释放空间使之+1
while(left < right && need[s.charAt(left)] < 0){
need[s.charAt(left)]++;
left++;
}
//left不能再向前移动时更新窗口大小
if(right - left + 1 < size){
begin = left;
size = right - left + 1;
}
//释放当前left位置的字符空间，并将count+1，重新维护左边界值
need[s.charAt(left)]++;
left++;
count++;
}
//右移right，继续循环
right++;
}
if(size == Integer.MAX_VALUE){
return "";
}else{
return s.substring(begin,begin+size);
}
}
}
|