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

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

1. 螺旋矩阵

给你一个 mn 列的矩阵 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.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++) {
                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 <= 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;
        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. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 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 == 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;
    }
}

🌟 每日一练刷题专栏 🌟

持续,努力奋斗做强刷题搬运工!

👍 点赞,你的认可是我坚持的动力!

🌟 收藏,你的青睐是我努力的方向!

评论,你的意见是我进步的财富!  

主页:https://hannyang.blog.csdn.net/


目录
相关文章
|
1月前
|
缓存 算法 Java
Caffeine Cache~高性能 Java 本地缓存之王
Caffeine Cache~高性能 Java 本地缓存之王
54 1
|
1月前
|
搜索推荐 C++
C++冒泡排序的实现
C++冒泡排序的实现
|
1月前
|
缓存 Java
JAVA带缓存的输入输出流
JAVA带缓存的输入输出流
19 0
|
1月前
|
Java
CSDN每日一练(Java)--小艺的英文名
CSDN每日一练(Java)--小艺的英文名
|
1月前
|
Java
Java并发编程中的锁机制
【2月更文挑战第22天】 在Java并发编程中,锁机制是一种重要的同步手段,用于保证多个线程在访问共享资源时的安全性。本文将介绍Java锁机制的基本概念、种类以及使用方法,帮助读者深入理解并发编程中的锁机制。
|
1月前
|
Java 程序员
Java中的异常处理机制
【2月更文挑战第22天】在Java编程中,异常处理是一个重要的概念。它允许程序员在程序执行过程中遇到错误时,对错误进行处理,而不是让程序崩溃。本文将介绍Java中的异常处理机制,包括异常的分类、如何捕获和处理异常以及自定义异常等内容。
18 1
|
1月前
|
开发框架 Java API
java反射机制的原理与简单使用
java反射机制的原理与简单使用
17 1
|
15小时前
|
Java 数据库连接
深入理解Java异常处理机制
【4月更文挑战第24天】本文将探讨Java中的异常处理机制,包括异常的概念、分类、捕获和抛出等方面。通过深入了解异常处理机制,可以帮助我们编写更加健壮的程序,提高代码的可读性和可维护性。
|
9天前
|
缓存 NoSQL Java
使用Redis进行Java缓存策略设计
【4月更文挑战第16天】在高并发Java应用中,Redis作为缓存中间件提升性能。本文探讨如何使用Redis设计缓存策略。Redis是开源内存数据结构存储系统,支持多种数据结构。Java中常用Redis客户端有Jedis和Lettuce。缓存设计遵循一致性、失效、雪崩、穿透和预热原则。常见缓存模式包括Cache-Aside、Read-Through、Write-Through和Write-Behind。示例展示了使用Jedis实现Cache-Aside模式。优化策略包括分布式锁、缓存预热、随机过期时间、限流和降级,以应对缓存挑战。
|
17天前
|
存储 缓存 NoSQL
Java手撸一个缓存类似Redis
`LocalExpiringCache`是Java实现的一个本地缓存类,使用ConcurrentHashMap存储键值对,并通过ScheduledExecutorService定时清理过期的缓存项。类中包含`put`、`get`、`remove`等方法操作缓存,并有`clearCache`方法来清除过期的缓存条目。初始化时,会注册一个定时任务,每500毫秒检查并清理一次过期缓存。单例模式确保了类的唯一实例。
13 0

热门文章

最新文章