回溯法大成!以回溯法实现栈的出栈情况的遍历为例子,轻松帮你深刻领悟回溯法

时间:2024-03-24 11:57:05

这里用回溯法实现了 栈的出栈情况的遍历 。虽然这个题有更好的做法,但是你如果用回溯法做这道题,做完后一定会对回溯法有这更高境界的领悟,而且在整个设计算法,debug算法的过程中会感受到一种酣畅淋漓的快感。因为这个题看似很小,其实规模很大,要考虑方方面面的问题,很多很多。


上题。

输入一个序列 比如 123。你进栈的顺序必须是按照这个序列来,但是你可以这样,进1,然后在2进入前,把1出栈。所以出栈顺序就有了许多种可能。


我讲一下我一开始是怎么做的:

感觉这题很简单,直接开始码代码,发现有新的需求,直接改,一处改,处处改,bug比比皆是,而且怎么改都是错的,因为思路上就有了偏差。


正确的做法是怎样的:

做回溯法和其他的不一样,对逻辑的缜密和条理性要求更高,特别是碰到大规模的题目的时候。所以你应该做的第一件事,是,打开一个txt文档,写下你的思路。

回溯法大成!以回溯法实现栈的出栈情况的遍历为例子,轻松帮你深刻领悟回溯法


接下来你只需要把你的文字转化成代码就可以了。由于我的思路是写给我自己看的,所以我这里重新写一下思路分析。

1.你的输入队列是1,2,3。所以我3推进去之后,后面就再也没有进栈的操作了,因为没有已经元素已经推光了,所以只需要进行出栈操作就可以了,所以这里进行统一处理。分两类情况,一,元素推光。二,元素还未推光。

2.元素未推光的情况。这里又分两种情况。当前栈是空的,当前栈是非空的。栈空,只能直接入栈(因为你元素未推光,所以肯定可以进行入栈操作)。栈非空。

3.栈非空的时候其实又有两种情况,你可以选择入栈(因为你元素未推光,所以肯定可以进行入栈操作),也可以选择出栈(栈非空)。所以我们用一个for循环,第一次执行入栈操作,当回溯回来的时候,for循环到下一个,执行出栈操作。


这样就把思路完美的分析出来了。接下来我会每一步都贴上对应的代码。


元素推光的一类情况

if (level == length) {
    // TODO: 2017/11/19 这里执行的是:把当前记录的出栈情况数组添加到所有情况的二维数组里,最后一起输出 
level == length。这里的level是我当前的层级。我什么都没入栈。level是0。每入栈一个数字,会执行递归,参数是level + 1。

length是数组的长度。这里是3。你的level是从0开始到,如果想到3,就已经加了4次。所以说这是一种元素都推光的情形。


元素未推光的一类情况-当前栈是空的

if (list.size() == 0) {
    list.add(inOrder[level]);
    back(level + 1, index);
    list.remove(list.size() - 1);
} 
我这里的list是模拟的栈。栈是空的,只能入栈,所以add,然后level+1进行回溯,进入下一层。这里的index先不用管,没有影响的。当你back(level + 1, index);执行完以后,你后面的层级的所有情况都已经搞定了,所以你这里需要把你推的东西重新移除,进行另外方向的寻找同时又避免你推进去的东西影响另外的判断,因为你和另外的情况是平行的,如果你不删除这个数的话你这次操作就影响了另外的情况,会出错。所以这里是必须移除的。


元素未推光的一类情况-当前栈非空的

for (int i = 0; i < 2; i++) {
    if (i == 0) {
        list.add(inOrder[level]);
        back(level + 1, index);
        list.remove(list.size() - 1);
    } else {
        int num = list.remove(list.size() - 1);
        current[index] = num;
        back(level, index + 1);
        list.add(num);
    }
}
非空情况你可以推也可以不推,所以用了一个for循环,第一次弄入栈的情况,第二次回溯回来循环执行到下一个地方,就执行下面的代码块即出栈操作。

也是一样你添加了之后就要移除,移除了之后就要添加。这里出栈多了一个操作current[index] = num;就是记录下你的出栈情况,这个index初始是0,当你出了一次栈以后,在继续遍历的时候,就要把index + 1带进去,让后面的层级对你的出栈情况数组的接下来的一位进行分析。所以我们可以看到,如果是入栈,level + 1会被传进去,如果是出栈,index+1会被传进去,前者代表的是你的入栈队列处理到哪个位置了,后者代表的是你的出栈队列处理到哪个位置了。


这就没了。

如果说还有的话就是元素推光的那一类情况,数据又是怎么处理的。有兴趣可以看一下。


取得你所有出栈情况的二维数组的当前是第几行。这里从0,0开始向下找,找到第一个值不为0的数,就是我们要找的行数了。

int row = -1;
//找到第一个没有被赋值过的行,这个找到的i就是pure(纯净,未赋值过的)行号
int flag = -1;
for (int i = 0; i < 100; i++) {
    if (allPossible[i][0] == 0) {
        row = i;
        break;
    }
}

把你栈中的剩下的元素记录下来(应该是要推掉的,但是为了不影响回溯的时候的数据,所以直接读出来了)

//把栈中剩余的数按出栈顺序读到结果数组里,实际上不出栈,怕影响之前的情况
for (int i = 0; i < list.size(); i ++) {//经检验,list出栈的数据完全正确!
    int num = list.get(i);
    for (int j = length - 1; j >= 0; j --) {
        if (allPossible[row][j] == 0) {
            allPossible[row][j] = num;
            break;
        }
    }
}

把在回溯的过程中出栈的元素也加上(因为我们这里到3就结束了简化了操作,所以需要通过这一步和上一步把出栈顺序完整拼接起来)

//current里的结果也一并加上
for (int i = 0; i < length; i++) {
    if (allPossible[row][i] == 0) {
        allPossible[row][i] = current[i];
    } else break;
}

搞定了。上结果图

回溯法大成!以回溯法实现栈的出栈情况的遍历为例子,轻松帮你深刻领悟回溯法


贴上完整回溯代码

void back(int level, int index) {//1,2带进去验证 level = 0 length = 2//最后发现index还是有必要的
        if (level == length) {
            // TODO: 2017/11/19 这里执行的是:把当前记录的出栈情况数组添加到所有情况的二维数组里,最后一起输出
            int row = -1;
            //找到第一个没有被赋值过的行,这个找到的i就是pure(纯净,未赋值过的)行号
            int flag = -1;
            for (int i = 0; i < 100; i++) {
                if (allPossible[i][length - 1] == 0) {
                    row = i;
                    break;
                }
            }
            //把栈中剩余的数按出栈顺序读到结果数组里,实际上不出栈,怕影响之前的情况
            for (int i = 0; i < list.size(); i ++) {//经检验,list出栈的数据完全正确!
                int num = list.get(i);
                for (int j = length - 1; j >= 0; j --) {
                    if (allPossible[row][j] == 0) {
                        allPossible[row][j] = num;
                        break;
                    }
                }
            }
            //current里的结果也一并加上
            for (int i = 0; i < length; i++) {
                if (allPossible[row][i] == 0) {
                    allPossible[row][i] = current[i];
                } else break;
            }
//            for (int i = 0; i < length; i ++) {//肯定不能都置为0,不然回溯的时候会打乱前面的数据
//                current[i] = 0;
//            }
            return;
        } else {//这里level0到最后一层,index指代当前操作数,如果仍在这个范围内,代表数没用完
            if (list.size() == 0) {
                list.add(inOrder[level]);
                back(level + 1, index);
                list.remove(list.size() - 1);
            } else {
                for (int i = 0; i < 2; i++) {
                    if (i == 0) {
                        list.add(inOrder[level]);
                        back(level + 1, index);
                        list.remove(list.size() - 1);
                    } else {
                        int num = list.remove(list.size() - 1);
                        current[index] = num;
                        back(level, index + 1);
                        list.add(num);
                    }
                }
            }
        }
    }

贴上全部代码

public class Test {

    int length;
    int[][] allPossible;
    String[][] allOperate;

    int[] current;
    String[] operate;

    int[] inOrder;
//    int[] outOrder;

    List<Integer> list;//这个当做栈

    int operateIndex;

    Test(int... ints) {//123321,后面3个是要求的出栈顺序,可以不用理会
        //length = ints.length / 2;
        length = ints.length;

        allPossible = new int[100][length];//不想分析有几种可能,暂定100        allOperate = new String[100][length * 2];

        current = new int[length];
        operate = new String[length * 2];

        inOrder = new int[length];
        for (int i = 0; i < length; i++) {
            inOrder[i] = ints[i];
        }

//        outOrder = new int[length];
//        for (int i = 0; i < length; i++) {
//            outOrder[i] = ints[i + length];
//        }

        list = new ArrayList<>();

        operateIndex = 0;
    }

    void back(int level, int index) {//1,2带进去验证 level = 0 length = 2//最后发现index还是有必要的
        if (level == length) {
            // TODO: 2017/11/19 这里执行的是:把当前记录的出栈情况数组添加到所有情况的二维数组里,最后一起输出
            int row = -1;
            //找到第一个没有被赋值过的行,这个找到的i就是pure(纯净,未赋值过的)行号
            int flag = -1;
            for (int i = 0; i < 100; i++) {
                if (allPossible[i][length - 1] == 0) {
                    row = i;
                    break;
                }
            }
            //把栈中剩余的数按出栈顺序读到结果数组里,实际上不出栈,怕影响之前的情况
            for (int i = 0; i < list.size(); i ++) {//经检验,list出栈的数据完全正确!
                int num = list.get(i);
                for (int j = length - 1; j >= 0; j --) {
                    if (allPossible[row][j] == 0) {
                        allPossible[row][j] = num;
                        break;
                    }
                }
            }
            //current里的结果也一并加上
            for (int i = 0; i < length; i++) {
                if (allPossible[row][i] == 0) {
                    allPossible[row][i] = current[i];
                } else break;
            }
//            for (int i = 0; i < length; i ++) {//肯定不能都置为0,不然回溯的时候会打乱前面的数据
//                current[i] = 0;
//            }
            return;
        } else {//这里level0到最后一层,index指代当前操作数,如果仍在这个范围内,代表数没用完
            if (list.size() == 0) {
                list.add(inOrder[level]);
                back(level + 1, index);
                list.remove(list.size() - 1);
            } else {
                for (int i = 0; i < 2; i++) {
                    if (i == 0) {
                        list.add(inOrder[level]);
                        back(level + 1, index);
                        list.remove(list.size() - 1);
                    } else {
                        int num = list.remove(list.size() - 1);
                        current[index] = num;
                        back(level, index + 1);
                        list.add(num);
                    }
                }
            }
        }
    }

    void print() {
        int row = -1;
        for (int i = 0; i < 100; i++) {
            if (allPossible[i][0] == 0) {
                row = i;
                break;
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < length; j++) {
                System.out.print(allPossible[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) throws Exception {
        Test test = new Test(1, 2, 3);
        test.back(0, 0);
        test.print();
    }
}

懂的人会发现自己的回溯法已经大成了,夸张点的甚至感觉自己的逻辑思维都清晰了许多。