算法-模拟

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 --;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93