5.3 时间效率与空间效率的平衡

面试题50：字符流中第一个只出现一次的字符
题目描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
输出描述
如果当前字符流没有存在出现一次的字符，返回#字符。
HashMap

import java.util.HashMap;
public class Solution {
    StringBuffer sb=new StringBuffer();
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        sb.append(ch);
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        HashMap<Character,Integer> map=new HashMap();
        for(int i=0;i<sb.length();i++)
        {
            if(map.containsKey(sb.charAt(i)))
            {
                map.put(sb.charAt(i),map.get(sb.charAt(i))+1);
            }
            else
            {
                map.put(sb.charAt(i),1);
            }
        }
        char c='#';
        for(int i=0;i<sb.length();i++)
        {
            if(map.get(sb.charAt(i))==1)
            {
                c=sb.charAt(i);
                break;
            }
        }
        return c;
    }
}

数组实现简易版HashMap

import java.util.HashMap;
public class Solution {
    StringBuffer sb=new StringBuffer();
    int[] a=new int[256];

    //Insert one char from stringstream
    public void Insert(char ch)
    {
        sb.append(ch);
        a[ch]++;
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        char c='#';
        for(int i=0;i<sb.length();i++)
        {
            if(a[sb.charAt(i)]==1)
            {
                c=sb.charAt(i);
                break;
            }
        }
        return c;
    }
}

测试用例

• 功能测试：输入一个字符，输入多个字符，输入的所有字符都是唯一的，输入的所有字符都是重复出现的；
• 特殊输入测试：输入0个字符。

面试题52 两个量表的第一个公共结点
题目描述
输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
用栈的思想 空间换时间

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.Stack;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead2==null||pHead1==null)
            return null;
        Stack<ListNode> s1=new Stack<>();
        Stack<ListNode> s2=new Stack<>();
        while(pHead1!=null)
        {
            s1.add(pHead1);
            pHead1=pHead1.next;
        }
        while(pHead2!=null)
        {
            s2.add(pHead2);
            pHead2=pHead2.next;
        }
        ListNode l=null;
        while(!s1.isEmpty()&&!s2.isEmpty()&&s1.peek()==s2.peek())
        {
            l=s1.pop();
            s2.pop();
        }
        return l;
    }
}

优化方法

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead2==null||pHead1==null)
            return null;
        ListNode p1=pHead1;
        ListNode p2=pHead2;
        while(p2!=p1)
        {
            p2=p2.next;
            p1=p1.next;
            if(p1!=p2)
            {
                if(p1==null)
                    p1=pHead2;
                if(p2==null)
                    p2=pHead1;
            }
        }
        return p2;
    }
}