算法-模拟

1、旋转数组

public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 旋转数组* @param n int整型 数组长度* @param m int整型 右移距离* @param a int整型一维数组 给定数组* @return int整型一维数组*/public int[] solve (int n, int m, int[] a) {int left = 0;int right = n - 1;swap(left, right, a);// 在将0 到 m-1 交换left = 0;right = (m - 1) % n;swap(left, right, a);// 在将0 到 m-1 交换left = right + 1;right = n - 1;swap(left, right, a);return a;}private void swap(int left, int right, int[] a) {while (left < right) {int temp = a[left];a[left] = a[right];a[right] = temp;left ++;right --;}}
}

2、 螺旋矩阵

public ArrayList<Integer> spiralOrder (int[][] matrix) {ArrayList res = new ArrayList();if (matrix == null || matrix.length == 0) {return res;}int l = 0;int t = 0;int r = matrix[0].length - 1;int d = matrix.length - 1;while (l <= r && t <= d) {for (int i = l; i <= r; i++) {res.add(matrix[t][i]);}t++;if (t > d) {break;}for (int i = t; i <= d; i++) {res.add(matrix[i][r]);}r--;if (l > r) {break;}for (int i = r; i >= l; i--) {res.add(matrix[d][i]);}d--;if (t > d) {break;}for (int i = d; i >= t; i--) {res.add(matrix[i][l]);}l++;if (l > r) {break;}}return res;}

3、 顺时针旋转矩阵

public int[][] rotateMatrix (int[][] mat, int n) {//  1 2 3    // 7 4 1//  4 5 6    // 8 5 2//  7 8 9    // 9 6 3for (int i = 0; i < mat.length; i++) {for (int j = 0; j < i; j++) {int temp = mat[i][j];mat[i][j] = mat[j][i];mat[j][i] = temp;}}int columnNumber = mat[0].length;for (int i = 0; i < mat.length; i++) {for (int j = 0; j < columnNumber / 2; j++) {int temp = mat[i][j];mat[i][j] = mat[i][columnNumber - j - 1];mat[i][columnNumber - j - 1] = temp;}}return mat;
}

4、 设计LRU缓存结构

public class Solution {Map<Integer, Node> resultMap = new HashMap();Node head = new Node(-1,-1);Node last = new Node(-1,-1);int used = 0;int capacity;class Node {int key;int value;Node pre;Node next;Node(int key,int value) {this.value = value;this.key = key;}}public Solution(int capacity) {this.capacity = capacity;head.next = last;last.pre = head;}public int get(int key) {if (!resultMap.containsKey(key)) {return -1;}Node nodeTemp = resultMap.get(key);moveToHead(nodeTemp);return nodeTemp.value;}public void set(int key, int value) {if (!resultMap.containsKey(key)) {Node node = new Node(key,value);resultMap.put(key, node);if (used == capacity) {removeLast();} else {used++;}insertFirst(node);} else {resultMap.get(key).value = value;moveToHead(resultMap.get(key));}}private void moveToHead(Node node) {if (node.pre == head) {return;}node.pre.next = node.next;node.next.pre = node.pre;insertFirst(node);}private void insertFirst(Node node) {node.next = head.next;node.pre = head;head.next = node;node.next.pre = node;}private void removeLast() {resultMap.remove(last.pre.key);last.pre.pre.next = last;last.pre = last.pre.pre;}
}

5、 设计LFU缓存结构

public class Solution {//记录缓存剩余容量private int size = 0;private int minFreq = 1;Map<Integer, Node> nodeMap = new HashMap();Map<Integer, LinkedList<Node>> freNodeMap = new HashMap();class Node {int key;int value;int fre;Node(int key, int value, int fre) {this.key = key;this.value = value;this.fre = fre;}}/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** lfu design* @param operators int整型二维数组 ops* @param k int整型 the k* @return int整型一维数组*/public int[] LFU (int[][] operators, int k) {this.size = k;int length = (int)Arrays.stream(operators).filter(e->e[0] == 2).count();int[] res = new int[length];int index = 0;for (int i = 0; i < operators.length; i++) {int[] operatorsTemp = operators[i];if (operatorsTemp[0] == 1) {set(operatorsTemp[1], operatorsTemp[2]);} else {res[index++] = get(operatorsTemp[1]);}}return res;}private int get(int key) {int res = -1;if (nodeMap.containsKey(key)) {res = nodeMap.get(key).value;updateFreq(nodeMap.get(key));}return res;}private void set(int key, int value) {if (nodeMap.containsKey(key)) {nodeMap.get(key).value = value;updateFreq(nodeMap.get(key));} else {if (size == 0) {int oldKey = freNodeMap.get(minFreq).getLast().key;freNodeMap.get(minFreq).removeLast();if (freNodeMap.get(minFreq).isEmpty()) {freNodeMap.remove(minFreq);}nodeMap.remove(oldKey);} else {size --;}minFreq = 1;if (!freNodeMap.containsKey(minFreq)) {freNodeMap.put(minFreq, new LinkedList());}freNodeMap.get(minFreq).addFirst(new Node(key, value, 1));nodeMap.put(key, freNodeMap.get(minFreq).getFirst());}}private void updateFreq(Node node) {LinkedList linkedListNode = freNodeMap.get(node.fre);linkedListNode.remove(node);if (linkedListNode.isEmpty()) {freNodeMap.remove(linkedListNode);if (minFreq == node.fre) {minFreq = node.fre + 1;}}node.fre = node.fre + 1;if (!freNodeMap.containsKey(node.fre)) {freNodeMap.put(node.fre, new LinkedList());}freNodeMap.get(node.fre).addFirst(node);}
}