LeetCode Hot 100:动态规划
LeetCode Hot 100:动态规划
70. 爬楼梯
class Solution {
public:int climbStairs(int n) {if (n == 0)return 0;vector<int> dp(n + 1);// 初始化dp[0] = 1;// 状态转移for (int i = 1; i <= n; i++) {dp[i] += dp[i - 1];if (i >= 2)dp[i] += dp[i - 2];}return dp[n];}
};
118. 杨辉三角
class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> ans(numRows);for (int i = 0; i < numRows; i++) {ans[i].resize(i + 1);ans[i][0] = ans[i][i] = 1;}for (int i = 1; i < numRows; i++)for (int j = 1; j < i; j++)ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j];return ans;}
};
198. 打家劫舍
class Solution {
public:int rob(vector<int>& nums) {if (nums.empty())return 0;int n = nums.size();if (n == 1)return nums[0];vector<int> dp(n + 1);// 初始化dp[0] = 0;dp[1] = nums[0];// 状态转移for (int i = 2; i <= n; i++)dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);return dp[n];}
};
279. 完全平方数
思路 1:动态规划
class Solution {
public:int numSquares(int n) {// dp[i]: 最少需要多少个数的平方来表示 ivector<int> dp(n + 1);// 初始化dp[0] = 0;for (int i = 1; i <= n; i++) {int minCnt = INT_MAX;for (int j = 1; j * j <= i; j++)minCnt = min(minCnt, dp[i - j * j]);dp[i] = minCnt + 1;}return dp[n];}
};
思路 2:记忆化搜索
@cache
def dfs(i: int, j: int) -> int:if i == 0:return inf if j else 0if j < i * i:return dfs(i - 1, j) # 只能不选res1 = dfs(i - 1, j) # 不选res2 = dfs(i, j - i * i) + 1 # 选return min(res1, res2)class Solution:def numSquares(self, n: int) -> int:return dfs(isqrt(n), n)
322. 零钱兑换
class Solution {
public:int coinChange(vector<int>& coins, int amount) {if (coins.empty())return -1;if (amount == 0)return 0;int n = coins.size();if (n == 1 && amount % coins[0])return -1;// dp[i]: vector<int> dp(amount + 1, INT_MAX / 2);// 初始化dp[0] = 0;// 状态转移for (int i = 1; i <= amount; i++)for (int& coin : coins) {if (i < coin)continue;dp[i] = min(dp[i], dp[i - coin] + 1);}return dp[amount] == INT_MAX / 2 ? -1 : dp[amount];}
};
139. 单词拆分
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int n = s.length();// dp[i]: s[0,...,i] 是否可以利用 wordDict 拼接出来vector<bool> dp(n + 1, false);// 初始化dp[0] = true;// 状态转移for (int i = 1; i <= n; i++)for (string& word : wordDict) {int len = word.length();if (i >= len && s.substr(i - len, len) == word)dp[i] = dp[i] | dp[i - len];}return dp[n];}
};
300. 最长递增子序列
思路 1:贪心 + 二分查找
class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> lis;for (int& num : nums) {auto it = lower_bound(lis.begin(), lis.end(), num);if (it == lis.end())lis.push_back(num); // >=num 的 lis[j] 不存在else*it = num;}return lis.size();}
};
思路 2:动态规划
class Solution {
public:int lengthOfLIS(vector<int>& nums) {if (nums.empty())return 0;int n = nums.size();if (n == 1)return 1;vector<int> dp(n, 1);// 初始化for (int i = 0; i < n; i++)dp[i] = 1;int maxLen = 0;// 状态转移for (int i = 0; i < n; i++)for (int j = 0; j < i; j++) {if (nums[j] < nums[i])dp[i] = max(dp[i], dp[j] + 1);maxLen = max(maxLen, dp[i]);}return maxLen;}
};
152. 乘积最大子数组
class Solution {
public:int maxProduct(vector<int>& nums) {int n = nums.size();vector<int> minF(n, 0), maxF(n, 0);// 初始化minF[0] = nums[0];maxF[0] = nums[0];// 状态转移for (int i = 1; i < n; i++) {minF[i] =min({nums[i], minF[i - 1] * nums[i], maxF[i - 1] * nums[i]});maxF[i] =max({nums[i], minF[i - 1] * nums[i], maxF[i - 1] * nums[i]});}return *max_element(maxF.begin(), maxF.end());}
};
416. 分割等和子集
思路 1:0-1背包
class Solution {
public:bool canPartition(vector<int>& nums) {if (nums.empty())return false;int sum = accumulate(nums.begin(), nums.end(), 0);if (sum % 2 == 1)return false;int n = nums.size();int target = sum / 2;// dp[i,j]:前i个数字、总和不超过j的情况下,能否满足j == targetvector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));// 初始化dp[0][0] = true;// 状态转移for (int i = 1; i <= n; i++)for (int j = 1; j <= target; j++) {int w = nums[i - 1];if (j >= w)dp[i][j] = dp[i - 1][j] || dp[i - 1][j - w]; // 选elsedp[i][j] = dp[i - 1][j]; // 不选}return dp[n][target];}
};
思路 1:栈
class Solution {
public:int longestValidParentheses(string s) {if (s.empty())return 0;int maxLen = 0;stack<int> stk;stk.push(-1);for (int i = 0; i < s.length(); i++) {if (s[i] == '(')stk.push(i);else {stk.pop();if (stk.empty())stk.push(i);elsemaxLen = max(maxLen, i - stk.top());}}return maxLen;}
};
思路 2:动态规划
class Solution {
public:int longestValidParentheses(string s) {if (s.empty())return 0;int n = s.length();// dp[i]: 表示以下标 i 字符结尾的最长有效括号的长度vector<int> dp(n, 0);int maxLen = 0;// 状态转移for (int i = 1; i < n; i++) {if (s[i] == ')') {if (s[i - 1] == '(')dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(')dp[i] = dp[i - 1] + ((i - dp[i - 1] - 2) >= 0 ? dp[i - dp[i - 1] - 2] : 0) + 2;}maxLen = max(maxLen, dp[i]);}return maxLen;}
};
相关文章:
LeetCode Hot 100:动态规划
LeetCode Hot 100:动态规划 70. 爬楼梯 class Solution { public:int climbStairs(int n) {if (n 0)return 0;vector<int> dp(n 1);// 初始化dp[0] 1;// 状态转移for (int i 1; i < n; i) {dp[i] dp[i - 1];if (i > 2)dp[i] dp[i - 2];}return …...
使用Python制作雪景图片教程
如果你想用Python写一个程序来输出有关“深夜雪”的诗意文本或描述,可以通过简单的字符串输出来实现。以下是一个示例代码,展示如何用Python来描绘深夜雪的场景。 # 定义深夜雪的描述 description """ 夜幕降临,天空洒下银色…...

S-Function
目录 S-Function介绍 生成S-Function的三种常用手段 使用手写S-函数合并定制代码 使用S-Function Builder块合并定制代码 使用代码继承工具合并定制代码 S-Function介绍 我们可以使用S-Function扩展Simulink对仿真和代码生成的支持。例如,可以使用它们…...

如何具备阅读JAVA JDK虚拟机源码能力
源码位置https://github.com/openjdk/jdk 核心实现源码[部分截图] /* * Copyright (c) 1995, 2024, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistr…...

Python | Leetcode Python题解之第514题自由之路
题目: 题解: Test "godding" target "d"i 0left i lc 0 right i rc 0while Test[left] ! target:left - 1lc 1if left -1:left len(Test) - 1while Test[right] ! target:right 1rc 1if right len(Test):right 0prin…...

Docker 镜像下载问题及解决办法
Docker 镜像下载问题及解决办法 我在杂乱的、破旧的村庄寂寞地走过漫长的雨季,将我年少的眼光从晦暗的日子里打捞出来的是一棵棵开花的树,它们以一串串卓然不俗的花擦明了我的眼睛,也洗净了我的灵魂。 引言 在使用 Docker 时,用户…...

2分钟搞定 HarmonyOs Next创建模拟器
官方文档参考链接: 创建模拟器-管理模拟器-使用模拟器运行应用/服务-应用/服务运行-DevEco Studio - 华为HarmonyOS开发者https://developer.huawei.com/consumer/cn/doc/harmonyos-guides-V5/ide-emulator-create-V5 1. 首先打开Device Manager 2. 进入这个界面后…...

方形件排样优化与订单组批问题探析
方形件排样优化与订单组批问题是计算复杂度很高的组合优化问题,在工业工程中有很广泛的应用背景。为实现个性化定制生产模式,企业会选择订单组批的方式,继而通过排样优化实现批量切割,加工完成后再按照不同客户需求进行分拣&#…...

vue3组件通信--自定义事件
自定义事件是典型的子传父的方法。 为什么叫自定义事件呢?是因为我们用sendToy"getToy"这种格式写,很显然,在DOM中,没有叫sendToy的事件。 父组件FatherComponent.vue: <script setup> import ChildComponent fr…...

ubuntu 安装k3s
配置hostname的方法为 hostnamectl set-hostname k3sserver hostnamectlsudo apt-get update && sudo apt-get upgrade -y sudo apt-get install -y curl#手动下载v1.31.1k3s1 https://github.com/k3s-io/k3s/releases/tag/v1.31.1%2Bk3s1 #将k3s-airgap-images-amd64…...
SQL CHECK 约束:确保数据完整性的关键
SQL CHECK 约束:确保数据完整性的关键 在数据库管理中,确保数据的完整性和准确性是至关重要的。SQL(Structured Query Language)提供了多种约束条件来帮助实现这一目标,其中之一就是 CHECK 约束。本文将深入探讨 SQL CHECK 约束的概念、用法和优势,并展示如何在不同的数…...

C++ | Leetcode C++题解之第502题IPO
题目: 题解: typedef pair<int,int> pii;class Solution { public:int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {int n profits.size();int curr 0;priority_queue<int, vect…...

《虚拟现实的边界:探索虚拟世界的未来可能》
内容概要 在虚拟现实(VR)技术的浪潮中,我们见证了其从实验室的奇想逐渐走向日常生活的非凡旅程。技术发展的背后是不断突破的创新,早期的设备虽然笨重,但如今却趋向精致、轻巧,用户体验显著提升。想象一下…...
Rust教程
2024 Rust现代实用教程:1.1Rust简介与安装更新––2024 Rust现代实用教程:1.2编译器与包管理工具以及开发环境–––––––––––...

测试代理IP的有效性和可用性
使用代理IP的有效性和可用性直接关系到用户的工作效率,尤其是在进行数据抓取、网络爬虫和保护个人隐私等场景中。 一、测试代理IP的必要性 代理IP的可用性测试是确保代理服务正常运行的重要步骤。测试代理IP的必要性主要体现在以下几个方面: 提升工作…...
散列表:为什么经常把散列表和链表放在一起使用?
散列表:为什么经常把散列表和链表放在一起使用? 在计算机科学中,散列表(哈希表)和链表是两种常见的数据结构。你可能会好奇,为什么它们经常被放在一起使用呢?让我们一起来深入探讨这个问题。 一、散列表的特点 散列表是一种根据关键码值(Key value)而直接进行访问的…...

计算机网络:网络层 —— IPv4 地址与 MAC 地址 | ARP 协议
文章目录 IPv4地址与MAC地址的封装位置IPv4地址与MAC地址的关系地址解析协议ARP工作原理ARP高速缓存表 IPv4地址与MAC地址的封装位置 在数据传输过程中,每一层都会添加自己的头部信息,最终形成完整的数据包。具体来说: 应用层生成的应用程序…...

PMP--一、二、三模、冲刺、必刷--分类--10.沟通管理--技巧--文化意识
文章目录 技巧一模10.沟通管理--1.规划沟通管理--文化意识--军事背景和非军事背景人员有文化差异文化意识:题干关键词 “两拨人的背景不同、文化差异、风格差异”。5、 [单选] 项目团队由前军事和非军事小组成员组成。没有军事背景的团队成员认为前军事团队成员在他…...
FileReader和FileWriter
FileReader 使用read()方法读取单个字符,下面是如何修改使程序性能更好的过程。 第一种:处理异常方式为throws Testpublic void test() throws IOException {//读取hello.txt,并显示内容// 创建文件对象File file new File("hello.txt…...

【UE5】将2D切片图渲染为体积纹理,最终实现使用RT实时绘制体积纹理【第六篇-阶段总结篇】
因为马上就要进入下一个阶段,制作动态编辑体积纹理的模块。 但在这之前,要在这一章做最后一些整理。 首先,我们完成没完成的部分。其次,最后整理一下图表。最后,本文附上正在用的贴图 完善Shader 还记得我们之前注…...

UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...

Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...

【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...

DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...