怎么查看网站空间,可以做 描文本链接的网站,商城建设网站,调取当前文章标签wordpress涉及知识点
双指针 C算法#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 贪心算法
题目
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。 你可以对数组执行 至多 k 次操作#xff1a; 从数组中选择一个下标 i #xff0c;将 nums[i] …涉及知识点
双指针 C算法前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 贪心算法
题目
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。 你可以对数组执行 至多 k 次操作 从数组中选择一个下标 i 将 nums[i] 增加 或者 减少 1 。 最终数组的频率分数定义为数组中众数的 频率 。 请你返回你可以得到的 最大 频率分数。 众数指的是数组中出现次数最多的数。一个元素的频率指的是数组中这个元素的出现次数。 示例 1 输入nums [1,2,6,4], k 3 输出3 解释我们可以对数组执行以下操作
选择 i 0 将 nums[0] 增加 1 。得到数组 [2,2,6,4] 。选择 i 3 将 nums[3] 减少 1 得到数组 [2,2,6,3] 。选择 i 3 将 nums[3] 减少 1 得到数组 [2,2,6,2] 。 元素 2 是最终数组中的众数出现了 3 次所以频率分数为 3 。 3 是所有可行方案里的最大频率分数。 示例 2 输入nums [1,4,4,2,4], k 0 输出3 解释我们无法执行任何操作所以得到的频率分数是原数组中众数的频率 3 。 参数范围 1 nums.length 105 1 nums[i] 109 0 k 1014
贪心算法中位数贪心)
假定众数是x,假定nums的长度为n将nums按升序排序。
x一定是nums中的数
我们用反证发证明。
x nums[0]所有数先降到nums[0]再由nums[0]降到x不如直接降到nums[0]x nums[n-1]所有数先升到nums[n-1]再升到x不如只升到nums[n-1]x在nums[i]和nums[j]之间nums中比x小的a个数比x大的b个数。如果abx–,可以节省a-b个操作直到x等于nums[i];否则x直到x等于nums[j]。
改变的数一定是一个子数组
假定改变的数是两个子数组[i1,i2]和[i3,i4]。如果x在[i1,i2]之间则将i4替换成i21直到两个子数组挨着一起合并。如果x在[i3,i4]之间则i1替换i3-1直到两个子数组挨着一起合并。
x只需要考虑中位数中位数贪心算法)
来证明贪心算法的正确性。假定x是nums[i]x前面的数a个x后面的数b个i变成i-1操作次数变化b-(a-1)如果表达式大于等于0则没必要左移。b -a1 0即a b1。同理b a1。即abs(a-b)1则没必要左移和右移。 即 如果n为偶数中间任意一个。 如果n为奇数中间的那个。
代码
核心代码
class Solution {
public:int maxFrequencyScore(vectorint nums, long long k) {m_c nums.size();sort(nums.begin(), nums.end());vectorlong long vPreSum { 0 };for (const auto n : nums){vPreSum.emplace_back(nvPreSum.back());} int iRet 0;for (int left 0, right 0; left m_c; left){while (right m_c){const long long mid left (right - left) / 2;const long long llLessNeed (mid - left) * nums[mid] - (vPreSum[mid] - vPreSum[left]);const long long llEqualMoreNeed (vPreSum[right] - vPreSum[mid]) - nums[mid] * (right - mid);if (llLessNeed llEqualMoreNeed k){iRet max(iRet, right - left);right;}else{break;}} }return iRet;}int m_c;
};测试用例
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()
{Solution slu;vectorint nums;int k;{Solution slu;nums { 1,4,4,2,4 }, k 0;auto res slu.maxFrequencyScore(nums, k);Assert(3, res);}{Solution slu;nums { 16, 2, 6, 20, 2, 18, 16, 8, 15, 19, 22, 29, 24, 2, 26, 19 }, k 40;auto res slu.maxFrequencyScore(nums, k);Assert(11, res);}{Solution slu;nums { 1, 2, 6, 4 }, k 3;auto res slu.maxFrequencyScore(nums, k);Assert(3, res);}//CConsole::Out(res);
}错误解法:二分查找双指针
错误原因 随着left增加targge可能减少 class Solution { public: int maxFrequencyScore(vector nums, long long k) { m_c nums.size(); sort(nums.begin(), nums.end()); vector vPreSum { 0 }; for (const auto n : nums) { vPreSum.emplace_back(nvPreSum.back()); } long long llLeftSum 0;//nums[left,target)的和nums升序 int iRet 0; for (int left 0, target 0; left m_c; left) { while ((target m_c) (nums[target]*(target-left)- llLeftSum k)) { const int right BF(vPreSum,nums, target, k - (nums[target] * (target - left) - llLeftSum)); iRet max(iRet, right - left); llLeftSum nums[target]; target; } llLeftSum - nums[left]; } return iRet; } int BF(const vector vPreSum,const vector nums, int index,long long canUse) { int left index, right vPreSum.size(); while (right - left 1) { const int mid left (right- left)/2 ; if ((vPreSum[mid] - vPreSum[index]- nums[index] * (mid - index)) canUse) { left mid; } else { right mid; } } return left; } int m_c; }; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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**实现。
