9.23 OPPO笔试算法题

又捞起来笔试了。

第一题

遍历交换就可以了

package bishi;

import java.util.Scanner;

public class oppo1 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String sint = scan.nextLine();
        int T = Integer.parseInt(sint);

        while(T-->0){
            String a = scan.nextLine();
            String b = scan.nextLine();

            if(a.equals(b)){
                System.out.println("Yes");
            }else if(a.length() != b.length()){
                System.out.println("No");
            }else {
                int H = 0;
                for (int i = 0; i < a.length() - 1; i++) {

                    StringBuffer sb = new StringBuffer(a);
                    char c1 = sb.charAt(i);
                    sb.setCharAt(i, sb.charAt(i+1));
                    sb.setCharAt(i+1,c1);
                    String s3 = sb.toString();

                    if (s3.equals(b)) {
                        System.out.println("Yes");
                        H = 1;
                        break;
                    }
                }
                if(H == 0){
                    System.out.println("No");
                }

            }





        }
    }
}

第二题

有些特殊情况需要处理比如

3 1

1 1

1 2

1 3

这里要处理1 1

还有

1 2

2 1

1 3

这里要处理1 2和2 1这种无限循环的问题我办法是把第二个2 1直接改为1 1

package bishi;


import java.util.Scanner;

public class oppo2 {
    static int res = 1;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int c = sc.nextInt();
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 2; j++) {
                arr[i][j] = sc.nextInt();

            }
        }
        for (int i = 0; i < n; i++) {
            findWrong(arr,i,arr[i][1]);
        }
        findRes(arr,c);
        System.out.println(res);

    }
    private static void findWrong(int[][] arr, int start, int j) {
        for (int i = start+1; i < arr.length; i++) {
            if(arr[i][0] == j){
                arr[i][0] = arr[i][1];
            }
        }


    }

    private static void findRes(int[][] arr, int j) {
        for (int i = 0; i < arr.length; i++) {
            if(arr[i][0] == j && arr[i][0] != arr[i][1]){
                res++;
                findRes(arr,arr[i][1]);

            }
        }

    }
}

第三题

那个什么树的连接根本没用，就是把问题转为是一个数组变为有序的最小交换次数就可以了，然后就很简单。

package bishi;

import java.util.Scanner;

public class oppo3 {
    static int res = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        for (int i = 0; i < n; i++) {
            if(arr[i] != i+1){
                res++;
                swap(arr,i,i+1);
            }

        }
        System.out.println(res);

    }

    private static void swap(int[] arr,int x, int z) {

        for (int n = 0; n < arr.length; n++) {
            if(arr[n] == z){
                int temp = arr[x];
                arr[x] = arr[n];
                arr[n] = temp;


            }

        }

    }
}

#OPPO##笔试#