📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 7886| 回复: 46
跳转到指定楼层
上一主题 下一主题
收起左侧

[其他] 请大家分享一下大家觉得高大上且鬼父神工的算法实现

 
全局:

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
这个世界上牛人很多,我这个老码农从几个月前重新开始刷题后,从答案里发现了不少高人们的代码实现。看完以后觉得整个人都不好了,感慨高人们是如何想到那么牛X那么简洁那么惊为天人鬼斧神工的算法的。对他们的敬仰犹如滔滔江水连绵不绝!
我来起个头,抛转引玉:

285. Inorder Successor in BST
作者: 不详 (已纳入我的个人题库)

  1.     public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
  2.         if (root == null) return null;
  3.         if (p.val >= root.val) return inorderSuccessor(root.right, p);

  4.         TreeNode successor = inorderSuccessor(root.left, p);
  5.         return successor == null ? root : successor;
  6.     }
复制代码



类似地,前驱节点也是可以如法炮制。
几个月前看完这道题的这个实现,我惊了。这就是差距啊!!他是如何想到的?!

请问大家还有没有类似的经历?放出来让我们开开眼吧!

评分

参与人数 6大米 +71 收起 理由
SwordHoly + 1 基本操作 勿6
syla + 3 很有用的信息!
初晓 + 1 赞一个
MrAtoZ + 5 给你点个赞!
crukedsh + 1 赞一个

查看全部评分


上一篇:solution通过了,但效率不高。
下一篇:纪念参加contest第一次做完
Warald 2019-1-23 04:07:37 | 只看该作者
全局:
本文被选为01/17/2019全站置顶文章之一。

本文被提升为今日话题:凡是在置顶有效期内参与讨论,提供言之有物、切中主题的高质量回复,最低奖励20大米,干货越多奖励越多。

也请大家踊跃参与,看到好回答,请加分、请顶上去。

说明:给别人加分不会扣除你的积分。

回复

使用道具 举报

全局:
lc的discussion部分看高赞答案里面one liner two liner很多
但是这些对刚开始刷题找工作的人 大部分情况并没有帮助 甚至是distraction

对于已经上岸的 为了提高自己还有些用

强烈不建议新手研究这些算法!

评分

参与人数 3大米 +44 收起 理由
yguo89 + 1 赞一个
michaelnyc + 3 兹词
Warald + 40

查看全部评分

回复

使用道具 举报

推荐
milanpato 2019-1-23 06:03:26 | 只看该作者
全局:
鬼父??
LZ的输入宝好像暴露了什么东西啊

评分

参与人数 5大米 +12 收起 理由
泊蚂蚁酱 + 1 赞一个
一蓑烟雨830 + 1 赞一个
joe297 + 1 给你点个赞!
破了洞的智囊 + 6 大家都看出来了就不要揭穿嘛
饮风醉月 + 3 手动滑稽

查看全部评分

回复

使用道具 举报

推荐
michaelnyc 2019-1-23 14:32:51 | 只看该作者
全局:
pandami 发表于 2019-1-23 06:24
lc的discussion部分看高赞答案里面one liner two liner很多
但是这些对刚开始刷题找工作的人 大部分情况并 ...

非常同意!面试写白板和在线写码的时候,更重要的还是解释清楚自己的思路,写让人容易理解的code,而不是一味地写这种code。这种鬼斧神工的code,还是适合已经上岸的人娱乐与自我提高。

想一下如果我刚开始刷leetcode的时候就去理解这种code,一定会痛苦,甚至误入歧途(没有对code负面评价的意思,只是太高深的话,不适合入门者)。刚入门的话,重要的还是,要思路清晰。

评分

参与人数 1大米 +40 收起 理由
Warald + 40

查看全部评分

回复

使用道具 举报

🔗
kissingurami 2019-1-20 04:40:17 | 只看该作者
全局:
走一个:经典0/1背包
subset sum equals to K
c++:
bool subset_sum(vector<int> &nums, int K) {
    bitset<10001> dp(1); // 0000000......0001
    for (int n : nums)  dp = dp|dp<<n;
    return dp[K];
}
给你一个眼神,自己体会。

评分

参与人数 1大米 +50 收起 理由
Warald + 50

查看全部评分

回复

使用道具 举报

全局:
kissingurami 发表于 2019/01/20 04:40:17
走一个:经典0/1背包
subset sum equals to K
c++:
bool subset_sum(vector<int> &nums, int K) {
    bitset<1...

给跪了……
回复

使用道具 举报

🔗
 楼主| moluren 2019-1-20 10:01:36 | 只看该作者
全局:
kissingurami 发表于 2019-1-20 04:40
走一个:经典0/1背包
subset sum equals to K
c++:

正好要学习背包问题,观摩一下。
回复

使用道具 举报

全局:
本帖最后由 tsl665 于 2019-1-23 12:14 编辑

鬼斧神工中的泥石流来了
猴子排序(Bogo Sort)[1]
  1. while not isInOrder(deck):
  2.     shuffle(deck)
复制代码


被加分了稍微多说一点吧(捂脸
为什么说这是泥石流呢,这个算法的平均时间复杂度,是O((n+1)!), 没错,你没看错,作为一个排序算法,它甚至不是polynomial time。
它的idea非常简单(nao)粗暴(can):
1. 我先检查一下现在的序列是不是有序。
2. 有序?好了问题解决了。不是有序?没关系我把数组打乱,然后回到1重新检查,循环。
然后问题来了,这个算法真的能做到“排序”吗?答案是,可以的。用通俗易懂的大白话解释就是,反正只有有限种可能性,我一直xjb试,总是能试出正确答案的。。。
btw,为什么叫猴子排序呢,因为这个作用原理叫做“无限猴子定理” (Infinite Monkey Theorem, [2])。大意是说,你让一只猴子在键盘上乱敲,如果无限敲下去,几乎必然(almost surely,这其实是个概率上的术语,意思是,不成功的概率=0)可以打出任何一串文字,比如,莎士比亚全集。


Reference:
[1] https://en.wikipedia.org/wiki/Bogosort
[2] https://en.wikipedia.org/wiki/Infinite_monkey_theorem

评分

参与人数 3大米 +32 收起 理由
sams + 1 很有用的信息!
nicemayi + 1 赞一个
Warald + 30

查看全部评分

回复

使用道具 举报

🔗
asd101200 2019-1-23 05:02:15 | 只看该作者
全局:
蓄水池算法
回复

使用道具 举报

🔗
bodeplot 2019-1-23 05:25:05 | 只看该作者
全局:
Binary Indexed Tree,简称BIT。

如果让你在一个大小是N的array A上支持以下的功能:
  • 在O(log N)的时间以内求任意一段的和: A(i) + A(i + 1) + ... + A(j), where i <= j(/i)
  • (i)在O(log N)的时间以内把某一个位置的数字增加x: A(i) = A(i) + x


简单数据结构只能做到一个操作O(N), 另一个O(1)。你也可以写一个balanced binary tree,在每一个node里存一个特定的sum来满足要求,但是代码量会比较大。

BIT的聪明之处就是用一个array来表示这个balanced binary tree,然后用简短的bit operation来找parent/child,极大地减小了代码量,在某些面试问题里会有奇效(e.g. LC307)。这种模式很像heap。用array也比用tree node更好做内存优化,运行起来可能也会快一些。

下面上代码(C++):

  1. // Returns sum of arr[0..index].
  2. // This function assumes that the array is preprocessed and partial sums of array elements are stored in BITree[]
  3. int getSum(int BITree[], int index) {
  4.     int sum = 0;
  5.     index = index + 1;
  6.     while (index>0) {
  7.         sum += BITree[index];
  8.         index -= index & (-index);
  9.     }
  10.     return sum;
  11. }
  12.   
  13. // Updates a node in Binary Index Tree (BITree) at given index in BITree.
  14. // The given value 'val' is added to BITree[i] and all of its ancestors in tree.
  15. void updateBIT(int BITree[], int n, int index, int val) {
  16.     index = index + 1;
  17.     while (index <= n) {
  18.         BITree[index] += val;
  19.         index += index & (-index);
  20.     }
  21. }
复制代码



这里的求和是从0到i的和。如果想要求从i到j的和,只要运行两遍,再求差就行了。

更多资料见这里: https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/

之前有一个更好的网站,但是最近排版出问题了,在我的电脑上很乱: https://www.topcoder.com/community/competitive-programming/tutorials/binary-indexed-trees/



补充内容 (2019-1-23 05:26):
管理员看到能不能帮忙改一下,把A方括号i 改成A(i)。在网页版里 A方括号i 会被理解成斜体。

补充内容 (2019-1-23 08:04):
代码是直接从geeksforgeeks复制过来的。面试里要写的话建议封装成一个class,更符合industry standard。面试官要求讲解的话可以准备一个很小的例子,把树画出来,并且举例子说明+- i & (-i)是父子节点的转换

补充内容 (2019-1-23 08:08):
LC有专门的一个tag, 里面全是BIT题目 https://leetcode.com/tag/binary-indexed-tree/ 。我不知道没有会员能不能看,不能的话,tag里的题号是218,307,308,315,493[/i]

评分

参与人数 2大米 +67 收起 理由
dayeandheye + 1 赞一个
Warald + 66

查看全部评分

回复

使用道具 举报

🔗
14417335 2019-1-23 05:34:39 | 只看该作者
全局:
睡觉排序

情绪的变化顺序:
惊,吐,服,拜。

https://www.youtube.com/watch?v=pWlc6COonc8

回复

使用道具 举报

🔗
14417335 2019-1-23 05:42:20 | 只看该作者
全局:
kissingurami 发表于 2019-1-20 04:40
走一个:经典0/1背包
subset sum equals to K
c++:

C++好强大。这个东东用java要O(10000 N)
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表