寫在前面

• 本系列包含《劍指Offer》66道算法題，一周刷完，這是完結(jié)篇，撒花！
  系列匯總：劍指Offer 66題 Java 刷題筆記匯總
• 所有題目均可在?？途W(wǎng)在線編程平臺(tái)進(jìn)行調(diào)試。
  網(wǎng)址：https://www.nowcoder.com/ta/coding-interviews
• 本系列包含題目，解題思路及代碼（Java）。
  代碼同步發(fā)布在GitHub：https://github.com/JohnnyJYWu/offer-Java

上一篇：算法 | 一周刷完《劍指Offer》 Day5：第50~60題

Day6：第60~66題

6天搞定！感覺還是有點(diǎn)進(jìn)步的。

• T61. 序列化二叉樹
• T62. 二叉搜索樹的第k個(gè)結(jié)點(diǎn)
• T63. 數(shù)據(jù)流中的中位數(shù)
• T64. 滑動(dòng)窗口的最大值
• T65. 矩陣中的路徑
• T66. 機(jī)器人的運(yùn)動(dòng)范圍

T61. 序列化二叉樹

題目描述

請(qǐng)實(shí)現(xiàn)兩個(gè)函數(shù)，分別用來序列化和反序列化二叉樹

解題思路

基本的序列化思想就可以。
此題每個(gè)人方法都不一樣，需要注意的是：
1.對(duì)于二叉樹來說，節(jié)點(diǎn)為null時(shí)最好采用一個(gè)字符來替代表示（這里用的 # 字符）；
2.該題二叉樹的value為int型，在序列化成字符串時(shí)最好用字符分隔開（這里用的逗號(hào)），不然int和String轉(zhuǎn)換過程中容易出錯(cuò)。

    public String Serialize(TreeNode root) {
        if(root == null) return "";
        
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        
        return sb.toString();
    }
    
    private void serialize(TreeNode root, StringBuilder sb) {
        if(root == null) {
            sb.append("#,");
            return;
        }
        
        sb.append(root.val);
        sb.append(",");
        serialize(root.left, sb);
        serialize(root.right, sb);
    }
       
    public TreeNode Deserialize(String str) {
        if(str == null || str.length() == 0) return null;

        String[] strs = str.split(",");
        index = 0;
        return deserialize(strs);
    }
    
    private int index;
    
    private TreeNode deserialize(String[] strs) {
        if(!strs[index].equals("#")) {
            TreeNode node = new TreeNode(Integer.parseInt(strs[index]));
            index ++;
            node.left = deserialize(strs);
            node.right = deserialize(strs);
            return node;
        } else {
            index ++;
        }
        return null;
    }

T62. 二叉搜索樹的第k個(gè)結(jié)點(diǎn)

題目描述

給定一棵二叉搜索樹，請(qǐng)找出其中的第k小的結(jié)點(diǎn)。例如， （5，3，7，2，4，6，8） 中，按結(jié)點(diǎn)數(shù)值大小順序第三小結(jié)點(diǎn)的值為4。

解題思路

注意題意。二叉搜索樹：左子結(jié)點(diǎn) < 根結(jié)點(diǎn) < 右子結(jié)點(diǎn)
因此對(duì)二叉搜索樹進(jìn)行中序遍歷，得到的即為從小到大排序序列。

    private ArrayList<TreeNode> list = new ArrayList<>();
    
    public TreeNode KthNode(TreeNode pRoot, int k) {//二叉搜索樹，中序遍歷即為從小到大的排序
        if(pRoot == null || k <= 0) return null;
        
        inOrder(pRoot);
        
        TreeNode kthNode = null;
        
        if(k <= list.size()) {
            kthNode = list.get(k - 1);
        }
        
        return kthNode;
    }
    
    private void inOrder(TreeNode root) {//中序遍歷
        if(root == null) return;
        
        //左
        if(root.left != null) inOrder(root.left);
        //根
        list.add(root);
        //右
        if(root.right != null) inOrder(root.right);
    }

T63. 數(shù)據(jù)流中的中位數(shù)

題目描述

如何得到一個(gè)數(shù)據(jù)流中的中位數(shù)？如果從數(shù)據(jù)流中讀出奇數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。如果從數(shù)據(jù)流中讀出偶數(shù)個(gè)數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個(gè)數(shù)的平均值。我們使用Insert()方法讀取數(shù)據(jù)流，使用GetMedian()方法獲取當(dāng)前讀取數(shù)據(jù)的中位數(shù)。

解題思路

畫了張草圖（如上）。這是一個(gè)比較巧妙的方法，用到了PriorityQueue，一個(gè)能自動(dòng)排序的隊(duì)列，排序方式也可以自定義。解題思路寫在注釋里了，對(duì)著代碼和圖片容易理解一些。

    private int count = 0;//計(jì)數(shù)，判斷奇偶
    //使用自動(dòng)排序的PriorityQueue,兩個(gè)堆詳情見圖片
    //小頂推：默認(rèn)從小到大排序，堆頂為最小數(shù)，用于存儲(chǔ)后半部分較大的數(shù)，堆頂用于計(jì)數(shù)中位數(shù)
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    //大頂堆：聲明從大到小排序，堆頂為最大數(shù)，用于存儲(chǔ)前半部分較小的數(shù)，堆頂用于計(jì)數(shù)中位數(shù)
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer arg0, Integer arg1) {
            return arg1 - arg0;
        }
    });
    
    public void Insert(Integer num) {
        //分奇偶次插入，一半入小頂堆，一半入大頂堆，保證兩個(gè)堆數(shù)量一半一半
        if(count % 2 == 0) {//注意這里0為第1個(gè)數(shù)，所以插入時(shí)奇數(shù)次對(duì)應(yīng)的count為偶數(shù)
            //奇數(shù)次插入時(shí)，最終入小頂堆
            //注意插入時(shí)是先入大頂堆，由大頂堆排序后取大頂堆最大的插入小頂堆
            
            //插入大頂堆
            maxHeap.offer(num);
            //取大頂堆堆頂
            int maxInMaxHead = maxHeap.poll();
            //堆頂插入小頂堆
            minHeap.offer(maxInMaxHead);
        } else {
            //偶數(shù)次插入時(shí)，最終入大頂堆
            //原理同上
            
            //插入小頂堆
            minHeap.offer(num);
            //取小頂堆堆頂
            int minInMinHead = minHeap.poll();
            //堆頂入大頂堆
            maxHeap.offer(minInMinHead);
        }
        
        count ++;
    }

    @SuppressWarnings("deprecation")
    public Double GetMedian() {
        //由于先入小頂堆，小頂堆數(shù)量總是比大頂堆多1或相等
        //所以這里，count為奇次時(shí)，插入了奇數(shù)次，中位數(shù)是小頂堆堆頂
        //count為偶次時(shí)，插入了偶數(shù)次，中位數(shù)是兩堆堆頂平均數(shù)
        if(count % 2 == 0) {
            return new Double(minHeap.peek() + maxHeap.peek()) / 2;
        } else {
            return new Double(minHeap.peek());
        }
    }

T64. 滑動(dòng)窗口的最大值

題目描述

給定一個(gè)數(shù)組和滑動(dòng)窗口的大小，找出所有滑動(dòng)窗口里數(shù)值的最大值。例如，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動(dòng)窗口的大小3，那么一共存在6個(gè)滑動(dòng)窗口，他們的最大值分別為{4,4,6,6,6,5}； 針對(duì)數(shù)組{2,3,4,2,6,2,5,1}的滑動(dòng)窗口有以下6個(gè)： {[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]}。

解題思路

使用到了Deque，一個(gè)雙端隊(duì)列，可從兩端彈出，用來模擬窗口，儲(chǔ)存當(dāng)前窗口顯示的元素在num數(shù)組的下標(biāo)。每當(dāng)移動(dòng)窗口時(shí)，要判斷隊(duì)列頭是否超出窗口范圍，同時(shí)要將新加入的隊(duì)尾的數(shù)與隊(duì)中最大數(shù)比較，小則直接退出，大則退出最大數(shù)。（這樣做實(shí)質(zhì)上始終只有一個(gè)最大元素在窗口中）

    public ArrayList<Integer> maxInWindows(int[] num, int size) {
        ArrayList<Integer> result = new ArrayList<>();
        
        if(num == null || num.length == 0 || size == 0 || size > num.length) {
            return result;
        }
        
        //雙端隊(duì)列，可從兩端彈出，模擬窗口，用于存當(dāng)前窗口最大值在num數(shù)組下標(biāo)
        Deque<Integer> deque = new ArrayDeque<>();
        
        for(int i = 0; i < num.length; i ++) {
            if(!deque.isEmpty() && (i - deque.peekFirst()) >= size) {//當(dāng)隊(duì)列頭已超出窗口范圍時(shí)移除隊(duì)列頭
                deque.pollFirst();
            }
            while(!deque.isEmpty() && num[i] >= num[deque.peekLast()]) {//如果，要進(jìn)隊(duì)列的新的數(shù)比隊(duì)列尾部大，移除隊(duì)尾，直到隊(duì)列中只剩最大的一個(gè)數(shù)
                deque.pollLast();
            }
            deque.offer(i);
            if(i >= (size - 1)) {//過濾前幾個(gè)，當(dāng)遍歷到第一個(gè)窗口大小時(shí)開始存結(jié)果
                result.add(num[deque.peekFirst()]);
            }
        }
        
        return result;
    }

T65. 矩陣中的路徑

題目描述

請(qǐng)?jiān)O(shè)計(jì)一個(gè)函數(shù)，用來判斷在一個(gè)矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一個(gè)格子開始，每一步可以在矩陣中向左，向右，向上，向下移動(dòng)一個(gè)格子。如果一條路徑經(jīng)過了矩陣中的某一個(gè)格子，則之后不能再次進(jìn)入這個(gè)格子。 例如 a b c e s f c s a d e e 這樣的3 X 4 矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑，因?yàn)樽址牡谝粋€(gè)字符b占據(jù)了矩陣中的第一行第二個(gè)格子之后，路徑不能再次進(jìn)入該格子。

解題思路

動(dòng)態(tài)規(guī)劃應(yīng)用題，思路是邊走邊找，具體見注釋。

注意：
定義輔助數(shù)組，用于記錄矩陣中各位置是否被訪問過；
二維數(shù)組在一維數(shù)組形式中的表示：index = i * cols + j;
此題求多種解，記得回溯。

    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        int[] flag = new int[matrix.length];//輔助數(shù)組，用于記錄矩陣中各位置是否被訪問過
        
        for(int i = 0; i < rows; i ++) {
            for(int j = 0; j < cols; j ++) {
                int index = i * cols + j;//二維數(shù)組在一維數(shù)組形式中的表示
                
                if(matrix[index] == str[0]) {//找到str在矩陣的開始位置
                    if(findPath(matrix, rows, cols, i, j, str, 0, flag)) {
                        return true;
                    }
                }
            }
        }
        
        return false;
    }
    
    //動(dòng)態(tài)規(guī)劃求解
    private boolean findPath(char[] matrix, int rows, int cols, int i, int j, 
                            char[] str, int strIndex, 
                            int[] flag) {
        int index = i * cols + j;
        if(i < 0 || i >= rows || j < 0 || j >= cols //數(shù)組越界
            || matrix[index] != str[strIndex] //矩陣該點(diǎn)與字符串相應(yīng)位置值不同
            || flag[index] == -1) {//矩陣該點(diǎn)已使用過
            return false;
        }
        if(strIndex == str.length - 1) {//該點(diǎn)符合要求且已是字符串最后一位
            return true;
        }
        
        flag[index] = -1;
        //對(duì)該點(diǎn)上下左右遞歸求解
        if(findPath(matrix, rows, cols, i - 1, j, str, strIndex + 1, flag)
            || findPath(matrix, rows, cols, i + 1, j, str, strIndex + 1, flag)
            || findPath(matrix, rows, cols, i, j - 1, str, strIndex + 1, flag)
            || findPath(matrix, rows, cols, i, j + 1, str, strIndex + 1, flag)) {
            return true;//任一符合即可
        }
        
        flag[index] = 0;//記得回溯時(shí)將該點(diǎn)標(biāo)記為未使用過
        
        return false;
    }

T66. 機(jī)器人的運(yùn)動(dòng)范圍

題目描述

地上有一個(gè)m行和n列的方格。一個(gè)機(jī)器人從坐標(biāo)0,0的格子開始移動(dòng)，每一次只能向左，右，上，下四個(gè)方向移動(dòng)一格，但是不能進(jìn)入行坐標(biāo)和列坐標(biāo)的數(shù)位之和大于k的格子。 例如，當(dāng)k為18時(shí)，機(jī)器人能夠進(jìn)入方格（35,37），因?yàn)?+5+3+7 = 18。但是，它不能進(jìn)入方格（35,38），因?yàn)?+5+3+8 = 19。請(qǐng)問該機(jī)器人能夠達(dá)到多少個(gè)格子？

解題思路

動(dòng)態(tài)規(guī)劃應(yīng)用題，同上一題，相比要簡(jiǎn)單很多，具體見注釋。

    public int movingCount(int threshold, int rows, int cols) {
        int[] flags = new int[rows * cols];//輔助數(shù)組，用于記錄矩陣中各位置是否被訪問過
        
        return moving(threshold, rows, cols, 0, 0, flags);
    }
    
    //動(dòng)態(tài)規(guī)劃
    private int moving(int k, int rows, int cols,
                        int i, int j, int[] flags) {
        int index = i * cols + j;
        if(i < 0 || i >= rows || j < 0 || j >= cols || flags[index] == -1) {//數(shù)組越界或該點(diǎn)被訪問過
            return 0;
        }
        
        int sum = 0;
        int tmp = i;
        while(tmp != 0) {//橫坐標(biāo)各位和
            sum += tmp % 10;
            tmp /= 10;
        }
        tmp = j;
        while(tmp != 0) {//縱坐標(biāo)各位和
            sum += tmp % 10;
            tmp /= 10;
        }
        
        if(sum <= k) {
            flags[index] = -1;//訪問過，與上題不同的是，這里不需回溯
            int steps = 1;//計(jì)入當(dāng)前點(diǎn)
            //對(duì)該點(diǎn)右邊和下邊的點(diǎn)遞歸求解，左邊與上邊在前面的迭代過程中已訪問過，無需再次訪問
            steps += moving(k, rows, cols, i + 1, j, flags);
            steps += moving(k, rows, cols, i, j + 1, flags);
            return steps;
        }
        
        return 0;
    }

項(xiàng)目地址：https://github.com/JohnnyJYWu/offer-Java

上一篇：算法 | 一周刷完《劍指Offer》 Day5：第50~60題

希望這篇文章對(duì)你有幫助~