当前位置：首页 > news >正文

算法训练（leetcode）二刷第三十三天 | 322. 零钱兑换、279. 完全平方数、*139. 单词拆分

news 来源：原创 2025/5/6 22:58:05

刷题记录

*322. 零钱兑换
*279. 完全平方数
*139. 单词拆分

*322. 零钱兑换

leetcode题目地址

dp[j]存储amount为j时所需要的最少硬币数。当j为0时需要0个硬币，因此dp[0]赋值为0.

因为是取最少硬币数，因此初始化需要赋值一个最大值。

状态转移方程：dp[j] = min(dp[j], dp[j-coins[i]]+1)

本题是求最少的硬币个数，因此排列组合都无所谓，不会影响结果（因为每次更新是取min），所以遍历顺序背包和硬币可以互换。

时间复杂度： $O(n^2)$
空间复杂度： $O (n)$

// java
class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount+1];for(int i=1; i<=amount; i++) dp[i] = amount+1;dp[0] = 0;for(int i=0; i<coins.length; i++){for(int j=coins[i]; j<=amount; j++){if(dp[j-coins[i]]>=0)dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);}}return dp[amount]==amount+1?-1:dp[amount];}
}

*279. 完全平方数

leetcode题目地址

完全背包。

dp[j]的意义：存储j可以最少由dp[j]个完全平方数之和组成。

同上题思路差不多，这里需要注意初始化的问题，dp[0]赋值为0，其余元素初始化一个最大值。

时间复杂度： $O(n^2)$
空间复杂度： $O (n)$

// java
class Solution {public int numSquares(int n) {int[] dp = new int[n+1];for(int i=0; i<=n; i++) dp[i] = n+1;dp[0] = 0;for(int i=1; i<=n; i++){for(int j=i*i; j<=n; j++){dp[j] = Math.min(dp[j], dp[j-i*i]+1);}}return dp[n];}
}

*139. 单词拆分

leetcode题目地址

本题较难以理解，对于字符串匹配如何转换成背包问题且用dp数组保存结果是一个难点。

dp[j]存储的是字符串s中长度为j的子串是否在wordDict中可以匹配。

在更新dp[j]时，只有前面的子串匹配成功了才会更新后面匹配成功的子串，也就是当访问到子串s[i-j]时，i<j，dp[i]==true时才更新dp[j]。

dp[0]初始化为true，没有实际含义（可以理解为空串），其他位置均为false。

时间复杂度： $O(n^2)$
空间复杂度： $O (n)$

// java
class Solution {public boolean wordBreak(String s, List<String> wordDict) {boolean[] dp = new boolean[s.length()+1];dp[0] = true;for(int j=1; j<=s.length(); j++){for(int i=0; i<j; i++){if(wordDict.contains(s.substring(i, j)) && dp[i]){dp[j] = true;}}}return dp[s.length()];}
}

算法训练（leetcode）二刷第三十三天 | 322. 零钱兑换、279. 完全平方数、*139. 单词拆分

刷题记录 *322. 零钱兑换*279. 完全平方数*139. 单词拆分 *322. 零钱兑换 leetcode题目地址 dp[j]存储amount为j时所需要的最少硬币数。当j为0时需要0个硬币，因此dp[0]赋值为0. 因为是取最少硬币数，因此初始化需要赋值一个最大值。状态转移方程&…...

编程日记 2025/5/6 22:58:05

windows的pip镜像源配置

Windows 中 pip 镜像源配置在 Windows 系统中，为了提高 pip 包的安装速度，我们可以配置 pip 的镜像源。以下是具体的配置步骤： 创建文件夹在 C:\Users\Administrator\pip 路径下创建一个名为 pip.ini 的文件。编辑 pip.ini 文件使用文本…...

编程日记 2025/5/2 14:49:22

Django Rest Framework中嵌套关系的JSON序列化

在 Django Rest Framework (DRF) 中，处理嵌套关系的 JSON 序列化是一个常见需求。以下是如何实现嵌套关系序列化的详细说明，包括序列化器定义、模型关系以及常见用法。 1、问题背景假设我们有以下两个模型： class Jobdtl(models.Model):jo…...

编程日记 2025/4/30 3:42:03

ONVIF协议网络摄像机客户端使用gsoap获取RTSP流地址GStreamer拉流播放

什么是ONVIF协议 ONVIF（开放式网络视频接口论坛）是一个全球性的开放式行业论坛，旨在促进开发和使用基于物理IP的安全产品接口的全球开放标准。 ONVIF规范的目标是建立一个网络视频框架协议，使不同厂商生产的网络视频产品完全互通。…...

编程日记 2025/5/3 9:35:20

40分钟学 Go 语言高并发：Go程序性能优化方法论

Go程序性能优化方法论一、性能指标概述指标类型关键指标重要程度优化目标CPU相关CPU使用率、线程数、上下文切换⭐⭐⭐⭐⭐降低CPU使用率，减少上下文切换内存相关内存使用量、GC频率、对象分配⭐⭐⭐⭐⭐减少内存分配，优化GC延迟指标响应时间、处理延…...

编程日记 2025/5/6 10:08:04

MySQL基础（语句）知识复习 (除索引和视图)

1.客户端和数据库操作 1.登录客户端界面：mysql -uroot -p 2.查看当前的数据库版本：select version(); 3.显示所有数据库：show databases;， 4.创建数据库：create [IF NOT EXISTS] database 库名 character set 字符…...

编程日记 2025/5/7 2:51:20

【sqlcipher】pc端sqflite使用过程中遇到的问题

在flutter中使用sqlcipher时 Mac上如果通过flutter带的文件管理api（即File的delete()方法）删除数据库文件，再创建同名的数据文件的话，必现readonly问题， 这里需要注意的一点是 DatabaseFactory 在Mac上直接使用全局的…...

编程日记 2025/5/7 4:30:25

Vue 实现无线滚动效果

目录 1.Element-plus官网中的Infinite Scroll组件说明 2.滚动条设置 3.滚动到底部的函数调用 1.Element-plus官网中的Infinite Scroll组件说明官网链接如下所示： Infinite Scroll 无限滚动 | Element Plus 首先查看该代码，发现这个组件使用了一个…...

编程日记 2025/5/6 22:28:14

【CSS in Depth 2 精译_062】第 10 章 CSS 中的容器查询（@container）概述 + 10.1 容器查询的一个简单示例

当前内容所在位置（可进入专栏查看其他译好的章节内容） 【第十章 CSS 容器查询】 ✔️ 10.1 容器查询的一个简单示例 ✔️ 10.1.1 容器尺寸查询的用法 ✔️ 10.2 深入理解容器10.3 与容器相关的单位10.4 容器样式查询的用法10.5 本章小结文章目录第 10…...

编程日记 2025/5/7 4:21:05

conda手动初始化

问题:环境中存在conda但是conda无法使用方法: 进入到anaconda目录下, 进入bin目录, 然后执行 source activate要想启动时自动进入conda环境, 需要在 ~/.bashrc中添加如下命令 # >>> conda initialize >>> # !! Contents within this block are managed by …...

编程日记 2025/4/30 11:15:00

hhdb数据库介绍(10-28)

管理管理菜单主要囊括对业务数据进行管理的功能，例如对数据的备份恢复或执行业务表的DDL语句等操作。数据对象数据对象功能可以帮助用户通过列表实时查看当前已存在的数据对象，了解业务数据的整体情况。提供了对数据对象的筛选、统计、关联、详情等…...

编程日记 2025/5/6 0:24:27

Spring Boot自定义启动banner

在启动 Springboot 应用时，默认情况下会在控制台打印出 Springboot 相关的banner信息。自定义banner 如果你想自定义一个独特的启动banner，该怎么做呢？Springboot 允许我们通过自定义启动banner来替换默认的banner。只需要在 resources 目…...

编程日记 2025/5/6 20:52:57

c语言——数组名该如何理解呢？

一般情况下，数组名表示首元素地址，以下2种除外： ①、sizeof(数组名) 表示整个数组 ※只有数组名的情况 sizeof（数组名i） 就不能表示整个数组 ②、&数组名表示整个数组，取的是整个数…...

编程日记 2025/5/7 4:30:25

前端如何用 div 标签实现步骤审批

在前端实现一个步骤审批流程，通常是通过 div 标签和 CSS 来构建一个可视化的流程图，结合 JavaScript 控制审批的状态变化。你可以使用 div 标签创建每一个步骤节点，通过不同的样式（如颜色、边框等）表示审批的不同状态&…...

编程日记 2025/5/2 16:57:22

QT工程，它该怎么学？

在现代软件开发中，QT因其强大的跨平台能力和友好的用户界面设计工具，成为开发者学习和应用的热门选择。特别是在Linux系统下，如何安装、配置QT开发环境，以及创建和管理QT工程是入门QT开发的关键环节。本文将从安装QT开发环境开始&…...

编程日记 2025/5/6 21:25:36

第426场周赛：仅含置位位的最小整数、识别数组中的最大异常值、连接两棵树后最大目标节点数目 Ⅰ、连接两棵树后最大目标节点数目 Ⅱ

Q1、仅含置位位的最小整数 1、题目描述给你一个正整数 n。返回大于等于 n 且二进制表示仅包含置位位的最小整数 x 。置位位指的是二进制表示中值为 1 的位。 2、解题思路我们需要找到一个整数 x，使得： x ≥ nx 的二进制表示中仅包含置位…...

编程日记 2025/4/29 21:44:31

23种设计模式之外观模式

目录 1. 简介2. 代码2.1 SelectFoodService (选择食品)2.2 PayService (支付服务)2.3 TakeService (制作服务)2.4 OrderService (下单服务)2.5 Food (食品)2.6 TackingSystem （外观类）2.7 Test （测试类） 3. 优缺点3. 总结 1. 简介…...

编程日记 2025/5/7 1:31:28

题目代码 #include <bits/stdc.h> using namespace std; const int N 1e510, M 110; int f[N][M]; int main() {int n, k;cin >> n >> k;for(int i 1; i < n; i){int x;cin >> x;f[i][0] __gcd(f[i-1][0], x);for(int j 1; j < min(i, k)…...

编程日记 2025/5/6 14:50:59

LeetCode-430. 扁平化多级双向链表-题解

题目链接 430. 扁平化多级双向链表 - 力扣（LeetCode） 题目介绍你将得到一个双链表，节点包含一个“下一个”指针、一个“前一个”指针和一个额外的“子指针”。这个子指针可能指向一个单独的双向链表，并且这些链表也包含类似的特殊…...

编程日记 2025/5/5 17:30:07

【CSS】一篇掌握CSS

不是因为有了希望才去坚持,而是坚持了才有了希望目录一.导入方式 1.行内样式 2.内部样式 3.外部样式(常用) 二.选择器 1.基本选择器(常用) 1.1标签选择器 1.2类选择器 1.3id选择器 2.层次选择器 2.1后代选择器 2.2子选择器 2.3相邻兄弟选择器 2.4通用兄弟选择器…...

编程日记 2025/5/2 10:33:05

华为仓颉编程环境搭建

1、仓颉介绍摘自华为官方：仓颉编程语言作为一款面向全场景应用开发的现代编程语言，通过现代语言特性的集成、全方位的编译优化和运行时实现、以及开箱即用的 IDE 工具链支持，为开发者打造友好开发体验和卓越程序性能。其具体特性表现为&am…...

编程日记 2025/5/4 13:58:43

手机实时提取SIM卡打电话的信令声音-蓝牙电话如何适配eSIM卡的手机

手机实时提取SIM卡打电话的信令声音 --蓝牙电话如何适配eSIM卡的手机一、前言蓝牙电话的海外战略中，由于海外智能手机市场中政策的差异性，对内置eSIM卡的手机进行支持是非常合理的需求。Android系列手机中，无论是更换通信运营商&#xf…...

编程日记 2025/5/7 4:24:54

三种方式（oss、本地、minio）图片的上传下载

一、OSS 1、前期准备 1.1 注册阿里云账号，开启对象存储oss功能，创建一个bucket（百度教程多的是，跟着创建一个就行，创建时注意存储类型是标准存储，读写权限是公共读） 有的在创建桶时读写属性是…...

编程日记 2025/5/6 0:19:53

使用pyQT完成简单登录界面

import sysfrom PyQt6.QtGui import QMovie,QPixmap from PyQt6.QtWidgets import QApplication, QWidget, QLabel, QPushButton,QLineEdit#封装我的窗口类 class MyWidget(QWidget):#构造函数def __init__(self):#初始化父类super().__init__()# 设置窗口大小self.resize(330,…...

编程日记 2025/5/5 15:21:04

Postgres数据库自动化分区

一.创建自动化分区配置表并插入数据 -- Table: managerdb.par_info-- DROP TABLE IF EXISTS managerdb.par_info;CREATE TABLE IF NOT EXISTS managerdb.par_info (table_schema character varying(255) COLLATE pg_catalog."default" NOT NULL,table_name characte…...

编程日记 2025/5/6 22:28:39

【技术介绍】C++编程语言中的瑰宝

C，这门源于C语言并在其基础上进行大幅增强的编程语言，自诞生以来便以其独特的魅力和强大的功能吸引了无数编程者的目光。它不仅是计算机科学领域的一颗璀璨明珠，更是现代软件开发中不可或缺的重要工具。解析【前言】 C的命名，寓…...

编程日记 2025/5/6 8:53:43

nginx反向代理

目录环境准备启动HTTP服务配置Nginx 访问部署 1.配置nginx 2.自动化脚本 3.执行脚本 4.使用ansible 什么是反向代理呢，参考nginx反向代理，业务部署过长中，常遇到的场景如下，通过访问域名/ip地址，后面接入网…...

编程日记 2025/5/5 22:50:46

分层图最短路

常见情形： 对于边有k次操作的题。。整体思想： 分层图最短路可以视作是dijkstra的一个扩展，通常用于处理N小于10000，或者是k不大的情形。整体有点类似于拆点。将一个点拆成k个点处理。层与层之间互不影响。好了我就说这么多&…...

编程日记 2025/4/27 10:52:50

FRU文件

FRU（Field Replaceable Unit）源文件的格式通常遵循IPMI FRU Information Storage Definition标准。在实际应用中，FRU源文件可以是JSON格式的，这种格式允许用户指定所有的FRU信息字段。以下是FRU源文件的JSON格式的一些关键点&…...

编程日记 2025/5/7 4:27:39

兔子繁衍问题

7-2 兔子繁衍问题分数 15 全屏浏览切换布局作者徐镜春单位浙江大学一对兔子，从出生后第3个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。假如兔子都不死，请问第1个月出生的一对兔子，至少需要繁衍到第几个月时兔…...

编程日记 2025/4/30 22:44:15

飞凌嵌入式受邀亮相OpenHarmony人才生态大会2024

2024年11月27日，OpenHarmony人才生态大会2024在武汉洲际酒店举行。在这场汇聚了行业精英、技术大咖及生态伙伴的年度盛会上，飞凌嵌入式作为OpenHarmony社区的重要成员受邀出席，并展示了其在OpenHarmony 4.1系统适配方面的最新成果。在大会的…...

编程日记 2025/5/6 20:24:05

Resrful控制器

Linux Debian 包管理器 apt DebianUbuntuKali红帽子包管理器dnf或者yum RHELFedroaCentos Stream RHEL上游版本，就是什么新的内容、特性会在这个上面进行测试运行运行页面--dotnet blog.dll配置管理 server{listen 80;server_name m.域名;location / {proxy_p…...

编程日记 2025/5/5 9:10:22

Python练习(2)

重复元素判定续。利用集合的无重复性来编写一个程序如果有一个元素出现了不止一次则返回true但不要改变原来列表的值： 一： def has_duplicates(lst): # 使用集合来存储已经见过的元素 seen set() for item in lst: if item in seen: # 如果元素已经在…...

编程日记 2025/5/5 8:58:40

Qt清空文件夹下的内容

Qt清空文件夹下的内容你可以使用 QDir 类来清空文件夹下的所有内容。以下是一个示例，展示了如何删除指定文件夹中的所有文件和子文件夹： #include <QCoreApplication> #include <QDir> #include <QFileInfoList> #include <QDeb…...

编程日记 2025/5/7 4:24:54

如何手动设置ubuntu服务器的ip、子网掩码、网关、DNS

在 Ubuntu 服务器上手动设置 IP 地址、子网掩码、网关和 DNS，通常有两种方式：使用传统的 ifconfig 命令和配置文件，或者使用现代的 netplan 配置方式（对于 Ubuntu 17.10 及以后版本，netplan 是默认的网络配置工具&…...

编程日记 2025/5/4 23:05:19

单片机状态机实现多个按键同时检测单击、多击、长按等操作

1.背景在之前有个项目需要一个或多个按键检测：单击、双击、长按等操作于是写了一份基于状态机的按键检测，分享一下思路 2.实现效果单击翻转绿灯电平双击翻转红灯电平长按反转红绿灯电平实现状态机检测按键单击，双击，长…...

编程日记 2025/5/3 17:17:00

graph rag都能做哪些事情

从提供的项目目录结构看，系统具备高复杂度和模块化的设计，可能用于大规模数据处理、知识图谱构建、自然语言处理等方面。以下是一些推理出的核心能力和应用场景： 1. 核心模块能力： API 层 (api) 主要用于对外接口的定义和服务调…...

编程日记 2025/5/6 1:38:10

Linux 用户和用户组管理

Linux 用户和用户组管理 Linux系统是一个多用户多任务的分时操作系统，任何一个要使用系统资源的用户，都必须首先向系统管理员申请一个账号，然后以这个账号的身份进入系统。用户的账号一方面可以帮助系统管理员对使用系统的用户进行跟踪&…...

编程日记 2025/5/4 0:56:22

Python酷库之旅-第三方库Pandas(251)

目录一、用法精讲 1186、pandas.tseries.offsets.BusinessMonthEnd.is_year_start方法 1186-1、语法 1186-2、参数 1186-3、功能 1186-4、返回值 1186-5、说明 1186-6、用法 1186-6-1、数据准备 1186-6-2、代码示例 1186-6-3、结果输出 1187、pandas.tseries.offs…...

编程日记 2025/4/30 0:50:07

利用Ubuntu批量下载modis图像（New）

由于最近modis原来批量下载的代码不再直接给出，因此，再次梳理如何利用Ubuntu下载modis数据。之前的下载代码为十分长，现在只给出一部分，需要自己再补充另一部分。之前的为： 感谢郭师兄的指导（https://blo…...

编程日记 2025/5/7 4:22:17

Redis分布式锁

一、全局ID生成器 1.1 概念全局ID生成器，是一种在分布式系统下用来生成全局唯一ID的工具。具有以下特点： （１）唯一性；（２）高可用；（３&…...

编程日记 2025/5/4 5:11:10

【Maven】依赖管理

4. Maven的依赖管理在 Java 开发中，项目的依赖管理是一项重要任务。通过合理管理项目的依赖关系，我们可以有效的管理第三方库，模块的引用及版本控制。而 Maven 作为一个强大的构建工具和依赖管理工具，为我们提供了便捷的方式来管…...

编程日记 2025/5/1 6:56:25

leetcode——移除数组

26.删除有序数组中的重复项给你一个非严格递增排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回 nums 中唯一元素的个数。考虑 nums 的唯一元素…...

编程日记 2025/5/3 19:56:12

vue项目部署到github pages后页面显示不出来？？

问题： 当我们在命令行执行 npm run build 后，项目的目录下会生成一个 dist 文件夹，它里面又包含一个 static 文件夹和一个 index.html 文件，这是 webpack 最终打包好的文件项目上传到仓库后发现页面为空，找不到文件路…...

编程日记 2025/5/5 6:52:11

为什么爱用低秩矩阵

目录为什么爱用低秩矩阵一、定义与性质二、区别与例子为什么爱用低秩矩阵我们更多地提及低秩分解而非满秩分解，主要是因为低秩分解在数据压缩、噪声去除、模型简化和特征提取等方面具有显著的优势。而满秩分解虽然能够保持数据的完整性，但在实际应用中的场景较为有限…...

编程日记 2025/5/1 2:33:02

如何在MySQL中计算两个日期的间隔天数

目录 1. DATEDIFF函数2. TIMESTAMPDIFF函数3. PERIOD_DIFF函数4. 函数对比在MySQL 5.7中，计算两个日期之间的间隔天数是一项常见的任务。 1. DATEDIFF函数 DATEDIFF函数可以直接计算两个日期之间的天数差异。 -- 计算2024年1月1日和2024年1月10日之间的天数差异 …...

编程日记 2025/5/6 8:38:12

SQL面试题——抖音SQL面试题共同问题—共同使用ip用户检测问题

共同使用ip用户检测问题现有用户登录日志表，记录了每个用户登录的IP地址，请查询共同使用过3个及以上IP的用户对； +---+--------------+-------------------+ | id| ip| etime| +---+--------------+-------------------+ | 2|223.104.41.101|20…...

编程日记 2025/5/5 2:17:24