每日5题Day8 - LeetCode 36 - 40

每一步向前都是向自己的梦想更近一步,坚持不懈,勇往直前!

第一题:36. 有效的数独 - 力扣(LeetCode)

题目要求我们进行判断,我们不需要自己填写,所以要一个标志位,来看当前的值是否在行、列、格中出现过,每当这时候可以考虑使用位掩码。

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[] line = new int[9];// 行
        int[] col = new int[9];// 列
        int[] cell = new int[9];// 9宫格
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                // 如果当前位置没有数字,不用判断。
                if (board[i][j] == '.')
                    continue;
                //使用位掩码来记录数字
                int shift = 1 << (board[i][j] - '0');// 确定第几位
                int k = (i / 3) * 3 + j / 3;// 9宫格的第几个。
                // 如果对应的位置只要有一个被标记过,说明有冲突,直接返回false。
                //&与要求两边完全相同才大于0,下面这一步在判断是否有相同数字出现过
                if ((col[i] & shift) > 0 || (line[j] & shift) > 0
                        || (cell[k] & shift) > 0)
                    return false;
                // 把当前位置所在的行,列以及9宫格都标记为该数字已经存在。
                //或|只要某一位是1,则都是1,所以不管原来的col[i]等是否为0,
                //反正判断的时候还是判断col[i] & shift,所以下面这样写正确
                //建议自己手动模拟一下
                col[i] |= shift;
                line[j] |= shift;
                cell[k] |= shift;
            }
        }
        return true;
    }
}

第二题:37. 解数独 - 力扣(LeetCode)

class Solution {
    //类似于dfs,要找到刚好唯一一组解,可能会涉及到已经放入的值回退的情况
    //直接使用空间换时间了,不回退直接判断可不可以放,注意看两层循环那个
    //if-for-return的逻辑:如果是'.' 那么能不能放数字,如果放了就继续,否则return false
    //再注意看for循环里的逻辑,判断这个数字放进去满足数独不,所以有一个isValidSudoku的判断函数
    public void solveSudoku(char[][] board) {
        solveSudokuHelper(board);
    }
    private boolean solveSudokuHelper(char[][] board){
        for (int i = 0; i < 9; i++){ // 遍历行
            for (int j = 0; j < 9; j++){ // 遍历列
                if (board[i][j] != '.'){ // 跳过原始数字
                    continue;
                }
                for (char k = '1'; k <= '9'; k++){ // (i, j) 这个位置放k是否合适
                    if (isValidSudoku(i, j, k, board)){
                        board[i][j] = k;
                        if (solveSudokuHelper(board)){ // 如果找到合适一组立刻返回
                        //注意这个地方的判断,潜逃了两层true的判断
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
        return true;
    }
    private boolean isValidSudoku(int row, int col, char val, char[][] board){
        //分别判断行列格里是否存在相同元素
        for (int i = 0; i < 9; i++){
            if (board[row][i] == val){
                return false;
            }
        }
        for (int j = 0; j < 9; j++){
            if (board[j][col] == val){
                return false;
            }
        }
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++){
            for (int j = startCol; j < startCol + 3; j++){
                if (board[i][j] == val){
                    return false;
                }
            }
        }
        return true;
    }
}

第三题:38. 外观数列 - 力扣(LeetCode)

public class Solution {
    // countAndSay 方法用于生成一个特定的字符串序列。
    // 序列的第 n 项是通过将第 n-1 项字符串中的连续相同字符进行计数和描述来生成的。
    public static String countAndSay(int n) {
        // 递归出口:如果 n 为 1,则返回字符串 "1",这是序列的第一项。
        if (n == 1) {
            return "1";
        }
        // 递归调用:如果 n 大于 1,则先递归调用 countAndSay(n - 1) 生成第 n-1 项,
        // 然后调用 transfer 方法将第 n-1 项转换为第 n 项。
        return transfer(countAndSay(n - 1));
    }

    // transfer 方法接受一个字符串 s 作为输入,并生成下一个字符串。
    // 它通过计数 s 中连续出现的相同字符,并将计数和字符拼接起来形成新的字符串。
    public static String transfer(String s) {
        StringBuilder sb = new StringBuilder(); // 使用 StringBuilder 来构建最终的字符串。
        int count = 1; // 初始化计数器,用于计数连续相同字符的数量。
        int length = s.length(); // 获取输入字符串的长度。
        int i;
        char temp = s.charAt(0); // 初始化临时变量 temp 为字符串的第一个字符。

        // 遍历输入字符串 s。
        for (i = 1; i <= length; i++) {
            // 如果当前字符 temp 与 s.charAt(i) 相同,继续计数。
            while (i < length && temp == s.charAt(i)) {
                count++; // 连续字符计数加 1。
                i++; // 移动到下一个字符。
            }
            // 如果 i < length,说明找到了不同的字符,更新 temp。
            if (i < length) {
                temp = s.charAt(i);
            }
            // 将当前字符的计数和字符本身添加到 StringBuilder 中。
            sb.append(count); // 添加计数。
            sb.append(s.charAt(i - 1)); // 添加字符本身。
            // 重置计数器,为下一个字符的计数做准备。
            count = 1; 
        }
        // 返回构建好的字符串。
        return sb.toString();
    }
}

第四题:39. 组合总和 - 力扣(LeetCode)

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //为了避免排列的重复情况出现,所以我们先进行排序
        Arrays.sort(candidates);
        traversal(0, target, candidates);
        return res;
    }

    private void traversal(int start, int target, int[] candidates){
        //把满足条件的提出来
        if(target == 0){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = start; i < candidates.length; i++){
            //对于每一个candidate进行遍历,因为我们升序排列了,所以一旦选过了,
            //就不会再回去,就避免了排列情况的发生,实际上变为了组合
            if(target - candidates[i] >= 0){
                path.add(candidates[i]);
                traversal(i, target - candidates[i], candidates);
                //记得回溯
                path.remove(path.size() - 1);
            }else{
                //注意给一个边界条件,如果不满足了就退出
                break;
            }
        }
    }
}

 第五题:40. 组合总和 II - 力扣(LeetCode)


class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates); // 对数组进行排序
        List<List<Integer>> res = new ArrayList<>();
        //因为每个候选人数字只能出现一次,所以我们与上一题不同的地方是要多加入一个标记数组
        backtrack(candidates, target, 0, new ArrayList<>(), res, new boolean[candidates.length]);
        return res;
    }
 
    private void backtrack(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> res, boolean[] used) {
        if (target == 0) {
            res.add(new ArrayList<>(path)); // 找到一种组合
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            // 本质来说,这题有重复元素的排列导致的结果重复的问题,必须去重
            // 跳过重复的元素,注意这种去重的方式(避免上一行提到的情况)
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            // 如果当前元素大于剩余目标,直接返回
            //注意边界条件
            if (candidates[i] > target) {
                break;
            }
            // 使用当前元素
            if (!used[i]) {
                used[i] = true; // 标记为已使用
                path.add(candidates[i]); // 添加到路径
                backtrack(candidates, target - candidates[i], i + 1, path, res, used); // 递归调用
                path.remove(path.size() - 1); // 回溯,移除当前元素
                used[i] = false; // 重置为未使用
            }
        }
    }
}

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

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

相关文章

LLM——探索大语言模型在心理学方面的应用研究

1. 概述 心理学经历了多次理论变革&#xff0c;目前人工智能&#xff08;AI&#xff09;和机器学习&#xff0c;特别是大型语言模型&#xff08;LLMs&#xff09;的使用&#xff0c;预示着新研究方向的开启。本文详细探讨了像ChatGPT这样的LLMs如何转变心理学研究。它讨论了LL…

从旅游广告联想到《桃花源记》

近日收到《长江头条网》等知名网络自媒体相邀,促我写点儿旅游题材的文案。虽说笔者游历过许多名山大川的绝美风景区,但那是在70岁之前的事儿了。如今年逾78岁,纵使有少许自有资本能够支持出游,可体力难撑,岂不是花钱买罪受吗?而且,写没有亲身经历过的事挺难,即便发表出…

台灯的功能作用有哪些?护眼台灯真的护眼吗?

现在的学生会长时间使用平板、手机、电脑等&#xff0c;这些设备的屏幕会产生一定的频闪和蓝光辐射&#xff0c;也就会影响视力健康&#xff0c;而护眼养眼也成了家长关注的问题&#xff0c;视力疲劳和眼部疾病不仅影响个体的生活质量&#xff0c;还可能导致长期的健康问题。当…

装修:尽显个性品味

家&#xff0c;是心灵的港湾&#xff0c;也是生活的舞台。装修&#xff0c;不仅是对空间的改造&#xff0c;更是对生活态度的诠释。无论是温馨的北欧风&#xff0c;还是华丽的欧式古典&#xff0c;或是简约的现代感&#xff0c;我们的专业团队都能为您量身打造。每一个细节&…

力扣--哈希表13.罗马数字转整数

首先我们可以知道&#xff0c;一个整数&#xff0c;最多由2个罗马数字组成。 思路分析 这个方法能够正确将罗马数字转换为阿拉伯数字的原因在于它遵循了罗马数字的规则&#xff0c;并且对这些规则进行了正确的编码和处理。 罗马数字规则 罗马数字由以下字符组成&#xff1a…

如何使用ffmpeg 实现10种特效

相关特效的名字 特效id 特效名 1 向上移动 2 向左移动 3 向下移动 4 颤抖 5 摇摆 6 雨刷 7 弹入 8 弹簧 9 轻微跳动 10 跳动 特效展示(同时汇总相关命令) pad背景显示 pad背景透明 相关命令(一会再讲这些命令&#xff0c;先往下看) # 合成特效语音 ffmpeg -y -loglevel erro…

Pandas高效数据清洗与转换技巧指南【数据预处理】

三、数据处理 1.合并数据&#xff08;join、merge、concat函数&#xff0c;append函数&#xff09; Concat()函数使用 1.concat操作可以将两个pandas表在垂直方向上进行粘合或者堆叠。 join属性为outer&#xff0c;或默认时&#xff0c;返回列名并集&#xff0c;如&#xff…

day34 贪心算法 455.分发饼干 376. 摆动序列

贪心算法理论基础 贪心的本质是选择每一阶段的局部最优&#xff0c;从而达到全局最优。 贪心一般解题步骤&#xff08;贪心无套路&#xff09;&#xff1a; 将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解 455.分发饼干 …

2024年最全的信息安全、数据安全、网络安全标准分享(可下载)

以上是资料简介和目录&#xff0c;如需下载&#xff0c;请前往星球获取&#xff1a;https://t.zsxq.com/Gz1a0

Unity3D雨雪粒子特效(Particle System)

系列文章目录 unity工具 文章目录 系列文章目录&#x1f449;前言&#x1f449;一、下雨的特效1-1.首先就是创建一个自带的粒子系统,整几张贴图,设置一下就能实现想要的效果了1-2 接着往下看视频效果 &#x1f449;二、下雪的特效&#x1f449;三、下雪有积雪的效果3-1 先把控…

基于Android studio 订餐、外卖系统

目录 项目介绍 图片展示 运行环境 获取方式 项目介绍 具有登录&#xff0c;注册&#xff0c;修改密码&#xff0c;查看关于开发信息(可以填写自己的信息) 我的&#xff1a;可以查看菜品详情&#xff0c;填写份数&#xff0c;加入购物车&#xff0c; 购物车&#xff1a;可…

ElasticSearch操作之重置密码脚本

ElasticSearch操作之重置密码脚本 #!/bin/bash # 使用样例 ./ES密码重置.sh 旧密码 新密码# 输入旧密码 es_old_password$1# 设置新的密码变量 es_password$2# 正确响应 es_reponse{"acknowledged":true}# 检查Elasticsearch是否在运行 if pgrep -f elasticsearch &g…

Java订餐系统源码 springboot点菜系统源码

Java订餐系统源码 springboot点菜系统源码 源码下载地址&#xff1a;https://download.csdn.net/download/xiaohua1992/89341358 功能介绍&#xff1a; 前台登录&#xff1a;前台登录&#xff1a; ①首页&#xff1a;菜品信息推荐、菜品信息展示、查看更多 ②菜品信息&…

IPIDEA与您分享:代理IP究竟是如何保护用户隐私的?

在信息化、网络化的今天&#xff0c;互联网已成为人们生活中不可或缺的一部分。无论是日常沟通、学习工作&#xff0c;还是娱乐休闲&#xff0c;网络都扮演着举足轻重的角色。然而&#xff0c;随着网络活动的增加&#xff0c;网络安全问题也日益凸显&#xff0c;为了保护个人隐…

Vue速成学习笔记

这两天速成了一下Vue&#xff0c;在这里记录一下相关的笔记&#xff0c;之后有时间详细学Vue的时候再来回顾一下&#xff01; 一、Vue理解 1、Vue的核心特征&#xff1a;双向绑定。 在网页中&#xff0c;存在视图和数据。在Vue之前&#xff0c;需要使用JavaScript编写复杂的逻…

vue 打印、自定义打印、页面打印、隐藏页眉页脚

花了一天时间搞了个打印功能&#xff0c;现则将整体实现过程进行整理分享。先来看看效果图&#xff1a; 1、页面展示为&#xff1a; 2、重组页面打印格式为&#xff1a;这里重组页面的原因是客户要求为一行两列打印 &#xff01;内容过于多的行则独占一行显示完整。 整体实现&…

「探讨」:什么是网络审计?好用的网络审计系统推荐【图文详解】

网络是企业运营、政府管理、个人生活不可或缺的基础设施。 然而网络安全问题却日益凸显&#xff0c;数据泄露、网络攻击、欺诈行为等风险日益严重。 一、网络审计的定义 网络审计&#xff0c;又称信息技术审计或电子审计&#xff0c;是指审计人员运用专业技能和工具&#xff…

给我瞅瞅呀

专业 流程&#xff08;一条龙服务&#xff09; 需求沟通-需求分析-产品架构-ue原型-ui设计-产品研发-产品测试-产品交付-产品运维 保障 1、按需定制&#xff0c;签订功能清单&#xff0c;根据功能报价 2、价格透明&#xff0c;签订合同保障&#xff0c;保障客户合法权益 3、源…

智慧校园建设的进阶之路

智慧校园的建设现已到达了老练的阶段&#xff0c;许多学校设备充满着数字化信息&#xff0c;进出宿舍楼&#xff0c;校园一卡通体系会记载下学生信息&#xff0c;外来人员闯入会报警&#xff0c;翻开电脑就能查到学生是否在宿舍等……学生的学习和日子都充满了数字化的痕迹。但…

全域运营是本地生活服务的新模式吗?

最近&#xff0c;本地生活赛道又出现了一个新的说法&#xff0c;即全域运营是本地生活的下半场。事实上&#xff0c;这一论断并非空穴来风&#xff0c;而是有真凭实据。 作为多家互联网大厂重点布局的业务板块&#xff0c;本地生活的火爆程度早已有目共睹。根据多家互联网大厂…