【算法入门与九月打卡】—— 第五天

双指针

867. 链表的中间结点

可以通过 快慢指针 来完成，快指针每次走两步，慢指针每次走一步，当快指针走到尽头，慢指针就到达了链表的中点。

重点在于临界条件的处理，快指针最后有两种状态：

指向链表的最后一个元素【链表元素为奇数个】
指向空 【链表元素为偶数个】

所以临界条件应该为 fast != null && fast.next != null

class Solution {
    public ListNode middleNode(ListNode head) {
        //设置快慢指针
        ListNode fast = head;
        ListNode slow = head;
        //遍历链表
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //返回结果
        return slow;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

19. 删除链表的倒数第N个结点

遍历一次链表，统计链表的结点个数，判断是否要删除第一个结点，是则直接返回链表的第二个结点，否则就遍历寻找待删除结点的前驱结点，删除后返回链表头结点

要注意，此题链表的头结点指的是链表的第一个结点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //记录链表结点的个数
        int count = 0;
        ListNode p = head;
        while(p != null){
            count++;
            p = p.next;
        }
        //待删除的结点为第一个结点
        if(count == n){
            return head.next;
        }
        //遍历到待删除结点的前驱结点
        ListNode pre = head;
        for(int i = 0; i < count - n - 1; i++){
            pre = pre.next;
        }
        //删除结点
        pre.next = pre.next.next;
        //返回结果
        return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

序列化

652. 寻找重复的子树

将整个二叉树的所有子树序列化，如果出现重复序列就添加到集合中

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //记录每个子树序列
    Map<String, TreeNode> map = new HashMap<String, TreeNode>();
    //记录重复出现的序列
    Set<TreeNode> set = new HashSet<TreeNode>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        //只有一个结点
        if(root.left == null && root.right == null){
            return new ArrayList();
        }
        //深搜遍历二叉树
        dfs(root);
        //返回重复序列的集合
        return new LinkedList<TreeNode>(set);
        
    }
    public String dfs(TreeNode root){
        //当前结点为空
        if(root == null){
            return "";
        }

        //将当前结点与其子树序列化
        StringBuilder sb = new StringBuilder();
        sb.append(root.val);
        sb.append("(");
        sb.append(dfs(root.left));
        sb.append(")()");
        sb.append(dfs(root.right));
        sb.append(")");

        //转化为String类型
        String s = sb.toString();

        //当前序列已经存在了
        if(map.containsKey(s)){
            set.add(map.get(s));
        }else{
            //添加到哈希表中
            map.put(s, root);
        }
        //返回上一个结点的子序列
        return s;
    }
}
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