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

亦凉 2024-04-07 12:37 64阅读 0赞

## 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: #####

![在这里插入图片描述][04df9f12b326447693a556678fc0f9c5.png]

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

[04df9f12b326447693a556678fc0f9c5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/9eca6dc3c7de4574b5ba708bbce7447c.png