剑指offer第二周

1. 正则表达式
   link
2. 表示数值的字符串

public class Solution {
    public boolean isNumeric(char[] str) {
        StringBuilder t1 = new StringBuilder();
        int i=0;
        while(i<str.length&&(str[i]!='e'&&str[i]!='E')){
            t1.append(str[i]);
            i++;
        }
        if(i>=str.length)
            return isNum(t1.toString());
        else{
            i++;
            StringBuilder t2 = new StringBuilder();
            while(i<str.length){
                t2.append(str[i]);
                i++;
            }
            return isintNum(t2.toString());
        }
    }
    private boolean isintNum(String str){
        int i=0;
        if(str == null ||str.length()==0)
            return false;
        if(str.charAt(0) == '+'||str.charAt(0)=='-')
            i++;
        if(i>=str.length())
            return false;
        else{
            for(;i<str.length();i++){
                if(str.charAt(i)<'0'||str.charAt(i)>'9')
                    return false;
            }
            return true;
        }
        
    }
        private boolean isNum(String str){
            int i=0;
            if(str.charAt(0)=='+'||str.charAt(0)=='-')
                i++;
            boolean tag = false;  
            for(;i<str.length();i++){
                if(str.charAt(i) == '.'){
                    if(!tag)
                        tag = true;
                    else
                        return false;
                    if(i == str.length()-1||i==0)
                        return false;
                }
                else if(str.charAt(i)<'0'||str.charAt(i)>'9')
                    return false;
            }
            return true;
        }
    
}

做的好像有点麻烦了，带有小数和不带小数的分别判断

3. 字符流中第一个不重复的字符

import java.util.*;
public class Solution {
    //Insert one char from stringstream
    Map<Character,Integer> map = new HashMap<Character,Integer>();
    Queue<Character> queue = new LinkedList<Character>();
    public void Insert(char ch)
    {
      if(map.containsKey(ch)){
          map.put(ch,map.get(ch)+1);
          queue.remove(ch);
      }else{
          map.put(ch,1);
          queue.add(ch);
      }
        
        
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        if(!queue.isEmpty())
             return queue.peek();
        else
            return '#';
    
    }
}

4. 链表中环的入口结点

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        ListNode pFast = pHead, pSlow = pHead;
        while(pFast!=null && pFast.next!=null){
            pFast = pFast.next.next;
            pSlow = pSlow.next;
            if(pSlow == pFast){
                pSlow = pHead;
                while(pSlow!=pFast){
                    pSlow = pSlow.next;
                    pFast = pFast.next;
                }
                return pSlow;
            }
        }
        return null;
    }
}

5. 删除链表中重复结点

• 思路是用三个指针遍历，并且保存头结点，发现有重复的，将pre指向last

public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        if(pHead == null ||pHead.next == null)
            return pHead;
       //考虑phead为null或者只有一个结点，直接返回pHead
        ListNode pre = new ListNode(-1);//pre为前结点
        pre.next = pHead;
        ListNode result = pre;//保留头结点
        ListNode cur = pHead;//当前结点
        ListNode last = pHead.next;//后结点
        while(last!=null){
            while(last!=null && last.val == cur.val){
                last = last.next;//如果有重复，last指向下一个
            }
            if(cur.next!= last){//这是有重复结点情况
                pre.next = last;
                cur = last;
                if(last !=null)
                    last = last.next;
            } else{//没有重复结点情况
                pre = cur;
                last = last.next;
                cur = cur.next;
            }
        }
        return result.next;

    }
}

6. 二叉树的下一个结点

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode == null)
            return pNode;
//考虑如果右结点不为空，寻找右结点的左结点的左结点
        if(pNode.right!=null){
            pNode = pNode.right;
            while(pNode.left!=null)
                pNode = pNode.left;
            return pNode;
        }
//向上寻找，要么pNode.next.left=pNode，那么说明下一个应该访问父节点。不然向上寻找，直到pNode.next.left == pNode
        while(pNode.next!=null){
            if(pNode.next.left == pNode)
                return pNode.next;
            pNode = pNode.next;
        }
        return null;
        
    }
}