• H
    hzx__

    两个版

    • 把数组分为两部分,逆序对可能在前半部分、后半部分、一个在前半部分一个在后半部分
    • 前两种情况可以递归处理
    • 第三种情况:如果没有这种逆序对,那么进行归并排序得到mere时,前半部分就 完全在后半部分前面,否则,一旦一个后部分的 x 排到了前半部分的 index 位置,那么它与 index后面所有的前半部分的元素都形成逆序对

    三个版

    • 同样的,三个元素可能全在前半部分、后半部分,也可能两个在前一个在后、一个在前两个在后
    • 递归处理前两种情况
    • 如果只有一个在后半部分,那么这一个就是三元组逆序对的最小元素,在归并排序的mere过程中,如果后半部分 某个元素 x 插入到前半部分的index位置,那么index后的所有两元组逆序对与 x 形成 三元组逆序对,
    • 重复上一个步骤,但这次是前半部分插入到后半部分,如果 x 插入后半部分的index位置,那么index前的所有后半部分的二元组逆序对与 x 构成三元组逆对
    • 代码中前两个步骤可以合起来

    发布在 算法与数据结构讨论区 阅读更多
  • H
    hzx__

    @诟屍

    • 先定义符号,s表示字符串,p表示预处理结果
    • 确实用KMP的预处理算法,周期等于n-P[n] (n是最后一个字符)
    • 子串那个
      • 因为i-p[i]部分刚好是0到i的字符串的最小周期串
      • 所以,如果我们需要求s[p] 到 s[q] 的这个子串,其中 q-p+1 是 q-p[q]的偶数倍,那么q-p[q]就是最小周期(这里有一个漏洞,就是没有证明 一个串如果有多个周期,那么这些周期中大的是小的整数倍)
      • 如果 q-p+1 不是q q-p[]的偶数倍,那么就得用KMP那个预处理算法单独搞。

    Hint == Answer 系列

    发布在 算法与数据结构讨论区 阅读更多
  • H
    hzx__

    unsigned replace_byte(unsigned x, int i, unsigned char b)
    {
    	unsigned t = ~0;//构造0xFFFFFFFF
    	t -= (1UL<<(i+1)*8) - (1UL<<i*8);//构造诸如0xFF00FFFF
    	x = x&t;//通过&清除相应的byte
    	x = x|(b<<i*8);
    	return x;
    }
    

    发布在 CSAPP 讨论区 阅读更多
  • H
    hzx__

    记得看过一篇文章,不同语言对负数除法的取整方式不同,有的向0方向取整有的向变小方向取整。
    所以负数的整数除法的取整应该只是规则,没有对错。然后csapp讲的是计算机硬件的实现方式。

    发布在 CSAPP 讨论区 阅读更多
  • H
    hzx__

    P104有一段

    Integer division always rounds toward zero. To define this precisely, let us
    introduce some notation \cdots\cdots
    Thatis, it should round down a positive result but round up a negative one.

    发布在 CSAPP 讨论区 阅读更多

与 图灵班论坛 的连接断开,我们正在尝试重连,请耐心等待