首页 > 其他分享 >力扣:有效的数独

力扣:有效的数独

时间:2024-08-22 14:59:58浏览次数:14  
标签:数字 boolean 九宫格 力扣 有效 num board 数独

文章目录

在这里插入图片描述


需求

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ,验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)

注意:
一个有效的数独(部分已被填充)不一定是可解的。
只需要根据以上规则,验证已经填入的数字是否有效即可。
空白格用 ‘.’ 表示。

示例1:
在这里插入图片描述

输入: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”]]

输出:true

示例 2:

输入:board =
[[“8”,“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”]]

输出:false
解释:除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示:
board.length == 9
board[i].length == 9
board[i][j] 是一位数字(1-9)或者 ‘.’


分析

看了题意, 其实不是很难理解哈, 如果用暴力解法也很好写, 这里就不写暴力的写法了.

我们可以根据题意看出, 其实维护三个容器然后在遍历数组的过程中, 能够比较容器了的已有值和当前元素比较就可以了.

public boolean isValidSudoku(char[][] board) {
    // 用于记录行、列和小九宫格中每个数字是否已经出现
    boolean[][] line = new boolean[9][9];  // 记录每一行中数字的出现情况
    boolean[][] con = new boolean[9][9];   // 记录每一列中数字的出现情况
    boolean[][] small9 = new boolean[9][9]; // 记录每个小九宫格中数字的出现情况

    // 遍历整个数独棋盘
    for (int i = 0; i < board.length; i++) {   // 遍历行
        for (int j = 0; j < board.length; j++) {  // 遍历列
            // 如果当前位置是 '.',则跳过
            if ('.' == board[i][j]) {
                continue;
            }
            
            // 将字符转换为数字(1-9)
            // '0' - 1 是为了将字符 '1' 转换为 0,'2' 转换为 1,以此类推
            int num = board[i][j] - '0' - 1;  
            
            // 计算小九宫格的索引
            int index = i / 3 * 3 + j / 3;
            
            // 检查当前数字在行、列或小九宫格中是否已经出现
            if (line[i][num] || con[j][num] || small9[index][num]) {
                return false;  // 如果出现重复数字,则数独无效
            }
            
            // 标记当前数字在行、列和小九宫格中已经出现
            line[i][num] = con[j][num] = small9[index][num] = true;
        }
    }
    
    // 如果没有发现重复数字,则数独有效
    return true;
}

执行结果:

在这里插入图片描述


结尾

以上 是我对这道算法的一些遐想和延伸, 可能不是最优解, 但是算法的优化嘛 本身就是一个思索的过程, 能在这个思索和迭代的过程中有所收获和乐趣就是在成长了, 欢迎大家一起来交流更多的解答…




标签:数字,boolean,九宫格,力扣,有效,num,board,数独
From: https://blog.csdn.net/Snowyyds/article/details/141426076

相关文章

  • 力扣热题100_栈_739_每日温度
    文章目录题目链接解题思路解题代码题目链接739.每日温度给定一个整数数组temperatures,表示每天的温度,返回一个数组answer,其中answer[i]是指对于第i天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用0来代替。示例1:输入:tempe......
  • 力扣面试经典算法150题:跳跃游戏
    跳跃游戏今天的题目是力扣面试经典150题中的数组的中等难度题:跳跃游戏。题目链接:https://leetcode.cn/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150题目描述给定一个非负整数数组nums,你最初位于数组的第一个下标,即nums[0]。数......
  • 大语言模型用于金融领域时间序列预测,真的有效吗?
    作者:老余捞鱼原创不易,转载请标明出处及原作者。写在前面的话:    本文主要探讨了大型语言模型(LLMs)在时间序列预测任务中的有效性,其对大语言模型在时间序列预测中的有效性提出了质疑,并且针对当下最为先进的OneFitsAll、Time-LLM、LLaTA这3个基于大语言模型的时间序......
  • 力扣热题100_二分查找_74_搜索二维矩阵
    文章目录题目链接解题思路解题代码题目链接74.搜索二维矩阵给你一个满足下述两条属性的mxn整数矩阵:每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。给你一个整数target,如果target在矩阵中,返回true;否则,返回fa......
  • 配置stm32cubemx采集stm32H743IIT6,通过DMA实现多通道和多模块ADC的采集,亲测有效!
     之前写到stm32cubemx通过阻塞实现单通道和多通道的ADC的采集。本文分享通过DMA实现单模块多通道和多模块多通道的ADC采集。stm32cubemx的版本6.10.0。一、DMA采集多通道ADC数据阻塞采集是每次采集adc数据,cpu死等,直到采集完或者在设定时间超时没能采集,返回到cpu。DMA采集......
  • day6 哈希表part01: 242.有效的字母异位词|349. 两个数组的交集|202. 快乐数|1. 两数
    242.有效的字母异位词 classSolution{publicbooleanisAnagram(Strings,Stringt){int[]record=newint[26];//a=97.soa-a=0,b-a=1.直接使用减法,不用记acii码值。//遍历第一个string++,遍历第二个string--.数组里的数字......
  • 零壹塔(力扣,递归,找父节点)
    https://leetcode.cn/problems/k-th-symbol-in-grammar/0/\01/\/0110/\/\/\/\01101001#include<iostream>usingnamespacestd;intsolve(i......
  • 利用python下载小鹅通课程视频的方法(已购) 绝对有效2024
    1、先找到视频对应的红框里的地址,网页右键,审查元素。2、打开地址,下载视频对应文件,使用记事本打开,查看文件内容。3、使用Python解析文件里的url,进行视频下载。importrequestsimportrefromCrypto.CipherimportAESdefm3u8(url):header={'User-Agen......
  • 有效的括号(20)
    题目描述给定一个只包括'(',')','{','}','[',']'的字符串s,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。大体思路这里我们使用栈这个数据结构来解决,我们从左到右依次遍......
  • 动态规划:找出每个位置为止最长的有效障碍赛跑路线
    目录问题定义思路解题过程复杂度code问题定义        你打算构建一些障碍赛跑路线。给你一个 下标从0开始 的整数数组 obstacles ,数组长度为 n ,其中 obstacles[i] 表示第 i 个障碍的高度。对于每个介于 0 和 n-1 之间(包含 0 和 n-1)的下......