免费做国际网站,深圳画册设计师,wordpress谷歌字体插件,wordpress自适应图片主题牛客网【面试必刷TOP101】~ 11 模拟 文章目录 牛客网【面试必刷TOP101】~ 11 模拟[toc]BM97 旋转数组(★★)BM98 螺旋矩阵(★)BM99 顺时针旋转矩阵(★★)BM100 设计LRU缓存结构(★★★)BM101 设计LFU缓存结构(★★★) BM97 旋转数组(★★)
两次反转 [1, 2, 3, 4, 5, 6] [4, 3,…牛客网【面试必刷TOP101】~ 11 模拟 文章目录 牛客网【面试必刷TOP101】~ 11 模拟[toc]BM97 旋转数组(★★)BM98 螺旋矩阵(★)BM99 顺时针旋转矩阵(★★)BM100 设计LRU缓存结构(★★★)BM101 设计LFU缓存结构(★★★)
BM97 旋转数组(★★)
两次反转 [1, 2, 3, 4, 5, 6] [4, 3, 2, 1, 6, 5] [5, 6, 1, 2, 3, 4] public class Solution {public int[] solve (int n, int m, int[] a) {m % n;reverse(a, 0, n - m - 1);reverse(a, n - m, n - 1);reverse(a, 0, n - 1);return a;}private void reverse(int[] a, int i, int j) {while (i j) {int t a[i];a[i] a[j];a[j--] t;}}
}BM98 螺旋矩阵(★)
一U型遍历
public class Solution {public ArrayListInteger spiralOrder (int[][] matrix) {ArrayListInteger res new ArrayList();if (matrix null || matrix.length 0 || matrix[0].length 0) {return res;}int top 0, bottom matrix.length - 1;int left 0, right matrix[0].length - 1;while (left right top bottom) {for (int i left; i right; i) res.add(matrix[top][i]);for (int i top 1; i bottom; i) res.add(matrix[i][right]);if (left right top bottom) {for (int i right - 1; i left; i--) res.add(matrix[bottom][i]);for (int i bottom; i top; i--) res.add(matrix[i][left]);}top;right--;bottom--;left;}return res;}
}BM99 顺时针旋转矩阵(★★) [1, 2, 3] [1, 4, 7] [7, 4, 1] [4, 5, 6] 沿对角线旋转 [2, 5, 8] 竖轴对称旋转 [8, 5, 2] [7, 8, 9] [3, 6, 9] [9, 6, 3] public class Solution {public int[][] rotateMatrix (int[][] mat, int n) {// 沿左上对角线旋转for (int i 0; i n; i) {for (int j 0; j i; j) {if (i j) continue;int t mat[i][j];mat[i][j] mat[j][i];mat[j][i] t;}}// 竖轴对称旋转for (int i 0; i n; i) {for (int j 0; j n / 2; j) {int t mat[i][j];mat[i][j] mat[i][n - j - 1];mat[i][n - j - 1] t;}}return mat;}
}BM100 设计LRU缓存结构(★★★) 哈希表双向链表
public class Solution {class DLinkedNode {int key;int value;DLinkedNode prev;DLinkedNode next;DLinkedNode () {};DLinkedNode (int key, int value) {this.key key;this.value value;}}private int size;private int capacity;private DLinkedNode head, tail;private HashMapInteger, DLinkedNode cache new HashMapInteger, DLinkedNode();public Solution(int capacity) {size 0;this.capacity capacity;// 使用伪头部和伪尾部节点this.head new DLinkedNode();this.tail new DLinkedNode();head.next tail;tail.prev head;}public int get(int key) {DLinkedNode node cache.get(key);if (node null) return -1;moveToHead(node);return node.value;}public void set(int key, int value) {DLinkedNode node cache.get(key);if (node null) {DLinkedNode newNode new DLinkedNode(key, value);cache.put(key, newNode);addToHead(newNode);size;if (size capacity) {DLinkedNode tail removeTail();cache.remove(tail.key);size--;}} else {node.value value;moveToHead(node);}return;}private void addToHead(DLinkedNode node) {node.prev head;node.next head.next;head.next.prev node;head.next node;}private void removeNode(DLinkedNode node) {node.prev.next node.next;node.next.prev node.prev;}private void moveToHead(DLinkedNode node) {removeNode(node);addToHead(node);}private DLinkedNode removeTail() {DLinkedNode res tail.prev;removeNode(res);return res;}}BM101 设计LFU缓存结构(★★★) 方法一HashMapTreeMap684ms
import java.util.*;public class Solution {// 缓存容量、时间戳int capacity, time;MapInteger, Node key_table;TreeSetNode tree;ListInteger res;public int[] LFU (int[][] operators, int k) {this.capacity k;this.time 0;this.key_table new HashMapInteger, Node();this.tree new TreeSetNode();this.res new ArrayListInteger();for (int[] opt : operators) {if (opt[0] 1) {set(opt[1], opt[2]);} else {res.add(get(opt[1]));}} int[] answer new int[res.size()];for (int i 0; i res.size(); i) {answer[i] res.get(i);}return answer;}public int get(int key) {if (capacity 0) return -1;if (!key_table.containsKey(key)) return -1;Node node key_table.get(key);key_table.remove(key);tree.remove(node);node.cnt 1;node.time time;tree.add(node);key_table.put(key, node);return node.value;}public void set(int key, int value) {if (capacity 0) return;if (key_table.containsKey(key)) {Node node key_table.get(key);tree.remove(node);key_table.remove(key);node.value value;node.cnt 1;node.time time;tree.add(node);key_table.put(key, node);} else {if (tree.size() capacity) {key_table.remove(tree.first().key);tree.remove(tree.first());}Node newNode new Node(key, value, 1, time);tree.add(newNode);key_table.put(key, newNode);}}class Node implements ComparableNode {int key, value;int cnt, time;Node(){};Node(int key, int value, int cnt, int time) {this.key key;this.value value;this.cnt cnt;this.time time;}public boolean equals(Object obj) {if (this obj) return true;if (obj instanceof Node) {Node node (Node) obj;return this.key node.key this.value node.value;}return true;}public int compareTo(Node node) {// 降序排列return this.cnt node.cnt ? this.time - node.time : this.cnt - node.cnt;}public int hashCode() {return this.cnt * 1000000007 time;}}}
方法二双HashMapDoublyLinkedList591ms
import java.util.*;public class Solution {int capacity, minfreq;MapInteger, Node keyTable;MapInteger, DLinkedList freqTable;ListInteger res;public int[] LFU (int[][] operators, int k) {this.capacity k;this.minfreq 0;this.keyTable new HashMapInteger, Node();this.freqTable new HashMapInteger, DLinkedList();this.res new ArrayListInteger();for (int[] opt : operators) {if (opt[0] 1) {this.set(opt[1], opt[2]);} else {res.add(this.get(opt[1]));}}int[] answer new int[res.size()];for (int i 0; i res.size(); i) {answer[i] res.get(i);}return answer;}public int get(int key) {if (capacity 0) return -1;if (!keyTable.containsKey(key)) return -1;Node node keyTable.get(key);int val node.val, freq node.freq;freqTable.get(freq).remove(node);if (freqTable.get(freq).size 0) {freqTable.remove(freq);if (minfreq freq) {minfreq 1;}}DLinkedList list freqTable.getOrDefault(freq 1, new DLinkedList());list.addFirst(new Node(key, val, freq 1));freqTable.put(freq 1, list);keyTable.put(key, list.getHead());return val;}public void set(int key, int val) {if (capacity 0) return;if (keyTable.containsKey(key)) {Node node keyTable.get(key);int freq node.freq;freqTable.get(freq).remove(node);if (freqTable.get(freq).size 0) {freqTable.remove(freq);if (minfreq freq) {minfreq 1;}}DLinkedList list freqTable.getOrDefault(freq 1, new DLinkedList());list.addFirst(new Node(key, val, freq 1));keyTable.put(key, list.getHead());freqTable.put(freq 1, list);} else {if (keyTable.size() capacity) {Node node freqTable.get(minfreq).getTail();keyTable.remove(node.key);freqTable.get(minfreq).remove(node);if (freqTable.get(minfreq).size 0) {freqTable.remove(minfreq);}}DLinkedList list freqTable.getOrDefault(1, new DLinkedList());list.addFirst(new Node(key, val, 1));keyTable.put(key, list.getHead());freqTable.put(1, list);minfreq 1;}}class Node {int key, val, freq;Node prev, next;Node(){ this(-1, -1, 0); }Node(int key, int val, int freq) {this.key key;this.val val;this.freq freq;}}class DLinkedList {Node dummyHead;Node dummyTail;int size;DLinkedList() {this.dummyHead new Node();this.dummyTail new Node();this.dummyHead.next this.dummyTail;this.dummyTail.prev this.dummyHead;this.size 0;}public void addFirst(Node node) {node.next dummyHead.next;node.prev dummyHead;dummyHead.next.prev node;dummyHead.next node;size;}public void remove(Node node) {node.prev.next node.next;node.next.prev node.prev;size--;}public Node getHead() {return this.dummyHead.next;}public Node getTail() {return this.dummyTail.prev;}}}
