#牛客春招刷题训练营# + https://www.nowcoder.com/discuss/726480854079250432

题目地址

https://www.nowcoder.com/practice/253986e66d114d378ae8de2e6c4577c1?channelPut=w25springcamp

https://www.nowcoder.com/practice/48b3cb4e3c694d9da5526e6255bb73c3?channelPut=w25springcamp

https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc?channelPut=w25springcamp

提取不重复的整数

开一个单独的 boolean 数组记录当前元素是否出现

如果已经出现过了

如果没有出现 输出 更新数组状态

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) {
            boolean arr[]=new boolean[10]; // 注意 while 处理多个 case
            String str=in.next();
            for(int i=str.length()-1;i>=0;i--){
                if(arr[str.charAt(i)-'0']==false){
                    System.out.print(str.charAt(i));
                    arr[str.charAt(i)-'0']=true;
                }    
            }
        }
    }
}

句子逆序

要注意 Java 读取一行字符串

String str=in.nextLine();

逆序输出数组即可

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { 
            // 注意 while 处理多个 case
            String str=in.nextLine();
            String[] arr=str.split(" ");
            for(int i=arr.length-1;i>=0;i--){
                System.out.print(arr[i]+" ");
            }
        }
    }
}

迷宫问题

递归 DFS 记忆化搜索

四个方向

辅助数组 visited

如果访问过了 就无需再访问

注意要回溯状态

到达终点后回溯状态

每一次递归结束后回溯状态

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static List<int[]> list;
    static int n;
    static int m;
    static int arr[][];
    static boolean visited[][];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) {
            ArrayList<int[]>ansList=new ArrayList<>();
            n=in.nextInt();
            m=in.nextInt();
            arr=new int[n][m];
            visited=new boolean[n][m];
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    arr[i][j]=in.nextInt();
                }
            }
            dfs(0,0,ansList);
            for(int arr[]:list){
                System.out.print("("+arr[0]+","+arr[1]+")");
                System.out.println("");
            }
        }
    }
    // 当前横坐标 当前纵坐标 存点
    private static void dfs(int i,int j,ArrayList<int []>anslist){
        // 递归出口
        if(i<0||j<0||i>n-1||j>m-1||arr[i][j]==1||visited[i][j]==true){
            return;
        }
        anslist.add(new int[]{i,j});
        visited[i][j]=true;
        if(i==n-1&&j==m-1){
            list=new ArrayList<>(anslist);
            visited[i][j]=false;
            anslist.remove(anslist.size()-1);
            return;
        }
        // 递归函数
        dfs(i+1,j,anslist);
        dfs(i,j+1,anslist);
        dfs(i-1,j,anslist);
        dfs(i,j-1,anslist);
        visited[i][j]=false;
        anslist.remove(anslist.size()-1);
    }
}