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.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;
    }
}

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;
        }
    }

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;
    }
}

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;
 }

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;
    }
}

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;
    }
}

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;
}

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;
}

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
}

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;
}

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;
    }

}

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);
    }
}

拓展：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);
        }
    }
}

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);
        }
    }
}

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);
        }
    }

}

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);
        }
    }

}

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

//求字符的全排列【交换字符位置】
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);
        }
    }
}

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);
        }
    }
}

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());
        }

    }

}