头像

昆卡

1




离线:10小时前


最近来访(0)


昆卡
2天前

java中没有swap函数,也不能对字符串进行直接操作,所以改变x的位置的操作需要先转化为char数组,然后再手写swap函数,再用String的valueOf()方法将char数组转化为字符串保存

import java.util.*;
import java.io.*;

public class Main{
    //本题难点需要进行状态更新,每次变换x的位置时,需要把当前状态记录下来,防止下次再次遍历出现死循环
    //如果使用二维数组来保存数据,很难实现状态更新
    static int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
    static Queue<String> qu = new LinkedList<String>();
    static Map<String, Integer> map = new HashMap<String, Integer>();
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String st = br.readLine().replace(" ", "");
        int stx=0,sty=0;
        System.out.print(bfs(st));
    }
    public static int bfs(String st){
        map.put(st, 0);
        qu.add(st);
        while(!qu.isEmpty()){
            st = qu.poll();
            if(st.equals("12345678x")) return map.get(st);
            int dis = map.get(st);
            int x = st.indexOf('x')/3;//将字符串转化为想象中的一个二维数组,记录x的横坐标
            int y = st.indexOf('x')%3;//将字符串转化为想象中的一个二维数组,记录x的纵坐标
            int xdis = st.indexOf('x');
            char[] sc = st.toCharArray();
            for(int i=0;i<4;i++){
                int newx = x+dir[i][0],newy = y+dir[i][1];
                if(newy<3&&newx>=0&&newx<3&&newy>=0){
                    char temp = sc[xdis];
                    sc[xdis]= sc[newx*3+newy];
                    sc[newx*3+newy] = temp;
                    if(!map.containsKey(String.valueOf(sc))) {//如果当前搜索的状态已经出现过那么久直接跳过,否则加入队列
                        map.put(String.valueOf(sc), dis+1);
                        qu.add(String.valueOf(sc));
                    }
                    temp = sc[xdis];
                    sc[xdis]= sc[newx*3+newy];
                    sc[newx*3+newy] = temp;
                }
            }
        }
        return -1;
    }
}



昆卡
2天前
import java.util.*;
import java.io.*;

public class Main{
    public static int N = 100010,tn,to;
    static int[] nums = new int[N];//数字栈
    static char[] op = new char[N];//操作符栈
    static Map<Character,Integer> map = new HashMap<Character,Integer>(){{
        put('(',0);put('+',1);put('-',1);put('*',2);put('/',2);

    }};//优先级map
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] s = br.readLine().toCharArray();
        for(int i=0;i<s.length;i++){
            char x = s[i];
            if(s[i]>='0'&&s[i]<='9'){//如果是不是1位数则需要循环读取
                int j = i,t = 0;
                while(j<s.length&&s[j]>='0'&&s[j]<='9'){
                    t = t*10+s[j++]-'0';
                }
                i=j-1;
                nums[++tn]=t;
            }
            else if(x=='(') op[++to]=x;
            else if(x==')'){
                while(op[to]!='(') operate();
                to--;
            }
            else{
                while(to!=0&&map.get(x)<=map.get(op[to])) operate();
                op[++to]=x;
            }


        }
        while(to!=0) operate();//操作剩下的数
        System.out.print(nums[tn]);
    }
    public static void operate(){
        int b = nums[tn--];
        int a = nums[tn--];
        char oop = op[to--];
        int res  = 0;
        if(oop=='/') res=a/b;
        else if(oop=='+') res=a+b;
        else if(oop=='-') res=a-b;
        else if(oop=='*') res=a*b;
        nums[++tn]=res;
    }
}