算法数据结构中来什么奇技淫巧？
罗必成 45分钟前 58 数据结构 数组算法数据结构中，有哪些技巧或使用方式能让你觉得“卧槽，还能这样用”？想要的就是那种特别简洁，理解以后又眼前一亮的技巧~
0 赞 0 踩
其他回答
Yao's protocol.
「如何让两个女士比较出谁更胖——在她们都不想泄漏体重的前提下？」
问题是这样的：假设 Alice 手上有一个隐私函数 f，Bob 有隐私数据 x，那么请为他们设计一个协议，让双方互相不给任何人透露自己隐私的情况下，计算出 f(x) 的数值？（从 f(x) 的结果推断 x 或者 f 不算在内；双方始终遵守协议。）
实现是这样的：考虑一个 k 个 bit 到一个 bit 的简单函数 f（更复杂的函数可以简化到这个样子），alice 可以打出 f 的真值表来，然后她产生 k+1 对随机数，表示 k 个输入 bit（）和输出 bit 的 0/1 值（）。
接着她按照这些随机数加密真值表，比如如果 f(1, 1)=0，则她用两个随机数作为密钥加密产生一个密文。她可以把加密的真值表连同表示结果的随机数发给 Bob。
接下来 Bob 需要按照自己的数据（x）找 Alice 要 k 个随机数解码他拿到的真值表，真值表中只有一项可以被解码，解码的结果就是 f(x)，其他的则无法解码。
要随机数的过程是基于 Oblivious Transfer，这个协议要求：
有关 @aricatamoy「为什么不用天平」，那么请问：两个人该怎么做才能保证天平上面没被动过手脚，暗地里收集她们的体重呢？
「如何让两个女士比较出谁更胖——在她们都不想泄漏体重的前提下？」
问题是这样的：假设 Alice 手上有一个隐私函数 f，Bob 有隐私数据 x，那么请为他们设计一个协议，让双方互相不给任何人透露自己隐私的情况下，计算出 f(x) 的数值？（从 f(x) 的结果推断 x 或者 f 不算在内；双方始终遵守协议。）
实现是这样的：考虑一个 k 个 bit 到一个 bit 的简单函数 f（更复杂的函数可以简化到这个样子），alice 可以打出 f 的真值表来，然后她产生 k+1 对随机数，表示 k 个输入 bit（）和输出 bit 的 0/1 值（）。
接着她按照这些随机数加密真值表，比如如果 f(1, 1)=0，则她用两个随机数作为密钥加密产生一个密文。她可以把加密的真值表连同表示结果的随机数发给 Bob。
接下来 Bob 需要按照自己的数据（x）找 Alice 要 k 个随机数解码他拿到的真值表，真值表中只有一项可以被解码，解码的结果就是 f(x)，其他的则无法解码。
要随机数的过程是基于 Oblivious Transfer，这个协议要求：
- Bob 根据自己的选择获取 Alice 两条私密消息中的一条，另一条则无法解密；
- 而 Alice 不能得知 Bob 的选择。
- Alice 生成 RSA 公钥-密钥对，她把公钥发给 Bob，Bob 根据自己的选择获取。以下计算均在上进行。
- Alice 生成两个随机数发给 Bob。
- Bob 生成随机数 k，计算发给 Alice。由于 k 是私密的，Alice 无法解密出 c 来。
- Alice 计算，发送给 Bob。
- Bob 计算（因为），而对于另一条消息，他就无法成功解码。
有关 @aricatamoy「为什么不用天平」，那么请问：两个人该怎么做才能保证天平上面没被动过手脚，暗地里收集她们的体重呢？
Belleve 1分钟前 0条评论
0 赞 0 踩
好像没人提到fractional cascading？本身就很强大，在很多数据结构中应用广泛，比如优化range tree一个log n。先mark，等学完车补上。
============================我是来填坑的============================
我们从一个简单的算法题开始考虑：给出k个有序的数组 ，每一个长度为n；你可以对该数组进行线性时间的预处理，然后回答如下询问：给出x，回答每个数组中第一个小于x的元素是什么。
常规的想法是对于每个数组二分查找，复杂度是，而fractional cascading通过一个简单的idea允许我们做到。
进行如下的预处理：令；然后递归构造对于每一个，令为将数组的全部元素与中偶数位置的元素归并而得到的新数组。这个预处理可以在线性时间内完成，因为我们发现对于任何 i 满足 。
同时每个元素计算左右两个指针，对于中的元素（上一段中，它是通过两个有序数组归并得到的）：
1) 如果来自，则维护左右第一个来自的元素的位置；
2) 如果来自，则维护左右第一个来自的元素的位置；
这类指针可以在线性时间内通过递推求得。
对于询问x，首先在中二分并使用指针找到对应的位置。然后利用左右指针p1 p2，找到对应在中的位置。由于p1 p2在中一定只隔一个元素，故我们只要扫描常数个位置就能找到中的第一个小于x的元素（且原本属于）。以此类推，得到了的答案后，只要常数时间就能得到的答案。故总的时间复杂度为，即第一次使用了二分，之后每次都是常数查找。
该方法还使用于range tree 和 half-plane range reporting data structure（给出平面上一些直线，构造一个线性空间的数据结构，可以在的时间内回答一个点的上方有哪些直线，这里m是答案数量）等等数据结构中来优化掉一个log n因子。
============================我是来填坑的============================
我们从一个简单的算法题开始考虑：给出k个有序的数组 ，每一个长度为n；你可以对该数组进行线性时间的预处理，然后回答如下询问：给出x，回答每个数组中第一个小于x的元素是什么。
常规的想法是对于每个数组二分查找，复杂度是，而fractional cascading通过一个简单的idea允许我们做到。
进行如下的预处理：令；然后递归构造对于每一个，令为将数组的全部元素与中偶数位置的元素归并而得到的新数组。这个预处理可以在线性时间内完成，因为我们发现对于任何 i 满足 。
同时每个元素计算左右两个指针，对于中的元素（上一段中，它是通过两个有序数组归并得到的）：
1) 如果来自，则维护左右第一个来自的元素的位置；
2) 如果来自，则维护左右第一个来自的元素的位置；
这类指针可以在线性时间内通过递推求得。
对于询问x，首先在中二分并使用指针找到对应的位置。然后利用左右指针p1 p2，找到对应在中的位置。由于p1 p2在中一定只隔一个元素，故我们只要扫描常数个位置就能找到中的第一个小于x的元素（且原本属于）。以此类推，得到了的答案后，只要常数时间就能得到的答案。故总的时间复杂度为，即第一次使用了二分，之后每次都是常数查找。
该方法还使用于range tree 和 half-plane range reporting data structure（给出平面上一些直线，构造一个线性空间的数据结构，可以在的时间内回答一个点的上方有哪些直线，这里m是答案数量）等等数据结构中来优化掉一个log n因子。
刘启鹏 1分钟前 0条评论
0 赞 0 踩
登录后可回答 提交回答
关键词 :
- 上一个：发什么样文艺含蓄的表白话语？
- 下一个：没有人跟自己出口怎么办？
相关资讯
- 谋女郎章子怡素颜助阵张艺谋电影 夸赞其很浪漫
- 伊能静儿子脚踩20cm高跟鞋 与美女同框大秀长腿
- 霍思燕教育孩子好严厉 嗯哼大哭满脸鼻涕紧跟妈妈
- 莫文蔚将举办“绝色”巡回演唱会 宣传海报遭网友吐槽
- 杨幂和许凯路透照曝光 杨幂身穿白衬衣美腿隐约可见
- 拍打戏被照顾？张蓝心:不要因为我是女孩降低标准
- TVB老戏骨余慕莲化险为夷顺利出院 和以前身形模样判若两人
- 王子文晒粉丝手写信 好奇提问“为什么叫我小丸”
- 李光洙为什么宣布退出RM主持 李光洙退出runningman原因曝光
- 郑恺公司涉合同纠纷案 被强制执行3300万
推荐资讯
点击排行