logo
Redian新闻
>未名空间
>gardening - 拈花惹草
>
第一年的收成要泡汤了....
avatar
第一年的收成要泡汤了....# gardening - 拈花惹草
O*i
1 楼
严蔚敏的老书介绍的是双指针向中间移动并交换，是Hoare的版本
CLRS介绍Lomuto版本的双指针一起向右边移动，前面的开路，后面的交换，类似荷兰旗
的方法
基于这两个方法的变种就更多了，选取pivot, 有选开头的，有选末尾的，有随机选的
，有选头，中，尾三个的median的...
编程珠玑专门开了一章讲它
可是，这些细节面试官基本不考的。
唯一有用的就是双指针大法，二爷认为该大法能解决一大票问题，包括直方图盛水,
Jump game, 有序数组去重...
avatar
s*s
2 楼
第一年的新农民，今年才知道zucchini 是长地上的，西红柿还会被蜂鸟戳.....
辛苦工作两个月，眼看西红柿茄子zucchini已经挂果了，辣椒已经吃上了。忽然菜园里
遭受严重病虫害，zucchini的茎从接近根部的地方开始烂，也不知是虫害还是真菌，欲
哭无泪>_<
准备明年再战，求问版上有没有微信群，方便我随时像大牛们请教。我的坐标是8a.先
谢谢大家了！
avatar
w*x
3 楼
没错，我个人认为双指针一起右移的更好实现
avatar
K*D
4 楼
安慰一下。还好啦，不会所有菜都烂掉的。辣椒不是吃上了吗？
没救的植物拔掉，腾出地方透透气。

【在 s******s 的大作中提到】
: 第一年的新农民，今年才知道zucchini 是长地上的，西红柿还会被蜂鸟戳.....
: 辛苦工作两个月，眼看西红柿茄子zucchini已经挂果了，辣椒已经吃上了。忽然菜园里
: 遭受严重病虫害，zucchini的茎从接近根部的地方开始烂，也不知是虫害还是真菌，欲
: 哭无泪>_<
: 准备明年再战，求问版上有没有微信群，方便我随时像大牛们请教。我的坐标是8a.先
: 谢谢大家了！
avatar
s*s
6 楼
谢谢安慰，我还准备再抢救一下，往茎里打bt试试

【在 K****D 的大作中提到】
: 安慰一下。还好啦，不会所有菜都烂掉的。辣椒不是吃上了吗？
: 没救的植物拔掉，腾出地方透透气。
avatar
p*2
7 楼
我看到题目正想说呢，又是two pointers.
avatar
k*5
8 楼
zucchini可能是有虫，可以直接在烂的地方看到白色warm。 那基本是没法救了。
avatar
o*d
9 楼
我怎么觉得两头往里容易的狠很多阿?

【在 w****x 的大作中提到】
: 没错，我个人认为双指针一起右移的更好实现
avatar
o*n
10 楼
是的，前面几年我都遇到这个问题，包括日本南瓜。今年提前打药预防就没事了

【在 k***5 的大作中提到】
: zucchini可能是有虫，可以直接在烂的地方看到白色warm。 那基本是没法救了。
avatar
O*i
11 楼
这个应该就是基于Hoare版本的，可能还是Lomuto版本的更容易写，不然不会被CLRS收
录到正文。Hoare的原始版本被CLRS放到课后习题去了。

【在 c*****a 的大作中提到】
: http://www.algolist.net/img/sorts/quick-sort.png
: 我就照着这个码.....前后指针跟pivot对比...找到适合然后交换
avatar
s*s
12 楼
是的，昨天把最烂的一株拔了 （心痛死了），靠着地的茎已经完全烂了还有一股臭味
。往断口处一看一只硕大的白蠕虫趴在那里往外看，气死我了，将其大卸八块以泄愤..
..

【在 k***5 的大作中提到】
: zucchini可能是有虫，可以直接在烂的地方看到白色warm。 那基本是没法救了。
avatar
O*i
13 楼
两头往里的代码更长些吧。
Lomuto的伪代码(t is pivot)很简短
m = a - 1
for i = [a, b]
if x[i] < t
swap(++m, i)

【在 o***d 的大作中提到】
: 我怎么觉得两头往里容易的狠很多阿?
avatar
P*m
14 楼
摸头，同是新农民，死了一大堆以后就心肠变冷了！及时拔掉，种出来东西就好
avatar
o*d
15 楼
效率高些么?否则两头的可读性高吧?容易维护,呵呵

【在 O******i 的大作中提到】
: 两头往里的代码更长些吧。
: Lomuto的伪代码(t is pivot)很简短
: m = a - 1
: for i = [a, b]
: if x[i] < t
: swap(++m, i)
avatar
y*1
16 楼
想在北美种菜有很多地方要留意，新土要杀虫，美国草地下面都是红鼻虫，菜园要围铁
网防动物，小鸟也会吃西红柿，吃水果更是一绝，果肉都吃了剩下核还挂在树上，土拨
鼠(woodchuck)专吃嫩叶，所以铁网要埋在土地的一尺以下，第一年无所谓啦，慢慢来
。
avatar
O*i
17 楼
二爷整理个full list吧，leetcode中能用广义双指针解的。
你的总结文中没有正式提到快排和荷兰旗。此外我觉得Jump Game I也是双指针

【在 p*****2 的大作中提到】
: 我看到题目正想说呢，又是two pointers.
avatar
s*u
18 楼
我今年种的green zebra西红柿，鸟还没有适应。不过我一般会照bird net

【在 k***5 的大作中提到】
: zucchini可能是有虫，可以直接在烂的地方看到白色warm。 那基本是没法救了。
avatar
O*i
19 楼
Jump Game I的双指针法
bool canJump(int A[], int n)
{
int t = A[0];
if (t >= n - 1)
return true;
int s = 0;
while (s <= t)
{
if (s + A[s] > t)
{
t = s + A[s];

if (t >= n - 1)
return true;
}
s++;
}

return false;
}
avatar
D*I
20 楼
重新种还来得及
这时候长得快
avatar
p*2
21 楼

我也在总结的过程中，准备一步一步的来。
快排没有提到是因为Leetcode中没有，面试也不常见。哈兰旗就是color sort吧。Jump
Game我一会儿看一下，感觉是。我的整理现在也还不是很全面。

【在 O******i 的大作中提到】
: 二爷整理个full list吧，leetcode中能用广义双指针解的。
: 你的总结文中没有正式提到快排和荷兰旗。此外我觉得Jump Game I也是双指针
avatar
F*0
22 楼
zucchini 长得快 重新种还来得及吧。
avatar
O*i
23 楼
荷兰旗和快排有很大联系，就是leetcode的 color sort。
我记得张弛的F面试就被问到荷兰旗，他的标准无误解法还被老印质疑有bug。

Jump

【在 p*****2 的大作中提到】
:
: 我也在总结的过程中，准备一步一步的来。
: 快排没有提到是因为Leetcode中没有，面试也不常见。哈兰旗就是color sort吧。Jump
: Game我一会儿看一下，感觉是。我的整理现在也还不是很全面。
avatar
s*s
24 楼
谢谢大牛指导。我们基本就是刨个坑就开始种了，果然还是太嫩了。

【在 y***1 的大作中提到】
: 想在北美种菜有很多地方要留意，新土要杀虫，美国草地下面都是红鼻虫，菜园要围铁
: 网防动物，小鸟也会吃西红柿，吃水果更是一绝，果肉都吃了剩下核还挂在树上，土拨
: 鼠(woodchuck)专吃嫩叶，所以铁网要埋在土地的一尺以下，第一年无所谓啦，慢慢来
: 。
avatar
w*x
25 楼

Jump
当年做荷兰旗的时候只会两边夹的那种快排，所以code麻烦死，后来知道了荷兰旗的两
指针一起往右移动的解法，当时感觉就是很难想到，后来才看到两指针一起往右移的快
排方法，当时一看就想，我靠，这不是荷兰旗吗，其实顺序是反过来的...

【在 p*****2 的大作中提到】
:
: 我也在总结的过程中，准备一步一步的来。
: 快排没有提到是因为Leetcode中没有，面试也不常见。哈兰旗就是color sort吧。Jump
: Game我一会儿看一下，感觉是。我的整理现在也还不是很全面。
avatar
s*s
26 楼
还剩了几株小的没挂果的，希望能长起来。这次先把药喷上。

【在 D***I 的大作中提到】
: 重新种还来得及
: 这时候长得快
avatar
O*i
27 楼
再加几个
两个pointers从两头往中间走，可以用于reverse string和判断是否palindrome
两个pointers从头往后走，有一类是读写头法，常常用于in place的去重或者删除元素
。PIE书中去除string中的元音字母aeiou介绍了这种方法，此外可以用于有序数组去重
，还有把字符串中空格替换为%20
avatar
j*3
28 楼
求问喷的啥药?
avatar
O*i
29 楼
清华严蔚敏的书只介绍两边夹的方法，所以很多人都先入为主了，那本书至少也应该提
一下别的方法，虽然两边夹的方法是快排鼻祖Hoare的最早方法。
另外荷兰旗对相同元素的处理更好，pivot从单个数扩展为中间一段相同的数。

【在 w****x 的大作中提到】
:
: Jump
: 当年做荷兰旗的时候只会两边夹的那种快排，所以code麻烦死，后来知道了荷兰旗的两
: 指针一起往右移动的解法，当时感觉就是很难想到，后来才看到两指针一起往右移的快
: 排方法，当时一看就想，我靠，这不是荷兰旗吗，其实顺序是反过来的...
avatar
k*9
30 楼
同问

【在 j**********3 的大作中提到】
: 求问喷的啥药?
avatar
p*2
31 楼

我color sort是自己做的。只会两边夹的快排。你们说的两个指针一起走的我没看过。
不过我感觉我的代码也挺简洁的。

【在 w****x 的大作中提到】
:
: Jump
: 当年做荷兰旗的时候只会两边夹的那种快排，所以code麻烦死，后来知道了荷兰旗的两
: 指针一起往右移动的解法，当时感觉就是很难想到，后来才看到两指针一起往右移的快
: 排方法，当时一看就想，我靠，这不是荷兰旗吗，其实顺序是反过来的...
avatar
s*s
32 楼
我喷的bt，网上评价很不错，也不知道在我这里管不管用

【在 j**********3 的大作中提到】
: 求问喷的啥药?
avatar
w*x
33 楼

跪求面向对象语言版本

【在 p*****2 的大作中提到】
:
: 我color sort是自己做的。只会两边夹的快排。你们说的两个指针一起走的我没看过。
: 不过我感觉我的代码也挺简洁的。
avatar
j*3
34 楼
BT是什么咚咚?
avatar
O*i
35 楼
zhangchi贴过代码的
http://www.mitbbs.com/article/JobHunting/32089461_3.html
其实是三个指针。不过前面两个指针就是一起走，第三个指针向中间走。
前两个指针的走法，就类似CLRS快排那节介绍的Lomuto法给数组partition

【在 p*****2 的大作中提到】
:
: 我color sort是自己做的。只会两边夹的快排。你们说的两个指针一起走的我没看过。
: 不过我感觉我的代码也挺简洁的。
avatar
p*2
37 楼

太巧了，跟我的解法几乎一模一样。

【在 O******i 的大作中提到】
: zhangchi贴过代码的
: http://www.mitbbs.com/article/JobHunting/32089461_3.html
: 其实是三个指针。不过前面两个指针就是一起走，第三个指针向中间走。
: 前两个指针的走法，就类似CLRS快排那节介绍的Lomuto法给数组partition
相关阅读
请教大牛们这是什么树，果子能吃么？【最悲催的】想当农民，却不能从种子开始这贴里的伪币奖励数目让人要来个【最欢乐的】某些ID也一定有写的Costco的玫瑰好不好？庆祝两节，上几个菜！院子里的土很贫瘠，如何种菜/花？求推荐climbing roseCostco的芍药怎么样？【最悲催的】木有时间抢包子想抢包子的，注意了，三月份北加可以开始种什么？Costco买的果树苗，例如苹果树，能直接放到大盆里头阳台上栽种么?郁金香开了请问这是什么树？【最悲催的】瓜瓜静静该回来了吧？Tomato Mania【最悲催的】 屡败屡战大集锦(二)有没有人种空气草的？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。