剑指offer笔记Java（6）

发表于 | 分类于 ，

表示数值的字符串

题目描述

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。

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

题目描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。

输出描述:
如果当前字符流没有存在出现一次的字符，返回#字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    //Insert one char from stringstream
    private int [] count = new int [256];
    private int index = 0;
    private String s = new String();
    public void Insert(char ch)
    {
        s = s + ch;
        index++;
        count[ch]++;
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        for (int i = 0; i < index; i++) {
            if (count[s.charAt(i)]==1)
                return s.charAt(i);
        }
        return '#';
    }
}

链表中环的入口节点

题目描述

一个链表中包含环，请找出该链表的环的入口结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
 public class ListNode {
    int val;
    ListNode next = null;

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

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        if (pHead == null || pHead.next == null)
            return null;
        ListNode p1 = pHead;
        ListNode p2 = pHead;
        while (p2.next.next != null && p1.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            if(p1 == p2)
                break;
        }
        ListNode meet = p2;
        if (meet == pHead)
            return meet;
        p1 = pHead;
        while (true) {
            p1 = p1.next;
            meet = meet.next;
            if (meet == p1)
                break;
        }
        return p1;
    } 
}

删除链表中重复的结点

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        if (pHead == null) return null;
        int last_val;
        int cur_val = 0;
        ListNode l = new ListNode(0);
        ListNode r = new ListNode(0);
        int cur_num = 0;
        ListNode cur = pHead;
        ListNode last_cur = new ListNode(0);
        last_cur.next = pHead;
        ListNode result = last_cur;
        while (cur != null) {
            if (cur == pHead) {
                l = last_cur;
                cur_val = cur.val;
                cur_num = 1;
            }
            else if (cur.val != cur_val && cur_num != 1) {
                r = last_cur;
                l.next = r.next;
                cur_val = cur.val;
                cur_num = 1;
            }
            else if (cur.val != cur_val) {
                l = last_cur;
                cur_val = cur.val;
                cur_num = 1;
            }
            else if (cur.val == cur_val) {
                cur_num++;
                if (cur.next == null)
                    l.next = null;
            }
            last_cur = cur;
            cur = cur.next;
        }
        return result.next;
    }
}

注意事项

利用哨兵（result）保存链表开始节点，方便最后输出结果，因为pHead可能被删除，最后无法使用。

使用cur遍历，使用last_cur辅助，方便删除节点操作。

使用cur_num和cur_val来记录出现次数和待比较的值，以判断是否需要删除节点操作。

二叉树的下一个结点

题目描述

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if (pNode == null) return null;
        if (pNode.right != null) {
            TreeLinkNode cur = pNode.right;
            while(cur.left != null) {
                cur = cur.left;
            }
            return cur;
        }
        if (pNode.right == null) {
            return Noright(pNode);
        }
        return pNode;
    }
    public TreeLinkNode Noright(TreeLinkNode pNode) {
        if (pNode.next == null) return null;
        else if (pNode.next != null && pNode.next.left == pNode)
            return pNode.next;
        else if (pNode.next != null && pNode.next.right == pNode) {
            return Noright(pNode.next);
        }
        return pNode;
    }
}

对称的二叉树

题目描述

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    boolean isSymmetrical(TreeNode pRoot)
    {
        if (pRoot == null)
            return true;
        return core(pRoot.left,pRoot.right);
    }
    boolean core(TreeNode l,TreeNode r) {
        if (l == null && r == null) 
            return true;
        if (l == null || r == null)
            return false;
        if (l.val != r.val) 
            return false;
        return core(l.left,r.right) && core(l.right,r.left);
    }
}

注意事项

遍历顺序分别为根左右和根右左

按之字形顺序打印二叉树

题目描述

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.util.ArrayList;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        boolean flag = true;
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (pRoot == null) return result;
        ArrayList<Integer> temp = new ArrayList<>();
        temp.add(pRoot.val);
        TreeNode cur = pRoot;
        stack1.push(cur);
        result.add(temp);
        while (!stack1.empty() || !stack2.empty()) {
            temp = new ArrayList<>();
            while (!stack1.empty()){
                cur = stack1.pop();
                if(cur.right != null) {
                    temp.add(cur.right.val);
                    stack2.push(cur.right);
                }
                if (cur.left != null) {
                    temp.add(cur.left.val);
                    stack2.push(cur.left);
                }
            }
            if (temp.size()>0)
            result.add(temp);
            temp = new ArrayList<>();
            while (!stack2.empty()){
                cur = stack2.pop();
                if (cur.left != null) {
                    temp.add(cur.left.val);
                    stack1.push(cur.left);
                }
                if(cur.right != null) {
                    temp.add(cur.right.val);
                    stack1.push(cur.right);
                }
            }
            if (temp.size()>0)
            result.add(temp);
        }
        return result;
    }

}

注意事项

注意判断temp是否为空，不然内部循环不执行的时候也会在结果加入空集合。

把二叉树打印成多行

题目描述

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.util.ArrayList;
import java.util.LinkedList;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        LinkedList<TreeNode> l1 = new LinkedList<>();
        LinkedList<TreeNode> l2 = new LinkedList<>();
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        ArrayList<Integer> temp = new ArrayList<>();
        if (pRoot == null) return result;
        l1.add(pRoot);
        TreeNode cur = pRoot;
        temp.add(pRoot.val);
        result.add(temp);
        while (l1.size()>0 || l2.size()>0 ) {
            temp = new ArrayList<>();
            while (l1.size()>0 ){
                cur = l1.get(0);
                if (cur.left != null) {
                    temp.add(cur.left.val);
                    l2.add(cur.left);
                }
                if(cur.right != null) {
                    temp.add(cur.right.val);
                    l2.add(cur.right);
                }
                l1.remove(0);
            }
            if (temp.size()>0)
            result.add(temp);
            
            temp = new ArrayList<>();
            while (l2.size()>0 ){
                cur = l2.get(0);
                if (cur.left != null) {
                    temp.add(cur.left.val);
                    l1.add(cur.left);
                }
                if(cur.right != null) {
                    temp.add(cur.right.val);
                    l1.add(cur.right);
                }
                l2.remove(0);
            }
            if (temp.size()>0)
            result.add(temp);
        }
        return result;
    }
    
}

注意事项

和上一题代码基本一致，使用LinkedList，实现先进先出。

二叉搜索树的第k个结点

题目描述

给定一颗二叉搜索树，请找出其中从小到大的第k个的结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
import java.util.ArrayList;
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        ArrayList<TreeNode> list = new ArrayList<>();
        if (pRoot == null) return null;
        mid(pRoot,list);
        if (k>list.size() || k <= 0)
            return null;
        int num = k - 1;
        return list.get(num);
    }
    ArrayList<TreeNode> mid(TreeNode root,ArrayList<TreeNode> list) {
        if (root == null) return list;
        
        list = mid(root.left,list);
        list.add(root);
        list = mid(root.right,list);
        return list;
    }

}

注意事项

数据流中的中位数

题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.ArrayList;
public class Solution {
    private ArrayList<Integer> list = new ArrayList<>();
    private ArrayList<Integer> nums = new ArrayList<>();
    public void Insert(Integer num) {
        list.add(num);
        sort(num);
    }

    public Double GetMedian() {
        double result;
        if (list.size() % 2 == 1) 
            result = nums.get((list.size()-1)/2);
        else {
            int r = list.size()/2;
            int l = r - 1;
            result = nums.get(l) + nums.get(r);
            result /= 2;
        }
        return Double.valueOf(result);
    }
    public void sort(Integer num) {
        int temp = num;
        int next = num;
        for (int i = 0; i < nums.size(); i++) {
            if (nums.get(i)<= num)
                continue;
                next = nums.get(i);
                nums.set(i,temp);
                temp = next;
        }
        nums.add(temp);
    }
}

注意事项

增加一个排序好的序列nums