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

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

当时蒙了,现场写出了不用最大整数的解法,还是被黑了..当时应该据理力争?

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做。

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就可以了

finerve 发表于 2016-10-23 16:31
所以不能用吗? 就是看leetcode很多人随便就用了..

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

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

求什么的最小值？数组么？你的意思是面试官问你如果数组本身中含有INT_MAX该怎么办？

stellari 发表于 2016-10-23 13:24
求什么的最小值？数组么？你的意思是面试官问你如果数组本身中含有INT_MAX该怎么办？

是的.其实是tree,不过没差了..

finerve 发表于 2016-10-23 13:30
是的.其实是tree,不过没差了..

为何不用root的值做初始值

finerve 发表于 2016-10-23 13:30
是的.其实是tree,不过没差了..

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

stellari 发表于 2016-10-23 14:07
不管是什么容器，用能访问到的第一个数字做初始值就好了吧，比如数组是A[0]，树是root->val. 还是说面试 ...

所以不能用吗? 就是看leetcode很多人随便就用了..

本人刷题经验是。。如果你这么做了，但遇到一个corner case导致这个初始的最大值直接被当结果返回，就错了。。。

freeaccount 发表于 2016-10-23 20:23
本人刷题经验是。。如果你这么做了，但遇到一个corner case导致这个初始的最大值直接被当结果返回，就错了 ...

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

freeaccount 发表于 2016-10-23 20:23
本人刷题经验是。。如果你这么做了，但遇到一个corner case导致这个初始的最大值直接被当结果返回，就错了 ...

预先判断input为空能不能排除掉你说的corner case? 求指正