脸家onsite

Stack<Integer> st=new Stack();
List<Integer> res=new ArrayList();
for(int i=0;i<A.length;i++){
   if(st.isEmpty()||st.peek()>A[i]) {st.push(A[i]); continue;}
   else{
      while(!st.isEmpyt()&&A[i]>st.peek())
       res.add(st.pop());
     st.push(A[i]);
  }
   while(!st.isEmpyt()) res.add(st.pop());

}

say543 发表于 2017-6-6 14:28
先序遍历结果 有包含null吗 如果没有 所以结果可能不unique?

这种题目对于BST的假定一般都是no duplicate node values. 否则的话任何traversal结果都没有区别。主要是想考察binary search.

leonxxx 发表于 2017-6-7 04:57
Stack st=new Stack();
List res=new ArrayList();
for(int i=0;iA) {st.push(A); continue;}

最后的“while(!st.isEmpyt()) res.add(st.pop());”是不是应该在for loop之外的？ 因为最后处理还在stack中的单调递减数值

第一个问题应该是sliding window的变形题吧？任何相邻字母都当成窗口的左右指针，如果他们刚好相等，就把中间字符做替换，然后移动到下一个窗口

mdf 发表于 2017-8-11 22:19
第一个问题应该是sliding window的变形题吧？任何相邻字母都当成窗口的左右指针，如果他们刚好相等，就把中 ...

看错题目了

是不是每个字符建一个interval，保留最左和最右
比如字符A出现在2，5，6的位置，那么interval a[2,6]
字符b出现在4，7，8的位置，那么interval b[4,7]
。。。。。。

然后合并所有的interval

根据合并的interval改+

mdf 发表于 2017-8-11 22:47
看错题目了

是不是每个字符建一个interval，保留最左和最右

可以先把所有的interval先建立出来，然后 merge

wwendywang 发表于 2017-6-6 12:48
建BST
108. Convert Sorted Array to Binary Search Tree

108假设的是balanced BST这题不一定是balanced.

kevin_06 发表于 2017-6-6 10:29
--a-d*-d-a-b 变成 --a-++++-a-b

这个题目需要recursive call么？比如先把两个d之间的变成+，然后继续处理可以把两个a之间的字符都变成+

这样可以用一个stack来处理？不知道这么理解对否？

waterbucket 发表于 2017-6-6 11:28
不是，至少recursive的二分比nlogn要好

请问recursive的二分的时间复杂度是(log(n))^2吗  有点想不清楚 = = 感谢

张欣 发表于 2017-9-24 07:13
请问recursive的二分的时间复杂度是(log(n))^2吗  有点想不清楚 = = 感谢

复杂度是O(n)吧