4.1 哈希表(5)
2017-12-30 本文已影响3人
coderjiege
套路
- 关键字:(不)重复、复制、第一个、只出现一次
- 寻找只出现一次的答案是可以用到哈希表
- LinkedHashMap是有序的hashMap,可以找到第一个出现一次的字符
注意点
- 遍历map时 Map.Entry<> en : map.entrySet()
目录
- 数组中重复的数字
- 复杂链表的复制
- 字符流中第一个不重复的字符
- 数组中只出现一次的数字
- 第一个只出现一次的字符
数组中重复的数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。
- 常规解法:数组中所有数字的值与哈希表下标索引建立关联,出现数组变为1,重复出现(即发现该位置为1),则返回该索引。时间复杂度为 N,空间复杂度为 N
- 最优解法:利用题目中所说在一个长度为n的数组里的所有数字都在0到n-1的范围内,这个数组自身就是一个完美的哈希表。让数组中每个元素不仅包含元素自身,还能够代表当前索引对应的数是否重复即可。时间复杂度为 N,空间复杂度为 O(1)相当于是一个加密解密的过程,一个位置包含两种含义
public boolean duplicate(int numbers[],int length,int [] duplication) {
if (numbers == null || length == 0) {
return false;
}
for (int i = 0; i < length; i++) {
int val = numbers[i] % length;
if (numbers[val] < length) {
numbers[val] += length;
} else {
duplication[0] = val;
return true;
}
}
return false;
}
复杂链表的复制
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
- 最优解:哈希表(hashmap)存放原节点和复杂链表对应新节点的双向key-value值,第一遍遍历填充新链表节点的值和next指针,第二遍遍历填充新链表节点的random指针。
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
public RandomListNode Clone(RandomListNode pHead) {
Map<RandomListNode, RandomListNode> map = new HashMap<>();
// 创建复制链表的额外头结点,方便复制链表所有节点操作的统一处理
RandomListNode cloneFront = new RandomListNode(0);
RandomListNode p1 = pHead, p2 = cloneFront;
while (p1 != null) {
p2.next = new RandomListNode(p1.label);
// 哈希表存放原节点和复制节点的双向键值对
map.put(p2.next, p1);
map.put(p1, p2.next);
p2 = p2.next;
p1 = p1.next;
}
p2 = cloneFront.next;
while (p2 != null) {
p2.random = map.get(map.get(p2).random);
p2 = p2.next;
}
return cloneFront.next;
}
字符流中第一个不重复的字符
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如,当从字符流中只读出前两个字符"go"时,第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时,第一个只出现一次的字符是"l"。
输出描述:
如果当前字符流没有存在出现一次的字符,返回#字符。
- 最优解法:时间复杂度 O(n),空间复杂度 O(n)
// 核心代码:LinkedHashMap 是有序的 hashMap,可以找到出现一次的字符并且满足是第一个出现
private Map<Character, Integer> map = new LinkedHashMap<>();
public void Insert(char ch) {
if (map.containsKey(ch)) {
map.put(ch, 0);
} else {
map.put(ch, 1);
}
}
public char FirstAppearingOnce() {
for (Map.Entry<Character, Integer> en : map.entrySet()) {
if (en.getValue() == 1) {
return en.getKey();
}
}
return '#';
}
数组中只出现一次的数字
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < array.length; i++) {
int t = array[i];
if (map.containsKey(t)) {
map.put(t, 2);
} else {
map.put(t, 1);
}
}
boolean flag = true;
for (Map.Entry<Integer, Integer> en : map.entrySet()) {
if (en.getValue() == 1) {
if (flag) {
num1[0] = en.getKey();
flag = false;
} else {
num2[0] = en.getKey();
}
}
}
}
第一个只出现一次的字符
在一个字符串(1<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置
- 字符串长度可能比较长,所以第一不转字符数组,大数组会占用很多内存空间,第二字符串长度很长时遍历比较费时,所以我们只遍历一次。
public int FirstNotRepeatingChar(String str) {
if (str == null || str.length() == 0) {
return -1;
}
// 能放得下所有大小写字母即可
int[] arr = new int['z' + 1];
for (int i = 0; i < str.length(); i++) {
arr[str.charAt(i)]++;
}
// 存放所有只出现一次的字母在字符串中的索引
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 1) {
res.add(str.indexOf(i));
}
}
int index = 9999;
for (int i = 0; i < res.size(); i++) {
if (res.get(i) < index) {
index = res.get(i);
}
}
return res.size() == 0 ? 0 : index;
}