AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

常用代码模板1——基础算法

作者: 作者的头像   yxc ,  2019-07-31 21:18:31 ,  阅读 69279


627


768

算法基础课相关代码模板

  • 活动链接 —— 算法基础课

快速排序算法模板 —— 模板题 AcWing 785. 快速排序

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

归并排序算法模板 —— 模板题 AcWing 787. 归并排序

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

整数二分算法模板 —— 模板题 AcWing 789. 数的范围

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

浮点数二分算法模板 —— 模板题 AcWing 790. 数的三次方根

bool check(double x) {/* ... */} // 检查x是否满足某种性质

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps 表示精度,取决于题目对精度的要求
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

高精度加法 —— 模板题 AcWing 791. 高精度加法

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

高精度减法 —— 模板题 AcWing 792. 高精度减法

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

高精度乘低精度 —— 模板题 AcWing 793. 高精度乘法

// C = A * b, A >= 0, b > 0
vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();

    return C;
}

高精度除以低精度 —— 模板题 AcWing 794. 高精度除法

// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

一维前缀和 —— 模板题 AcWing 795. 前缀和

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

二维前缀和 —— 模板题 AcWing 796. 子矩阵的和

S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵的和为:
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

一维差分 —— 模板题 AcWing 797. 差分

给区间[l, r]中的每个数加上c:B[l] += c, B[r + 1] -= c

二维差分 —— 模板题 AcWing 798. 差分矩阵

给以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵中的所有元素加上c:
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

位运算 —— 模板题 AcWing 801. 二进制中1的个数

求n的第k位数字: n >> k & 1
返回n的最后一位1:lowbit(n) = n & -n

双指针算法 —— 模板题 AcWIng 799. 最长连续不重复子序列, AcWing 800. 数组元素的目标和

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}
常见问题分类:
    (1) 对于一个序列,用两个指针维护一段区间
    (2) 对于两个序列,维护某种次序,比如归并排序中合并两个有序序列的操作

离散化 —— 模板题 AcWing 802. 区间和

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素

// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

区间合并 —— 模板题 AcWing 803. 区间合并

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}

123 评论


用户头像
haonanya   6天前     回复

太厉害了 优美的快速排序


用户头像
卖核弹的小女孩   20天前     回复

y总和小伙伴们,快排那里用【1,2】数组测试
如果是x = q[l + r >> 1]
下面用quick_sort(q, l, j), quick_sort(q, j + 1, r)才能出结果
用i结果为什么会出错
然后l + r >> 1不是就是(l+r)/2吗,为什么要用位移运算符才能ac

用户头像
李隽熙   19天前     回复

老师上课讲了 你可以再去听下
要改成i如下:
1.int x = q[(l + r + 1) / 2]
2.quick_sort(q, l, i - 1)
3.quick_sort(q, i, r);

用户头像
李隽熙   19天前     回复

然后>>确实相当于/2
所以(l + r) >> 1 == (l + r) / 2
例如:10>>1==10/2==5

用户头像
卖核弹的小女孩   18天前    回复了 李隽熙 的评论     回复

嗯嗯,谢谢小伙伴,明白了

用户头像
卖核弹的小女孩   12天前    回复了 李隽熙 的评论     回复

好的。


用户头像
huangzufenghuang   2个月前     回复

二维前缀和为什么是S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1],而不是S[x2, y2] - S[x1, y2] - S[x2, y1] + S[x1 , y1],这样不才是减去左上角吗

用户头像
Twinmoon   2个月前     回复

因为s[i,j]是表示从[0,..,i][0,…j]区间的和,其中包含s[i][j]。


用户头像
小霸王   3个月前     回复

y总。我想问问,实现快速排序其实有很多种方法,但有没有一种最好的方式呀?我在《数据结构与算法 c语言描述》中看到关于快排的一种说发,说用左端,右端和中心位置上的三个元素的中值作为枢纽元,然后加上插叙排法+加上处理集聚相等元素这样做法是最好的,考虑最全面的,这种说法对么?那y总的模板是有考虑这么多极端情况么?还是说 这个模板只是针对普通情况呀?

用户头像
小霸王   3个月前     回复

补充一点:在个数小于四个时采用插入排序应该比快速排序快,所以快排序时分类,大于四个时就快速排序,小于四个就采用插入排序

用户头像
来夕   3个月前    回复了 小霸王 的评论     回复

模版没有对这些复杂情况进行讨论,如果想知道最快的可以看看stl源码

用户头像
LHHHHHH   1个月前    回复了 小霸王 的评论     回复

快排和归并模板是基于平均时间复杂度来说是O(nlogn) 如果考虑多种情况的话例如相对有序的数对那插入排序当然最好只有O(n),不过平均时间复杂度是O(n²),具体问题具体分析

用户头像
Nopainnogain.   1个月前    回复了 小霸王 的评论     回复

真正意义上 想要让快排达到最快效率 最好的办法就是随机选择一个值作为枢纽元 因为这样子才可以使得初试序列尽可能无序 所以在库函数底层 是随机选择一个位置的数作为枢纽的 但是 遗憾的是 计算机没有真正的随机数 库函数中的random函数生成的随机数也非真正机器自己生成的随机数 所以理论上快排不能达到最好 只有更好 选值最好方式就是随机选枢纽。


用户头像
Sukai   3个月前     回复

y总,模版我记下了,但是还是不太懂里面的细节,比如边界条件之类的,在写代码的过程中我常常反问自己为什么这里要加等号这里不加等号,然后就进入到递归里面一个一个的去分析,搞得晕头转向的,最后也不了了之

用户头像
张大壮   1个月前     回复

兄弟我也是,进递归里面分析搞的脑瓜子嗡嗡


用户头像
Rambo   5个月前     回复

快排

do i ++ ; while (q[i] < x);//这里为什么不能写q[i] <= x
用户头像
re0_614   5个月前     回复

我感觉是为了处理多个 $x$ 的情况

用户头像
Delayeddesire   4个月前     回复

感觉是这样的,对于序列 1 2 3 4 5,假设选取 5 为特定值,如果采用 <=,那么i会一直自增导致数组会越界,但是如果你采用的 < 那么一定会在数组中的某个位置停下来,因为特定值就在数组中,此例子中会在 5 的地方停下来。

用户头像
yxc   4个月前     回复

快排的边界情况太多了,很dirty,建议直接背过一个模板即可。如果自己修改完发现错了,可以手动模拟错误数据的执行过程,就可以发现是哪里出现问题了。

用户头像
Monster_   2个月前     回复

用2 1模拟一下即可 x取1

2 <i
1 <j
看i 2不是小于等于1,不移动
看j 1是大于等于1的,移动


2 <i <j
1
看i 2不是小于等于1,不移动
看j 2是大于等于1的,移动


() <j
2 <i
1
j越界了


用户头像
我是管小亮   5个月前     回复

y总,快排模板你不改改啊~那两个do while,不然除了C++之外挺难受的,哈哈

用户头像
yxc   5个月前     回复

这两行可以写成:

while (q[ ++ i] < x);
while (q[ -- j] > x);
用户头像
Rambo   5个月前    回复了 yxc 的评论     回复

为什么不能写等于,q[ ++ i] <= x

用户头像
yxc   4个月前    回复了 Rambo 的评论     回复

快排的边界情况太多了,很dirty,建议直接背过一个模板即可。如果自己修改完发现错了,可以手动模拟错误数据的执行过程,就可以发现是哪里出现问题了。


用户头像
yhyh   5个月前     回复

花了一天+刷完了模板1,加油呀,谢谢y神的总结哟>.<

用户头像
yxc   5个月前     回复

客气啦,加油hh


用户头像
ywt51   6个月前     回复

归并排序算法模板 —— 模板
最后一个合并的地方i=l; j=0 这个位置的初始值赋值不太理解,为什么j是0啊

用户头像
LH   5个月前     回复

其实只是为了计数,将tep数组里的值赋给a,只是用了后面不再用的变量j,改变了j的意义,把变量j改成其他的变量也可以

用户头像
yxc   5个月前     回复

j是用来遍历tmp[]数组的,在tmp[]数组里存的时候是从下标0开始的,所以j也要从0开始。


用户头像
YaoZH   6个月前     回复

请问快排是不稳定的🐎

用户头像
hua   6个月前     回复

是的

用户头像
YaoZH   6个月前    回复了 hua 的评论     回复

谢谢👌


用户头像
Three_Tree   6个月前     回复

归并排序,需不需要在最后一个语句下面加上return。

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
    //这里在加上return,表示返回上一层
    return;
用户头像
yxc   6个月前     回复

不需要,函数执行完以后会自动return。


用户头像
醉生梦死   7个月前     回复

归并排序的模板那里

while (i <= mid && j <= r)
        if (q[i] < q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

中的q[i] < q[j] 应该最好换成 q[i] <= q[j] 吧,毕竟要保持归并排序是“稳定”的

用户头像
yxc   7个月前     回复

代码已更新。


用户头像
chwma   8个月前     回复

quick_sort(q, l, j)
这个为什么quick_sort(q, l, j-1)会是错的?
既然j左边的元素都小于等于j,右边的元素都大于等于j,那么j这个值应该可以不用再参与排序了吧

用户头像
yxc   8个月前     回复

建议对照错误数据调试。快速排序代码的边界情况很多,推荐背一个现成的模板。

用户头像
zybj3   7个月前     回复

这个模版只是确保1~j区间内的都是小于等于x的数,j + 1~ r 都是大于x的数。一轮操作之后x不一定位于j这个位置上,所以quick_sort(q, l, j-1)可能是错的

用户头像
chwma   7个月前    回复了 zybj3 的评论     回复

嗯好像是这样的,谢谢大佬


用户头像
bpink   9个月前     回复

请问一下,二分查找的两个模板中,这两个模版是应用于不同类型的题目划分的区间,还是只是对于同一种题目的两种解法呢

用户头像
yxc   8个月前     回复

一般每道题目这两个模板都可以用,不过会有一个模板更好写一点。

用户头像
bpink   8个月前    回复了 yxc 的评论     回复

get!谢谢y总~


用户头像
jerryflymi   9个月前     回复

y总给的快排的模版只是将小于等于x的数放在了左边,大于等于x的数放在了右边,但是并不能实现每一趟都把x放在它最终的位置上。

用户头像
yxc   8个月前     回复

对滴。

用户头像
Udsnf   7个月前     回复

哎? 为什么?既然 所有小于等于x的在左边 并且 所有大于等于x的在右边 那么x为什么不在最终位置上?

用户头像
Udsnf   7个月前    回复了 yxc 的评论     回复

y总 求教
为什么 所有小于等于x的在左边 并且 所有大于等于x的在右边 那么x为什么不在最终位置上?

用户头像
yxc   7个月前    回复了 Udsnf 的评论     回复

注意小于等于x的数在左边,但并不是在x的左边,所以两段的分界点上的数不一定是x。

用户头像
Udsnf   7个月前    回复了 yxc 的评论     回复

哦 我的理解是:如果序列中不包含相同元素那么分界点上的数就是x了

用户头像
yxc   6个月前    回复了 Udsnf 的评论     回复

不一定的。


用户头像
yanxie411   10个月前     回复

y总给的快排的模版也适用于数组中有重复元素的情况吗, 我试了一下, 好像如果有重复元素的话就不行了。能帮忙解答一下吗? 🙏

用户头像
yxc   9个月前     回复

适合的,你应该是某些地方写错了。


用户头像
Arroganceの浓   10个月前     回复

我一直用的二分模板是这样的,区别大吗,我感觉我好像包括了两个模板把

int bsearch(int l,int r)
{
while(l<=r)
{
int mid = l+r >>1;
if(chekc(mid))r=mid-1;
else l = mid + 1;
}
return l - 1;
}

用户头像
Arroganceの浓   10个月前     回复

额怎么贴代码的我不会。。。

用户头像
Ripple-zjw   10个月前    回复了 Arroganceの浓 的评论     回复

用你键盘左上角的 ,打六下,把代码放在前三个和后三个之间。然后前三个后面还可以写上你用的是什么语言,比如cpp`。具体你可以看Markdown语法。

int bsearch(int l,int r)
{
while(l<=r)
{
int mid = l+r >>1;
if(chekc(mid))r=mid-1;
else l = mid + 1;
}
return l - 1;
}
用户头像
Ripple-zjw   10个月前    回复了 Arroganceの浓 的评论     回复

。。。那个点没显示出来,就是这个键~

用户头像
Arroganceの浓   10个月前    回复了 Ripple-zjw 的评论     回复
这样吗
用户头像
Arroganceの浓   10个月前    回复了 Ripple-zjw 的评论     回复

会了,多谢

用户头像
yxc   9个月前    回复了 Arroganceの浓 的评论     回复

二分模板有很多,背一个经过验证的即可。


用户头像
熠丶   10个月前     回复

在高精度乘法的模板中
vector[HTML_REMOVED] mul(vector[HTML_REMOVED] &A,int B)
为什么要加&?
我去掉&时也能ac
加上&有什么好处吗

用户头像
mach4101   10个月前     回复

速度更快,加上&相当于传了个地址编号过去,不加的话就需要将整个数组的内容传过去

用户头像
minux   10个月前     回复

参数使用引用, 不必要复制整个栈中的值, 空间被优化了一波

用户头像
熠丶   10个月前    回复了 minux 的评论     回复

是不是时间换空间 ?我用两种方法的话看测试数据加&时间会变长

用户头像
minux   10个月前    回复了 熠丶 的评论     回复

&仅仅是内存标签作为参数传过去和传地址类似, 但是值参数传递就是开辟一块空间将原来参数信息复制到这块空间中,效率上&会高一些

用户头像
yxc   10个月前    回复了 熠丶 的评论     回复

楼上同学解释地不错,不是时间换空间,而是时间和空间都变小了。


用户头像
mzhccc   2020-02-16 11:37     回复

用数组做离散化

#include<bits/stdc++.h>
#define N 300010
#define For(i,l,r) for(int i = l;i<=r;i++)
using namespace std;
int all[N],allsi;int q[N];
int n,m;
struct node{
    int fir;
    int sec;
};
node add[N],que[N];int addsi,quesi;
int main(){
    cin>>n>>m;
    For(i,1,n){//存储操作并把点保存。 
        int x,c;
        cin>>x>>c;
        add[++addsi].fir=x;add[addsi].sec=c;
        all[++allsi]=x;
    }
    For(i,1,m){//存储查询的点 
        int l,r;
        cin>>l>>r;
        que[++quesi].fir=l;que[quesi].sec=r;
        all[++allsi]=l;all[++allsi]=r;
    }
    sort(all+1,all+allsi+1);//排序 
    allsi=unique(all+1,all+allsi+1)-(all+1);//去重并获取最后一个数的下标 
    For(i,1,n){//进行操作。【对离散化后的数组】 
        int x = lower_bound(all+1,all+allsi+1,add[i].fir)-all;
        q[x]+=add[i].sec;
    }
    For(i,1,allsi){//计算前缀和 
        q[i]+=q[i-1];
    }
    For(i,1,m){//查找离散化后的位置,输出答案 
        int l,r;
        l = lower_bound(all+1,all+allsi+1,que[i].fir)-all;
        r = lower_bound(all+1,all+allsi+1,que[i].sec)-all;
        cout<<q[r]-q[l-1]<<endl;
    }
}
用户头像
yxc   2020-02-16 13:46     回复

不错!

用户头像
mzhccc   2020-02-16 14:26    回复了 yxc 的评论     回复

谢谢y总


用户头像
Ker   2020-02-07 01:44     回复

可否请教一下高精x高精

用户头像
yxc   2020-02-14 10:48     回复

比较快的方式是用快速傅里叶变换,可以百度一下。

用户头像
Ker   2020-02-14 12:53    回复了 yxc 的评论     回复

好的,谢谢大佬


用户头像
小白菜_ruc   2019-12-11 03:25     回复

闫总你好,请问算法基础课程的例题讲解是用cpp来讲吗?谢谢啦!

用户头像
只想AC一次   2019-12-11 08:32     回复

都是c++

用户头像
yxc   2019-12-16 16:01     回复

对滴


用户头像
发光二极管   2019-12-08 11:11     回复

y总感觉mergeSort可以一个while循环搞定V(^_^)V

void merge_sort(int nums[], int left, int right) 
{
    if (left >= right) return ;
    int mid = left + ((right - left) >> 1);
    merge_sort(nums, left, mid);
    merge_sort(nums, mid + 1, right);

    int k = left, l = left, r = mid + 1;
    while (k <= right) 
    {
        if ((r > right) || (l <= mid && nums[l] <= nums[r])) tmp[k++] = nums[l++];
        else tmp[k++] = nums[r++];
    }

    for (int i = left; i <= right; ++i) nums[i] = tmp[i];
}
用户头像
yxc   2019-12-08 13:20     回复

很好!只要代码正确即可,写法不唯一,选择一种自己最习惯的就好。

用户头像
发光二极管   2019-12-09 00:26    回复了 yxc 的评论     回复

^ - ^嗯嗯


用户头像
hbhdhd   2019-11-19 12:45     回复

为啥整数二分里 区间[l, r]被划分成[l, mid - 1]和[mid, r]时 mid = l+r+1>>1啊

用户头像
yxc   2019-11-19 14:15     回复

否则会有边界问题,当l == r - 1时,mid会等于l,那么此时如果执行l = mid就死循环了。

用户头像
hbhdhd   2019-11-19 14:22    回复了 yxc 的评论     回复

晓得了,谢谢大佬


用户头像
WenQ   2019-11-13 13:54     回复

请问为什么在快排的子函数里, x = q[l + r >> 1],时间正常;当我写成 x = q[l ]的时候,会报超时错误呢,他俩在运行时间上有什么差别吗?

用户头像
yxc   2019-11-13 17:37     回复

后来加强了数据,具体可以参考这篇讨论帖及其评论内容:AcWing 785. 注意本题数据已加强。

用户头像
WenQ   2019-11-14 05:20    回复了 yxc 的评论     回复

明白了,谢谢

用户头像
minux   10个月前     回复

如果被排序数据具有单调性的话,pivot选择使用q[l]的方法将导致时间复杂度从O(NlgN)退化到O(N^2),一般pivot选择选择用mid或者随机化方式降低退化的概率

用户头像
yxc   10个月前    回复了 minux 的评论     回复

对滴。


用户头像
Leonardo   2019-10-12 09:57     回复

浮点数二分法是不是-1到1没法算呀?

用户头像
yxc   2019-10-14 14:49     回复

可以算的,终止条件是区间长度,和区间两个端点的具体取值无关。

用户头像
Leonardo   2019-10-15 08:31    回复了 yxc 的评论     回复

例如:求0.125的三次方根,结果应该是0.5。通过二分,mid越来越小,绝对值小于1的数乘方越来越小。

用户头像
yxc   2019-10-15 16:00    回复了 Leonardo 的评论     回复

如果mid的三次方小于0.5,就应该选择[mid, r]这个区间,否则选择[l, mid]这个区间,只要0.5在[l, r]中,就一定可以二分出来。

用户头像
Leonardo   2019-10-16 02:00    回复了 yxc 的评论     回复

按照模板,求0.125的三次方根时,l=0, r=0.125,是不是mid无法取到大于0.125

用户头像
yxc   2019-10-17 13:57    回复了 Leonardo 的评论     回复

模板里没有说让r = 0.125啊,需要自己根据题目来判断l和r的取值,要保证答案一定在[l, r]中。

用户头像
Leonardo   2019-10-19 13:52    回复了 yxc 的评论     回复

现在明白了,谢谢。


用户头像
bmdxyn0725   2019-10-10 01:20     回复

AcWing 790. 数的三次方根 这个模版, 为什么check(mid)后, l 与 r的更新都是mid呢?

用户头像
yxc   2019-10-11 06:30     回复

因为相比于整数,实数可以取任意值,不存在中点取不到的情况。


用户头像
Octopus   2019-09-27 22:32     回复

为什么快排在 相等的情况下也要交换

用户头像
yxc   2019-09-28 13:17     回复

就算法而言,这里交不交换都是正确的,但这里在相等时也停止可以让代码简洁一些。


用户头像
AYX   2019-09-17 03:55     回复

关于快排的模板:
int i = l - 1, j = r + 1,
左边指针i为啥要-1,如果l==0,那i岂不是变成-1了?
同样,r为啥要+1?

用户头像
yxc   2019-09-17 04:06     回复

每次迭代i会先加1,再判断;同样j也是先减一再判断。

用户头像
yxc   2019-09-17 04:08     回复

所以就将最开始的l - 1和r + 1抵消成l和r了。

用户头像
AYX   2019-09-17 04:42    回复了 yxc 的评论     回复

明白了
另外发现了一个网站bug哈,在手机上打开没法回复~~
期待啥时候搞个app,以方便大家利用碎片时间学习

用户头像
AYX   2019-09-17 09:40    回复了 yxc 的评论     回复

另外,还发现一个特别奇妙的地方,就是quick_sort(q, l, j), quick_sort(q, j + 1, r), 用j,j+1来划分,为啥这里不用i来划分?

用户头像
yxc   2019-09-20 05:01    回复了 AYX 的评论     回复

手机是什么系统,以及用的是哪个浏览器啊,可能是有些语法不兼容。

用户头像
yxc   2019-09-20 05:06    回复了 AYX 的评论     回复

也可以用i - 1, i来划分,但分界点也需要相应变一下,不能使用q[l],因为当区间长度是2的时候,如果x = q[l],并且q[l] < q[r],就会无限递归。

用户头像
AYX   2019-09-21 15:49    回复了 yxc 的评论     回复

iOS,自带的safari

用户头像
yxc   2019-09-23 12:10    回复了 AYX 的评论     回复

好滴,我去排查一下

用户头像
寒星吻月   9个月前    回复了 yxc 的评论     回复

这里应该是q[l] > q[r]才会无限递归。。

用户头像
yxc   9个月前    回复了 寒星吻月 的评论     回复

不是的,q[l] > q[r]时会直接return。无限递归产生的原因是当区间长度为2时,划分成的两个区间的长度分别是0和2,就无限递归了。


用户头像
Vodka编程菜菜   2019-09-10 01:32     回复
int partition(vector<int>& input, int l, int r) {
    int v = input[r];
    int s = l, e = r-1;
    while(s<=e) {
        while(s<=e && input[s]<=v) s++;
        while(s<=e && input[e]>=v) e--;
        if(s<=e) swap(input[s],input[e]);
    }
    swap(input[s],input[r]);
    return s;
}

void quicksort(vector<int>&input, int l, int r) {

    if (l >= r) return;
    int pivot = partition(input, l, r);
    //cout << pivot << endl;
    quicksort(input, l, pivot-1);
    quicksort(input, pivot+1, r);
    return ;
}

这个虽然罗嗦感觉更适合面试使用。

用户头像
yxc   2019-09-10 02:43     回复

棒!也是可以的hh

用户头像
北极熊问企鹅为啥不去找它玩   11个月前    回复了 yxc 的评论     回复
int partition(vector<int>& a, int l, int r)
{
    int v = a[l + r >> 1];
    swap(a[l + r >> 1], a[r]);
    int s = l, e = r - 1;
    while(s <= e)
    {
        while(s <= e && a[s] <= v) s++;
        while(s <= e && a[e] >= v) e--;
        if(s <= e) swap(a[s], a[e]);
    }
    swap(a[s], a[r]);
    return s;
}

void quicksort(vector<int>& a, int l, int r)
{
    if(l >= r) return;
    int p = partition(a, l, r);
    quicksort(a, l, p - 1);
    quicksort(a, p + 1, r);
}

按上面这位的写法,我把分界点变成了中点,可是还是要超时是怎么回事捏?

用户头像
yxc   11个月前    回复了 北极熊问企鹅为啥不去找它玩 的评论     回复

这种写法当所有数均相同时会变成 $O(n^2)$ 的复杂度。

用户头像
北极熊问企鹅为啥不去找它玩   11个月前    回复了 yxc 的评论     回复

啊对的!大佬太喜欢你这回复的效率了!

用户头像
北极熊问企鹅为啥不去找它玩   11个月前    回复了 yxc 的评论     回复

大佬所以你的写法在任何时候都不会变成O(n^2)是嘛?

用户头像
yxc   11个月前    回复了 北极熊问企鹅为啥不去找它玩 的评论     回复

也是会的。不过被出题人卡的概率不大。

用户头像
LJX_   3个月前    回复了 北极熊问企鹅为啥不去找它玩 的评论     回复

超时的根本原因是a[s]<=v和a[e]>=v这两个条件,也就是遇到和分界点相等的数时不会停下,这样遇到所有数相同时切分就会很不均衡,导致退化。
解决方法是修改成a[s]<v和a[e]>v并做一些其他改动,也就是遇到与分界点相等的数仍然停下:(我基于你代码改的模板hh,既能保证每轮分界点处于正确位置,也能AC)

int partition(int a[], int l, int r)
{
    int v = a[l + r >> 1];
    swap(a[l + r >> 1], a[r]);
    int i = l-1, j = r;
    while(1)
    {
        while(a[++i] < v) if(i==r) break;
        while(a[--j] > v) if(j==l) break;
        if(i >= j) break;
        swap(a[i],a[j]);
    }
    swap(a[i], a[r]);
    return i;
}

void quicksort(int a[], int l, int r)
{
    if(l >= r) return;
    int j = partition(a, l, r);
    quicksort(a, l, j - 1);
    quicksort(a, j + 1, r);
}

用户头像
Vodka编程菜菜   2019-09-09 01:14     回复

这模板总结的好!不过我更倾向于根据这个帖子总结出自己的模板。

用户头像
yxc   2019-09-09 03:25     回复

是的hh 自己最习惯的模板,才是最好的模板~


用户头像
goontry   2019-08-29 11:10     回复

aaa, y总快排中while循环内,缺少else。

用户头像
yxc   2019-08-29 11:11     回复

快排模板有很多hh 这里给出的模板可以不用写else ~

用户头像
goontry   2019-08-29 11:19    回复了 yxc 的评论     回复

不写else,会tle的。试了好久[jiong]

用户头像
yxc   2019-08-29 11:23    回复了 goontry 的评论     回复

你说的带else的版本在哪

用户头像
goontry   2019-08-30 01:13    回复了 yxc 的评论     回复

hhaa, y总抱歉,我刚反应过来。又试了一下,发现是我代码写错了。

用户头像
yxc   2019-08-30 11:37    回复了 goontry 的评论     回复

好的hh

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息