一个回溯算法问题，请大家帮忙看看

[woodenwang]

呵呵，不是大问题，晚安，继续加油，祝一切顺利

 

[gongbao]

那个帖子又把我的数组符号给吃了，我截个图上来吧

你用linux UBUNTU啊，什么型号的电脑？
我早就想弄个linux笔记本了，求推荐！

 

[gongbao]

呵呵，不是大问题，晚安，继续加油，祝一切顺利

谢谢，晚安！

 

[woodenwang]

你用linux UBUNTU啊，什么型号的电脑？
我早就想弄个linux笔记本了，求推荐！

公司的机器，ASUS的笔记本

 

[woodenwang]

直接买预装LINUX 的比较少吧，我这都是公司买来以后重新装的

 

[gongbao]

公司的机器，ASUS的笔记本

配置很高。可否告知具体型号？

 

[gongbao]

直接买预装LINUX 的比较少吧，我这都是公司买来以后重新装的

是的，dell有预装linux的，但性价比一般般，虽然我可以有学生折扣。我想买个物美价廉的win笔记本，然后自己装。买过二手thinkpad，风扇转不停。现在是macbook pro + ubuntu on USB，有空拿出来玩玩，发热严重

 

[gongbao]

为什么总是不行呢？现在输出的错误结果包含了正确结果，多处5步，是多余的错误步，但是正确答案的顺序就在里面……

呵呵，不是大问题，晚安，继续加油，祝一切顺利

/*
* Sort characters recursively
*/
package T7;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
* Sort a series of characters in ascended ordering.
*/
public class CharRecSorter {

    // Data fields
    private static char[] characters = {'C', 'C', 'C', 'B', 'A', 'A', 'A'};
    private ArrayList<String> dontCare = new ArrayList<>();

    // Constructor
    public CharRecSorter() {
        dontCare.add(" don't care ");
    }

    // Private class to record the current state of testing.
    private static class CurrentState {

        public final char[] chars;
        public final ArrayList<String> steps;

        public CurrentState(char[] chars, ArrayList<String> steps) {
            this.chars = chars;
            this.steps = steps;
        }
    }

    private static int getIndexOfB(char[] c) {
        for (int i = 0; i < c.length; i++) {
            if (c[i] == 'B') {
                return i;
            }
        }
        return -1;
    }

    private static int left(char[] characters) {
        int index = getIndexOfB(characters);
        if (index - 1 >= 0 && characters[index - 1] == 'C') {
            char tmp = characters[index - 1];
            characters[index - 1] = 'B';
            characters[index] = tmp;
            return index;
        }
        return -1;
    }

    private static int left2(char[] characters) {
        int index = getIndexOfB(characters);
        if (index - 2 >= 0 && characters[index - 2] == 'C') {
            char tmp = characters[index - 2];
            characters[index - 2] = 'B';
            characters[index] = tmp;
            return index;
        }
        return -1;
    }

    private static int right(char[] characters) {
        int index = getIndexOfB(characters);
        if (index + 1 <= characters.length - 1 && characters[index + 1] == 'A') {
            char tmp = characters[index + 1];
            characters[index + 1] = 'B';
            characters[index] = tmp;
            return index;
        }
        return -1;
    }

    private static int right2(char[] characters) {
        int index = getIndexOfB(characters);
        if (index + 2 <= characters.length - 1 && characters[index + 2] == 'A') {
            char tmp = characters[index + 2];
            characters[index + 2] = 'B';
            characters[index] = tmp;
            return index;
        }
        return -1;
    }

    /**
     * Check if the characters in the array is well sorted ascended.
     *
     * @param characters The input array of characters
     * @return true if sorted ascended; otherwise, false.
     */
    private static boolean isSorted(char[] characters) {
        char[] target = {'A', 'A', 'A', 'B', 'C', 'C', 'C'};
        return java.util.Arrays.equals(target, characters);
    }

    /**
     * Wrapper method to call recursive sort().
     *
     * @return The recursive sort()
     */
    public String sort() {
        ArrayList<String> str = sort(characters);
        StringBuilder steps = new StringBuilder();
        str.forEach((s) -> {
            steps.append(s);
        });
        return "Steps: " + steps + "\nTotal: " + str.size() + " steps.";
    }

    /**
     * Recursive method to sort the characters. pre: disordered letters post:
     * letters in alphabet ordering
     *
     * @param chars The input array of char.
     * @return The ordering represented by index
     */
    public ArrayList<String> sort(char[] chars) {

        char[] newArray = chars.clone();
        ArrayList<String> steps = new ArrayList<>();
        Queue<CurrentState> queue = new LinkedList<>();
        CurrentState state = new CurrentState(newArray, steps);

        while (state!=null && !isSorted(state.chars)) {

            newArray = state.chars.clone();
            int left = left(newArray);
            if (left != -1) {
                steps = (ArrayList<String>) state.steps.clone();
                steps.add((left - 1 + 1) + "->" + (left + 1) + ", ");
                queue.offer(new CurrentState(newArray, steps));
            }

            newArray = state.chars.clone();
            int left2 = left2(newArray);
            if (left2 != -1) {
                steps = state.steps;
                steps.add((left2 - 2 + 1) + "->" + (left2 + 1) + ", ");
                queue.offer(new CurrentState(newArray, steps));
            }

            newArray = state.chars.clone();
            int right = right(newArray);
            if (right != -1) {
                steps = state.steps;
                steps.add((right + 1 + 1) + "->" + (right + 1) + ", ");
                queue.offer(new CurrentState(newArray, steps));
            }

            newArray = state.chars;
            int right2 = right2(newArray);
            if (right2 != -1) {
                steps = state.steps;
                steps.add((right2 + 2 + 1) + "->" + (right2 + 1) + ", ");
                queue.offer(new CurrentState(newArray, steps));
            }
            state = queue.poll();
        }
        if(state != null)
            return state.steps;
        else
            return dontCare;
    }

    public static void main(String[] args) {

        CharRecSorter sorter = new CharRecSorter();
        String result = sorter.sort();
        System.out.println(result);
    }
}
[/i]

 

[woodenwang]

配置很高。可否告知具体型号？

Manufacturer: ASUSTeK COMPUTER INC.
Product Name: GL552VW
Version: 1.0

 

[gongbao]

Manufacturer: ASUSTeK COMPUTER INC.
Product Name: GL552VW
Version: 1.0

是游戏本？我这边二手的要10490克朗，新的没有卖。

 

[woodenwang]

是不是游戏本我就不清楚了，主要就是我们开发需要接双显示屏，所以买的这个

 

[dennistan2009]

牛，家园上的最强大脑。

 

[gongbao]

是的woodenwang是家园最强大脑，我非常佩服！！！

是不是游戏本我就不清楚了，主要就是我们开发需要接双显示屏，所以买的这个

牛，家园上的最强大脑。