第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));
}
}
本题使用动态规划也可以求解，在二刷的时候，会进行补充和改进，谢谢大家。
京公网安备 11010502036488号