第64題：滑動窗口的最大值

難易度：???

題目描述
給定一個數(shù)組和滑動窗口的大小殿如，找出所有滑動窗口里數(shù)值的最大值。
例如最爬，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動窗口的大小3涉馁，那么一共存在6個滑動窗口:
他們的最大值分別為{4,4,6,6,6,5}； 
針對數(shù)組{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]}。

解析：
本題的思路是使用雙端隊列
雙端隊列用來保存窗口最大數(shù)值的index值
每次都是用隊列的隊尾與新進入的數(shù)字進行比較互艾，如果隊列隊尾要比新的值小试和，那么就出隊，需要注意的是纫普，此處應該使用while循環(huán)阅悍，而不是if判斷：

while(!deque.isEmpty() && num[deque.peekLast()] < num[i]){
    deque.pollLast();
}

同時，還需要注意的點是需要判斷對首數(shù)字是否過期，對于數(shù)組

{2,3,4,2,6,2,5,1}

來說节视，當index = 5的時候拳锚，原本對首的數(shù)字4過期，當滿足deque.peekFirst() == i - size時寻行，滿足過期的條件霍掺。整理好思路后就可以寫代碼了。
代碼如下：

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size){
        ArrayList<Integer> arrayList = new ArrayList<>();
        if(num == null || num.length == 0 || size == 0 || num.length < size){
            return arrayList;
        }
        Deque<Integer> deque = new LinkedList<>();
        for(int i = 0;i < num.length;i++){
            while(!deque.isEmpty() && num[deque.peekLast()] < num[i]){
                deque.pollLast();
            }
            deque.addLast(i);
            // 判斷對首數(shù)字是否過期
            if(deque.peekFirst() == i - size){
                deque.pollFirst();
            }
            if(i >= size - 1){
                arrayList.add(num[deque.peekFirst()]);
            }
        }
        return arrayList;
    }
}

第65題：矩陣中的路徑

難易度：???

題目描述
請設計一個函數(shù)寡痰，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑抗楔。
路徑可以從矩陣中的任意一個格子開始棋凳，每一步可以在矩陣中向左拦坠，向右，向上剩岳，向下移動一個格子贞滨。
如果一條路徑經(jīng)過了矩陣中的某一個格子，則該路徑不能再進入該格子拍棕。 
例如:
a b c e
s f c s
a d e e
矩陣中包含一條字符串"bcced"的路徑晓铆，
但是矩陣中不包含"abcb"路徑，
因為字符串的第一個字符b占據(jù)了矩陣中的第一行第二個格子之后绰播，路徑不能再次進入該格子骄噪。

又是一道我想破頭沒寫出來的題目，思路其實還是比較簡單的蠢箩，即：
暴力遞歸
當矩陣中坐標為(row,col)的格子和路徑字符串中的下標pathLength的字符一樣時链蕊，使用暴力遞歸的思想，從相鄰的四個格子中去定位路徑字符串中下標為pathLenth + 1的字符谬泌。
如果四個相鄰的個子都沒有匹配字符串中下標為pathLength + 1的字符滔韵，則表明當前路徑字符串中下標為pathLength的字符在矩陣中的定位是錯誤的，那么則需要返回到前一個字符pathLength - 1,然后重新定位
本題同時還要使用一個矩陣大小的boolean數(shù)組掌实，去記錄陪蜻，哪些點是被訪問過的，因為題中有明確說明贱鼻，“好馬不吃回頭草”宴卖。當走過的部分有被標記過則無法再走。
代碼如下：

public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str){
        if(matrix == null || matrix.length == 0 || str == null || str.length == 0 || rows * cols != matrix.length || rows * cols < str.length){
            return false;
        }
        boolean [] visited = new boolean[rows * cols];
        int[] pathLength = {0};
        for(int i = 0;i < rows;i++){
            for(int j = 0;j < cols;j++){
                if(hasPathCore(matrix,rows,cols,str,i,j,visited,pathLength)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean hasPathCore(char[] matrix,int rows,int cols,char[] str,int row,int col,boolean[] visited,int[] pathLength){
        boolean res = false;
        if(row >= 0 && row < rows && col >= 0 && col < cols && !visited[row * cols + col] && matrix[row * cols + col] == str[pathLength[0]]){
            visited[row * cols + col] = true;
            pathLength[0]++;
            if(str.length == pathLength[0]){
                return true;
            }
            res = hasPathCore(matrix,rows,cols,str,row + 1,col,visited,pathLength)
                || hasPathCore(matrix,rows,cols,str,row - 1,col,visited,pathLength)
                || hasPathCore(matrix,rows,cols,str,row,col + 1,visited,pathLength)
                || hasPathCore(matrix,rows,cols,str,row,col - 1,visited,pathLength);
            if(!res){
                visited[row * cols + col] = false;
                pathLength[0]--;
            }
        }
        return res;
    }
}

第66題：機器人的運動范圍

難易度：???

題目描述:
地上有一個m行和n列的方格邻悬。
一個機器人從坐標0,0的格子開始移動,每一次只能向左症昏，右，上拘悦，下四個方向移動一格齿兔，但是不能進入行坐標和列坐標的數(shù)位之和大于k的格子。
 例如，當k為18時分苇，機器人能夠進入方格（35,37）添诉，因為3+5+3+7 = 18。
但是医寿，它不能進入方格（35,38）栏赴，因為3+5+3+8 = 19。
請問該機器人能夠達到多少個格子靖秩？

解析：
本題和上一題實際上都屬于一個類型的問題须眷，都屬于暴力遞歸
本題的解析，在二刷的時候會進行改進沟突，寫的詳細一些花颗，敬請期待
代碼如下：

public class Solution {
    public int movingCount(int threshold, int rows, int cols){
        if(threshold < 0 || rows < 0 || cols < 0){
            return 0;
        }
        boolean[] visited = new boolean[rows * cols];
        int count = movingCountCore(threshold,rows,cols,0,0,visited);
        return count;
    }
    
    public int movingCountCore(int threshold,int rows,int cols,int row,int col,boolean[] visited){
        int res = 0;
        if(check(threshold,rows,cols,row,col,visited)){
            visited[row * cols + col] = true;
            res  = 1 + movingCountCore(threshold,rows,cols,row + 1,col,visited)
                     + movingCountCore(threshold,rows,cols,row - 1,col,visited)
                     + movingCountCore(threshold,rows,cols,row,col + 1,visited)
                     + movingCountCore(threshold,rows,cols,row,col - 1,visited);
        }
        return res;
    }
    
    public boolean check(int threshold,int rows,int cols,int row,int col,boolean[] visited){
        if(row >= 0 && row < rows && col >= 0 && col < cols && !visited[row * cols + col] && (getDigitSum(row) + getDigitSum(col) <= threshold)){
            return true;
        }
        return false;
    }
    
    public int getDigitSum(int target){
        int res = 0;
        while(target != 0){
            res += target % 10;
            target /= 10;
        }
        return res;
    }
}

第67題：剪繩子

難易度：???

題目描述:
給你一根長度為n的繩子，請把繩子剪成整數(shù)長的m段（m惠拭、n都是整數(shù)扩劝，n>1并且m>1），每段繩子的長度記為k[0],k[1],...,k[m]职辅。
請問k[0]xk[1]x...xk[m]可能的最大乘積是多少棒呛？
例如，當繩子的長度是8時域携，我們把它剪成長度分別為2簇秒、3、3的三段秀鞭，此時得到的最大乘積是18趋观。

解析：
思路一：
貪心算法：
貪心策略如下：
當繩子的長度大于等于5的時候，我們需要盡可能多去剪出長度為3的繩子气筋；當剩下的繩子長度為4的時候拆内，把繩子簡稱兩段長度為4的繩子。因為2 × 2 > 3 × 1
貪心策略的證明非常難宠默，在這里就不予以證明了麸恍。
代碼如下：

public class Solution {
    // 貪心策略
    public int cutRope(int target) {
        if(target < 2){
            return 1;
        }
        if(target == 2){
            return 1;
        }
        if(target == 3){
            return 2;
        }
        int timesOf3 = target / 3;
        if(target - timesOf3 * 3 == 1){
            timesOf3--;
        }
        int timesOf2 = (target - timesOf3 * 3) / 2;
        return (int)(Math.pow(3,timesOf3) * Math.pow(2,timesOf2));
    }
}

本題使用動態(tài)規(guī)劃也可以求解，在二刷的時候搀矫，會進行補充和改進抹沪，謝謝大家。