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

LeetCode 解题思路 45（分割等和子集、最长有效括号）

news 来源：原创 2025/8/23 10:11:41

在这里插入图片描述

解题思路：

dp 数组的含义： 在数组中是否存在一个子集，其和为 i。
递推公式： dp[i] |= dp[i - num]。
dp 数组初始化： dp[0] = true。
遍历顺序： 从大到小去遍历，从 i = target 开始，直到 i = num。确保每个数只用一次。
打印 dp 数组

Java代码：

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums)sum += num;if (sum % 2 != 0)return false;int target = sum / 2;boolean[] dp = new boolean[target + 1];dp[0] = true;for (int num : nums) {for (int i = target; i >= num; i--) {dp[i] |= dp[i - num];}}return dp[target];}
}

复杂度分析：

时间复杂度： O(n * target)。
空间复杂度： O(target)。

解题思路：

可以使用栈来解决这个问题。核心思想是利用栈来跟踪未匹配的括号的索引。初始化时，栈中压入一个基准索引 -1，用于后续计算有效子串的长度。遍历字符串时：

遇到左括号 ‘(’，将其索引压入栈中。
遇到右括号 ‘)’，弹出栈顶元素。此时：
若栈为空，说明当前右括号无匹配，将当前索引压入栈作为新基准。
若栈不为空，当前有效子串长度为当前索引与栈顶元素的差值，更新最大值。

此方法确保每次弹出栈顶后，栈顶元素即为最近未匹配的左括号或基准点，从而快速计算有效长度。

Java代码：

public class Solution {public int longestValidParentheses(String s) {Deque<Integer> stack = new ArrayDeque<>();stack.push(-1);int maxLen = 0;for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c == '(') {stack.push(i);} else {stack.pop();if (stack.isEmpty()) {stack.push(i);} else {maxLen = Math.max(maxLen, i - stack.peek());}}}return maxLen;}
}

复杂度分析：

时间复杂度： O(n)。
空间复杂度： O(n)。

LeetCode 解题思路 45（分割等和子集、最长有效括号）

解题思路： dp 数组的含义： 在数组中是否存在一个子集，其和为 i。递推公式： dp[i] | dp[i - num]。dp 数组初始化： dp[0] true。遍历顺序： 从大到小去遍历，从 i target 开始，直到 …...

编程日记 2025/8/23 10:11:41

AI Agent 入门指南：从 LLM 到智能体

AI. AI. AI. 最近耳朵里是不是总是被这些词轰炸？特别是“Agent”、“AI Agent”、“智能体”、“Agentic”…… 感觉一夜之间，AI 就从我们熟悉的聊天框里蹦出来，要拥有“独立思考”和“自主行动”的能力了？ 说实话，一…...

编程日记 2025/8/23 10:08:55

高级java每日一道面试题-2025年5月02日-基础篇[反射篇-编码]-使用反射，获取Class对象

如果有遗漏,评论区告诉我进行补充面试官: 编写代码通过三种方式（类名.class、对象.getClass()、Class.forName()）获取java.util.ArrayList的Class对象。我回答: 在Java中，反射（Reflection）是一种强大的机制&#…...

编程日记 2025/8/23 1:34:15

【bug】fused_bias_act_kernel.cu卡住没反应

简述在推理人脸修复face restoration算法 GPEN的时候，发现有时候fused_bias_act_kernel.cu卡住没反应。解决清理下缓存，让程序自己再编译下...

编程日记 2025/8/19 7:44:36

小游戏（2）扫雷游戏

一、简述鸽子的时间太长了，其实学完数组和函数就应该搞出来这个丐版的小游戏了，不耽误，反正总归是轮到了，嘻嘻。二、依旧菜单\. 我们这里写的是一个丐版的扫雷游戏，难度就固定了，所以菜单写起来就是玩游…...

编程日记 2025/8/20 22:25:50

如何在vscode中set the environment variable `TF_ENABLE_ONEDNN_OPTS=0`

1.打开工作区设置文件在 VS Code 中通过文件 -> 首选项 -> 设置，接着在设置窗口的右上角点击打开设置（JSON），这会打开settings.json文件。 2.添加环境变量设置 "terminal.integrated.env.linux": { "TF_EN…...

编程日记 2025/8/20 21:24:47

题目描述代码 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next…...

编程日记 2025/8/20 10:59:55

微调大模型如何准备数据集——常用数据集，Alpaca和ShareGPT

微调大模型如何准备数据集——常用数据集，Alpaca和ShareGPT 数据集准备常用数据集自定义数据集AlpacaShareGPT数据集准备常用数据集预训练数据集 Wiki Demo (en)RefinedWeb (en)RedPajama V2 (en)Wikipedia (en)Wikipedia (zh)Pile (en)...

编程日记 2025/8/23 10:07:38

使用Homebrew下载配置git和连接GitHub（Mac版）

本文详细介绍了在M系列Mac上安装Homebrew并配置Git的过程，包括git的下载、设置全局用户名和邮箱、生成SSH密钥、添加GitHubSSH密钥以及终端验证。这些步骤有助于用户顺利进行协同开发。一、下载git 1、终端输入一下命令 brew install git2、这时下载完成二、配…...

编程日记 2025/8/18 20:13:55

电子电器架构 --- 网关转发时延解析

我是穿拖鞋的汉子，魔都中坚持长期主义的汽车电子工程师。老规矩，分享一段喜欢的文字，避免自己成为高知识低文化的工程师：钝感力的“钝”，不是木讷、迟钝，而是直面困境的韧劲和耐力，是面对外界噪音的通透淡然。生活中有两种人，一种人格外在意别人的眼光;另一种人无论…...

编程日记 2025/8/21 14:12:45

shell-流程控制-循环-函数

1. 2. 3.获取当前目录下的普通文件的文件名作为变量列表打印输出 4.打印出下面语句中字符数不大于6的单词 rabbit is favorite to eat cabbage 5.Shell允许用户指定for语句的步长。当用户需要另外指定步长时 6.批量创建用户： 用户名以test开头，按数字序号…...

编程日记 2025/8/19 2:41:53

Paramiko 性能优化详解

1. 复用连接：减少 SSH 连接开销 SSH 连接的建立涉及 TCP 握手、密钥交换、身份认证等步骤，频繁创建连接会显著降低性能。复用连接是核心优化手段。优化方法手动创建 Transport 对象并复用通过同一 Transport 执行多种操作（命令、SFTP、端…...

编程日记 2025/8/19 6:14:33

代码随想录图论part03

第十一章：图论part03 孤岛的总面积 （深搜） 代码随想录孤岛问题：先处理边缘岛在处理孤岛沉没孤岛 （广搜） 代码随想录水流问题代码随想录目的：找水源思路;逆向思考，找两…...

编程日记 2025/8/22 15:50:00

树上背包学习笔记

树上背包，顾名思义，就是在树上跑背包。每日顾名思义 Q：那么到底为什么要树上跑背包 dp 呢？ A：因为我们到现在学的背包 dp 还是属于较浅的一类，什么 01 背包、完全背包还是多重背包，但是如果这…...

编程日记 2025/8/23 10:09:44

CPU：为什么Ryzen 7000系列处理器PCIe通道总数是28，而可用的通道数是24？

AMD Ryzen 7000系列（Zen 4架构）处理器的 28条PCIe 5.0通道中，有 4条固定用于连接主板芯片组（如X670/B650），剩余的 24条直接分配给用户设备。以下是具体分配逻辑： 1. PCIe通道的总分配 24条直连…...

编程日记 2025/8/20 21:32:51

OpenCV 图形API（80）图像与通道拼接函数-----仿射变换函数warpAffine()

操作系统：ubuntu22.04 OpenCV版本：OpenCV4.9 IDE:Visual Studio Code 编程语言：C11 算法描述对图像应用仿射变换。函数 warpAffine 使用指定的矩阵对源图像进行变换： dst ( x , y ) src ( M 11 x M 12 y M 13 , M 21 x M…...

编程日记 2025/8/22 21:46:32

巧记英语四级单词 Unit7-下【晓艳老师版】

navigate v. 航行，航空那六扇门gatevibrate v.颤抖，抖动男生早上起来看到六个文胸在那挂着，春心荡漾virtual a.事实上，实际上的发音“龌龊”；通常lyvia prep.经过 a想成小乌龟，兔子想到河对面吃草&am…...

编程日记 2025/8/23 10:07:40

idea使用lombok错误，找不到符号，明明编译没问题，运行报错

lombok使用出现的问题问题找不到方法经常遇到这样的小伙伴看到这个是不是一头雾水，明明我编译没有我问题，运行就出现问题，真的很生气。下面介绍解决这个问题的几种方法。开启 annotation processing 开启之后重启，试试有…...

编程日记 2025/8/19 7:44:37

Transformer面经

请问你对Transformer有什么了解简要回答的话可以这样： Transformer是一种基于自注意力机制的神经网络架构，它主要用于处理序列数据，如自然语言处理。核心的组件有：自注意力机制（计算序列中每个元素与其他元素的相…...

编程日记 2025/8/23 10:09:48

学习Python的第二天之网络爬虫

30岁程序员学习Python的第二天之网络爬虫的信息提取 BeautifulSoup库地址：https://beautifulsoup.readthedocs.io/zh-cn/v4.4.0/ 1、BeautifulSoup4安装在windows系统下通过管理员权限运行cmd窗口运行pip install beautifulsoup4 测试实例 import requests…...

编程日记 2025/8/18 15:21:30

【基础】Python包管理工具uv使用教程

一、uv简介 uv 是由 Astral（前身为 Basis）团队开发的 Python 包安装器和解析器，完全使用 Rust 语言编写。与传统 Python 工具不同，uv 将多个工具的功能整合到一个高性能的解决方案中，旨在提供更现代、更高效的 Python…...

编程日记 2025/8/20 11:00:52

【十五】Mybatis动态SQL实现原理

Mybatis动态SQL实现原理目录 Mybatis动态SQL实现原理概述动态 SQL 实现原理总结概述每天日常开发都在使用mybatis，但是很多人并没有花心思去理解mybatis的实现原理，一直处于使用阶段，程序员的使命是改变世界，这一点可能…...

编程日记 2025/8/23 10:11:04

UE5 把翅膀动画额外创建动画蓝图并和角色绑定混合动画

把翅膀和角色合并,把翅膀绑在Spine_3上在5.3内,需要LayerSetup指定骨骼才能使用混合...

编程日记 2025/8/23 10:11:39

Coding Practice，48天强训（30）

Topic 1：爱吃素（素数性质） 爱吃素在强训25的第一题我总结过关于素数的几种判断方式，如果忘了可以回去看第一次写我是这样写的 #include <bits/stdc.h> using namespace std;bool isPrime(long long &a, long long …...

编程日记 2025/8/19 7:46:41

华为私有协议Hybrid

实验top图理论环节 1. 基本概念 Hybrid接口： 支持同时处理多个VLAN流量，且能针对不同VLAN配置是否携带标签（Tagged/Untagged）。核心特性： 灵活控制数据帧的标签处理方式，适用于复杂网络场景。 2. 工作…...

编程日记 2025/8/19 7:45:56

神经网络之互动练习详解：从基础到拟合非线性数据

神经网络之互动练习详解：从基础到拟合非线性数据在机器学习的世界里，神经网络是一种强大而神奇的工具，它可以帮助我们解决各种复杂的问题。今天，我们就通过一个有趣的互动练习，来深入了解神经网络的工作原理以及如何…...

编程日记 2025/8/23 8:54:50

遨游科普：2025年，三防平板有多智能？

在极端环境与复杂场景中，专业设备的可靠性始终是行业应用的核心命题。随着物联网、5G通信与边缘计算技术的深度融合，三防平板已突破传统“坚固耐用”的单一属性，进化为集多模通讯、智能感知与场景化扩展于一体的移动智能终端。 AORO P9000三防…...

编程日记 2025/8/20 10:59:55

基于C++的IOT网关和平台7：github项目ctGateway设备协议开发指南

初级代码游戏的专栏介绍与文章目录-CSDN博客我的github：codetoys，所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。这些代码大部分以Linux为目标但部分代码是纯C++的，可以在任何平台上使用。源码指引：github源码指引_初级代码游戏的博客-CSDN博客系…...

编程日记 2025/8/19 18:16:08

yolov8中的python基础--模块导入篇

import语句有几种不同的写法，它们有不同的用途和优势。 1. 直接 import 语法 import module_name 用途导入整个模块，使用时需要通过模块名访问其中的内容。示例 import os print(os.listdir()) # 必须用 os. 前缀适用场景当需要频繁使用模块…...

编程日记 2025/8/22 21:48:13

26.2Linux中SPI的驱动实验(编程)_csdn

我尽量讲的更详细，为了关注我的粉丝！！！ 这里我们用到的是stm32mp157的板子，所以我们看一下SPI用到的引脚。 1、硬件原理图分析 SPI1_MOSI（对应芯片引脚 SDA/SDI ）：主机输出从机输入…...

编程日记 2025/8/20 18:20:02

uv简单使用

通过uv创建项目和虚拟环境初始化项目 uv init --package my-project 初始化一个名为 my-project 的新项目，并生成必要的文件结构。创建虚拟环境 uv venv .venv 激活虚拟环境 # For Windows .venv\Scripts\activate# For macOS/Linux source .venv/bin/acti…...

编程日记 2025/8/22 5:44:31

扩增子分析|微生物生态网络稳定性评估之鲁棒性（Robustness）和易损性（Vulnerability）在R中实现

一、引言周集中老师团队于2021年在Nature climate change发表的文章，阐述了网络稳定性评估的原理算法，并提供了完整的代码。自此对微生物生态网络的评估具有更全面的指标，自此网络稳定性的评估广受大家欢迎。本系列将介绍网络稳定性之鲁棒性…...

编程日记 2025/8/20 12:36:59

线性回归评价标准

In [1]: 12345 import numpy as npfrom sklearn.linear_model import LinearRegressionimport sklearn.datasets as datasets 12 ()diabetesdiabetes $$datasets.load_diabetes In [2]: Out[2]: {‘data’: array([[ 0.03807591,0.05068012,0.06169621,…,-0.00259226, 0.0…...

编程日记 2025/8/21 3:21:23

解题思路：

Java代码：

复杂度分析：

解题思路：

Java代码：

复杂度分析：

相关文章：