[数据结构与算法]剑指offer第五天

剑指 Offer 22. 链表中倒数第k个节点

思路：

双指针:让快指针先走k步，这样快慢指针一起走，快指针走到尾部的时候，慢指针刚好走到了n-k处

代码：

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode slow = head, fast = head;
        for(int i = 0; i < k; i++){
            fast = fast.next;
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

剑指 Offer 24. 反转链表

思路：

先定义一个空节点，将当前节点指向头节点，进入循环体，将当前节点的下一个节点存起来，然后将当前节点的尾部指向空节点，将空节点移向当前节点，然后将存起来的节点给当前节点，最后返回前节点

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null)
            return null;
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

剑指 Offer 25. 合并两个排序的链表

1.判断两个链表是不是为空，其中一个为空则返回另外一个

2.新建一个临时节点，用于添加元素

3.再定义一个指向合并后的尾节点，初始值为新建的头节点

4.合并，最小就给新链表

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        ListNode root = new ListNode();
        ListNode pointer = root;
        while(l1!=null && l2!=null){//都不为空则进行
            if(l1.val<l2.val){
                pointer.next = l1;//1小于2，所以将尾指针指向1
                l1= l1.next;
            }else{
                pointer.next = l2;
                l2 = l2.next;
            }
            pointer = pointer.next;//将指针移动到合并后的链表的末尾
        }
        if(l1!=null){
            pointer.next = l1;//如果第一个链表的元素未处理完，则将尾指针直接指向1
        }
        if(l2!=null){
            pointer.next = l2;
        }
        return root.next;//最后返回根节点

    }

剑指 Offer 26. 树的子结构

采用递归的方法

先序遍历树A中的每个节点（对于issubstructure）

判断树A中的每个节点为根节点的子树是否包含树B(recur)

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }
    boolean recur(TreeNode A, TreeNode B) {
        if(B == null) return true;
        if(A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}

剑指 Offer 27. 二叉树的镜像

递归解析：

1. 终止条件： 当节点 root为空时（即越过叶节点），则返回 null；
2. 递推工作：
   初始化节点 tmp ，用于暂存 root 的左子节点；
   开启递归 右子节点 mirrorTree(root.right)，并将返回值作为 root的 左子节点 。
   开启递归 左子节点 mirrorTree(tmp)，并将返回值作为 root 的 右子节点 。
3. 返回值： 返回当前节点 root；

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) 
            return null;
        TreeNode tmp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(tmp);
        return root;
    }
}

剑指 Offer 28. 对称的二叉树

和上一题差不多

递归解析：

1. 终止条件
   • 当 L和 R 同时越过叶节点： 此树从顶至底的节点都对称，因此返回true ；
   • 当 L 或 R 中只有一个越过叶节点： 此树不对称，因此返回 false ；
   • 当节点 L值 节点 R 值： 此树不对称，因此返回false ；
2. 终止工作
   • 判断两节点 L.left 和 R.right 是否对称，即 recur(L.left, R.right) ；
     判断两节点 L.right和 R.left是否对称，即 recur(L.right, R.left) ；

    public boolean isSymmetric(TreeNode root) {
        return root == null?true:recur(root.left,root.right);

    }
    boolean recur(TreeNode L,TreeNode R){
        if(L==null && R==null)
            return true;
        if(L==null || R == null || L.val!=R.val)
            return false;
        return recur(L.left,R.right) && recur(L.right,R.left);
    }

剑指 Offer 29. 顺时针打印矩阵

public int[] spiralOrder(int[][] matrix) {
    if(matrix.length==0){
        return new int[0];
    }
    int l=0,r=matrix[0].length-1;
    int t=0,b=matrix.length-1;
    int x=0;
    int[] res = new int[(r+1)*(b+1)];
    while(true){
        for(int i = l;i<=r;i++) res[x++] = matrix[t][i];
        if(++t>b) break;
        for(int i = t;i<=b;i++) res[x++] = matrix[i][r];
        if(--r<l) break; 
        for(int i = r;i>=l;i--) res[x++] = matrix[b][i];
        if(--b<t) break; 
        for(int i = b;i>=t;i--) res[x++] = matrix[i][l];
        if(++l>r) break; 
    }
    return res;
}

剑指 Offer 30. 包含min函数的栈

辅助栈

数据栈 A： 栈 A用于存储所有元素，保证入栈 push() 函数、出栈 pop() 函数、获取栈顶 top() 函数的正常逻辑

辅助栈 B： 栈 B中存储栈 A 中所有 非严格降序 的元素，则栈 A中的最小元素始终对应栈 B 的栈顶元素，即 min() 函数只需返回栈 B 的栈顶元素即可。

如果是添加的话，A添加了一个元素，B不为空且这个元素小于B的顶部元素，那么B就要添加

如果是取最小值出来的话，就去取B的顶部元素

class MinStack {

    /** initialize your data structure here. */
    Stack<Integer> A,B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();

    }
    
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >= x)
            B.add(x);
    }
    
    public void pop() {
        if(A.pop().equals(B.peek()))
            B.pop();
    }
    
    public int top() {
        return A.peek();
    }
    
    public int min() {
        return B.peek();
    }
}

剑指 Offer 31. 栈的压入、弹出序列

辅助栈

初始化：辅助栈，弹出序列的索引

遍历压栈序列：

1. 各个元素遍历依次入栈
2. 循环出栈，如果栈顶的元素==弹出序列元素，那么执行出栈，此时弹出序列自增

返回值：如果栈为空，那么弹出序列是合法的作出判断

public boolean validateStackSequences(int[] pushed, int[] popped) {
    Stack<Integer> stack = new Stack<Integer>();
    for(int i = 0,j = 0;i<pushed.length;i++){
        stack.push(pushed[i]);
        while(stack.size()>0 && stack.peek()==popped[j]){
            stack.pop();
            j++;
        }
    }
    return stack.size()==0;
}

剑指 Offer 32 - I. 从上到下打印二叉树

特例处理：当树的根节点为空，则返回空列表

初始化：结果列表、包含根节点的队列

BFS广度优先循环：当队列为空时跳出

1. 出队：队首元素出队
2. 打印：将值添加到列表尾部
3. 添加子节点：如果队首的左右子节点不为空，则将左右子节点加入队列

返回值：打印列表即可

public int[] levelOrder(TreeNode root) {
        if(root==null)
            return new int[0];
        
            Queue<TreeNode> list = new LinkedList<>();
            list.add(root);
            ArrayList<Integer> ans = new ArrayList<>();
            
            while(!list.isEmpty()){
               TreeNode curnode = list.poll();
                // System.out.print(curnode.val+" ");
                ans.add(curnode.val);
                if(curnode.left !=null){
                    list.add(curnode.left);
                }
                if(curnode.right != null){
                    list.add(curnode.right);
                }
            }
                int[] res = new int[ans.size()];
                for(int i = 0;i<ans.size();i++){
                    res[i] = ans.get(i);
                }
                return res;
}