j********2
发帖数: 82 | 1 1. Print all paths of a binary tree
How to do it iteratively? 用一个stack实现preorder来做？
2. Given an array of integers, find any 3 numbers in array such that they
sum to zero. eg:
[1, 2, -3, 4, 0]
1) 1 , 2, -3
2) 0, 0, 0
这个是不是三重循环？还有更快的吗？
3. 一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
hash table? 要是k=0, 所有数都相等呢？怎么看都是n^2了
4. 一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
有元素.
abbc, [a,b,c] -> a, b, c, ab, abb, bbc, bb, bc
有什么好思路？
5.多层链表压扁及还原
我用stack写了一下，面试写起来太麻烦。哪位大牛给个简洁的recursion版本？
谢谢！ | y***n
发帖数: 1594 | | l*****a
发帖数: 14598 | 3 1. Print all paths of a binary tree
How to do it iteratively? 用一个stack实现preorder来做？
==>postOrder可做
2. Given an array of integers, find any 3 numbers in array such that they
sum to zero. eg:
[1, 2, -3, 4, 0]
1) 1 , 2, -3
2) 0, 0, 0
这个是不是三重循环？还有更快的吗？
==>sort O(nlogn), then n^2
3. 一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
hash table? 要是k=0, 所有数都相等呢？怎么看都是n^2了
==> u should know 2 sum
4. 一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
有元素.
abbc, [a,b,c] -> a, b, c, ab, abb, bbc, bb, bc
有什么好思路？
==>懒得想
5.多层链表压扁及还原
我用stack写了一下，面试写起来太麻烦。哪位大牛给个简洁的recursion版本？
==> please see PIE | a***n
发帖数: 623 | 4
1. Print all paths of a binary tree
How to do it iteratively? 用一个stack实现preorder来做？
DFS，每到一个叶子节点打印stack。（不过这里的path是指root到leaf？有见过题目定
义是leaf到leaf）
2. Given an array of integers, find any 3 numbers in array such that they
sum to zero. eg:
[1, 2, -3, 4, 0]
1) 1 , 2, -3
2) 0, 0, 0
这个是不是三重循环？还有更快的吗？
这个已经有数学证明了，X-sum问题最少时间开销是O(N^(X-1))
3. 一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
hash table? 要是k=0, 所有数都相等呢？怎么看都是n^2了
同上，应该是O(n)吧，用一个hashmap的话（重复元素可以加个counter）
4. 一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
有元素.
abbc, [a,b,c] -> a, b, c, ab, abb, bbc, bb, bc
有什么好思路？
单机没有好思路，貌似就一边生成一边过滤。不过建议和面试官讨论多机环境下map
reduce->对字符数组中的每个元素（应该可以assume无重复），map到子问题：从字符
串生成所有不包含此元素的子串->再reduce。我觉得我要是面试官会想听到这个思路。
5.多层链表压扁及还原
leetcode原题？
【在 j********2 的大作中提到】
: 1. Print all paths of a binary tree
: How to do it iteratively? 用一个stack实现preorder来做？
: 2. Given an array of integers, find any 3 numbers in array such that they
: sum to zero. eg:
: [1, 2, -3, 4, 0]
: 1) 1 , 2, -3
: 2) 0, 0, 0
: 这个是不是三重循环？还有更快的吗？
: 3. 一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
: hash table? 要是k=0, 所有数都相等呢？怎么看都是n^2了
| y***n
发帖数: 1594 | | Q**F
发帖数: 995 | 6 同问“多层链表压扁及还原”，原题应该是怎么样的？ | j********2
发帖数: 82 | 7 Thanks! Inline ...
1. Print all paths of a binary tree
How to do it iteratively? 用一个stack实现preorder来做？
DFS，每到一个叶子节点打印stack。（不过这里的path是指root到leaf？有见过题目定
义是leaf到leaf）
==> 那就是还是用一个stack来实现preorder了？
2. Given an array of integers, find any 3 numbers in array such that they
sum to zero. eg:
[1, 2, -3, 4, 0]
1) 1 , 2, -3
2) 0, 0, 0
这个是不是三重循环？还有更快的吗？
这个已经有数学证明了，X-sum问题最少时间开销是O(N^(X-1))
===》这个怎么用n^2解？注意这里一个数可以被选多次
3. 一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
hash table? 要是k=0, 所有数都相等呢？怎么看都是n^2了
同上，应该是O(n)吧，用一个hashmap的话（重复元素可以加个counter）
===》要是k=0, 所有数都相等呢？把解输出就已经是n^2了吧。另外，是把a[i]和-a[i]
都放到hashtable里？
4. 一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
有元素.
abbc, [a,b,c] -> a, b, c, ab, abb, bbc, bb, bc
有什么好思路？
单机没有好思路，貌似就一边生成一边过滤。不过建议和面试官讨论多机环境下map
reduce->对字符数组中的每个元素（应该可以assume无重复），map到子问题：从字符
串生成所有不包含此元素的子串->再reduce。我觉得我要是面试官会想听到这个思路。
===》makes sense. 单机没有好办法了？ | j********2
发帖数: 82 | 8 Thanks! 但是这里一个数可以被选好几次，怎么n^2搞？
2. Given an array of integers, find any 3 numbers in array such that they
sum to zero. eg:
[1, 2, -3, 4, 0]
1) 1 , 2, -3
2) 0, 0, 0
这个是不是三重循环？还有更快的吗？
==>sort O(nlogn), then n^2 | j********2
发帖数: 82 | 9 Sorry. It is like this:
Given a doubly linked list, besides the next and previous pointers, each
element has a child pointer, which may or may not point to a separate doubly
linked list. These child lists may have one or more children of their own.
Now do the following:
a. Flattern this multilevel data structure
b. Restore the original structure from the flatterned structure
e.g.
L1 --> L2 --> L3 --> L7 --> L8
|
v
L4 --> L5-->L6
WIll be flattened to
L1 --> L2 --> L3 -->L4 -->L5-->L6-->L7-->L8
有大牛发一个working的简洁code吗？
【在 y***n 的大作中提到】
: 到底什么是“多层链表压扁及还原”
| j********2
发帖数: 82 | 10 up
【在 j********2 的大作中提到】
: Thanks! Inline ...
: 1. Print all paths of a binary tree
: How to do it iteratively? 用一个stack实现preorder来做？
: DFS，每到一个叶子节点打印stack。（不过这里的path是指root到leaf？有见过题目定
: 义是leaf到leaf）
: ==> 那就是还是用一个stack来实现preorder了？
: 2. Given an array of integers, find any 3 numbers in array such that they
: sum to zero. eg:
: [1, 2, -3, 4, 0]
: 1) 1 , 2, -3
| | | n********g
发帖数: 6504 | 11 4. 双重循环？
【在 j********2 的大作中提到】
: 1. Print all paths of a binary tree
: How to do it iteratively? 用一个stack实现preorder来做？
: 2. Given an array of integers, find any 3 numbers in array such that they
: sum to zero. eg:
: [1, 2, -3, 4, 0]
: 1) 1 , 2, -3
: 2) 0, 0, 0
: 这个是不是三重循环？还有更快的吗？
: 3. 一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
: hash table? 要是k=0, 所有数都相等呢？怎么看都是n^2了
| y***n
发帖数: 1594 | 12 如果一个number可以重复选的话，就不是3-Sum 问题了吧。。
【在 j********2 的大作中提到】
: Thanks! 但是这里一个数可以被选好几次，怎么n^2搞？
: 2. Given an array of integers, find any 3 numbers in array such that they
: sum to zero. eg:
: [1, 2, -3, 4, 0]
: 1) 1 , 2, -3
: 2) 0, 0, 0
: 这个是不是三重循环？还有更快的吗？
: ==>sort O(nlogn), then n^2
| l*****a
发帖数: 14598 | 13 你怎么写preOrder
preOrder上来不就把root打印扔掉了吗？
最后怎么生成path呢
【在 j********2 的大作中提到】
: Thanks! Inline ...
: 1. Print all paths of a binary tree
: How to do it iteratively? 用一个stack实现preorder来做？
: DFS，每到一个叶子节点打印stack。（不过这里的path是指root到leaf？有见过题目定
: 义是leaf到leaf）
: ==> 那就是还是用一个stack来实现preorder了？
: 2. Given an array of integers, find any 3 numbers in array such that they
: sum to zero. eg:
: [1, 2, -3, 4, 0]
: 1) 1 , 2, -3
| y*e
发帖数: 9799 | 14 if extra storage allowed - think of a tree as a graph, store the parent of
each node as you traverse through the tree
【在 l*****a 的大作中提到】
: 你怎么写preOrder
: preOrder上来不就把root打印扔掉了吗？
: 最后怎么生成path呢
| l*****a
发帖数: 14598 | 15 你上code吧
【在 y*e 的大作中提到】
: if extra storage allowed - think of a tree as a graph, store the parent of
: each node as you traverse through the tree
| j**********3
发帖数: 3211 | | y***n
发帖数: 1594 | 17 用个String来Concatenate, 今天有时间写一些。
楼主这几个题都不错，谢谢。。
【在 l*****a 的大作中提到】
: 你怎么写preOrder
: preOrder上来不就把root打印扔掉了吗？
: 最后怎么生成path呢
| y***n
发帖数: 1594 | 18 写了一个，看一看。。
http://ideone.com/NyqYyS
【在 y***n 的大作中提到】
: 用个String来Concatenate, 今天有时间写一些。
: 楼主这几个题都不错，谢谢。。
| y***n
发帖数: 1594 | 19 这个题目明明说“find any 3 numbers”，原题在那里找到的？
【在 j********2 的大作中提到】
: Thanks! 但是这里一个数可以被选好几次，怎么n^2搞？
: 2. Given an array of integers, find any 3 numbers in array such that they
: sum to zero. eg:
: [1, 2, -3, 4, 0]
: 1) 1 , 2, -3
: 2) 0, 0, 0
: 这个是不是三重循环？还有更快的吗？
: ==>sort O(nlogn), then n^2
| j********2
发帖数: 82 | 20 怎么搞？注意一个数可以被选多次
【在 j**********3 的大作中提到】
: 第2个，不是2重循环么？
| | | n********g
发帖数: 6504 | 21 2重循环加一个hash map
【在 j********2 的大作中提到】
: 怎么搞？注意一个数可以被选多次
| y***n
发帖数: 1594 | 22 写了Flattern this multilevel data structure： http://ideone.com/11xcqw
Restore 不知道如何写，感觉要存一下那里开始Flat的才行。
doubly
.
【在 j********2 的大作中提到】
: Sorry. It is like this:
: Given a doubly linked list, besides the next and previous pointers, each
: element has a child pointer, which may or may not point to a separate doubly
: linked list. These child lists may have one or more children of their own.
: Now do the following:
: a. Flattern this multilevel data structure
: b. Restore the original structure from the flatterned structure
: e.g.
: L1 --> L2 --> L3 --> L7 --> L8
: |
| j**7
发帖数: 143 | 23 1.)
/*
* print all paths from root to leaf.
*/
public static void printPaths(TreeNode root) {
if (root == null) {
return;
}
ArrayList path = new ArrayList();
// post order tree traversal.
Stack st = new Stack();
st.add(root);
while (st.isEmpty() == false) {
TreeNode current = st.pop();
if (current == null) {
current = st.pop();
if (current.left == null && current.right == null) {
System.out.println(path.toString());
}
path.remove(path.size() - 1);
} else {
st.add(current);
st.add(null);
path.add(current.val);
if (current.right != null) {
st.add(current.right);
}
if (current.left != null) {
st.add(current.left);
}
}
}
} | j**7
发帖数: 143 | 24 5.多层链表压扁及还原
// 没有测试过。
public static Node flatten(Node head, Node tail) {
Node start = head;
while (head != tail.next) {
Node next = head.next;
if (head.down != null) {
Node leftMost = leftMost(head.down);
Node rightMost = rightMost(head.down);
head.down.up = null;
head.down = null;
head.next = leftMost;
leftMost.prev = head;
rightMost.next = next;
next.prev = rightMost;
next = leftMost;
}
if (head.up != null) {
Node leftMost = leftMost(head.up);
Node rightMost = rightMost(head.up);
head.up.down = null;
head.up = null;
head.next = leftMost;
leftMost.prev = head;
rightMost.next = next;
next.prev = rightMost;
next = leftMost;
}
head = next;
}
return start;
}
private static Node leftMost(Node n) {
while (n != null && n.prev != null) {
n = n.prev;
}
return n;
}
private static Node rightMost(Node n) {
while (n != null && n.next != null) {
n = n.next;
}
return n;
}
private static class Node {
private Node next;
private Node prev;
private Node up;
private Node down;
public Node() {
}
} | j********8
发帖数: 10 | 25 static int setBit(int input, int bit)
{
int mask = 1;
mask <<= bit;
return input |= mask;
}
// assumption all characters are lower case
static vector findSubStr(string source, vector chars)
{
vector result;
// first convert chars into an integer, where bit 0-25 correspond to
a-z, o(n)
int charsBits = 0;
for (int i = 0; i < chars.size(); i++)
{
int bit = chars[i] - 'a';
charsBits = setBit(charsBits, bit);
}
// then find all the substrings of the source, o(s^2), convert
substring to integer, o(1), overall o(s^2)
for (int i = 0; i < source.length(); i++)
{
int bit = source[i] - 'a';
int currSubStrBits = setBit(0, bit);
for (int j = i; j < source.length(); j++)
{
//update currSubStrBits with the incoming character
bit = source[j] - 'a';
currSubStrBits = setBit(currSubStrBits, bit);
// then compare the currSubStrBits with charsBits, if they
equal, then its not valid, we can skip the rest of j
if (currSubStrBits == charsBits)
{
break;
}
else
{
result.push_back(source.substr(i, j - i + 1));
}
}
}
return result;
}
Test code:
string source = "abccccdef";
char mychars[] = {'a', 'b', 'c'};
std::vector chars (mychars, mychars + sizeof(mychars) / sizeof
(char) );
vector result = findSubStr(source, chars);
【在 j********2 的大作中提到】
: 1. Print all paths of a binary tree
: How to do it iteratively? 用一个stack实现preorder来做？
: 2. Given an array of integers, find any 3 numbers in array such that they
: sum to zero. eg:
: [1, 2, -3, 4, 0]
: 1) 1 , 2, -3
: 2) 0, 0, 0
: 这个是不是三重循环？还有更快的吗？
: 3. 一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
: hash table? 要是k=0, 所有数都相等呢？怎么看都是n^2了
| j********2
发帖数: 82 | 26 这个解法很赞，谢了！
【在 y***n 的大作中提到】
: 写了一个，看一看。。
: http://ideone.com/NyqYyS
| j********2
发帖数: 82 | 27 我也不知道restore怎么写，贴一下我的flattern. 没用recursion, 用了一个stack:
void flatternAugListWithStack(AugListNode *&node)
{
if (!node) return;
stack st;
AugListNode *p = node; // current node
AugListNode *tail = node; // current tail
while (1)
{
if (!p && st.empty()) break;
// after we go over the children, fetch it from the stack
if (!p) {p = st.top(); st.pop(); tail->next = p; continue;}
if (!p->next) tail = p;
if (!p->child) p = p->next;
else
{
if (p->next)
{
st.push(p->next); // save the next node
}
p->next = p->child; // change the next pointer
p = p->next;
}
}
}
【在 y***n 的大作中提到】
: 写了Flattern this multilevel data structure： http://ideone.com/11xcqw
: Restore 不知道如何写，感觉要存一下那里开始Flat的才行。
:
: doubly
: .
| y***n
发帖数: 1594 | | j********2
发帖数: 82 | 29 大牛觉得code应该怎么写呢
【在 y***n 的大作中提到】
: 感觉Restore还要一些其他条件
| w******w
发帖数: 126 | | | | y***n
发帖数: 1594 | 31 找longway2008, 我是文科生转的。。。
【在 j********2 的大作中提到】
: 大牛觉得code应该怎么写呢
| l*****a
发帖数: 14598 | 32 PIE上有solution
自己去看好了
【在 j********2 的大作中提到】
: 大牛觉得code应该怎么写呢
| t********n
发帖数: 611 | 33 Thanks!
My answer in ruby:
require 'set'
def sum_3(arr, k)
check = arr.to_set
result = Set.new
arr.each do |m|
arr.each do |n|
target = k - m -n
if check.include?(target)
result.add([m, n, target].to_set)
end
end
end
result
end
def restore(my_set, k)
result = []
my_set.each do |s|
if s.length == 3
result << s.to_a
elsif s.length == 2
arr = s.to_a
arr << (k - arr[0] - arr[1])
result << arr
else
result << (s.to_a * 3)
end
end
result
end
my_set = sum_3([1, 2, -3, 4, 0], 0)
p restore(my_set, 0)
I tested it and got the correct answer.
【在 n********g 的大作中提到】
: 2重循环加一个hash map
| t********n
发帖数: 611 | 34 4. 一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
有元素.
abbc, [a,b,c] -> a, b, c, ab, abb, bbc, bb, bc
My answer in Ruby:
def limited_sub(s, arr)
result = Set.new
(0..s.length - 1).each do |i|
(i..s.length - 1).each do |j|
sub = s[i..j]
if sub.split("").to_set.length < arr.length
result.add(sub)
end
end
end
result
end
p limited_sub("abbc", ['a', 'b', 'c'])
I tested and got correct answer. | t********n
发帖数: 611 | 35 4. 一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
有元素.
abbc, [a,b,c] -> a, b, c, ab, abb, bbc, bb, bc
有什么好思路？
单机没有好思路，貌似就一边生成一边过滤。不过建议和面试官讨论多机环境下map
reduce->对字符数组中的每个元素（应该可以assume无重复），map到子问题：从字符
串生成所有不包含此元素的子串->再reduce。我觉得我要是面试官会想听到这个思路。
I can't figure out how to implement this to make it faster than O(n ^2)... | t********n
发帖数: 611 | 36 3. 一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
hash table? 要是k=0, 所有数都相等呢？怎么看都是n^2了
同上，应该是O(n)吧，用一个hashmap的话（重复元素可以加个counter）
===》要是k=0, 所有数都相等呢？把解输出就已经是n^2了吧。另外，是把a[i]和-a[i]
都放到hashtable里？
def sum_2b(arr, k)
seen = Hash.new{ |hash, key| hash[key] = [] }
result = Set.new
(0..arr.length - 1).each do |i|
if seen.include?(k+ arr[i])
seen[k+ arr[i]].each do |j|
result.add([j, i])
end
end
seen[arr[i]]<< i
end
result
end
p sum_2b([3,3,3], 0) #got [[0, 1],[0, 2],[1, 2]], O(n ^2)
If we just want the actual nums, we can use 2 sum to get linear time, but is
we want the actual index, it seems like linear time impossible? | t********n
发帖数: 611 | 37 What is PIE?
【在 l*****a 的大作中提到】
: PIE上有solution
: 自己去看好了
| r*******k
发帖数: 1423 | 38 这个case可以先从头到尾访问一遍字符串
然后就可以得到好多个最小的包含abc的范围
[0,4]
然后双重循环i，j
只要不满足i<=0,j>=4
都是一个合法的子串
【在 t********n 的大作中提到】
: 4. 一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
: 有元素.
: abbc, [a,b,c] -> a, b, c, ab, abb, bbc, bb, bc
: 有什么好思路？
: 单机没有好思路，貌似就一边生成一边过滤。不过建议和面试官讨论多机环境下map
: reduce->对字符数组中的每个元素（应该可以assume无重复），map到子问题：从字符
: 串生成所有不包含此元素的子串->再reduce。我觉得我要是面试官会想听到这个思路。
: I can't figure out how to implement this to make it faster than O(n ^2)...
| r*******k
发帖数: 1423 | 39 其实好像不用遍历再判断
i的范围会决定了j的范围
可以直接生成
所以应该比n^2低点，不过还是有可能有重复的
还是要判断是否已经生成过
【在 r*******k 的大作中提到】
: 这个case可以先从头到尾访问一遍字符串
: 然后就可以得到好多个最小的包含abc的范围
: [0,4]
: 然后双重循环i，j
: 只要不满足i<=0,j>=4
: 都是一个合法的子串
| l*********8
发帖数: 4642 | 40 Programming Interview Exposed.
【在 t********n 的大作中提到】
: What is PIE?
| | | l*********8
发帖数: 4642 | 41 PIE上的跟这个不是一题。
【在 l*****a 的大作中提到】
: PIE上有solution
: 自己去看好了
| l*********8
发帖数: 4642 | 42 我写一个linked list flatten和restore吧。 可能还有bugs
Node * flatten(Node * curr, Node * tail = NULL, Node * parent = NULL) {
if (!curr) return tail;
if (tail)
tail->next = current;
tail = current;
Node * next = curr->next;
if (curr->child)
tail = flatten(curr->child, tail, next ? curr : parent);
else if (!next)
curr->child = parent;
return flatten(next, tail, parent);
}
void restore(Node * curr) {
while (curr) {
Node * next = curr->next;
if (curr->child) {
curr->next = NULL;
if (curr->child != next) {
curr->child->next = next;
curr->child = NULL;
}
}
curr = next;
}
}
【在 y***n 的大作中提到】
: 找longway2008, 我是文科生转的。。。
| j********2
发帖数: 82 | 43 restore 部分没看懂，大牛可否解释一下？
【在 l*********8 的大作中提到】
: 我写一个linked list flatten和restore吧。 可能还有bugs
: Node * flatten(Node * curr, Node * tail = NULL, Node * parent = NULL) {
: if (!curr) return tail;
:
: if (tail)
: tail->next = current;
: tail = current;
: Node * next = curr->next;
: if (curr->child)
: tail = flatten(curr->child, tail, next ? curr : parent);
| l*********8
发帖数: 4642 | 44 在flatten的时候，利用没有child也没有next的节点的child pointer来指向restore时
要返回的祖先节点。
restore的时候，利用前面说的"child pointer"来返回祖先节点，并恢复指针的值。
【在 j********2 的大作中提到】
: restore 部分没看懂，大牛可否解释一下？
| y***n
发帖数: 1594 | 45 这个有点看晕了，我可能会用一个map 存一下被Flatten的List 的头尾
节点，然后Restore 一下。 | j********2
发帖数: 82 | 46 大牛上个code吧
【在 y***n 的大作中提到】
: 这个有点看晕了，我可能会用一个map 存一下被Flatten的List 的头尾
: 节点，然后Restore 一下。
| j********2
发帖数: 82 | 47 照你的建议写了一个，没测过
void restore(AugListNode *head, unordered_map
&ht)
{
if (!head) return;
AugListNode *curNode, *nextNode;
curNode = head; nextNode = curNode->next;
while (1)
{
if (!curNode) break;
if (ht.find(nextNode) != ht.end()) // a child list found
{
// separate the child list
curNode->child = nextNode;
AugListNode *nextNodeAfterChildList = ht[nextNode]->next;
curNode->next = nextNodeAfterChildList;
restore(nextNode, ht); // restore the child list
// move on
curNode = nextNodeAfterChildList;
nextNode = curNode->next;
}
else
{
// move on
curNode = nextNode;
nextNode = curNode->next;
}
}
}
【在 y***n 的大作中提到】
: 这个有点看晕了，我可能会用一个map 存一下被Flatten的List 的头尾
: 节点，然后Restore 一下。
| y***n
发帖数: 1594 | | v***o
发帖数: 287 | 49 1. 递归 plus path array
Pseudo code(Pre-Order)
public void PrintAllPath( ArrayList paths, Node node)
{
System.Out.Println(paths.Tostring);
if (node ==null)
return;
paths.Add(node);
PrintAllPath(paths, node.Left);
PrintAllPath(paths, node.right);
}
不用递归的话，用个 额外的stack traversal即可。
【在 j********2 的大作中提到】
: 1. Print all paths of a binary tree
: How to do it iteratively? 用一个stack实现preorder来做？
: 2. Given an array of integers, find any 3 numbers in array such that they
: sum to zero. eg:
: [1, 2, -3, 4, 0]
: 1) 1 , 2, -3
: 2) 0, 0, 0
: 这个是不是三重循环？还有更快的吗？
: 3. 一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
: hash table? 要是k=0, 所有数都相等呢？怎么看都是n^2了
| p****6
发帖数: 724 | 50
doubly
.
if(node == null) return node;
Stack stack = new Stack();
ListNode head = new ListNode(-1);
head.next = node;
while(node!=null){
if(node.other!=null){
if(node.next!=null)
stack.add(node.next);
node.next = node.other;
node.other = null;
}else{
if(node.next == null && !stack.isEmpty()){
ListNode top = stack.pop();
node.next = top;
}
}
node = node.next;
}
return head.next;
用stack还清晰些。
【在 j********2 的大作中提到】
: Sorry. It is like this:
: Given a doubly linked list, besides the next and previous pointers, each
: element has a child pointer, which may or may not point to a separate doubly
: linked list. These child lists may have one or more children of their own.
: Now do the following:
: a. Flattern this multilevel data structure
: b. Restore the original structure from the flatterned structure
: e.g.
: L1 --> L2 --> L3 --> L7 --> L8
: |
| | | m*********a
发帖数: 3299 | 51 这个不错
【在 j**7 的大作中提到】
: 1.)
: /*
: * print all paths from root to leaf.
: */
: public static void printPaths(TreeNode root) {
: if (root == null) {
: return;
: }
: ArrayList path = new ArrayList();
: // post order tree traversal.
| x****B
发帖数: 103 | 52 你把这个链表想像成二叉树或者带父亲节点的二叉树。然后前序遍历？
doubly
.
【在 j********2 的大作中提到】
: Sorry. It is like this:
: Given a doubly linked list, besides the next and previous pointers, each
: element has a child pointer, which may or may not point to a separate doubly
: linked list. These child lists may have one or more children of their own.
: Now do the following:
: a. Flattern this multilevel data structure
: b. Restore the original structure from the flatterned structure
: e.g.
: L1 --> L2 --> L3 --> L7 --> L8
: |
| b*******r
发帖数: 50 | |
|
