剑指Offer_25

发表于 2017-12-03 | 分类于剑指Offer

题目

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

解题思路

a. 复制链表的节点
b. 将复制的节点random指向正确的位置
c. 拆分成两个链表……题目没有交代清楚

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;
    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if(pHead == null){
            return null;
        }
        
        RandomListNode p = pHead;
        while(p != null){
            RandomListNode copy = new RandomListNode(p.label);
            copy.next = p.next;
            p.next = copy;
            
            p = p.next.next;
        }
        
        p = pHead;
        while(p != null){
            if(p.random != null){
                p.next.random = p.random.next;
            }
            p = p.next.next;
        }
        
        RandomListNode newList = pHead.next;
        RandomListNode pList = newList;
        p = pHead;
        while(p != null){
            p.next = p.next.next;
            
            //指针节点的位置很容混淆..
            if(pList.next != null){
                pList.next = pList.next.next;
            }
            p = p.next;
            pList = pList.next;
        }
        return newList;
        
    }
}

剑指Offer_24

发表于 2017-12-03 | 分类于剑指Offer

题目

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

解题思路

从树的根点开始，直至叶节点的路径和为target，打印路径。

采用带记忆的深度优先搜索。

import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    private ArrayList<ArrayList<Integer>> AA = new ArrayList<>();
    private ArrayList<Integer> A = new ArrayList<>();
    
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null){
            return AA;
        }
        //将被试探的节点加入
        A.add(root.val);
        target -= root.val;
        if(target == 0 && root.left == null && root.right == null){
            AA.add(new ArrayList<Integer>(A));
        }
        //试探节点的左右子树节点
        FindPath(root.left, target);
        FindPath(root.right, target);
        
        //该节点被试探完，就从记忆数组中丢弃
        A.remove(A.size()-1);
        
        return AA;
    }
}

剑指Offer_23

发表于 2017-12-03 | 分类于剑指Offer

题目

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

解题思路

解法一：

非递归版本

对于二叉搜索树的节点来说，它总是大于左子树所有的节点，小于右子树所有的节点。这样就可以一一检查每个节点是否符合条件。

因为数组是后续遍历的结果，所以各个子树的根节点在数组末尾。

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length == 0){
            return false;
        }
        int N = sequence.length-1;
        int i = 0;
        while(N != 0){
        	//N节点左子树小于根节点 以及 大于根节点 
            while(i < N && sequence[i++] < sequence[N]){}
            while(i < N && sequence[i++] > sequence[N]){}
            if(i != N){
                return false;
            }
            i = 0;
            --N;
        }
        return true;
    }
}

解法二：

递归版本

public class Solution {
    private boolean helper(int []sequence, int N){
        if(N == 0){
            return true;
        }
        int i = 0;
        while(i < N && sequence[i++] < sequence[N]){}
        while(i < N && sequence[i++] > sequence[N]){}
        if(i != N){
            return false;
        }
        return helper(sequence, --N);
    }
    
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length == 0){
            return false;
        }
        return helper(sequence, sequence.length-1);
    }
    
}

剑指Offer_22

发表于 2017-12-03 | 分类于剑指Offer

题目

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

解题思路

层序遍历二叉树

将ArrayList换成LinkedList效率会高一点……

import java.util.ArrayList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> ret = new ArrayList<>();
        ArrayList<TreeNode> nodeList = new ArrayList<>();
        if(root == null){
            return ret;
        }
        nodeList.add(root);
        while(!nodeList.isEmpty()){
            TreeNode node = nodeList.get(0);
            nodeList.remove(0);
            ret.add(node.val);
            if(node.left != null){
                nodeList.add(node.left);
            }
            if(node.right != null){
                nodeList.add(node.right);
            }
        }
        return ret;
    }
}

剑指Offer_21

发表于 2017-12-03 | 分类于剑指Offer

题目

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

解题思路

输入的数字均不相等.

import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int index = 0;
        
        for(int i = 0; i < pushA.length; ++i){
            
            //入栈的顺序就是pushA数组
            stack.push(pushA[i]);
            
            //出栈的顺序就是popA数组
            while(!stack.isEmpty() && stack.peek() == popA[index]){
                ++index;
                stack.pop();
            }
        }
        
        //栈内元素全被弹出才是成功的
        return stack.isEmpty();
    }
}

剑指Offer_20

发表于 2017-12-03 | 分类于剑指Offer

题目

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

解题思路

一道，感觉怪怪的题目

import java.util.Stack;
public class Solution {
	Stack<Integer> dataStack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();
    
    public void push(int node) {
        dataStack.push(node);
        if(minStack.isEmpty()){
			minStack.push(node);
        }
        else{
			if(node <= minStack.peek()){
				minStack.push(node);
            }
        }
    }
    
    public void pop() {
        if(!dataStack.isEmpty()){
            if(minStack.peek() == dataStack.pop()){
                minStack.pop();
            }
        }
    }
    
    public int top() {
        if(!dataStack.isEmpty()){
            return dataStack.pop();
        }
        return -1;
    }
    
    public int min() {
        if(!minStack.isEmpty()){
            return minStack.peek();
        }
        else{
            
        }
        return -1;
    }
}

剑指Offer_19

发表于 2017-12-03 | 分类于剑指Offer

题目

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

解题思路

顺时针打印数组，注意top, bottom, left 和 right 的边界

退出条件为 top == bottom 或者 left = = right

可能会有m或者n为奇数的时候，可能会有如下的数未遍历
输入矩阵有m x n矩阵，
a. 当 m == n 时，最后只剩中间的一个数
b. 当 m > n 时，最后只剩中间一行的部分
c. 当 m < n 时，最后只剩之间一列的部分

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
       ArrayList<Integer> integers = new ArrayList<>();
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return null;
        }
        int top = 0;
        int bottom = matrix.length - 1;
        int left = 0;
        int right = matrix[0].length - 1;
        while(top < bottom && left < right){
            for(int i = left; i <= right; ++i){
                integers.add(matrix[top][i]);
            }
            for(int i = top+1; i <= bottom; ++i){
                integers.add(matrix[i][right]);
            }
            for(int i = right-1; i >= left; --i){
                integers.add(matrix[bottom][i]);
            }
            for(int i = bottom-1; i >= top+1; --i){
                integers.add(matrix[i][left]);
            }
            ++top;
            --bottom;
            ++left;
            --right;
        }
        if(top == bottom && left == right){
            integers.add(matrix[left][top]);
        }
        if(top == bottom && left != right){
            for(int i = left; i <= right; ++i){
                integers.add(matrix[top][i]);
            }
        }
        
        if(top != bottom && left == right){
            for(int i = top; i <= bottom; ++i){
                integers.add(matrix[i][left]);
            }
        }
        
        return  integers;
    
    }
}

剑指Offer_18

发表于 2017-12-02 | 分类于剑指Offer

题目

操作给定的二叉树，将其变换为源二叉树的镜像。

解题思路

二叉树的镜像定义：源二叉树 
    	    8
    	   /  \
    	  6   10
    	 / \  / \
    	5  7 9 11
    	镜像二叉树
    	    8
    	   /  \
    	  10   6
    	 / \  / \
    	11 9 7  5

解法一：

递归实现

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public void Mirror(TreeNode root) {
        TreeNode aux = null;
        if(root != null){
            aux = root.left;
            root.left = root.right;
            root.right = aux;
            
            Mirror(root.left);
            Mirror(root.right);
        }
    }
}

解法二：

非递归实现

剑指Offer_17

发表于 2017-12-02 | 分类于剑指Offer

题目

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

解题思路

判断树root2是不是root1的子树

a. 在主函数HasSubtree中，先设置了而标志位ret为false，当从辅助函数isSubtree返回true之后，就退出递归，否则，继续递归。如果在主函数中输入的root1和root2其一为null时，程序退出。

b. 进入辅助函数isSubtree的条件是，当前两个树的节点值是一样的。

c. ret返回true的条件是，root2的每个节点值都等于对应的root1的节点值，直到root2为null。

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    private boolean isSubtree(TreeNode root1, TreeNode root2){
        if(root2 == null){
            return true;
        }
        //当root2 != null 而 root1 == null 时，肯定不是子树
        if(root1 == null){
            return false;
        }
        if(root1.val != root2.val){
            return false;
        }
        //如果上述条件都通过，递归判断是否子树
        return isSubtree(root1.left, root2.left) && isSubtree(root1.right, root2.right);
    }
    
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        boolean ret = false;
        if(root1 != null && root2 != null){
            if(root1.val == root2.val){
                ret = isSubtree(root1, root2);
            }
            if(ret == false){
                ret = HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
            }
        }
        return ret;
    }
    
}

剑指Offer_16

发表于 2017-12-01 | 分类于剑指Offer

题目

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

解题思路

就简单的拼凑两条链表，注意一些代码的细节，详见代码内注释
注意因为Java的对象都是引用类型，当一个实例对象引用了null，不要试图操作如下代码

ListNode header = new ListNode(-1);
ListNode node1 = new ListNode(1);
ListNode cur = header.next;	//此时的cur引用的是null
header.next = node1;		//header.next 与 cur 并无关系
System.out.println(cur.val);	//因此会抛出异常javaNullPointException

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        
        ListNode header = new ListNode(-1);
        ListNode cur = header;	//将cur指向header节点
        
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                cur.next = list1;
                list1 = list1.next;
            }
            else{
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        
        //拼接可能出现未遍历的剩余节点
        cur.next = (list1 == null) ? list2 : list1;
        
        return header.next;
    }
}