每日一题之《剑指offer》64,65,66,67题

第64题：滑动窗口的最大值

难易度：⭐⭐⭐

题目描述
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
例如，如果输入数组{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]}。

解析：
本题的思路是使用双端队列
双端队列用来保存窗口最大数值的index值
每次都是用队列的队尾与新进入的数字进行比较，如果队列队尾要比新的值小，那么就出队，需要注意的是，此处应该使用while循环，而不是if判断：

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

同时，还需要注意的点是需要判断对首数字是否过期，对于数组

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

来说，当index = 5的时候，原本对首的数字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);
            // 判断对首数字是否过期
            if(deque.peekFirst() == i - size){
                deque.pollFirst();
            }
            if(i >= size - 1){
                arrayList.add(num[deque.peekFirst()]);
            }
        }
        return arrayList;
    }
}

第65题：矩阵中的路径

难易度：⭐⭐⭐

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

又是一道我想破头没写出来的题目，思路其实还是比较简单的，即：
暴力递归
当矩阵中坐标为(row,col)的格子和路径字符串中的下标pathLength的字符一样时，使用暴力递归的思想，从相邻的四个格子中去定位路径字符串中下标为pathLenth + 1的字符。
如果四个相邻的个子都没有匹配字符串中下标为pathLength + 1的字符，则表明当前路径字符串中下标为pathLength的字符在矩阵中的定位是错误的，那么则需要返回到前一个字符pathLength - 1,然后重新定位
本题同时还要使用一个矩阵大小的boolean数组，去记录，哪些点是被访问过的，因为题中有明确说明，“好马不吃回头草”。当走过的部分有被标记过则无法再走。
代码如下：

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的格子开始移动,每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于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的绳子，请把绳子剪成整数长的m段（m、n都是整数，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));
    }
}

本题使用动态规划也可以求解，在二刷的时候，会进行补充和改进，谢谢大家。