代码随想录算法训练营第二十天
LeetCode题目:
- 39. 组合总和
- 40. 组合总和 II
- 131. 分割回文串
- 2176. 统计数组中相等且可以被整除的数对(每日一题)
其他:
今日总结
往期打卡
39. 组合总和
跳转: 39. 组合总和
学习: 代码随想录公开讲解
问题:
给你一个 无重复元素 的整数数组 candidates
和一个目标整数 target
,找出 candidates
中可以使数字和为目标数 target
的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates
中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为 target
的不同组合数少于 150
个。
思路:
回溯,可以当成组合问题一次一次的选,也可以每个元素多次的选(不过效率不高).
复杂度:
- 时间复杂度: O ( 2 n ) O(2^n) O(2n)
- 空间复杂度: O ( n 2 ) O(n^2) O(n2)
代码(一层选一个):
class Solution {List<List<Integer>> ans;private final List<Integer> path = new ArrayList<>();int target;void dfs(int[] candidates, int sum,int index){if(sum>target) return;if(sum==target) ans.add(new ArrayList<>(path));for(int i=index;i<candidates.length;i++){path.add(candidates[i]);dfs(candidates,sum+candidates[i],i);path.remove(path.size()-1);}}public List<List<Integer>> combinationSum(int[] candidates, int target) {ans = new ArrayList<>();this.target = target;dfs(candidates,0,0);return ans;}
}
代码(每个选0-n次):
class Solution {List<List<Integer>> ans;int target;int[] candidates;private final List<Integer> path = new ArrayList<>();int n;void dfs(int index,int value){if(value>target) return;if(value == target){ans.add(new ArrayList<>(path));return;}if(index<0) return;int sum = 0;while(sum+value<=target){dfs(index-1,value+sum);path.add(candidates[index]);sum+=candidates[index];}int count = sum/candidates[index];path.removeAll(path.subList(path.size()-sum/candidates[index],path.size()));}public List<List<Integer>> combinationSum(int[] candidates, int target) {ans = new ArrayList<>();this.target = target;this.candidates = candidates;n = candidates.length;dfs(n-1,0);return ans;}
}
40. 组合总和 II
跳转: 40. 组合总和 II
学习: 代码随想录公开讲解
问题:
给定一个候选人编号的集合 candidates
和一个目标数 target
,找出 candidates
中所有可以使数字和为 target
的组合。
candidates
中的每个数字在每个组合中只能使用 一次 。
**注意:**解集不能包含重复的组合。
思路:
每层同种元素只能选一个,为了更好的分辨同种元素,可以先排序
复杂度:
- 时间复杂度: O ( n 2 ) O(n^2) O(n2)
- 空间复杂度: O ( n ) O(n) O(n)
代码(回溯):
class Solution {List<List<Integer>> ans;private final List<Integer> path = new ArrayList<>();int target;void dfs(int[] candidates, int sum, int index) {if (sum == target) {ans.add(new ArrayList<>(path));return;}for (int i = index; i < candidates.length; i++) {if (sum + candidates[i] > target) {break;}if (i > index && candidates[i] == candidates[i - 1]) {continue;}path.add(candidates[i]);dfs(candidates, sum + candidates[i], i + 1);path.remove(path.size() - 1);}}public List<List<Integer>> combinationSum2(int[] candidates, int target) {ans = new ArrayList<>();Arrays.sort(candidates);// System.out.println(Arrays.toString(candidates));this.target = target;dfs(candidates, 0, 0);return ans;}
}
131. 分割回文串
跳转: 131. 分割回文串
学习: 代码随想录公开讲解
问题:
给你一个字符串 s
,请你将 s
分割成一些 子串,使每个子串都是 回文串 。返回 s
所有可能的分割方案。
思路:
在回文串位置切割,切割到最后一个位置时返回
复杂度:
- 时间复杂度: O ( n 3 ) O(n^3) O(n3)
- 空间复杂度: O ( n 2 ) O(n^2) O(n2)
代码:
class Solution {List<List<String>> ans;List<String> path = new ArrayList<>();void dfs(String s,int startIndex){if(startIndex==s.length()){ans.add(new ArrayList<>(path));}for(int i=startIndex+1;i<=s.length();i++){if(isPalindrome(s,startIndex,i-1)){path.add(s.substring(startIndex,i));}else continue;dfs(s,i);path.remove(path.size()-1);}}boolean isPalindrome(String s,int startIndex,int endIndex){while(startIndex<endIndex){if(s.charAt(startIndex++)!=s.charAt(endIndex--)) return false;}return true;}public List<List<String>> partition(String s) {ans = new ArrayList<>();dfs(s,0);return ans;}
}
2176. 统计数组中相等且可以被整除的数对(每日一题)
跳转: 2176. 统计数组中相等且可以被整除的数对
问题:
给你一个下标从 0 开始长度为 n
的整数数组 nums
和一个整数 k
,请你返回满足 0 <= i < j < n
,nums[i] == nums[j]
且 (i * j)
能被 k
整除的数对 (i, j)
的 数目 。
思路:
直接两层for循环遍历,遇到满足条件的位置+1
复杂度:
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( 1 ) O(1) O(1)
代码:
class Solution {public int countPairs(int[] nums, int k) {int n = nums.length;int ans = 0;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(nums[i]==nums[j]&&i*j%k==0) ans++;}}return ans;}
}
总结
练习了带条件的组合回溯
往期打卡
代码随想录算法训练营第十九天
代码随想录算法训练营第十八天
代码随想录算法训练营第十七天
代码随想录算法训练营周末三
代码随想录算法训练营第十六天
代码随想录算法训练营第十五天
代码随想录算法训练营第十四天
代码随想录算法训练营第十三天
代码随想录算法训练营第十二天
代码随想录算法训练营第十一天
代码随想录算法训练营周末二
代码随想录算法训练营第十天
代码随想录算法训练营第九天
代码随想录算法训练营第八天
代码随想录算法训练营第七天
代码随想录算法训练营第六天
代码随想录算法训练营第五天
代码随想录算法训练营周末一
代码随想录算法训练营第四天
代码随想录算法训练营第三天
代码随想录算法训练营第二天
代码随想录算法训练营第一天
相关文章:
代码随想录算法训练营第二十天
LeetCode题目: 39. 组合总和40. 组合总和 II131. 分割回文串2176. 统计数组中相等且可以被整除的数对(每日一题) 其他: 今日总结 往期打卡 39. 组合总和 跳转: 39. 组合总和 学习: 代码随想录公开讲解 问题: 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 targ…...
C++入门基础:命名空间,缺省参数,函数重载,输入输出
命名空间: C语言是基于C语言的,融入了面向对象编程思想,有了很多有用的库,所以接下来我们将学习C如何优化C语言的不足的。 在C/C语言实践中,在全局作用域中变量,函数,类会有很多,这…...
GPU怎么绑定到服务器上
确认服务器与 GPU 兼容性1:不同的服务器和 GPU 型号连接方式有所不同,要确保所选的 GPU 卡与服务器兼容。可通过服务器和 GPU 的产品文档,或使用服务器厂商提供的兼容性查询工具进行确认。安装前准备:关闭服务器电源,并…...
opencv函数展示2
一、像素操作与算术运算 1.cv2.split() 2. cv2.merge() 3.cv2.add() 4.cv2.bitwise_and() 5.cv2.bitwise_or() 6.cv2.inRange() 二、仿射变换 1.cv2.getRotationMatrix2D() 2.cv2.warpAffine() 3.cv2.flip() 4.cv2.resize() 三、透视变换 1.cv2.getPerspectiveTransform() 2…...
零基础上手Python数据分析 (16):DataFrame 常用统计分析方法
写在前面 —— 超越简单排序,探索数据内在规律,掌握Pandas统计分析基础 上一篇博客,我们学习了如何使用 Pandas 对 DataFrame 进行排序和排名,这使得我们能够更好地组织数据并快速定位关键信息。 然而,仅仅对数据进行排序和排名,还不足以完全理解数据。 要想更深入地解…...
文件系统 软硬连接
🌻个人主页:路飞雪吖~ 🌠专栏:Linux 目录 一、理解文件系统 🌠磁盘结构 二、软硬连接 🌟软硬链接 🌠软链接: 🌠硬链接: 🌟理解软硬链接的应…...
Linux环境基础开发工具使用
本节目标: 1. 学习yum工具,进行软件安装 2. 掌握vim编辑器使用,学会vim的简单配置 3. 掌握gcc/g编译器的使用,并了解其过程,原理 4. 掌握简单gdb使用于调试 5. 掌握简单的Makefile编写,了解其运行思想…...
秘密任务 2.0:如何利用 WebSockets + DTOs 设计实时操作
在之前的文章中,我们探讨了为什么 DTO 是提升 API 效率和安全性的秘密武器。现在,我们进入了一个全新的场景——我们将深入探讨如何通过 WebSockets DTOs 实现实时操作! Agent X 正在进行一项高风险的卧底任务。突然,总部更新了…...
LeetCode hot 100—括号生成
题目 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例 示例 1: 输入:n 3 输出:["((()))","(()())","(())()","()(())",&…...
2025.04.17【Dendrogram】生信数据可视化:Dendrogram图表详解
Dendrogram customization Go further with ggraph: edge style, general layout, node features, adding labels, and more. Customized circular dendrogram Learn how to build a circular dendrogram with proper labels. 文章目录 Dendrogram customizationCustomized c…...
SDL基础
SDL SDL(Simple DirectMedia Layer)是一个开源的跨平台多媒体开发库,主要用于开发需要图形、音频和输入设备支持的应用程序。它使用C语言编写,提供了简单易用的API,**能够帮助开发者快速实现跨平台的多媒体功能。**SD…...
硬件工程师面试常见问题(2)
第六问:你知道那些常用逻辑电平?TTL与COMS电平可以直接互连吗? 逻辑电平:是数字电路中用于表示二进制逻辑状态(0 和 1)的电压或电流信号范围,是数字系统中器件间信号传输的统一标准。 注:逻辑电…...
Python自学第2天:条件语句,循环语句
条件语句 1.条件判断 score 60 if score > 90:print("优秀") elif score > 60:print("及格") else:print("不及格") 注意: 1、每个条件后面要使用冒号 :,表示接下来是满足条件后要执行的语句块。2、使用缩进来划…...
2025年4月16日华为笔试第一题100分
📌 点击直达笔试专栏 👉《大厂笔试突围》 💻 春秋招笔试突围在线OJ 👉 笔试突围OJ 01. 博物馆展览规划 问题描述 卢小姐是一家著名博物馆的策展人,她需要从众多展品中选择一些组成新的展览。每件展品可以展示不同的历史文化主题,而博物馆希望通过最少的展品数量覆…...
智能体开发的范式革命:Cangjie Magic全景解读与实践思考
引言:当智能体开发遇见仓颉魔法 在人工智能技术日新月异的今天,智能体(Agent)开发正从实验室走向产业应用的核心舞台。2025年3月,仓颉社区推出的Cangjie Magic开源平台,以其创新的设计理念和技术架构,为这一领域带来了…...
LeetCode hot 100—单词搜索
题目 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或…...
基于flask+vue框架的灯饰安装维修系统u49cf(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。
系统程序文件列表 项目功能:用户,工单人员,服务项目,订单记录,服务记录,评价记录 开题报告内容 基于 FlaskVue 框架的灯饰安装维修系统开题报告 一、选题背景与意义 (一)选题背景 随着城市化进程的加速与居民生活品质的显著提升…...
C/C++指针
为什么要使用指针 函数的值传递,无法通过调用函数,来修改函数的实参;被调用函数需要提供更多的“返回值”给调用函数;减少值传递时带来的额外开销,提高代码执行效率 指针定义:指针是什么 int age18; /* …...
Unity编辑器扩展之项目资源查找工具
一、需要实现的效果如下: 二、在项目的Asset目录下新增Editor目录,新增AssetSearchWindow和EditorDefine和EditorTools这三个C#脚本,并复制以下的代码保存好之后,就可以实现上述功能啦。 -------------------------------------------EditorTools脚本Begin----------------…...
什么是分布式锁?
分布式锁是一种在分布式系统中控制资源共享的机制。 一、背景和作用 在单机环境下,当多个线程同时访问共享资源时,可以通过线程锁(如 Java 中的 synchronized 关键字、ReentrantLock 等)来保证操作的原子性、可见性和有序性&#…...
ESP32- 开发笔记- 硬件设计-ESP32-C3 天线设计-利用嘉立创EDA来设计
这个硬件设计,只是一个随手记录文档。如果中间有什么问题,欢迎大家提出来。 1 板载天线 1.1 背景介绍 PCB(Printed Circuit Board)板载天线是现代电子设备中用于无线通信的一种关键组件,它直接集成在电路板上&#…...
setTimeoutsetIntervalrequestAnimationFrame
requestAnimationFrame 详解及与 setTimeout/setInterval 的比较 requestAnimationFrame(简称 rAF)是浏览器提供的专门用于 动画渲染 的 API,相比 setTimeout 和 setInterval,它在性能和流畅度上有显著优势。以下是详细解析和对比…...
Python内置函数---anext()
用于异步迭代器的核心工具,专为处理异步数据流设计。 1. 基本语法 await anext(async_iterator, default) 参数: async_iterator :实现了异步迭代协议的对象(如异步生成器、异步迭代器类)。 default (可选…...
JavaEE——线程安全
目录 前言1.线程安全的定义2.线程安全问题产生的原因2.1 多个线程修改一个变量2.2 修改操作不是原子的2.3 内存可见性引起的线程安全问题 3.解决线程安全问题的方法3.1 通过synchronized关键字加锁3.2 使用volatile关键字 总结 前言 在使用多线程的时候,难免会出现…...
MongoServerError: Authentication failed.处理办法
1停止MongoDB服务: systemctl stop mongod2临时修改MongoDB配置,禁用认证: vim /etc/mongdb.config 在配置文件中找到 security:authorization: disabled # 临时关闭认证3.重启MongoDB服务 # 重启MongoDB服务 sudo systemctl restart mon…...
IOS微信小程序无法显示背景图片
最近线上突然出现了一个问题,就是原来的在线上的小程序无法显示背景图片。而且这个问题只有在IOS上才有。在安卓上是正常的。 然后这里和前端沟通说是,看能不能用苹果手机真机调试。果然也成功复现出来了,部分图片无法显示。 然后在网上找了…...
实验五 8255和LED数码管显示实验
一、实验目的 1.掌握并行接口8255A的工作原理及使用方法。 2.了解七段数码管显示数字的原理。 3.掌握多位数码显示的接口技术。 二、实验电路 三、实验内容 1.静态显示:按图3连接好电路࿰…...
秒杀系统解决两个核心问题的思路方法总结:1.库存超卖问题;2.用户重复抢购问题。
秒杀系统解决两个核心问题 秒杀系统解决两个核心问题:一、解决库存超卖的核心逻辑:解释:原子性保证: 二、如何避免重复抢购:使用 Redis 做唯一标识判断优点: 三、流程完整梳理:四、通过数据库建…...
大数吞小数
A-春_牛客练习赛134 double 的有效数字约 15-17 位十进制,因此: 如果两个数的数量级相差超过 15-16 个数量级,较小的数会被吞掉。...
1-9 堆宝塔
堆宝塔游戏是让小朋友根据抓到的彩虹圈的直径大小,按照从大到小的顺序堆起宝塔。但彩虹圈不一定是按照直径的大小顺序抓到的。聪明宝宝采取的策略如下: 首先准备两根柱子,一根 A 柱串宝塔,一根 B 柱用于临时叠放。把第 1 块彩虹圈…...
Java虚拟机(JVM)平台无关?相关?
计算机的概念模型 计算机实际上就是实现了一个图灵机模型。即,输入参数,根据程序计算,输出结果。图灵机模型如图。 Tape是输入数据,Program是针对这些数据进行计算的程序,中间横着的方块表示的是机器的状态。 目前使…...
第七章--查找
查找表 定义 由同一类型的数据元素(或记录)构成的集合。 1)特点:数据元素的类型相同;结构松散→先后次序无关紧要,只关心是否在集合内。 2)常用操作:查询某个“特定的”数据元素是否在查找表中…...
photo-sphere-viewer 4.8.1在vue中使用
photo-sphere-viewer 加载单张平面图 import { Viewer } from photo-sphere-viewerthis.viewer new Viewer({panorama: ‘完整的url,也可以是一个base64’,// Containercontainer: document.getElementById(viewer1),navbar: true,// Resize the panoramasize: {width: 100%,…...
vue MarkdownIt标签多出了<p>标签导致高度变丑
效果如下: [点击并拖拽以移动] F12观察后发现多了 标签包裹,所以要解决 标签。 在 markdown-it 中禁用自动包裹 <p> 标签的方法 要让 markdown-it 渲染的 Markdown 内容不自动包裹 <p> 标签,你可以使用以下两种方…...
《Java 并发编程实践》阅读笔记(一):线程重要性
文章目录 一. 并发历史二. 线程优势三. 线程带来的风险1. 安全性问题2. 活跃性问题3. 性能问题 四. 线程无处不在示例1: Timer示例2: 远程方法调用(Remote Method Invocation, RMI)示例3: GUI 程序 一. 并发历史 操作系统的出现 大型机时代, 没有操作系统, 一台主机只能执行一…...
算法思想之分治-归并
欢迎拜访:雾里看山-CSDN博客 本篇主题:算法思想之分治-归并 发布时间:2025.4.17 隶属专栏:算法 目录 算法介绍核心思想与步骤时空复杂度分析C代码实现关键特性与优化 例题排序数组题目链接题目描述算法思路代码实现 交易逆序对的总…...
Vue基础(5)_事件修饰符
事件修饰符 Vue中的事件修饰符: 1、prevent:阻止默认事件(常用)。 2、stop:阻止事件冒泡(常用)。 3、once:事件只触发一次(常用)。 4、capture:使用事件的捕获模式。 5、self:只有event.target是当前操作的…...
网络编程 - 1
目录 为什么需要网络编程? —— 丰富的网络资源 什么是网络编程 网络编程中的基本概念 发送端和接收端 请求和相应 客户端和服务端 常见的客户端服务端模型 Socket 套接字 概念 分类 解释 有连接 / 无连接 可靠传输 / 不可靠传输 面向字节流 / 面向数…...
github | 仓库权限管理 | 开权限
省流版总结: github 给别人开权限:仓库 -> Setting -> Cllaborate -> Add people GitHub中 将公开仓库改为私有:仓库 -> Setting -> Danger Zone(危险区) ->Change repository visibility( 更改仓…...
【系统搭建】DPDK关键概念与l2fwd源码解析
DPDK(Data Plane Development Kit)是一套用于高性能网络数据面处理的开发框架,其核心设计在于绕过内核协议栈,它提供了一个用户空间下的高效数据包处理库函数,可以用于快速开发高性能的网络应用程序,如网络…...
【Qt】初识Qt(一)
目录 一、Qt的背景二、认识Qt项目 一、Qt的背景 关于客户端开发: 客户端开发的重要任务,是编写和用户交互的界面,和用户交互的界面有两种风格: TUI:命令行界面,也叫终端界面GUI:图形化界面 Q…...
Django REST framework 并结合 `mixin` 的示例
下面为你提供一个使用 Django REST framework 并结合 mixin 的示例,该示例将实现一个简单的图书管理 API。 项目需求 我们要创建一个图书管理系统的 API,支持对图书信息的创建、读取、更新和删除操作。 实现步骤 1. 项目初始化 首先,确保你已经安装了 Django 和 Django…...
《前端性能优化秘籍:打造极致用户体验》
在当下,网站和应用的性能表现直接关乎用户去留。快速加载、流畅交互的页面能让用户沉浸其中,反之,缓慢的响应速度则会让他们毫不犹豫地离开。对于前端开发者而言,性能优化不仅是技术追求,更是提升用户体验、增强产品竞…...
数据结构与算法学习导航
目录 指导思想资料总结代码随想录hello-algoOI-WIKI 一名麻瓜的刷leetcode的简单概述。 在这里对过去的自己说: 如果你相信算法有用你就刷刷leetcode,如果不相信面试会让你相信。 当然,现在我确实认为算法和数据结构有用,leetcode也有用。 …...
【Python】用Python写一个俄罗斯方块玩玩
【Python】用Python写一个俄罗斯方块玩玩 一、引言1.成品效果展示 二、思考准备1.思考设计2.代码设计2.1 游戏页面2.2 控件设计2.2.1 方块生成2.2.2 方块碰撞2.2.3 方块消融2.2.4 游戏主循环2.2.5 游戏窗口 三、游戏完整版 一、引言 今日看到侄子在玩游戏,凑近一看…...
nginx中的代理缓存
1.缓存存放路径 对key取哈希值之后,设置cache内容,然后得到的哈希值的倒数第一位作为第一个子目录,倒数第三位和倒数第二位组成的字符串作为第二个子目录,如图。 proxy_cache_path /xxxx/ levels1:2 2.文件名哈希值...
【深度学习】详解矩阵乘法、点积,内积,外积、哈达玛积极其应用|tensor系列02
博主简介:努力学习的22级计算机科学与技术本科生一枚🌸博主主页: Yaoyao2024往期回顾:【深度学习】你真的理解张量了吗?|标量、向量、矩阵、张量的秩|01每日一言🌼: “脑袋想不明白的,就用脚想”…...
20.3 使用技巧3
版权声明:本文为博主原创文章,转载请在显著位置标明本文出处以及作者网名,未经作者允许不得用于商业目的 20.3.5 禁止追加行与禁止删除行 通常情况下DataGridView最末一行是空白行,在此行单元格输入数据就可以追加新行。如果需要…...
使用代理IP提取数据的步骤是什么?代理IP如何提高爬虫采集效率?
在当今大数据时代,网络爬虫已成为获取互联网信息的重要手段。然而,许多网站为了防止数据被过度抓取,会设置反爬机制,如IP封禁、访问频率限制等。这时,使用代理IP就成为了一种有效的解决方案。本文将详细介绍使用代理IP…...
探索关系型数据库 MySQL
目录 引言 一.SQL的基本操作 1.数据库是什么? 什么是SQL? 1.1.OLTP 1.2.OLAP 1.3.SQL 1.4.DQL 1.5.DML 1.6.DDL 1.7.DCL 1.8.TCL 1.9.数据库术语 2.MySQL体系结构 2.1.连接者 2.2.MySQL 内部连接池 2.3.管理服务和工具组件 2.4.SQL接口 …...