Leetcode刷题-(36~40)-Java

算法是码农的基本功,也是各个大厂必考察的重点,让我们一起坚持刷算法题吧。

遇事不决,可问春风,春风不语,即是本心。

我们在我们能力范围内,做好我们该做的事,然后相信一切都事最好的安排就可以啦,慢慢来,会很快,向前走,别回头。

目录

1.有效的数独

2.解数独

3.外观数列

4.组合总数

5.组合总数II


1.有效的数独

题目链接:. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/valid-sudoku/

思路:9*9的数独,要求每行的数字1-9只能出现一次,每列的数字1-9只能出现一次,每个3*3宫格内数字1-9只能出现一次,那么需要开辟三个标记数组用于记录每行、每列、每个3*3宫格内数字1-9出现的次数,若出现次数大于1,则无效,反之有效。


Java版:

class Solution {
    public boolean isValidSudoku(char[][] board) {
        // 第i行对应的元素j的数目
        int [][] row = new int [9][9] ;
        // 第i列对应的元素j的数目
        int [][] column = new int [9][9] ;
        // 当前宫内的第i行第j列元素k的数目
        int [][][] square = new int [3][3][9] ;
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                if(board[i][j] != '.'){
                    int element = board[i][j] - '0' - 1  ;
                    row[i][element] ++ ;
                    column[j][element] ++ ;
                    square[i/3][j/3][element] ++ ;
                      if(row[i][element] > 1 || column[j][element] > 1 || square[i/3][j/3][element] > 1){
                    return false ;
                }
                }
              
            }
        }
        return true ;
    }
}

2.解数独

题目链接:. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/sudoku-solver/

思路:同样是需要用三个数字去标记元素在相应的行、列、宫内是否出现,在list集合存储i行与j列上的非数字元素下表,遍历数字1-9搜索所有的非数字下表,填充满足要求的数字。

Java版:

class Solution {
    boolean valid = false ;
    List<int []> list = new ArrayList<>() ;
    public void solveSudoku(char[][] board) {
        // dfs搜索加标记的思想
        // 先进行标记,若相应的行、列、宫内出现了数字用数组标记为true,反之标记为false
        // 对于标记为false的,可以传入值进去
        int n = board.length, m = board[0].length ;
        boolean [][] row = new boolean[n][m] ;
        boolean [][] column = new boolean[n][m] ;
        boolean [][][] matrix = new boolean[n/3][m/3][9] ;
    
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(board[i][j] != '.'){
                    int element = board[i][j] - '0'  - 1 ;
                    row[i][element] = true ;
                    column[j][element] = true ;
                    matrix[i/3][j/3][element] = true ;
                }else{
                    list.add(new int []{i,j}) ;
                }
            }
        }
        dfs(board, 0, row, column, matrix) ;
    }
    public void dfs(char [][] board, int k, boolean [][] row, boolean [][] column, boolean [][][] matrix){
        if(k==list.size()){
            // valid = true ;
            return ;
        }
        int i = list.get(k)[0], j = list.get(k)[1] ;
        for(int digit=0; digit<9 && !valid; digit++){
            if(!row[i][digit] && !column[j][digit] && !matrix[i/3][j/3][digit]){
                board[i][j] = (char)(digit + 1 + '0');
                row[i][digit] = column[j][digit] = matrix[i/3][j/3][digit] = true ;
                dfs(board, k+1, row, column, matrix) ;
                // 回溯
                row[i][digit] = column[j][digit] = matrix[i/3][j/3][digit] = false ;
            }

        }
    }
}

3.外观数列

题目链接:. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/count-and-say/description/

思路:外观数列是一种有效数列,由1开始,通过n-1次转换成第n项,每次转换通过统计每个元素的数目,第一个元素相同元素的数目,第二个元素是相同的元素值,通过字符串拼接的思想将数字组合成为外观数列。

class Solution {
    public String countAndSay(int n) {
        String res = "1" ;
        for(int i=2; i<=n; i++){
            // 每次根据当前的数字生成下一个数字
            int left = 0, right = 0 ;
            StringBuilder sb = new StringBuilder("") ;
            // 一次外观数列
            while(right < res.length()){
                // 一次相同数字
                while(right <res.length() && res.charAt(left) == res.charAt(right)){
                    right ++ ;
                }
                sb.append(String.valueOf(right-left)).append(res.charAt(left) ) ;
                left = right ;
            }
            res = sb.toString() ;
        }
        return res ; 
    }
}

4.组合总数

题目链接:. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/combination-sum/description/

思路:随机选择元素中的数字组合成目标数字,数字可以重复选择,但是要保证每次从初始化位置选择,不允许初始化位置之前的元素,不然是认为重复的选择,所以需要用k标志当前初始化选择的位置。

Java版:

class Solution {
    List<Integer> tmp = new ArrayList<>() ;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>() ;
        dfs(res, candidates, target, 0) ;
        return res ;
    }
    public void dfs(List<List<Integer>> res, int [] candidates,  int target, int k){

        if(target == 0){
            res.add(new ArrayList<>(tmp)) ;
            return ;
        }
        if(target < 0){
            return ;
        }
        // 每次从第i个开始选,不允许选择第i个之前的
        for(int i=k; i<candidates.length; i++){
            tmp.add(candidates[i]) ;
            dfs(res, candidates, target - candidates[i], i) ;
            tmp.remove(tmp.size()-1) ;
        }
    }
}

5.组合总数II

题目链接:. - 力扣(LeetCode). - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/combination-sum-ii/

思路:这道题相比较上一道,除了需要考虑每次的搜索位置标记,还要保证搜索到后面的去重问题,所以需要先排序,在搜索过程中遇到重复的组合跳过。

Java版:

class Solution {
    List<Integer> tmp = new ArrayList<>() ;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>() ;
        Arrays.sort(candidates) ;
        dfs(res, candidates, 0, target) ;
        return res ;
    }
    public void dfs(List<List<Integer>> res, int [] candidates, int k, int target){

        if(target == 0){
            res.add(new ArrayList<>(tmp)) ;
            return ;
        }
        if(target < 0){
            return ;
        }
        for(int i=k; i<candidates.length; i++){
            // 避免选到重复的组合
            if(i-1 >=k  && candidates[i] == candidates[i-1]){
                continue ;
            }
            tmp.add(candidates[i]) ;
            dfs(res, candidates, i+1, target - candidates[i]) ;
            tmp.remove(tmp.size() - 1) ;
        }
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/578383.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

深入理解Python协程:从基础到实战

title: 深入理解Python协程&#xff1a;从基础到实战 date: 2024/4/27 16:48:43 updated: 2024/4/27 16:48:43 categories: 后端开发 tags: 协程异步IO并发编程Pythonaiohttpasyncio网络爬虫 第1章&#xff1a;协程基础 1.1 协程概念介绍 协程&#xff08;Coroutines&…

【科学研究】读博:一场精神赌博❓

::: block-1 “时问桫椤”是一个致力于为本科生到研究生教育阶段提供帮助的不太正式的公众号。我们旨在在大家感到困惑、痛苦或面临困难时伸出援手。通过总结广大研究生的经验&#xff0c;帮助大家尽早适应研究生生活&#xff0c;尽快了解科研的本质。祝一切顺利&#xff01;—…

C++必修:类与对象(一)

✨✨ 欢迎大家来到贝蒂大讲堂✨✨ &#x1f388;&#x1f388;养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; 所属专栏&#xff1a;C学习 贝蒂的主页&#xff1a;Betty’s blog 1. 面向过程与面向对象 1.1. 面向过程 我们之前学习的C语言就是一种面向过程的语…

java中http调用组件深入详解

目录 一、前言 二、http调用概述 2.1 什么是http调用 2.1.1 http调用步骤 2.2 HTTP调用特点 2.3 HTTP调用应用场景 三、微服务场景下http调用概述 3.1 微服务开发中http调用场景 3.2 微服务组件中http的应用 四、常用的http调用组件 4.1 java中常用的http组件介绍 4…

用 Python 创建 Voronoi 图

概述 最常见的空间问题之一是找到距离我们当前位置最近的兴趣点 (POI)。假设有人很快就会耗尽汽油&#xff0c;他/她需要在为时已晚之前找到最近的加油站&#xff0c;解决这个问题的最佳解决方案是什么&#xff1f;当然&#xff0c;驾驶员可以检查地图来找到最近的加油站&…

力扣每日一题-总行驶距离-2024.4.25

力扣题目&#xff1a;总行驶距离 题目链接: 2739.总行驶距离 题目描述 代码思路 直接用数学模拟计算即可 代码纯享版 class Solution {public int distanceTraveled(int mainTank, int additionalTank) {int sum 0;while(additionalTank > 0){if(mainTank > 5){mai…

CATO原理中的数学与魔术(六)——Baby Hummer的拓展一

在上一篇中&#xff0c;我们从CATO原理的数学讲解进入了魔术部分&#xff0c;介绍了其经典作品《Baby Hummer》&#xff0c;相关内容请戳&#xff1a; CATO原理中的数学与魔术&#xff08;五&#xff09;——Baby Hummer CATO原理中的数学与魔术&#xff08;四&#xff09;——…

leetcode 221 最大正方形面积

示例 3&#xff1a; 输入&#xff1a;matrix [["0"]] 输出&#xff1a;0 # 最大正方形面积 def max_square(matrix):m len(matrix)n len(matrix[0])if m 0 or n 0::return Nonemax_side 1dp [[0] * (n 1) for _ in range(m 1)]for i in range(1, m 1):fo…

2024全新瀚海跑道:矢量图片迅速养号游戏玩法,每天一小时,日转现200

最初我注意到这种玩法&#xff0c;是因为最近在浏览各大平台的视频时&#xff0c;我发现了一种特殊类型的账号&#xff0c;其养号成功率高达90%。这些账号发布的视频内容和数据非常夸张&#xff0c;而且制作起来非常简单&#xff0c;任何人都可以轻松上手。这些账号主要发布矢量…

Spring Web MVC入门(2)——请求

目录 一、传递单个参数 基础类型和包装类型的区别 1、基础类型 &#xff08;1&#xff09;不传参 &#xff08;2&#xff09;传字符串 2、包装类型 &#xff08;1&#xff09;不传参 &#xff08;2&#xff09;传字符串 3、小结 二、传递多个参数 三、传递对象 四、…

Leetcode_相交链表

✨✨所属专栏&#xff1a;LeetCode刷题专栏✨✨ ✨✨作者主页&#xff1a;嶔某✨✨ 题目&#xff1a; 题解&#xff1a; 看到这个题目首先我们要排除链表逆置的想法&#xff0c;如图、因为c1节点只有一个next指针&#xff0c;逆置后不可能同时指向a2和b3节点。 其次有的的同学…

阿里前端常考vue面试题汇总_阿里高级vue面试题

改变 ![](https://img-blog.csdnimg.cn/img_convert/b736620bcd29f08f3685022ab5583d8b.webp?x-oss-processimage/format,png)你会发现&#xff0c; **只有改变的栏目才闪烁&#xff0c;也就是进行重绘** &#xff0c;数据没有改变的栏目还是保持原样&#xff0c;这样就大大节…

WebSocket 深入浅出

WebSocket 深入浅出 1. WebSocket 是什么2. WebSocket 建立连接通信的过程3. WebSocket 和http的联系与区别4. WebSocket 的使用场景及限制 1. WebSocket 是什么 定义&#xff1a;WebSocket 是一种网络通信协议&#xff0c;它允许在单个TCP连接上进行全双工通信。是HTML5规范提…

网络安全实训Day15

写在前面 电子垃圾&#xff0c;堂堂恢复连载。本来不想分天数梳理了&#xff0c;但是最后要写实训报告&#xff0c;报告里还要有实训日记记录每日学的东西&#xff0c;干脆发这里留个档&#xff0c;到时候写报告提供一个思路。 网络空间安全实训-渗透测试 渗透测试概述 定义 一…

关于conda占C盘内存的问题

文章目录 前言一、C盘中.conda文件中的envs二、C盘中.conda文件中的pkgs 前言 最近发现C盘空间越来越少&#xff0c;于是就去清理了一下conda在C盘的存储&#xff0c;不看不知道&#xff0c;一看吓一跳&#xff0c;足足十几G&#xff01;于是去网上搜索了相关的包能不能删除&a…

(3)C程序可执行文件的生成过程

原文链接&#xff1a;https://www.jianshu.com/p/b7e44f749211 一、可执行文件的生成 我们先通过一个简单C程序&#xff0c;回顾一下可执行文件的生成过程。 ​​​​​​​ ​​​​​​​ 可执行文件的生成过程如下图&#xff1a; 如图&#xff0c;可执行文…

------分割线之 WebSecurityConfigrerAdapter弃用问题------

WebSecurityConfigurerAdapter 被弃用的原因是 Spring Security 项目的维护者希望将项目的主要开发工作集中在新的配置方式上&#xff0c;即基于 Java 的配置&#xff08;Java Configuration&#xff09;和基于 Lambda 的表达式。这主要是因为 Spring 5.0 引入了重量级的 Java …

Windows系统下使用MySQL8.0.22创建第二套数据库

配置新的 MySQL 实例&#xff1a; 为了创建一个新的数据库实例&#xff0c;你需要复制 MySQL 的安装目录并创建一个新的数据目录和配置文件。假设你已经安装了 MySQL 在 C:\Program Files\MySQL\ 下&#xff0c;按照以下步骤操作&#xff1a; 复制整个 MySQL 文件夹&#xff0c…

【探索Java编程:从入门到入狱】Day2

&#x1f36c; 博主介绍&#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 hacker-routing &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【应急响应】 【Java、PHP】 【VulnHub靶场复现】【面试分析】 &#x1f389;点赞➕评论➕收…

STM32 USB HID报告描述符没有报告长度

STM32 USB HID设置(STM32CubeMX)_我也想成大侠的博客-CSDN博客 不影响鼠标功能