笔试题整理

[TOC]

1.王大锤

//这题就暴力扫一遍就可以了，碰到3个连续的或者AABB删掉那个字符即可。。。
//当时没做出来。。。菜是原罪！
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = Integer.parseInt(sc.nextLine());
            for(int i = 0; i < n; i++){
                StringBuilder sb = new StringBuilder(sc.nextLine());
                for(int j = 2; j < sb.length(); j++){
                    if(sb.charAt(j) == sb.charAt(j - 1) 
                       && sb.charAt(j - 1) == sb.charAt(j - 2)){
                        sb.deleteCharAt(j);
                        j--;
                    }
                    else if(isPattern(sb, j - 3, j)){
                        sb.deleteCharAt(j);
                        j--;
                    }
                }
                System.out.println(sb.toString());
            }
        }
        sc.close();
    }
    public static boolean isPattern(StringBuilder sb, int i, int j){
        if(i < 0) return false;
        return sb.charAt(i) == sb.charAt(i + 1) &&
                sb.charAt(j - 1) == sb.charAt(j);
    }
}

2.雀魂

import java.util.Scanner;

/**
 * 回溯法
 */
public class Main {


    private static int[] arr = new int[13];
    private static int[] count;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);


        count = new int[9];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scanner.nextInt();
            ++count[arr[i]-1];
        }


        int winCount = 0;
        // 选择1到9中的一个作为第14张牌，然后判断是否胡牌
        for (int i = 1 ; i <= 9; i++) {
            if(count[i-1]<4){
                ++count[i-1];
                if(win()){
                    ++winCount;
                    System.out.print(i);
                    System.out.print(" ");
                }
                --count[i-1];
            }
        }
        if(winCount==0){
            System.out.println(0);
        }
    }
    public static boolean win(){
        // 从1到9 中选择一个作为雀头, 然后判断剩余的牌是否构成4对
        for (int i = 1; i <= 9; i++) {
            if(count[i-1]<2){
                continue;
            }
            count[i-1]-=2;
            if(hasTriples(4)){
                count[i-1]+=2;
                return true;
            }
            count[i-1]+=2;
        }
        return false;
    }

    public static boolean hasTriples(int n){
        if(n==0){
            return true;
        }
        // 1到9，每一张牌尝试三张或顺子
        for (int i = 1; i <= 9; i++) {
            if(count[i-1]>=3){
                count[i-1]-=3;
                boolean subHashTriples = hasTriples(n-1);
                count[i-1]+=3;
                if(subHashTriples){
                    return true;
                }
            }
            if(i<=7  && count[i-1]>0 && count[i] > 0 && count[i+1]>0){
                --count[i-1];
                --count[i];
                --count[i+1];
                boolean subHasTriples = hasTriples(n-1);

                ++count[i-1];
                ++count[i];
                ++count[i+1];
                if(subHasTriples){
                    return true;
                }
            }
        }
        return false;
    }
}

3.特工

import java.util.*;

public class Main {
    private int mod = 99997867;

    private void sln() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(), D = sc.nextInt();
        long cnt = 0;
        if (N <= 2) {
            System.out.println(-1);
            return;
        }
        int[] locs = new int[N];
        for (int i = 0; i < N; i++) {
            locs[i] = sc.nextInt();
        }
        sc.close();
        int left = 0, right = 2;
        while (right < N) {
            if (locs[right] - locs[left] > D) left++;
            else if (right - left < 2) right++;
            else {
                cnt += calC(right - left);
                right++;
            }
        }
        cnt %= mod;
        System.out.println(cnt);
    }

    private long calC(long num) {
        return num * (num - 1) / 2;
    }


    public static void main(String[] args) {
        new Main().sln();
    }
}

3。迷宫

由于新冠肺炎疫情的爆发，小明养在宿舍的小昆虫已经很久很久都没有人管了。小昆虫已经饿的不行了，必须出来找东西吃，可是出来之后需要走出一个迷宫。小昆虫每次可以朝上、下、左、右四个方向之一走一步，且只要走出任意一条边界线即可逃出迷宫。这只小昆虫曾感染过X星的一种奇异病毒，目前还没有发现任何副作用，但是却拥有了一项特异功能——破坏障碍物。
假设小昆虫在一个NM的迷宫中，”@”代表小昆虫的初始位置，”.”代表可以通过的空地，”“代表可以破坏的障碍物，”#”代表不可破坏的障碍物。请问小昆虫最少需要使用多少次特异功能才可以逃出迷宫？

输入描述
多组数据，第1行有1个正整数T，表示有T组数据。（T<=100）
对于每组数据，第1行有两个整数N和M。(1<=N, M<=1000)
接着N行，每行有一个长度为M的字符串，表示N*M的迷宫。
输出描述
输出一个整数，表示使用特异功能的最少次数。如果小昆虫不能走出迷宫，则输出-1。

样例输入
3
3 3
###
#@*

3 4
####
#@.*
*.
3 3
.#.
#@#
.#.

import java.util.PriorityQueue;
import java.util.Scanner;

public class D2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String st = sc.nextLine();
       int t = Integer.parseInt(st);
        for (int i = 0; i < t; i++) {
            String str = sc.nextLine();
            String[] strs = str.split(" ");
            int n =Integer.parseInt(strs[0]);    //行数
            int m =Integer.parseInt(strs[1]);    //列数

            char[][] board = new char[n][m];
            int x = -1;
            int y = -1;
            for (int j = 0; j < n; j++) {
                String s = sc.nextLine();
                for (int k = 0; k < m; k++) {
                    board[j][k]=s.charAt(k);
                    if (board[j][k] == '@') {
                        x = k;    //列号
                        y = j;    //行号
                    }
                }
            }
            boolean[][] used = new boolean[n][m];
            int[][] move = new int[4][2];
            move[0][0]=0;
            move[0][1]=1;
            move[1][0]=0;
            move[1][1]=-1;
            move[2][0]=1;
            move[2][1]=0;
            move[3][0]=-1;
            move[3][1]=0;

            PriorityQueue<Integer> list = new PriorityQueue<>();
            //System.out.println(t +" "+n+ " "+m+" "+x+" "+y );
            dis(x,y,board,used,list,0,move);
            if(list.size()>0){
                System.out.println(list.poll());
            }else{
                System.out.println("-1");
            }


        }
    }

    public static void dis(int x,int y,char[][] board,boolean[][] used, PriorityQueue<Integer> list,int count,int[][] move){
        if(x<=0||x>=board[0].length-1||y<=0||y>=board.length-1){     //第3个或写成了与
            //System.out.println(count);
            list.add(count);
            return;
        }
        for (int i = 0; i < 4; i++) {
            x=x+move[i][0];
            y=y+move[i][1];
            if(x>=0&&x<board[0].length&&y>=0&&y<board.length&&!used[y][x]){
                used[y][x] = true;
                if (board[y][x]=='*'){
                    dis(x,y,board,used,list,count+1,move);
                    // System.out.println(count);
                }else if (board[y][x]=='.'){
                    dis(x,y,board,used,list,count,move);
                }

                used[y][x] = false;
            }
            x-=move[i][0];
            y-=move[i][1];
        }


    }
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int bfs(vector<string> grid)
{
    vector<vector<char>> direct{{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
    queue<vector<int>> que_;
    int hei = grid.size();
    int wid = grid[0].length();
    int result = -1;
    vector<vector<int>> visited(hei, vector<int>(wid, -1));

    for (int i = 0; i < hei; i++)
    {
        for (int j = 0; j < wid; j++)
        {
            if (grid[i][j] == '@')
            {
                que_.push({i, j, 0});
                visited[i][j] = 0;
            }
        }
    }

    while (!que_.empty())
    {
        auto cur = que_.front();
        que_.pop();
        if (cur[0] == 0 || cur[0] == hei - 1 || cur[1] == 0 || cur[1] == wid - 1)
        {
            if (cur[2] < result || result == -1)
            {
                result = cur[2];
            }
            continue;
        }
        for (int i = 0; i < 4; i++)
        {
            int next_y = cur[0] + direct[i][0];
            int next_x = cur[1] + direct[i][1];
            int last_time = cur[2];
            if (visited[next_y][next_x] != -1 && visited[next_y][next_x] <= last_time + 1)
            {
                continue;
            }
            visited[next_y][next_x] = last_time + 1;
            if (grid[next_y][next_x] == '.')
            {
                que_.push({next_y, next_x, last_time});
            }
            else if (grid[next_y][next_x] == '*')
            {
                que_.push({next_y, next_x, last_time + 1});
            }
        }
    }

    return result;
}

int main()
{
    int t, n, m;
    cin >> t;
    vector<vector<string>> grids(t);
    for (int i = 0; i < t; i++)
    {
        cin >> n;
        cin >> m;
        grids[i].resize(n);
        for(int j = 0; j < n; j++)
        {
            cin >> grids[i][j];
        }
    }

    for (auto grid : grids)
    {
        cout << bfs(grid) << endl;
    }


    return 0;
}

public class hello {//100 999
    static int[][] dir={{0,1},{1,0},{0,-1},{-1,0}};
    static int startX,startY;
  //  static int endX,endY;
    static int min=Integer.MAX_VALUE;
    static int[][] vis;
    static Scanner sc=new Scanner(System.in);
    public static void main(String[] args) {
    int x=sc.nextInt();

    while(x-->0)
    {
        int n=sc.nextInt();
        int m=sc.nextInt();
        char[][] matrix=new char[n][m];
        for(int i=0;i<n;i++)
        {
            matrix[i]=sc.next().toCharArray();
          //  sc.nextLine();
            for(int j=0;j<m;j++)
            {
             if(matrix[i][j]=='@')
             {
                 startX=i;
                 startY=j;
             }
            }
        }
        vis=new int[n][m];
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                vis[i][j]=-1;
            }
        }
        int count=0;
        Queue<Node> q=new LinkedList<>();
        //
        min=Integer.MAX_VALUE;
        q.add(new Node(startX,startY));
        BFS(matrix,q);
        System.out.println(min);
    }
    }

    private static void BFS(char[][] matrix,Queue<Node> q) {
    while(!q.isEmpty()) {
        int size = q.size();
        while (size-- > 0) {
            Node nowNode = q.poll();
            int i = nowNode.x, j = nowNode.y;
            vis[i][j]=nowNode.step;
            if (i == 0 || i == matrix.length - 1
                    || j == 0
                    || j == matrix[0].length - 1
            ) {
                min=Math.min(vis[i][j],min);
                continue;
            }
            for (int[] d : dir) {
                int newX = d[0] + i;
                int newY = d[1] + j;
                if (matrix[newX][newY] == '#') {
                    continue;
                }
                if(vis[newX][newY]!=-1 && vis[newX][newY]<=nowNode.step+1)
                {
                    continue;
                }
                Node newNode = new Node(newX, newY);
                if (matrix[newX][newY] == '*') {

                    newNode.step =nowNode.step+1;
                }
                else if(matrix[newX][newY] == '.')
                {
                    newNode.step =nowNode.step;
                }
                q.add(newNode);
            }
        }

    }
    //  ####
        // ####
        // #@.*
        // **.*
        //
        //


    }
    static class Node
    {
        int x;
        int y;
        int step;
        Node(int a,int b)
        {
            x=a;
            y=b;

        }
    }

}

4.