JobHu

隨筆 - 8, 文章 - 0, 評論 - 6, 引用 - 0

數據加載中……

2007年7月18日

實現一個棧,使其push,pop,min(取得棧中的最小元素)均為O(1)

實現一個棧,使其push,pop,min(取得棧中的最小元素)均為O(1)

我的解

interface IntStack

{

int pop();

void push(int i);

int get();

}

class MinStack

{

//store all the element

private IntStack elemStack = new IntStack();

//store current and historical smallest element

private IntStack minStack = new IntStack();

public void push(int i)

{

elemStack.push(i);

int currentMin = minStack.get();

if(i <= currentMin) minStack.push(i);

}

public int pop()

{

int result = elemStack.pop();

if(result == minStack.get()) minStack.pop();

return result;

}

public int getMinElem()

{

return minStack.get();

}

posted @ 2007-07-18 20:57 Job Hu 閱讀(902) | 評論 (0) | 編輯收藏

二叉排序樹變為雙向鏈表

把一個二叉排序樹(也許不叫這個)變為遞增的雙向鏈表,不能夠生成額外的結點.
eg 6
       / \
      4   8
     / \ / \
    3 5 7 9

3=4=5=6=7=8=9

我的解:

class Node

{

public Node left;

public Node right;

private static Node getLinkListTail(Node head)

{

Node result = head;

if(result==null) return null;

while(result.right!=null)

{

result = result.right;

}

return result;

}

public static Node flatten(Node root)

{

if(root==null) return null;

Node result = root;

// A leaf node

if(root.left==null&&root.right==null) return root;

//divide-and-conquer

Node leftSubTreeLinkListHead = flatten(root.left);

Node rightSubTreeLinkListHead = flatten(root.right);

//merge

Node leftSubTreeLinkListTail = getLinkListTail(leftSubTreeLinkListHead);

root.left = leftSubTreeLinkListTail;

root.right = rightSubTreeLinkListHead;

if(leftSubTreeLinkListHead!=null)

{

result = leftSubTreeLinkListHead;

leftSubTreeLinkListTail.right = root;

}

if(rightSubTreeLinkListHead!=null) rightSubTreeLinkListHead.left = root;

return result;

}

posted @ 2007-07-18 20:37 Job Hu 閱讀(648) | 評論 (0) | 編輯收藏

JobHu

實現一個棧,使其push,pop,min(取得棧中的最小元素)均為O(1)

二叉排序樹變為雙向鏈表

導航

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜