一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1078|回复: 20
收起左侧

[算法题] 面试的时候求最小值我用了初始最大整数,居然...

[复制链接] |试试Instant~ |关注本帖
finerve 发表于 2016-10-23 12:54:25 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
阿三面试官居然问,如果输入的值是最大整数怎么办...
(我觉得是凉拌吧,反正变量不会改变)

当时蒙了,现场写出了不用最大整数的解法,还是被黑了..当时应该据理力争?
stellari 发表于 2016-10-23 13:24:01 | 显示全部楼层
求什么的最小值?数组么?你的意思是面试官问你如果数组本身中含有INT_MAX该怎么办?
回复 支持 反对

使用道具 举报

 楼主| finerve 发表于 2016-10-23 13:30:31 | 显示全部楼层
stellari 发表于 2016-10-23 13:24
求什么的最小值?数组么?你的意思是面试官问你如果数组本身中含有INT_MAX该怎么办?

是的.其实是tree,不过没差了..
回复 支持 反对

使用道具 举报

huai10 发表于 2016-10-23 13:59:05 | 显示全部楼层
finerve 发表于 2016-10-23 13:30
是的.其实是tree,不过没差了..

为何不用root的值做初始值
回复 支持 反对

使用道具 举报

stellari 发表于 2016-10-23 14:07:46 | 显示全部楼层
finerve 发表于 2016-10-23 13:30
是的.其实是tree,不过没差了..

不管是什么容器,用能访问到的第一个数字做初始值就好了吧,比如数组是A[0],树是root->val. 还是说面试官有什么其他的限制条件?
回复 支持 反对

使用道具 举报

 楼主| finerve 发表于 2016-10-23 16:31:29 | 显示全部楼层
stellari 发表于 2016-10-23 14:07
不管是什么容器,用能访问到的第一个数字做初始值就好了吧,比如数组是A[0],树是root->val. 还是说面试 ...

所以不能用吗? 就是看leetcode很多人随便就用了..
回复 支持 反对

使用道具 举报

freeaccount 发表于 2016-10-23 20:23:30 | 显示全部楼层
本人刷题经验是。。如果你这么做了,但遇到一个corner case导致这个初始的最大值直接被当结果返回,就错了。。。
回复 支持 反对

使用道具 举报

stellari 发表于 2016-10-24 02:36:19 | 显示全部楼层
finerve 发表于 2016-10-23 16:31
所以不能用吗? 就是看leetcode很多人随便就用了..

把minVal初始化成INT_MAX不是不可以,但是关键是你要清楚这可能会造成什么影响。如果仅是单纯地求容器内的“最小值”的话,这样没有问题:minVal初始化成容器的第一个数都可以, 那么初始化成肯定>=容器第一个数的INT_MAX更不会有问题了(当然要做好容器如果是空情况下的检查)。就你的描述而言,面试官或许就是期待一个“输入值即使有最大整数也不影响结果”的答案。

不过说起来单纯求tree的最小值有太过简单的嫌疑,所以面试官或许还安排了什么不为人所注意的限制也说不定。仅供参考。
回复 支持 反对

使用道具 举报

stellari 发表于 2016-10-24 02:45:37 | 显示全部楼层
本帖最后由 stellari 于 2016-10-24 02:55 编辑
freeaccount 发表于 2016-10-23 20:23
本人刷题经验是。。如果你这么做了,但遇到一个corner case导致这个初始的最大值直接被当结果返回,就错了 ...

只要minVal初始化成一个合理的值,总是可以写出返回结果正确的代码的。如果是minVal初始化成INT_MAX代码就不能正常工作,那么这就是代码本身的整体逻辑有问题。这在面试时会被扣掉很多分的。
回复 支持 反对

使用道具 举报

 楼主| finerve 发表于 2016-10-24 04:19:34 | 显示全部楼层
freeaccount 发表于 2016-10-23 20:23
本人刷题经验是。。如果你这么做了,但遇到一个corner case导致这个初始的最大值直接被当结果返回,就错了 ...

预先判断input为空能不能排除掉你说的corner case? 求指正
回复 支持 反对

使用道具 举报

 楼主| finerve 发表于 2016-10-24 04:25:37 | 显示全部楼层
stellari 发表于 2016-10-24 02:36
把minVal初始化成INT_MAX不是不可以,但是关键是你要清楚这可能会造成什么影响。如果仅是单纯地求容器内 ...

多谢解答,也不是单纯求了,就是比如validate bst的初始值之类的.

好像第一个node的INT_MAX和本身的INT_MAX会造成False,但是如果只有一个Node应该是True.

所以就应该完全避免使用INT_MAX了..?
回复 支持 反对

使用道具 举报

yxyxyx 发表于 2016-10-24 05:13:55 | 显示全部楼层
finerve 发表于 2016-10-23 16:25
多谢解答,也不是单纯求了,就是比如validate bst的初始值之类的.

好像第一个node的INT_MAX和本身的INT_ ...

这类问题的处理方式大概有两种:
1.1. 把input为极值的情况单独处理。比如在代码里专门写如果输入时极大/小值该如何如何。
1.2. 如你所说,先判断下input为空在某些时候也可以。

2. 另外一个比较cheese的做法就是把input从int转成long,然后用LONG_MAX作为极大值去比。这样的好处是如果面试官认为可以的话实现起来最简单,坏处是面试官也可以顺着问:
“那如果input本身就是long怎么办?”
“那就用long long"
“那如果input本身就是long long怎么办”
“...DOUBLE_MAX?????”

所以看情况。其实根据以前的经验不少情况下方法2就可以了
回复 支持 反对

使用道具 举报

yxyxyx 发表于 2016-10-24 05:31:58 | 显示全部楼层
本帖最后由 yxyxyx 于 2016-10-23 17:33 编辑
finerve 发表于 2016-10-23 16:25
多谢解答,也不是单纯求了,就是比如validate bst的初始值之类的.

好像第一个node的INT_MAX和本身的INT_ ...

恩就validate bst这道题来说的话:

比如我想用inorder traversal, 比上一个遍历过的值和现在node的值,那么有多个做法:

1. 把“上一个遍历过的值”设成LONG_MIN. 这样的做法代码如下:
  1. bool helper(TreeNode *root, long &prev_val) {
  2.     if (root == NULL) return true;
  3.     bool left_valid = helper(root->left, prev_val);
  4.     if (!left_valid) return false;
  5.     if (prev_val >= root->val) return false;
  6.     prev_val = root->val;
  7.     return helper(root->right, prev_val);
  8. }
  9.    
  10. bool isValidBST(TreeNode* root) {
  11.     long prev_val = LONG_MIN;
  12.     return helper(root, prev_val);
复制代码
2. 当然“上一个遍历过的值”是可以初始化成INT_MIN的,但是你需要代码里专门处理下如果这个数里面存在INT_MIN怎么办(比如最左节点是INT_MIN)。一个可行的处理方法就是看你是不是已经遍历过了最左节点,因为一个正确的BST里,INT_MIN只可能存在于最左节点。这样的代码如下:
  1. bool helper(TreeNode *root, int &prev_num, bool &visited_leftmost) {
  2.     if (root == NULL) return true;
  3.     bool left_valid = helper(root->left, prev_num, visited_leftmost);
  4.     if (!left_valid) return false;
  5.         
  6.     if (root->val == INT_MIN) {
  7.         if (visited_leftmost) return false;
  8.         else visited_leftmost = true;
  9.     } else if (root->val <= prev_num) return false;
  10.     visited_leftmost = true;
  11.     prev_num = root->val;
  12.     return helper(root->right, prev_num, visited_leftmost);
  13. }
  14.    
  15. bool isValidBST(TreeNode* root) {
  16.     int prev_num = INT_MIN;
  17.     bool visited_leftmost = false;
  18.     return helper(root, prev_num, visited_leftmost);
  19. }
复制代码
当然你也可以采取另外一种方式validate bst,那就是看当前节点的值是不是比左子树的最大值大且比右子树的最小值小。这类做法也有写法可以把你的最大值最小值用INT_MIN和INT_MAX初始化而不用担心树里有INT_MIN和INT_MAX的node。提示一下:用postorder traversal做。


评分

1

查看全部评分

回复 支持 反对

使用道具 举报

xietao0221 发表于 2016-10-24 05:57:49 | 显示全部楼层
用Integer类型,设置为null就好了,判断的时候多加一个if
回复 支持 反对

使用道具 举报

 楼主| finerve 发表于 2016-10-24 07:19:45 | 显示全部楼层
yxyxyx 发表于 2016-10-24 05:31
恩就validate bst这道题来说的话:

比如我想用inorder traversal, 比上一个遍历过的值和现在node的值 ...

大神,如果想用迭代+in-order的方法判断valid bst,"上一个node"变量不能设初始值为root,如果也不能设初始值为最小int,只能初始为null 再加判断了是吗?
回复 支持 反对

使用道具 举报

 楼主| finerve 发表于 2016-10-24 07:21:10 | 显示全部楼层
xietao0221 发表于 2016-10-24 05:57
用Integer类型,设置为null就好了,判断的时候多加一个if

这方法好,虽然很朴素,不过感觉各种情况通吃啊~
回复 支持 反对

使用道具 举报

ykwwind 发表于 2016-10-24 07:59:10 | 显示全部楼层
finerve 发表于 2016-10-24 07:21
这方法好,虽然很朴素,不过感觉各种情况通吃啊~

你这个不是技术问题...

阿三一旦发问,不要怂,直接干. 不服就举例,摁不死他就是被摁死. 千万不要被阿三带着走.....人家未必就是想黑你,但是阿三就这风格,就是喜欢突然岔开去...搞着搞着最后面的人崩了.
回复 支持 反对

使用道具 举报

yxyxyx 发表于 2016-10-24 09:24:24 | 显示全部楼层
finerve 发表于 2016-10-23 19:19
大神,如果想用迭代+in-order的方法判断valid bst,"上一个node"变量不能设初始值为root,如果也不能设初始 ...

恩听起来你用的是Java?如果java里有NULL定义的话那自然最好了,c++里的int不幸不能设定成NULL,所以没有这个选项
回复 支持 反对

使用道具 举报

xietao0221 发表于 2016-10-24 09:32:21 | 显示全部楼层
yxyxyx 发表于 2016-10-24 09:24
恩听起来你用的是Java?如果java里有NULL定义的话那自然最好了,c++里的int不幸不能设定成NULL,所以没有 ...

其实如果没有null也没关系,可以另外设置一个bool变量作为是否第一个值已经赋值,其实是一个道理,只是代码会多一些东西。
回复 支持 反对

使用道具 举报

freeaccount 发表于 2016-10-24 10:46:56 | 显示全部楼层
finerve 发表于 2016-10-23 15:19
预先判断input为空能不能排除掉你说的corner case? 求指正

我忘了我的case了。应该是可以,总之就是要对corner case做特殊处理,input为空当然是corner case的一种。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 01:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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