1. 螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
出处：
https://edu.csdn.net/practice/26654049
代码：
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; } }
2. LRU 缓存机制
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。
实现 LRUCache 类：
LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。void put(int key, int value)如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
提示：
1 <= capacity <= 30000 <= key <= 100000 <= value <= 10^5- 最多调用
2 * 10^5次get和put
出处：
https://edu.csdn.net/practice/26654050
代码：
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; } }
3. 解数独
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例：
输入：board =
[["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]
输出：
[["5","3","4","6","7","8","9","1","2"],
["6","7","2","1","9","5","3","4","8"],
["1","9","8","3","4","2","5","6","7"],
["8","5","9","7","6","1","4","2","3"],
["4","2","6","8","5","3","7","9","1"],
["7","1","3","9","2","4","8","5","6"],
["9","6","1","5","3","7","2","8","4"],
["2","8","7","4","1","9","6","3","5"],
["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
提示：
board.length == 9board[i].length == 9board[i][j]是一位数字或者'.'- 题目数据 保证 输入数独仅有一个解
以下程序实现了这一功能，请你填补空白处内容：
···Java 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; ____________________; 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; } } ```
出处：
https://edu.csdn.net/practice/26654051
代码：
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; } }
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
