剑指offer035复杂链表的复制

Posted on 2020-02-07 Edited on 2020-02-11 In 剑指offer Valine:

Problem:

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

Intuition:

第一反应是这道题需要做吗？不就从头到尾复制一遍就完事了吗？但是我们要注意链表里面的节点需要指向下一个节点，那这里就出现问题，不能直接复制了。因为你肯定不能直接指向原链表的节点进行复制。

Solution:

public class CodingInterview_035 {

    public class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;

        RandomListNode(int label) {
            this.label = label;
        }
    }

    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null) {
            return null;
        }

        RandomListNode currentNode = pHead;
        //1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
        while(currentNode != null){
            RandomListNode cloneNode = new RandomListNode(currentNode.label);
            RandomListNode nextNode = currentNode.next;
            currentNode.next = cloneNode;
            cloneNode.next = nextNode;
            currentNode = nextNode;
        }

        currentNode = pHead;
        //2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;这里选择A.random.next的原因是本来应该指向A.random,但是经过第一次操作后
        //A.random.next对应的就是复制后链表中的A.random.
        while(currentNode != null) {
            currentNode.next.random = currentNode.random==null?null:currentNode.random.next;
            currentNode = currentNode.next.next;
        }

        //3、拆分链表，将链表拆分为原链表和复制后的链表
        currentNode = pHead;
        RandomListNode pCloneHead = pHead.next;
        while(currentNode != null) {
            RandomListNode cloneNode = currentNode.next;
            currentNode.next = cloneNode.next;
            //因为这里需要操作.next.next,所以需要判断null,否则会抛异常
            cloneNode.next = cloneNode.next==null?null:cloneNode.next.next;
            currentNode = currentNode.next;
        }

        return pCloneHead;
    }
}

剑指offer034二叉树中和为某一值的路径

Posted on 2020-02-04 Edited on 2020-02-11 In 剑指offer Valine:

Problem:

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

Intuition:

这个题目是个典型的递归结构，本质上面是一个深度搜索的问题。我们看递归的问题要明白，递归问题的返回其实是返回到调用递归函数的下面一行代码。比如我们访问完左子树，return之后对应的下面的代码就是返回到backtracking(node.right,target,path).那么这个时候我们检查递归用到的参数，就会发现我们需要删除之前添加的节点才能够保证接下来的代码正常运行。

Solution:

public class CodingInterview_034 {

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val){
            this.val=val;
        }
    }

    private ArrayList<ArrayList<Integer>> ret = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        backtracking(root, target, new ArrayList<>());
        return ret;
    }

    private void backtracking(TreeNode node, int target, ArrayList<Integer> path) {
        if (node == null)
            return;
        path.add(node.val);
        target -= node.val;
        //路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。所以要判断叶子节点的左右节点是否为空
        if (target == 0 && node.left == null && node.right == null) {
            ret.add(new ArrayList<>(path));
        } else {
            backtracking(node.left, target, path);
            backtracking(node.right, target, path);
        }
        //下面这一行是深度优先搜索的关键，我们注意到上面有一个path.add(node.val),现在这个节点检查完之后就应该删除这个节点。
        path.remove(path.size() - 1);
    }
}

剑指offer033二叉搜索树的后序遍历序列

Posted on 2020-02-03 In 剑指offer Valine:

Problem:

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

Intuition:

已知条件：后序序列最后一个值为root；二叉搜索树左子树值都比root小，右子树值都比root大。
1、确定root；
2、遍历序列（除去root结点），找到第一个大于root的位置，则该位置左边为左子树，右边为右子树；
3、遍历右子树，若发现有小于root的值，则直接返回false；
4、分别判断左子树和右子树是否仍是二叉搜索树（即递归步骤1、2、3）。

Solution:

public class CodingInterview_033 {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0){
            return false;
        }
        if(sequence.length == 1){
            return true;
        }

        return judge(sequence,0,sequence.length-1);
    }
    public boolean judge(int[] a,int start,int end){
        if(start >= end){
            return true;
        }
        int i = start;
        while(a[i] < a[end]){
            ++i;
        }
        for(int j=i;j<end;j++){
            if(a[j] < a[end]){
                return false;
            }
        }
        return judge(a,start,i-1) && judge(a,i,end-1);
    }
}

剑指offer032.3按之字形顺序打印二叉树

Posted on 2020-02-03 In 剑指offer Valine:

Problem:

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

Intuition:

在上一题的基础上加一个reverse变量每打印一行就更新就行了。

Solution:

public class CodingInterview_032_2 {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val){
            this.val=val;
        }
    }

    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        boolean reverse = false;
        while (!queue.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            int cnt = queue.size();
            while (cnt-- > 0) {
                TreeNode node = queue.poll();
                if (node == null)
                    continue;
                list.add(node.val);
                queue.add(node.left);
                queue.add(node.right);
            }
            if (reverse)
                Collections.reverse(list);
            reverse = !reverse;
            if (list.size() != 0)
                ret.add(list);
        }
        return ret;
    }

}

剑指offer032.2把二叉树打印成多行

Posted on 2020-02-03 In 剑指offer Valine:

Problem:

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

Intuition:

要打印多行，只用按行整理出list就行了。

Solution:

public class CodingInterview_032_2 {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val){
            this.val=val;
        }
    }

    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        while (!queue.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            int cnt = queue.size();
            while (cnt-- > 0) {
                //poll是删除队列的第一个元素并且返回该元素
                TreeNode node = queue.poll();
                if (node == null)
                    continue;
                list.add(node.val);
                queue.add(node.left);
                queue.add(node.right);
            }
            if (list.size() != 0)
                ret.add(list);
        }
        return ret;
    }

}

剑指offer032.1从上往下打印二叉树

Posted on 2020-02-03 In 剑指offer Valine:

Problem:

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

Intuition:

要实现按层打印，只需要将左右节点存到一个队列里面，按顺序打印即可

Solution:

public class CodingInterview_032 {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val){
            this.val=val;
        }
    }


    public class Solution {
        public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
            ArrayList<Integer> list = new ArrayList<>();
            ArrayList<TreeNode> queue = new ArrayList<>();
            if (root == null) {
                return list;
            }
            queue.add(root);
            while (queue.size() != 0) {
                TreeNode temp = queue.remove(0);
                if (temp.left != null){
                    queue.add(temp.left);
                }
                if (temp.right != null) {
                    queue.add(temp.right);
                }
                list.add(temp.val);
            }
            return list;
        }
    }
}

剑指offer031栈的压入弹出序列

Posted on 2020-02-03 In 剑指offer Valine:

Problem:

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

Intuition:

我们用一个栈s来模拟整个进栈出栈的过程，注意题干里面有说过进栈的所有元素都不一样，这个是很重要的前提。

Solution:

public class CodingInterview_031 {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA.length==0||popA.length==0||pushA.length!=popA.length){
            return false;
        }
        Stack<Integer> s=new Stack<Integer>();
        //用于表示弹出序列的位置
        int popIndex=0;
        for(int i=0;i<pushA.length;i++){
            s.push(pushA[i]);
            //如果栈不为空，且栈顶元素等于弹出序列
            while(!s.empty()&&s.peek()==popA[popIndex]){
                //出栈
                s.pop();
                //弹出序列向后一位
                popIndex++;
            }
        }
        return s.empty();
    }
}

剑指offer029包含min函数的栈

Posted on 2020-02-03 In 剑指offer Valine:

Problem:

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

Intuition:

这个题目我们要稍微注意一下，找出最小元素的操作可能会进行多次，不是进行一次就结束了。这就意味着我们仅仅用一个整数存最小元素的方案是行不通的，我们要某种数据结构将所有栈中的元素按大小顺序进行保存。

Solution:

public class CodingInterview_029 {
    private Stack<Integer> dataStack=new Stack<>();
    private Stack<Integer> minStack=new Stack<>();
    public void push(int node){
        dataStack.push(node);
        if(minStack.isEmpty()||node<minStack.peek()){
            minStack.push(node);
        }
    }

    public void pop(){
        int dataTop=dataStack.peek();
        int minTop=minStack.peek();
        dataStack.pop();
        if(dataTop==minTop){
            minStack.pop();
        }
    }

    public int top(){
        return dataStack.peek();
    }

    public int min(){
        return minStack.peek();
    }
}

剑指offer028顺时针打印矩阵

Posted on 2020-02-02 In 剑指offer Valine:

Problem:

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 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.

Intuition:

这一题总体思路很好定。要顺时针打印矩阵，我们不难发现每次打印的都是矩阵的外框，这个外框每打印一次就往里缩一圈。那么我们用r1,r2来表示外框的行数范围，c1,c2来表示外框的列数范围，然后顺时针进行打印就可以了。需要注意的是特殊情况。如果行数为奇数，那么横着打印的部分在最后一次只有从左到右的一次，而没有从右到左的一次。如果列数为奇数，那么竖着打印的部分在最后一次只有从上到下的那一次。

Solution:

public class CodingInterview_028 {
    public ArrayList<Integer> printMatrix(int[][] matrix) {
        ArrayList<Integer> ret = new ArrayList<>();
        int r1 = 0, r2 = matrix.length - 1, c1 = 0, c2 = matrix[0].length - 1;
        while (r1 <= r2 && c1 <= c2) {
            for (int i = c1; i <= c2; i++)
                ret.add(matrix[r1][i]);
            for (int i = r1 + 1; i <= r2; i++)
                ret.add(matrix[i][c2]);
            if (r1 != r2)
                for (int i = c2 - 1; i >= c1; i--)
                    ret.add(matrix[r2][i]);
            if (c1 != c2)
                for (int i = r2 - 1; i > r1; i--)
                    ret.add(matrix[i][c1]);
            r1++; r2--; c1++; c2--;
        }
        return ret;
    }
}

剑指offer027二叉树的镜像

Posted on 2020-02-02 In 剑指offer Valine:

Problem:

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

Intuition:

典型的递归问题，轻松搞定。

Solution:

public class CodingInterview_027 {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val){
            this.val=val;
        }
    }
    public void Mirror(TreeNode root) {
        if (root == null)
            return;
        swap(root);
        Mirror(root.left);
        Mirror(root.right);
    }

    private void swap(TreeNode root) {
        TreeNode t = root.left;
        root.left = root.right;
        root.right = t;
    }
}