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

2007年7月9日

实现一个栈,使其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 阅读(282) | 评论 (0) | 编辑 收藏

Java Language Keywords

Here's a list of keywords in the Java programming language. You cannot use any of the following as identifiers in your programs. The keywords const and goto are reserved, even though they are not currently used. true, false, and null might seem like keywords, but they are actually literals; you cannot use them as identifiers in your programs.
abstract continue for new switch
assert*** default goto* package synchronized
boolean do if private this
break double implements protected throw
byte else import public throws
case enum**** instanceof return transient
catch extends int short try
char final interface static void
class finally long strictfp** volatile
const* float native super while

posted @ 2007-07-09 22:38 Job Hu 阅读(194) | 评论 (1) | 编辑 收藏