力扣热门算法题 75. 颜色分类,76. 最小覆盖子串,77. 组合

75. 颜色分类,76. 最小覆盖子串,77. 组合,每题做详细思路梳理,配套Python&Java双语代码, 2024.03.21 可通过leetcode所有测试用例。

目录

75. 颜色分类

解题思路

完整代码

Python

Java

76. 最小覆盖子串

解题思路

完整代码

Python

Java

77. 组合

解题思路

完整代码

Python

Java


75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1:

输入:nums = [2,0,2,1,1,0]
输出:[0,0,1,1,2,2]

示例 2:

输入:nums = [2,0,1]
输出:[0,1,2]

提示:

  • n == nums.length
  • 1 <= n <= 300
  • nums[i] 为 01 或 2

解题思路

其核心思想是使用三个指针来分别跟踪 0、1 和 2。我们可以将数组中的元素分为三部分:红色区(0),白色区(1),以及蓝色区(2)。以下是具体的步骤:

  1. 初始化三个指针lowmidhighlow 指针跟踪红色区的最后一个元素的下一个位置,mid 指针用于遍历整个数组,high 指针跟踪蓝色区的第一个元素的前一个位置。初始时,lowmid 都设置为数组的起始位置,high 设置为数组的末尾位置。

  2. 遍历数组:当 mid 指针小于等于 high 指针时,进行遍历:

    • 如果 nums[mid] 等于 0(红色),则将其与 nums[low] 交换,并将 lowmid 指针都向前移动一位。
    • 如果 nums[mid] 等于 1(白色),则不需要交换,只需将 mid 指针向前移动一位。
    • 如果 nums[mid] 等于 2(蓝色),则将其与 nums[high] 交换,并将 high 指针向后移动一位。此时不移动 mid 指针,因为交换后的元素还未被检查。
  3. 重复步骤 2,直到 mid 指针超过 high 指针。

完整代码

Python
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        low, mid, high = 0, 0, len(nums) - 1

        while mid <= high:
            if nums[mid] == 0:
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 1:
                mid += 1
            else:
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1
Java
class Solution {
    public void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;

        while (mid <= high) {
            switch (nums[mid]) {
                case 0:
                    // 交换 low 和 mid 的值
                    int temp = nums[low];
                    nums[low] = nums[mid];
                    nums[mid] = temp;
                    low++;
                    mid++;
                    break;
                case 1:
                    mid++;
                    break;
                case 2:
                    // 交换 mid 和 high 的值
                    temp = nums[mid];
                    nums[mid] = nums[high];
                    nums[high] = temp;
                    high--;
                    break;
            }
        }
    }
}

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。

注意:

  • 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串,我们保证它是唯一的答案。

示例 1:

输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2:

输入:s = "a", t = "a"
输出:"a"
解释:整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中,
因此没有符合条件的子字符串,返回空字符串。

解题思路

我们可以使用滑动窗口的方法。基本思想是使用两个指针 leftright 来表示 s 中的一个窗口,并在这个窗口中寻找包含 t 所有字符的最小子串。这个过程分为几个步骤:

  1. 初始化:创建两个哈希表,一个用于存储字符串 t 中字符的频率(称为 need),另一个用于存储当前窗口中字符的频率(称为 window)。还需要两个指针 leftright 表示当前窗口的左右边界,初始化为 0。定义 valid 变量来记录窗口中满足 need 条件的字符数量。

  2. 扩大窗口:移动右指针 right 扩大窗口,直到窗口中包含了 t 的所有字符。

  3. 更新结果:当窗口包含了 t 的所有字符后,尝试移动左指针 left 缩小窗口,同时更新最小子串的长度和起始位置。如果当前窗口的长度小于之前找到的最小子串长度,更新最小子串长度和起始位置。

  4. 缩小窗口:继续移动左指针 left 缩小窗口,直到窗口不再满足 t 的所有字符。此时再次扩大窗口,重复步骤 2 和 3。

  5. 返回结果:根据记录的最小子串起始位置和长度返回最终结果。

完整代码

Python
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import Counter
        need, window = Counter(t), {}
        left = right = 0
        valid = 0
        start, length = 0, float('inf')
        
        while right < len(s):
            # c 是将移入窗口的字符
            c = s[right]
            # 右移窗口
            right += 1
            # 进行窗口内数据的一系列更新
            if c in need:
                window[c] = window.get(c, 0) + 1
                if window[c] == need[c]:
                    valid += 1
            
            # 判断左侧窗口是否要收缩
            while valid == len(need):
                # 更新最小覆盖子串
                if right - left < length:
                    start = left
                    length = right - left
                # d 是将移出窗口的字符
                d = s[left]
                # 左移窗口
                left += 1
                # 进行窗口内数据的一系列更新
                if d in need:
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
        
        return "" if length == float('inf') else s[start:start+length]
Java
class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) need.put(c, need.getOrDefault(c, 0) + 1);

        int left = 0, right = 0;
        int valid = 0;
        int start = 0, length = Integer.MAX_VALUE;
        
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(need.get(c))) valid++;
            }

            while (valid == need.size()) {
                if (right - left < length) {
                    start = left;
                    length = right - left;
                }
                char d = s.charAt(left);
                left++;
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) valid--;
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        
        return length == Integer.MAX_VALUE ? "" : s.substring(start, start + length);
    }
}

 

77. 组合

给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1:

输入:n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2:

输入:n = 1, k = 1
输出:[[1]]

解题思路

我们可以使用回溯法,这是一种通过探索所有可能的候选解来找出所有解的解决方案的算法。当搜索到一个可能解时,回溯法会先记录下这个解,然后撤销到上一步状态,尝试另一种选择,继续探索直到所有的选择都尝试过了。以下是具体的步骤:

  1. 定义回溯函数:创建一个回溯函数 backtrack,它接受当前的组合 combination 和下一个要添加到组合中的数字 start

  2. 递归的终止条件:当 combination 的长度等于 k 时,将其添加到结果列表中,然后返回。

  3. 遍历所有可能的选择:从 startn 遍历所有可能的数字。对于每一个数字,将其添加到当前组合中,然后递归地调用 backtrack 函数进入下一层。

  4. 回溯:递归调用返回后,撤销上一步的操作,即从 combination 中移除上一步添加的数字,尝试下一个可能的数字。

  5. 调用回溯函数并返回结果:初始化一个空列表来存储所有可能的组合,然后从数字 1 开始调用回溯函数。

完整代码

Python
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        combination = []

        def backtrack(start):
            if len(combination) == k:
                result.append(combination[:])
                return
            for i in range(start, n + 1):
                combination.append(i)
                backtrack(i + 1)
                combination.pop()

        backtrack(1)
        return result
Java
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> combination = new ArrayList<>();

        void backtrack(int start) {
            if (combination.size() == k) {
                result.add(new ArrayList<>(combination));
                return;
            }
            for (int i = start; i <= n; i++) {
                combination.add(i);
                backtrack(i + 1);
                combination.remove(combination.size() - 1);
            }
        }

        backtrack(1);
        return result;
    }
}

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

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

相关文章

六.排序nb三人组(快速排序)

目录 17-快速排序原理介绍 思路: 18-快速排序代码实现 19-快速排序代码实现2 缺点: 递归的限度: 17-快速排序原理介绍 思路: --先找一个变量把 5(第一个数) 存起来, (两个箭头分别是left , right) --左边有一个空位, 发现左边的位置是给比5小的值准备的. --找比5小的值…

校招应聘流程讲解

在整个应聘流程中&#xff0c;记得保持积极的态度、认真准备面试&#xff0c;同时也要对自己的能力和经验有清晰的认识&#xff0c;这样才能在竞争激烈的校园招聘中脱颖而出&#xff0c;成功获得心仪的工作机会. 1. 校招资源获取 想要参加校招&#xff0c;首先需要获取校招资…

ROS2从入门到精通0-3:VSCode 搭建 ROS2 工程环境

目录 0 专栏介绍1 Ubuntu下安装VSCode1.1 基本安装1.2 将VSCode添加到侧边栏 2 VSCode集成相关插件3 VSCode运行ROS2环境步骤3.1 安装编译依赖项3.2 创建工作空间和源码空间3.3 启动VSCode与配置 4 测试工程环境4.1 C版本4.2 Python版本 0 专栏介绍 本专栏旨在通过对ROS2的系统…

每日一题 --- 977. 有序数组的平方[力扣][Go]

今天这一题和昨天的知识点是一样的&#xff0c;就是双指针法。 题目&#xff1a; 给你一个按 非递减顺序 排序的整数数组 nums&#xff0c;返回 每个数字的平方 组成的新数组&#xff0c;要求也按 非递减顺序 排序。 示例 1&#xff1a; 输入&#xff1a;nums [-4,-1,0,3,1…

Java中调用由C/C++实现的本地库(JNI本地程序调用)

文章目录 背景介绍什么是JNI&#xff1f;什么是本地库&#xff1f;开发Java使用JNI本地库步骤 编写Java类实现JNI本地调用windows系统下编译动态链接库创建Java项目&#xff08;demo&#xff09;第一步&#xff1a;编写带有native的Java类第二步&#xff1a;javac生成NativeDem…

深度学习_微调_7

目标 微调的原理利用微调模型来完成图像的分类任务 微调的原理 微调&#xff08;Fine-tuning&#xff09;是一种在深度学习中广泛应用的技术&#xff0c;特别是在预训练模型&#xff08;Pretrained-Models&#xff09;的基础上进行定制化训练的过程。微调的基本原理和步骤如下…

CRM软件推荐2024:五款顶级产品解析,助您找到最佳选项!

一天之计在于晨&#xff0c;一年之计在于春。 2024年&#xff0c;民营经济发展继续壮大&#xff0c;这对于各行各业而言都是一种机遇挑战。企业想要规范化客户管理&#xff0c;实现销售增长&#xff0c;CRM软件仍然是一个不错的选择。在数字化时代&#xff0c;企业数字化转型已…

预防颈椎病,从职场健康做起

随着现代社会工作方式的转变&#xff0c;职场人士长时间伏案工作&#xff0c;颈椎病的发病率逐渐上升。本文将介绍一些实用的预防颈椎病的方法&#xff0c;帮助职场人士保持健康&#xff0c;提高工作效率。 一、了解颈椎病 颈椎病是指颈椎间盘退行性变及其继发性椎间关节病理性…

基于Python实现高德地图找房系统-爬虫分析

概要 针对大学毕业生对于工作地周边交通出行情况不了解、租房困难等问题,本文主要研究了厦门市的租房信息及地铁公交出行路线,利用Python爬虫爬取58同城上厦门市的租房信息,并进行处理分析,再通过高德地图API将房源信息展示在地图上,实现了基于高德地图API的租房地图。 关键词&…

基于Spring Boot技术的幼儿园管理系统

摘 要 随着信息时代的来临&#xff0c;过去的传统管理方式缺点逐渐暴露&#xff0c;对过去的传统管理方式的缺点进行分析&#xff0c;采取计算机方式构建幼儿园管理系统。本文通过课题背景、课题目的及意义相关技术&#xff0c;提出了一种活动信息、课程信息、菜谱信息、通知公…

Angular入门问题小本本

1、console.log打印object对象显示[object object] 解决方案&#xff1a;使用JSON.stringify console.log(JSON.stringify($rootScope.MaintainDeviceInfo));2、 State ‘goDiskManagement’’ is already defined 解决方案&#xff1a;同一个项目中&#xff0c;不能定义相同…

基于骨骼的动作识别的行动结构图卷积网络

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 摘要Abstract文献阅读&#xff1a;基于骨骼的动作识别的行动结构图卷积网络1、研究背景2、方法提出3、关键结构3.1、A-links inference module (AIM)3.2、Structura…

MyBatis3源码深度解析(二十)动态SQL实现原理(一)动态SQL的核心组件

文章目录 前言第八章 动态SQL实现原理8.1 动态SQL的使用8.1.1 \<if>8.1.2 <where|trim>8.1.3 <choose|when|otherwise>8.1.4 \<foreach>8.1.5 \<set> 8.2 SqlSource组件&BoundSql组件8.3 LanguageDriver组件8.3.1 XMLLanguageDriver8.3.2 Ra…

leetcode 20.有效的括号 JAVA

题目 思路 括号的匹配&#xff0c;这是一道经典的栈的应用问题。 给我们一个字符串&#xff0c;当我们遍历到左括号时&#xff0c;让其入栈。当我们遍历到右括号时&#xff0c;让栈顶元素出栈&#xff0c;看看栈顶的元素是否和遍历到的右括号匹配。不匹配的话直接false,匹配的…

vue2 脚手架

安装 文档&#xff1a;https://cli.vuejs.org/zh/ 第一步&#xff1a;全局安装&#xff08;仅第一次执行&#xff09; npm install -g vue/cli 或 yarn global add vue/cli 备注&#xff1a;如果出现下载缓慢&#xff1a;请配置npm 淘宝镜像&#xff1a; npm config set regis…

java算法第32天 | ● 122.买卖股票的最佳时机II ● 55. 跳跃游戏 ● 45.跳跃游戏II

122.买卖股票的最佳时机II 本题中理解利润拆分是关键点&#xff01; 不要整块的去看&#xff0c;而是把整体利润拆为每天的利润。假如第 0 天买入&#xff0c;第 3 天卖出&#xff0c;那么利润为&#xff1a;prices[3] - prices[0]。 相当于(prices[3] - prices[2]) (prices[…

XSS-labs详解

xss-labs下载地址https://github.com/do0dl3/xss-labs 进入靶场点击图片&#xff0c;开始我们的XSS之旅&#xff01; Less-1 查看源码 代码从 URL 的 GET 参数中取得 "name" 的值&#xff0c;然后输出一个居中的标题&#xff0c;内容是 "欢迎用户" 后面…

手撕算法-买卖股票的最佳时机 II(买卖多次)

描述 分析 使用动态规划。dp[i][0] 代表 第i天没有股票的最大利润dp[i][1] 代表 第i天持有股票的最大利润 状态转移方程为&#xff1a;dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]); // 前一天没有股票&#xff0c;和前一天有股票今天卖掉的最大值dp[i][1] max(dp[i-1…

智能财务新选择!Zoho Books入选福布斯榜单,助力中小企业!

放眼全球&#xff0c;中小企业始终是经济发展的重要组成部分。然而&#xff0c;由于中小企业的规模、流程规范和资源等方面受限较多&#xff0c;从而导致其在管理及运营上存在着诸多问题。其中包括财务管理不规范、成本控制不到位、运营效率低下等&#xff0c;这些问题则直接影…

如何在CentOS安装SQL Server数据库并实现无公网IP远程连接内网数据库

文章目录 前言1. 安装sql server2. 局域网测试连接3. 安装cpolar内网穿透4. 将sqlserver映射到公网5. 公网远程连接6.固定连接公网地址7.使用固定公网地址连接 前言 简单几步实现在Linux centos环境下安装部署sql server数据库&#xff0c;并结合cpolar内网穿透工具&#xff0…