剑指Offer_65

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

题目

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如 a b c e s f c s a d e e 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

解题思路

回溯法

public class Solution {
    public boolean hasPathHelper(char []matrix, int rows, int cols, char []str, int k, boolean []isVisited, int i, int j){
        int pos = i * cols + j;
        if(i < 0 || i >= rows || j < 0 || j >= cols || isVisited[pos] || matrix[pos] != str[k]){
            return false;
        }
        if(k == str.length -1){
            return true;
        }
        ++k;
        isVisited[pos] = true;
        if(    hasPathHelper(matrix, rows, cols, str, k, isVisited, i+1, j) 
            || hasPathHelper(matrix, rows, cols, str, k, isVisited, i-1, j)
            || hasPathHelper(matrix, rows, cols, str, k, isVisited, i, j-1)
            || hasPathHelper(matrix, rows, cols, str, k, isVisited, i, j+1)){
            
            return true; 
        }
        isVisited[pos] = false;
        
        return false;
    }
    
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
    	boolean []isVisited = new boolean[rows * cols];
        for(int i = 0; i < rows; ++i){
            for(int j = 0; j < cols; ++j){
                if(hasPathHelper(matrix, rows, cols, str, 0, isVisited, i, j)){
                    return true;
                }
            }
        }
        return false;
    }
}

剑指Offer_64

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

题目

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

解题思路

使用一个双端队列，队列第一个位置保存当前窗口最大值的下标，每当窗口滑动一次

a. 新增加的值从队尾开始比较，把所有比他小的值丢掉

b. 判断当前最大值是否过期

import java.util.ArrayList;
import java.util.LinkedList;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> A = new ArrayList<>();
        LinkedList<Integer> maxIndexList = new LinkedList<>();
        
        if(num == null || num.length == 0 || size == 0){
            return A;
        }
        
        for(int i = 0; i < num.length; ++i){
            while(!maxIndexList.isEmpty() && num[maxIndexList.getLast()] < num[i]){
                maxIndexList.removeLast();
            }
            if(!maxIndexList.isEmpty() && (i - maxIndexList.getFirst()) >= size){
                maxIndexList.pollFirst();
            }
            maxIndexList.addLast(i);
            if(i+1 >= size){
                A.add(num[maxIndexList.getFirst()]);
            }
        }
        return A;
    }
}

剑指Offer_63

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

题目

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

解题思路

a. 最小堆放大数，最大堆放大数，那么两个堆的堆顶就是逼近中位数的数

b. count计数，当两堆数目一样时候，优先放在最小堆

c. 插入最大、最小堆的时候，先到对方的堆中换取合适的值

import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
	private int count = 0;
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>(){
        @Override
        public int compare(Integer o1, Integer o2){
            return o2 - o1;
        }
    });
    
    public void Insert(Integer num) {
    
    	//往最小堆插入数据，num进入最大堆，
    	//取出最大堆现在最大的数据
    	//插入最小堆
    	if(count % 2 == 0){
            maxHeap.offer(num);
            int maxHeapMax = maxHeap.poll();
            minHeap.offer(maxHeapMax);
        }
        //往最大堆插入数据，num进入最小堆
        //取出最小堆现在最大的数据
        //插入最小堆
        else{
            minHeap.offer(num);
            int minHeapMin = minHeap.poll();
            maxHeap.offer(minHeapMin);
        }
        ++count;
    }
    public Double GetMedian() {
        if(count % 2 == 0){
            return (minHeap.peek() + maxHeap.peek()) / 2.0;
        }
        else{
            return (double)minHeap.peek();
        }
    }
}

剑指Offer_62

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

题目

给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。

解题思路

中序遍历的结果就是二叉搜索树排序之后的结果。

解法一：

递归版本

//防止返回null
if(node != null){
	return node;
}

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    private int index = 0;
    
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot != null){
            //首先程序递归到最左子树节点
            TreeNode node = KthNode(pRoot.left, k);
            if(node != null){
                return node;
            }
            //从最左子树节点开始计算
            ++index;
            if(k == index){
                return pRoot;
            }
            //弹出栈的节点访问它的右子树
            node = KthNode(pRoot.right, k);
            if(node != null){
                return node;
            }
        }
        return null;
    }
}

解法二：

非递归版本

import java.util.Stack;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot == null || k <= 0){
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        
        do{
        	//每次循环先 先将非空pRoot入栈
            if(pRoot != null){
                stack.push(pRoot);
                pRoot = pRoot.left;
            }
            else{
            	//出栈开始遍历，--k
                pRoot = stack.pop();
                if(--k == 0){
                    return pRoot;
                }
                //上面是将节点的左子树入栈
                //如果节点的右子树非空，那么就有机会入栈
                pRoot = pRoot.right;
            }
        }while(pRoot != null || !stack.isEmpty());
        
        return null;
    }
}

剑指Offer_61

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

题目

请实现两个函数，分别用来序列化和反序列化二叉树

解题思路

序列化二叉树：

前序遍历二叉树

反序列化二叉树：

根据“＃” 的值判断是否应该构造节点

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    
    String Serialize(TreeNode root) {
        StringBuffer sb = new StringBuffer();
        if(root == null){
            sb.append("#,");
            return sb.toString();
        }
        sb.append(root.val + ",");
        sb.append(Serialize(root.left));
  		sb.append(Serialize(root.right));
        
        return sb.toString();
    }
    
    private int index;
    private TreeNode DeserializeHelper(String []strings){
        ++index;
        TreeNode node = null;
        if(!strings[index].equals("#")){
            node = new TreeNode(Integer.valueOf(strings[index]));
            node.left = DeserializeHelper(strings);
            node.right = DeserializeHelper(strings);
        }
        return node;
    }
    
    TreeNode Deserialize(String str) {
        index = -1;
        String []strings = str.split(",");
        return DeserializeHelper(strings);
  	}
    
}

剑指Offer_60

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

题目

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

解题思路

二叉树层序遍历

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) {
    	ArrayList<ArrayList<Integer>> AA = new ArrayList<>();
        if(pRoot == null){
            return AA;
        }
        LinkedList<TreeNode> nodeList = new LinkedList<>();
        nodeList.add(pRoot);
        while(!nodeList.isEmpty()){
            ArrayList<Integer> A = new ArrayList<>();
            
            int size = nodeList.size();
            for(int i = 0; i < size; ++i){
            	TreeNode node = nodeList.removeFirst();
                A.add(node.val);
                if(node.left != null){
                    nodeList.addLast(node.left);
                }
                if(node.right != null){
                    nodeList.addLast(node.right);
                }
            }
            AA.add(A);
        }
        return AA;
    }
    
}

剑指Offer_59

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

题目

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

解题思路

解法一：

简洁版本，在数据大的时候效率并不高，因为偶数层的AarrayList总是操作Collections.revers(A)

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Collections;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
		ArrayList<ArrayList<Integer>> AA = new ArrayList<>();
        if(pRoot == null){
            return AA;
        }
        LinkedList<TreeNode> nodeList = new LinkedList<>();
        nodeList.add(pRoot);
        boolean isEven = false;
        while(!nodeList.isEmpty()){
            ArrayList<Integer> A = new ArrayList<>();
           
           //这里的size要保存，nodeList的size是动态的 
            int size = nodeList.size();
            for(int i = 0; i < size; ++i){
                TreeNode node = nodeList.removeFirst();
                A. add(node.val);
                if(node.left != null){
                    nodeList.add(node.left);
                }
                if(node.right != null){
                    nodeList.add(node.right);
                }
            }
            //偶数层的元素逆序
            if(isEven){
                Collections.reverse(A);
            }
            isEven = !isEven;
            AA.add(A);
        }
        return AA;
    }
}

解法二：

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 {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
		ArrayList<ArrayList<Integer>> AA = new ArrayList<>();
        if (pRoot == null) {
            return AA;
        }
        LinkedList<TreeNode> oddList = new LinkedList<>();
        LinkedList<TreeNode> evenList = new LinkedList<>();
        oddList.add(pRoot);
        boolean isEven = false;
        while(!oddList.isEmpty() || !evenList.isEmpty()){
            ArrayList<Integer> A = new ArrayList<>();
            if(isEven){
                while (!evenList.isEmpty()){
                    TreeNode node = evenList.removeFirst();
                    A.add(node.val);
                    if(node.right != null){
                        oddList.addFirst(node.right);
                    }
                    if(node.left != null){
                        oddList.addFirst(node.left);
                    }
                }
            }
            else{
                while(!oddList.isEmpty()){
                    TreeNode node = oddList.removeFirst();
                    A.add(node.val);
                    if(node.left != null){
                        evenList.addFirst(node.left);
                    }
                    if(node.right != null){
                        evenList.addFirst(node.right);
                    }
                }
            }
            isEven = !isEven;
            AA.add(A);
        }
        return AA;
    }
}

剑指Offer_58

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

题目

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

解题思路

解法一：

递归版本

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

解法二：

非递归版本

剑指Offer_57

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

题目

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

解题思路

二叉树的中序遍历要熟悉

点击加载

该二叉树的中序遍历为：
G D H B E A K C I J F

a. 如果该节点有右子树，那么找该右子树的最左子树节点。

比如输入的节点为C，它有右子树，那么就找其右子树的最左节点 I

b. 如果没有右子树，节点A的父节点的左子树等于该节点A，那么节点A的父节点就是下一节点，否则继续向上搜索

比如输入的节点为H，它的父亲节的左子树不是它本身，那么就要向上搜索，
令pNode = pNode.next，此时PNode = D，它的父节点B就是下一节点

/*
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 pNode;
        }
        if(pNode.right != null){
			pNode = pNode.right;
            while(pNode.left != null){
                pNode = pNode.left;
            }
            return pNode;
        }
        while(pNode.next != null){
            if(pNode.next.left == pNode){
                return pNode.next;
            }
            pNode = pNode.next;
        }
        return null;
    }
}

剑指Offer_56

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

题目

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

解题思路

/*
 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;
        }
        
        ListNode header = new ListNode(-1);
        header.next = pHead;
        
        ListNode pre = header;
        ListNode cur = pHead;
        while(cur != null){
        	//拥有cur.val相同节点值的最后一个
            while(cur.next != null && cur.val == cur.next.val){
                cur = cur.next;
            }
            
            //cur不出现重复值的情况，更新pre为cur
            if(pre.next == cur){
                pre = cur;
            }
            //所有的cur节点都要被删除，不用更新pre节点
            else{
                pre.next = cur.next;
            }
            //更新完pre，更新cur
            cur = cur.next;
        }
        return header.next;
    }
}