前言

刚刚参加完百度的网上笔试，编码部分主要考察对递归函数的运用和数理逻辑(离散、线代的内容为主，学完早都还给老师了有木有)。

编码题有三题，我在这里会尽量通俗地解析题目，希望能帮助到想去百度发展的童鞋们。

题目

No.1

为了进程城市规划，需要计算居民区的住宅数目。该区域是一个n*m的网格，如果有屋顶则为1，如果是空地则为0.有1组成的相邻网格单元组成的簇为一个单独住宅。对角为1不算相邻。

 输入：图，由0，1表示  输出：住宅总数。

这题的考点主要是考四连通图:即验证一个节点是否向上下左右四个方向连通。根据本题题意，我们可以假设，当节点在上下左右四个方向上任意一个相邻节点的权值为1，则认为节点在该方向连通，反之认为不连通。

public class Test1{ public static int countHomes(int[][] grid){ int returnVal=0; for (int n = 0; n < grid.length; n++) { for (int m = 0; m <grid[0].length;m++) { //如果当前权值为1，就进行递归访问，否则不访问 if (grid[n][m] == 1) { returnVal++; dfs(grid, n, m); //当递归结束后，以grid[n][m]为起点开始递归整个连通图(即房屋簇)都被标记为0,属于它的任何一个节点都不会进入下次递归 //为方便理解，输出每次递归完一个连通图后，整个网格图的变化情况 for (int i = 0; i < grid.length; i++) { for (int j = 0; j <grid[0].length;j++) { System.out.print(grid[i][j]+" "); } System.out.println(""); } System.out.println("房屋总数:"+returnVal); } } } return returnVal; } public static void dfs(int[][] matrix,int n,int m){ //为避免数组下标越界,如果是在网格边缘上的节点直接返回 if (n < 0 || n > matrix.length - 1 || m < 0 || m > matrix[0].length - 1) return; //递归直到本连通图中所有节点权值都为0返回 if (matrix[n][m] == 0) return; else { matrix[n][m] = 0; //对于每个节点都往上下左右四个方向递归，测试是否连通 dfs(matrix, n + 1, m); dfs(matrix, n - 1, m); dfs(matrix, n, m - 1); dfs(matrix, n, m + 1); } } //测试 public static void main(String[] args){ countHomes(new int[][]{{0,0,1,0,1},{0,1,0,1,1}}); } }

No.2

构建一个增量矩阵，求该矩阵和它的转置矩阵相乘得到的矩阵.

 输入：初始值，行数，列数  输出：乘积矩阵。

这题的考点主要是矩阵乘法,没有什么好说。

public class Test2 { public static int[][] getResult(int initVal,int rows,int cols){ //得到增量矩阵 int[][] resultm=new int[rows][cols]; for(int i=0;i<rows;i++){ for(int j=0;j<cols;j++){ resultm[i][j]=initVal; initVal++; } } return MultiMatrix(resultm, reverse(resultm)); } //求矩阵的转置矩阵 public static int[][] reverse(int[][] s){ int[][] r=new int[s[0].length][s.length]; for(int i=0;i<s[0].length;i++){ for(int j=0;j<s.length;j++){ r[i][j]=s[j][i]; } } return r; } //进行矩阵乘法运算 static int[][] MultiMatrix(int[][] a,int[][] b){ int c[][] = new int[a.length][b[0].length]; int x,i,j; for(i = 0;i<a.length ;i++) { for(j = 0;j<b[0].length;j++) { int temp = 0; for(x = 0;x<b.length;x++) { temp+=a[i][x]*b[x][j]; } c[i][j] = temp; } } return c; } //测试 public static void main(String[] args) { // TODO Auto-generated method stub int[][] result=getResult(1, 3, 3); for(int i=0;i<result.length;i++){ for(int j=0;j<result[0].length;j++){ System.out.print(result[i][j]+" "); } System.out.println(""); } }

}

No.3

求一个二叉树的最优(权值最小)路径.

 输入：二叉树  输出：最优路径的权值。

这题的考点主要是运用递归函数遍历二叉数，我使用了深度遍历。

//二叉数类

public class TNode {     public int value;     public TNode leftNode;     public TNode rightNode; }

public class TNodeTest { public static int getMinPathVal(TNode t){ int sum=0; sum+=t.value; if(t.leftNode!=null&&t.rightNode!=null){ if(t.leftNode.value<t.rightNode.value){ sum+=getMinPathVal(t.leftNode); } else{ sum+=getMinPathVal(t.rightNode); } } else{ if(t.leftNode==null&&t.rightNode!=null){ sum+=getMinPathVal(t.rightNode); } else if(t.leftNode!=null&&t.rightNode==null){ sum+=getMinPathVal(t.leftNode); } else{ System.out.println("遍历到叶子"); } } return sum; }

//测试 public static void main(String[] args) { // TODO Auto-generated method stub TNode t=new TNode(); t.value=5; t.leftNode=new TNode(); t.rightNode=new TNode(); t.leftNode.value=10; t.rightNode.value=20; t.leftNode.leftNode=new TNode(); t.leftNode.leftNode.value=60; System.out.println(getMinPathVal(t)); } }