第32天--算法（Leetcode 136,138,139,140,141,146）
136.只出现一次的数字
public int singleNumber(int[] nums) {
int ans = 0;
for(int i : nums) {
ans ^= i;
}
return ans;
}
138.复制带随机指针的链表
public Node copyRandomList(Node head) {
if(head == null) {
return null;
}
Node cur = head;
while(cur != null) {
Node temp = new Node(cur.val);
temp.next = cur.next;
cur.next = temp;
cur = temp.next;
}
cur = head;
while(cur != null) {
cur.next.random = cur.random == null ? null : cur.random.next;
cur = cur.next.next;
}
cur = head;
Node res = head.next;
Node temp = res;
while(temp.next != null) {
cur.next = temp.next;
cur = cur.next;
temp.next = cur.next;
temp = temp.next;
}
cur.next = null;
return res;
}
139.单词拆分
public boolean wordBreak(String s, List wordDict) {
HashSet hs = new HashSet<>(wordDict);
int N = s.length();
boolean dp[] = new boolean[N + 1];
dp[N] = true;
for(int index = N - 1;index >= 0;index --) {
for(int j = index;j < s.length();j ++) {
if(hs.contains(s.substring(index,j + 1))) {
if(dp[j + 1]) {
dp[index] = true;
continue;
}
}
}
}
return dp[0];
}
140.单词拆分2
public List wordBreak(String s, List wordDict) {
HashSet hs = new HashSet<>(wordDict);
int N = s.length();
boolean dp[] = new boolean[N + 1];
dp[N] = true;
List res = new ArrayList<>();
StringBuilder path = new StringBuilder();
process(s,0,hs,path,res);
return res;
}
public void process(String s,int index,HashSet hs,StringBuilder path,List res) {
if(index == s.length()) {
res.add(path.toString().substring(0,path.length() - 1));
}else {
for(int j = index;j < s.length();j ++) {
StringBuilder rest = new StringBuilder(path);
if(hs.contains(s.substring(index,j + 1))) {
path.append(s.substring(index,j + 1)).append(" ");
process(s,j + 1,hs,path,res);
}
path = rest;
}
}
}
141.环形链表
public boolean hasCycle(ListNode head) {
return process(head) != null;
}
public ListNode process(ListNode head) {
if(head == null || head.next == null || head.next.next == null) {
return null;
}
ListNode fast = head.next.next;
ListNode slow = head.next;
while(slow != fast) {
if(fast.next == null || fast.next.next == null) {
return null;
}
fast = fast.next.next;
slow = slow.next;
}
fast = head;
while(slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
146.LRU缓存
private MyCache cache;
public LRUCache(int capacity) {
cache = new MyCache<>(capacity);
}
public int get(int key) {
Integer ans = cache.get(key);
return ans == null ? -1 : ans;
}
public void put(int key, int value) {
cache.set(key, value);
}
public static class Node {
public K key;
public V value;
public Node last;
public Node next;
public Node(K key, V value) {
this.key = key;
this.value = value;
}
}
public static class NodeDoubleLinkedList {
private Node head;
private Node tail;
public NodeDoubleLinkedList() {
head = null;
tail = null;
}
public void addNode(Node newNode) {
if (newNode == null) {
return;
}
if (head == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
newNode.last = tail;
tail = newNode;
}
}
public void moveNodeToTail(Node node) {
if (tail == node) {
return;
}
// node 不是尾巴
if (head == node) {
head = node.next;
head.last = null;
} else {
node.last.next = node.next;
node.next.last = node.last;
}
node.last = tail;
node.next = null;
tail.next = node;
tail = node;
}
public Node removeHead() {
if (head == null) {
return null;
}
Node res = head;
if (head == tail) { // 链表中只有一个节点的时候
head = null;
tail = null;
} else {
head = res.next;
res.next = null;
head.last = null;
}
return res;
}
}
public static class MyCache {
private HashMap> keyNodeMap;
private NodeDoubleLinkedList nodeList;
private final int capacity;
public MyCache(int cap) {
if (cap < 1) {
throw new RuntimeException("should be more than 0.");
}
keyNodeMap = new HashMap>();
nodeList = new NodeDoubleLinkedList();
capacity = cap;
}
public V get(K key) {
if (keyNodeMap.containsKey(key)) {
Node res = keyNodeMap.get(key);
nodeList.moveNodeToTail(res);
return res.value;
}
return null;
}
public void set(K key, V value) {
if (keyNodeMap.containsKey(key)) {
Node node = keyNodeMap.get(key);
node.value = value;
nodeList.moveNodeToTail(node);
} else {
if (keyNodeMap.size() == capacity) {
removeMostUnusedCache();
}
Node newNode = new Node(key, value);
keyNodeMap.put(key, newNode);
nodeList.addNode(newNode);
}
}
private void removeMostUnusedCache() {
Node removeNode = nodeList.removeHead();
keyNodeMap.remove(removeNode.key);
}
}