3月份还没开胡 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Stock

3月份还没开胡

3月份还没开胡# Stock

s*n2011-03-07 08:03

1 楼

两道leetcode原题
1. 判断一个array of integer是不是单调: 12345 = true, 54321 = true, 12321 =
false, 11111 = true, 11112 = true, 22221 = true, 11221 = false
2. flatten bst成为linkedlist，要求最后的linkedlist必须是sorted而且不能占用额
外的空间。
没刷到这两道题，第二道题磕磕碰碰没做完
脸家前辈来说说是不是这样就没戏了？
谢谢

f*w2011-03-07 08:03

2 楼

不知道算数对不对哦，对的话就很便宜的买了
4张digiorno的pizza，我们这是6.99
bogo，即2张pizza钱，用一张buy2 get 1（coupons.com50265 )
不过是up to 6.01，
即6.99+0.98=8块钱买4张pizza，若可凑单更便宜
这个算数正常小二都该给过的，如果小二季度picky，你只有good luck啦
当然如果买6张pizza，不知道是不是可以3张pizza的钱用两张bogo，那就更便宜了。6.
99+0.98+0.98=9刀6张pizza
如果你有off胖子更便宜咯

F*k2011-03-07 08:03

3 楼

惨啊

i*d2011-03-07 08:03

4 楼

第二题不是就直接inorder吗

s*c2011-03-07 08:03

5 楼

买6张应该是出6.99+6.99+0.98吧?
看小二怎么理解了

6.

【在 f*******w 的大作中提到】

: 不知道算数对不对哦，对的话就很便宜的买了
: 4张digiorno的pizza，我们这是6.99
: bogo，即2张pizza钱，用一张buy2 get 1（coupons.com50265 )
: 不过是up to 6.01，
: 即6.99+0.98=8块钱买4张pizza，若可凑单更便宜
: 这个算数正常小二都该给过的，如果小二季度picky，你只有good luck啦
: 当然如果买6张pizza，不知道是不是可以3张pizza的钱用两张bogo，那就更便宜了。6.
: 99+0.98+0.98=9刀6张pizza
: 如果你有off胖子更便宜咯

S*I2011-03-07 08:03

6 楼

第二题磕磕碰碰不应该啊；LC上的原题是从sorted linked list转BST，算是有一点难
度；反过来一个in-order traversal就解决了。

【在 s****n 的大作中提到】

: 两道leetcode原题
: 1. 判断一个array of integer是不是单调: 12345 = true, 54321 = true, 12321 =
: false, 11111 = true, 11112 = true, 22221 = true, 11221 = false
: 2. flatten bst成为linkedlist，要求最后的linkedlist必须是sorted而且不能占用额
: 外的空间。
: 没刷到这两道题，第二道题磕磕碰碰没做完
: 脸家前辈来说说是不是这样就没戏了？
: 谢谢

f*w2011-03-07 08:03

7 楼

是啊，一般小二应该算不过来的，用2张胖我觉得没问题，于理也没错

【在 s*****c 的大作中提到】

: 买6张应该是出6.99+6.99+0.98吧?
: 看小二怎么理解了
:
: 6.

c*a2011-03-07 08:03

8 楼

什么叫 “判断一个array of integer是不是单调”？
单调增，单调减？
O(N)?

【在 s****n 的大作中提到】

w*a2011-03-07 08:03

9 楼

bogo胖子是哪期报纸的？

6.

【在 f*******w 的大作中提到】

: 是啊，一般小二应该算不过来的，用2张胖我觉得没问题，于理也没错

W*o2011-03-07 08:03

10 楼

左右各扫一遍即可，复杂度没变化

: 什么叫 “判断一个array of integer是不是单调”？

: 单调增，单调减？

: O(N)?

【在 c*******a 的大作中提到】

: 什么叫 “判断一个array of integer是不是单调”？
: 单调增，单调减？
: O(N)?

c*52011-03-07 08:03

11 楼

cvs的deal bogo

【在 w****a 的大作中提到】

: bogo胖子是哪期报纸的？
:
: 6.

c*a2011-03-07 08:03

12 楼

解释一下题目的意思吧

【在 W***o 的大作中提到】

: 左右各扫一遍即可，复杂度没变化
:
:
: 什么叫 “判断一个array of integer是不是单调”？
:
: 单调增，单调减？
:
: O(N)?
:

c*52011-03-07 08:03

13 楼

其实买4个也很挑战小二了~~~

6.

【在 f*******w 的大作中提到】

: 是啊，一般小二应该算不过来的，用2张胖我觉得没问题，于理也没错

W*o2011-03-07 08:03

14 楼

楼猪的例子已经不能再清楚了

: 解释一下题目的意思吧

【在 c*******a 的大作中提到】

: 解释一下题目的意思吧

f*w2011-03-07 08:03

15 楼

买4个用1张胖正常也应该过的，除了picky到一塌糊涂的小二会jjww

【在 c*******5 的大作中提到】

: 其实买4个也很挑战小二了~~~
:
: 6.

t*b2011-03-07 08:03

16 楼

牛我还想着用个flag标一下增减
这样写个helper 然后扫两遍就够了又快又好

【在 W***o 的大作中提到】

: 左右各扫一遍即可，复杂度没变化
:
:
: 什么叫 “判断一个array of integer是不是单调”？
:
: 单调增，单调减？
:
: O(N)?
:

f*y2011-03-07 08:03

17 楼

买6个最划算，好像还有个$2/2，可以一起用吗？这样就可以彻底把小二弄晕
我们这家店以前用BOGO胖子还可以搭一张$xoff的

y*x2011-03-07 08:03

18 楼

扫一遍看最大最小值是不是在两端也行吧。

: 牛我还想着用个flag标一下增减

: 这样写个helper 然后扫两遍就够了又快又好

【在 t****b 的大作中提到】

: 牛我还想着用个flag标一下增减
: 这样写个helper 然后扫两遍就够了又快又好

f*w2011-03-07 08:03

19 楼

胖子是二维码的，不知道对应几个东西

【在 f*******y 的大作中提到】

: 买6个最划算，好像还有个$2/2，可以一起用吗？这样就可以彻底把小二弄晕
: 我们这家店以前用BOGO胖子还可以搭一张$xoff的

t*b2011-03-07 08:03

20 楼

1 2 4 3 5
就不行啊

【在 y******x 的大作中提到】

: 扫一遍看最大最小值是不是在两端也行吧。
:
:
: 牛我还想着用个flag标一下增减
:
: 这样写个helper 然后扫两遍就够了又快又好
:

l*72011-03-07 08:03

21 楼

冒胖子了……

【在 f*******w 的大作中提到】

: 胖子是二维码的，不知道对应几个东西

x*r2011-03-07 08:03

22 楼

楼主运气真好，碰到这么简单的题
楼主运气真背，这么简单的题竟然没有刷到

f*y2011-03-07 08:03

23 楼

真的没了，昨天只打印了一张
本来想说今天再补一张的

【在 l******7 的大作中提到】

: 冒胖子了……

s*a2011-03-07 08:03

24 楼

这种题目不准备也应该做好的得练练基本功啊

f*w2011-03-07 08:03

25 楼

不会吧，我发帖子前刚打的啊
换个zip再试试
已经打印过一张通常在最后一页啊

【在 f*******y 的大作中提到】

: 真的没了，昨天只打印了一张
: 本来想说今天再补一张的

t*n2011-03-07 08:03

26 楼

刷了poj 这些题就如同小儿科 40W大包送上门

w*02011-03-07 08:03

27 楼

一天不来就会miss掉好deal.5555..coupon没有了.

o*p2011-03-07 08:03

28 楼

小苑城边猎骑回
手中已有新春桂
一方狱市获来苏
伸舒轶出元气外
包含万象藏心里
子若得之慎勿失
来时歌舞助欢娱

f*y2011-03-07 08:03

29 楼

好像真的木有了555，昨天打印了一张，看看过期日太近，想说等明天打印应该不晚吧
上次洗发水也是这样子的，我怎么还不吸取教训！！

【在 f*******w 的大作中提到】

: 不会吧，我发帖子前刚打的啊
: 换个zip再试试
: 已经打印过一张通常在最后一页啊

s*b2011-03-07 08:03

30 楼

不懂啊。左右扫一遍然后呢？

【在 W***o 的大作中提到】

: 左右各扫一遍即可，复杂度没变化
:
:
: 什么叫 “判断一个array of integer是不是单调”？
:
: 单调增，单调减？
:
: O(N)?
:

w*02011-03-07 08:03

31 楼

一天不来就会miss掉好deal.5555..coupon没有了.

s*b2011-03-07 08:03

32 楼

不许用额外空间怎么办？

【在 S**I 的大作中提到】

: 第二题磕磕碰碰不应该啊；LC上的原题是从sorted linked list转BST，算是有一点难
: 度；反过来一个in-order traversal就解决了。

f*w2011-03-07 08:03

33 楼

ft居然真的没了

l*82011-03-07 08:03

34 楼

第一题我也不太会，在网上搜的一个答案，不知道大牛具体是怎么做的。
public boolean isIncreasingOrDecreasing(int[] arr) {
boolean increasing = true, decreasing = true;
if (arr.length <= 2) {
return true;
}
for (int i = 1; i < arr.length; i++) {
if (arr[i] < arr[i-1]) {
increasing = false;
}
if (arr[i] > arr[i-1]) {
decreasing = false;
}
if (!increasing && !decreasing) {
return false;
}
}
return true;
}

l*o2011-03-07 08:03

35 楼

上午还有就已经很奇迹了。
我昨晚3点走的时候去打，最开始的zip就已经没了。。

【在 f*******w 的大作中提到】

: ft居然真的没了

u*n2011-03-07 08:03

36 楼

对的，扫一遍就可以了，一个判断增，一个判断减，只要有一个判断全过就是单调

【在 l**8 的大作中提到】

: 第一题我也不太会，在网上搜的一个答案，不知道大牛具体是怎么做的。
: public boolean isIncreasingOrDecreasing(int[] arr) {
: boolean increasing = true, decreasing = true;
: if (arr.length <= 2) {
: return true;
: }
: for (int i = 1; i < arr.length; i++) {
: if (arr[i] < arr[i-1]) {
: increasing = false;
: }

w*02011-03-07 08:03

37 楼

freschetta pizza还有1.5刀off两个。这个牌子没吃过呢？cvs有吗？

u*n2011-03-07 08:03

38 楼

不需要额外空间，linkedlist value就是Treenode

【在 s******b 的大作中提到】

: 不许用额外空间怎么办？

f*w2011-03-07 08:03

39 楼

挺好吃。。。。。。。。。。。。。。没有

【在 w******0 的大作中提到】

: freschetta pizza还有1.5刀off两个。这个牌子没吃过呢？cvs有吗？

t*b2011-03-07 08:03

40 楼

这个太长而且引入了变量不够优雅我来抛个砖
private bool isInc (int[] array) {
for(int i=0;iif(array[i]>array[i+1]) return false;
}
return true;
}
public bool isMono (int[] array) {
return isInc(array) || isInc(array.reverse());
}

【在 l**8 的大作中提到】

f*w2011-03-07 08:03

41 楼

3点。。。。。
好胖子居然只给两个zip，而且还死得那么快，ft
而且每个zip还不一样价

【在 l*****o 的大作中提到】

:
: 上午还有就已经很奇迹了。
: 我昨晚3点走的时候去打，最开始的zip就已经没了。。

W*o2011-03-07 08:03

42 楼

几个月之前写的代码
public static boolean isMonotonic(int[] A) {
int n = A.length, start = 1;
while (start < n && A[start] == A[start-1]) { start++; }
if (start == n) return true; // NOTE: critical
boolean isIncreasing = A[start] > A[start-1];
for (int i = start + 1; i < n; i++) {
if (isIncreasing && A[i] < A[i-1]) return false;
if (!isIncreasing && A[i] > A[i-1]) return false;
}
return true;
}
// 单调栈的思路
public static boolean isMonotonic2(int[] A) {
int n = A.length, start = 1;
while (start < n && A[start] == A[start-1]) { start++; }
if (start == n) return true; // NOTE: critical
boolean isIncreasing = A[start] > A[start-1];
int prev = A[start];
for (int i = start + 1; i < n; i++) {
if (isIncreasing && A[i] < prev || !isIncreasing && A[i] > prev)
return false;
prev = A[i]; // update prev -- this is simpler than monotonic
stack!
}
/*
Stack stack = new Stack<>();
for (int i = start; i < n; i++) {
// 单调栈存储的是数值,不是INDEX
while (stack.size() > 0 && ((isIncreasing && A[i] < stack.peek()
) || (!isIncreasing && A[i] > stack.peek()))) {
if (isIncreasing && A[i] < stack.peek()) return false;
else if (!isIncreasing && A[i] > stack.peek()) return false;
}
stack.push(A[i]);
}
*/
return true;
}

j*g2011-03-07 08:03

43 楼

我家小子天天嚷着烤pizza,才学会说这个，看到烤箱就是烤pizza

s*b2011-03-07 08:03

44 楼

dfs所需要的空间不算？

【在 u***n 的大作中提到】

: 不需要额外空间，linkedlist value就是Treenode

l*o2011-03-07 08:03

45 楼

是啊，打全两个真不容易。哈哈。
昨晚某人工作太耽误时间了，等碎觉就4点了，呜呜呜。大概就是太晚脑子秀逗了，我
都没想起来换个zip试试。。
不过这个胖子过期很快，ra估计也没等到deal就过期了

【在 f*******w 的大作中提到】

: 3点。。。。。
: 好胖子居然只给两个zip，而且还死得那么快，ft
: 而且每个zip还不一样价

s*b2011-03-07 08:03

46 楼

没有贴完。

【在 W***o 的大作中提到】

: 几个月之前写的代码
: public static boolean isMonotonic(int[] A) {
: int n = A.length, start = 1;
: while (start < n && A[start] == A[start-1]) { start++; }
: if (start == n) return true; // NOTE: critical
: boolean isIncreasing = A[start] > A[start-1];
: for (int i = start + 1; i < n; i++) {
: if (isIncreasing && A[i] < A[i-1]) return false;
: if (!isIncreasing && A[i] > A[i-1]) return false;
: }

f*w2011-03-07 08:03

47 楼

早就准备烧cvs的了，碰巧今天看到，碰巧赶在过期前打出来，碰巧过期日14号赶上下
周第一天deal，欧欧，好像运气不错

【在 l*****o 的大作中提到】

:
: 是啊，打全两个真不容易。哈哈。
: 昨晚某人工作太耽误时间了，等碎觉就4点了，呜呜呜。大概就是太晚脑子秀逗了，我
: 都没想起来换个zip试试。。
: 不过这个胖子过期很快，ra估计也没等到deal就过期了

D*72011-03-07 08:03

48 楼

上周salesforce也考过这题，思路就是上面回复的，扫一遍就可以了。

j*32011-03-07 08:03

49 楼

这个牌子极度难吃。。。
买过一次，再也不买了

l*82011-03-07 08:03

50 楼

第二道题是用inorder traversal, 但是有些tricky.
如果只是把元素值打印出来或者放入到list的话，就是个简单的inorder traversal.
但是这里是要把BST变成linked list。在遍历的时候要把tree node的left child变成
null, right child变为 next node of an in-order traversal.
刚开始我也写不出来，后来去看LC 114. Flatten Binary Tree to Linked List.
把那道题的最优解法改动了一下：
public class Solution {
private TreeNode pre = null;
private void flatten(TreeNode root){
if(root==null) return;
flatten(root.right);
root.right=pre;
pre=root;
TreeNode leftchild=root.left;
root.left=null;
flatten(leftchild);
}
}
这里pre记录的是上一个访问的node，也是linked list中的next child. 思路是build
the linked list from the tail. 这里，先访问right child，然后是current root,
最后是left child。
代码不长，但是我自己也想不出来...

l*o2011-03-07 08:03

51 楼

运气是不错，哈哈，这个胖子觉得最划算就是这次cvs了。ra要学着点呀。
digiorno的啤酒rebate要是再来一轮就好了。。买2返8

【在 f*******w 的大作中提到】

: 早就准备烧cvs的了，碰巧今天看到，碰巧赶在过期前打出来，碰巧过期日14号赶上下
: 周第一天deal，欧欧，好像运气不错

m*e2011-03-07 08:03

52 楼

比较头尾数字，可以得出增或减或相等，定义3个bool predictor，循环的时候用指定
predictor即可，楼主以为如何

l*o2011-03-07 08:03

53 楼

家里有个多难吃的pizza都能吃下去的。。
我也觉得难吃。。大概去年冷冻pizza吃多了，什么牌子的冷冻我都觉得难吃。。

【在 j******3 的大作中提到】

: 这个牌子极度难吃。。。
: 买过一次，再也不买了

f*n2011-03-07 08:03

54 楼

第一题报个题号吧，我怎么没搜出来这题。今天开始刷了。首先是sort colors。

f*w2011-03-07 08:03

55 楼

是啊，刚查了查好像没有了，现在是rebate淡季了

【在 l*****o 的大作中提到】

:
: 家里有个多难吃的pizza都能吃下去的。。
: 我也觉得难吃。。大概去年冷冻pizza吃多了，什么牌子的冷冻我都觉得难吃。。

B*O2011-03-07 08:03

56 楼

Omg 现在真是什么人都敢去脸书面试啦

【在 t****b 的大作中提到】

: 这个太长而且引入了变量不够优雅我来抛个砖
: private bool isInc (int[] array) {
: for(int i=0;i: if(array[i]>array[i+1]) return false;
: }
: return true;
: }
: public bool isMono (int[] array) {
: return isInc(array) || isInc(array.reverse());
: }

f*w2011-03-07 08:03

57 楼

pepperoni的厚大饼，cvs，ra最多的那种是不怎么滴
不过那是美国人的最爱应该
supreme的薄底的比较适合中国人口味我觉得

【在 j******3 的大作中提到】

: 这个牌子极度难吃。。。
: 买过一次，再也不买了

X*g2011-03-07 08:03

58 楼

第二题用Morris Inorder遍历就行。
vector inorderTraversal(TreeNode* root)
{
vector res;
TreeNode* curr=root;
while(curr)
{
if(!curr->left)
{
res.push_back(curr->val);
curr=curr->right;
}
else
{
TreeNode* lrMost=curr->left;
while(lrMost->right&&lrMost->right!=curr)
lrMost=lrMost->right;
if(!lrMost->right)
lrMost->right=curr,curr=curr->left;
else //if lrMost->right==curr
{
lrMost->right=NULL;
res.push_back(curr->val);
curr=curr->right;
}
}
}
return res;
}

【在 s****n 的大作中提到】

l*o2011-03-07 08:03

59 楼

马上就要来gc的rebate啦，hoho。。
去年digiorno pizza有好几个rebate呢。不然我可能也没机会吃腻。。。。

【在 f*******w 的大作中提到】

: 是啊，刚查了查好像没有了，现在是rebate淡季了

p*g2011-03-07 08:03

60 楼

这2题简单到爆了，第一题左扫一遍，又扫一遍，
第二题，pre-order, middle -> left -> right

f*w2011-03-07 08:03

61 楼

我看淡rebate
不知道是我这里还是全国都一样
基本所有的啤酒rebate全是买酒返，只碰到coors一家，估计他们很后悔，到现在还没收
到呢。

【在 l*****o 的大作中提到】

:
: 马上就要来gc的rebate啦，hoho。。
: 去年digiorno pizza有好几个rebate呢。不然我可能也没机会吃腻。。。。

u*u2011-03-07 08:03

62 楼

单调题
class Solution {
public:
bool isMono(vector &nums) {
int n = nums.size();
if (n < 2) return true;
bool inc = false, dec = false;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) inc = true;
else if (nums[i] < nums[i - 1]) dec = true;
if (inc && dec) return false;
}
return true;
}
};

l*o2011-03-07 08:03

63 楼

没收
你们从前也不是这样吧。。。。

【在 f*******w 的大作中提到】

: 我看淡rebate
: 不知道是我这里还是全国都一样
: 基本所有的啤酒rebate全是买酒返，只碰到coors一家，估计他们很后悔，到现在还没收
: 到呢。

u*u2011-03-07 08:03

64 楼

狗家题最近能把你们虐哭，烦的要死，各种自己遍的题

f*w2011-03-07 08:03

65 楼

从前bud家都是买菜肉直接返，从没要求买酒过

【在 l*****o 的大作中提到】

:
: 没收
: 你们从前也不是这样吧。。。。

t*b2011-03-07 08:03

66 楼

太长要是狗家的题一定问你怎么能不考虑具体增减

【在 u**u 的大作中提到】

: 单调题
: class Solution {
: public:
: bool isMono(vector &nums) {
: int n = nums.size();
: if (n < 2) return true;
: bool inc = false, dec = false;
: for (int i = 1; i < n; i++) {
: if (nums[i] > nums[i - 1]) inc = true;
: else if (nums[i] < nums[i - 1]) dec = true;

l*o2011-03-07 08:03

67 楼

太奇怪了。一般这些都是和当地法律有关系。。
法律没有改变，这些也不应该。。
那你就发现点新乐子吧。。。。

【在 f*******w 的大作中提到】

: 从前bud家都是买菜肉直接返，从没要求买酒过

s*b2011-03-07 08:03

68 楼

第二题：
List* flattenToLL(Node* root) {
List *list1 = (root->left) ? flattenToLL(root->left) : NULL;
List *list2 = (root->right) ? flattenToLL(root->right) : NULL;
root->left=NULL
root->right=list2
// The "middle" list3 cannot be NULL; append list2 to list3
if (!list1) return root; // Nothing to prepend
List *last = list1;
while (last->right) last=last->right; // Go to the end of list1
last->right = root; // Append list3+list2 to the end of list1
return list1;
}

f*y2011-03-07 08:03

69 楼

这个还有不同口味吗？给介绍下吧

M*62011-03-07 08:03

70 楼

我也这么想的。这题太直接了，不考任何数据结构和算法。

【在 W***o 的大作中提到】

f*w2011-03-07 08:03

71 楼

有啊，pizza怎么可能只出一个口味呢对吧
但是cvs或者ra通常最多两个口味，一个pepperoni 一个supreme
supreme用国内话说就是**至尊匹萨啊，就是放了很多杂碎蔬菜和小肉块
我比较喜欢这个。
还有厚饼子和薄饼子，厚饼子分量大，不过就好像在啃馒头，薄饼子轻，相对显得出上
面料的味道。厚饼子国内叫铁盘匹萨，薄的叫薄脆，好像

【在 f*******y 的大作中提到】

: 这个还有不同口味吗？给介绍下吧

p*k2011-03-07 08:03

72 楼

你这个i++就优雅了？

【在 t****b 的大作中提到】

L*e2011-03-07 08:03

73 楼

没有胖子就省事了，呵呵

s*g2011-03-07 08:03

74 楼

recursion的空间当然要算
所以要用morris traversal
其实不算特简单

【在 s******b 的大作中提到】

: dfs所需要的空间不算？

f*y2011-03-07 08:03

75 楼

谢谢啊，好详细

【在 f*******w 的大作中提到】

: 有啊，pizza怎么可能只出一个口味呢对吧
: 但是cvs或者ra通常最多两个口味，一个pepperoni 一个supreme
: supreme用国内话说就是**至尊匹萨啊，就是放了很多杂碎蔬菜和小肉块
: 我比较喜欢这个。
: 还有厚饼子和薄饼子，厚饼子分量大，不过就好像在啃馒头，薄饼子轻，相对显得出上
: 面料的味道。厚饼子国内叫铁盘匹萨，薄的叫薄脆，好像

s*g2011-03-07 08:03

76 楼

morris traversal不是谁都会的
直接dfs有额外空间（recursion stack）

【在 p*********g 的大作中提到】

: 这2题简单到爆了，第一题左扫一遍，又扫一遍，
: 第二题，pre-order, middle -> left -> right

a*92011-03-07 08:03

77 楼

thanks

s*g2011-03-07 08:03

78 楼

啥叫最近
难道不一直都这样吗

【在 u**u 的大作中提到】

: 狗家题最近能把你们虐哭，烦的要死，各种自己遍的题

y*32011-03-07 08:03

79 楼

public class Monotonic {
enum type {
increasing, decreasing, undefined
}
public boolean isMonotonic(int[] input) {
if (input == null || input.length <= 1)
return true;
type mono_type = type.undefined;
for (int i = 0; i < input.length - 1; i++) {
if (input[i] > input[i+1]) {
if (mono_type == type.increasing) return false;
mono_type = type.decreasing;
}
else if (input[i] < input[i+1]) {
if (mono_type == type.decreasing) return false;
mono_type = type.increasing;
}
}
return true;
}
}

【在 s****n 的大作中提到】