Niuke brush questions - Sword finger offer (phase II)

  Preface

Author's brief introduction ： Hello, friends , I'm your classmate Xiao Wang

Personal home page ： Xiao Wang

Series column ： Niu Ke brushes the question column

Recommend a very popular interview 、 Brush Title artifact Click jump to enter the website

What I think Xiao Wang wrote is good Please use your hands give the thumbs-up Collection   Comment on

Today's question brushing series is ： The finger of the sword offer The second phase

 

 

  There are many question banks Knowledge of heel Sutra I really have a good conscience ！！

Catalog

JZ12  Path in matrix 🥣

Title Description 🥣

Their thinking 🥣

Code details 🥣

Too hot ~ JZ16  Integer power of value 🥣

Title Description 🥣

Their thinking 🥣

Code details 🥣

JZ40  The smallest K Number 🥣

Title Description 🥣

Their thinking 🥣

Code details 🥣

JZ12  Path in matrix 🥣

Path in matrix _ Niuke Tiba _ Cattle from (nowcoder.com)

Title Description 🥣

 

 

Their thinking 🥣

This problem is a standard dfs Example

The general board is as follows ！

  if Meet the end condition :
        result.add( route )
        return
    
    for choice in Selection list :
        To make a choice
        backtrack( route , Selection list )
        Unselect

Because it is a two-dimensional matrix First, two layers for loop Traverse all points

Then there is the most important dfs function  

A point recurses to four places around

Recursion and then restore the current coordinates

Code details 🥣

import java.util.*;


public class Solution {
    /**
     *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly 
     *
     * 
     * @param matrix char Character type 2D array  
     * @param word string character string  
     * @return bool Boolean type 
     */
    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){
        // Dealing with border issues  index It means to find a string word The first character of ,
        if(i>=matrix.length||i<0||j>=matrix[0].length||j<0||matrix[i][j]!=world[index])
        return false;
        // If world  Every string is found   direct return true
        if(index==world.length-1)
            return true;
        char temp=matrix[i][j]; // Mark the coordinates you have passed   The final output 
        // Modify the value of the current coordinate 
        matrix[i][j]=' ';
        // Look up, down, left and right from the current coordinates   recursive 
        boolean res=dfs(matrix,world,i+1,j,index+1)|| // Right recursion 
            dfs(matrix,world,i-1,j,index+1)||// Left recursion 
            dfs(matrix,world,i,j-1,index+1)||// Down the recursive 
            dfs(matrix,world,i,j+1,index+1);// Recursion up 
            // After recursion, restore the current coordinates 
            matrix[i][j]=temp;
            return res;
        
    }

 

 

 

Too hot ~ 
JZ16  Integer power of value 🥣

Integer power of value _ Niuke Tiba _ Cattle from (nowcoder.com)

Title Description 🥣

 

Their thinking 🥣

• First deal with the case where the power is negative , Convert the base number into a fraction to solve .
• The number of times to traverse the power number , Keep multiplying the base number .

 

 

Code details 🥣

import java.util.*;
public class Solution {
    public double Power(double base, int exponent) {
        // First deal with the case that the power number is negative 
        if(exponent<0){
            base=1/base;
            exponent=-exponent;
            
            
        }
        double ret=1.0;
        for(int i=0;i<exponent;i++){
            ret*=base;
        }
        return ret;
        
        
        
        
  }
}

 

A clear voice Too spicy   

JZ40  The smallest K Number 🥣

The smallest K Number _ Niuke Tiba _ Cattle from (nowcoder.com)

Title Description 🥣

 

Their thinking 🥣

This problem is directly used java Built in sorting function Arrays.sort()

Code details 🥣

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list =new ArrayList<>();
        // Special judgement k=0 when   Go straight back to 
        if(k==0) return list;
        
        Arrays.sort(input);// Arrange the array in ascending order from small to large   Go to the front k Just one 
        for(int i=0;i<k;i++){
            list.add(input[i]);
        }
        return list;
        
    }
}

 

Niuke is an interview Or brush the questions It's all very useful What are you waiting for to register Follow classmate Wang to brush questions Enter the big factory ！   Niu Ke brushes the question bank