假期第一天，有时间带娃出去玩。上午先去了农家乐摘草莓，发现草莓都下市了，暴露了平时很少吃水果。随后去了汤山，在博物馆附近找了一家小店，干净整洁，5个人吃了250块钱，很满意，毕竟原来在景区附近都没吃好过。
第一题 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组 {3, 4, 5, 1, 2} 为 {1, 2, 3, 4, 5} 的一个旋转，该数组的最小值为 1；
解题思路：使用二分查找法，左边下标left，右边right，中间m。比较left与m对应的大小，如果arr[left]<=arr[m]说明最小的数字在m与right之间。优化一下，下次查找left=m+1。
当arr[left]>arr[m]，那么值在left与m中间，right=m
package com.lyc.dataautest;
public class minNumberInRotateArray {
public static int find(int[] arr) {
int left = 0;
int right = arr.length-1;
int m = (right+1)/2;
while(left<m) {
if(arr[left]<=arr[m]) {
left = m+1;
} else {
right = m;
}
m = (left+right)/2;
}
return arr[left];
}
public static void main(String[] args) {
int[] arr = {3,4,5,1,2};
System.out.println("the result is:"+find(arr));
}
}
第二题 矩阵中的路径
用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
参考 https://blog.csdn.net/sbq63683210/article/details/51703047
解题思路：
回溯法的一个应用。所谓回溯法就是按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。
具体到这里，hasPath从坐标0,0开始遍历，通过hasPathCore递归的方法查找。hasPathCore是具体递归查找的实现。visited代表该字符是否访问过。下标的计算方式通过index = i*cols+j获取。如果matrix[index]!=str[k]，那么显然不是一个合法的路径，visited[index]==0代表访问过，也不是一个合法的路径。j>=cols i>=rows当然也不行，rows col是固定最大的行 列。
k == str.length - 1 这个很显然就是找到了
如果没找到向上下左右四个方向遍历，如果没找到k要回退，访问过的地方要重新设置为false
public class Solution {
/* @author miracle
*/
public boolean hasPath(char[] matrix, int rows, int cols, char[] str){
//创建一个布尔数组
boolean visited[]= new boolean[matrix.length];
for(int i = 0;i
for(int j=0;j
if(hasPathCore(matrix,i,j,0,rows,cols,str,visited)){
return true;
}
}
}
return false;
}
public boolean hasPathCore(char[] matrix,int i,int j,int k,int rows,int cols,char[] str,boolean[] visited){
// 对于给定行数和列数得到其在矩阵中的下标
int index = i*cols+j;
//判断合法性
if(i<0||i>=rows||j<0||j>=cols||matrix[index]!=str[k]||visited[index]){
return false;
}
visited[index] =true;
// 如果递归到最后一个位置的字符，则表明前面位置的字符都在矩阵中找到了对应的位置
if (k == str.length - 1)
return true;
if(hasPathCore(matrix,i-1,j,k+1,rows,cols,str,visited)
||hasPathCore(matrix,i,j-1,k+1,rows,cols,str,visited)
||hasPathCore(matrix,i+1,j,k+1,rows,cols,str,visited)
||hasPathCore(matrix,i,j+1,k+1,rows,cols,str,visited)){
return true;
}else{
//如果相邻格子的字符都没有匹配到下一个字符，则需要回到前一个格子，从而需要把把位置的状态重新设定为未访问
k--;
visited[index] =false;
}
return false;
}
}
第三题 机器人的运动范围
地上有一个 m 行和 n 列的方格。一个机器人从坐标 (0, 0) 的格子开始移动，每一次只能向左右上下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 k 的格子。例如，当 k 为 18 时，机器人能够进入方格（35, 37），因为 3+5+3+7=18。但是，它不能进入方格（35, 38），因为 3+5+3+8=19。请问该机器人能够达到多少个格子？
解题思路同上，区别是再加个判断
