矩阵&滑动窗口|36. 有效的数独 3. 无重复字符的最长子串

这篇具有很好参考价值的文章主要介绍了矩阵&滑动窗口|36. 有效的数独 3. 无重复字符的最长子串。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] hang=new int[9][10];
        int[][] lie=new int[9][10];
        int[][] small=new int[9][10];
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[0].length;j++){
                if(board[i][j]!='.'){
                    if(hang[i][Character.getNumericValue(board[i][j])]!=1){
                        hang[i][Character.getNumericValue(board[i][j])]=1;
                    }else{
                        return false;
                    }
                    if(lie[j][Character.getNumericValue(board[i][j])]!=1){
                        lie[j][Character.getNumericValue(board[i][j])]=1;
                    }else{
                        return false;
                    }
                    int numofsmall= (i/3)*3+j/3;
                    if(small[numofsmall][Character.getNumericValue(board[i][j])]!=1){
                        small[numofsmall][Character.getNumericValue(board[i][j])]=1;
                    }else{
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

题目:给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
题目链接:无重复字符的最长子串
注意条件:s 由英文字母、数字、符号和空格组成
所以 不能用英文对应数组的方式进行记录
解题思路:滑动窗口+哈希表文章来源地址https://www.toymoban.com/news/detail-802041.html

class Solution {
    public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> dic = new HashMap<>();
        int i = -1, res = 0, len = s.length();
        for(int j = 0; j < len; j++) {
            if (dic.containsKey(s.charAt(j)))
                i = Math.max(i, dic.get(s.charAt(j)));// 更新左指针 i  因为是滑动窗口 有一些前面的值已经不作数了但没有更新 所以加一个max确保i不回跳 取到一些没有意义的值(也可以遍历删除 但比较麻烦)(实例:abba 建议手推)
            dic.put(s.charAt(j), j); // 哈希表记录
            res = Math.max(res, j - i); // 更新结果
        }
        return res;
    }
}

到了这里,关于矩阵&滑动窗口|36. 有效的数独 3. 无重复字符的最长子串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣题库刷题笔记36--有效的数独

    1、题目如下:  2、个人Python代码实现如下: 3、个人Python代码思路:         先放一个AI解释的思路:         个人理解,本题思路其实很简单,判断每一行、每一列、每一个3*3的子数独是否存在重复数字,如果存在则返回False,如果不存在则返回True。         1、首先

    2024年02月13日
    浏览(44)
  • C语言 | Leetcode C语言题解之第36题有效的数独

    题目: 题解:

    2024年04月22日
    浏览(37)
  • 【面试经典150 | 矩阵】有效的数独

    本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删: Tag:介绍本题牵涉到的知识点、数据结构; 题目来源:

    2024年02月05日
    浏览(38)
  • 有效的数独

    有效的数独 board.length == 9 board[i].length == 9 board[i][j] 是一位数字(1-9)或者 ‘.’ 首先判断行是否满足数独条件,再判断列是否满足数独条件,最后再判断划分的3x3方格是否满足数独条件,中间有一处不满足则直接返回false,遍历完后都满足条件则返回true 有效数独的条件

    2024年02月06日
    浏览(42)
  • C++面试宝典第31题:有效的数独

    题目         判断一个9 x 9的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。         1、数字1-9在每一行只能出现一次。         2、数字1-9在每一列只能出现一次。         3、数字1-9在每一个以粗实线分隔的3 x 3宫内只能出现一次。

    2024年02月22日
    浏览(33)
  • 力扣(LeetCode)算法_C++——有效的数独

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

    2024年02月09日
    浏览(38)
  • 【LeetCode滑动窗口专题#2】无重复字符的最长子串

    #1传送门 滑动窗口最大值 长度最小的子数组 给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: s = \\\"abcabcbb\\\" 输出: 3 解释: 因为无重复字符的最长子串是 \\\"abc\\\",所以其长度为 3。 示例 2: 输入: s = \\\"bbbbb\\\" 输出: 1 解释: 因为无重复字符的最长子串

    2024年02月08日
    浏览(40)
  • 【滑动窗口】leetcode3:无重复字符的最长子串

    无重复字符的最长子串 题目要求我们找符合要求的最长子串,要求是不能包含重复字符 确定一个子串只需确定它的左右区间即可,于是我们可以两层循环暴力枚举所有的子串,找到符合要求的,并通过比较得到最长的长度。还有一个问题,怎么确定有没有重复字符呢?可以

    2024年02月11日
    浏览(31)
  • 【滑动窗口】1100. 长度为 K 的无重复字符子串

    给你一个字符串 S,找出所有长度为 K 且不含重复字符的子串,请你返回全部满足要求的子串的 数目。 示例 1: 输入:S = “havefunonleetcode”, K = 5 输出:6 解释: 这里有 6 个满足题意的子串,分别是:‘havef’,‘avefu’,‘vefun’,‘efuno’,‘etcod’,‘tcode’。 示例 2: 输入:

    2024年02月08日
    浏览(35)
  • 【LeetCode】滑动窗口妙解无重复字符的最长子串

    Problem: 3. 无重复字符的最长子串 首先我们来分析一下本题的思路 如果读者有看过 长度最小的子数组 的话就可以清楚这个子串其实和子数组是一个道理,都是 连续的一段区间 但是呢它们本质上还是存在一定区别的,这里说到是要我们去寻找不含有重复字符的【最长子串】

    2024年02月07日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包