算法-模拟

淩亂°似流年 2024-03-26 22:56 9阅读 0赞

## 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 3
        for (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);
        }
    }