随笔 - 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 阅读(894) | 评论 (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 阅读(641) | 评论 (0) | 编辑 收藏