https://www.ciyekua.cn/index.php/category/算法 zh-CN Sat, 31 Aug 2024 13:51:00 +0800 Sat, 31 Aug 2024 13:51:00 +0800 https://www.ciyekua.cn/index.php/diary/157.html https://www.ciyekua.cn/index.php/diary/157.html Sat, 31 Aug 2024 13:51:00 +0800 ciye 二分搜索函数 C语言：`bsearch()` C++：`binary_search()` 1.C语言：bsearch() 函数原型如下： ``` void* bsearch( const void *key, const void *ptr, size_t count, size_t size, int (*comp)(const void*, const void*) ); ``` 2.C++：binary_search() ``` binary_search(起始地址，结束地址，要查找的数值) 返回的是是否存在这么一个数，是一个bool值。 ``` 3.C++扩展 ``` lower_bound(起始地址，结束地址，要查找的数值) lower_bound()：返回大于或等于目标值的第一个位置 upper_bound(起始地址，结束地址，要查找的数值) upper_bound()：返回大于目标值的第一个位置 ``` ``` 参考资料： https://blog.csdn.net/sinat_31608641/article/details/124975237 https://baijiahao.baidu.com/s?id=1793956676806508127&wfr=spider&for=pc ``` ]]> 0 https://www.ciyekua.cn/index.php/diary/157.html#comments https://www.ciyekua.cn/index.php/feed/diary/157.html https://www.ciyekua.cn/index.php/diary/153.html https://www.ciyekua.cn/index.php/diary/153.html Thu, 15 Aug 2024 18:35:00 +0800 ciye https://www.ciyekua.cn/index.php/diary/152.html]]> 1.nth_element() 2024/08/15 作用：找出数组中第k小的数 > https://www.ciyekua.cn/index.php/diary/152.html ]]> 0 https://www.ciyekua.cn/index.php/diary/153.html#comments https://www.ciyekua.cn/index.php/feed/diary/153.html https://www.ciyekua.cn/index.php/diary/152.html https://www.ciyekua.cn/index.php/diary/152.html Thu, 15 Aug 2024 18:28:00 +0800 ciye 找出一个数组中第k小的数 一、朴素做法 sort() 时间复杂度：O(nlogn) 二、利用STL库函数nth_element() 时间复杂度：O(n) 用法：`nth_element(a,a+k,a+n)` 长度为n的数组a[]中找出第k小的数 ]]> 0 https://www.ciyekua.cn/index.php/diary/152.html#comments https://www.ciyekua.cn/index.php/feed/diary/152.html https://www.ciyekua.cn/index.php/diary/148.html https://www.ciyekua.cn/index.php/diary/148.html Thu, 15 Aug 2024 17:09:00 +0800 ciye 1.rand() 函数的基本用法 rand() 函数不需要参数，它会返回一个从 0 到最大随机数之间的任意整数。 最大随机数的大小通常是固定的一个大整数，例如 RAND_MAX。 ***注意：***在windows操作系统下最大为2^15-1（即32767），LINUX坏境下最大为2^31-1 如要生成更大范围随机数需要`rand()*rand()`或`(rand()<<15)+rand()` 2.生成指定范围的随机整数 要生成介于 0 和 99 之间的随机整数，可以使用取模运算：int num = rand() % 100; 这样，num 的值就是一个 0 到 99 之间的随机数。 3.初始化随机数种子 在使用 rand() 之前，通常需要初始化随机数种子。 一种常见的做法是使用当前时间作为种子，以确保每次运行程序时都会生成不同的随机数序列。（即使生成的数互不相同） 示例代码： ``` #include <iostream> #include <cstdlib> #include <ctime> int main() { // 初始化随机数种子 std::srand(static_cast<unsigned int>(std::time(nullptr))); // 生成 1 到 100 之间的随机数 int randomNum = std::rand() % 100 + 1; std::cout << "随机数：" << randomNum << std::endl; return 0; } ``` 参考资料：`https://blog.csdn.net/m0_60134435/article/details/136165552` ]]> 0 https://www.ciyekua.cn/index.php/diary/148.html#comments https://www.ciyekua.cn/index.php/feed/diary/148.html https://www.ciyekua.cn/index.php/diary/138.html https://www.ciyekua.cn/index.php/diary/138.html Wed, 14 Aug 2024 23:30:00 +0800 ciye 一、求区间最大值的各种方法及时间复杂度 1、朴素（即搜索），O(n)-O(qn) online。 2、线段树，O(n)-O(qlogn) online。 3、ST（实质是动态规划），O(nlogn)-O(q) online。 ST算法（Sparse Table），以求最大值为例，设d[i,j]表示[i,i+2^j-1]这个区间内的最大值，那么在询问到[a,b]区间的最大值时答案就是max(d[a,k], d[b-2^k+1,k])，其中k是满足2^k＜=b-a+1(即长度)的最大的k,即k=[ln(b-a+1)/ln(2)]。 d的求法可以用动态规划，d[i, j]=max(d[i, j-1],d[i+2^(j-1), j-1])。 4、RMQ标准算法：先规约成LCA（Lowest Common Ancestor），再规约成约束RMQ，O(n)-O(q) online。 首先根据原数列，建立笛卡尔树，从而将问题在线性时间内规约为LCA问题。LCA问题可以在线性时间内规约为约束RMQ，也就是数列中任意两个相邻的数的差都是+1或-1的RMQ问题。约束RMQ有O(n)-O(1)的在线解法，故整个算法的时间复杂度为O(n)-O(1)。 RMQ算法时间复杂度： ***时间复杂度为O(nlogn),然后可以在O(1)的时间内处理每次查询。*** 二、RMQ模板题 > https://ac.nowcoder.com/acm/contest/88527/H ac代码：`https://ac.nowcoder.com/acm/contest/view-submission?submissionId=70974305` 三、RMQ模板 ``` int n,a[1000005]; int dp[100005][25]; void rmq_init(){ for(int i = 1; i <= n; i++) dp[i][0] = a[i]; for(int j = 1; (1<<j) <= n; j++){ for(int i = 1; i+(1<<j)-1 <= n; i++){ dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]); } } } int rmq(int l, int r){ int k=0; while(1<<(k+1) < r-l+2) k++; return max(dp[l][k],dp[r-(1<<k)+1][k]); } ``` 四、参考资料 1.`https://blog.csdn.net/Struggle_0/article/details/109169076` 2.`https://blog.csdn.net/Struggle_0/article/details/109166581` ]]> 0 https://www.ciyekua.cn/index.php/diary/138.html#comments https://www.ciyekua.cn/index.php/feed/diary/138.html https://www.ciyekua.cn/index.php/diary/136.html https://www.ciyekua.cn/index.php/diary/136.html Mon, 05 Aug 2024 23:10:00 +0800 ciye gcd：最大公约数 lcm：最小公倍数 **2个数a,b的gcd、lcm：** GCD2=__gcd(a,b) LCM2=a*b/GCD **3个数a,b,c的gcd、lcm：** GCD3=__gcd(GCD2,c) LCM3=LCM2*c/GCD3 代码实现： ``` #include <iostream> using namespace std; // 求最大公约数 int GCD(int a, int b) { if (b == 0) { return a; } else { return GCD(b, a % b); } } // 求最小公倍数 int LCM(int a, int b) { return a * b / GCD(a, b); } int main() { int a, b, c; cout << "请输入三个整数：" << endl; cin >> a >> b >> c; int gcd = GCD(GCD(a, b), c); int lcm = LCM(LCM(a, b), c); cout << "最大公约数：" << gcd << endl; cout << "最小公倍数：" << lcm << endl; ``` ]]> 0 https://www.ciyekua.cn/index.php/diary/136.html#comments https://www.ciyekua.cn/index.php/feed/diary/136.html https://www.ciyekua.cn/index.php/diary/134.html https://www.ciyekua.cn/index.php/diary/134.html Sun, 04 Aug 2024 21:39:00 +0800 ciye 1.滑动窗口 2024/07/23 cf961 b1 `https://codeforces.com/contest/1995/problem/B1` （据说也可用贪心做？但不知道怎么做...） 2.gcd、lcm 2024/08/05 `https://www.ciyekua.cn/index.php/diary/136.html` 3.RMQ（求区间最大值） 2024/08/14 时间复杂度为O(nlogn),然后可以在O(1)的时间内处理每次查询。 `https://ac.nowcoder.com/acm/contest/88527/H` 4.质数筛 2024/08/14 （待补充...） 5.rand()随机化算法 2024/08/15 `https://www.ciyekua.cn/index.php/diary/148.html` ]]> 0 https://www.ciyekua.cn/index.php/diary/134.html#comments https://www.ciyekua.cn/index.php/feed/diary/134.html https://www.ciyekua.cn/index.php/diary/133.html https://www.ciyekua.cn/index.php/diary/133.html Fri, 10 May 2024 17:36:00 +0800 ciye 一、滑动窗口是什么 滑动窗口是双指针算法的一种，基本思路为维护一个窗口，然后从前往后遍历元素进行运算。 二、滑动窗口算法和其他双指针算法的区别 双指针算法常见的为三种： 1.快慢指针算法（常用于链表有环判断） 2.双向指针（两个指针一个从最左，一个从最右出发进行查找），典型应用为二分查找 3.滑动窗口（两个指针一前一后出发，两个指针中间维持一个窗口结构 [点击查看原文][1] [1]: https://blog.csdn.net/qq_54850598/article/details/127863026 ]]> 0 https://www.ciyekua.cn/index.php/diary/133.html#comments https://www.ciyekua.cn/index.php/feed/diary/133.html