当前位置：网站首页>牛客刷题篇——剑指offer （第二期）

牛客刷题篇——剑指offer （第二期）

2022-07-23 04:30:00 【学好c语言的小王同学】

前言
作者简介：友友们大家好，我是你们的小王同学
个人主页：小王同学
系列专栏：牛客刷题专栏
推荐一款非常火的面试、刷题神器点击跳转进入网站
觉得小王写的不错的话麻烦动动小手点赞收藏评论
今天给大家带来的刷题系列是：剑指offer 第二期

里面有非常多的题库跟面经知识真的非常良心了！！

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;
        
    }
}