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

企业如何进行网站备案网络营销的目标

企业如何进行网站备案,网络营销的目标,湛江论坛,私人网站建设作者推荐 [二分查找]LeetCode2040:两个有序数组的第 K 小乘积 本文涉及的基础知识点 二分查找算法合集 分组 动态规划 题目 给你一个下标从 0 开始包含 n 个正整数的数组 arr &#xff0c;和一个正整数 k 。 如果对于每个满足 k < i < n-1 的下标 i &#xff0c;都有…

作者推荐

[二分查找]LeetCode2040:两个有序数组的第 K 小乘积

本文涉及的基础知识点

二分查找算法合集
分组 动态规划

题目

给你一个下标从 0 开始包含 n 个正整数的数组 arr ,和一个正整数 k 。
如果对于每个满足 k <= i <= n-1 的下标 i ,都有 arr[i-k] <= arr[i] ,那么我们称 arr 是 K 递增 的。
比方说,arr = [4, 1, 5, 2, 6, 2] 对于 k = 2 是 K 递增的,因为:
arr[0] <= arr[2] (4 <= 5)
arr[1] <= arr[3] (1 <= 2)
arr[2] <= arr[4] (5 <= 6)
arr[3] <= arr[5] (2 <= 2)
但是,相同的数组 arr 对于 k = 1 不是 K 递增的(因为 arr[0] > arr[1]),对于 k = 3 也不是 K 递增的(因为 arr[0] > arr[3] )。
每一次 操作 中,你可以选择一个下标 i 并将 arr[i] 改成任意 正整数。
请你返回对于给定的 k ,使数组变成 K 递增的 最少操作次数 。
示例 1:
输入:arr = [5,4,3,2,1], k = 1
输出:4
解释:
对于 k = 1 ,数组最终必须变成非递减的。
可行的 K 递增结果数组为 [5,6,7,8,9],[1,1,1,1,1],[2,2,3,4,4] 。它们都需要 4 次操作。
次优解是将数组变成比方说 [6,7,8,9,10] ,因为需要 5 次操作。
显然我们无法使用少于 4 次操作将数组变成 K 递增的。
示例 2:
输入:arr = [4,1,5,2,6,2], k = 2
输出:0
解释:
这是题目描述中的例子。
对于每个满足 2 <= i <= 5 的下标 i ,有 arr[i-2] <= arr[i] 。
由于给定数组已经是 K 递增的,我们不需要进行任何操作。
示例 3:
输入:arr = [4,1,5,2,6,2], k = 3
输出:2
解释:
下标 3 和 5 是仅有的 3 <= i <= 5 且不满足 arr[i-3] <= arr[i] 的下标。
将数组变成 K 递增的方法之一是将 arr[3] 变为 4 ,且将 arr[5] 变成 5 。
数组变为 [4,1,5,4,6,5] 。
可能有其他方法将数组变为 K 递增的,但没有任何一种方法需要的操作次数小于 2 次。
提示:
1 <= arr.length <= 105
1 <= arr[i], k <= arr.length

分析

时间复杂度

O(nlogn),枚举每个元素,时间复杂度O(n),每个元素二分查找O(logn)。

代码

原理

一,有多少对不符合递增,则至少需要多少次操作。arr[i]和arr[i+1]不符合,需要修改arr[i]或arr[i+1]。能否一次修改,同时解决两个数对,假定arr[i-1] > arr[i] > arr[i+1],由于arr[i-1]>arr[i+1],所以arr[i]无论如何都不可能大于等于arr[i-1],同时小于等于arr[i+1]。
二,需要的操作数,可能大于非递增的对数。比如:4 1 3 ,4 1非递增,1 3递增。
三,操作次数等于=总元素数-最长递增序列的长度。假定最长子系列为:newNew[0]…newNew[n]。
四,第三只能说明是一个解,现在来证明是最优解: 假定arr2最优解,删掉修改过的元素,那么它一定是arr的子序列,且是递增的。此子系列越长,删除(操作)的元素越少。

newNew[0]之前的元素全部改成newNew[0]
newNew[n]之后的元素全部改成newNew[n]
newNew[i]和newNew[i+1]的元素全改成newNew[i]

变量解释

vLenMinEndvLenMinEnd[i]=x,在长度为i的子序列中,结尾的最小值为x

核心代码

class Solution {
public:int kIncreasing(vector<int>& arr, int k) {int iMaxLen = 0;for (int i = 0; i < k; i++){vector<int> vLenMinEnd = { 0,arr[i] };for (int j = i + k; j < arr.size(); j += k){auto index = std::upper_bound(vLenMinEnd.begin(), vLenMinEnd.end(), arr[j])- vLenMinEnd.begin();if (index >= vLenMinEnd.size()){vLenMinEnd.emplace_back(arr[j]);continue;}vLenMinEnd[index] = min(vLenMinEnd[index], arr[j]);		}iMaxLen += vLenMinEnd.size() - 1;}return arr.size()-iMaxLen;}
};

测试用例

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

int main()
{
vector arr;
int k, res;
{
Solution slu;
arr = { 12, 6, 12, 6, 14, 2, 13, 17, 3, 8, 11, 7, 4, 11, 18, 8, 8, 3 }, k = 1;
auto res = slu.kIncreasing(arr, k);
Assert(12, res);
}
{
Solution slu;
arr = { 5, 4, 3, 2, 1 }, k = 1;
auto res = slu.kIncreasing(arr,k);
Assert(4, res);
}
{
Solution slu;
arr = { 4,1,5,2,6,2 }, k = 2;
auto res = slu.kIncreasing(arr, k);
Assert(0, res);
}
{
Solution slu;
arr = { 4,1,5,2,6,2 }, k = 3;
auto res = slu.kIncreasing(arr, k);
Assert(2, res);
}

//CConsole::Out(res);

}

2023年9月旧代码

class Solution {
public:
int kIncreasing(vector& arr, int k) {
vector<vector> vSubArr(k);
for (int i = 0; i < arr.size(); i++)
{
vSubArr[i%k].push_back(arr[i]);
}
int iRet = 0;
for ( auto& v : vSubArr)
{
iRet += NeedChange(v, 0, v.size() );
}
return iRet;
}
int NeedChange(vector& arr,int iLeft,int iRight)
{
std::map<int, int> mValueNums;
for (const auto& a : arr)
{
auto it = mValueNums.upper_bound(a);
auto itTmp = it;
const int iValue = ((mValueNums.begin() == it) ? 0 : (–itTmp)->second) + 1;
if ((mValueNums.end() != it) && (it->second <= iValue))
{
mValueNums.erase(it);
}
mValueNums[a] = iValue;
}
return arr.size() - mValueNums.rbegin()->second;
}
int m_iK;
};

2023年9月第一版

class Solution {
public:
int kIncreasing(vector& arr, int k) {
int iRet = 0;
for (int turn = 0; turn < k; turn++)
{
std::map<int, int> mEndLen;
mEndLen[0] = 0;
int iMaxLen = 0;
for (int index = turn; index < arr.size(); index += k)
{
auto it = mEndLen.upper_bound(arr[index]);
const int iLen = std::prev(it)->second+1;
it = mEndLen.lower_bound(arr[index]);
auto ij = it;
for (; (ij != mEndLen.end()) && (ij->second <= iLen); ij++);
mEndLen.erase(it, ij);
mEndLen[arr[index]] = iLen;
iMaxLen = max(iMaxLen, iLen);
}
iRet += iMaxLen;
}
return arr.size()- iRet;
}
};

2023年9月第二版

class Solution {
public:
int kIncreasing(vector& arr, int k) {
int iRet = 0;
for (int turn = 0; turn < k; turn++)
{
vector vValue;
for (int index = turn; index < arr.size(); index += k)
{
auto it = std::upper_bound(vValue.begin(), vValue.end(),arr[index]);
if (vValue.end() == it)
{
vValue.emplace_back(arr[index]);
}
else
{
*it = arr[index];
}
}
iRet += vValue.size();
}
return arr.size()- iRet;
}
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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 C++17
或者 操作系统:win10 开发环境:

VS2022 C++17

http://www.hrbkazy.com/news/17381.html

相关文章:

  • 百度右侧相关网站seo网站优化软件
  • 网站信息内容建设局通报宁波seo博客
  • 做电子商务网站需要办理什么证seddog站长之家
  • 用微信怎么做商城网站吗营销做得好的品牌
  • 如何让网站快速收录有别人的交易链接怎么交易
  • 从哪个网站设置宽带主机游戏如何在网上推广
  • 网站搭建哪里找更靠谱营销渠道
  • 重庆北京网站建设重庆网络推广公司
  • 快速搭建小程序seo怎么做排名
  • 怎么做劫持网站广州seo公司哪个比较好
  • 狠狠做最新网站国内十大搜索引擎排名
  • 北京 网站建设公司靠谱seo外包定制
  • 什么网站做顶置便宜杭州百度seo
  • 北京建站公司兴田德润很好疫情优化调整
  • 网站动态页面打不开企业培训内容
  • 自己做网站是用什么软件如何做平台推广
  • 互站网怎么样seo外链优化
  • 做网站包含微信公众号吗河南省郑州市金水区
  • 鄂州第一网官方网站seo推广专员招聘
  • 西安官网seo诊断常州seo博客
  • 做移动网站优百度官方网首页
  • 在线制作假亲子鉴定书上海专业排名优化公司
  • 网站建设 企业观点广州宣布5条优化措施
  • 北京企业做网站费用软文推广经典案例
  • 家用宽带怎么做网站 访问推广引流工具
  • 网站做支付需要准备什么条件建网站免费
  • 深圳网站制作网站建设怎么制作网站深圳博纳网络培训课程
  • 深圳做购物网站1+x网店运营推广
  • 网络设计网站多少钱google play下载安卓
  • 北京欢迎你网站建设建网站平台