dfs

1.迷宫

public class Point {
    int x;
    int y;
    public Point(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }
public class keda2 {
    List<Point> temp =new LinkedList<>();
    List<Point> result =new LinkedList<>();
    int minCount =Integer.MAX_VALUE;
    public  ArrayList<Point> winMazeGift(int[][] maze) {
        // write code here
        Point gift =null;
        boolean flag=false;
​
        int n = maze.length;
        int m = maze[0].length;
        ArrayList<Point> ans = new ArrayList<>();
        //找到礼物点
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                    if (maze[i][j] == 8) {
                        gift=new Point(i,j);
                        flag=true;
                        temp.add(new Point(i,j));
                        break;
                    }
            }
            if(flag) break;
        }
        //从礼物点回溯
        dfs(gift,0,maze);
        //正序输出
        ArrayList<Point> finalResult=new ArrayList<>();
        while (!result.isEmpty()){
            finalResult.add(result.get(result.size()-1));
            result.remove(result.size()-1);
        }
        return finalResult;
    }
    private void dfs(Point gift,int count,int [][] maze){
        //若走到边界，说明发现了路径，比较是否最短
        if(gift.x==0||gift.x==3||gift.y==0||gift.y==3){
            if(count< minCount){
                result =new LinkedList<>(temp);
                minCount =count;
            }
            return;
         }
        //判断下个点能不能走，上下左右四个方向，
        if(maze[gift.x-1][gift.y]==0){
            Point point1=new Point(gift.x-1,gift.y);
            //下个点加入路径
            temp.add(point1);
            //将当前点设置为-1，表示不可走(不加的话来回走，超时)
            int kk=maze[gift.x][gift.y];
            maze[gift.x][gift.y]=-1;
            //向下递归
            dfs(point1,count+1,maze);
            maze[gift.x][gift.y]=kk;
            temp.remove(temp.size()-1);
        }
        if(maze[gift.x+1][gift.y]==0){
            Point point2=new Point(gift.x+1,gift.y);
            temp.add(point2);
            int kk=maze[gift.x][gift.y];
            maze[gift.x][gift.y]=-1;
            dfs(point2,count+1,maze);
            maze[gift.x][gift.y]=kk;
            temp.remove(temp.size()-1);
        }
        if(maze[gift.x][gift.y-1]==0){
            Point point3=new Point(gift.x,gift.y-1);
            temp.add(point3);
            int kk=maze[gift.x][gift.y];
            maze[gift.x][gift.y]=-1;
            dfs(point3,count+1,maze);
            maze[gift.x][gift.y]=kk;
            temp.remove(temp.size()-1);
        }
​
        if(maze[gift.x][gift.y+1]==0){
            Point point3=new Point(gift.x,gift.y+1);
            temp.add(point3);
​
            int kk=maze[gift.x][gift.y];
            maze[gift.x][gift.y]=-1;
            dfs(point3,count+1,maze);
            maze[gift.x][gift.y]=kk;
            temp.remove(temp.size()-1);
        }
    }
}
​
​
​

2.小数

public class keda {
    public static void main(String[] args) {
        seqSum(2);
    }
​
    public static float seqSum (int n) {
        double p=1;
        double q=2;
        double total=0;
        double sum=0;
        for(int i=1;i<=n;i++){
            total=p/q;
            double temp=q;
            q=p+q;
            p=temp;
            sum+=total;
        }
        NumberFormat nf=NumberFormat.getNumberInstance();
        nf.setMaximumFractionDigits(2);
        //         return (float) String.format("%。2f",total);
        return  Float.parseFloat(nf.format(total));
    }
}

3.

两个正整数a，b；有一种操作：删除这两个数中的一个数位，使得a是b的倍数或者b是a的倍数。问最少要操作几次。如 a = 1246，b = 9；可以删除a的一个数位得到126，是9的倍数，因此最少操作一次。 一个字符串，只包含'r'、'e'、'd'三种字符，有一种操作：可以将一个字符替换为其他两种字符。规定字符'e'的左右两个字符有'r'和'd'的，就叫做好'e'。现在需要使字符串中的好'e'数量最多，问最少需要操作多少次？ 举例：reddr，操作一次变成 reder，有两个好'e'。 类似于锯齿数组。给一个数组，每次可以对一个元素值加1操作，现在需要保证数组中的每个元素的左右两个元素相等，且中间的元素不等于左右两个元素。问最少需要操作多少次。 网易给出的样例是： [1,1,4,5,1,4]，最终变成[4,5,4,5,4,5]。为什么到处都有homo啊(恼)。 又是三元组问题。一个数组，n <= 100000，arr[i] <= 10^9；需要找到这样的三元组<i,j,k>，i < j < k，且 ai == ak && ai > aj。问有多少个。

1.

public class aug1 {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int a= in.nextInt();
        int b=in.nextInt();
        String valuea=a+"";
        String valueb=b+"";
        int n=valuea.length();
        int m=valueb.length();
        List<String> ans1= cutDownList(valuea.toString());
        List<String> ans2= cutDownList(valueb.toString());
        int res=Integer.MAX_VALUE;
        for (int i = 0; i <ans1.size() ; i++) {
            for (int j = 0; j < ans2.size() ; j++) {
                String tempa=ans1.get(i);
                String tempb=ans2.get(j);
                if(is(Integer.parseInt(tempa),Integer.parseInt(tempb))){
                    int tmp=n-tempa.length()+m-tempb.length();
                    res=Math.min(res,tmp);
                }
            }
        }
        System.out.println(res);
    }
    public static boolean is(int a,int b){
        if(a%b==0 || b%a ==0) return true;
        else return  false;
    }
    public  static List<String> cutDownList(String str){
        char [] chars=str.toCharArray();
        String path="";
        List<String> ans=new ArrayList<>();
        process(chars,0,ans,path);
        return ans;
    }
    public  static void process(char[] chars,int index,List<String> ans,String path){
      if(index ==chars.length){
          if(path.equals("")) return;
          ans.add(path);
          return;
      }
      process(chars,index+1,ans,path);
      process(chars,index+1,ans,path+chars[index]);
​
    }
​
}

2.

/**
 * 输入6
 * 1 1 4 5 1 4
 * 输出11
 * {得到长城 {4,5,4,5,4,5}}
 */
public class aug2 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int nums[]=new int[n];
        for (int i = 0; i <n ; i++) {
            nums[i]=sc.nextInt();
        }
        int temp1=0,temp2=0;
        //long ans1=0,ans2=0;
        for (int i = 0; i <n ; i++) {
            if(i%2==1){
                //ans1+=nums[i];
                temp1=Math.max(temp1,nums[i]);
            }
            else {
               // ans2+=nums[i];
                temp2=Math.max(temp2,nums[i]);
            }
        }
        if(temp1==temp2){
            temp2++;
        }
        long res=0;
        for (int i = 0; i <n ; i++) {
            if(i%2==1){
                res+=temp1-nums[i];
            }
            else {
                res+=temp2-nums[i];
            }
        }
        System.out.println(res);
    }
}

3.

public class aug3 {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        String str=in.nextLine();
        char [] ch=str.toCharArray();
        int n=ch.length;
        if(n%2==0){
            long ans=func(ch,0,n-2,'a');
            for (int i = 0; i <n ; i++) {
                long tmp=func(ch,0,i,'a')+func(ch,i+1,n-1,'a');
                ans=Math.min(ans,tmp);
            }
            System.out.println(ans);
        }else {
            long ans=func(ch,0,n-1,'a');
            System.out.println(ans);
        }
        return;
    }
    public static long func(char[] ch,int begin,int end,char first) {
        if(first == 'a'){
            return Math.min(func(ch,begin,end,'r'),func(ch,begin,end,'d'));
        }
        if(begin>=end){
            return 0;
        }
        char next=first;
        long cnt =0;
        for (int i = begin; i <=end; i++) {
            if((i-begin)%2 == 0){
                if(ch[i] != next){
                    cnt++;
                }
                next =next=='r'?'d':'r';
            }else {
                if(ch[i] != 'e'){
                    cnt++;
                }
            }
        }
        return cnt;
    }
}
​

4.

public class aug4 {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int nums[]=new int[n];
        for (int i = 0; i < n; i++) {
            nums[i]=in.nextInt();
        }
        int res=0;
        for (int i = 0; i <n ; i++) {
            int sum=0;
            for (int j = i+1; j <n ; j++) {
                if(nums[j]<nums[i]){
                    sum++;
                }
                else if(nums[j]==nums[i]){
                    res+=sum;
                }
            }
        }
        System.out.println(res);
    }
}

5.zijie2

package com.zijie;
​
import java.util.Scanner;
​
/**
 * @Author:txd
 * @Date:2022/8/21
 * @Description：
 */
public class aug21_2 {
    public static int [][] visited;
     public static int x,y;
     public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        char [][] positions=new char[n][m];
        int [][] visitor=new int[n][m];
        for (int i = 0; i < n ; i++) {
            for (int j = 0; j < m ; j++) {
                positions[i][j]=sc.next().charAt(0);
            }
        }
        //找到出口点 xStart yStart
        for (int i = 0; i < n ; i++) {
            for (int j = 0; j < m ; j++) {
                if(positions[i][j]=='O'){
                    y=j;
                    x=i;
                    visitor[i][j]=1;
                }
             }
        }
         dfs(x-1,y,'D',positions,visitor);
         dfs(x+1,y,'U',positions,visitor);
         dfs(x,y-1,'R',positions,visitor);
         dfs(x,y+1,'L',positions,visitor);
         int ans=0;
         for (int i = 0; i < n ; i++) {
             for (int j = 0; j < m ; j++) {
                 if(visitor[i][j]==1){
                    ans++;
                 }
             }
         }
         System.out.println(n*m-ans);
​
    }
    public static void dfs(int i,int j,char c,char position [][],int visitor[][]){
        if(i==x&&j==y){
            return;
        }
        if(i<0 || i>=position.length ||j<0 ||j>=position[0].length){
            return;
        }
        if(position[i][j]=='.' || position[i][j]==c){
            visitor[i][j]=1;
            dfs(i-1,j,'D',position,visitor);
            dfs(i+1,j,'U',position,visitor);
            dfs(i,j-1,'R',position,visitor);
            dfs(i,j+1,'L',position,visitor);
        }
​
    }
}
​