JZ12 矩阵中的路径🥣
矩阵中的路径_牛客题霸_牛客网 (nowcoder.com)
题目描述🥣
解题思路🥣
这道题是一道标准的dfs例题
通用板子如下！
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
因为是一个二维矩阵 首先两层for循环 遍历全部的点
接着就是最重要的dfs函数
一个点向周围四个地方递归
递归之后再把当前的坐标复原
代码详解🥣
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param matrix char字符型二维数组 * @param word string字符串 * @return bool布尔型 */ public boolean hasPath (char[][] matrix, String word) { char worlds[]= word.toCharArray(); for(int i=0;i<matrix.length;i++){ for( int j=0;j<matrix[0].length;j++){ if(dfs(matrix,worlds,i,j,0)) return true; } } return false; // write code here } boolean dfs(char[][] matrix,char []world , int i,int j,int index){ //处理边界问题 index表示的是查找到字符串word的第几个字符， if(i>=matrix.length||i<0||j>=matrix[0].length||j<0||matrix[i][j]!=world[index]) return false; //如果world 每个字符串都找到了 直接return true if(index==world.length-1) return true; char temp=matrix[i][j]; //把走过的坐标标记下来 最后输出 //修改当前坐标的值 matrix[i][j]=' '; //从当前坐标的上下左右四个方向去寻找 递归 boolean res=dfs(matrix,world,i+1,j,index+1)|| //向右递归 dfs(matrix,world,i-1,j,index+1)||//向左递归 dfs(matrix,world,i,j-1,index+1)||//向下递归 dfs(matrix,world,i,j+1,index+1);//向上递归 //递归后再把当前坐标复原 matrix[i][j]=temp; return res; }
过辣~
JZ16 数值的整数次方🥣
数值的整数次方_牛客题霸_牛客网 (nowcoder.com)
题目描述🥣
解题思路🥣
- 先处理次方数为负数的情况，将底数化为分数解决。
- 遍历次方数的次数，不断累乘底数。
代码详解🥣
import java.util.*; public class Solution { public double Power(double base, int exponent) { //先处理次方数是负数的情况 if(exponent<0){ base=1/base; exponent=-exponent; } double ret=1.0; for(int i=0;i<exponent;i++){ ret*=base; } return ret; } }
一声清脆的声音 过过辣
JZ40 最小的K个数🥣
最小的K个数_牛客题霸_牛客网 (nowcoder.com)
题目描述🥣
解题思路🥣
这道题直接用java 自带的排序函数 Arrays.sort()
代码详解🥣
import java.util.*; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) { ArrayList<Integer> list =new ArrayList<>(); //特判k=0时 直接返回 if(k==0) return list; Arrays.sort(input);//将数组从小到大升序排列 去最前面k个即可 for(int i=0;i<k;i++){ list.add(input[i]); } return list; } }
