随笔 - 8, 文章 - 0, 评论 - 6, 引用 - 0
数据加载中……

2007年7月17日

实现一个栈,使其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) | 编辑 收藏

Byte in Java


public class ByteTest
{
    public static void main(String[] args)
    {
        byte b;
        byte c;
        //b = 255; //Cannot convert from int to byte
        //b = 0xFF; //Cannot convert from int to byte
        b = 127;
        c = 0x7F;
        if(b == c) System.out.println("b == c");
        if(127 == 0x7F) System.out.println("127 == 0x7F");
        
        b = -128;
        //c = 0x80; //Cannot convert from int to byte
        c = (byte)0x80;
        if(b == c) System.out.println("b == c");
        if(-128 == 0x80) System.out.println("-128 == 0x80");
        if(128 == 0x80) System.out.println("128 == 0x80"); 
        
        c = (byte)0x80;
        if(128 == c) System.out.println("128 == c");
        if(-128 == c) System.out.println("-128 == c");
        if(128 == (c&0xFF)) System.out.println("128 == (c&0xFF)");
    }
}
输出:
b == c
127 == 0x7F
b == c
128 == 0x80
-128 == c
128 == (c&0xFF)

posted @ 2007-07-17 23:22 Job Hu 阅读(281) | 评论 (0) | 编辑 收藏