做ic比较有名的网站,营销公司有哪些,我是在百度上搜广东网站建设,湛江做网站哪家好作者推荐
动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本
本题涉及知识点
滑动窗口 有序向量 二分查找
LeetCode862:和至少为 K 的最短子数组
给你一个整数数组 nums 和一个整数 k #xff0c;找出 nums 中和至少为 k 的 最短非空子数组 #xff0c;并返回…作者推荐
动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本
本题涉及知识点
滑动窗口 有序向量 二分查找
LeetCode862:和至少为 K 的最短子数组
给你一个整数数组 nums 和一个整数 k 找出 nums 中和至少为 k 的 最短非空子数组 并返回该子数组的长度。如果不存在这样的 子数组 返回 -1 。子数组 是数组中 连续 的一部分。 示例 1 输入nums [1], k 1 输出1 示例 2 输入nums [1,2], k 4 输出-1 示例 3 输入nums [2,-1,2], k 3 输出3 提示 1 nums.length 105 -105 nums[i] 105 1 k 109
滑动窗口
时间复杂度O(nlogn)。枚举子数组的结尾时间复杂度O(n)计算最佳开始时间复杂度O(logn)。 vPreSum是前缀和。 nums[l,r]的和为vPreSum[r1]-vPreSum[l] k vPreSum[r1] - k vPreSum[l] l取值范围[0,r]。 最短子数组也就是l最大。也就是满足 vPreSum[l] vPreSum[r1] - k的最大l。 如果l1 l2 且vPreSum[l1] vPreSum[l2] ,则l1被淘汰l2 被淘汰后 vPreSum成升序。我寻找最后一个小于等于vPreSum[r1] - k的索引。 用std::upper_bound 。
代码
核心代码
//默认升序
templateclass T long long,bool bAsc true
class COrderValueIndexVector
{
public:COrderValueIndexVector(const vectorT vValue):m_vValue(vValue){}void AddIndex(int index){if (bAsc){Addstd::less_equalT(index);}else{assert(false);}} //升序最后一个小于等于的索引 int PreUpperBoundIndex(T value){const int inx std::upper_bound(m_vOrderValue.begin(), m_vOrderValue.end(), value) - m_vOrderValue.begin();if (inx 0){return m_vInx[inx - 1];}return -1;}
protected: templateclass _PRvoid Add(int index){//nums[l,r]的和为vPreSum[r1]-vPreSum[l] k vPreSum[r1] - k vPreSum[l]while (m_vOrderValue.size() _PR()(m_vValue[index], m_vOrderValue.back())){m_vInx.pop_back();m_vOrderValue.pop_back();}m_vInx.emplace_back(index);m_vOrderValue.emplace_back(m_vValue[index]);}vectorint m_vInx;vectorT m_vOrderValue;const vectorT m_vValue;
};
class Solution {
public:int shortestSubarray(vectorint nums, int k) {vectorlong long vPreSum { 0 };for (const auto n : nums){vPreSum.emplace_back(n vPreSum.back());}COrderValueIndexVector ov(vPreSum);int iRet INT_MAX;for (int r 0; r nums.size(); r){//nums[l,r]的和为vPreSum[r1]-vPreSum[l] k vPreSum[r1] - k vPreSum[l]ov.AddIndex(r);const int left ov.PreUpperBoundIndex(vPreSum[r 1] - k);if (left 0 ){iRet min(iRet, r - left 1);} }return (INT_MAX iRet) ? -1 : iRet;}
};测试用例
templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){Assert(v1[i], v2[i]);}
}int main()
{vectorint nums;int k;{Solution sln;nums { 1 }, k 1;auto res sln.shortestSubarray(nums, k);Assert(1, res);}{Solution sln;nums { 1,2 }, k 4;auto res sln.shortestSubarray(nums, k);Assert(-1, res);}{Solution sln;nums { 2,-1,2 }, k 3;auto res sln.shortestSubarray(nums, k);Assert(3, res);}//CConsole::Out(res);
}扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用C 实现。
