Java每日一练(20230427) 螺旋矩阵、LRU缓存机制、解数独

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<Integer>();
        if (matrix.length == 0 || (matrix.length == 1 && matrix[0].length == 0))
            return res;
        int left = 0;
        int right = matrix[0].length - 1;
        int top = 0;
        int bottom = matrix.length - 1;
        int num = (right + 1) * (bottom + 1);
        while (num > 0) {
            for (int j = left; j <= right; j++) {
                res.add(matrix[top][j]);
                num--;
            }
            if (num <= 0)
                break;
            top++;
            for (int i = top; i <= bottom; i++) {
                res.add(matrix[i][right]);
                num--;
            }
            if (num <= 0)
                break;
            right--;
            for (int j = right; j >= left; j--) {
                res.add(matrix[bottom][j]);
                num--;
            }
            if (num <= 0)
                break;
            bottom--;
            for (int i = bottom; i >= top; i--) {
                res.add(matrix[i][left]);
                num--;
            }
            if (num <= 0)
                break;
            left++;
        }
        return res;
    }
}

class LRUCache {
    class Node {
        Node prev, next;
        int key, value;
        Node(int _key, int _value) {
            key = _key;
            value = _value;
        }
    }
    Node head = new Node(0, 0), tail = new Node(0, 0);
    Map<Integer, Node> map = new HashMap<>();
    int max_len;
    public LRUCache(int capacity) {
        max_len = capacity;
        head.next = tail;
        tail.prev = head;
    }
    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            remove(node);
            add(node);
            return node.value;
        } else {
            return -1;
        }
    }
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            remove(map.get(key));
        }
        if (map.size() == max_len) {
            remove(head.next);
        }
        add(new Node(key, value));
    }
    private void remove(Node node) {
        map.remove(node.key);
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    private void add(Node node) {
        map.put(node.key, node);
        Node pre_tail = tail.prev;
        node.next = tail;
        tail.prev = node;
        pre_tail.next = node;
        node.prev = pre_tail;
    }
}

class Solution {
    boolean row[][] = new boolean[9][9];
    boolean col[][] = new boolean[9][9];
    boolean cell[][][] = new boolean[3][3][9];
    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int t = board[i][j] - '1';
                    row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
                }
            }
        }
        dfs(board, 0, 0);
    }
    public boolean dfs(char[][] board, int x, int y) {
        if (y == 9) {
            x++;
            y = 0;
        }
        if (x == 9)
            return true;
    if (board[x][y] != '.')
        return dfs(board, x, y + 1);
        for (int num = 0; num < 9; num++) {
            if (!row[x][num] && !col[y][num] && !cell[x / 3][y / 3][num]) {
                board[x][y] = (char) (num + '1');
                row[x][num] = col[y][num] = cell[x / 3][y / 3][num] = true;
                if (dfs(board, x, y + 1))
                    return true;
                board[x][y] = '.';
                row[x][num] = col[y][num] = cell[x / 3][y / 3][num] = false;
            }
        }
        return false;
    }
}