首页 > 其他分享 >day36

day36

时间:2024-10-13 11:22:38浏览次数:2  
标签:nums day36 ret int vector dp size

最长递增子序列
class Solution {
public:
int lengthOfLIS(vector& nums) {
if (nums.size() <= 1) return nums.size();
vector dp(nums.size(), 1);
dp[0] = 1;
int ret = 0;
for(int i = 1; i < nums.size(); ++i)
{
for(int j = 0; j < i; ++j)
{
if(nums[i] > nums[j])
{
dp[i] = max(dp[j] + 1, dp[i]);
}
}
ret = max(ret, dp[i]);
}
return ret;
}
};

最长连续递增子序列

class Solution {
public:
int findLengthOfLCIS(vector& nums) {
vector dp(nums.size(), 1);
int ret = 1;
for(int i = 1; i < nums.size(); ++i)
{
if(nums[i] > nums[i-1])
{
dp[i] = dp[i-1] + 1;
}
ret = max(ret, dp[i]);
}
return ret;
}
};

最长重复子数组

class Solution {
public:
int findLength(vector& nums1, vector& nums2) {
vector<vector> dp(nums1.size()+1, vector(nums2.size()+1, 0));
int ret = 0;
for(int i = 1; i <= nums1.size(); ++i)
{
for(int j = 1; j <= nums2.size(); ++j)
{
if(nums1[i-1] == nums2[j-1])
{
dp[i][j] = dp[i-1][j-1] + 1;
ret = max(ret, dp[i][j]);
}
}
}
return ret;

}

};

标签:nums,day36,ret,int,vector,dp,size
From: https://www.cnblogs.com/pwangikun/p/18462035

相关文章

  • NOIP2024集训Day36 DP优化
    NOIP2024集训Day36DP优化A.[NOIP2023]天天爱打卡前段时间才看过这道题。dp+线段树优化+离散化。经典。考虑朴素dp。定义\(f_i\)表示考虑到第\(i\)个位置,并钦定第\(i\)天跑步的最大能量值。枚举最后一段跑步时间,有:\(f_i=\max(\max\limits_{k\ltj}f_k-(i-......
  • 【题解】Solution Set - NOIP2024集训Day36 dp 优化 + 状态设计
    【题解】SolutionSet-NOIP2024集训Day36dp优化+状态设计https://www.becoder.com.cn/contest/5550最后一题较难。「NOIP2023」天天爱打卡考虑dp。\(f_{i,j}\):前\(i\)天,到第\(i\)天为止连续打卡\(j\)天。有转移:\[f_{i,0}=\max(f_{i,j})\\f_{i,j}=\max(f_{i......
  • 代码随想录day36 || 1049 最后一筐石头重量||, 494 目标和,474 一和零
    1049最后一块石头重量||funclastStoneWeightII(stones[]int)int{ //本题思路在于要想得到最小差,就要尽可能将石头分割为两堆相近的重量,然后转换为背包问题 //dp[i]表示容量i背包能装的石头总价值,其中重量和价值相等 //递推公式dp[j]=max(dp[j],dp[j-w(i)]+v[i]......
  • 从零开始的JAVAday36~day42
    定义方法语句格式:publicstaticvoid方法名(){}这是没有参数没有返回值的方法。格式:publicstaticviod方法名(参数1,参数2,参数3){}这是有参数没有返回值的方法。格式:publicstatic返回值类型方法名(参数1,参数2,参数3){return返回值}这是有参数有返回值的方法。......
  • Day36 代码随想录打卡|二叉树篇---翻转二叉树
    题目(leecodeT226):给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。方法:迭代法翻转二叉树,即从根节点开始,一一交换每个节点的左右孩子节点,然后递归此过程,将根节点的左右孩子节点再分别作为参数传入交换节点的函数中。重复此过程,直到结束。就完成了二叉树的翻......
  • 稀碎从零算法笔记Day36-LeetCode:H指数
    有点绕的一个题,题目描述的有点奇怪(可以看下英文?)题型:数组、模拟链接:274.H指数-力扣(LeetCode)来源:LeetCode题目描述给你一个整数数组 citations ,其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。根据维基百科上 h指数......
  • 代码随想录训练营Day36:● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间
    435.无重叠区间题目链接https://leetcode.cn/problems/non-overlapping-intervals/description/题目描述思路直接统计重叠区间的个数,就是需要删除的个数publicinteraseOverlapIntervals(int[][]intervals){Arrays.sort(intervals,(a,b)->Integer.com......
  • 代码随想录 day36 无重叠区间 划分字母区间 合并区间
    无重叠区间这里的思路是找到有几个非重叠区间然后总数减去非重叠区间就是剩下的重叠区间数首先排好序按左或者右都可以这里按左排好然后发现边界不重叠就++边界重叠那么由于左边界优先对齐了所以右边界更新作为一个新的整体区间和下一个区间比较划分字母区间......
  • 算法学习Day36重叠区间
    Day36重叠区间ByHQWQF2024/01/21笔记435.无重叠区间给定一个区间的集合,找到需要移除区间的最小数量,使剩余区间互不重叠。注意:可以认为区间的终点总是大于它的起点。区间[1,2]和[2,3]的边界相互“接触”,但没有相互重叠。示例1:输入:[[1,2],[2,3],[3,4],[1......
  • Day36 写一个简易计算器
    写一个计算器写一个计算器,要求实现加减乘除功能,并且能够循环接收新的数据,通过用户交互实现。思路推荐:(不用写出界面)写4个方法:加减乘除利用循环+switch进行用户交互(判断是+-*/)传递需要操作的两个数输出结果难点:1.选用哪种循环结构主要是要实现:(是否继续使用计算器,......