c****7
发帖数: 13 | 1 写了个第一题的DFS的非递归解法， 请高手多指教
public static TreeNode findDeepestNode(TreeNode root){
if(root ==null) return root;
int maxDepth = 1;
TreeNode deepestNode = root;
// The previous node we just traversed
TreeNode preNode=null;
// The top item in the stack
TreeNode curNode;
Stack nodeStack = new Stack();
nodeStack.push(root);
// exit until the stack is empty
while(!nodeStack.isEmpty())... 阅读全帖 |
|
r*******n
发帖数: 3020 | 2 我的递归解法，大家看看对吗？
Node flat_list_head[N]; // N is the largest level.
void flattenList(Node *head, int level)
{
if (head->next){
insert_node_front_flat_list_head(head, level);
// Go next
head = head->next;
flattenList(head, level);
}
if (head->child){
insert_node_front_flat_list_head(head, level+1);
// Go child
head = head->child;
flattenList(head, level+1);
}
}
void ... 阅读全帖 |
|
m*****g
发帖数: 226 | 3 不是很明白。高手评价一下：
void postOrderTraversal(node *root)
{
stack st;
st.push(root);
st.push(root);
node *curNode;
node *visited;
while(!st.empty())
{
visited=st.top();
st.pop();
curNode=st.top();
st.pop();
if(!(curNode->left&&curNode->right)) {printf(curNode); st.push(curNode)
; continue;}
if(curNode->left && (curNode->left != visited))
{ st.push(curNode);
if(curNode->right) st.push(curNode->right);
st.push(curNode->left);
|
|
b*********s
发帖数: 115 | 4 非大牛
我是在最开始加一个dummy head
public class Solution {
public ListNode insertionSortList(ListNode head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
ListNode dummy = new ListNode(Integer.MIN_VALUE);
dummy.next = head;
ListNode preNode = dummy;
ListNode curNode = dummy.next;
while (curNode != null) {
ListNode pre = dummy;
ListNode cur = dum... 阅读全帖 |
|
k*******n
发帖数: 190 | 5 public class BinaryTree {
TreeNode root;
Vector path;
public void FindPath() {
if (root!=null) FindPath(root);
};
public void FindPath(TreeNode curNode) {
boolean isLeaf=(curNode.leftNode==null && curNode.rightNode==null);
if (!isLeaf) {
path.add(curNode);
if (curNode.leftNode!=null) FindPath(curNode.leftNode);
if (curNode.rightNode!=null) FindPath(curNode.rightNode);
path.removeElement(curNode);
} else {
path.add(curNode);
... 阅读全帖 |
|
k*******n
发帖数: 190 | 6 public class BinaryTree {
TreeNode root;
Vector path;
public void FindPath() {
if (root!=null) FindPath(root);
};
public void FindPath(TreeNode curNode) {
boolean isLeaf=(curNode.leftNode==null && curNode.rightNode==null);
if (!isLeaf) {
path.add(curNode);
if (curNode.leftNode!=null) FindPath(curNode.leftNode);
if (curNode.rightNode!=null) FindPath(curNode.rightNode);
path.removeElement(curNode);
} else {
path.add(curNode);
... 阅读全帖 |
|
c******n
发帖数: 16666 | 7 说来比较悲催 非cs专业，搞了个小程序跑模拟，数据量小的时候还好，数据量一大先
是内存挂了。后来跑去ec2租了个大内存服务器发现跑得还是很慢，仔细一看，有个
function算得特别慢，因为是n*n的复杂度，数据量上去了计算时间马上跳了等量级上
升。自己又是一知半解的，不知道哪位能帮着改进下算法然后提示下OpenMP该怎么做。
简而言之，是个关于水文的模拟，计算流域面积，所以数据的基本单位/对象就是node
。 有两个linked-list（求别吐槽用这个而不用vector，摊子摊太大了 改起来不容易
，或者如果我现在添加一个vector，复制现有list行不？）里面存的都是node之间的指
针。
第一个linked-list存的所有node的指针，按照node的ID存放，方便遍历所有node
第二个linked-list，其实不止一个，存的是所有在当前node的下游的node的指针，遍
历的话可以从当前node一直走到当前mesh的边界
流域面积的具体计算，就是当前node自己的面积加上其所有上有点面积的总和
比如在下图中，
a b c d e
... 阅读全帖 |
|
c****7
发帖数: 13 | 8 各位高手，我想用 Pre-Order Traversal 来实现 maxDepth()。 我用了个hashmap来
保存各个节点的高度.不知道有没有跟优化的解法， 谢谢了！
Here is my code:
public static int maxDepth_preOrderTraversal(TreeNode root){
int maxHight =1;
HashMap nodeHashMap = new HashMap();
if (root==null) return 0;
Stack nodeStack = new Stack();
TreeNode curNode;
nodeStack.push(root);
nodeHashMap.put(root, 1);
while(!nodeStack.isEmpty()){
curNode = nodeStack.pop();
if(curNode.right!=null){
nodeStack.pu... 阅读全帖 |
|
j********2
发帖数: 82 | 9 照你的建议写了一个，没测过
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->... 阅读全帖 |
|
h****8
发帖数: 599 | 10 请教一下 有个地方没看懂
if(curNode.second)
{
treeNode *curChild = curNode.first->children[curNode.second-1];
treeNodeStack.push(make_pair(curNode.first, curNode.second-1));
treeNodeStack.push(make_pair(curChild, curChild->numChildren));
}
else
{
if(!(curNode.first->numChildren)) //leaf node
{
depth = 0;
}
else
这里最后一个else是什么情况？哪些情况才会depth++? |
|
c****7
发帖数: 13 | 11 原题是leetcode上的merge k sorted lists
http://discuss.leetcode.com/questions/204/merge-k-sorted-lists
这个题有好几种解法，比如divide and conquer, priority queue.
我写了个priority queue的。我的问题是， 如果现在要做 merge k sorted
array,怎样来设计这个priority queue才能最简单有效呢？
附上 merge-k-sorted-lists的代码
public static ListNode mergeKLists_priorityQueue(ArrayList kLists)
{
// border case
if(kLists.size()==0) return null;
if(kLists.size()==1) return kLists.get(0);
// create a Comparator based on the nod... 阅读全帖 |
|
l******6
发帖数: 340 | 12 struct node;
void print100(stack& waitStack);
struct childList{
node* curNode;
childList* next;
};
struct node{
void* data;
childList* children;
};
void print(node* root)
{
if(!root)
return;
childList* dummy = new childList();
dummy -> curNode = root;
dummy -> next = NULL;
stack waitStack;
waitStack.push(dummy);
while(!waitStack.empty())
{
print100(waitStack);
}
delete dummy;
}
void print1... 阅读全帖 |
|
m*****g
发帖数: 226 | 13 int treeDepthNonRec(treeNode *root)
{
int maxDepth = 0;
if(!root) return 0;
stack > treeNodeStack;
//using traversal
treeNodeStack.push(make_pair(root, root->numChildren));
int depth = 0;
while(!treeNodeStack.empty())
{
pair curNode = treeNodeStack.top();
treeNodeStack.pop();
if(curNode.second)
{
treeNode *curChild = curNode.first->children[curNode.second-1];
|
|
g***9
发帖数: 159 | 14 第二题公共前缀并不是leetcode原题吧...
请教大牛 rolling hash 的解法 .. ?
自己写了一个Trie的python版本:
import sys
CHAR_COUNT = 26
class Entry(object):
def __init__(self, count=0, next=None):
self.cnt = count
self.nxt = next
#def
#class
class TrieNode(object):
def __init__(self):
self.entrylist = []
for i in xrange(CHAR_COUNT):
self.entrylist.append(Entry())
#for
#def
#class
root = TrieNode()
def InsertTrieNodes(root, curstr):
n = len(curstr)
prefix = []
curnode = root
valid = Tru... 阅读全帖 |
|
k******4
发帖数: 94 | 15 level order的最大问题就是空间复杂度，指数增长.
试着用DFS写了下，空间复杂度是O(logn)，时间O(n),
//treeDepth 是树的实际高度，desiredDepth是叶子的期望高度。
//当第一次遇到一个比treeDepth高度小一的叶子，把desiredDepth的设置为treeDepth
-1,并且需要后面所有叶子的高度都是这个值。
bool validateCompleteBT(TreeNode*root, const int &treeDepth, int &
desiredDepth, int curDepth, bool &setDesiredDepthFlag)
{
curDepth++;
if(root->left == NULL && root->right == NULL)
{
if(setDesiredDepthFlag && curDepth == (treeDepth-1))
{
setDesiredDepthFlag... 阅读全帖 |
|
l******6
发帖数: 340 | 16 put node* root in stack
while stack is not empty :
node* curNode equals the top
pop the top
visit curNode
if curNode is not null:
put all the children of curNode in stack |
|
l******6
发帖数: 340 | 17
void printn(stack& waitStack , int n)
{
if(n == 0 || waitStack.empty())
return;
childList* curHead = waitStack.top();
waitStack.pop();
dealWith(curHead -> curNode -> data);
if(curHead -> next)
waitStack.push(curHead -> next);
if(curHead -> curNode -> children)
waitStack.push(curHead -> curNode -> children);
printn(waitStack , n-1);
} |
|
w********g
发帖数: 106 | 18 太强了！！！你的最后一行code我写了很多行实现，分了各种情况。看了你的code，才
发现其实那么多种情况本质上就是递归调用到栈顶，顿时佩服得五体投地。万分感谢赐
教！
void printn(stack& waitStack , int n)
{
if(n == 0 || waitStack.empty())
return;
childList* curHead = waitStack.top();
waitStack.pop();
dealWith(curHead -> curNode -> data);
if(curHead -> next)
waitStack.push(curHead -> next);
if(curHead -> curNode -> children)
waitStack.push(curHead -> curNode -> children);
printn(waitStack , n-1);
} |
|
e****e
发帖数: 418 | 19 For Q2, implement 2 methods, goToNextNode(Node node), goToPrevNode(Node node
). Mehtod goToNextNode(Node curNode) returns the node on the right subTree
of curNode and this node has the closest key to the curKey among the subTree
. It's like the next node in inorder traversal.
Then go to the node containing the input key, from there, call goToNextNode(
)/goToPrevNode recursively and compare its key the input key. You can think
of those two methods as two pointers in between which input key node.
... 阅读全帖 |
|
l******6
发帖数: 340 | 20 struct childList{
node* curNode;
childList* next;
};
struct node{
void* data;
childList* children;
};
curHead is a pointer of childList type , not a node type. childlist have
sibling pointer while node doesn't have.
It is true it is only a preorder iterative traverse, the point is to modify
the code so that parameter can be passed to the printn() function nicely. |
|
