Facebook新鲜面经！！！

lyburke 发表于 2016-3-2 13:04
LZ考的第一题和我面的一样。。。可以写的更简洁一些

嗯嗯，可以指点一下吗？谢谢

spwahaha 发表于 2016-3-2 10:03
这道题为什么不能用DFS？

可以用啊。。。dfs。。

lyburke 发表于 2016-3-2 13:04
LZ考的第一题和我面的一样。。。可以写的更简洁一些

大神快指导。。

spwahaha 发表于 2016-3-2 10:03
这道题为什么不能用DFS？

因为题目要求是同一列中顺序由level的高低决定，如果dfs则不能保证这一顺序，只能保证左子树排在右子树前边。。。如果没有这个要求，dfs也行。

zhenjieruan 发表于 2016-3-2 13:16
嗯嗯，可以指点一下吗？谢谢

用两个指针，从左右两边扫，类似merge sort，结果从后往前加，O(n)一遍就可以解决啦

xiaozhuxiaozhu 发表于 2016-3-2 13:18
可以用啊。。。dfs。。

我也举得可以用，而且应该比BFS好写吧，
但是楼主和面试官不是说BFS有问题还是什么的

第一题 扫一遍可以吗？

1. public class Solution {
   
2.         public int[] square(int[] nums) {
   
3.                 if (nums == null || nums.length == 0) return new int[0];
   
4.                 int left = 0, right = nums.length - 1, index = right;
   
5.                 int[] res = new int[nums.length];
   
6.                 while (left <= right) {
   
7.                         if (Math.abs(nums[left]) >= Math.abs(nums[right])) {
   
8.                                 nums[index--] = nums[left] * nums[left];
   
9.                                 left++;
   
10.                         }else if (Math.abs(nums[left]) < Math.abs(nums[right])) {
    
11.                                 nums[index--] = nums[right] * nums[right];
    
12.                                 right--;
    
13.                         }
    
14.                 }
    
15.                 return res;
    
16.         }
    
17. }

复制代码

xiaozhuxiaozhu 发表于 2016-3-2 13:18
大神快指导。。

不是大神= =就是先声明一个和输入等长的结果array，然后用左右指针比较对应值的绝对值大小，绝对值较大的将其平方放入结果array末尾，就这样一步步从后往前放结果。。。这样不用考虑全正，全负还是有正有负

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

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

lyburke 发表于 2016-3-3 05:11
不是大神= =就是先声明一个和输入等长的结果array，然后用左右指针比较对应值的绝对值大小，绝对值较大的 ...

大神，看不懂汉语，能写格code么。 ＋大米 10