Dijkstral算法优化及经典递归题目

Dijkstral算法优化及经典递归题目

1 Dijkstral算法优化（利用加强堆）

求一个图中一个点到其他所有点的最短路径的算法

1 构建图结构

1.1.1 图中节点的结构

//图结构的节点结构
public class Node {
    public int value;
    public int in;
    public int out;
    public ArrayList<Node> nexts;
    public ArrayList<Edge> edges;

    public Node(int value){
        this.value = value;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1.1.2 图中边的结构

//图结构的边
public class Edge {
    public int weight;
    public Node from;
    public Node to;

    public Edge(int weight, Node from, Node to){
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

2 实现Dijkstral算法

2.1 构建NodeRecord（返回的节点信息）

//返回的节点信息
    public static class NodeRecord {
        public Node node;
        public int distance;

        public NodeRecord(Node node, int distance) {
            this.node = node;
            this.distance = distance;
        }
    }
1
2
3
4
5
6
7
8
9
10

2.2 构建加强堆NodeHeap

2.2.1 NodeHeap构造函数

//加强堆
public static class NodeHeap {
    // 堆！
    private Node[] nodes;
    // node -> 堆上的什么位置？

    //记录每个节点在堆上的位置
    private HashMap<Node, Integer> heapIndexMap;
    //记录每个节点对应的距离
    private HashMap<Node, Integer> distanceMap;
    private int size;

    public NodeHeap(int size) {
        nodes = new Node[size];
        heapIndexMap = new HashMap<>();
        distanceMap = new HashMap<>();
        size = 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.2.2 isEmpty、inHeap及isEntered

public boolean isEmpty() {
    return size == 0;
}

private boolean isEntered(Node node) {
    return heapIndexMap.containsKey(node);
}


//判断是否在堆中
 private boolean inHeap(Node node) {
     return isEntered(node) && heapIndexMap.get(node) != -1;
 }
1
2
3
4
5
6
7
8
9
10
11
12
13

2.2.3 堆的上浮insertHeapify

//上浮【添加一个node之后，判断是否可以上浮】
private void insertHeapify(Node node, int index) {
    //node每次与(index-1) / 2比较， 与父节点比较
    while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {
        swap(index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}
1
2
3
4
5
6
7
8

2.2.4 堆的下沉heapify

//下沉【删除一个节点后，将末尾节点与堆顶节点互换】
private void heapify(int index, int size) {
    //该节点的左节点
    int left = index * 2 + 1;
    while (left < size) {
        //获得该节点的左右节点的最小值
        int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left])
                ? left + 1
                : left;
        smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index;
        //判断该节点的值与其左右节点最小值大小【如果大于，需要下沉】
        if (smallest == index) {
            break;
        }
        swap(smallest, index);
        index = smallest;
        left = index * 2 + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.2.5 swap

private void swap(int index1, int index2) {
    heapIndexMap.put(nodes[index1], index2);
    heapIndexMap.put(nodes[index2], index1);
    Node tmp = nodes[index1];
    nodes[index1] = nodes[index2];
    nodes[index2] = tmp;
}
1
2
3
4
5
6
7

2.2.6 pop

//从堆中弹出元素【小跟堆，弹出最小值】
public NodeRecord pop() {
    NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
    swap(0, size - 1); // 0 > size - 1    size - 1 > 0
    heapIndexMap.put(nodes[size - 1], -1);
    distanceMap.remove(nodes[size - 1]);
    // free C++同学还要把原本堆顶节点析构，对java同学不必
    nodes[size - 1] = null;
    heapify(0, --size);
    return nodeRecord;
}
1
2
3
4
5
6
7
8
9
10
11

2.2.7 addOrUpdateOrIgnore

// 有一个点叫node，现在发现了一个从源节点出发到达node的距离为distance
// 判断要不要更新，如果需要的话，就更新
public void addOrUpdateOrIgnore(Node node, int distance) {
   if (inHeap(node)) { // update
       distanceMap.put(node, Math.min(distanceMap.get(node), distance));
       insertHeapify(node, heapIndexMap.get(node));
   }
   if (!isEntered(node)) { // add
       nodes[size] = node;
       heapIndexMap.put(node, size);
       distanceMap.put(node, distance);
       insertHeapify(node, size++);
   }
   // ignore
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.2.8 dijkstral主方法

从第一个节点node，往下找，找到所有边，及边的from、to，直往下更新

// 改进后的dijkstra算法
// 从head出发，所有head能到达的节点，生成到达每个节点的最小路径记录并返回
public static HashMap<Node, Integer> dijkstra2(Node head, int size) {
    NodeHeap nodeHeap = new NodeHeap(size);
    nodeHeap.addOrUpdateOrIgnore(head, 0);
    HashMap<Node, Integer> result = new HashMap<>();
    while (!nodeHeap.isEmpty()) {
        NodeRecord record = nodeHeap.pop();
        Node cur = record.node;
        int distance = record.distance;
        //每次找到一个节点后，遍历其边，找到最短distance
        for (Edge edge : cur.edges) {
            nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);
        }
        result.put(cur, distance);
    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.2.9 全代码

//迪杰特斯拉算法【利用加强堆实现】
public class DijkstraDemo {

    //返回的节点信息
    public static class NodeRecord {
        public Node node;
        public int distance;

        public NodeRecord(Node node, int distance) {
            this.node = node;
            this.distance = distance;
        }
    }

    //加强堆
    public static class NodeHeap {
        // 堆！
        private Node[] nodes;
        // node -> 堆上的什么位置？

        //记录每个节点在堆上的位置
        private HashMap<Node, Integer> heapIndexMap;
        //记录每个节点对应的距离
        private HashMap<Node, Integer> distanceMap;
        private int size;

        public NodeHeap(int size) {
            nodes = new Node[size];
            heapIndexMap = new HashMap<>();
            distanceMap = new HashMap<>();
            size = 0;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        // 有一个点叫node，现在发现了一个从源节点出发到达node的距离为distance
        // 判断要不要更新，如果需要的话，就更新
        public void addOrUpdateOrIgnore(Node node, int distance) {
            if (inHeap(node)) { // update
                distanceMap.put(node, Math.min(distanceMap.get(node), distance));
                insertHeapify(node, heapIndexMap.get(node));
            }
            if (!isEntered(node)) { // add
                nodes[size] = node;
                heapIndexMap.put(node, size);
                distanceMap.put(node, distance);
                insertHeapify(node, size++);
            }
            // ignore
        }

        //从堆中弹出元素【小跟堆，弹出最小值】
        public NodeRecord pop() {
            NodeRecord nodeRecord = new NodeRecord(nodes[0], distanceMap.get(nodes[0]));
            swap(0, size - 1); // 0 > size - 1    size - 1 > 0
            heapIndexMap.put(nodes[size - 1], -1);
            distanceMap.remove(nodes[size - 1]);
            // free C++同学还要把原本堆顶节点析构，对java同学不必
            nodes[size - 1] = null;
            heapify(0, --size);
            return nodeRecord;
        }

        //上浮【添加一个node之后，判断是否可以上浮】
        private void insertHeapify(Node node, int index) {
            //node每次与(index-1) / 2比较， 与父节点比较
            while (distanceMap.get(nodes[index]) < distanceMap.get(nodes[(index - 1) / 2])) {
                swap(index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        //下沉【删除一个节点后，将末尾节点与堆顶节点互换】
        private void heapify(int index, int size) {
            //该节点的左节点
            int left = index * 2 + 1;
            while (left < size) {
                //获得该节点的左右节点的最小值
                int smallest = left + 1 < size && distanceMap.get(nodes[left + 1]) < distanceMap.get(nodes[left])
                        ? left + 1
                        : left;
                smallest = distanceMap.get(nodes[smallest]) < distanceMap.get(nodes[index]) ? smallest : index;
                //判断该节点的值与其左右节点最小值大小【如果大于，需要下沉】
                if (smallest == index) {
                    break;
                }
                swap(smallest, index);
                index = smallest;
                left = index * 2 + 1;
            }
        }

        private boolean isEntered(Node node) {
            return heapIndexMap.containsKey(node);
        }

        //判断是否在堆中
        private boolean inHeap(Node node) {
            return isEntered(node) && heapIndexMap.get(node) != -1;
        }

        private void swap(int index1, int index2) {
            heapIndexMap.put(nodes[index1], index2);
            heapIndexMap.put(nodes[index2], index1);
            Node tmp = nodes[index1];
            nodes[index1] = nodes[index2];
            nodes[index2] = tmp;
        }
    }

    // 改进后的dijkstra算法
    // 从head出发，所有head能到达的节点，生成到达每个节点的最小路径记录并返回
    public static HashMap<Node, Integer> dijkstra2(Node head, int size) {
        NodeHeap nodeHeap = new NodeHeap(size);
        nodeHeap.addOrUpdateOrIgnore(head, 0);
        HashMap<Node, Integer> result = new HashMap<>();
        while (!nodeHeap.isEmpty()) {
            NodeRecord record = nodeHeap.pop();
            Node cur = record.node;
            int distance = record.distance;
            //每次找到一个节点后，遍历其边，找到最短distance
            for (Edge edge : cur.edges) {
                nodeHeap.addOrUpdateOrIgnore(edge.to, edge.weight + distance);
            }
            result.put(cur, distance);
        }
        return result;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

2 经典递归题目

暴力递归：
所谓暴力递归其实就是尝试的过程

1. 把问题转换为规模缩小了的同类问题的子问题
2. 有明确的不需要继续进行递归的条件（base case）【递归终止条件】
3. 有当得到了子问题的结果之后的决策过程
4. 不记录每一个子问题的解

2.1 打印N层汉诺塔从最左边移动到最右边的全部过程

也可以定义6个函数来实现【此处采用浓缩版】

public class Solution {
    //给定一个数字【将数字从1-N依次按照汉诺塔方式移动】
    public static void hanNota(int N) {
        if (N > 1) {
            func(N, "left", "right", "mid");
        }
    }

    //将6个小函数浓缩成一个【左到右、左到中。。。。】
    public static void func(int N, String from, String to, String other) {
        if (N == 1) {
            System.out.println("Move 1 from " + from + " to " + to);
        } else {
            //函数都一样，只是传入的东西不同
            //1-N-1层，从left移动到mid【相对于N层：从N层的from到N层的other】
            func(N - 1, from, other, to);
            System.out.println("Move " + N + " from " + from + " to " + to);
            func(N - 1, other, to, from);
        }
    }

    public static void main(String[] args) {
        hanNota(3);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

拓展：LeetCode-086:

class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        int N = A.size();
        if(N > 0){
            func(N, A, C, B);
        }
        System.out.println(C);
    }
    public void func(int N, List<Integer> from, List<Integer> to, List<Integer> other){
        //如果是只有一层了
        if(N == 1){
            //每次移动最上层，对于数组来说就是末尾
            to.add(from.remove(from.size() - 1));
        } else {
            func(N - 1, from, other, to);
            to.add(from.remove(from.size() - 1));
            func(N - 1, other, to, from);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.2 打印一个字符串的全部子序列

假如字符串为abc,全部子序列就是a要或者不要，b要或者不要，c要或者不要

public class PrintAllSequenceDemo {

    /**
     * 获取字符串s的所有子序列
     *
     * @param s
     * @return
     */
    public static List<String> subs(String s) {
        char[] str = s.toCharArray();
        String path = "";
        List<String> ans = new ArrayList<>();
        process1(str, 0, ans, path);
        return ans;
    }

    //str是固定参数
    //来到了str[index]字符，index是当前所在位置
    //之前的决定已经不能改变了，就是path
    //str[index..]还能决定，之前已经确定，index后面还可以自由选择
    //把所有生成的子序列，放入到ans里去
    public static void process1(char[] str, int index, List<String> ans, String path) {
        if (index == str.length) {
            //如果走到了字符串末尾，表明一种情况诞生了
            ans.add(path);
            return;
        }
        //没有要index位置的字符
        process1(str, index + 1, ans, path);
        //要了index位置的字符
        process1(str, index + 1, ans, path + String.valueOf(str[index]));
    }

    public static void main(String[] args) {
        String test = "abc";
        List<String> ans1 = subs(test);
        for (String str : ans1) {
            System.out.println(str);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

2.3 打印一个字符串的全部子序列，要求不出现重复字面值的子序列

使用set过滤

public class PrintAllSequenceDemo {

    /**
     * 求不重复的子序列
     *
     * @param s
     * @return
     */
    public static List<String> subsNoRepeat(String s) {
        char[] str = s.toCharArray();
        String path = "";
        HashSet<String> set = new HashSet<>();
        process2(str, 0, set, path);
        List<String> ans = new ArrayList<>();
        for (String cur : set) {
            ans.add(cur);
        }
        return ans;
    }

    public static void process2(char[] str, int index, HashSet<String> set, String path) {
        if (index == str.length) {
            set.add(path);
            return;
        }
        //没要
        process2(str, index + 1, set, path);
        //要了
        process2(str, index + 1, set, path + String.valueOf(str[index]));
    }

    public static void main(String[] args) {
        String test = "acccc";
        List<String> list = subsNoRepeat(test);
        for(String str : list){
            System.out.println(str);
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

2.4 打印一个字符串的全部排列

方法一：将字符放入list集合中

//求字符的全排列
public class PermutationDemo {

    /**
     * 全排列
     *
     * @return
     */
    public static List<String> permutation1(String s) {
        List<String> ans = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return ans;
        }
        //将字符串拆成字符【挨个拼接】
        char[] str = s.toCharArray();
        //存储字符
        ArrayList<Character> rest = new ArrayList<>();
        for (char c : str) {
            rest.add(c);
        }
        //起始路径
        String path = "";
        func(rest, path, ans);
        return ans;
    }

    public static void func(ArrayList<Character> rest, String path, List<String> ans) {
        //字符集合为空
        if (rest.isEmpty()) {
            ans.add(path);
            return;
        } else {
            for (int i = 0; i < rest.size(); ++i) {
                char c = rest.get(i);
                rest.remove(i);
                func(rest, path + String.valueOf(c), ans);
                //恢复现场
                rest.add(i, c);
            }
        }
    }

    public static void main(String[] args) {
        String s = "abc";
        List<String> list = permutation1(s);
        for(String str : list){
            System.out.println(str);
        }
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

方法二：在字符串数组中，直接交换位置

//求字符的全排列【交换字符位置】
public class PermutationDemo {

    public static List<String> permutation2(String s){
        List<String> ans = new ArrayList<>();
        if(s == null || s.length() == 0){
            return ans;
        }
        int index = 0;
        char[] str = s.toCharArray();
        func(str, 0, ans);
        return ans;
    }

    public static void func(char[] str, int index, List<String> ans){
        //遍历到了字符集末尾
        if(index == str.length){
            ans.add(String.valueOf(str));
            return;
        }
        for(int i = index; i < str.length; ++i){
            //在数组上交换字符位置【自己与自己交换也得算上】
            swap(str, i, index);
            func(str, index+1, ans);
            //恢复现场
            swap(str, index, i);
        }
    }

    public static void swap(char[] str, int i, int j){
        char c = str[i];
        str[i] = str[j];
        str[j] = c;
    }

    public static void main(String[] args) {
        String test = "abc";
        List<String> list = permutation2(test);
        for(String str : list){
            System.out.println(str);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

2.5 打印一个字符串的全部排列，要求不出现重复的排列

利用boolean[] 数组实现减枝

//求字符的全排列【去重，剪枝】
public class PermutationDemo {

    public static List<String> permutation3(String s) {
        List<String> ans = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return ans;
        }
        char[] str = s.toCharArray();
        //在char[]数组上交换
        int index = 0;
        func(str, index, ans);
        return ans;
    }

    public static void func(char[] str, int index, List<String> ans) {
        if (index == str.length) {
            //已经遍历完了【找到了一个组合方式】
            ans.add(String.valueOf(str));
            return;
        } else {
            //记录该字符是否已经有过了【方便剪枝】
            boolean[] visited = new boolean[256];
            for (int i = index; i < str.length; ++i) {
                //该字符没有被访问过
                if (!visited[str[i]]) {
                    visited[str[i]] = true;//更新状态
                    swap(str, index, i);
                    func(str, index + 1, ans);
                    //复原现场
                    swap(str, index, i);
                }
            }
        }
    }

    public static void swap(char[] str, int i, int j) {
        char c = str[i];
        str[i] = str[j];
        str[j] = c;
    }


    public static void main(String[] args) {
        System.out.println("=======");
        String s = "accc";
        List<String> ans3 = permutation3(s);
        for (String str : ans3) {
            System.out.println(str);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

2.6 递归实现逆序栈（微软面试题）

给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。如何实现？

//利用递归实现栈的反转
public class ReverseStackingUsingRecursive {

    public static void reverse(Stack<Integer> stack){
        if(stack.isEmpty()){
            return;
        }
        int i = f(stack);
        reverse(stack);
        stack.push(i);
    }

    //每次返回栈底元素
    public static int f(Stack<Integer> stack){
        int result = stack.pop();
        if(stack.isEmpty()){
            return result;
        } else {
            int last = f(stack);
            stack.push(result);
            return last;
        }
    }

    public static void main(String[] args) {
        Stack<Integer> test = new Stack<Integer>();
        test.push(1);
        test.push(2);
        test.push(3);
        test.push(4);
        test.push(5);
        reverse(test);
        while (!test.isEmpty()) {
            System.out.println(test.pop());
        }

    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39