网站建设 月光博客,网站优化推广 site,高端网站建设万维科技,免费行情软件app网站大全1、旋转数组
public class Solution {/*** 代码中的类名、方法名、参数名已经指定#xff0c;请勿修改#xff0c;直接返回方法规定的值即可** 旋转数组* param n int整型 数组长度* param m int整型 右移距离* param a int整型一维数组 给定数组* return int整型一维数组*/…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 ArrayListInteger 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 {MapInteger, 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;MapInteger, Node nodeMap new HashMap();MapInteger, LinkedListNode 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);}
}
