给定一个数组,为每个元素找到数组中的下一个较小元素,而不改变元素的原始顺序.
例如,假设给定的数组是4,2,1,5,3.
结果数组为2,1,-1,3,-1.
我在接受采访时被问到这个问题,但我想不出一个比普通的O(n ^ 2)解决方案更好的解决方案.我能想到的任何方法,即制作二元搜索树,或对数组进行排序,都会扭曲元素的原始顺序,从而导致错误的结果.
任何帮助将受到高度赞赏.
这是一个非常有趣的采访问题:
给出一个单词,将最少数量的字母附加到它上面以将其转换为回文结构.
例如,如果"hello"是给定的字符串,则结果应为"hellolleh".如果给出"coco",结果应该是"cococ".
我能想到的一种方法是将字符串的反向追加到原始字符串的末尾,然后尝试从末尾消除额外的字符.但是,我无法弄清楚如何有效地做到这一点.有没有人有任何想法？
我在一次采访中被问到了这个问题,它让我付出了一份工作:P面试官问道,你将获得一棵树的根,你必须将根返回复制的树,但副本应该是以迭代的方式.我在这里粘贴我的代码,我在那里写了相同的,它工作正常.我最初使用两个堆栈来做这个,面试官说他不喜欢,然后我用以下方式做到了.面试官对我使用另一个包含指向原始和最终树的指针的结构有点不满(参考代码).
我想知道是否还有其他更好的方法吗？
struct node
{
int data;
struct node * left;
struct node * right;
};
struct copynode
{
node * original;
node * final;
};
node * copy(node *root)
{
stack <copynode*> s;
copynode * temp=(copynode*)malloc(sizeof(copynode));
temp->original=root;
temp->final=(node *)malloc(sizeof(node));
s.push(temp);
while(s.empty()==false)
{
copynode * i;
i=s.top();
s.pop();
i->final=i->original;
if(i->original->left)
{
copynode *left=(copynode*)malloc(sizeof(copynode));
left->original=i->original->left;
left->final=(node *)malloc(sizeof(node));
s.push(left);
}
if(i->original->right)
{
copynode *right=(copynode*)malloc(sizeof(copynode));
right->original=i->original->right;
right->final=(node *)malloc(sizeof(node));
s.push(right);
}
}
return temp->final;
}
我之前发过一个问题,给定一个数组,现在找出每个元素的下一个较小的元素 ,我试图知道,如果有任何方法可以找出"给定一个数组,对于每个元素,找出总数比它更小的元素,它出现在它的右边"例如,数组[4 2 1 5 3]应该产生[3 1 0 1 0] ??
[编辑]我已经找到了解决方案,请看一下,如果有任何错误,请告诉我.
1制作一个平衡的BST插入元素,从右到左穿过阵列
2 BST的制作方式使每个元素都保持以该元素为根的树的大小
3现在,当您搜索插入任何元素的正确位置时,如果向右移动,请考虑根据左侧兄弟+ 1(对于父级)生成的子树的总大小,因为计数是在插入时计算的一个元素,并且我们从右向左移动,我们得到的元素的精确数量小于它后面出现的给定元素.
最近我遇到了这个采访问题:
在数组中给出n个实数.如果数组中的数字超过n/10次,则数组中的数字称为十进制显性.给出O(n)时间算法以确定给定数组是否具有十进制显性.
现在我可以想出几种方法来解决这个问题,以及这个问题的任何概括(即找到在数组中出现K次的任何数字)
一种可能是在第1遍中创建哈希表,然后计算第2遍中的出现次数,即O(n),但也使用O(n)空间,
有一种方法可以使用9个桶
但是,我们有什么方法可以在一个恒定的空间里做到这一点？有什么建议？？
[编辑]我还没有检查过9桶解决方案,读者可能想通过下面的nm评论
这是我在在线门户网站上看到的Facebook面试问题.
给定集合S,找到其总和<= k的所有最大子集.例如,如果S = {1,2,3,4,5}且k = 7输出是:{1,2,3} {1,2,4} {1,5} {2,5} {3 ,4}
提示:
任何想法如何解决？