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

## 1. 螺旋矩阵

• m == matrix.length
• n == matrix[i].length
• 1 <= 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++) {
num--;
}
if (num <= 0)
break;
top++;
for (int i = top; i <= bottom; i++) {
num--;
}
if (num <= 0)
break;
right--;
for (int j = right; j >= left; j--) {
num--;
}
if (num <= 0)
break;
bottom--;
for (int i = bottom; i >= top; i--) {
num--;
}
if (num <= 0)
break;
left++;
}
return res;
}
}

## 2. LRU 缓存机制

• LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
• void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

["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 <= 3000
• 0 <= key <= 10000
• 0 <= value <= 10^5
• 最多调用 2 * 10^5getput

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;
}
public int get(int key) {
if (map.containsKey(key)) {
Node node = map.get(key);
remove(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) {
}
}
private void remove(Node node) {
map.remove(node.key);
node.prev.next = node.next;
node.next.prev = node.prev;
}
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. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

[["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 == 9
• board[i].length == 9
• board[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;
}
}

## 🌟 每日一练刷题专栏 🌟

👍 点赞，你的认可是我坚持的动力！

🌟 收藏，你的青睐是我努力的方向！

|
1月前
|

Caffeine Cache~高性能 Java 本地缓存之王
Caffeine Cache~高性能 Java 本地缓存之王
54 1
|
1月前
|

C++冒泡排序的实现
C++冒泡排序的实现
10 0
|
1月前
|

JAVA带缓存的输入输出流
JAVA带缓存的输入输出流
19 0
|
1月前
|
Java
CSDN每日一练（Java）--小艺的英文名
CSDN每日一练（Java）--小艺的英文名
20 0
|
1月前
|
Java
Java并发编程中的锁机制
【2月更文挑战第22天】 在Java并发编程中，锁机制是一种重要的同步手段，用于保证多个线程在访问共享资源时的安全性。本文将介绍Java锁机制的基本概念、种类以及使用方法，帮助读者深入理解并发编程中的锁机制。
|
1月前
|
Java 程序员
Java中的异常处理机制
【2月更文挑战第22天】在Java编程中，异常处理是一个重要的概念。它允许程序员在程序执行过程中遇到错误时，对错误进行处理，而不是让程序崩溃。本文将介绍Java中的异常处理机制，包括异常的分类、如何捕获和处理异常以及自定义异常等内容。
18 1
|
1月前
|

java反射机制的原理与简单使用
java反射机制的原理与简单使用
17 1
|
15小时前
|
Java 数据库连接

【4月更文挑战第24天】本文将探讨Java中的异常处理机制，包括异常的概念、分类、捕获和抛出等方面。通过深入了解异常处理机制，可以帮助我们编写更加健壮的程序，提高代码的可读性和可维护性。
7 2
|
9天前
|

159 7
|
17天前
|

Java手撸一个缓存类似Redis
LocalExpiringCache是Java实现的一个本地缓存类，使用ConcurrentHashMap存储键值对，并通过ScheduledExecutorService定时清理过期的缓存项。类中包含put、get、remove等方法操作缓存，并有clearCache`方法来清除过期的缓存条目。初始化时，会注册一个定时任务，每500毫秒检查并清理一次过期缓存。单例模式确保了类的唯一实例。
13 0