网站排名查询alexa,百度广告投放价格,wordpress cdn 规则,招聘网58同城C前缀和算法的应用#xff1a;统计上升四元组
本文涉及的基础知识点
C算法#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
题目
给你一个长度为 n 下标从 0 开始的整数数组 nums #xff0c;它包含 1 到 n 的所有数字#xff0c;请你返回上…C前缀和算法的应用统计上升四元组
本文涉及的基础知识点
C算法前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
题目
给你一个长度为 n 下标从 0 开始的整数数组 nums 它包含 1 到 n 的所有数字请你返回上升四元组的数目。 如果一个四元组 (i, j, k, l) 满足以下条件我们称它是上升的 0 i j k l n 且 nums[i] nums[k] nums[j] nums[l] 。 示例 1 输入nums [1,3,2,4,5] 输出2 解释
当 i 0 j 1 k 2 且 l 3 时有 nums[i] nums[k] nums[j] nums[l] 。当 i 0 j 1 k 2 且 l 4 时有 nums[i] nums[k] nums[j] nums[l] 。 没有其他的四元组所以我们返回 2 。 示例 2 输入nums [1,2,3,4] 输出0 解释只存在一个四元组 i 0 j 1 k 2 l 3 但是 nums[j] nums[k] 所以我们返回 0 。 参数范围 4 nums.length 4000 1 nums[i] nums.length nums 中所有数字 互不相同 nums 是一个排列。
容易理解
分析
第一层循环枚举j第二层循环枚举k。时间复杂度O(n*n)。在通过不通过之间用vectorvector就通过不了用int**勉强可以通过。分两步
第一步求前缀和第二步枚举j和k
核心代码
class Solution { public: long long countQuadruplets(vector nums) { m_c nums.size(); int** vSum new int*[m_c 1];//vSum[i][j]nums[0,j)中小于等于i的个数 for (int i 1; i m_c; i) {//计算小于i的个数 vSum[i] new int[m_c1]; vSum[i][0] 0; for (int j 0 ; j m_c; j ) { vSum[i][j1] vSum[i][j] (nums[j] i); } } long long llRet 0; for (int j 1; j m_c; j) { for (int k j 1; k1 m_c; k) { if (nums[j] nums[k]) { continue; } //nums[i]范围nums[0,j)中小于等于nums[k]的数量 const long long lessNumK vSum[nums[k]][j]; //nums[k1,m_c)中大于nums[j] const long long moreNumJ m_c - (k 1) - (vSum[nums[j]][m_c]- vSum[nums[j]][k1]); llRet lessNumK * moreNumJ; } } return llRet; } int m_c; };
测试用例
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() { Solution slu; vector nums ; long long res; nums { 1, 3, 2, 4, 5 }; res slu.countQuadruplets(nums); Assert(2LL, res); nums { 1, 2,3,4 }; res slu.countQuadruplets(nums); Assert(0LL, res); nums { 4,3,2,1 }; res slu.countQuadruplets(nums); Assert(0LL, res); nums { 4,3,2,6,5,1 }; res slu.countQuadruplets(nums); Assert(0LL, res); nums { 1,3,2,4 }; res slu.countQuadruplets(nums); Assert(1LL, res); nums { 2,1,4,3,5 }; res slu.countQuadruplets(nums); Assert(2LL, res); nums.clear(); for (int i 0; i 4000; i) { nums.emplace_back(i 1); } res slu.countQuadruplets(nums); Assert(0LL, res); //CConsole::Out(res); }
性能稍强
分析
第一层循环枚举l或k第二层循环枚举j。时间复杂度O(n*n)代码简洁得多可以轻松通过。
变量解释
llRet所有符合条件的四元祖iLessLKnums[0,j)中小于nums[i]的数量m_v132[j]nums[0,i)中符合i,j,k的数量
核心代码
class Solution {
public:long long countQuadruplets(vectorint nums) {m_c nums.size();long long llRet 0;vectorlong long m_v132(m_c);//132for (int lk 0; lk m_c; lk){int iLessLK 0;for (int j 0; j lk; j){if (nums[j] nums[lk]){iLessLK;llRet m_v132[j];}else{//iLessLK 表示[0,j)中小于nums[lk]的数假定其索引为i则nums[i] nums[lk] nums[j] nums[lk],故i j lk符合前三个数i,j,km_v132[j] iLessLK;}}}return llRet;}int m_c;
};2月旧代码
class Solution { public: long long countQuadruplets(vector nums) { m_c nums.size(); //vLeft[i][m] 表示nums[i]及之前的元素小于等于m1的个数 int vLeft[4000][4000] { 0 }; { for (int i 0; i m_c; i) { if (i 0) { memcpy(vLeft[i], vLeft[i - 1], sizeof(vLeft[0])); } for (int j nums[i] - 1; j m_c; j) { vLeft[i][j] ; } } } long long llRet 0; for (int j 1; j 1 m_c; j) { for (int k j 1; k 1 m_c; k) { if (nums[j] nums[k]) { continue; } const int iLeft vLeft[j - 1][nums[k] - 1]; const int iRight nums[j] - vLeft[k][nums[j] - 1]; llRet vLeft[j - 1][nums[k] - 1] * (nums.size() - k - 1 - iRight); } } return llRet; }; 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
