脸/非死不可 电2020面筋

国人小哥，全程黑脸，感觉完全没兴趣面试，只是完成任务而已

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

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

舞伞


目测要跪

其实 我觉得1313 这个 不算是corner case 呀 。

其实这道题的核心思想是，怎么样可以变小，但是变得没那么小。所以这就决定了你做交换的时候保证1. 尽量对高位的数字不要有影响 2. 对有影响的低位数字消减的最小。


比如 [1,9,4,6,7]，我们的思路应该是从后往前搜索，比如我在 6 这个位置，我一定是要向后搜索，找一个比6小，但是在比6小的情况下最大的那个，相当于 矮子里面挑高个，这样才可以保证

1. 换了 6之后对前面高位的数字没有影响
2. 交换之后的低位数字是我能凑到的最大的数字

满足这两点就可以保证得到的数组组成的数字一定是比原来的小，但是是小的里面最大的那个。当然在这个6 的例子里面是没有找到合适的交换数字。
但是换成9的话就不一样了，明显在后面有4，6，7比9小，但是明显7最大，那理所应当就是9和7交换变成 [1,7,4,6,9]

基于以上两点一个O(N^2) 的解法是

1. public int[] prevPermOpt1(int[] A) {
   
2.         if (A.length == 1 || A.length == 0) {
   
3.             return A;
   
4.         } else {            //从后往前搜索哦
   
5.             for (int i = A.length-1; i >= 0; i--) {
   
6.                // 比当前小，但是是小的里面最大的那个value
   
7.                 int tempMax = -1;
   
8.                //value 的index，方便我之后交换
   
9.                 int index = -1;
   
10.                 for (int j = A.length-1; j > i; j--) {
    
11.                     //第二重循环，找i之后的数字，如果比i指向的小，而且比当前以及得到的最大值还要大，这个就是合适的candidate
    
12.                     if (A[j] < A[i] && A[j] >= tempMax) {
    
13.                         tempMax = A[j];
    
14.                         index =  j;
    
15.                     }
    
16.                 }[/i]
    
17. [i]                 //只要找到了一个合适的，这个肯定是最终答案，
    
18.                 if (tempMax != -1) {
    
19.                     swap(i, index ,  A);
    
20.                     return A;
    
21.                 }
    
22.             }
    
23.             return A;
    
24.         }
    
25.     }
    
26. 
    
27.     private void swap(int i, int j, int[] A) {
    
28.         int temp = A[i];
    
29.         A[i] = A[j];
    
30.         A[j] = temp;
    
31.     }

复制代码

所以 3113 也是同样思路。 你在最后一个3的时候，后面没有数字可以交换 ，忽略它。两个1后面都没有比他小的，忽略。到第一个3的时候，你从后找，找到一个1比他小，而且1是能找到比第一个3小的最大值了。交换就得出 1313

这个是AC答案而且速度是100%。我暂时没想到O(N)的解法，不过关键在于怎么快速找到比当前index的数字小，但是是小的里面最大的这样一个数据结构。[/i][/i][/i]

xxxxqia 发表于 2020-10-26 08:41
感谢楼主，第二题只做过类似的next permutation. 以为一样的，结果有 [3，1，1，3] 这种corner case，关键 ...

是啊，这个题目真的，作为面试题真会把人烦死，而且当时小哥就说了句"you know what is prev permutation right?"

我觉得这个题目的难点在于理解这个规律，光是这个就要花很多时间，更别说还要在这么短的时间内写出来了，目测是跪定了

RainbowRidge 发表于 2020-10-24 13:31
楼主，第一题感觉BST和BT对这题没啥区别吧？

有区别，如果是BST的话，问题就转换成为了，某个node，最左边儿子的depth+最右边儿子的depth

如果只是一般的二叉树的话，就只能DFS了，差别还是很大的

真会出第二题这种垃圾题？我服了，遇到必死

儒雅随和的小川 发表于 2020-10-23 17:07:22
真会出第二题这种垃圾题？我服了，遇到必死

其实反而第二题我做出来了、但这个题目真的是很烦人

anastasia22 发表于 2020-10-24 09:36
其实反而第二题我做出来了、但这个题目真的是很烦人

这道题3113正确是1313我是真想了半小时，遇到了我也不知道怎么解释，下周面试估计纯看命

儒雅随和的小川 发表于 2020-10-24 10:03
这道题3113正确是1313我是真想了半小时，遇到了我也不知道怎么解释，下周面试估计纯看命

的确，这个题目我觉得就是坑人的，一共45分钟，两个medium题目。估计要跪
兄弟加油

出这个题的人应该自认是高智商...

楼主，第一题感觉BST和BT对这题没啥区别吧？

hgon23 发表于 2020-10-24 12:57
出这个题的人应该自认是高智商...

而且还是同胞~认了

感谢楼主，第二题只做过类似的next permutation. 以为一样的，结果有 [3，1，1，3] 这种corner case，关键我的答案错了这个test还跑过了。。。真是奇葩