算法原理题目解析1.迷宫中离入口最近的出口题目描述给你一个m*n的迷宫举证maze(下标从0开始).矩阵中有空格子(用.表示) 和墙(用)表示,同时给你一个entrance (在迷宫的起始位置)每一步操作,你可以往上下左右任一方向移动一个格子(注意不能进入墙) 我们的目标是找到离起始位置最旧的出口出口是maze边界上的空格子 entrance格子不算出口(也就是说如果小人最开始在边界,这个是不能当做出口的)请你返回从起点到出口的最短路径的步数,如果不存在这样的路径,请返回-1;算法原理这是一道经典的边权为1的最短路问题这里我们使用bfs来解决这一问题,这里我们遍历上下左右位置的时候,需要用到向量数组同时要使用一个vis[][]数组来标记当前位置是否已经遍历过了代码实现class Solution { int[] dx{1,-1,0,0}; int[] dy{0,0,1,-1}; boolean[][] visnew boolean[101][101]; public int nearestExit(char[][] maze, int[] entrance) { int mmaze.length; int nmaze[0].length; Queueint[] qnew LinkedList(); q.add(entrance); int ret0; vis[entrance[0]][entrance[1]]true; while(!q.isEmpty()){ int szq.size(); ret; for(int i0;isz;i){ int[] tq.poll(); int at[0]; int bt[1]; for(int k0;k4;k){ int xadx[k]; int ybdy[k]; if(x0yny0xmmaze[x][y].!vis[x][y]){ q.add(new int[]{x,y}); if(x0||y0||xm-1||yn-1){ return ret; } vis[x][y]true; } } } } return -1; } }2.最小基因变化题目描述基因序列可以表示为一条8个字符组成的字符串,其中每个字符都是AGCT之一假设我们需要调查从基因序列start变为end所发生的的基因变化.一次基因变化就是意味着这个基因序列的一个字符发生了变化例如:AACCGGTT--AACCGGTA就是一次基因变化另外有一个基因库bank记录了所有有效的基因变化,只有基因库中的基因才是有效的基因序列(也就是说变化后的基因必须要位于基因库中)给你两个基因序列start和end,以及一个基因库bank,请找出并返回能够是start变化为end所需的最少变化次数.如果无法完成此基因变化 返回-1注意:起始基因序列默认是有效的,但他不一定会出现在基因库中算法原理转化:图论问题,边权为1的最短路问题每次只能改变一个,而且是AGCT中的一个基因序列相当于一个点q存的是一个个字符串,还要标记当前改变后的字符串是否存在于基因库中(哈希表) 这里要注意如果最后的字符在基因库中不存在,可以直接返回-1如何枚举出所有的变化情况?暴力枚举(每个位置用AGCT替换)还有一个基因库(用来判断变化后的字符是否合法)如何快速判断这个情况在基因库中存在,把基因库中的字符串丢进哈希表中代码实现class Solution { public int minMutation(String startGene, String endGene, String[] bank) { SetString vis new HashSet(); SetString hash new HashSet(); for(String s: bank){ hash.add(s); } if(startGene.equals(endGene)){ return 0; } if(!hash.contains(endGene)){ return -1; } QueueString q new LinkedList(); q.add(startGene); int ret 0; char[] change {A,G,C,T}; while(!q.isEmpty()){ ret ; int sz q.size(); while(sz--!0){ String t q.poll(); for(int i 0;i8;i){ char[] tmp t.toCharArray(); for(int j0;j4;j){ tmp[i] change[j]; String s new String(tmp); if(!vis.contains(s)hash.contains(s)){ if(s.equals(endGene)){ return ret; } q.add(s); vis.add(s); } } } } } return -1; } }3.单词接龙题目描述字典wordList中从单词beginWord到endWord的转换序列是一个按照下述规格形成的序列beginWord-s1-s2-...-sk:1.每一对相邻的 单词只差一个一个字母2.对于1ik时,每个si都在wordList中. 注意,beginWord不需要再wordList3.skendWord给你两个单词beginWord和endWord和一个字典wordList,返回从beginWord到endWord的最短转换序列中的单词数目,如果不存在这个的转换序列,返回0算法原理这道题的算法原理与上道题最小基因序列基本相同(我们需要做的是准备一个set用来判断是否已经出现过,再准备一个set来快速判断这个新变化的set是否存在于字典中)代码实现class Solution { public int ladderLength(String beginWord, String endWord, ListString wordList) { SetString visnew HashSet(); SetString hashnew HashSet(); for(String s:wordList){ hash.add(s); } if(!hash.contains(endWord)) return 0; QueueString qnew LinkedList(); q.add(beginWord); int ret1; while(!q.isEmpty()){ ret; int szq.size(); while(sz--!0){ String tq.poll(); for(int i0;it.length();i){ char[] tmpt.toCharArray(); for(char cha;chz;ch){ tmp[i]ch; String nextnew String(tmp); if(hash.contains(next)!vis.contains(next)){ if(endWord.equals(next)){ return ret; } q.add(next); vis.add(next); } } } } } return 0; } }4. 为高尔夫比赛砍树题目描述你被请来给一个要举办高尔夫比赛的树林砍树,树林由一个m*n的矩阵表示,再这个矩阵中:0表示障碍,无法触碰,1表示地面,可以行走 比1大的数表示有树的单元格,可以行走,数值表示树的高度每一步可以向上下左右四个方向移动一个单元,如果你站的地方有一个数,那么你可以决定是否砍到他你需要按照树的高度从低到高的砍掉所有的数,每砍过一棵树,该单元格的值表示为1你讲从(0,0)点开始工作,返回你砍完所有的树需要走的最小步数,如果你无法看完所有的树,返回-1可以保证的是:没有两棵树的高度是完全相同的,并且你至少需要砍到一棵树算法原理这道题我们可以理解为若干个迷宫问题,首先我们要确定砍树顺序(是要从低到高的进行砍树,我们可以先将大于1的单元格的位置存起来,然后排序,这样我们就确定了 砍树顺序)接着我们先找(0,0)-第一个树的位置这样的迷宫来进行解决即可代码实现class Solution { int m,n; public int cutOffTree(ListListInteger f) { mf.size();nf.get(0).size(); //1.确定砍树顺序 Listint[] treesnew ArrayList(); for(int i0;im;i){ for(int j0;jn;j){ if(f.get(i).get(j)1){ trees.add(new int[]{i,j}); } } } Collections.sort(trees,(a,b)-{ return f.get(a[0]).get(a[1])-f.get(b[0]).get(b[1]); }); //2.按照顺序砍 int ret0; int bx0,by0; for(int[] tree:trees){ int xtree[0],ytree[1]; int stepbfs(f,bx,by,x,y); if(step-1) return -1; retstep; bxx; byy; } return ret; } int[] dx{1,-1,0,0}; int[] dy{0,0,1,-1}; public int bfs(ListListIntegerf,int bx,int by,int ex,int ey){ if(bxexbyey) return 0; Queueint[] qnew LinkedList(); boolean[][] visnew boolean[m][n]; q.add(new int[]{bx,by}); vis[bx][by]true; int ret0; while(!q.isEmpty()){ ret; int szq.size(); while(sz--!0){ int[] tq.poll(); int at[0],bt[1]; for(int i0;i4;i){ int xadx[i],ybdy[i]; if(x0xmy0ynf.get(x).get(y)!0!vis[x][y]){ if(xexyey){ return ret; } q.add(new int[]{x,y}); vis[x][y]true; } } } } return -1; } }