不努力的话,天赋就会被收回

  menu

OJ作业-栈的应用

本人秉承着能不写代码就不写代码的原则,所以,能怎么简单就怎么来 ̄ω ̄=

问题 A: 数据转换

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Scanner;

/**
 * author 罗炜杰
 */

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            if(m == 0 && n == 0){
                break;
            }
            String a = BigInteger.valueOf(m).toString(n);
            System.out.println("(" + m + ")10->" + "(" + a + ")" + n);
        }
    }
}
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int a =n;
            Stack<Integer> stack = new Stack<Integer>();
            while(n != 0) {
                stack.push(n % m);
                n /= m;
            }
            StringBuffer sb = new StringBuffer();
            while(!stack.isEmpty()) {
                sb.append(stack.pop());
            }
            System.out.println("(" + a + ")10->(" + sb + ")" + m);
        }
    }
}

我把栈的实现抽取出来,后面的题目就不重复写了

栈的实现

/**
 * 栈的实现接口,规定了栈的主要方法
 *
 * @param <T>
 */
interface Stack<T> {

    public T push(T data);

    public T pop();

    public T peek();

    public boolean isEmpty();

    public int size();
}

/**
 * 自定义结点类
 *
 * @param <T>
 */
class Node<T> {
    T dataT;
    Node<T> nextNode;

    public T getDataT() {
        return dataT;
    }

    public void setDataT(T dataT) {
        this.dataT = dataT;
    }

    public Node<T> getNextNode() {
        return nextNode;
    }

    public void setNextNode(Node<T> nextNode) {
        this.nextNode = nextNode;
    }

    public Node(T dataT) {
        this.dataT = dataT;
        this.nextNode = null;
    }

    public Node() {
        super();
    }
}

/**
 * 实现Stack<T>接口,运用链表实现栈的基本方法
 *
 * @param <T>
 */
class LinkedStack<T> implements Stack<T> {

    private int size; // 栈的大小
    private Node<T> top; // 栈顶指针

    public LinkedStack() {
        size = 0;
        top = null;
    }

    /**
     * 进行入栈操作,先判断栈是否为空,如果为空,直接入栈,否则,用头插的方式将新结点插入链表头部
     *
     * @param data
     * @return
     */
    public T push(T data) {
        Node<T> newNode = new Node<T>(data);
        if (!isEmpty()) {
            newNode.setNextNode(top);
            top = newNode;
        } else {
            top = newNode;
        }
        size++;
        return data;
    }

    /**
     * 出栈操作,将栈顶元素弹出,同时删除栈顶元素,这里就是讲链表头部的数据return,栈顶指针向后移动
     *
     * @return 栈顶元素
     */
    public T pop() {
        T iT;
        if (!isEmpty()) {
            iT = top.getDataT();
            top = top.getNextNode();
            size--;
            return iT;
        } else {
            return null;
        }
    }

    /**
     * 查看栈顶元素,不弹出
     *
     * @return 栈顶元素
     */
    public T peek() {
        T iT;
        if (!isEmpty()) {
            iT = top.getDataT();
            return iT;
        } else {
            return null;
        }
    }

    /**
     * 判断栈是否为空,就是判断栈顶指针是否为空以及栈的大小是否为0
     *
     * @return
     */
    public boolean isEmpty() {
        if ((top == null) && (size == 0)) {
            return true;
        } else {
            return false;
        }
    }

    /**
     * 返回栈的大小
     *
     * @return
     */
    public int size() {
        return size;
    }
}

问题 B: 圆括号配对

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int count = 1;
        while (input.hasNext()) {
            String string = input.next();
            char ch;
            boolean flog = false;
            boolean flag = true;
            LinkedStack<String> ppz = new LinkedStack<String>();
            int a = 0;
            int b = 0;
            for (int i = 0; i < string.length(); i++) {
                ch = string.charAt(i);
                switch (ch) {
                    case '(':
                        ppz.push(ch + "");
                        a++;
                        break;
                    case ')':
                        b++;
                        if (i == 0) {
                            flag = false;
                        } else {
                            if (('(' + "").equals(ppz.pop())) {
                                flog = true;
                            } else {
                                flog = false;
                            }
                        }
                        break;
                }
            }
            if (flog && flag && a == b) {
                System.out.println("Case " + (count++) + ":共有" + a + "个\"(\"" + "和" + b + "个\")\"" + ",可配成"
                        + ((a + b) / 2) + "对.");
            } else {
                System.out.println("Case " + (count++) + ":共有" + a + "个\"(\"" + "和" + b + "个\")\"" + ",不可以配对.");
            }
        }
        input.close();
    }

    public static int Max(int m, int n) {
        if (m > n) {
            return m;
        } else {
            return n;
        }
    }
}

问题 C: 多种括号配对

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int count = 1;
        while (input.hasNext()) {
            String string = input.next();
            boolean flog = false;
            int a = 0, e = 0;
            int b = 0, f = 0;
            int c = 0, g = 0;
            int d = 0, h = 0;
            LinkedStack<String> ppz = new LinkedStack<String>();
            for (int i = 0; i < string.length(); i++) {
                char ch = string.charAt(i);
                switch (ch) {
                    case '(':
                        g++;
                        ppz.push(ch + "");
                        break;
                    case '{':
                        ppz.push(ch + "");
                        e++;
                        break;
                    case '[':
                        f++;
                        ppz.push(ch + "");
                        break;
                    case '<':
                        h++;
                        ppz.push(ch + "");
                        break;
                    case ')':
                        if (('(' + "").equals(ppz.pop())) {
                            flog = true;
                            c++;
                        } else {
                            flog = false;
                        }
                        break;
                    case ']':
                        if (('[' + "").equals(ppz.pop())) {
                            flog = true;
                            b++;
                        } else {
                            flog = false;
                        }
                        break;
                    case '}':
                        if (('{' + "").equals(ppz.pop())) {
                            flog = true;
                            a++;
                        } else {
                            flog = false;
                        }
                        break;
                    case '>':
                        if (('<' + "").equals(ppz.pop())) {
                            flog = true;
                            d++;
                        } else {
                            flog = false;
                        }
                        break;
                    default:
                        break;
                }
            }
            if (flog && (a == e) && (b == f) && (c == g) && (d == h)) {
                System.out.println("Case " + (count++) + ":配对。共有" + a + "对{}、" + b + "对[]、" + c + "对()、" + d + "对<>。");
            } else {
                System.out.println("Case " + (count++) + ":不配对。");
            }
        }
        input.close();
    }
}

问题 D: 求表达式的值

import java.util.ArrayList;
import java.util.Scanner;

/**
 * author 罗炜杰
 */

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.next(); // 算出来结果为-11.5
            Double result = Calculate(infixToSuffix(analysisExpression(str)));
            System.out.println(str + "=" + String.format("%.0f", result));
        }
    }

    /**
     * 解析表达式
     *
     * @param str
     * @return
     */
    public static ArrayList<String> analysisExpression(String str) {
        ArrayList<String> list = new ArrayList<String>();
        char[] arr = str.toCharArray();
        StringBuffer tmpStr = new StringBuffer();
        for (char c : arr) {
            if ((c >= '0') && (c <= '9') || (c == '.')) {
                tmpStr.append(c);
            } else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '('
                    || c == ')') {
                if (tmpStr.length() > 0) {
                    list.add(tmpStr.toString());
                    tmpStr.setLength(0);
                }
                list.add(c + "");
            }
        }
        if (tmpStr.length() > 0) {
            list.add(tmpStr.toString());
        }
        return list;
    }

    /**
     * 中缀转后缀 infix转suffix
     *
     * @param list
     * @return 后缀表达式
     */
    public static ArrayList<String> infixToSuffix(ArrayList<String> list) {
        ArrayList<String> strList = new ArrayList<String>();
        LinkedStack<String> stack = new LinkedStack<String>();
        String tmp;
        for (String s : list) {
            if (s.equals("(")) {
                stack.push(s);
            } else if (s.equals(")")) {
                while (!(tmp = stack.pop()).equals("(")) {
                    strList.add(tmp);
                }
            } else if (s.equals("*") || s.equals("/")) {
                while (!stack.isEmpty()) {
                    tmp = stack.peek();
                    if (tmp.equals("*") || tmp.equals("/")) {
                        stack.pop();
                        strList.add(tmp);
                    } else {
                        break;
                    }
                }
                stack.push(s);
            } else if (s.equals("+") || s.equals("-")) {
                while (!stack.isEmpty()) {
                    tmp = stack.peek();
                    if (!tmp.equals("(")) {
                        stack.pop();
                        strList.add(tmp);
                    } else {
                        break;
                    }
                }
                stack.push(s);
            } else {
                strList.add(s);
            }
        }
        while (!stack.isEmpty()) {
            strList.add(stack.pop());
        }
        return strList;
    }

    /**
     * 计算后缀表达式的值
     *
     * @param 后缀表达式
     * @return 最终结果的值
     */
    public static double Calculate(ArrayList<String> strList) {
        LinkedStack<Double> newStack = new LinkedStack<Double>();
        for (String s : strList) {
            if (s.equals("+") || s.equals("-") || s.equals("*")
                    || s.equals("/")) {
                double b1 = newStack.pop();
                double b2 = newStack.pop();
                if (s.equals("+")) {
                    newStack.push(b2 + b1);
                } else if (s.equals("-")) {
                    newStack.push(b2 - b1);
                } else if (s.equals("*")) {
                    newStack.push(b2 * b1);
                } else if (s.equals("/")) {
                    newStack.push(b2 / b1);
                }
            } else {
                newStack.push(Double.valueOf(s));
            }
        }
        return newStack.peek();
    }
}

问题 E: 求带空格的后缀表达式的值

import java.util.ArrayList;
import java.util.Scanner;

/**
 * author 罗炜杰
 */

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.nextLine();
            ArrayList<String> list = new ArrayList<String>();
            for(String s : str.split(" ")){
                list.add(s);
            }
            Double result = Calculate(list);
            System.out.println(String.format("%.0f", result));
        }
    }

    /**
     * 解析表达式
     *
     * @param str
     * @return
     */
    public static ArrayList<String> analysisExpression(String str) {
        ArrayList<String> list = new ArrayList<String>();
        char[] arr = str.toCharArray();
        StringBuffer tmpStr = new StringBuffer();
        for (char c : arr) {
            if ((c >= '0') && (c <= '9') || (c == '.')) {
                tmpStr.append(c);
            } else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '('
                    || c == ')') {
                if (tmpStr.length() > 0) {
                    list.add(tmpStr.toString());
                    tmpStr.setLength(0);
                }
                list.add(c + "");
            }
        }
        if (tmpStr.length() > 0) {
            list.add(tmpStr.toString());
        }
        return list;
    }

    /**
     * 中缀转后缀 infix转suffix
     *
     * @param list
     * @return 后缀表达式
     */
    public static ArrayList<String> infixToSuffix(ArrayList<String> list) {
        ArrayList<String> strList = new ArrayList<String>();
        LinkedStack<String> stack = new LinkedStack<String>();
        String tmp;
        for (String s : list) {
            if (s.equals("(")) {
                stack.push(s);
            } else if (s.equals(")")) {
                while (!(tmp = stack.pop()).equals("(")) {
                    strList.add(tmp);
                }
            } else if (s.equals("*") || s.equals("/")) {
                while (!stack.isEmpty()) {
                    tmp = stack.peek();
                    if (tmp.equals("*") || tmp.equals("/")) {
                        stack.pop();
                        strList.add(tmp);
                    } else {
                        break;
                    }
                }
                stack.push(s);
            } else if (s.equals("+") || s.equals("-")) {
                while (!stack.isEmpty()) {
                    tmp = stack.peek();
                    if (!tmp.equals("(")) {
                        stack.pop();
                        strList.add(tmp);
                    } else {
                        break;
                    }
                }
                stack.push(s);
            } else {
                strList.add(s);
            }
        }
        while (!stack.isEmpty()) {
            strList.add(stack.pop());
        }
        return strList;
    }

    /**
     * 计算后缀表达式的值
     *
     * @param 后缀表达式
     * @return 最终结果的值
     */
    public static double Calculate(ArrayList<String> strList) {
        LinkedStack<Double> newStack = new LinkedStack<Double>();
        for (String s : strList) {
            if (s.equals("+") || s.equals("-") || s.equals("*")
                    || s.equals("/")) {
                double b1 = newStack.pop();
                double b2 = newStack.pop();
                if (s.equals("+")) {
                    newStack.push(b2 + b1);
                } else if (s.equals("-")) {
                    newStack.push(b2 - b1);
                } else if (s.equals("*")) {
                    newStack.push(b2 * b1);
                } else if (s.equals("/")) {
                    newStack.push(b2 / b1);
                }
            } else {
                newStack.push(Double.valueOf(s));
            }
        }
        return newStack.peek();
    }
}

问题 F: 转换中缀表达式为带空格的后缀表达式

import java.util.ArrayList;
import java.util.Scanner;

/**
 * author 罗炜杰
 */

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.next();
            ArrayList<String> strlist = new ArrayList<String>();
            for(int i = 0; i < str.length(); i++){
                strlist.add(str.charAt(i) + "");
            }
            ArrayList<String> list = infixToSuffix(analysisExpression(str));
            System.out.print(list.get(0));
            for(int i = 1; i < list.size(); i++){
                System.out.print(" " + list.get(i));
            }
            System.out.println();
        }
    }

    /**
     * 解析表达式
     *
     * @param str
     * @return
     */
    public static ArrayList<String> analysisExpression(String str) {
        ArrayList<String> list = new ArrayList<String>();
        char[] arr = str.toCharArray();
        StringBuffer tmpStr = new StringBuffer();
        for (char c : arr) {
            if ((c >= '0') && (c <= '9') || (c == '.')) {
                tmpStr.append(c);
            } else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '('
                    || c == ')') {
                if (tmpStr.length() > 0) {
                    list.add(tmpStr.toString());
                    tmpStr.setLength(0);
                }
                list.add(c + "");
            }
        }
        if (tmpStr.length() > 0) {
            list.add(tmpStr.toString());
        }
        return list;
    }

    /**
     * 中缀转后缀 infix转suffix
     *
     * @param list
     * @return 后缀表达式
     */
    public static ArrayList<String> infixToSuffix(ArrayList<String> list) {
        ArrayList<String> strList = new ArrayList<String>();
        LinkedStack<String> stack = new LinkedStack<String>();
        String tmp;
        for (String s : list) {
            if (s.equals("(")) {
                stack.push(s);
            } else if (s.equals(")")) {
                while (!(tmp = stack.pop()).equals("(")) {
                    strList.add(tmp);
                }
            } else if (s.equals("*") || s.equals("/")) {
                while (!stack.isEmpty()) {
                    tmp = stack.peek();
                    if (tmp.equals("*") || tmp.equals("/")) {
                        stack.pop();
                        strList.add(tmp);
                    } else {
                        break;
                    }
                }
                stack.push(s);
            } else if (s.equals("+") || s.equals("-")) {
                while (!stack.isEmpty()) {
                    tmp = stack.peek();
                    if (!tmp.equals("(")) {
                        stack.pop();
                        strList.add(tmp);
                    } else {
                        break;
                    }
                }
                stack.push(s);
            } else {
                strList.add(s);
            }
        }
        while (!stack.isEmpty()) {
            strList.add(stack.pop());
        }
        return strList;
    }

    /**
     * 计算后缀表达式的值
     *
     * @param 后缀表达式
     * @return 最终结果的值
     */
    public static double Calculate(ArrayList<String> strList) {
        LinkedStack<Double> newStack = new LinkedStack<Double>();
        for (String s : strList) {
            if (s.equals("+") || s.equals("-") || s.equals("*")
                    || s.equals("/")) {
                double b1 = newStack.pop();
                double b2 = newStack.pop();
                if (s.equals("+")) {
                    newStack.push(b2 + b1);
                } else if (s.equals("-")) {
                    newStack.push(b2 - b1);
                } else if (s.equals("*")) {
                    newStack.push(b2 * b1);
                } else if (s.equals("/")) {
                    newStack.push(b2 / b1);
                }
            } else {
                newStack.push(Double.valueOf(s));
            }
        }
        return newStack.peek();
    }
}

问题 G: 后缀表达式求值

import java.util.ArrayList;
import java.util.Scanner;

/**
 * author 罗炜杰
 */

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.nextLine();
            String stx = str.replace(";"," ");
            ArrayList<String> strlist = new ArrayList<String>();
            for(String s : stx.split(" ")){
                strlist.add(s);
            }
            System.out.println("结果为:" + String.format("%.0f", Calculate(strlist)));
        }
    }

    /**
     * 解析表达式
     *
     * @param str
     * @return
     */
    public static ArrayList<String> analysisExpression(String str) {
        ArrayList<String> list = new ArrayList<String>();
        char[] arr = str.toCharArray();
        StringBuffer tmpStr = new StringBuffer();
        for (char c : arr) {
            if ((c >= '0') && (c <= '9') || (c == '.')) {
                tmpStr.append(c);
            } else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '('
                    || c == ')') {
                if (tmpStr.length() > 0) {
                    list.add(tmpStr.toString());
                    tmpStr.setLength(0);
                }
                list.add(c + "");
            }
        }
        if (tmpStr.length() > 0) {
            list.add(tmpStr.toString());
        }
        return list;
    }

    /**
     * 中缀转后缀 infix转suffix
     *
     * @param list
     * @return 后缀表达式
     */
    public static ArrayList<String> infixToSuffix(ArrayList<String> list) {
        ArrayList<String> strList = new ArrayList<String>();
        LinkedStack<String> stack = new LinkedStack<String>();
        String tmp;
        for (String s : list) {
            if (s.equals("(")) {
                stack.push(s);
            } else if (s.equals(")")) {
                while (!(tmp = stack.pop()).equals("(")) {
                    strList.add(tmp);
                }
            } else if (s.equals("*") || s.equals("/")) {
                while (!stack.isEmpty()) {
                    tmp = stack.peek();
                    if (tmp.equals("*") || tmp.equals("/")) {
                        stack.pop();
                        strList.add(tmp);
                    } else {
                        break;
                    }
                }
                stack.push(s);
            } else if (s.equals("+") || s.equals("-")) {
                while (!stack.isEmpty()) {
                    tmp = stack.peek();
                    if (!tmp.equals("(")) {
                        stack.pop();
                        strList.add(tmp);
                    } else {
                        break;
                    }
                }
                stack.push(s);
            } else {
                strList.add(s);
            }
        }
        while (!stack.isEmpty()) {
            strList.add(stack.pop());
        }
        return strList;
    }

    /**
     * 计算后缀表达式的值
     *
     * @param 后缀表达式
     * @return 最终结果的值
     */
    public static double Calculate(ArrayList<String> strList) {
        LinkedStack<Double> newStack = new LinkedStack<Double>();
        for (String s : strList) {
            if (s.equals("+") || s.equals("-") || s.equals("*")
                    || s.equals("/")) {
                double b1 = newStack.pop();
                double b2 = newStack.pop();
                if (s.equals("+")) {
                    newStack.push(b2 + b1);
                } else if (s.equals("-")) {
                    newStack.push(b2 - b1);
                } else if (s.equals("*")) {
                    newStack.push(b2 * b1);
                } else if (s.equals("/")) {
                    newStack.push(b2 / b1);
                }
            } else {
                newStack.push(Double.valueOf(s));
            }
        }
        return newStack.peek();
    }
}

问题 H: 中缀转后缀表达式求值

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;

@SuppressWarnings("all")
public class Main {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNext()) {
            String str = input.nextLine();
            String string = str.replace(";", "");
            double p = cal(string);
            System.out.println("结果为:" + String.format("%.0f", p));
        }
        input.close();
    }

    public static double cal(String str) {
        ArrayList<String> list = new ArrayList<String>();
        char[] arr = str.toCharArray();
        StringBuffer tmpStr = new StringBuffer();
        for (char c : arr) {
            if ((c >= '0') && (c <= '9') || (c == '.')) {
                tmpStr.append(c);
            } else if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')') {
                if (tmpStr.length() > 0) {
                    list.add(tmpStr.toString());
                    tmpStr.setLength(0);
                }
                list.add(c + "");
            }
        }
        if (tmpStr.length() > 0) {
            list.add(tmpStr.toString());
        }
        return TO(list);
    }

    public static double TO(ArrayList<String> list) {
        ArrayList<String> strList = new ArrayList<String>();
        LinkedStack<String> stack = new LinkedStack<String>();
        String tmp;
        for (String s : list) {
            if (s.equals("(")) {
                stack.push(s);
            } else if (s.equals(")")) {
                while (!(tmp = stack.pop()).equals("(")) {
                    strList.add(tmp);
                }
            } else if (s.equals("*") || s.equals("/")) {
                while (!stack.isEmpty()) {
                    tmp = stack.peek();
                    if (tmp.equals("*") || tmp.equals("/")) {
                        stack.pop();
                        strList.add(tmp);
                    } else {
                        break;
                    }
                }
                stack.push(s);
            } else if (s.equals("+") || s.equals("-")) {
                while (!stack.isEmpty()) {
                    tmp = stack.peek();
                    if (!tmp.equals("(")) {
                        stack.pop();
                        strList.add(tmp);
                    } else {
                        break;
                    }
                }
                stack.push(s);
            } else {
                strList.add(s);
            }
        }
        while (!stack.isEmpty()) {
            strList.add(stack.pop());
        }
        ArrayList<String> list02 = new ArrayList<String>();
        list02 = strList;
        Iterator<String> iterator = list02.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next());
        }
        System.out.println();
        return Calculate(strList);
    }

    public static double Calculate(ArrayList<String> strList) {
        LinkedStack<Double> newStack = new LinkedStack<Double>();
        for (String s : strList) {
            if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
                double b1 = newStack.pop();
                double b2 = newStack.pop();
                if (s.equals("+")) {
                    newStack.push(b2 + b1);
                } else if (s.equals("-")) {
                    newStack.push(b2 - b1);
                } else if (s.equals("*")) {
                    newStack.push(b2 * b1);
                } else if (s.equals("/")) {
                    newStack.push(b2 / b1);
                }
            } else {
                newStack.push(Double.valueOf(s));
            }
        }
        return newStack.peek();
    }
}

问题 I: 迷宫出口

这题可以用栈做,不过我觉得用栈的话,麻烦

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = 1;
        while (sc.hasNext()) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            if (m == 0 && n == 0) {
                break;
            }
            int data[][] = new int[m][n];
            for (int i = 0; i < m; i++) {
                String str = sc.next();
                for (int j = 0; j < n; j++) {
                    char ch = str.charAt(j);
                    data[i][j] = ch - '0';
                }
            }
            Solution solution = new Solution(data);
            System.out.print("Case " + (count++) + ":");
            solution.mazeExit(0, 0);
            solution.PrintLoad();
            System.out.println();
        }
    }
}

class Solution {
    private int[][] maze;
    private int[][] load = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};      //寻路方向
    private ArrayList<Point> list;

    public Solution(int[][] data) {
        this.maze = new int[data.length][data[0].length];
        for (int i = 0; i < data.length; i++) {
            for (int j = 0; j < data[0].length; j++) {
                maze[i][j] = data[i][j];
            }
        }
        this.list = new ArrayList<Point>();
    }

    /**
     * 递归
     *
     * @param x
     * @param y
     */
    public void mazeExit(int x, int y) {

        //如果当前位置是出口的话,打印
        if (x == maze.length - 1 || y == maze[0].length - 1) {
//            System.out.print("(" + x + "," + y + ")");
            list.add(new Point(x, y));
        }

        //标记当前位置已走过
        maze[x][y] = 1;

        //搜索下一步可走位置
        for (int i = 0; i < 4; i++) {
            int nextX = x + load[i][0];
            int nextY = y + load[i][1];
            if (judgeNext(nextX, nextY)) {
                //递归,进行下一步寻找
                mazeExit(nextX, nextY);
            }
        }
    }

    private boolean judgeNext(int x, int y) {
        if (x >= maze.length || x < 0 || y >= maze[0].length || y < 0 || maze[x][y] == 1) {
            return false;
        }
        return true;
    }

    public void PrintLoad(){
        Collections.sort(list, new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                return o1.getY() - o2.getY();
            }
        });

        for(Point p : list){
            System.out.print(p);
        }
    }
}


class Point{
    private int x;
    private int y;

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }

    public Point(int x,int y){
        this.x = x;
        this.y = y;
    }

    public Point(){
        this(0, 0);
    }

    public String toString(){
        return "(" + x + "," + y + ")";
    }
}

问题 J: 马踏棋盘

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sin = new Scanner(System.in);
        while (sin.hasNext()) {
            int m = sin.nextInt();
            int n = sin.nextInt();
            HouseMaze houseMaze = new HouseMaze();
            houseMaze.createMatrix();
            houseMaze.dfs(m - 1, n - 1, 1);
        }
    }
}

class HouseMaze {
    private int[][] matrix = new int[8][8];
    private int[][] flag = new int[8][8];
    private int[] step1 = {-2, -1, 1, 2, 2, 1, -1, -2};
    private int[] step2 = {1, 2, 2, 1, -1, -2, -2, -1};
    
    public void createMatrix() {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                matrix[i][j] = 0;
                flag[i][j] = 0;
            }
        }
    }
    
    public boolean check(int x, int y) {
        if (x > 7 || x < 0 || y > 7 || y < 0 || flag[x][y] == 1)
            return false;
        return true;

    }

    public boolean dfs(int x, int y, int step) {
        flag[x][y] = 1;
        matrix[x][y] = step;
        if (step == 64) {
            print();
            return true;
        }
        for (int i = 0; i < 8; i++) {
            if (check(x + step1[i], y + step2[i])) {
                step++;
                boolean result = dfs(x + step1[i], y + step2[i], step);
                if (result == true)
                    return true;
                flag[x + step1[i]][y + step2[i]] = 0;
                matrix[x + step1[i]][y + step2[i]] = 0;
                step--;
            }
        }
        return false;
    }

    public void print() {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (j == 0) {
                    System.out.print(String.format("%2d", matrix[i][j]));
                } else {
                    System.out.print(String.format(" %2d", matrix[i][j]));
                }
            }
            System.out.println();
        }
    }
}

优化版本:
不过OJ不能通过,输出不一样

public class horse {
    private final int[][] load = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};  //马下一步的方向
    private int[][] chessBoard;

    public horse() {
        this.chessBoard = new int[8][8];
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                chessBoard[i][j] = 0;
            }
        }
    }

    public void horseTrav(int x, int y, int count) {

        //64个格子都走过,退出,打印棋盘
        if (count == 64) {
            printChessBoard();
            return;
        }

        //判断当前位置是否能走
        if (!judgeNext(x, y)) {
            return;
        }

        count++;
        chessBoard[x][y] = count;

        /**
         * 贪心算法,记录下一个可走位置的可走步数,将步数最少的可走位置作为下一步的位置
         * 网上的解释是:“选择最难走的路,才能走的远”
         * 这边个人理解为,有些位置的下一步很少,如果不先遍历它的话以后可能会很难遍历到它。
         * 甚至极端一点的情况是,如果现在不遍历它,以后都遍历不到了。遍历不成功的时候只能回溯,一直回溯到此刻的点,然后选了这个点以后才能完成,这就浪费了大量的时间。
         */
        int[] next = {-1, -1, -1, -1, -1, -1, -1, -1};
        for (int i = 0; i < 8; i++) {
            int x_next = x + load[i][0];
            int y_next = y + load[i][1];
            if (judgeNext(x_next, y_next)) {
                next[i]++;
                for (int j = 0; j < 8; j++) {
                    int m_next_next = x_next + load[j][0];
                    int n_next_next = y_next + load[j][1];
                    if (judgeNext(m_next_next, n_next_next))
                        next[i]++;
                }
            }
        }

        int direct = 0; //记录下一步的方向
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < 8; i++) {
            if (next[i] != -1 && next[i] < min) {
                min = next[i];
                direct = i;
            }
        }

        int nextX = x + load[direct][0];
        int nextY = y + load[direct][1];

        //递归,进行下一步
        horseTrav(nextX, nextY, count);

        //回溯,对应位置标记为0
        chessBoard[x][y] = 0;

    }

    private boolean judgeNext(int x, int y) {
        if (x >= 8 || x < 0 || y >= 8 || y < 0 || chessBoard[x][y] != 0) {
            return false;
        }
        return true;
    }

    private void printChessBoard() {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(String.format("%2d", chessBoard[i][j]) + " ");
            }
            System.out.println(String.format("%2d", chessBoard[i][7]));
        }
    }

    public static void main(String[] args) {
        horse h = new horse();
        System.out.println("\t  递归+贪心优化");
        long start = System.currentTimeMillis();
        h.horseTrav(1, 1, 0);
        long end = System.currentTimeMillis();
        System.out.println();
        System.out.println("共耗时:" + (end - start) + "ms");

    }
}

问题 K: 迷宫最短路径

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sin = new Scanner(System.in);
        while (sin.hasNext()) {
            int m = sin.nextInt();
            int n = sin.nextInt();
            int[][] ppz = new int[m][n];
            for (int i = 0; i < m; i++) {
                String str = sin.next();
                for (int j = 0; j < n; j++) {
                    ppz[i][j] = Integer.parseInt(str.charAt(j) + "");
                }
            }
            BFS b = new BFS(ppz, m, n);
            b.BFS();
            System.out.println();
        }
    }
}

class Potision {
    int x;
    int y;
    Potision cur;

    public Potision(int x, int y, Potision cur) {
        this.x = x;
        this.y = y;
        this.cur = cur;
    }
}

class BFS {
    private int[][] martix;
    private Potision [][]maze;
    private int m;
    private int n;
    static int Load[][] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

    public BFS(int [][]martix,int m, int n) {
        this.martix=martix;
        this.m = m;
        this.n = n;
        maze=new Potision[m][n];
    }

    public void BFS() {
        Queue<Potision> queue = new LinkedList<Potision>();
        martix[0][0] = -1;
        Potision p=new Potision(0,0,null);
        queue.add(p);
        maze[0][0]=p;
        while (!queue.isEmpty()) {
            Potision q = queue.poll();
            if (q.x == m - 1 && q.y == n - 1) {
                Print(this.m-1, this.n-1);
                break;
            }
            for (int i = 0; i < 4; i++) {
                int x = q.x + Load[i][0];
                int y = q.y + Load[i][1];
                if (Check(x, y)) {
                    Potision pp=new Potision(x,y,q);
                    maze[x][y]=pp;
                    queue.add(pp);
                    martix[x][y] = -1;
                }
            }
        }
    }

    private void Print(int m, int n) {
        if (maze[m][n].cur == null) {
            System.out.print("(1,1)");
            return ;
        } else {
            Print(maze[m][n].cur.x, maze[m][n].cur.y);
            System.out.print("(" + (m + 1) + "," + (n + 1) + ")");
        }
    }

    private boolean Check(int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n || martix[x][y] != 0) {
            return false;
        }
        return true;
    }
}

愿你生活的每一个角落,都有细微安静的美,愿你看淡世事沧桑,内心安然无恙,愿你洗净铅华,能被岁月温柔相待

标题:OJ作业-栈的应用
作者:Bursteretion
地址:https://www.lwjppz.cn/OJ-03-HomeWork.html
版权声明:本博客除了特殊声明的文章外,均采用CC BY 3.0 CN协议进行许可。转载请署名作者且注明文章出处。
评论
  • hhhh,不管了,还要肝项目,反正30号才结束( ̄︶ ̄)↗ 

    Reply
  • (>ω・* )ノ,当时做的时候,马踏棋盘这题用栈直接超时,后来用递归试了一下,过了(o°ω°o),后来对着Java的版本写了个C++的,超时了,无语......
    所以,吸取了一个教训,这种题能递归,就递归搞定,代码看着舒服,还短

    Reply
  • 马踏棋盘和最后一题走地图的自己维护运行栈(就是用循环)过不了,吐血.jpg,一题超时一题答案错误

    Reply