hashmap算法

034-第一个只出现一次的字符#

1.使用hashmap
2.indexof lastindexof

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public int FirstNotRepeatingChar(String str) {
for (int i = 0; i < str.length(); i++) {
char t = str.charAt(i);
if (str.indexOf(t) == i && str.lastIndexOf(t) == i){
return i;
}
}
return -1;
}
}

03-无重复字符的最长子串 *#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int lengthOfLongestSubstring(String s) {
char[] chars = s.toCharArray();
int len = chars.length;
int left =0, right = 0;
int max = 0;
Integer index;
Map<Character, Integer> indexMap = new HashMap();
for (;right < len;right ++) {
char c = chars[right];
if ((index = indexMap.get(c)) != null && index >= left) {
left = index + 1;
}
indexMap.put(c, right);
max = Math.max(max, right - left + 1);
}
return max;
}

146.实现lru#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public class LRUCache {

class DNode {
int key;
int val;
DNode pre;
DNode next;
}

private DNode head;
private DNode tail;
private HashMap<Integer, DNode> cache = new HashMap<Integer, DNode>();
private int capacity;
private int size;

public LRUCache(int capacity) {
this.capacity = capacity;
this.size = 0;
head = new DNode();
tail = new DNode();
head.next = tail;
tail.pre = head;
}

public int get(int key) {
// cache
DNode node = cache.get(key);
if (node == null) return -1;
// 移到最前面
moveToHead(node);
return node.val;
}

public void put(int key, int value) {
DNode node = cache.get(key);
if (node != null) {
node.val = value;
moveToHead(node);
} else {
node = new DNode();
node.key = key;
node.val = value;
cache.put(key, node);
addFirst(node);
size++;

if (size > capacity) {
cache.remove(tail.pre.key);
removeNode(tail.pre);
size--;
}
}
}

private void moveToHead(DNode node) {
// 删除节点
removeNode(node);
// 放到首节点后面
addFirst(node);
}

private void removeNode(DNode node) {
DNode pre = node.pre;
DNode next = node.next;
pre.next = next;
next.pre = pre;
}

private void addFirst(DNode node) {
DNode next = head.next;
node.next = next;
node.pre = head;

head.next = node;
next.pre = node;
}
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×