146. LRU缓存机制
使用双向链表+哈希表。
双向链表靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
哈希表通过键映射到其在双向链表中的位置。
get时，如果哈希表中没有这个key，则返回-1。如果有，则返回value，且把对应的结点移到双向链表头部。
put时，如果哈希表中没有这个key，则新建一个node，加到链表头部，如果超出最大容量，则删除尾部结点。如果有这个key，则更新，且移到头部。
class LRUCache {
class DLinkedNode {
int key, value;
DLinkedNode pre, next;
public DLinkedNode() {
}
public DLinkedNode(int _key, int _value) {
this.key = _key;
this.value = _value;
}
}
Map<Integer, DLinkedNode> cache;
int capcacity, size;
DLinkedNode head, tail;
public LRUCache(int capacity) {
this.capcacity = capacity;
this.cache = new HashMap<>();
this.size = 0;
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.pre = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
moveTohead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
DLinkedNode newNode = new DLinkedNode(key, value);
addToHead(newNode);
size++;
cache.put(key, newNode);
if (size > capcacity) {
DLinkedNode lastNode = removeTail();
size--;
cache.remove(lastNode.key);//注意这里是删key，而不是删结点
}
} else {
node.value = value;
moveTohead(node);
}
}
private void moveTohead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
private void removeNode(DLinkedNode node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
private void addToHead(DLinkedNode node) {
node.next = head.next;
node.pre = head;
head.next.pre = node;
head.next = node;
}
private DLinkedNode removeTail() {
DLinkedNode node = tail.pre;
removeNode(node);
return node;
}
}
147. 对链表进行插入排序
用pre记录结点应该插入的位置，插入到pre之后。
head.next记录当前应该进行插入的结点。
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummyHead = new ListNode(0), pre;
dummyHead.next = head;
while (head != null && head.next != null) {
if (head.val <= head.next.val) {
head = head.next;
continue;
}
pre = dummyHead;
ListNode insertNode = head.next;//将要插入的结点
while (pre.next.val < insertNode.val) {
pre = pre.next;
}
head.next = insertNode.next;
insertNode.next = pre.next;
pre.next = insertNode;
}
return dummyHead.next;
}
}
148. 排序链表
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode head2 = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(head2);
return merge(left, right);
}
public ListNode merge(ListNode node1, ListNode node2) {
if (node1 == null) {
return node2;
}
if (node2 == null) {
return node1;
}
if (node1.val < node2.val) {
node1.next = merge(node1.next, node2);
return node1;
} else {
node2.next = merge(node1, node2.next);
return node2;
}
}
}
149. 直线上最多的点数
遇到了很多坑，要考虑斜率为无穷的情况，要考虑完全相同的点，要考虑斜率的精度问题。
import java.math.BigDecimal;
class Solution {
public int maxPoints(int[][] points) {
if (points.length == 1) {
return 1;
}
int res = 0;
for (int i = 0; i < points.length; i++) {
Map<BigDecimal, Integer> map = new HashMap<>();
BigDecimal x = new BigDecimal(points[i][0]), y = new BigDecimal(points[i][1]);
int count = 0, res2 = 0;
for (int j = 0; j < points.length; j++) {
if (j == i) {
continue;
}
BigDecimal x1 = new BigDecimal(points[j][0]), y1 = new BigDecimal(points[j][1]);
if (x1.equals(x) && y1.equals(y)) {
count++;
res = Math.max(res, count + 1);
continue;
}
BigDecimal k;
if (x1.subtract(x).equals(new BigDecimal(0))) {
k = new BigDecimal(Integer.MAX_VALUE);
} else {
k = y1.subtract(y).divide(x1.subtract(x), 20, BigDecimal.ROUND_HALF_UP);
}
if (map.containsKey(k)) {
map.put(k, map.get(k) + 1);
} else {
map.put(k, 2);
}
res2 = Math.max(res2, map.get(k));
res = Math.max(res, res2 + count);
}
}
return res;
}
}
150. 逆波兰表达式求值
逆波兰表达式就是后缀表达式。
题目提示了：
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new ArrayDeque<>();
for (String token : tokens) {
if (token.equals("+")) {
Integer a = stack.pop();
Integer b = stack.pop();
stack.push(a + b);
} else if (token.equals("-")) {
Integer a = stack.pop();
Integer b = stack.pop();
stack.push(b - a);
} else if (token.equals("*")) {
Integer a = stack.pop();
Integer b = stack.pop();
stack.push(b * a);
} else if (token.equals("/")) {
Integer a = stack.pop();
Integer b = stack.pop();
stack.push(b / a);
} else {
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
}
