阅后即焚的新鲜店面

前天面的，现在还没消息。发面经攒人品求过呀。店面第一轮，是非常友好的国人小哥，非常耐心的给了很多提示。。如果小哥你也看到这贴了，求给我个加面吧。。非常想去的公司啊。。
第一提，给你你个数组，要你返回数组的最小值的平方是否小于最大值。题目很简单，需要注意的就是最小

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这上面是可以run的。。哎，当时不知道啊。。提醒一下大家。我就奇怪当时小哥怎么说，我们写几个test case来跑一下看看。。然后我用人工给他run了几个

第一问不说了;
第二问从尾巴往前;
第三问第一反应bottom up-DP, 想了下...线段树查最小值啊?

jy_121 发表于 2016-5-19 05:26
请问最后一问的DP方程应该怎样写呢？谢谢

C++代码：

1. 
   
2. /*
   
3. * Given an array. Check whether 2 power the minimum of the array is larger then the maximum of the array.
   
4. * follow up 1: (minTakesFront)     If you can take out the front elements in the array, how many steps it takes to make the rest of the array satisfying the above condition?
   
5. * follow up 2: (minTakesBothEnds)  what if you can take out elements from both ends of the arrary? Then what is the minimum steps to find a subarray that satisfying the above condition?
   
6. */
   
7. 
   
8. #include <iostream>
   
9. #include <string>
   
10. #include <vector>
    
11. #include <algorithm>
    
12. #include <limits>
    
13. 
    
14. using namespace std;
    
15. 
    
16. bool checkPow(const int& minValue, const int& maxValue) {
    
17.     errno = 0;
    
18.     double pow2 = std::pow( minValue, 2 );
    
19.     if ( errno == 0 ) {
    
20.         //  std::pow succeeded (without overflow)
    
21.         if (pow2 > maxValue) {
    
22.             return true;
    
23.         }
    
24.     } else {
    
25.         //  some error (probably overflow) with std::pow.
    
26.         return false;
    
27.     }   
    
28.     return false;
    
29. }
    
30. 
    
31. int minTakesFront(const vector<int>& nums) {
    
32.         int minValue = numeric_limits<int>::max();
    
33.         int maxValue = numeric_limits<int>::min();
    
34.         int s = static_cast<int>(nums.size());
    
35.         int i = s - 1;
    
36.         for (; i >= 0 ; --i) {   
    
37.                 minValue = min(nums[i], minValue);
    
38.                 maxValue = max(nums[i], maxValue);
    
39.                 if (!checkPow(minValue, maxValue)) {
    
40.                         break;
    
41.                 }
    
42.         }
    
43.         if (i == s - 1) {
    
44.                 return -1;
    
45.         }
    
46.         return i + 1;
    
47. }
    
48. 
    
49. // return minimum steps to make a subarray inside the passed in array such that 2 power the minimum is larger the maximum
    
50. // or -1 if there is no such subarray
    
51. int minTakesBothEnds(const vector<int>& nums) {
    
52.         int s = static_cast<int>(nums.size());
    
53.        
    
54.         if (s == 0) {
    
55.             return -1;
    
56.         }
    
57.        
    
58.         vector<vector<int>> f(s, vector<int>(s, 0));
    
59.         for (int i = 0; i < s; ++i) {
    
60.             if (checkPow(nums[i], nums[i])) {
    
61.                 f[i][i] = 0;
    
62.             } else {
    
63.                 f[i][i] = 1;
    
64.             }
    
65.         }
    
66.        
    
67.         for (int i = s - 1; i >= 0; --i) {
    
68.                 int minValue = nums[i];
    
69.                 int maxValue = nums[i];
    
70.                 for (int j = i + 1; j < s; ++j) {
    
71.                         minValue = min(nums[j], minValue);
    
72.                         maxValue = max(nums[j], maxValue);
    
73.                         if (checkPow(minValue, maxValue)) {
    
74.                                 f[i][j] = 0;
    
75.                         } else {
    
76.                                 f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1;
    
77.                         }
    
78.                 }
    
79.         }
    
80.        
    
81.         //if steps equal to size of the array, all elements have been taken out
    
82.         if (f[0][s - 1] == s) {
    
83.             return -1;
    
84.         }
    
85.        
    
86.         return f[0][s - 1];
    
87. }
    
88. 
    
89. int main()
    
90. {
    
91.   vector<int> test1 = {5};
    
92.   vector<int> test2 = {1};
    
93.   vector<int> test3 = {5, 1, 3};
    
94.   vector<int> test4 = {1, 1, 1};
    
95.   vector<int> test5 = {5, 3, 1};
    
96.   vector<int> test6 = {2, 5, 3, 1};
    
97.   vector<int> test7 = {-2};
    
98.   vector<int> test8 = {1, 5, 3};
    
99.   
    
100.   cout << "test1 front result : " << minTakesFront(test1) << endl;
     
101.   cout << "test2 front result : " << minTakesFront(test2) << endl;
     
102.   cout << "test3 front result : " << minTakesFront(test3) << endl;
     
103.   cout << "test4 front result : " << minTakesFront(test4) << endl;
     
104.   cout << "test5 front result : " << minTakesFront(test5) << endl;
     
105.   cout << "test6 front result : " << minTakesFront(test6) << endl;
     
106.   cout << "test7 front result : " << minTakesFront(test7) << endl;
     
107.   cout << "test8 front result : " << minTakesFront(test8) << endl;
     
108.   cout << endl;
     
109.   cout << "test1 both result : " << minTakesBothEnds(test1) << endl;
     
110.   cout << "test2 both result : " << minTakesBothEnds(test2) << endl;
     
111.   cout << "test3 both result : " << minTakesBothEnds(test3) << endl;
     
112.   cout << "test4 both result : " << minTakesBothEnds(test4) << endl;
     
113.   cout << "test5 both result : " << minTakesBothEnds(test5) << endl;
     
114.   cout << "test6 both result : " << minTakesBothEnds(test6) << endl;
     
115.   cout << "test7 both result : " << minTakesBothEnds(test7) << endl;
     
116.   cout << "test8 both result : " << minTakesBothEnds(test8) << endl;
     
117. }
     

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

问下楼主，第一个佛罗阿噗是从数组尾巴开始往前扫，然后每次记录最大值和最小值，然后求是否满足吗？这样应该是O(n)，然后第二个的话，目前只能想到n方的方法，感觉应该有更好的办法- -

GavinM 发表于 2016-5-6 01:24
问下楼主，第一个佛罗阿噗是从数组尾巴开始往前扫，然后每次记录最大值和最小值，然后求是否满足吗？这样应 ...

对，由尾向前扫。。第三问我说的是用dp，dp(i, j)表示i到j的subarray是否满足，然后他接着问是否可以省空间。。。

第二问，是不是题目不对。删除一个元素后，只有三中情况
1. 没有删到max min，关系不变
2. 删了min，第二min的平方更不可能小于max
3. 删了max，min平方更不可能小于第二max

ok123 发表于 2016-5-6 04:45
第二问，是不是题目不对。删除一个元素后，只有三中情况
1. 没有删到max min，关系不变
2. 删了min，第二 ...

元素可以为正，可以为负。

ok123 发表于 2016-5-6 04:45
第二问，是不是题目不对。删除一个元素后，只有三中情况
1. 没有删到max min，关系不变
2. 删了min，第二 ...

元素可以为正，可以为负。

给的数组是sorted的吗？

请问第二问： 从前往后删和从后往前删的区别是？
我感觉如果不是sorted的话，没有区别啊，因为没法知道max和min会在哪。。。请大家指导

wtcupup 发表于 2016-5-18 18:50
给的数组是sorted的吗？

不是。。