算法-数据结构

不基于比拟的排序，核心思想就是桶排序，工夫复杂度都是O(N)，常见的不基于比拟的排序有计数排序、基数排序。 一、计数排序实用于排序元素的值范畴比拟小的，且是整数。（例如：年龄） 1、外围思路：（1）先筹备一个无限个数（比方200）的整型辅助数组，挨个遍历原始数组，失去的值是 i，则将辅助数组 i 地位的值加一 （2）遍历辅助数组，如果数组地位 i 上的值是k，则输入k个i，失去的即是排好序的数组 2、具体参考代码：/** * @author Java和算法学习：周一 */public static void countSort(int[] arr) {    if (arr == null || arr.length < 2) {        return;    }    // 统计    int max = Integer.MIN_VALUE;    for (int v : arr) {        max = Math.max(max, v);    }    int[] bucket = new int[max + 1];    for (int v : arr) {        bucket[v]++;    }    // 排序    int i = 0;    for (int j = 0; j < bucket.length; j++) {        while (bucket[j]-- > 0) {            arr[i++] = j;        }    }}从第一步中就能看进去，如果排序的值跨度比拟大，那么得筹备一个很大的辅助数组，然而数组绝大部分都是空着的，所以极大的节约空间，由此也能看出计数排序的局限性。 二、基数排序实用于十进制正整数。 1、外围思路：（1）遍历整个数组，失去最大值的十进制位数，同时将不满足最大位数的数高位补0 （2）筹备十个桶，从0 - 9编号，每个桶大小为原数组大小 （3）遍历数组，以个位数为规范，个位数的值是 i，则将其放到第 i 号桶里；遍历完后，从0号桶开始，挨个将外面的数倒进去（先进先出）。此时的数是依据个位数排序 （4）遍历数组，以十位数为规范，十位数的值是 i，则将其放到第 i 号桶里；遍历完后，从0号桶开始，挨个将外面的数倒进去（先进先出）。此时的数是依据十位数排序 ……直到遍历到最高位，最初倒进去的数即已排好序。 理论代码编写的时候，并没有筹备十个桶，而是筹备的一个长度为10的数组，这样能够大大节俭空间。 2、具体参考代码：/** * @author Java和算法学习：周一 */public static void radixSort(int[] arr) {    if (arr == null || arr.length < 2) {        return;    }    sort(arr, 0, arr.length - 1, maxBit(arr));}/** * 查找数组最大十进制位数 */public static int maxBit(int[] arr) {    int max = Integer.MIN_VALUE;    for (int value : arr) {        max = Math.max(max, value);    }    int res = 0;    while (max != 0) {        res++;        max /= 10;    }    return res;}private static void sort(int[] arr, int l, int r, int digit) {    int radix = 10;    // 辅助数组    int[] help = new int[r - l + 1];    // 有多少位就进桶几次、出桶几次    for (int d = 1; d <= digit; d++) {        // 前缀和数组：count[i]以后位（d位）是[0-i]的数有多少个        int[] count = new int[radix];        // 统计此时数组d位上的数各呈现了几次，        for (int i = l; i <= r; i++) {            // 失去d位上的值，范畴[0,9]            int v = getDigit(arr[i], d);            count[v]++;        }        // 此时，count[i]示意以后位（d位）是[0-i]的数有多少个        for (int i = 1; i < radix; i++) {            count[i] = count[i] + count[i - 1];        }        // 从右到左出桶        for (int i = r; i >= l; i--) {            // 失去d位上的值            int v = getDigit(arr[i], d);            help[--count[v]] = arr[i];        }        // 拷贝回原数组        for (int i = 0; i < help.length; i++) {            arr[l + i] = help[i];        }    }}public static int getDigit(int x, int d) {    return ((x / ((int) Math.pow(10, d - 1))) % 10);}三、基于比拟的排序和不基于比拟的排序比照基于比拟的排序适用范围更广（任何状况都能够），但工夫复杂度极限是O(N*logN) 不基于比拟的排序适用范围很窄，但工夫复杂度更好O(N) 本文全副代码：https://github.com/monday-pro/algorithm-study/tree/master/src/basic/nocomparesort

一、前缀树定义1）单个字符串中，字符从前到后的加到一棵多叉树上 2）字符放在边上，节点上有专属的数据项（常见的是pass和end值） 3）样本增加形式，每个字符串都从根节点开始加，如果没有路就新建，如果有路就复用 4）增加时，沿途节点的pass值加1，每个字符串完结时来到的节点end值加1 作用：能够更加不便的实现前缀相干的查问 二、简版的前缀树只能寄存26个小写字母组成的字符串 /** * 字符品种：只有26个小写字母 * * @author Java和算法学习：周一 */public static class Node1 {    // 以后节点被通过了几次    private int pass;    // 有多少个字符串以以后节点结尾    private int end;    // 以后节点所有的子节点    private Node1[] nexts;    // 节点只寄存26个小写字母    public Node1() {        pass = 0;        end = 0;        // node[i] == null，节点不存在        nexts = new Node1[26];    }}public static class Trie1 {    private Node1 root;    public Trie1() {        root = new Node1();    }    /**     * 向前缀树中增加一个字符串     */    public void insert(String word) {        if (word == null) {            return;        }        // 正在增加字符的节点        Node1 node = root;        // 曾经有字符通过该节点，批改节点pass值        node.pass++;        int path = 0;        // 以后单词挨个字符的增加到前缀树上        char[] chars = word.toCharArray();        for (char aChar : chars) {            // 以后字符应该走的门路            path = aChar - 'a';            // 以后节点的path门路对应节点不存在，则新建            if (node.nexts[path] == null) {                node.nexts[path] = new Node1();            }            // 以后节点的path门路对应节点必定曾经存在了            // 所以以后节点来到path门路对应节点            node = node.nexts[path];            // 曾经有字符达到该节点，批改pass值            node.pass++;        }        // 字符增加结束，批改最初节点的end值        node.end++;    }    /**     * word单词之前加过多少次     */    public int search(String word) {        if (word == null) {            return 0;        }        int index = 0;        char[] chars = word.toCharArray();        // 从根节点开始找        Node1 node = root;        for (char aChar : chars) {            // 以后字符应该走的门路            index = aChar - 'a';            // 以后节点的index门路对应节点不存在，间接返回            if (node.nexts[index] == null) {                return 0;            }            // 以后节点的index门路对应节点存在，则以后查找节点来到index门路对应节点            node = node.nexts[index];        }        // 最初以后节点的end值即是此单词加过的次数        return node.end;    }    /**     * 所有曾经退出的字符串中，有多少是以pre为前缀的     */    public int prefixNumber(String pre) {        if (pre == null) {            return 0;        }        int index = 0;        // 从根节点开始找        Node1 node = root;        // 挨个字符找        char[] chars = pre.toCharArray();        for (char aChar : chars) {            // 以后字符应该走的门路            index = aChar - 'a';            // 以后节点的index门路对应节点不存在，间接返回            if (node.nexts[index] == null) {                return 0;            }            // 以后节点的index门路对应节点存在，则以后查找节点来到index门路对应节点            node = node.nexts[index];        }        // 最初以后查找节点所处节点的pass值即是以pre为前缀的数量        return node.pass;    }    /**     * 在前缀树中删除某个字符串     */    public void delete(String word) {        // 字符串存在才执行删除逻辑        if (search(word) != 0) {            // 从根节点开始            Node1 node = root;            // 批改根节点pass值            node.pass--;            int index = 0;            char[] chars = word.toCharArray();            for (char aChar : chars) {                // 以后字符应该走的门路                index = aChar - 'a';                // 以后节点index门路对应节点的pass值减一                if (--node.nexts[index].pass == 0) {                    // 减一后如果为0，表明没有字符串再通过此节点                    // 将此节点index门路对应节点置空，帮忙GC                    node.nexts[index] = null;                    return;                }                // 减一后不为0，表明还有字符串通过此节点                // 则以后节点挪动到index门路对应的节点                node = node.nexts[index];            }            // 最初批改节点所在位置end值            node.end--;        }    }}三、通用的前缀树不限定寄存的内容 /** * 字符品种：不肯定只有26个小写字母 * * @author Java和算法学习：周一 */public static class Node2 {    // 以后节点被通过了几次    private int pass;    // 有多少个字符串以以后节点结尾    private int end;    // 以后节点所有的子节点，Key为节点对应字符串字符转换为整型后的ASCII码值    private HashMap<Integer, Node2> nexts;    public Node2() {        pass = 0;        end = 0;        nexts = new HashMap<>();    }}public static class Trie2 {    private Node2 root;    public Trie2() {        root = new Node2();    }    /**     * 向前缀树中增加一个字符串，此字符串不肯定全是小写字母     */    public void insert(String str) {        if (str == null) {            return;        }        // 正在增加字符串的节点        Node2 node = root;        // 曾经有字符通过该节点，批改节点pass值        node.pass++;        int index = 0;        // 以后字符串挨个字符的增加到前缀树上        char[] chars = str.toCharArray();        for (char aChar : chars) {            index = aChar;            // 以后节点的index门路对应节点不存在，则新建            if (!node.nexts.containsKey(index)) {                node.nexts.put(index, new Node2());            }            // 以后节点的index门路对应节点曾经存在了            // 所以以后节点来到index门路对应节点            node = node.nexts.get(index);            // 曾经有字符达到该节点，批改pass值            node.pass++;        }        // 字符串增加结束，批改最初节点的end值        node.end++;    }    /**     * 字符串之前加过多少次     */    public int search(String str) {        if (str == null) {            return 0;        }        int index = 0;        char[] chars = str.toCharArray();        // 从根节点开始找        Node2 node = root;        for (char aChar : chars) {            // 以后字符应该走的门路            index = aChar;            // 以后节点的index门路对应节点不存在，间接返回            if (!node.nexts.containsKey(index)) {                return 0;            }            // 以后节点的index门路对应节点存在，则以后查找节点来到index门路对应节点            node = node.nexts.get(index);        }        // 最初以后节点的end值即是此字符串加过的次数        return node.end;    }    /**     * 所有曾经退出的字符串中，有多少是以pre为前缀的     */    public int prefixNumber(String pre) {        if (pre == null) {            return 0;        }        int index = 0;        // 从根节点开始找        Node2 node = root;        // 挨个字符找        char[] chars = pre.toCharArray();        for (char aChar : chars) {            // 以后字符应该走的门路            index = aChar;            // 以后节点的index门路对应节点不存在，间接返回            if (!node.nexts.containsKey(index)) {                return 0;            }            // 以后节点的index门路对应节点存在，则以后查找节点来到index门路对应节点            node = node.nexts.get(index);        }        // 最初以后节点的pass值即是以pre为前缀的数量        return node.pass;    }    /**     * 在前缀树中删除某个字符串     */    public void delete(String str) {        // 字符串存在才执行删除逻辑        if (search(str) != 0) {            // 从根节点开始            Node2 node = root;            // 批改根节点pass值            node.pass--;            int index = 0;            char[] chars = str.toCharArray();            for (char aChar : chars) {                // 以后字符应该走的门路                index = aChar;                // 以后节点index门路对应节点的pass值减一                if (--node.nexts.get(index).pass == 0) {                    // 减一后如果为0，表明没有字符串再通过此节点                    // 将此节点index门路对应节点置空                    node.nexts.remove(index);                    return;                }                // 减一后不为0，表明还有字符串通过此节点                // 则以后节点挪动到index门路对应的节点                node = node.nexts.get(index);            }            // 最初批改节点所在位置end值            node.end--;        }    }}以上两种前缀树都只实现了最根本的性能，当理论我的项目中遇到相似的需要，能够在此基础上增加须要的性能即可，相当于提供了一个模板。 本文所有代码Github获取

上次咱们聊了堆和堆排序，这次咱们就顺着说说和堆无关的题目。 一、简直有序的数组排序1、题目形容已知一个简直有序的数组，简直有序是指，如果把数组排好序的话，每个元素挪动的间隔肯定不超过K，并且K绝对于数组长度来说是比拟小的。 请抉择一个适合的排序策略，对这个数组进行排序。 2、解决思路：从第一个数开始， 将前K+1个数放到小根堆里，弹出第一个数放到数组第一个地位； 将第K+2个数放到这个小根堆里，再弹出第一个数放到数组第二个地位； 将第K+3个数放到这个小根堆里，再弹出第一个数放到数组第三个地位； 直到小根堆为空 3、具体的参考代码： /** * @author Java和算法学习：周一 */    public static void sortArrayDistanceLessK(int[] arr, int k) {        if (arr == null || arr.length < 2 || k == 0) {            return;        }        // 默认是小根堆        PriorityQueue<Integer> heap = new PriorityQueue<>();        // 标记以后曾经放到堆中元素的数组下标        int index = 0;        // 将前k个数放进数组中        for (; index < k; index++) {            heap.add(arr[index]);        }        // 标记以后数组中曾经排好序的下标        int i = 0;        // 从第k+1个数始终到数组最初一个数，        for (; index < arr.length; index++) {            // 每次放进堆中一个数，            heap.add(arr[index]);            // 同时弹出此时堆顶元素放到数组中，排序下标后移            arr[i++] = heap.poll();        }        // 将小根堆中残余数据放到数组中        while (!heap.isEmpty()) {            arr[i++] = heap.poll();        }    }4、工夫复杂度为O(N*logK)堆中只有K+1个数，也就是调整为小根堆的过程，工夫复杂度是logK，因为须要遍历一遍整个数组，所以最初的工夫复杂度是O(N*logK)。 二、最大线段重合问题1、题目形容给定很多线段，每个线段都有两个数[start, end]，示意线段开始地位和完结地位，左右都是闭区间。 规定： 1）线段的开始地位和完结地位肯定都是整数 2）两个线段重合的定义：线段重合区域的长度必须>=1才示意线段重合 求：线段最多的重合区域中，蕴含了几条线段。 2、解决思路1）将所有线段依照开始地位从小到大排序，同时筹备一个小根堆用于寄存线段完结地位 2）遍历排序后的所有线段，将此时小根堆里小于等于此时线段开始地位的数弹出，同时将此时线段完结地位的数放到小根堆里，此时小根堆的个数即是从此时线段开始地位作为重合区域左边界的重合区域所蕴含线段的个数。（任何重合区域的左边界必然是某个线段的左边界） 因为此时小根堆里的数示意之前线段的右边界会穿过此时线段的左边界，而之前线段的左边界是小于此时线段的左边界的，所以小根堆的个数即是重合区域中蕴含线段的个数。 3）最初第2步中 最大的个数 即是 蕴含线段最多的重合区域中所蕴含的线段数 3、具体的参考代码： /** * @author Java和算法学习：周一 */    public static class Line {        private int start;        private int end;        public Line(int start, int end) {            this.start = start;            this.end = end;        }    }    /**     * 工夫复杂度 O(N*logN)     */    public static int lineCoverMaxByHeap(int[][] n) {        Line[] lines = new Line[n.length];        for (int i = 0; i < n.length; i++) {            lines[i] = new Line(n[i][0], n[i][1]);        }        // 将所有线段依照开始下标从小到大排序        Arrays.sort(lines, (o1, o2) -> o1.start - o2.start);        // 筹备一个小根堆（寄存线段的完结值）        PriorityQueue<Integer> heap = new PriorityQueue<>();        int cover = 0;        for (Line line : lines) { // O(N)            // 将小根堆中所有小于等于以后线段开始值的数据弹出            while (!heap.isEmpty() && heap.peek() <= line.start) { // O(logN)                heap.poll();            }            // 将以后线段的完结值放到小根堆中            heap.add(line.end);            cover = Math.max(cover, heap.size());        }        return cover;    }蕴含测试的所有代码Github获取

大家好，我是周一。 明天咱们聊聊堆，以及堆排序。 一、堆谈到堆，首先咱们要从二叉树说起，从二叉树到齐全二叉树，再才到堆。 1、二叉树每个结点最多只能有两棵子树，且有左右之分 2、齐全二叉树一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的程序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中（除最初一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树）编号为i的结点在二叉树中的地位雷同，则这棵二叉树称为齐全二叉树。 艰深的说法就是：叶子结点只能呈现在最上层和次上层，且最上层的叶子结点集中在树的左部。须要留神的是，满二叉树必定是齐全二叉树，而齐全二叉树不肯定是满二叉树。 对于某个地位为i的节点，左孩子（如果有）2i+1，右孩子（如果有）2i+2，父节点(i-1)/2（向下取整） 3、堆首先是一个齐全二叉树。同时辨别大根堆和小根堆。 大根堆：每一颗子树的最大值都是头节点。 小根堆：每一颗子树的最小值都是头节点。 （1）对于用户顺次输出数字的一个数组，如何将其结构为大根堆？ 每插入一个数都和父节点比拟，大于父节点则和父节点替换，直到根节点；如果小于父节点，则马上进行比拟。 // 对于新加进来的i地位的数，请放到数组适合地位，使其成为一个大根堆private void heapInsert(int[] arr, int i) {    // i = 0 或 i地位数小于父节点    // while蕴含这两种终止条件    while(arr[i] > arr[(i - 1)/2]) {        swap(arr, i, (i - 1)/2);        i = (i - 1)/2;    }}（2）获取以后数组最大值，并从堆中删除，同时维持大根堆构造 public int pop() {    int ans = heap[0];    swap(heap, 0, --heapSize);    heapify(heap, 0, heapSize);    return ans;}// 将index地位的数往下沉，直到较大的孩子都没本人大，或者没孩子了private void heapify(int[] arr, int index, int heapSize) {    // 左子树地位    int left = 2 * index + 1;    while(left < heapSize) {                // 找到左右子树哪个值更大       int maxIndex = (left + 1) < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;       // 将左右子树中较大的和父节点比拟       maxIndex = arr[maxIndex] > arr[index] ? maxIndex : index;       // 左右子树较大的值都小于父节点，进行循环            if (maxIndex == index) {           break;       }       // 将左右子树中较大的和父节点替换       swap(arr, maxIndex, index);       // 以后比拟的节点地位来到较大的子节点       index = maxIndex;       // 从新获取以后节点的左子树       left = 2 * index + 1;    }}4、PriorityQueue底层就是用堆实现的，默认是小根堆 5、工夫复杂度heapinsert，在曾经是堆构造的数中退出一个数，工夫复杂度是O(logN) heapify，在曾经是堆构造的数中退出一个数，工夫复杂度是O(logN) 二、堆排序1、将整个数组调整为大根堆，那么此时0地位的数就是最大值 2、将0地位和数组最大地位的数替换，此时的最大值就处于最初排好序的地位了 3、数组的调整范畴个数减一，循环执行1、2步，直到数组为空 public static void heapSort(int[] arr) {    if (arr == null || arr.length < 2) {        return;    }    // 将整个数组调整为大根堆，O(NlogN)    for (int i = 0; i < arr.length; i++) { // O(N)        heapinsert(arr, i); // O(logN)    }    // 获取以后数组大小    int heapSize = arr.length;    // 0地位和数组最大地位的数替换    swap(arr, 0, --heapSize);    while(heapSize > 0) {        // 将替换到0地位的数下沉，行将以后数组再次调整为大根堆        heapify(arr, 0, heapSize);        // 0地位和数组最大地位的数替换        swap(arr, 0, --heapSize);    }    }4、复杂度 （1）工夫复杂度：O(N*logN) （2）额定空间复杂度：O(1)

大家好，我是周一。 最近几篇算法，咱们都是聊的归并排序，归并排序也说的差不多了，明天聊聊疾速排序。 一、荷兰国旗问题1、啥是荷兰国旗问题荷兰国旗是由红白蓝3种颜色的条纹拼接而成，如下图所示： 假如这样的条纹有多条，且各种色彩的数量不一，并且随机组成了一个新的图形，新的图形可能如下图所示，但不仅仅只有这一种状况： 需要是：把这些条纹依照色彩排好，红色的在上半局部，红色的在两头局部，蓝色的在下半局部，咱们把这类问题称作荷兰国旗问题。 2、荷兰国旗问题的形象咱们把荷兰国旗问题形象成数组的模式是上面这样的： 给定一个整数数组和一个值M（存在于原数组中），要求把数组中小于M的元素放到数组的右边，等于M的元素放到数组的两头，大于M的元素放到数组的左边，最终返回一个整数数组，只有两个值，0地位是等于M的数组局部的左下标值、1地位是等于M的数组局部的右下标值。 进一步形象为更加通用的模式是上面这样的： 给定数组arr，将[l, r]范畴内的数（当然默认是 [ 0 - arr.length - 1 ]），小于arr[r]（这里间接取数组最左边的值进行比拟）放到数组右边，等于arr[r]放到数组两头，大于arr[r]放到数组左边。最初返回等于arr[r]的左, 右下标值。 3、解决的思路定义一个小于区，一个大于区；遍历数组，挨个和arr[r]比拟， （1）小于arr[r]，与小于区的后一个地位替换，以后地位后移； （2）等于arr[r]，以后地位间接后移； （3）大于arr[r]，与大于区的前一个地位替换，以后地位不动（替换到此地位的数还没比拟过，所以不动）。 遍历完后，arr[r]和大于区的最左侧地位替换。 最初返回，此时小于区的后一个地位，大于区的地位，即是最初的等于arr[r]的左, 右下标值。 4、具体的参考代码    /**     * 荷兰国旗问题     * <p>     * 把数组arr中，[l, r]范畴内的数，小于arr[r]放到数组最右边，等于arr[r]放到数组两头，大于arr[r]放到数组最左边     *     * @return 返回等于arr[r]的左, 右下标值     */    public static int[] netherlandsFlag(int[] arr, int l, int r) {        if (l > r) {            return new int[]{-1, -1};        }        if (l == r) {            return new int[]{l, r};        }        // 小于arr[r]的右边界，从L的右边一位开始        int less = l - 1;        // 大于arr[r]的左边界，从r开始，即以后右边界里曾经有arr[r]        int more = r;        // 以后正在比拟的下标        int index = l;        // 不能与 大于arr[r]的左边界 撞上        while (index < more) {            if (arr[index] < arr[r]) {                // 小于时，将以后地位的数和小于arr[r]的右边界的下一个地位替换                // 以后地位后移一位                swap(arr, index++, ++less);            } else if (arr[index] == arr[r]) {                // 等于时，以后地位后移一位即可                index++;            } else {                // 大于时，以后地位的数和大于arr[r]的左边界的前一个地位替换                // 以后地位不动                swap(arr, index, --more);            }        }        // 将arr[r]地位的数和大于arr[r]的左边界的数替换        // 此时整个数组就依照 小于、等于、大于arr[r] 分成了左中右三块        swap(arr, more, r);        // 最初整个数组中，等于arr[r]的左右边界别离是less + 1, more        return new int[]{less + 1, more};    }二、疾速排序1、啥是快排（排序流程）首先设定一个分界值，通过该分界值将数组分成左中右三局部。 （1）将小于分界值的数据集中到数组的右边，等于分界值的数据集中到数组的两头，大于分界值的数据集中到数组左边。 （2）而后，右边和左边的数据能够独立排序。对于左侧的数据，又能够取一个分界值，将该局部数据分成左中右三局部，同样在右边放较小值，两头放等于值，左边放较大值。左边数据也做同样的解决。 （3）反复上述过程，能够看出，这是一个递归过程。通过递归将左侧局部排好序后，再递归排好右侧局部的程序。当左、右两个局部各数据排序实现后，整个数组的排序也就实现了。 当看完了快排的流程，是不是发现快排的外围办法就是荷兰国旗问题，所以晓得为啥本文一开始就介绍荷兰国旗问题了吧。 2、形象后的快排流程（1）随机将数组中的某个数放到比拟地位上（即最右侧地位） （2）调用荷兰国旗办法，（此时等于区的数即在最初排好序的地位上），拿到等于区的左右下标 （3）小于区和大于区再各自递归调用（1）（2）步即可将小于区和大于区排好序。 3、具体的参考代码    /**     * 随机快排     */    public static void quickSortRandom(int[] arr) {        if (arr == null || arr.length < 2) {            return;        }        processRandom(arr, 0, arr.length - 1);    }    private static void processRandom(int[] arr, int l, int r) {        if (l >= r) {            return;        }        // 随机将数组中的某个数放到比拟地位上（即数组最左边地位）        // 这一步是保障快排工夫复杂度是O(N*logN)的要害，不然，快排的工夫复杂度是O(N^2)        swap(arr, l + (int) ((r - l + 1) * Math.random()), r);        // 将数组划分为 小于、等于、大于arr[r] 的左中右三块        int[] equalArea = netherlandsFlag(arr, l, r);        // 此时等于区域的值曾经处于最初排序后果的地位了        // 递归将左半局部的排好序        processRandom(arr, l, equalArea[0] - 1);        // 递归将右半局部的排好序        processRandom(arr, equalArea[1] + 1, r);    }    public static void swap(int[] arr, int i, int j) {        int tmp = arr[i];        arr[i] = arr[j];        arr[j] = tmp;    }

大家好，我是周一。 最近几篇算法，咱们都是聊的归并排序，明天再开一篇。再聊两题。 一、大于右侧数的两倍怕大家忘了归并排序，所以先拿一题练练手。 1、题目形容求给定数组中，以后数 大于 右侧数两倍 的个数 2、例子数组：[6, 7, 3, 2, 1] 以后数大于右侧数的两倍的数有(6,2)，(6,1)，(7,3)，(7,2)，(7,1)，(3,1) 所有总共有6个。 3、思路认真看过归并排序：解决小和、逆序对问题的搭档都晓得，咱们在求解时，都是和merge操作放在一起的。然而此题再和merge操作放在一起求解，难度、代码复杂度就很大了。 所以，咱们换个角度，很简略，咱们把 求个数的操作 和 merge操作 分成两个循环独自求，霎时就恍然大悟了。 4、具体的参考代码只有merge操作的代码，其余和归并排序的截然不同 private static int merge(int[] arr, int l, int mid, int r) {        int num = 0;        // l...mid, mid+1...r, 目前右组寻找的范畴 [mid+1, windowR)        int windowR = mid + 1;        for (int i = l; i <= mid; i++) {            while (windowR <= r && arr[i] > (arr[windowR] << 1)) {                windowR++;            }            // 此时，符合条件的个数为 (windowR - (mid+1))            // 因为此时windowR不满足要求，所以不是(windowR - (mid+1)) +1            num += windowR - mid - 1;        }        int[] help = new int[r - l + 1];        int i = 0;        int pL = l;        int pR = mid + 1;        while (pL <= mid && pR <= r) {            // 谁小拷贝谁（相等的拷贝左组的）            help[i++] = arr[pL] <= arr[pR] ? arr[pL++] : arr[pR++];        }        while (pL <= mid) {            help[i++] = arr[pL++];        }        while (pR <= r) {            help[i++] = arr[pR++];        }        for (int j = 0; j < help.length; j++) {            arr[l + j] = help[j];        }        return num;    }OK，热身结束。明天的重头戏当然是如何用归并排序解决LeetCode的这道Hard题。 二、LeetCode327. 区间和的个数那么咱们就看看在LeetCode的题目中，归并排序有何妙用呢。 1、题目形容https://leetcode-cn.com/probl... 给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范畴 [lower, upper] （蕴含 lower 和 upper）之内的 区间和的个数 。 区间和 S(i, j) 示意在 nums 中，地位从 i 到 j 的元素之和，蕴含 i 和 j (i ≤ j)。 2、例子输出：nums = [-2,5,-1], lower = -2, upper = 2 输入：3 解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和别离是：-2 、-1 、2 。 ...

大家好，我是周一。 在上一篇归并排序中，咱们讲了归并排序的基本概念、merge（合并）过程等，明天趁热打铁，咱们来说说应用归并排序的一些常见面试题。 一、小和问题1、题目形容：在一个数组中，每一个数右边比以后数小的数累加起来，叫做这个数组的小和。求一个给定数组的小和。 2、例子：数组为：[1,3,4,2,5] 1右边比1小的数：没有 3右边比3小的数：1 4右边比4小的数：1,3 2右边比2小的数：1 5右边比5小的数：1,3,4,2 所以小和为1+(1+3)+1+(1+3+4+2)=16 3、思路：找每一个数左边比以后数大的个数，(个数 * 以后数) 的累加和就是后果。 这咋和归并排序分割上的呢，认真想想，在左组和右组merge的时候，会比拟数的大小，这时就能够在右组找到比左组以后数大的个数。 4、具体的参考代码：/** * 小和问题：在一个数组中，每一个数右边比以后数小的数累加起来，叫做这个数组的小和。要求工夫复杂度O(N*logN)  * * @author Java和算法学习：周一 */public class SmallSum {    public static int smallSum(int[] arr) {        if (arr == null || arr.length < 2) {            return 0;        }        return process(arr, 0, arr.length - 1);    }    private static int process(int[] arr, int l, int r) {        if (l == r) {            return 0;        }        int mid = l + ((r - l) >> 1);        return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);    }    private static int merge(int[] arr, int l, int mid, int r) {        int[] help = new int[r - l + 1];        int i = 0;        int pL = l;        int pR = mid + 1;        int res = 0;        while (pL <= mid && pR <= r) {            // 当左组的数小于右组的数时， 以后右组的个数*以后数 的累加和 即是小和的后果            // 认真和归并排序比拟，发现就多了此处的代码。惟一的区别是，            // 等于的时候拷贝右组的，因为要在右组中找出比左组大的个数，必定不能先拷贝左组的，不然咋找出个数            res += arr[pL] < arr[pR] ? (r - pR + 1) * arr[pL] : 0;            help[i++] = arr[pL] < arr[pR] ? arr[pL++] : arr[pR++];        }        while (pL <= mid) {            help[i++] = arr[pL++];        }        while (pR <= r) {            help[i++] = arr[pR++];        }        for (int j = 0; j < help.length; j++) {            arr[l + j] = help[j];        }        return res;    }    /**     * 对数器办法     */    public static int comparator(int[] arr) {        int res = 0;        for (int i = 1; i < arr.length; i++) {            for (int j = 0; j < i; j++) {                res += arr[j] < arr[i] ? arr[j] : 0;            }        }        return res;    }    public static void main(String[] args) {        int maxSize = 100;        int maxValue = 100;        int testTimes = 100000;        boolean isSuccess = true;        for (int i = 0; i < testTimes; i++) {            int[] arr1 = generateArray(maxSize, maxValue);            int[] arr2 = copyArray(arr1);            if (smallSum(arr1) != comparator(arr2)) {                printArray(arr1);                printArray(arr2);                isSuccess = false;                break;            }        }        System.out.println(isSuccess ? "Nice" : "Error");    }    //------------------------------------------ TEST METHODS ----------------------------------------------    public static int[] generateArray(int maxSize, int maxValue) {        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];        for (int i = 0; i < arr.length; i++) {            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random());        }        return arr;    }    public static int[] copyArray(int[] arr) {        if (arr == null) {            return null;        }        int[] res = new int[arr.length];        for (int i = 0; i < arr.length; i++) {            res[i] = arr[i];        }        return res;    }    public static void printArray(int[] arr) {        if (arr == null) {            return;        }        for (int value : arr) {            System.out.print(value + " ");        }        System.out.println();    }}二、逆序对问题1、题目形容：设有一个数组 [a1, a2, a3,... an]，对于数组中任意两个元素ai，aj，若i<j，ai>aj，则阐明ai和aj是一对逆序对。求一个给定数组的逆序对个数。 2、例子：3 5 2 1 0 4 9 所有逆序对是：(3,2)，(3,1)，(3,0)，(5,2)，(5,1)，(5,0)，(5,4)，(2,1)，(2,0)，(1,0)。逆序对个数为10。 3、思路：合并的时候，从右往左合并，(此时右组地位 - mid地位) 的累加和 即是逆序对个数。 这又咋和归并排序分割上的呢，认真想想，在左组和右组merge的时候，会比拟数的大小，然而我要找到的是左边更小的，所以能够采纳从右往左合并的形式；同时在解决相等的时候，须要先拷贝右组的，这样能力精确找出右组小的个数。 4、具体的参考代码：/** * 逆序对问题：设有一个数组 [a1, a2, a3,... an]，对于数组中任意两个元素ai，aj，若i<j 且 ai>aj，则阐明ai和aj是一对逆序对。 * 求一个给定数组的逆序对个数。 * * @author Java和算法学习：周一 */public class ReversePair {    public static int reversePairNum(int[] arr) {        if (arr == null || arr.length < 2) {            return 0;        }        return process(arr, 0, arr.length - 1);    }    private static int process(int[] arr, int l, int r) {        if (l == r) {            return 0;        }        int mid = l + ((r - l) >> 1);        return process(arr, l, mid) + process(arr, mid + 1, r) + merge(arr, l, mid, r);    }    private static int merge(int[] arr, int l, int mid, int r) {        // 辅助数组        int[] help = new int[r - l + 1];        // 辅助下标，因为从右往左合并，所以下标为数组最大值        int i = help.length - 1;        // 同理，左组第一个数地位为mid        int pL = mid;        // 右组第一个数为最初一个        int pR = r;        // 逆序对个数        int num = 0;        while (pL >= l && pR >= (mid + 1)) {            // 找到右组第一个比左组小的数，则以后满足要求的逆序对个数为 (pR - (mid + 1) + 1) 即是 (pR - mid)            num += arr[pL] > arr[pR] ? (pR - mid) : 0;            // 从右往左拷贝，相等的拷贝右组的            help[i--] = arr[pL] > arr[pR] ? arr[pL--] : arr[pR--];        }        // 左组和右组有且仅有一个未拷贝完，所以以下两个循环只会执行其中一个        while (pL >= l) {            help[i--] = arr[pL--];        }        while (pR > mid) {            help[i--] = arr[pR--];        }        // 拷贝回原数组        for (int j = 0; j < help.length; j++) {            arr[l + j] = help[j];        }        return num;    }    /**     * 对数器用于测试     */    public static int comparator(int[] arr) {        int num = 0;        for (int i = 0; i < arr.length; i++) {            for (int j = i + 1; j < arr.length; j++) {                if (arr[j] < arr[i]) {                    num++;                }            }        }        return num;    }    public static void main(String[] args) {        int testTime = 1000000;        int maxSize = 100;        int maxValue = 100;        boolean isSuccess = true;        for (int i = 0; i < testTime; i++) {            int[] arr1 = generateRandomArray(maxSize, maxValue);            int[] arr2 = copyArray(arr1);            if (reversePairNum(arr1) != comparator(arr2)) {                printArray(arr1);                printArray(arr2);                isSuccess = false;                break;            }        }        System.out.println(isSuccess ? "Nice" : "Error");    }    //--------------------------------------- 辅助测试的办法 ---------------------------------------------    public static int[] generateRandomArray(int maxSize, int maxValue) {        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];        for (int i = 0; i < arr.length; i++) {            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random());        }        return arr;    }    public static int[] copyArray(int[] arr) {        if (arr == null) {            return null;        }        int[] res = new int[arr.length];        for (int i = 0; i < arr.length; i++) {            res[i] = arr[i];        }        return res;    }    public static void printArray(int[] arr) {        if (arr == null) {            return;        }        for (int value : arr) {            System.out.print(value + " ");        }        System.out.println();    }}OK，明天就临时先说利用归并排序解决小和和逆序对问题的题目。 有时候，各种排序算法把握它自身并不难，难的是你可能充沛了解它的过程和精华，更难的是在真正遇到理论题目的时候，可能想到用这种排序算法来解决它。所以，算法无捷径，唯有多练习，在有足够多的量，积攒质变，而后能力迎来量变，那时能力信手拈来，加油。

一、概念归并排序（Merge Sort）是建设在归并操作上的一种无效，稳固的排序算法，该算法是采纳分治法的一个十分典型的利用。 将已有序的子序列合并，失去齐全有序的序列；即先使每个子序列有序，再使子序列段间有序。 二、排序过程1、归并操作，指的是将两个程序序列合并成一个程序序列的办法。 如：数组 {6，202，100，301，38，8，1} 初始状态：6,202,100,301,38,8,1 第一次归并后：{6,202},{100,301},{8,38},{1}； 第二次归并后：{6,100,202,301}，{1,8,38}； 第三次归并后：{1,6,8,38,100,202,301}； 2、归并操作步骤如下： （1）申请空间，大小为两个曾经排好序的序列之和，该空间用来做辅助数组 （2）设定两个指针，最后地位别离为两个曾经排序序列的起始地位 （3）比拟两个指针所指向的元素，抉择绝对小的元素放入到合并空间（相等抉择左组），并挪动指针到下一地位。 反复步骤3直到某一指针越界。将另一序列剩下的所有元素间接复制到合并序列（辅助数组）尾，将辅助数组数据拷贝回原数组。 三、Master公式预计工夫复杂度Master公式：剖析递归函数的工夫复杂度，要求子问题规模统一 形如：T(N) = a * T(N/b) + O(N^d)（其中a、b、d都是常数）的递归函数，能够间接通过Master公式来确定工夫复杂度1）如果log(b,a) < d，工夫复杂度为O(N^d)2）如果log(b,a) > d，工夫复杂度为O(N^log(b,a))3）如果log(b,a) == d，工夫复杂度为O(N^d * logN)依据Master公式可得 T(N) =2 * T(N/2) + O(N) 因为每次都是拆分为两个子问题，每个子问题占总规模的一半，且合并过程的工夫复杂度是O(N) 可得归并排序的工夫复杂度是O(N*logN)。 四、代码实现1、递归办法实现 /** * 1.递归办法实现 */ public static void mergeSort1(int[] arr) { if (arr == null || arr.length < 2) { return; } process(arr, 0, arr.length - 1); } private static void process(int[] arr, int l, int r) { if (l == r) { return; } int mid = l + ((r - l) >> 1); // 左组递归 process(arr, l, mid); // 右组递归 process(arr, mid + 1, r); // 合并 merge(arr, l, mid, r); } private static void merge(int[] arr, int l, int m, int r) { // 辅助数组 int[] help = new int[r - l + 1]; int i = 0; // 左组地位 int pL = l; // 右组地位 int pR = m + 1; while (pL <= m && pR <= r) { // 谁小拷贝谁，相等的拷贝左组 help[i++] = arr[pL] <= arr[pR] ? arr[pL++] : arr[pR++]; } // pL和pR有且只有一个会越界，也就是上面两个while只有一个会执行 while (pL <= m) { help[i++] = arr[pL++]; } while (pR <= r) { help[i++] = arr[pR++]; } // 拷贝回原数组 for (int j = 0; j < help.length; j++) { arr[l + j] = help[j]; } }2、迭代形式实现定义一个步长，初始值为1。从0地位的数开始，每两个步长的数merge完后拷贝回原数组，步长*2；再从0地位的数开始，每两个步长的数merge完后拷贝回原数组，步长*2……直到（步长 > 数组长度 / 2） /** * 2.迭代形式实现归并排序 * <p> * 步长调整次数 复杂度是logN，每次调整步长都会遍历一遍整个数组 复杂度是N，整个的工夫复杂度是O(N*logN) */ public static void mergeSort2(int[] arr) { if (arr == null || arr.length < 2) { return; } int N = arr.length; // 步长初始值 int mergeSize = 1; // 步长不能超过数组长度 while (mergeSize < N) { // 以后左组的第一个地位 int L = 0; // 左组也不能超过数组长度 while (L < N) { // 左组最初一个地位 int M = L + mergeSize - 1; // 如果左组最初一个地位越界，表明左组都不够则不须要merge if (M >= N) { break; } // 右组的最初一个地位 // 右组第一个地位是 M + 1，满足个数要求则右组大小是mergeSize，所以最初一个地位是 (M + 1) + mergeSize - 1 // 不满足则是数组的最大地位 N - 1 int R = Math.min(M + mergeSize, N - 1); // 目前 左组：L......M，右组：M+1......R merge(arr, L, M, R); // 下一次左组的地位（所以才须要判断L < N） L = R + 1; } // 避免溢出 // 当步长很凑近N的最大值时，乘以2扩充步长后，步长就溢出了 // 不能取 >=，假如最大值是9，mergeSize = 4时就不会扩充步长了，然而mergeSize = 8时还有一次merge，所以不能取 = if (mergeSize > N / 2) { break; } // 步长每次扩充2倍 mergeSize <<= 1; } }

1、如何用栈构造实现队列构造首先，用一个栈必定是实现不了的。所以，思考两个栈来实现。一个是push栈、一个是pop栈。 放数据的时候往push栈放，当取数据的时候，将数据全副倒到pop栈，再从pop栈取数据。 留神： （1）倒数据的时候要一次性倒完（2）如果pop栈没有拿完，不能倒数据具体代码： package basic.stackqueue;import java.util.Stack;/** * 应用栈构造实现队列构造的性能 * * @author 周一 */public class TwoStacksImplementQueue { /** * 应用两个栈来实现队列构造 */ public static class TwoStackQueue<T> { // 用于寄存增加数据的栈 public Stack<T> stackPush; // 用于寄存获取数据的栈 public Stack<T> stackPop; public TwoStackQueue() { stackPush = new Stack<>(); stackPop = new Stack<>(); } /** * 倒数据 */ private void pushToPop() { // pop为空才倒数据 if (stackPop.empty()) { // push有数据可倒，并且一次性倒完 while (!stackPush.empty()) { stackPop.push(stackPush.pop()); } } } /** * 增加数据都往stackPush栈放 */ public void add(T data) { stackPush.push(data); } public T poll() { if (stackPush.empty() && stackPop.empty()) { throw new RuntimeException("Queue is empty"); } // 拿数据前先执行倒数据办法 pushToPop(); // 拿数据都从stackPop栈拿 return stackPop.pop(); } public T peek() { if (stackPush.empty() && stackPop.empty()) { throw new RuntimeException("Queue is empty"); } pushToPop(); return stackPop.peek(); } } public static void main(String[] args) { TwoStackQueue<Integer> test = new TwoStackQueue<>(); test.add(1); test.add(4); test.add(3); test.add(2); System.out.println(test.peek()); System.out.println(test.poll()); System.out.println(test.peek()); System.out.println(test.poll()); System.out.println(test.peek()); System.out.println(test.poll()); System.out.println(test.peek()); System.out.println(test.poll()); }}2、如何用队列构造实现栈构造同理，想用一个队列来实现，是不行的。所以，思考两个队列来实现。 ...

优先队列有什么用？能够求一些数据里的最大几个值，能够设定事件程序。 为什么不间接排序后再从头拿？ 假如数据量很大时，比方1亿个选10个最大的，你排好序内存可能装不下。优先队列只有10个空间，间接往队列尾巴插入就行。 根底优先队列的根底是把数据结构齐全二叉树构造，用数组实现。 树的个性父节点比任何一个子节点大。父节点的地位是k，子节点别离是2k和2k+1优先队列应用时，每次都从根节点拿数据，而后从新调整树结构。 插入与删除插入时，数据插入到尾部，而后用【上浮】操作使其到适合地位，达成有序。 public void insert(Key v){ pq[++N] = v; swim(N);}删除时，移除删除节点，同时把尾部的节点换到删除地位，而后用【下沉】操作使其到适合地位，达成有序。 /** * 删除。该数组0地位不存数据，从1开始存。 * @return*/public Key deleteMax(){ Key key = pq[1]; exchange(1, N--); pq[N+1] = null; sink(1); return key;}上浮对应插入操作。新插入的数据放在开端，它必然突破了本来树的有序性。这时须要将插入的节点和父节点比拟。 如果该节点比父节点大，则替换他们地位。达成【父节点比子节点大】这个个性。而后再一直与上一级的父节点比拟，直到满足个性。 //由个性2得：当子节点是k时，父节点地位是k/2private void swim(int k){ while (k > 1 && less(k/2, k)){ exchange(k, k/2); k = k/2; }}下沉对应删除操作。原先删除的地位被最尾部的节点取代，这也突破了树的有序性。这时该节点要和和子节点比拟，首先得有子节点，其次要选大的那个子节点（这样选出来的节点能力胜任父节点），说白了就是该节点，与两个子节点之间选个最大的当父节点。选到适合的子节点作为父节点后，再往一直下一级比拟，直到没有子节点或者有序。 private void sink(int k){ //这个条件是保障有叶子节点 while (2 * k < N){ //左子节点的坐标 int j = 2 * k; //这一段是比拟左右叶子节点哪个大，要选大的那个 if(j < N && less(j, j+1)){ j++; } //如果k > j,阐明排序失常，间接退出，k < j时替换它们的地位，持续向下比拟 if(!less(k, j)){ break; } exchange(k, j); k = j; } }Java里有对应的实现线程平安：PriorityBlockingQueue ...

function createArray(num) { let res = []; for (let i = 0; i < num; i++) { res.push(Math.floor(Math.random() * num)); } return res;}function checkArraySorted(arr) { let res = true; for (let i = 0, length = arr.length - 1; i < length; i++) { if (arr[i] > arr[i + 1]) { res = false; break; } } return res;}let arr = createArray(10000);/** * 冒泡排序 * 复杂度: O(n2) * 327.085ms */function bubbleSort(arr) { let length = arr.length; for (let i = 0; i < length; i++) { for (let j = 0; j < length - i - 1; j++) { if (arr[j] > arr[j + 1]) { [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; } } }}/** * 抉择排序 * 复杂度: O(n2) * 94.6 ms */function selectSort() { let length = arr.length; for (let i = 0; i < length; i++) { let minIndex = i; for (let j = i + 1; j < length; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } } if (minIndex > i) { [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]]; } }}/** * 插入排序 * 工夫复杂度: 最差为O(n2), 空间复杂度: O(1) * 5.284ms * 思维: 假如前 i - 1 个元素曾经排序好了, 为第 i 个元素在前 i 个元素中找到正确的地位 * 适宜: nearly sorted数组 * 个性: 稳固; 对于 nearly sorted 数组, 工夫复杂度降为 O(1) */function insertSort(arr) { let length = arr.length; for (let outer = 1; outer < length; outer++) { let inner = outer; while (inner > 0 && arr[outer] < arr[inner - 1]) { arr[inner] = arr[inner - 1]; inner--; } arr[inner] = arr[outer]; }}/** * 归并排序 * 工夫复杂度: O(nlogn) 空间复杂度: O(nlogn) * 27.349ms */function mergeSort(arr) { if (arr.length > 1) { let mid = arr.length >> 1; let left = mergeSort(arr.slice(0, mid)); let right = mergeSort(arr.slice(mid)); arr = merge(left, right); } return arr; function merge(left, right) { let i = j = 0; let res = []; while (left[i] && right[j]) { if (left[i] < right[j]) { res.push(left[i]); i++; } else { res.push(right[j]); j++; } } return res.concat(left[i] ? left.slice(i) : right.slice(j)); }}/** * 疾速排序 * 工夫复杂度: O(nlogn) * 22.066ms * */function quickSort(arr) { if (arr.length < 2) { return arr; } let base = arr[0]; let less = []; let greater = []; for (let i = 1, length = arr.length; i < length; i++) { if (arr[i] > base) { greater.push(arr[i]); } else { less.push(arr[i]); } } return quickSort(less).concat(base).concat(quickSort(greater));}function quickSort2(arr) { return quick(arr, 0, arr.length - 1); function quick(arr, left, right) { if (right > left) { let index = partition(arr, left, right); if (left < index - 1) { quick(arr, left, index - 1); } quick(arr, index, right); } return arr; } function partition(arr, left, right) { let pivot = arr[(left + right) >> 1]; while (left <= right) { while (arr[left] < pivot) { left++; } while (arr[right] > pivot) { right--; } if (left <= right) { [arr[left], arr[right]] = [arr[right], arr[left]]; left++; right--; } } return left; }}console.time();arr = quickSort2(arr);console.timeEnd();console.log(checkArraySorted(arr));

给你一个整数数组 coins ，示意不同面额的硬币；以及一个整数 amount ，示意总金额。 计算并返回能够凑成总金额所需的 起码的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 你能够认为每种硬币的数量是有限的。 示例 1： 输出：coins = [1, 2, 5], amount = 11输入：3 解释：11 = 5 + 5 + 1示例 2： 输出：coins = [2], amount = 3输入：-1示例 3： 输出：coins = [1], amount = 0输入：0示例 4： 输出：coins = [1], amount = 1输入：1示例 5： 输出：coins = [1], amount = 2输入：2解题思路这道题有些人可能会想到贪婪法，优先用面值大的硬币去凑，然而贪婪无奈取得最优解。例如上面这个例子： int[] coins = {1, 2, 5, 7, 10};int amount = 14;如果用贪婪法，那么首先必定是用面值为 10 的硬币，而后还需两个面值为 2 的硬币，总共须要 3 个硬币。但事实上，只须要两个面值为 7 的硬币就能凑出 14 的金额。因而这道题须要用动静布局的思维。 ...

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你能够尽可能地实现更多的交易（屡次交易一支股票）。 留神： 你不能同时参加多笔交易（你必须在再次购买前发售掉之前的股票）。 示例 1: 输出: prices = [7,1,5,3,6,4]输入: 7解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能取得利润 = 5-1 = 4 。  随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能取得利润 = 6-3 = 3 。示例 2: 输出: prices = [1,2,3,4,5]输入: 4解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能取得利润 = 5-1 = 4 。  留神你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参加了多笔交易，你必须在再次购买前发售掉之前的股票。示例 3: ...

给定一个数组 prices ，它的第 i 个元素 prices[i] 示意一支给定股票第 i 天的价格。 你只能抉择 某一天 买入这只股票，并抉择在 将来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你能够从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。 示例 1： 输出： [7,1,5,3,6,4]输入： 5解释： 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。留神利润不能是 7-1 = 6, 因为卖出价格须要大于买入价格；同时，你不能在买入前卖出股票。示例 2： 输出： prices = [7,6,4,3,1]输入： 0解释： 在这种状况下, 没有交易实现, 所以最大利润为 0。暴力法写两层 for 循环，一一比拟，必定能比进去，代码就不写了。 工夫复杂度：O(n2)空间复杂度: O(1) 动静布局定义子问题 假如咱们曾经晓得 i-1 个股票的最大利润为 dp[i-1] ，显然 i 个间断股票的最大利润要么是 dp[i-1] ，要么就是 prices[i] - minprice （minprice 为前 i-1 支股票的最小值）。 状态转移方程 ...

定义 (维基百科)在一个序列汇合中（通常为两个序列）查找所有序列中最长的子序列。这与查找最长公共子串的问题不同的中央是：子序列不须要在原序列中占用间断的地位。 最长公共子序列问题是一个经典的计算机科学问题，也是数据比拟程序，比方 Diff工具 和 生物信息学利用的根底。它也被宽泛地利用在 版本控制，比方Git用来和谐文件之间的扭转解决方案这类问题通常都是采纳动静布局的思维来解决，外围就是结构出动静解决方程。 以两个序列 X、Y 为例子：　设有二维数组dp[i,j]示意X的第i位和Y的第j位之前的最长公共子序列的长度，则有： $$ dp[i,j]= \begin{cases} dp[i-1][j-1]+1& \text{(X[i]==Y[j])}\\ max\{dp[i-1,j],dp[i,j-1]\}& \text{(X[i]!=Y[j])} \end{cases}$$ 工夫复杂度和空间复杂度都是O(mn)。力扣水题 func longestCommonSubsequence(text1 string, text2 string) int { len1, len2 := len(text1), len(text2) if len1 == 0 || len2 == 0 { return 0 } commonSub := make([][]int, len1+1, len1+1) // 初始化二维数据 for i := 0; i <= len1; i++ { commonSub[i] = make([]int, len2+1, len2+1) } for i := 0; i < len1; i++ { for j := 0; j < len2; j++ { if text1[i] == text2[j] { commonSub[i+1][j+1] = commonSub[i][j] + 1 } else { commonSub[i+1][j+1] = max(commonSub[i][j+1], commonSub[i+1][j]) } } } return commonSub[len1][len2]}func max(a, b int) int { if a > b { return a } else { return b }}

对于最长公共子序列的动静布局算法剖析示例引出： 给定序列\( X = \{A, B, C, B, D, A, B\} \)和 \( Y = \{B, D, C, A, B, A\} \)，要求找出它们的最长公共子序列。什么是子序列？ 简略来说，就是从某个给定的序列中，依照从左向右的程序提取出某些元素形成的序列。那么对于上述示例中的\( X \)来说，\( \{B, C, D, B\} \)就是其中的一个子序列.那么最长公共子序列就是求两个序列中最长雷同的子序列，对于上述示例来说，\( \{B,C,B,A\},\{B,D,A,B\},\{B,C,A,B\} \)是两者的最长公共子序列。构造剖析： 最长公共子序列具备最优子结构的性质：某个问题的最优解蕴含其子问题的最优解。这里给出递推关系：假如序列\( X_n=\{x_1, x_2,...,x_n\} \)和序列\( Y_m=\{y_1,y_2,..,,y_m\} \)，而两者的最长公共子序列\( Z_k=\{z_1,z_2,...,z_k\} \)；那么： 当\( x_n=y_m \)时，有\(z_k=x_n=y_m\)，\( z_{k-1} \)为\( x_{n-1} \)和\( y_{m-1} \)的最长公共子序列；当\( x_n\neq y_m \)且\( z_k=y_m \)时，\( z_{k-1} \)为\( x_n \)和\( y_{m-1} \)的最长公共子序列；当\( x_n\neq y_m \)且\( z_k=x_n \)时，\( z_{k-1} \)为\( x_{n-1} \)和\( y_{m} \)的最长公共子序列.能够给出递归关系： ...

算法背景在之前，咱们探讨了冒泡排序，其算法外围，就是：相邻两数顺次比拟，让较大的值缓缓浮出水面，达到其适合的地位，使数组变得有序。也能够说，冒泡排序就是顺次从高到低确认元素的地位。在工夫复杂度上为稳固的 O（n²） 抉择排序也是一种稳固的 O（n²）排序办法，其算法的外围，就是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，寄存在序列的起始地位，而后再从残余的未排序元素中寻找到最小（大）元素，而后放到已排序的序列的开端 以上两种算法的局限在于，疏忽了原有数组，在某个片段内，是否是有序的，例如int[] arr = {0,1,2,3,5,4,3},在这个进行排序过程中，前3项在某个时刻曾经变得有序，无需再进行关注。 上面咱们来看一下插入排序： 插入排序，个别也被称为间接插入排序。对于大量元素的排序，它是一个无效的算法。插入排序是一种最简略的排序办法，它的根本思维是将一个记录插入到曾经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程应用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对以后元素后面有序表进行待插入地位查找，并进行挪动。------百度百科 算法思维插入排序的工作形式像许多人排序一手扑克牌。开始时，咱们的左手为空并且桌子上的牌面向下。而后，咱们每次从桌子上拿走一张牌并将它插入左手中正确的地位。为了找到一张牌的正确地位，咱们从右到左将它与已在手中的每张牌进行比拟。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌。 插入排序是指在待排序的元素中，假如后面n-1(其中n>=2)个数曾经是排好程序的，现将第n个数插到后面曾经排好的序列中，而后找到适合本人的地位，使得插入第n个数的这个序列也是排好程序的。依照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。 图解算法 两层循环，咱们首先保障0-i是有序的，而后再拿到数组中的第i+1个元素，从后往前插入到0-i中适合的地位，此时0-i+1也有序了，再拿到第0-i+2个元素，插入到0-i+1中适合的地位。始终到0-n全副有序。 JAVA代码第一种：public static void insertSorting(int[] arr){ for (int i = 1 ; i < arr.length; i++) { for (int j = i-1; j >= 0&&arr[j]>arr[j+1]; j--) { swap(arr,j,j+1); } } } public static void swap(int[] arr, int i,int j){ arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; }以上实现，将插入到适合地位进行替换的条件和for循环是否持续，做了合并。第二种实现形式不合并。 第二种：public static void insertSorting(int[] arr){ for (int i = 1 ; i < arr.length; i++) { for (int j = i-1; j >= 0; j--) { if (arr[j]>arr[j+1]) swap(arr,j,j+1); else break; } } } public static void swap(int[] arr, int i,int j){ arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; }两种代码的执行是一样的，只是写法不同。第二种代码的else break；是必须加的，要不然工夫上就会减少，违反了插入排序的思维。 ...

组合总和题目形容：给定一个无反复元素的数组 candidates 和一个指标数 target ，找出 candidates 中所有能够使数字和为 target 的组合。 candidates 中的数字能够无限度反复被选取。 阐明： 所有数字（包含 target）都是正整数。解集不能蕴含反复的组合。示例阐明请见LeetCode官网。 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 解法一：穷举法相似结构一棵多叉树，最大深度为candidates数组的长度，而后获取所有可能的门路，最大门路是由根节点到叶子节点，判断所有的门路之和是否等于target，如果相等，则加到后果集中，最初须要判重，把反复的组合去掉，最初返回。import java.util.*;public class LeetCode_039 { /** * 穷举法 * * @param candidates * @param target * @return */ public static List<List<Integer>> combinationSum(int[] candidates, int target) { // 后果集 List<List<Integer>> result = new ArrayList<>(); // 所有可能的组合状况 Queue<List<Integer>> allPossibleCombinations = new LinkedList<>(); // 初始化所有的状况 for (int candidate : candidates) { List<Integer> onePossibleCombination = new ArrayList<>(); onePossibleCombination.add(candidate); allPossibleCombinations.add(onePossibleCombination); } while (!allPossibleCombinations.isEmpty()) { List<Integer> temp = allPossibleCombinations.poll(); int sum = 0; for (Integer num : temp) { sum += num; } if (sum == target) { result.add(temp); } else if (sum < target) { for (int candidate : candidates) { // List复制办法 List<Integer> toAdd = new ArrayList<>(Arrays.asList(new Integer[temp.size()])); Collections.copy(toAdd, temp); toAdd.add(candidate); allPossibleCombinations.add(toAdd); } } } // 去重后的后果 List<List<Integer>> result1 = new ArrayList<>(); for (int i = 0; i < result.size(); i++) { boolean isRepeated = false; List<Integer> one = result.get(i); Collections.sort(one); for (int j = i + 1; j < result.size(); j++) { List<Integer> two = result.get(j); Collections.sort(two); if (one.size() != two.size()) { continue; } boolean equals = true; for (int x = 0; x < one.size(); x++) { if (!one.get(x).equals(two.get(x))) { equals = false; continue; } } if (equals) { isRepeated = true; } } if (!isRepeated) { result1.add(one); } } return result1; } public static void main(String[] args) { int[] candidates = new int[]{8, 10, 6, 3, 4, 12, 11, 5, 9}; for (List<Integer> integers : combinationSum(candidates, 28)) { for (Integer integer : integers) { System.out.print(integer + " "); } System.out.println(); } }}【每日寄语】 不要急着让生存给予所有的答案，有时咱们须要急躁的期待。置信过程，坦然前行，不负生存，生存也必不负你。

include<stdio.h>include<stdlib.h>include<stdbool.h>define MAXSTRLEN 255// 存储构造typedef unsigned char SString[MAXSTRLEN + 1]; // 奢侈匹配模式int Index(SString S, SString T, int pos){ int i = pos;int j = 1;while(i<S[0] && j<=T[0]){ if(S[i] == T[j]){ ++i; ++j; }else{ i = i-j+2; j = 1; }}if(j>T[0]){ return i-T[0];}return 0;} bool StrAssign(SString str, char *src){ char * c = src;for(int i=0; *c!='\0'; ++i, ++c){ if(0==i){ str[0] = 0; }else{ str[0] = 0; for(int j=1; j<=i; j++){ str[j] = src[j-1]; str[0] +=1; } }}} ...

简介均衡二叉搜寻树是一种非凡的二叉搜寻树。为什么会有均衡二叉搜寻树呢？ 考虑一下二叉搜寻树的非凡状况，如果一个二叉搜寻树所有的节点都是右节点，那么这个二叉搜寻树将会进化成为链表。从而导致搜寻的工夫复杂度变为O(n),其中n是二叉搜寻树的节点个数。 而均衡二叉搜寻树正是为了解决这个问题而产生的，它通过限度树的高度，从而将工夫复杂度升高为O(logn)。 AVL的个性在探讨AVL的个性之前，咱们先介绍一个概念叫做均衡因子，均衡因子示意的是左子树和右子树的高度差。 如果均衡因子=0，示意这是一个齐全均衡二叉树。 如果均衡因子=1，那么这棵树就是均衡二叉树AVL。 也就是是说AVL的均衡因子不可能大于1。 先看一个AVL的例子： 总结一下，AVL首先是一个二叉搜寻树，而后又是一个二叉均衡树。 AVL的构建有了AVL的个性之后，咱们看下AVL是怎么构建的。 public class AVLTree { //根节点 Node root; class Node { int data; //节点的数据 int height; //节点的高度 Node left; Node right; public Node(int data) { this.data = data; left = right = null; } }同样的，AVL也是由各个节点形成的，每个节点领有data，left和right几个属性。 因为是二叉均衡树，节点是否均衡还跟节点的高度无关，所以咱们还须要定义一个height作为节点的高度。 在来两个辅助的办法，一个是获取给定的节点高度： //获取给定节点的高度 int height(Node node) { if (node == null) return 0; return node.height; }和获取均衡因子： //获取均衡因子 int getBalance(Node node) { if (node == null) return 0; return height(node.left) - height(node.right); }AVL的搜寻AVL的搜寻和二叉搜寻树的搜寻形式是统一的。 ...

二叉树的层序遍历题目形容：给你一个二叉树，请你返回其按 层序遍历 失去的节点值。 （即逐层地，从左到右拜访所有节点）。 示例阐明请见LeetCode官网。 起源：力扣（LeetCode） 链接：https://leetcode-cn.com/probl... 著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 解法一：利用队列遍历二叉树队列的特点是先进先出，所以利用队列来遍历二叉树实现层序遍历，具体过程如下： 首先，如果root为空，间接返回空的List。如果root不为空，申明一个队列nodes，将root节点退出到队列中，申明一个result，而后遍历nodes中的节点，遍历过程如下： 首先，用count记录以后队列中节点的数量，即为以后层节点的数量，vals记录以后节点的值；从nodes中按程序取出count个节点，并且将相应的节点值放入vals中，同时如果以后节点的左右子节点不为空，按从左到右的程序放入nodes中。而后将vals退出到后果result中。反复遍历nodes中的节点，直到nodes为空。最初返回result即为层序遍历的后果。import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue;public class LeetCode_102 { /** * 利用队列遍历二叉树：队列的个性是先进先出 * @param root * @return */ public static List<List<Integer>> levelOrder(TreeNode root) { if (root == null) { return new ArrayList<>(); } List<List<Integer>> result = new ArrayList<>(); // 暂存每一行的节点 Queue<TreeNode> nodes = new LinkedList<>(); nodes.add(root); while (!nodes.isEmpty()) { // 每次遍历一行数据 List<Integer> vals = new ArrayList<>(); int count = nodes.size(); while (count > 0) { TreeNode curNode = nodes.poll(); vals.add(curNode.val); // 将以后节点的左右子节点从左到右放入队列 if (curNode.left != null) { nodes.add(curNode.left); } if (curNode.right != null) { nodes.add(curNode.right); } count--; } result.add(vals); } return result; } public static void main(String[] args) { TreeNode root = new TreeNode(3); root.left = new TreeNode(9); root.right = new TreeNode(20); root.right.left = new TreeNode(15); root.right.right = new TreeNode(7); for (List<Integer> integers : levelOrder(root)) { for (Integer integer : integers) { System.out.print(integer + " "); } System.out.println(); } }}【每日寄语】 虚心使人提高，自豪使人落后。

目录 图的存储构造图的存储构造次要分两种，一种是邻接矩阵，一种是邻接表。 邻接矩阵图的邻接矩阵存储形式是用两个数组来示意图。一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。 设图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为： 看一个实例，下图左就是一个无向图。 从下面能够看出，无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴，右上角的元和左下角绝对应的元全都是相等的。 从这个矩阵中，很容易晓得图中的信息。 （1）要判断任意两顶点是否有边无际就很容易了； （2）要晓得某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行或（第i列）的元素之和； （3）求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1就是邻接点； 而有向图考究入度和出度，顶点vi的入度为1，正好是第i列各数之和。顶点vi的出度为2，即第i行的各数之和。 若图G是网图，有n个顶点，则邻接矩阵是一个n*n的方阵，定义为： 邻接表邻接矩阵是不错的一种图存储构造，然而，对于边数绝对顶点较少的图，这种构造存在对存储空间的极大节约。因而，找到一种数组与链表相结合的存储办法称为邻接表。 邻接表的解决办法是这样的： （1）图中顶点用一个一维数组存储，当然，顶点也能够用单链表来存储，不过，数组能够较容易的读取顶点的信息，更加不便。 （2）图中每个顶点vi的所有邻接点形成一个线性表，因为邻接点的个数不定，所以，用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。 例如，下图就是一个无向图的邻接表的构造。 从图中能够看出，顶点表的各个结点由data和firstedge两个域示意，data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。 对于带权值的网图，能够在边表结点定义中再减少一个weight的数据域，存储权值信息即可。如下图所示。 两者区别对于一个具备n个顶点e条边的无向图 它的邻接表示意有n个顶点表结点2e个边表结点 对于一个具备n个顶点e条边的有向图 它的邻接表示意有n个顶点表结点e个边表结点 **如果图中边的数目远远小于n^2称作稠密图，这是用邻接表示意比用邻接矩阵示意节俭空间; 如果图中边的数目靠近于n^2,对于无向图靠近于n*(n-1)称作浓密图,思考到邻接表中要附加链域，采纳邻接矩阵表示法为宜。** 图的java实现这个实现是基于邻接矩阵的 顶点应用label作为顶点的标识 edgelist作为linkedlist，存储以这个顶点为终点的边 前面3个属性是为了应答其余操作（比方深度遍历等），特意保留的变量 package datastructure.graph.adjacencymatrixgraph;import java.util.Iterator;import java.util.LinkedList;import java.util.List;/**邻接矩阵的顶点类 * @author xusy * * @param <T> */public class Vertex<T> { /** * 可能标识这个定点的属性，能够用不同类型来标识顶点如String,Integer.... */ private T label; /** * 这个定点对应的边<br> * 如果为有向图，则代表以这个定点为终点的边 */ private List<Edge> edgeList; /** * 示意这个顶点是否已被拜访，在bfs和dfs中会被应用到 */ private boolean visited; /** * 该顶点的前驱节点<br> * 在求图中某两个顶点之间的最短门路时，在从起始顶点遍历过程中，须要记录下遍历到某个顶点时的前驱顶点 */ private Vertex previousVertex; /** * 这个定点的权值（留神不是边的权值） */ private double cost; /**创立顶点 * @param label 这个顶点的标识 * @param cost 这个顶点的权值 */ public Vertex(T label,double cost){ this.label=label; //用链表存储边 edgeList=new LinkedList<>(); visited=false; previousVertex=null; this.cost=cost; } //上面与顶点的标识相干 /**返回顶点的标识 * @return */ public T getLabel() { return label; } /** * 依据顶点的标识确定是否是同一个顶点 */ @Override public boolean equals(Object otherVertex) { boolean result; //如果otherVertex为空或者类不同，间接返回false if(otherVertex==null||getClass()!=otherVertex.getClass()){ return false; } Vertex other=(Vertex)otherVertex; //依据label确定是否是同一个顶点 result=label.equals(other.getLabel()); return result; } //上面与顶点的边相干 /** 返回边的迭代器 * @return */ public Iterator<Edge> getEdgeIterator(){ return edgeList.iterator(); } /**返回是否有以这个顶点为出发点的边数 * @return */ public int getEdgeCount(){ return edgeList.size(); } /**将这个顶点与endVertex连贯，边的权值为weight * @param endVertex * @param weight * @return 如果顶点曾经与endVertex连贯，那么将会更新权值，返回false<br> * 如果顶点没有与endVertex相连，则相互连贯，返回true */ public boolean connect(Vertex endVertex,double weight){ Iterator<Edge> iterator=getEdgeIterator(); Edge edge=null; Vertex vertex=null; while(iterator.hasNext()){ edge=iterator.next(); vertex=edge.getEndVertex(); if(vertex.equals(endVertex)){ //如果顶点曾经与endVertex连贯，那么将会更新权值，返回false edge.setWeight(weight); return false; } } //如果顶点没有与endVertex相连，则相互连贯，返回true edge=new Edge(this,endVertex, weight); edgeList.add(edge); return true; } /**将这个顶点与endVertex连贯的边删除 * @param endVertex * @return 如果顶点曾经与endVertex连贯，那么将会删除这条边，返回true<br> * 如果顶点没有与endVertex连贯，则啥都不做，返回false */ public boolean disconnect(Vertex endVertex){ Iterator<Edge> iterator=getEdgeIterator(); Edge edge=null; Vertex vertex=null; while(iterator.hasNext()){ edge=iterator.next(); vertex=edge.getEndVertex(); if(vertex.equals(endVertex)){ //如果顶点曾经与endVertex连贯，那么将会删除这条边，返回true //edgeList.remove(edge); iterator.remove(); return true; } } //如果顶点没有与endVertex连贯，则啥都不做，返回false return false; } /**返回是否有以这个顶点为出发点,以endVertex为完结点的边 * @return 如果有，返回那条边<br> * 如果没有，返回null */ public Edge hasNeighbourVertex(Vertex endVertex){ Iterator<Edge> iterator=getEdgeIterator(); Edge edge=null; Vertex vertex=null; while(iterator.hasNext()){ edge=iterator.next(); vertex=edge.getEndVertex(); if(vertex.equals(endVertex)){ //如果顶点曾经与endVertex连贯，那么将返回这个边 return edge; } } //没有则返回null return null; } //上面是与顶点是否被拜访相干 /**返回顶点是否被拜访 * @return */ public boolean isVisited() { return visited; } /** * 拜访这个顶点 */ public void visit(){ visited=true; } /** * 不拜访这个顶点，或者说是革除拜访状态 */ public void unVisit(){ visited=false; } /**取得以这个顶点为出发点，相邻的第一个没有被拜访的顶点 * @return 如果没有，返回null<br> * 如果有，返回对应的顶点 */ public Vertex getUnvisitedVertex(){ Iterator<Edge> iterator=getEdgeIterator(); Edge edge=null; Vertex vertex=null; while(iterator.hasNext()){ edge=iterator.next(); vertex=edge.getEndVertex(); if(vertex.isVisited()==false){ return vertex; } } //没有则返回null return null; } //上面与前驱节点相干 /**返回顶点的前驱节点 * @return */ public Vertex getPreviousVertex() { return previousVertex; } /**设置顶点的前驱节点 * @param previousVertex */ public void setPreviousVertex(Vertex previousVertex) { this.previousVertex = previousVertex; } //上面与顶点的权值相干 /**返回顶点的权值 * @return */ public double getCost() { return cost; } /** 设置顶点的权值 * @param cost */ public void setCost(double cost) { this.cost = cost; } }边- ...

前言公众号目前与「动静布局」相干系列包含：曾经完结的「动静布局-门路问题」和正在更新「动静布局-背包问题」。 这都是默认大家有肯定的「动静布局」意识的系列文章。 但事实上，可能有不少同学是刚接触算法，还处于只会应用「奢侈/暴力解法」来解决算法问题的阶段，对于「动静布局」并不理解。 因而我特意翻出来大略是我六七年写的文章（过后更多作为学习笔记），来帮忙大家对「动静布局」有个根本意识。 须要阐明的是，本文只停留在对「动静布局」的感性认识，并没有深刻到动静布局与图论的实质关系。 因而更多的面向是算法入门读者。 以下是注释内容。 演变过程始终搞不懂「动静布局」和「记忆化搜寻」之间的区别。 总感觉动静布局只是单纯的难在于对“状态”的形象定义和“状态转移方程”的推导，并无具体的法则可循。 但从算法逐渐优化角度而言，动静布局更多是从如下形式进行演变： ❝ 暴力递归 -> 记忆化搜寻 -> 动静布局。 ❞ 甚至能够说简直所有的「动静布局」都能够通过「暴力递归」转换而来，前提是该问题是一个“无后效性”问题。 从对“个例”的奢侈枚举做法，演变为对“汇合”的枚举做法。 无后效性所谓的“无后效性”是指：当某阶段的状态一旦确定，尔后的决策过程和最终后果将不受此前的各种状态所影响。 可简略了解为当编写好一个递归函数之后，当可变参数确定之后，后果是惟一确定的。 可能你还是对什么是“无后效性”问题感到难以了解。没关系，咱们再举一个更具象的例子，这是 LeetCode 62. Unique Paths ：给定一个 的矩阵，从左上角作为终点，达到右下角共有多少条门路（机器人只能往右或者往下进行挪动）。 这是一道经典的「动静布局」入门题目，也是一个经典的“无后效性”问题。 它的“无后效性”体现在：当给定了某个状态（一个具体的 的矩阵和某个终点，如 (1,2)），那么从这个点达到右下角的门路数量就是齐全确定的。 而与如何达到这个“状态”无关，与机器人是通过点 (0,2) 达到的 (1,2)，还是通过 (1,1) 达到的 (1,2) 无关。 这就是所谓的“无后效性”问题。 当咱们尝试应用「动静布局」解决问题的时候，首先要关注该问题是否为一个“无后效性”问题。 1：暴力递归常常咱们面对一个问题，即便咱们明确晓得了它是一个“无后效性”问题，它能够通过「动静布局」来解决。咱们还是感觉难以动手。 这时候我的倡议是，先写一个「暴力递归」的版本。 还是以刚刚说到的 LeetCode 62. Unique Paths 举例： class Solution {    public int uniquePaths(int m, int n) {        return recursive(m, n, 0, 0);    }    private int recursive(int m, int n, int i, int j) {        if (i == m - 1 || j == n - 1) return 1;        return recursive(m, n, i + 1, j) + recursive(m, n, i, j + 1);    }}当我还不晓得如何应用「动静布局」求解时，我会设计一个递归函数 。 函数传入矩阵信息和机器人以后所在的地位，返回在这个矩阵里，从机器人所在的地位登程，达到右下角有多少条门路。 有了这个递归函数之后，那问题其实就是求解 ：求解从 (0,0) 到右下角的门路数量。 接下来，实现这个函数： Base case: 因为题目明确了机器人只能往下或者往右两个方向走，所以能够定下来递归办法的 base case 是当曾经处于矩阵的最初一行或者最初一列，即只一条路能够走。其余状况：机器人既能够往右走也能够往下走，所以对于某一个地位来说，达到右下角的门路数量等于它左边地位达到右下角的门路数量 + 它下方地位达到右下角的门路数量。即 recursive(m,n,i+1,j) + recursive(m,n,i,j+1)，这两个地位都能够通过递归函数进行求解。其实到这里，咱们曾经求解了这个问题了。 ...

一、《数据结构与算法之美》学习数据结构与算法之美(1)—— 排序

递归代码： class Solution { public ListNode reverseList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; }}剖析： if (head == null || head.next == null) { return head; }head==null：当第一次输出为null的时候间接返回null，不进行递归操作。head.next == null：返回链表的最初一个节点ListNode newHead = reverseList(head.next);顺着链表节点一直的递归，每层的递归操作都会进行两个节点替换地位的操作；且当递归到最初一个节点的时候会返回最初一个节点（这最初一个节点是反转后链表的头结点）。head.next.next = head; //节点的下一个节点的后一节点指向本结点head.next = null; //本节点的下一节点指向null（此时本结点前一节点对该结点的指向未发生变化，以便后续本结点与其前一结点替换地位）替换前后节点的地位。（能够在纸上画一个任意长度的链表，用带箭头的线连贯示意指向关系，思考一下下整个链表节点替换地位的过程）return newHead; 若链表不为null，通过迭代并将链表的最初节点（反转后变为链表头节点）回溯if (head == null || ** head.next == null **) { return head;}作为办法调用后果返回。 ...

算法两种算法的比拟算法的独特1.写一个 求1加到100的程序 大多数人马上会写出以下的代码 写法1 // 容器 int sum = 0; for (int i = 1; i <= 100 ; i++) { // 1+2+3+4...加到100 sum = i + sum; } // 输入后果 5050 System.out.println(sum);问题是这样写是不是真的很好呢，或者来说最高效呢？ 这是高斯小时候就想出过一种求等差数列的算法 写法2 int sum = 0, n =100; // (1 + 100) * 50 = 5050 sum = (1+ n) * n/2; // 输入后果 5050 System.out.println(sum);写法1算法每次计算须要挨个挨个的加。 写法2呢也就一瞬间的事他提前晓得了后果。 算法的个性：输入 输出 有穷性 + 确定性 + 可行性 = 算法。 ...

一、概述最近在看一些面试题，发现很多面试过程中都会要求手写疾速排序，查阅一些博客发现他人写的并不是特地分明而且也很难记住，所以为了更好的把握这个算法，所以在这篇文章中，将本人的学习过程记录下来，你将学习到疾速排序算法和应用 Java 如何实现疾速排序。 疾速排序是一种基于分而治之的排序算法，其中：1、通过从数组中抉择一个核心元素将数组划分成两个子数组，在划分数组时，将比核心元素小的元素放在左子数组，将比核心元素大的元素放在右子数组。2、左子数组和右子数组也应用雷同的办法进行划分，这个过程始终继续到每个子数组都蕴含一个元素为止。3、最初，将元素组合在一起以造成排序的数组。 核心元素（pivot element)：有的中央翻译为：枢轴元素、基元，基准元素，我这里就叫做核心元素二、疾速排序算法的工作原理1、抉择核心元素抉择不同地位的核心元素，疾速排序就有不同的变体，比方能够抉择：第一个元素、最初一个元素以及左端、右端和核心地位上的三个元素的中值作为核心元素，在这里，咱们将抉择数组的最初一个元素作为核心元素。 2、重新排列数组当初重新排列数组，将比核心元素小的放在右边，比核心元素大的放在左边。 重新排列数组的办法如下：1、指针固定在核心元素上，将核心元素与从第一个索引开始的元素进行比拟。2、如果该元素大于核心元素，则为该元素设置第二指针。3、当初将核心元素与其余元素进行比拟，如果达到的元素小于核心元素，则将较小的元素和上次找到的较大元素替换地位。4、同样，反复该过程以将下一个更大的元素设置为第二指针，并且将其和另一个较小的元素替换地位。5、该过程始终进行到达到倒数第二个元素为止。6、最初将核心元素与第二个指针指向的元素替换地位。 3、划分子数组再次别离为左子局部和右子局部抉择了核心元素，并且反复步骤2，子数组被宰割，直到每个子数组只有一个元素，至此，该数组曾经通过疾速排序算法升序排好序了。 4、疾速排序可视化插图阐明能够借助以下插图理解疾速排序算法的工作原理。 三、疾速排序算法伪代码1、伪代码阐明quickSort(array, leftmostIndex, rightmostIndex) if (leftmostIndex < rightmostIndex) pivotIndex <- partition(array,leftmostIndex, rightmostIndex) quickSort(array, leftmostIndex, pivotIndex - 1) quickSort(array, pivotIndex, rightmostIndex)partition(array, leftmostIndex, rightmostIndex) set rightmostIndex as pivotIndex storeIndex <- leftmostIndex - 1 for i <- leftmostIndex + 1 to rightmostIndex if element[i] < pivotElement swap element[i] and element[storeIndex] storeIndex++ swap pivotElement and element[storeIndex+1]return storeIndex + 1四、Java 实现疾速排序Java 实现疾速排序的代码如下： public class QuickSort { public static int partition(int[] array, int low, int high) { // 取最初一个元素作为核心元素 int pivot = array[high]; // 定义指向比核心元素大的指针，首先指向第一个元素 int pointer = low; // 遍历数组中的所有元素，将比核心元素大的放在左边，比核心元素小的放在右边 for (int i = low; i < high; i++) { if (array[i] <= pivot) { // 将比核心元素小的元素和指针指向的元素替换地位 // 如果第一个元素比核心元素小，这里就是本人和本人替换地位，指针和索引都向下一位挪动 // 如果元素比核心元素大，索引向下挪动，指针指向这个较大的元素，直到找到比核心元素小的元素，并替换地位，指针向下挪动 int temp = array[i]; array[i] = array[pointer]; array[pointer] = temp; pointer++; } System.out.println(Arrays.toString(array)); } // 将核心元素和指针指向的元素替换地位 int temp = array[pointer ]; array[pointer] = array[high]; array[high] = temp; return pointer; } public static void quickSort(int[] array, int low, int high) { if (low < high) { // 获取划分子数组的地位 int position = partition(array, low, high); // 左子数组递归调用 quickSort(array, low, position -1); // 右子数组递归调用 quickSort(array, position + 1, high); } } public static void main(String[] args) { int[] array = {6,72,113,11,23}; quickSort(array, 0, array.length -1); System.out.println("排序后的后果"); System.out.println(Arrays.toString(array)); }}排序过程的后果如下： ...

前言数据结构与算法是程序员内功体现的重要规范之一，且数据结构也利用在各个方面，业界更有程序=数据结构+算法这个等式存在。各个中间件开发者，架构师他们都在致力的优化中间件、我的项目构造以及算法进步运行效率和升高内存占用，在这里数据结构起到相当重要的作用。此外数据结构也蕴含一些面向对象的思维，故学好把握数据结构对逻辑思维解决形象能力有很大晋升。 为什么学习数据结构与算法？如果你还是学生，那么这门课程是必修的，考研根本也是必考科目。工作在内卷重大的大厂中找工作数据结构与算法也是面试、口试必备的十分重要的考察点。如果工作了数据结构和算法也是内功晋升一个十分重要的体现，对于程序员来说，想要失去称心的后果，数据结构与算法是必备功力！ 数据结构 概念数据结构是计算机存储、组织数据的形式。数据结构是指相互之间存在一种或多种特定关系的数据元素的汇合。通常状况下，精心抉择的数据结构能够带来更高的运行或者存储效率。 简言之，数据结构是一系列的存储构造依照肯定执行规定、配合肯定执行算法所造成的高效的存储构造。在咱们所熟知的关系数据库、非关系数据库、搜索引擎存储、音讯队列等都是比拟牛的大型数据结构良好的使用。当然这些利用中间件不单单要思考单纯的构造问题。还思考理论os、网络等其余因素。 而对于数据结构与算法这个专栏。咱们程序员更改把握的首先是在内存中运行的形象的数据结构。是一个绝对比拟繁多的数据结构类型，比方线性构造、树、图等等. 相干术语在数据结构与算法中，数据、数据对象、数据元素、数据项很多人搞不清其中的关系。通过画一张图来捋一捋，而后上面举个例子给大家分享一下。 用户信息表users idnamesex001bigsaiman002smallsaiman003菜虚鲲womanusers的pojo对象 class users{ //略 int id; String name; String sex;}//list和woman是数据List<users>list;//数据对象listList<users>woman;//数据对象womanlist.add(new users(001,"bigsai","man"));//增加数据元素 一个users由（001，bigsai，man）三个数据项组成 list.add(new users(002,"smallsai","man"));//数据元素list.add(new users(003,"菜虚鲲","woman"));//数据元素woman.add(list.get(2));//003,"菜虚鲲","woman"三个数据项形成的一个数据元素数据：对客观事物的符号示意，指所有能输出到计算机中并被计算机程序解决的符号的汇合总称。上述表中的三条用户信息的记录就是数据(也可能多表多汇合这里只有一个)。这些数据个别都是用户输出或者是自定义结构实现。当然，还有一些图像、声音也是数据。 数据元素：数据元素是数据的根本单位。一个数据元素由若干数据项形成！可认为是一个pojo对象、或者是数据库的一条记录。比方菜虚鲲那条记录就是一个数据元素。 数据项： 而形成用户字段/属性的有id、name、sex等，这些就是数据项.数据项是形成数据元素的最小不可分割字段。能够看作一个pojo对象或者一张表(people)的一个属性/字段的值。 数据对象：是雷同性质数据元素的汇合。是数据的一个子集。比方下面的users表、list汇合、woman汇合都是数据对象。独自一张表，一个汇合都能够是一个数据对象。 总的捋一捋，数据范畴最广，所有数据即数据，而数据对象仅仅是有雷同性质的一个汇合，这个汇合是数据的子集，但并不是数据的根本单位，而数据元素才是数据的根本单位。举个例子表cat和表dog都是数据，而后表cat是个数据对象(因为都形容cat这种对象)，然而数据的根本单位并不是猫和狗，而是他们的具体的每一条，比方小猫咪1号，大猫咪二号，哈士奇1号，藏獒2号这些每一条才是数据的根本单位。 还有数据类型，抽象数据类型也在上面讲一讲。 数据类型 原子类型：其值不可再分的类型。比方int，char，double，float等。 构造类型：其值能够再分为若干成分的数据类型。比方构造体结构的各种构造等。 抽象数据类型(ADT)：抽象数据类型（ADT）是一个实现包含贮存数据元素的存储构造以及实现基本操作的算法。使得只钻研和应用它的构造而不必思考它的实现细节成为可能。比方咱们应用List、Map、Set等等只须要理解它的api和性质性能即可。而具体的实现可能是不同的计划，比方List的实现有数组和链表不同抉择。 三要素逻辑构造：数据元素之间的逻辑关系。逻辑构造分为线性构造和非线性构造。线性构造就是程序表、链表之类。而非线性就是汇合、树、图这些构造。 存储构造：数据结构在计算机中的示意(又称映像，也称物理构造)，存储构造次要分为顺序存储、链式存储、索引存储和散列(哈希)存储，这几种存储通过上面这张图简略理解一下(仅仅为了解不思考更多)： 数据的运算：施加在数据上的运算包含运算的定义和实现,运算的定义基于逻辑构造，运算的实现基于存储构造。 在这里容易混同的是逻辑构造与存储构造的概念。对于逻辑构造，不难看得出逻辑二字，逻辑关系也就是两者存在数据上的关系而不思考物理地址的关系，比方线性构造和非线性构造，它形容的是一组数据中分割的形式和模式，他针对的是数据。看中的是数据结构的性能，比方线性表就是前后有序的，我须要一个有序的汇合就能够应用线性表。 而存储构造就是跟物理地址挂钩的。因为同样逻辑构造采纳不同存储构造实现实用场景和性能可能不同。比方同样是线性表,可能有多种存储构造的实现形式。比方程序表和链表(Arraylist,Linkedlist)它们的存储构造就不同，一个是顺序存储(数组)实现，一个是链式存储(链表)实现。它关注的是计算机运行物理地址的关系。但通常同一类存储构造实现的一些数据结构有一些相似的共同点和毛病(线性易查难插、链式易插难查等等)。 算法剖析下面讲了数据结构相干概念，上面对算法剖析的一些概念进行形容。 算法的五个重要特色：有穷性、确定性、可行性、输出、输入。这些从字面意思即可了解，其中有穷性强调算法要有完结的时候不能有限循环；而确定性是每条指令有它意义，雷同的输出失去雷同的输入；可行性是指算法每个步骤通过若干次执行能够实现；输出是0个或多个输出(可0);输入是1个或多个输入(肯定要有输入)。 而一个好的算法，通常更要着重思考的是效率和空间资源占用(工夫复杂度和空间复杂度)，通常复杂度更多形容的是一个量级水平而很少用具体数字形容。 空间复杂度概念：是对一个算法在运行过程中长期占用存储空间大小的量度，记做S(n)=O(f(n)) 空间复杂度其实在算法的掂量占比是比拟低的(咱们常常应用就义空间换工夫的数据结构和算法)，然而不能漠视空间复杂度中重要性。无论在刷题还是理论我的项目生产内存都是一个极大额指标。对于Java而言更是如此。自身内存就大，如果采纳的存储逻辑不太好会占用更多的系统资源，对服务造成压力。 而算法很多状况都是就义空间换取工夫(效率)。就比方咱们熟知的字符串匹配String.contains()办法，咱们都晓得他是暴力破解，工夫复杂度为O(n^2),不须要借助额定内存。而KMP算法在效率和速度上都原生暴力办法，然而KMP要借助其余数组(next[])进行标记贮存运算。就用到了空间开销。再比方归并排序也会借助新数组在递归分冶的适宜进行逐级计算，提高效率，但减少点影响不大的内存开销。 当然，算法的空间花销最大不能超过jvm设置的最大值，个别为2G.(2147483645)如果开二维数组多种多维数据不要开的太大，可能会导致heap OutOfMemoryError。 工夫复杂度概念：计算机科学中，算法的工夫复杂度是一个函数，它定性描述了该算法的运行工夫。这是一个对于代表算法输出值的字符串的长度的函数。工夫复杂度罕用大O符号表述，不包含这个函数的低阶项和首项系数。应用这种形式时，工夫复杂度可被称为是渐近的，它考查当输出值大小趋近无穷时的状况。 工夫复杂度的排序：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) <O(n!) < O(n^n) 常见工夫复杂度：对于工夫复杂度，很多人的概念是比拟含糊的。上面举例子阐明一些工夫复杂度。 O(1): 常数函数 ...

好久没刷 LeetCode 了，刚关上页面，啪，每日一题就显示进去了，很快啊。明天的每日一题是字符串的easy题目，可我还是花了有一二十分钟，许久不刷题手都生了。 题目 回升降落字符串给你一个字符串 s ，请你依据上面的算法从新结构字符串： 从 s 中选出 最小 的字符，将它 接在 后果字符串的前面。从 s残余字符中选出 最小 的字符，且该字符比上一个增加的字符大，将它 接在 后果字符串前面。反复步骤 2 ，直到你没法从 s 中抉择字符。从 s 中选出 最大 的字符，将它 接在 后果字符串的前面。从 s 残余字符中选出 最大 的字符，且该字符比上一个增加的字符小，将它 接在 后果字符串前面。反复步骤 5 ，直到你没法从 s 中抉择字符。反复步骤 1 到 6 ，直到 s 中所有字符都曾经被选过。在任何一步中，如果最小或者最大字符不止一个 ，你能够抉择其中任意一个，并将其增加到后果字符串。 请你返回将 s 中字符从新排序后的 后果字符串 。 示例一输出：s = "aaaabbbbcccc"输入："abccbaabccba"解释：第一轮的步骤 1，2，3 后，后果字符串为 result = "abc" 第一轮的步骤 4，5，6 后，后果字符串为 result = "abccba" 第一轮完结，当初 s = "aabbcc" ，咱们再次回到步骤 1 第二轮的步骤 1，2，3 后，后果字符串为 result = "abccbaabc" 第二轮的步骤 4，5，6 后，后果字符串为 result = "abccbaabccba"示例二输出：s = "rat"输入："art"解释：单词 "rat" 在上述算法重排序当前变成 "art"思路拿到题目后，首先到我脑海里的有一个 Map ，因为咱们须要对输出中不同的字母进行标记（或者说计数）用于判断是否被拼接了；再者是一个先后顺序关系，咱们能够从它提到的步骤中发现，选取最大的进行拼接，是在选取最小的进行拼接之后的，那么这个先后顺序咱们就能够用于确定咱们编写过程中的代码先后顺序。 ...

`「胜利案例」教你如何判断下期大小陈北企鹅:753~7227：蕴含与数字运算无关的类。 罕用静态方法 abs()：取绝对值，Math.abs(-100)=100 floor()：向下取值,Math.floor(10.7)=10 round()：四舍五入. Collections类:addAll(Collection<? super T> c, T... elements) 将所有指定的元素增加到指定的汇合。 shuffle(List<?> list) 应用默认的随机源随机排列指定的列表。(打乱list中的数据) sort(List<T> list) 进行排序 一个人，身边有多少人，就有多大的世界，有什么样的人，就有什么样的世界。这些人素养的高下，决定了你的鄙俗与低俗、辽远与浅狭、明媚与卑琐。一句话，别人的品质，就是你的世界的品质。 在天然的山水里，无论走多远，最初还要回到这群人当中。也就是说，你最终要回到本人的世界里来。远足，是心灵的沐洗，是换一种形式让精力解围，是以天然的视觉，看清人的世界。 身边的世界，总有你不喜爱的人，总有你嫌弃的事，这些必然要来到生命中，它们来到，只是为揭示生存的假相，通知你生存是怎么一回事。 一个人的弱小，就是能与不堪的人和事周旋，最终，战败柔弱卑怯的本人。你救不起道德沦丧，但在一大片道德沦丧里，你能够抉择本人巍然挺立。`

2-3树 在理解红黑树之前，咱们先来意识2-3树，在算法里也是先从2-3树切入到红黑树的。并且理解2-3树对于了解B类树也会有帮忙，因为2-3树能够说就是根底的B类树。 2-3树的个性： 满足二分搜寻树的根本性质节点能够寄存一个元素或者两个元素，或者说数据项每个节点有2个或者3个子节点，这也是2-3树的名称由来2-3树是一棵相对均衡的树，对于任意节点的左右子树的高度肯定是相等的2-3树为了维持相对均衡，须要满足以下条件： 2节点有且只能有两个子节点，并只能蕴含一个数据项3节点有且只能有三个子节点，并只能蕴含两个数据项，大小关系从左至右顺次递增增加数据项时不能将该数据项增加到一个空节点上，因为新的节点只能通过决裂或者交融产生当2-3树只有2节点的时候，其只能是一棵满二叉树2-3树的两类节点： 能够看到，2节点有两个子节点，5和15，且本身只蕴含一个数据项，即10。3节点则有三个子节点，本身只能蕴含两个数据项，从左至右顺次递增：5 < 6 < 7 < 8 < 9下图是一颗残缺的2-3树： 从上图中能够看到2-3树是满足二分搜寻树的根本性质的，只有两个节点的状况，如 42 这个节点，右子节点小于父节点，左子节点大于父节点。而有三个节点时，右子节点依然小于父节点，两头的子节点大于父节点的左数据项，小于父节点的右数据项（如图中18大于17，小于33），左子节点则大于父节点。 2-3树的相对平衡性 之前咱们提到了2-3树插入节点时不能将该节点插入到一个空节点上，新的节点只能通过决裂或者交融产生。咱们晓得对二分搜寻树顺次增加有序的数据时，如顺次增加 1、2、3、4、5，会产生间断的节点，使得二分搜寻树进化成链表。 为了防止进化成链表，具备均衡个性的树状构造，会采取一些伎俩来维持树的均衡，例如AVL是通过旋转节点，而2-3树则是通过决裂和交融。当咱们顺次增加 1、2、3、4、5 到2-3树时，其流程如下： 增加元素1，创立一个2节点类型的根节点增加元素2，此时元素1和2存在同一个节点中，成为一个3节点。为什么增加元素2时，不能生成一个新的节点作为元素1所在节点的右子节点呢？因为“增加数据项时不能将该数据项增加到一个空节点上，新的节点只能通过决裂或者交融产生”增加元素3，元素1、2、3，临时存在同一个节点中，造成一个4节点决裂，2-3树中最多只有3节点，不能存在4节点，所以临时造成的4节点要进行决裂，将两头的元素作为根节点，左右两个元素各为其左右子节点。这时可见造成了一棵满二叉树增加元素4，依据元素的大小关系，将会寄存到元素3所在的节点。因为新增加的元素不能增加到一个空节点上，所以元素4将依据搜寻树的性质找到最初一个节点与其交融。即元素3和4将交融为一个三节点。并且依据大小关系元素4要位于元素3的右侧增加元素5，同插入元素4，元素5一路查找到元素3、4所在的三节点，与其交融，临时造成一个4节点决裂，元素3、4、5所在的4节点同下面元素1、2、3造成的4节点一样，进行决裂操作。依据大小关系，4元素将会作为根节点，元素3、5则各为其左右子节点交融，后面的决裂操作曾经导致该2-3树不满足其第四条性质“当2-3树只有2节点的时候，其只能是一棵满二叉树”，所以该2-3树将要向上交融以满足2-3树的性质。咱们只须要将元素4所在节点与其父节点即元素2所在的节点进行交融即可。这时，元素2、4就造成了一个3节点如果咱们持续往2-3树中增加元素6和7，那么最终造成的2-3树如下图所示： 如果在这个案例中咱们应用的是二分搜寻树，那么该二分搜寻树将会进化为一个链表，而2-3树则通过决裂、交融的形式成为了一颗满二叉树。 红黑树与2-3树的等价性 理解了2-3树后，咱们来看下红黑树与2-3树的等价性，严格来说是左倾红黑树才是与2-3树是等价的。与2-3树一样，红黑树具备二分搜寻树的性质，并且也是自均衡的，但不是相对均衡，甚至平衡性比AVL树还要差一些。 之前提到了2-3树是相对均衡的，对于任意节点的左右子树的高度肯定是相等的。而AVL树则是任意节点的左右子树高度相差不超过 1 即可，属于高度均衡的二分搜寻树。 红黑树则是从根节点到叶子节点的最长门路不超过最短门路的2倍，其高度仅仅只会比AVL树高度大一倍，所以在性能上，降落得并不多。因为红黑树也是自均衡的树，也会采取一些机制来维持树的均衡。 红黑树的定义： 每个节点或者是红色的，或者是彩色的根节点是彩色的每一个叶子节点（最初的空节点）是彩色的如果一个节点是红色的，那么它的左右子节点都是彩色的从任意一个节点到叶子节点，通过的彩色节点是一样的这里的第三点要求“每一个叶子节点（最初的空节点）是彩色的”，略微有些奇怪，它次要是为了简化红黑树的代码实现而设置的。咱们也能够了解为，只有是空的节点，它就是彩色的。 在理解了2-3树之后，咱们晓得2-3树是通过决裂和交融来产生新的节点并维持均衡的。2-3树有两类节点，2节点和3节点。除此之外，还会有一种长期的4节点。接下来咱们看看2-3树向红黑树转换的过程，下图展现了2-3树的这三种节点对应于红黑树的节点： 2节点：对应于红黑树的彩色节点3节点：对应于红黑树中彩色的父节点和红色的左子节点长期的4节点：对应于红色的父节点和彩色的左右子节点。这里须要说一下，为什么是红色的父节点而不是彩色的呢？次要是因为2-3树的3节点须要将决裂后的父节点进行向上交融，红色的合乎咱们向红黑树中插入任何一个节点默认都是红色的实现形式。如果该父节点是红黑树的根节点的话，那它必定须要变色，这一点就不属于2-3树向红黑树的变换规定了，而属于红黑树的性质。依据这个对应关系，咱们将这样一颗2-3树： 转换成红黑树，就是这样子的，能够看到其中的红色节点都对应着2-3树的3节点： 如果这样看着不太好对应的话，咱们也能够将其绘制成这个样子，就更容易了解红黑树与2-3树是等价的了： 从2-3树过渡到红黑树后，接下来，咱们就着手实现一个红黑树。首先，编写红黑树的友链交易根底构造代码，如节点定义等。具体代码如下所示： package tree; /** * _红黑树_ * * @author 01 * @date 2021-01-22 **/ public class RBTree<K extends Comparable<K>, V> { /** * _因为只有红色和彩色，这里用两个常量来示意_ */ private static final boolean RED = true; private static final boolean BLACK = false; ...

一、罕用数据结构1、数组、字符串（1）字符串转化因为须要针对字符串当中的每一个字符进行剖析和解决，有时候字符串转换成字符数组 （2）数组的长处构建非常简单能在 O(1) 的工夫里依据数组的下标（index）查问某个元素（3）数组的毛病构建时必须调配一段间断的空间查问某个元素是否存在时，须要遍历整个数组，消耗 O(n) 的工夫（其中，n 是元素的个数）删除和增加某个元素时，同样须要消耗 O(n) 的工夫

读完本文，你能够去力扣拿下如下题目： 92.反转链表II ----------- 反转单链表的迭代实现不是一个艰难的事件，然而递归实现就有点难度了，如果再加一点难度，让你仅仅反转单链表中的一部分，你是否能够递归实现呢？ 本文就来由浅入深，step by step 地解决这个问题。如果你还不会递归地反转单链表也没关系，本文会从递归反转整个单链表开始拓展，只有你明确单链表的构造，置信你可能有所播种。 // 单链表节点的构造public class ListNode { int val; ListNode next; ListNode(int x) { val = x; }}什么叫反转单链表的一部分呢，就是给你一个索引区间，让你把单链表中这部分元素反转，其余局部不变：e 留神这里的索引是从 1 开始的。迭代的思路大略是：先用一个 for 循环找到第 m 个地位，而后再用一个 for 循环将 m 和 n 之间的元素反转。然而咱们的递归解法不必一个 for 循环，纯递归实现反转。 迭代实现思路看起来尽管简略，然而细节问题很多的，反而不容易写对。相同，递归实现就很简洁柔美，上面就由浅入深，先从反转整个单链表说起。 一、递归反转整个链表这个算法可能很多读者都据说过，这里具体介绍一下，先间接看实现代码： ListNode reverse(ListNode head) { if (head.next == null) return head; ListNode last = reverse(head.next); head.next.next = head; head.next = null; return last;}看起来是不是感觉不知所云，齐全不能了解这样为什么可能反转链表？这就对了，这个算法经常拿来显示递归的奇妙和柔美，咱们上面来具体解释一下这段代码。 对于递归算法，最重要的就是明确递归函数的定义。具体来说，咱们的 reverse 函数定义是这样的： ...

最近刚好算法试验做了这个, 水一篇博客吧 算法思路根本剖析:假如字符串A的长度为m, 字符串B的长度为n, 应用一个数组fm示意对应后果, 其中f[i][j]示意 A.substr(0, i) 和 B.substr(0, j)这两个子字符串的LCS. 思考f[i][j], 他总是能够从上方⬆ (即不应用A的第i个字符)和 左方⬅(不应用B的第j个字符)两个方向转移过去, 因而有f[i][j] = max(f[i – 1][j], f[i][j – 1]); 此外, 如果A[i] == B[j], 那么它能够从左上方转移过去, 此时有f[i][j] = max(f[i][j], f[i – 1][j – 1] + 1); 空间优化:上述剖析曾经能够残缺地解决LCS问题, 想求出LCS只须要在转移的时候进行记录就行, 不过空间复杂度是O(mn)的, 而后通过咱们的剖析过程能够看到, 转移的时候只波及了以后行和上一行(这里假如行size更小, 如果列size更小的话同理). 因而咱们能够用两个长度为m + 1的数组, 通过不停更新来实现这个算法. 空间进一步优化:通过上一步优化之后所用空间为两个长度为 m + 1的数组, 以及常数个额定变量. 不过还能够更进一步优化, 因为从头至尾咱们转移到[i][j]的时候只和三个地位的值无关: 正上方[i – 1][j], 左方[i][j – 1]和左上方[i – 1][j – 1]. 因而咱们能够思考用一个数组来示意, 在只应用一个数组的状况下, 更新前f[j]就是上一轮更新后的上方f[i – 1][j], 而f[j – 1]也就是左方f[i][j – 1], 也就是说咱们在更新f[j]的时候, 须要的三个值中的两个都在这个数组中了, 那么咱们只须要缓存f[i – 1][j – 1]就行了. 这种状况下, 空间为一个长度为m + 1的数组, 加上两个额定变量. 空间复杂度较低. ...

以下5个习题是用dfs解决数组or链表和二叉树互相转换的问题，进行对立一起解决能够无效地加强学习，坚固记忆。 105. 从前序与中序遍历序列结构二叉树题目形容依据一棵树的前序遍历与中序遍历结构二叉树。 留神:你能够假如树中没有反复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树： 3 / \ 9 20 / \ 15 7思路首先如果想解决此题，首先晓得前序和中序遍历的特色。前序遍历的特点是中左右，也就是说数组第一个元素也就是整个树根节点的值，而中序遍历的特点是左中右，也就是说左子树的节点都在根节点的左侧，右子树在根节点的右侧。 依据下面的特色，咱们就能够依据前序+中序的遍历序列进行构建二叉树。 在前序遍历序列中找到树的根节点在中序序列中找到这个根节点而后递归构建子树既然咱们应用递归构建子树，就须要明确递归的几个条件 递归的完结条件递归的程序构造首先是递归的完结条件，咱们是依据树遍历后果来构建树，所以能够依据遍历的数组确定递归条件 if (instart == inEnd || preStart == preEnd) return;其次是递归的程序构造，因为咱们能够确定根节点的地位，而后能力找出其对应的左子树和右子树，所以这种状况就是先确定节点而后进行递归，相似于先序遍历。 ensure the root node;recursion left;recursion right;另外咱们能够应用map将中序序列的遍历后果进行缓存，防止反复遍历，应用空间换工夫。 代码实现class Solution { private Map<Integer, Integer> map = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { int index = 0; for (int cur : inorder) { map.put(cur, index++); } return build(preorder, inorder, 0, preorder.length, 0, inorder.length); } TreeNode build(int[] pre, int[] in, int pStart, int pEnd, int inStart, int inEnd) { if (pStart == pEnd) return null; int rootVal = pre[pStart]; int rootIndex = map.get(rootVal); TreeNode root = new TreeNode(rootVal); int leftNum = rootIndex - inStart; root.left = build(pre, in, pStart + 1, pStart + 1 + leftNum, inStart, rootIndex); root.right = build(pre, in, pStart + 1 + leftNum, pEnd, rootIndex + 1, inEnd); return root; }}106.从中序与后序遍历序列结构二叉树题目形容依据一棵树的中序遍历与后序遍历结构二叉树。留神:你能够假如树中没有反复的元素。例如，给出中序遍历 inorder = [9,3,15,20,7]后序遍历 postorder = [9,15,7,20,3]返回如下的二叉树： 3 / \ 9 20 / \ 15 7思路这道题和下面的105题根本相似，没有太多区别。后序遍历的根节点是数组的最初一个元素。数组的边界是左开右闭。 ...

题目粗心：给定一个序列，需要求出该序列的最大子序列和及其第一个数字和最初一个数字，如果所有的数字都是正数，输入0和第一个数字及其最初一个数字。 算法思路：算法思路1（暴力递归）：如上图所示，实际上该问题，等价与初始和为0，获得每一个数字作为终点的所有子序列和的最大值中的最大值，如图中所标注的20.间接应用深度优先搜寻解决。代码如下： /* * index为以后所抉择的数字下标 * sum为[i,index]的子序列和，其中i为终点 */int DFS(const int *nums,int N,int index,int sum){ // [i,index+1]的最大子序列和 int current = -0x7fffffff; if(index+1<N){ current = DFS(nums,N,index+1,sum+nums[index+1]); } return max(sum,current);}int process(const int *nums,int N,int index){ int max_sum = nums[index]; for (int i = index; i < N; ++i) { int next = DFS(nums,N,i,nums[i]); max_sum = max(max_sum,next); } return max_sum;}因为该办法会导致一个测试点超时，而且不太好求解左右端点，这里不再给出残缺代码，然而其搜寻过程值得借鉴，也是接下来优化的根据。 算法思路2(双重循环)：咱们枚举每一个左端点i，应用temp记录以后端点i的每一个子序列和，并应用max_sum记录所有子序列和中的最大值，L和R为其左右下标，而后应用j遍历每一个右端点，起始为i，每一次temp累加nums[j]，判断temp是否大于max_sum，如果是，就更新max_sum，L,R。最初依据max_sum进行输入即可。代码如下： int max_sum = nums[0];int L=0,R=0;for(int i=0;i<N;++i){ int temp = 0;// 暂存每一个终点的局部子序列和 for(int j=i;j<N;++j){ temp += nums[j]; if(temp>max_sum){ max_sum = temp; L = i; R = j; } }}算法思路3(动静布局)：仔细观察下面的图就晓得，在最右边的抉择，肯定是蕴含了左边的抉择的，也即是说，如果右边的抉择在某个时刻选了一个正数，而下一个抉择是一个负数，咱们齐全能够将后面抉择的最大子序列和舍弃掉，为什么呢？因为下一个抉择的负数，恰好是左边第一个抉择的数字，其前面的后果肯定比右边的后果大，比方后面2条分支，最开始抉择了-2和11，右边的那支在抉择-2之后的下一次抉择就是11，正好是左边以后的抉择，那么右边的抉择的数字的最大子序列和=-2+左边抉择的数字的最大子序列和，天然就没有必要还要保留之前抉择的小于0的子序列和。咱们能够应用一个数组dp[n]保留从终点(不确定，因为会呈现舍弃后会从新的终点开始)到以后数字n的最大子序列和，如果后面的子序列和小于0，就舍弃dp[n-1],让dp[n]=nums[n]即可，如果dp[n-1]大于等于0，就保留dp[n]=dp[n-1]+nums[n]（因为它可能会让前面的子序列和更大），这样就失去了前一个状态和后一个状态的关系，初始状态为dp[0]=nums[0]。代码如下： ...

7-4 Professional Ability Test (30分)Professional Ability Test (PAT) consists of several series of subject tests. Each test is divided into several levels. Level A is a prerequisite (前置要求) of Level B if one must pass Level A with a score no less than S in order to be qualified to take Level B. At the mean time, one who passes Level A with a score no less than S will receive a voucher（代金券）of D yuans (Chinese dollar) for taking Level B. ...

7-2 How Many Ways to Buy a Piece of Land (25分)The land is for sale in CyberCity, and is divided into several pieces. Here it is assumed that each piece of land has exactly two neighboring pieces, except the first and the last that have only one. One can buy several contiguous（间断的） pieces at a time. Now given the list of prices of the land pieces, your job is to tell a customer in how many different ways that he/she can buy with a certain amount of money. ...

7-1 Panda and PP Milk (20分) PP milk （盆盆奶）is Pandas' favorite. They would line up to enjoy it as show in the picture. On the other hand, they could drink in peace only if they believe that the amount of PP milk is fairly distributed, that is, fatter panda can have more milk, and the ones with equal weight may have the same amount. Since they are lined up, each panda can only compare with its neighbor(s), and if it thinks this is unfair, the panda would fight with its neighbor. ...

7-3 Left-View of Binary Tree (25分)The left-view of a binary tree is a list of nodes obtained by looking at the tree from left hand side and from top down. For example, given a tree shown by the figure, its left-view is { 1, 2, 3, 4, 5 } Given the inorder and preorder traversal sequences of a binary tree, you are supposed to output its left-view. ...

7-4 Replacement Selection (30分)When the input is much too large to fit into memory, we have to do external sorting instead of internal sorting. One of the key steps in external sorting is to generate sets of sorted records (also called runs) with limited internal memory. The simplest method is to read as many records as possible into the memory, and sort them internally, then write the resulting run back to some tape. The size of each run is the same as the capacity of the internal memory. ...

7-2 The Judger (25分)A game of numbers has the following rules: at the beginning, two distinct positive integers are given by the judge. Then each player in turn must give a number to the judge. The number must be the difference of two numbers that are previously given, and must not be duplicated to any of the existed numbers. The game will run for several rounds. The one who gives a duplicate number or even a wrong number will be kicked out. ...

7-3 Safari Park (25分)A safari park（家养动物园）has K species of animals, and is divided into N regions. The managers hope to spread the animals to all the regions, but not the same animals in the two neighboring regions. Of course, they also realize that this is an NP complete problem, you are not expected to solve it. Instead, they have designed several distribution plans. Your job is to write a program to help them tell if a plan is feasible. ...

7-1 Prime Day (20分) The above picture is from Sina Weibo, showing May 23rd, 2019 as a very cool "Prime Day". That is, not only that the corresponding number of the date 20190523 is a prime, but all its sub-strings ended at the last digit 3 are prime numbers. Now your job is to tell if a given date is a Prime Day. Input Specification:Each input file contains one test case. For each case, a date between January 1st, 0001 and December 31st, 9999 is given, in the format yyyymmdd. ...

7-4 Dijkstra Sequence (30分)Dijkstra's algorithm is one of the very famous greedy algorithms. It is used for solving the single source shortest path problem which gives the shortest paths from one particular source vertex to all the other vertices of the given graph. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later. In this algorithm, a set contains vertices included in shortest path tree is maintained. During each step, we find one vertex which is not yet included and has a minimum distance from the source, and collect it into the set. Hence step by step an ordered sequence of vertices, let's call it Dijkstra sequence, is generated by Dijkstra's algorithm. ...

7-3 Postfix Expression (25分)Given a syntax tree (binary), you are supposed to output the corresponding postfix expression, with parentheses reflecting the precedences of the operators. Input Specification:Each input file contains one test case. For each case, the first line gives a positive integer N (≤ 20) which is the total number of nodes in the syntax tree. Then N lines follow, each gives the information of a node (the i-th line corresponds to the i-th node) in the format: ...

7-2 Merging Linked Lists (25分)Given two singly linked lists L1=$a_1$→$a_2$→⋯→$a_{n-1}$→$a_n$ and L2=$b_1$→$b_2$→⋯→$b_{m-1}$→$b_m$. If n≥2m, you are supposed to reverse and merge the shorter one into the longer one to obtain a list like a1→a2→bm→a3→a4→bm−1⋯. For example, given one list being 6→7 and the other one 1→2→3→4→5, you must output 1→2→7→3→4→6→5. Input Specification:Each input file contains one test case. For each case, the first line contains the two addresses of the first nodes of L1 and L2, plus a positive $N (≤10^5)$ which is the total number of nodes given. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1. ...

7-1 Forever (20分)"Forever number" is a positive integer A with K digits, satisfying the following constrains: the sum of all the digits of A is m;the sum of all the digits of A+1 is n; andthe greatest common divisor of m and n is a prime number which is greater than 2.Now you are supposed to find these forever numbers. Input Specification:Each input file contains one test case. For each test case, the first line contains a positive integer N (≤5). Then N lines follow, each gives a pair of K (3<K<10) and m (1<m<90), of which the meanings are given in the problem description. ...

7-4 Cartesian Tree (30分)A Cartesian tree is a binary tree constructed from a sequence of distinct numbers. The tree is heap-ordered, and an inorder traversal returns the original sequence. For example, given the sequence { 8, 15, 3, 4, 1, 5, 12, 10, 18, 6 }, the min-heap Cartesian tree is shown by the figure. Your job is to output the level-order traversal sequence of the min-heap Cartesian tree. ...

7-3 Summit (25分)A summit (峰会) is a meeting of heads of state or government. Arranging the rest areas for the summit is not a simple job. The ideal arrangement of one area is to invite those heads so that everyone is a direct friend of everyone. Now given a set of tentative arrangements, your job is to tell the organizers whether or not each area is all set. ...

7-2 Block Reversing (25分)Given a singly linked list L. Let us consider every K nodes as a block (if there are less than K nodes at the end of the list, the rest of the nodes are still considered as a block). Your job is to reverse all the blocks in L. For example, given L as 1→2→3→4→5→6→7→8 and K as 3, your output must be 7→8→4→5→6→1→2→3. ...

7-1 Good in C (20分)When your interviewer asks you to write "Hello World" using C, can you do as the following figure shows? Input Specification:Each input file contains one test case. For each case, the first part gives the 26 capital English letters A-Z, each in a 7×5 matrix of C's and .'s. Then a sentence is given in a line, ended by a return. The sentence is formed by several words (no more than 10 continuous capital English letters each), and the words are separated by any characters other than capital English letters.It is guaranteed that there is at least one word given. ...

7-4 Structure of a Binary Tree (30分)Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, a binary tree can be uniquely determined. Now given a sequence of statements about the structure of the resulting tree, you are supposed to tell if they are correct or not. A statment is one of the following: A is the rootA and B are siblingsA is the parent of BA is the left child of BA is the right child of BA and B are on the same levelIt is a full treeNote: ...

7-3 Telefraud Detection (25分)Telefraud（电信欺骗） remains a common and persistent problem in our society. In some cases, unsuspecting victims lose their entire life savings. To stop this crime, you are supposed to write a program to detect those suspects from a huge amount of phone call records. A person must be detected as a suspect if he/she makes more than K short phone calls to different people everyday, but no more than 20% of these people would call back. And more, if two suspects are calling each other, we say they might belong to the same gang. A makes a short phone call to B means that the total duration of the calls from A to B is no more than 5 minutes. ...

7-2 Anniversary (25分)Zhejiang University is about to celebrate her 122th anniversary in 2019. To prepare for the celebration, the alumni association （校友会） has gathered the ID's of all her alumni. Now your job is to write a program to count the number of alumni among all the people who come to the celebration. Input Specification:Each input file contains one test case. For each case, the first part is about the information of all the alumni. Given in the first line is a positive integer $N (≤10^5)$. Then N lines follow, each contains an ID number of an alumnus. An ID number is a string of 18 digits or the letter X. It is guaranteed that all the ID's are distinct. ...

7-1 Sexy Primes (20分)Sexy primes are pairs of primes of the form (p, p+6), so-named since "sex" is the Latin word for "six". (Quoted from http://mathworld.wolfram.com/SexyPrimes.html) Now given an integer, you are supposed to tell if it is a sexy prime. Input Specification:Each input file contains one test case. Each case gives a positive integer $N (≤10^8)$. Output Specification:For each case, print in a line Yes if N is a sexy prime, then print in the next line the other sexy prime paired with N (if the answer is not unique, output the smaller number). Or if N is not a sexy prime, print No instead, then print in the next line the smallest sexy prime which is larger than N. ...

题目粗心：给定一颗N个节点的齐全二叉树的档次序列，须要输入该树的所有从根节点到叶子节点的门路(优先拜访右子树),而后判断是否是堆，如果不是输入Not Heap，否则输入Max Heap或者Min Heap。 算法思路：应用heap数组存储齐全二叉树的档次遍历，无需做任何建树的操作，因为节点的下标之间天然存在父子关系，所以间接应用先序遍历遍历这课树，并且在拜访每一个节点的时候应用path数组进行保留，在遇到叶子节点的时候就进行输入，节点拜访结束就回溯，该过程应用$preTraverse$函数来实现。紧接着就是应用$isMaxHeap$和$isMinHeap$变量标记以后齐全二叉树是否是大根堆或者小根堆，初始为true,而后应用援用传值到$isMaxOrMinHeap$中，同时判断是否是大根堆或者小根堆，这里采纳负向逻辑，只有有左孩子，左孩子小于根节点的阐明不是小根堆，否则阐明不是大根堆，右孩子亦然如此。最初依据$isMaxHeap$和$isMinHeap$的值进行相应的输入即可。 提交后果： AC代码：#include<cstdio>#include<vector>using namespace std;int N;int heap[1005];vector<int> path;void preTraverse(int root){ if(rreoot>N) return; // 先拜访以后节点，因为这样就能够在遇到叶子节点的时候失去一个从根节点到叶子节点的门路 path.push_back(heap[root]); if(2*root>N&&2*root+1>N){ // 达到叶子节点,输入该门路即可 for(int i=0;i<path.size();++i){ printf("%d",path[i]); if(i<path.size()-1) printf(" "); } printf("\n"); } preTraverse(2*root+1); preTraverse(2*root); path.pop_back();}void isMaxOrMinHeap(bool &isMaxHeap,bool &isMinHeap){ for (int i = 1; i <= N; ++i) { if((2*i<=N&&heap[i]<heap[2*i])||(2*i+1<=N&&heap[i]<heap[2*i+1])){ isMaxHeap = false; } if((2*i<=N&&heap[i]>heap[2*i])||(2*i+1<=N&&heap[i]>heap[2*i+1])){ isMinHeap = false; } }}int main(){ scanf("%d",&N); for (int i = 1; i <= N; ++i) { scanf("%d",&heap[i]); } postTraverse(1); bool isMaxHeap = true; bool isMinHeap = true; isMaxOrMinHeap(isMaxHeap,isMinHeap); if(isMaxHeap){ printf("Max Heap"); } else if(isMinHeap){ printf("Min Heap"); } else { printf("Not Heap"); } return 0;}

题目粗心：给出一个图（先给出所有边，后给出每个点的色彩），问是否满足：所有的边的两个点的色彩不雷同，如果存在须要输入不同顶点个数，否则输入No。 算法思路：咱们应用set diff_colors保留每一次输出的每一个顶点，其大小就是不同顶点的个数，而后遍历每一条边，如果呈现一条边的2个顶点色彩雷同的状况，阐明不存在k-coloring，输入No,否则输入diff_colors汇合的大小。 提交后果： AC代码：#include<cstdio>#include<unordered_set>using namespace std;struct Edge{ int a,b;}edges[10005];int N,M;// 顶点和边的数目unordered_set<int> diff_colors;int colors[10005];// 记录每一个节点的色彩int main(){ scanf("%d %d",&N,&M); int a,b; for (int i = 0; i < M; ++i) { scanf("%d %d",&a,&b); edges[i].a = a; edges[i].b = b; } int K; scanf("%d",&K); for (int j = 0; j < K; ++j) { int color; bool proper = true; diff_colors.clear();// 每一次都得清空 for (int i = 0; i < N; ++i) { scanf("%d",&color); colors[i] = color; diff_colors.insert(color); } // 遍历每一条边 for (int k = 0; k < M; ++k) { int u = edges[k].a; int v = edges[k].b; if(colors[u]==colors[v]){ // 一条边的2个顶点呈现色彩雷同的状况 proper = false; break; } } if(proper){ printf("%lu-coloring\n",diff_colors.size()); } else { printf("No\n"); } } return 0;}

题目粗心：给出一个L长度的字符串，求出其中第一个K位的素数。 算法思路：应用字符串s承受输出的字符串，并枚举每个k位的子串(起始地位从0到L-K)，而后再转换成整数，判断是否是素数，如果是就间接输入并退出程序。如果不存在就输入404. 留神点：1、测试点3考查前导0的输入。提交后果： AC代码：#include<cstdio>#include<string>#include<iostream>#include<cmath>using namespace std;bool isPrime(int num){ if(num<=1){ return false; } int sqrtn = (int)sqrt(num*1.0); for (int i = 2; i <= sqrtn; ++i) { if(num%i==0){ return false; } } return true;}int main(){ int L,K; scanf("%d %d",&L,&K); string s; cin>>s; int len = L-K; for(int i=0;i<=len;++i){ string r = s.substr(i,K); int num = stoi(r); if(isPrime(num)){ cout<<r; return 0; } } printf("404"); return 0;}

题目粗心：给定一颗含有N个节点的前序和中序序列，要求给定任意2个节点，须要输入其最近公共先人。 算法思路：这里和1143一样给出2种思路，一种不必建树，一种须要建树。 算法思路1(不必建树)：咱们借鉴建树的递归过程实现树的局部搜寻，如果以后搜寻的子树的根节点和查问节点U和V相等，阐明其中之一就是先人，间接保留并返回即可，否则获取U和V是否在左子树或者右子树的标记，如果都在左子树，那么就都往左子树搜寻，如果都在右子树，那么就都往右子树搜寻，否则阐明以后子树的根节点就是U和V的最近公共先人，间接保留并返回即可，具体做法就是，在输出中序序列的时候，应用pos保留每一个节点在中序遍历序列中的地位，那么每一次递归查找中序序列根节点的地位就能够替换为int k = pos[pre[preL]];而后再应用uInRight和vInRight别离示意U和V是否在右子树，true示意在右子树，获取的办法也很简略，就是pos[U]>k和pos[V]>k即可，而后再依据uInRight和vInRight的值，要么递归搜寻，要么保留先人ancestor = pre[preL];并返回即可。 算法思路2(建树)：首先依据前序和中序建设一颗二叉树，而后利用层序遍历的办法取得每一个节点的父亲和其所在层数，对于输出的节点x和y，如果节点所在层数一样，那么只有两者不相等就一起向上搜寻，直到相遇，其相遇节点即为最近公共先人，否则让层数更大的那个先向上走，直到和另外一个节点层数雷同，而后再同时向上，直到相遇为止。 留神点：1、对于算法思路一呈现的测试点4超时景象，须要应用pos记录每一个节点在中序序列的地位，这是要害。提交后果： AC代码1（举荐）：#include<cstdio>using namespace std;const int maxn = 0x3ffffff;int N,M;// 节点数目和测试数目int pre[maxn],in[maxn];bool isValid[maxn];int pos[maxn];// 每一个节点在中序序列中的下标，不会超时的要害void createTree(int preL,int preR,int inL,int inR,int &ancestor,int U,int V){ if(preL>preR) return; if(pre[preL]==U||pre[preL]==V){ ancestor = pre[preL]==U?U:V; return ; } // 找到根节点在中序序列中的地位 int k = pos[pre[preL]];// 间接获取地位 int numOfLeft = k-inL;// 左子树节点个数 bool uInRight = pos[U]>k,vInRight = pos[V]>k;// U和V在左子树还是右子树，true在右子树 if(uInRight&&vInRight){ // U和V都在右子树 createTree(preL+numOfLeft+1,preR,k+1,inR,ancestor,U,V); } else if(!uInRight&&!vInRight){ // U和V都在左子树 createTree(preL+1,preL+numOfLeft,inL,k-1,ancestor,U,V); } else { // U和V别离在左右子树 ancestor = pre[preL]; return; }}int main(){ scanf("%d %d",&M,&N); for (int i = 0; i < N; ++i) { scanf("%d",&in[i]); isValid[in[i]] = true; pos[in[i]] = i; } for (int i = 0; i < N; ++i) { scanf("%d",&pre[i]); } for (int j = 0; j < M; ++j) { int u,v; scanf("%d %d",&u,&v); if(!isValid[u]&&!isValid[v]){ printf("ERROR: %d and %d are not found.\n",u,v); } else if(!isValid[u]){ printf("ERROR: %d is not found.\n",u); } else if(!isValid[v]){ printf("ERROR: %d is not found.\n",v); } else { int ancestor = -1; createTree(0,N-1,0,N-1,ancestor,u,v); if (ancestor==u||ancestor==v){ printf("%d is an ancestor of %d.\n",ancestor,ancestor==u?v:u); } else { printf("LCA of %d and %d is %d.\n",u,v,ancestor); } } } return 0;}AC代码2：#include<cstdio>#include<string>#include<cstring>#include<iostream>#include<queue>#include<algorithm>using namespace std;struct node{ int data; int level; node* lchild; node* rchild; node* parent; }; const int maxn = 200005;int pre[maxn],in[maxn];int Hash[maxn];//PAT不能用hash node* preN[maxn];int num = 0;//先序遍历下标 node* newNode(int x){ node* w = new node; w->data =x; w->level = 1; w->lchild=w->rchild=w->parent=NULL; return w;}//依据以后子树的前序排序序列和中序排序序列构建二叉树 node* create(int preL,int preR,int inL,int inR){ if(preL>preR){//以后子树为空，没有结点 return NULL; } node* root = newNode(pre[preL]); //首先找到中序遍历序列中等于以后根结点的值得下标 int i; for(i=inL;i<=inR;++i){ if(in[i]==pre[preL]){ break; } } int numLeft = i-inL; //往左子树插入,左子树先序遍历区间为[preL+1,preL+numleft],中序遍历区间为[inL,i-1] root->lchild = create(preL+1,preL+numLeft,inL,i-1); //往右子树插入,右子树先序遍历区间[preL+numLeft+1,preR],中序遍历区间为[i+1,inR] root->rchild = create(preL+numLeft+1,preR,i+1,inR); return root;}//先序遍历void tre(node* root){ if(root==NULL) return; preN[num++] = root; tre(root->lchild); tre(root->rchild);} //层序遍历void layerOrder(node* root){ queue<node*> q; q.push(root); while(!q.empty()){ node* w = q.front(); q.pop(); if(w->lchild!=NULL){ w->lchild->level = w->level+1; w->lchild->parent = w; q.push(w->lchild); } if(w->rchild!=NULL){ w->rchild->level = w->level+1; w->rchild->parent = w; q.push(w->rchild); } }} int main(){ int m,n;//测试的结点对数和结点数目 scanf("%d %d",&m,&n); memset(Hash,0,sizeof(Hash)); for(int i=0;i<n;++i){ scanf("%d",&in[i]); } for(int i=0;i<n;++i){ scanf("%d",&pre[i]); Hash[pre[i]] = i+1; } node* root = create(0,n-1,0,n-1); layerOrder(root); //先序遍历 tre(root); //测试 int x,y; for(int i=0;i<m;++i){ scanf("%d %d",&x,&y); if(Hash[x]!=0&&Hash[y]!=0){ //均是树中结点 node* w1 = preN[Hash[x]-1];//通过结点的值找到前序遍历数组的下标，而后再找到对应结点 node* w2 = preN[Hash[y]-1]; if(w1->level==w2->level){ //2个结点在同一层 if(w1==w2){ printf("%d is an ancestor of %d.\n",x,y); } else{ //2结点不相等，则同时往上走 node* t1 = w1; node* t2 = w2; while(t1->parent!=NULL){ t1 = t1->parent; t2 = t2->parent; if(t1==t2){ printf("LCA of %d and %d is %d.\n",x,y,t1->data); break; } } } }else{ //2结点不在同一层,让层数较大的先往上走 node* max = w1->level>w2->level?w1:w2; node* min = w1->level<w2->level?w1:w2; while(max->level!=min->level&&max->parent!=NULL){ max = max->parent; } //而后判断min是否和max相等 if(min==max){ //阐明min是max的先人,但此时max曾经更改所以得从新赋值 max = w1->level>w2->level?w1:w2; printf("%d is an ancestor of %d.\n",min->data,max->data); } else{ //2结点不相等，则同时往上走 while(max->parent!=NULL){ max = max->parent; min = min->parent; if(max==min){ printf("LCA of %d and %d is %d.\n",x,y,min->data); break; } } } } }else if(Hash[x]==0&&Hash[y]!=0){ printf("ERROR: %d is not found.\n",x); }else if(Hash[x]!=0&&Hash[y]==0){ printf("ERROR: %d is not found.\n",y); }else{ printf("ERROR: %d and %d are not found.\n",x,y); } } return 0;}

题目粗心：已知 N 名玩家中有 2 人表演狼人角色，有 2 人说的不是瞎话，有狼人扯谎但并不是所有狼人都在扯谎。要求你找出表演狼人角色的是哪几号玩家，如果有解，在一行中按递增程序输入 2 个狼人的编号；如果解不惟一，则输入最小序列解；若无解则输入 No Solution. 算法思路：题意不太好了解，此题没有考查任何算法技巧，是一个模拟题，重点在于依据给定的信息假如一个确定条件，在搜寻过程中，呈现同时合乎第二个条件的就是解，具体来说就是，题目给定了2个确定的条件，第一个就是有且仅有2个狼人，第二个就是有2人说谎，一个是狼人，一个是平民。题目既然要求给出狼人的编号，那么搜寻的整体空间就是所有人，因为狼人有2个，所以得应用双重循环搜寻所有狼人，别离应用i和j代表2个狼人的编号(i<=j)。既然当初确定了狼人的编号，就阐明第一个确定条件曾经应用，当初就是须要晓得怎么晓得一个人有说谎了，其实也很简略，每次搜寻的时候，咱们给所有人一个初始状态，均为1，示意平民，让i和j为-1示意狼人，如果有一个人k说的话指定的那个人的状态a[k]与其当初自身的状态不统一就阐明k在说谎。具体的做法就是，应用state初始化为1，state[i] = state[j] = -1;遍历每一个人的编号，只有a[k]*state[abs(a[k])]<0(a[k]为k所说的那个人的身份)，就阐明k在说谎,记录下来，增加进liars中，只有liars.size()==2&&state[liars[0]]+state[liars[1]]==0，阐明当初找到一个解,因为是从返回后搜寻失去的后果，编号肯定是最小的，间接退出循环。 考场上要是遇见这个题，心态可能得解体。提交后果： AC代码：#include<cstdio>#include<vector>#include<algorithm>using namespace std;int main(){ int N; scanf("%d",&N); int a[N+1]; for (int i = 1; i <= N; ++i) { scanf("%d",&a[i]); } // 暴力搜寻,遍历所有的狼人，找到2个说谎的人，一人是平民，一人是狼人 for (int i = 1; i <= N; ++i) { for (int j = i+1; j <= N; ++j) { // 首先初始化每一个人的状态，假如都是平民 int state[N+1]; fill(state,state+N+1,1); //(i,j)是一对狼人 state[i] = state[j] = -1; // 只有以后人说的话与那个人的身份不合乎，阐明在说谎 vector<int> liars; state[i] = state[j] = -1; for (int k = 1; k <= N; ++k) { if(a[k]*state[abs(a[k])]<0){ //k在说谎,记录下来 liars.push_back(k); } } if(liars.size()==2&&state[liars[0]]+state[liars[1]]==0){ // 找到一组解 printf("%d %d",i,j); return 0; } } } printf("No Solution"); return 0;}

题目粗心：给定一个N个顶点和M条边的无向图,K个查问，每一个查问输出长度为n的门路，判断该门路是否是TS cycle或者TS simple cycle并输入题目要求的对应信息。 算法思路：咱们应用邻接矩阵G保留该图的边权，而后应用path数组保留每一次查问的门路，判断该门路是否是TS cycle和TS simple cycle的办法如下： 1、应用 set differentVertices汇合保留所有门路上的不同顶点数目，total_dist为门路长度，frequencyOfStart为终点呈现的次数，isNa标记门路是否连通。2、遍历门路上每一个顶点，累加total_dist的边权并判断以后边权是否为0，如果是，阐明该门路不连通，isNa = true，并统计终点呈现的次数。3、首先判断isNa是否为true，如果是阐明以后门路不连通，肯定不是cycle，输入printf("Path %d: NA (Not a TS cycle)n",i);如果不是转44、判断终点和起点是否一样，如果不一样，阐明该门路不是cycle，输入printf("Path %d: %d (Not a TS cycle)n",i,total_dist);否则转55、判断differentVertices的大小(门路中呈现的不同顶点数目)是否等于N，如果不是，阐明没有拜访每一个城市,不是TS cycle或者TS simple cycle，输入printf("Path %d: %d (Not a TS cycle)n",i,total_dist);否则转66、判断顶点呈现了几次，如果是2次，阐明是TS simple cycle，输入printf("Path %d: %d (TS simple cycle)n",i,total_dist);否则是TS cycle,输入printf("Path %d: %d (TS cycle)n",i,total_dist);同时在此状况下，得更新TS cycle或者TS simple cycle的最小门路长度和编号。留神点：1、只有在判断以后门路是TS cycle或者TS simple cycle的时候能力进行更新最小门路长度提交后果： AC代码：#include<cstdio>#include<vector>#include<unordered_set>using namespace std;int N,M;// 顶点数目和边数int G[205][205];// 邻接矩阵,存储边权，不存在为0int main(){ scanf("%d %d",&N,&M); int a,b,dist; for (int i = 0; i < M; ++i) { scanf("%d %d %d", &a, &b, &dist); G[a][b] = G[b][a] = dist; } int K,num,city; scanf("%d",&K); int min_dis = 0x3fffffff; int min_dis_index = -1; for(int i=1;i<=K;++i){ scanf("%d",&num); vector<int> path; unordered_set<int> differentVertices;// 门路中不同顶点的数目 for (int j = 0; j < num; ++j) { scanf("%d",&city); path.push_back(city); } // 取得门路长度和终点呈现的次数 int total_dist = 0; int frequencyOfStart = 0; bool isNa = false; for (int k = 0; k < path.size(); ++k) { differentVertices.insert(path[k]); if(k<path.size()-1){ total_dist += G[path[k]][path[k+1]]; if(G[path[k]][path[k+1]]==0) { // 存在无奈达到的边 isNa = true; } } if(path[k]==path[0]){ ++frequencyOfStart; } } if(isNa){ // 以后门路不连通，肯定不是cycle printf("Path %d: NA (Not a TS cycle)\n",i); } else { // 肯定连通 if(path[0]!=path[path.size()-1]){ // 终点和起点不一样，不是cycle printf("Path %d: %d (Not a TS cycle)\n",i,total_dist); } else { // 肯定是cycle，终点至多呈现了2次 if(differentVertices.size()!=N){ // 没有拜访每一个城市,不是TS cycle或者TS simple cycle printf("Path %d: %d (Not a TS cycle)\n",i,total_dist); } else { // 肯定是TS cycle或者TS simple cycle if(min_dis>total_dist){ // 更新最短距离和编号 min_dis_index = i; min_dis = total_dist; } if(frequencyOfStart==2){ // 顶点只呈现了2次且拜访了每一个城市,是TS simple cycle printf("Path %d: %d (TS simple cycle)\n",i,total_dist); } else{ // 顶点呈现大于2次且拜访了每一个城市,是TS cycle printf("Path %d: %d (TS cycle)\n",i,total_dist); } } } } } printf("Shortest Dist(%d) = %d",min_dis_index,min_dis); return 0;}

题目粗心：现有N对互不兼容的物品清单和M个须要装箱的货物清单，询问每一个须要装箱的货物清单是否能够齐全兼容并装箱，如果能够输入Yes，否则输入No。 算法思路：首先应用$incompatible$二维数组存储每一个物体的所有不兼容的物体，并应用$incompat$数组记录以后货箱有哪些无奈兼容的物品(为true即为不可兼容)，而后在每一个须要装箱的货物进行顺次装箱的时候，先查看以后物品是否与曾经装箱的物品兼容，如果是，那么就将与该物品不兼容的所有物品的$incompat$记录为true，只有在装箱的时候呈现一次$incompat$为true的状况，就阐明该货物清单无奈齐全装箱，并应用$isCompatible$记录为false,否则为true,最初依据$isCompatible$进行输入Yes和No即可。 提交后果： AC代码：#include<cstdio>#include<vector>#include<cstring>using namespace std;vector<int> incompatible[100000];// 每一个物品的所有不兼容的物体汇合bool incompat[100000];// 以后集装箱不可兼容的物体int main(){ int N,M; scanf("%d %d",&N,&M); int a,b; for (int i = 0; i < N; ++i) { // N对互不兼容的物品 scanf("%d %d",&a,&b); incompatible[a].push_back(b); incompatible[b].push_back(a); } for (int i = 0; i < M; ++i) { int num; scanf("%d",&num); memset(incompat,0, sizeof(incompat)); bool isCompatible = true;// 以后集装箱是否能够兼容所有物品 for (int j = 0; j < num; ++j) { int index; scanf("%d",&index); if(!incompat[index]){ // 将index退出其中，并且将其不兼容的物品全副设置为true for(auto &item:incompatible[index]){ incompat[item] = true; } } else { isCompatible = false;// 这里不能break,因为得承受所有的输出数据 } } if(isCompatible){ printf("Yes\n"); } else { printf("No\n"); } } return 0;}

题目粗心：现有M个查问，每一个查问给定一个长度为N的齐全二叉树层序序列，判断该二叉树是大根堆，小根堆和非堆，而后输入该齐全二叉树的后序遍历序列。 算法思路：对于齐全二叉树能够应用一个数组来保留其层序序列，而后应用函数isMaxHeap和isMinHeap别离判断该齐全二叉树是否是大根堆还是小根堆，如果都不是则输入Not Heap，而后再应用postTraverse对该齐全二叉树进行后序遍历，拜访节点的时候输入节点即可。 isMaxHeap// 判断是否是大根堆bool isMaxHeap(){ for (int i = 1; i <= N; ++i) { if((2*i<=N&&heap[2*i]>heap[i])||(2*i+1<=N&&heap[2*i+1]>heap[i])){ return false; } } return true;}isMinHeap// 判断是否是小根堆bool isMinHeap(){ for (int i = 1; i <= N; ++i) { if((2*i<=N&&heap[2*i]<heap[i])||(2*i+1<=N&&heap[2*i+1]<heap[i])){ return false; } } return true;}提交后果： AC代码：#include<cstdio>using namespace std;int heap[1005];int M,N;// 判断是否是大根堆bool isMaxHeap(){ for (int i = 1; i <= N; ++i) { if((2*i<=N&&heap[2*i]>heap[i])||(2*i+1<=N&&heap[2*i+1]>heap[i])){ return false; } } return true;}// 判断是否是小根堆bool isMinHeap(){ for (int i = 1; i <= N; ++i) { if((2*i<=N&&heap[2*i]<heap[i])||(2*i+1<=N&&heap[2*i+1]<heap[i])){ return false; } } return true;}int num;// 管制空格输入void postTraverse(int root){ if(root>N) return; postTraverse(2*root); postTraverse(2*root+1); printf("%d",heap[root]); if(num<N-1) printf(" "); ++num;}int main(){ scanf("%d %d",&M,&N); for (int i = 0; i < M; ++i) { // M次查问 num = 0;// 每次都得赋值为0 for (int j = 1; j <= N; ++j) { scanf("%d",&heap[j]); } if(isMinHeap()){ printf("Min Heap\n"); } else if(isMaxHeap()){ printf("Max Heap\n"); } else { printf("Not Heap\n"); } postTraverse(1); printf("\n");// 记得换行 } return 0;}

题目粗心：给定一个有向图，N个顶点，M条边，现给定K个查问，每一个查问输出一个序列，判断该序列是否是该图的拓扑排序序列，如果不是，输入该序列的编号(从0开始) 算法思路：模仿拓扑排序的过程，对于输出的序列，先查看其入度是否为0，不为0阐明该序列不是拓扑排序序列，否则就将该结点的邻接点的入度全副减一，顺次向下进行判断，晓得退出循环。为了避免最初一个测试点的格局谬误，所有不是拓扑排序的序列编号都应用result数组保留，最初输入后果即可。 提交后果： AC代码：#include<cstdio>#include<vector>using namespace std;const int maxn = 1005; int inDegree[maxn];// 每一个结点的入度 int tempInDegree[maxn];// 每次查问暂存入度数组 int query[maxn];// 每次查问的序列 vector<int> Adj[maxn];// 邻接表，保留每一个结点的所有邻接点 vector<int> result;// 保留所有不是拓扑排序序列的编号 int N,M;bool isTopologicalOrder(){ for(int i=1;i<=N;++i){ // 从新赋值入度数组 tempInDegree[i] = inDegree[i]; } for(int i=0;i<N;++i){ if(tempInDegree[query[i]]!=0){ return false; } for(auto &item:Adj[query[i]]){ // 将以后顶点的邻接点的入度减一 --tempInDegree[item]; } } return true;}int main(){ scanf("%d %d",&N,&M); for(int i=0;i<M;++i){ int a,b; scanf("%d %d",&a,&b); ++inDegree[b]; Adj[a].push_back(b); } int K; scanf("%d",&K); for(int i=0;i<K;++i){ for(int j=0;j<N;++j){ scanf("%d",&query[j]); } if(!isTopologicalOrder()){ result.push_back(i); } } for(int i=0;i<result.size();++i){ printf("%d",result[i]); if(i<result.size()-1) printf(" "); } return 0;}

题目粗心：给定一颗二叉排序树的先序序列，输入待查问的两个节点的最近公共先人 。 算法思路1(不建树)：应用$pre$寄存输出的先序序列，$isLegal$标记每一个树中的节点，对于输出的节点只有小于0或者$isLegal$对应值为false，就阐明不在树中，输入对应的$ERROR$信息，都在就在先序序列中进行搜寻，假如输出的结点为$a$和$b$，那么对应$a$和$b$的所有先人肯定是在先序序列中从左向右顺次排列，那么第一次在先序序列中呈现的先人就是$a$和$b$的最近公共先人，对于$a$和$b$的先人，肯定是在$a$和$b$之间，也就是处在$[a,b]$或者$[b,a]$之中，所以，咱们须要做的事件就是遍历一遍pre数组，找到第一个处于$[a,b]$或者$[b,a]$之间的结点$ans$，而后进行输入即可。 算法思路2(建树)：首先依据二叉查找树的前序序列构建二叉排序树 ，对建设好的二叉查找树进行层序遍历,初始化每个结点的档次和父节点，首先对于2个档次不同的结点A和B，layer=max(Alayer,Blayer)，则先人肯定不在layer层上，那么先查看min(Alayer,Blayer) 层上的结点是否是另外一个结点的先人，也就是只有 Alayer！=Blayer，层数较大者始终往上走，如果层数相等后恰好为其中一个结点，则该结点就是最小公共先人，否则2个结点同时向上走，晓得走到同一结点或者到NULL。 留神点：1、结点的数值能够大于100000，所以isLegal数组大小最小为193313，否则测试点2会呈现段谬误。提交后果： AC代码1：#include<cstdio>using namespace std;struct Node{ int data; Node *left; Node *right;};int pre[100005];// 先序序列bool isLegal[193313];// 标记树中的每一个结点,过小会导致测试点2段谬误 int main(){ int M,N;// 查问数目和结点数目 scanf("%d %d",&M,&N); for(int i=0;i<N;++i){ scanf("%d",&pre[i]); isLegal[pre[i]] = true; } int a,b; for(int i=0;i<M;++i){ scanf("%d %d",&a,&b); bool not_legal_a = a<0?true:!isLegal[a]; bool not_legal_b = b<0?true:!isLegal[b]; if(not_legal_a&&not_legal_b){ printf("ERROR: %d and %d are not found.\n",a,b); }else if(not_legal_a){ printf("ERROR: %d is not found.\n",a); }else if(not_legal_b){ printf("ERROR: %d is not found.\n",b); }else{ // a和b都在树中 int ans; for(int i=0;i<N;++i){ if((pre[i]>=a&&pre[i]<=b)||(pre[i]>=b&&pre[i]<=a)){ ans = pre[i]; break; } } if(ans==a){ // a是b的先人 printf("%d is an ancestor of %d.\n",ans,b); }else if(ans==b){ // b是a的先人 printf("%d is an ancestor of %d.\n",ans,a); }else { printf("LCA of %d and %d is %d.\n",a,b,ans); } } } return 0;} AC代码2：#include<cstdio>#include<string>#include<cstring>#include<iostream>#include<queue>#include<algorithm>using namespace std;struct node{ int data; int level; node* lchild; node* rchild; node* parent; }; const int maxn = 200005;int pre[maxn];int Hash[maxn];//PAT不能用hash node* preN[maxn];int num = 0;//先序遍历下标 node* newNode(int x){ node* w = new node; w->data =x; w->level = 1; w->lchild=w->rchild=w->parent=NULL; return w;}//依据以后子树的前序排序序列构建二叉排序树 node* create(int preL,int preR){ if(preL>preR){//以后子树为空，没有结点 return NULL; } node* root = newNode(pre[preL]); //首先找到第一个大于以后子树根结点的地位i int i; for(i=preL+1;i<=preR;++i){ if(root->data<pre[i]){ break; } } //往左子树插入,左子树范畴为[preL+1,k-1] root->lchild = create(preL+1,i-1); //往右子树插入,右子树范畴为[k,preR] root->rchild = create(i,preR); return root;}//先序遍历void tre(node* root){ if(root==NULL) return; preN[num++] = root; tre(root->lchild); tre(root->rchild);} //层序遍历void layerOrder(node* root){ queue<node*> q; q.push(root); while(!q.empty()){ node* w = q.front(); q.pop(); if(w->lchild!=NULL){ w->lchild->level = w->level+1; w->lchild->parent = w; q.push(w->lchild); } if(w->rchild!=NULL){ w->rchild->level = w->level+1; w->rchild->parent = w; q.push(w->rchild); } }} int main(){ int m,n;//测试的结点对数和结点数目 scanf("%d %d",&m,&n); memset(Hash,0,sizeof(Hash)); for(int i=0;i<n;++i){ scanf("%d",&pre[i]); Hash[pre[i]] = i+1; } node* root = create(0,n-1); layerOrder(root); //先序遍历 tre(root); //测试 int x,y; for(int i=0;i<m;++i){ scanf("%d %d",&x,&y); if(Hash[x]!=0&&Hash[y]!=0){ //均是树中结点 node* w1 = preN[Hash[x]-1];//通过结点的值找到前序遍历数组的下标，而后再找到对应结点 node* w2 = preN[Hash[y]-1]; if(w1->level==w2->level){ //2个结点在同一层 if(w1==w2){ printf("%d is an ancestor of %d.\n",x,y); } else{ //2结点不相等，则同时往上走 node* t1 = w1; node* t2 = w2; while(t1->parent!=NULL){ t1 = t1->parent; t2 = t2->parent; if(t1==t2){ printf("LCA of %d and %d is %d.\n",x,y,t1->data); break; } } } }else{ //2结点不在同一层,让层数较大的先往上走 node* max = w1->level>w2->level?w1:w2; node* min = w1->level<w2->level?w1:w2; while(max->level!=min->level&&max->parent!=NULL){ max = max->parent; } //而后判断min是否和max相等 if(min==max){ //阐明min是max的先人,但此时max曾经更改所以得从新赋值 max = w1->level>w2->level?w1:w2; printf("%d is an ancestor of %d.\n",min->data,max->data); } else{ //2结点不相等，则同时往上走 while(max->parent!=NULL){ max = max->parent; min = min->parent; if(max==min){ printf("LCA of %d and %d is %d.\n",x,y,min->data); break; } } } } }else if(Hash[x]==0&&Hash[y]!=0){ printf("ERROR: %d is not found.\n",x); }else if(Hash[x]!=0&&Hash[y]==0){ printf("ERROR: %d is not found.\n",y); }else{ printf("ERROR: %d and %d are not found.\n",x,y); } } return 0;}

题目粗心：给定K给测试用例，每一个测试用例给定一个N个结点的二叉搜寻树的前序序列，要求判断该二叉树是否是红黑树。 算法思路：首先应用isRed记录所有的红色结点，这样在建树的时候就能够应用负数来建树。而后再依据先序序列建设二叉搜寻树(不须要中序),而后再应用先序遍历判断该数是否是红黑树即可。 建树过程：每一次递归拜访首先建设根节点并初始化数据，而后找到第一个大于根节点的地位k，这样[preL+1,k-1]为左子树 ，[k,preR]为右子树，别离递归建树就好。 Node* createTree(int preL,int preR){ if(preL>preR) return nullptr; Node *root = new Node; root->data = pre[preL]; // 找到第一个大于根节点的地位k int k; for(k=preL+1;k<=preR;++k){ if(pre[k]>root->data) break; } // [preL+1,k-1]为左子树 root->left = createTree(preL+1,k-1); // [k,preR]为右子树 root->right = createTree(k,preR); return root;}先序遍历判断过程：如果root==nullptr，阐明达到叶子结点，将以后门路彩色结点数目countBlack增加进set cntBlack中，而后判断汇合大小是否为1，如果不是阐明不是红黑树。如果不是叶子结点，就拜访该结点，如果是彩色结点，就自增countBlack，如果是红色结点，就判断其存在的孩子是否也是红色结点，如果是就阐明不是红黑树，并返回，否则就递归拜访左子树和右子树。 unordered_set<int> cntBlack;// 记录每一条门路的彩色结点个数void DFS(Node *root,int countBlack,bool &flag){ if(root==nullptr){ // 达到叶子结点 cntBlack.insert(countBlack); if(cntBlack.size()!=1){ // 呈现不同门路彩色结点不同的状况 flag = false; } return; } // 以后结点为黑结点 if(!isRed[root->data]){ ++countBlack; }else { // 以后结点为红结点 if((root->left!=nullptr&&isRed[root->left->data])||(root->right!=nullptr&&isRed[root->right->data])) { // 孩子结点也为红色 flag = false; return; } } DFS(root->left,countBlack,flag); DFS(root->right,countBlack,flag);}在建树之前，先判断根节点是否是彩色结点，如果是再建树，能够缩小工夫老本。 ...

题目粗心：给定一个无向图G，顶点编号为1到Nv,Ne条边，判断给出的一组顶点汇合是否形成该图的一个极大齐全子图，如果是输入Yes,否则判断是否是一个齐全子图，如果是输入Not Maximal，否则输入Not a Clique。 算法思路：首先得判断输出的汇合是否是以后图G的一个齐全子图，这里采纳isClique函数来实现，如果是就再判断是否是一个极大齐全子图，这里采纳isMaximal来实现，最初就依据判断的后果进行相应的输入就好。 isClique函数：间接遍历输出汇合的不同顶点之间是否存在不邻接的点，如果是就返回false，否则返回true。 bool G[201][201];// 邻接矩阵，判断2点是否邻接 bool isClique(const vector<int> &a){ for(int i:a){ for(int j:a){ if(i!=j&&!G[i][j]){ // 存在不邻接的结点 return false; } } } return true;}isMaximal函数：咱们应用exist标记所有输出的结点，而后遍历所有的顶点，只有没有呈现在输出汇合中并且与汇合所有顶点都邻接，阐明不是极大齐全子图，返回false,否则返回true。 bool G[201][201];// 邻接矩阵，判断2点是否邻接 bool exist[201];// 标记每一个在subset中的结点编号 bool isMaximal(const vector<int> &a,int N){ for(int i=1;i<=N;++i){ if(exist[i]) continue; bool isAllAdjcent = true; for(int j:a){ // 得判断i和所有的点是否邻接 if(!G[i][j]){ isAllAdjcent = false; break; } } if(isAllAdjcent){ // 能够扩大一个邻接点 return false; } } return true;}提交后果： ...

题目粗心：给定N个学生的ID，问题和所属学校，现要求依照每一个学校参加的学生信息获取学校的排名并输入。 算法思路：咱们应用Institution保留须要输入的学院的每一个信息，在输出的时候应用map institution容器来保留每一个学校的相干信息，而后再将信息收集结束所有学校增加进vector result容器中以不便排序从而获取排名，最初再输入即可。 获取排名的办法：// 获取排名int ra = 1;// 初始排名 for(int i=0;i<result.size();++i){ if(i==0){ result[i].rank = ra; }else { if(result[i].tws==result[i-1].tws){ // 加权分数雷同的排名雷同 result[i].rank = result[i-1].rank; }else{ // 不同的，排名等于后面的人数加1 result[i].rank = i+1; } }} 留神点：1、输入的所有学校都是小写字母组成的，输出的时候得进行解决。2、学校的加权平均分是间接截断浮点数失去的，不是四舍五入。3、排序的时候，根据的是截断后的加权平均分进行的比拟。提交后果： AC代码：#include<vector>#include<string>#include<iostream>#include<unordered_map>#include<algorithm>using namespace std;struct Institution{ int rank; string school; double TWS; int tws; int Ns;};unordered_map<string,Institution> institution;vector<Institution> result;bool cmp(const Institution &a,const Institution &b){ return a.tws!=b.tws?a.tws>b.tws:a.Ns!=b.Ns?a.Ns<b.Ns:a.school<b.school;}string toLowerCase(const string &s){ string r; for(int i=0;i<s.size();++i){ if(s[i]>='A'&&s[i]<='Z'){ r += (s[i]+32); }else{ r += s[i]; } } return r;}int main(){ int N; scanf("%d",&N); string id,school; int score; for(int i=0;i<N;++i){ cin>>id>>score>>school; // 将学校名字转化为小写字符串 string r = toLowerCase(school); institution[r].school = r; if(id[0]=='B'){ institution[r].TWS += score/1.5; }else if(id[0]=='A'){ institution[r].TWS += score; }else{ institution[r].TWS += score*1.5; } ++institution[r].Ns; } unordered_map<string,Institution>::iterator it; // 将所有学校增加进 result中不便排序 for(it=institution.begin();it!=institution.end();++it){ it->second.tws = (int)it->second.TWS; result.push_back(it->second); } sort(result.begin(),result.end(),cmp); // 获取排名 int ra = 1;// 初始排名 for(int i=0;i<result.size();++i){ if(i==0){ result[i].rank = ra; }else { if(result[i].tws==result[i-1].tws){ // 加权分数雷同的排名雷同 result[i].rank = result[i-1].rank; }else{ // 不同的，排名等于后面的人数加1 result[i].rank = i+1; } } } // 输入 printf("%lu\n",result.size()); for(auto &item:result){ printf("%d %s %d %d\n",item.rank,item.school.c_str(),item.tws,item.Ns); } return 0;}

题目粗心：给定一个[0,9]的数字D和正整数N，第一个数字为D，前面每一个数字都是用来形容后面一个数字所产生的，要求输入第N个数字。比方第一个数字为1，形容为有一个1，那么第二个数字就是数字1和次数1的组合11，顺次类推。 算法思路：这里采纳字符串来解决该问题比拟不便进行拼接操作，首先第一个数字为输出的D，那么第N个数字就是解决了N-1次后的后果，咱们每一次解决应用字符串s来保留，并且每一次都会从新赋值给D作为以后轮次的最终后果，每一次形容解决都须要遍历字符串D，对于地位j的字符，须要找到第一个和它不相等的字符的地位k,同时记录D[j]呈现的次数num,这样就失去了以后字符D[j]的形容，而后将D[j]和num增加到字符串s中，并且更新j的地位为k，直到循环完结。 留神点：1、以后字符地位j的更新得在字符串拼接操作之后进行。提交后果： AC代码：#include<cstdio>#include<string>#include<iostream>using namespace std;int main(){ int N; string D; cin>>D>>N; for(int i=0;i<N-1;++i){ // 解决N-1次 string s; for(int j=0;j<D.size();){ int num = 0;// 以后字符D[j]的个数 int k = j;// 记录第一个与D[j]字符不相等的地位 while(k<D.size()) { if(D[j]==D[k]){ ++num; }else{ break; } ++k; } // 取得以后字符D[j]和其呈现的次数 s += D[j]; s += to_string(num); j = k; } D = s; } cout<<D; return 0;}

题目粗心：一张人际关系网络图，而后给出一对情侣A和B(正数代表女生，负数代表男生)，要求找到A的敌人(不是B,和A性别雷同)C,B的敌人(不是A,和B的性别雷同)D,如果C和D是敌人那么输入C和D的编号(输入的编号均为负数)，并且依照C的非递加排列，如果雷同，则依照D的升序排列。 算法思路：对于每个人的编号保留其符号进行输出，应用string类型变量接管， 这样，判断性别是否雷同直接判断两个字符串长度是否一样就行，并且为了简化搜寻，咱们用邻接表Adj只保留每一个人的同性敌人，而后再应用邻接矩阵保留所有的敌人关系，其行为男生，列为女生，这样就能够将女生转化为负数来进行保留，又因为题目的特殊性，从A到B的门路肯定得是一个长度为4的门路，那么就间接遍历每一个A的同性敌人和B的同性敌人，判断这两人是否是敌人就好。如果是就阐明找到了C和D，并将其增加进result中，在遍历完结后，对result依照规定排序输入即可. 留神点：1、此题没有必要应用DFS，第一个起因是男生编号为0000，女生编号为-0000的状况不是很好解决，第二是最初一个测试点会运行超时。2、这里应用邻接表只保留同性敌人能够大大降低工夫复杂度。3、对于A的敌人不能是B，对于B的敌人不能是A，这里是针对A和B是同性敌人的非凡解决，避免门路长度为2.提交后果： AC代码：#include<cstdio>#include<vector>#include<cstring>#include<algorithm>#include<string>#include<cmath>#include<iostream>using namespace std;struct Pair{ int first,second; Pair(int f,int s){ first = f; second = s; }};vector<int> Adj[10000];// 邻接表 ,保留每一个人的同性敌人 int G[10000][10000];// 邻接矩阵，用来判断任意2人是否是敌人 bool cmp(const Pair &a,const Pair &b){ return a.first!=b.first?a.first<b.first:a.second<b.second;}int main(){ int N,M; scanf("%d %d",&N,&M); string a,b; for(int i=0;i<M;++i){ cin>>a>>b; int A = abs(stoi(a)); int B = abs(stoi(b)); if(a.size()==b.size()){ // a和b是同性敌人 Adj[A].push_back(B); Adj[B].push_back(A); } G[A][B] = G[B][A] = 1; } int K; scanf("%d",&K); for(int i=0;i<K;++i){ vector<Pair> result; cin>>a>>b; int A = abs(stoi(a)); int B = abs(stoi(b)); // 遍历A的同性敌人 for(auto &friendA:Adj[A]){ // 遍历B的同性敌人 if(friendA==B) continue;// 其敌人不能是B，不然长度不能到达4 for(auto &friendB:Adj[B]){ if(friendB==A) continue;// 其敌人不能是A，不然长度不能到达4 if(G[friendA][friendB]==1){ // 找到C和D result.emplace_back(friendA,friendB); } } } if(result.empty()){ printf("0\n"); }else { printf("%lu\n",result.size()); sort(result.begin(),result.end(),cmp); for(auto &item:result){ printf("%04d %04d\n",item.first,item.second); } } } return 0;}

题目粗心：给定一颗二叉树的前序和中序遍历序列，输入后序遍历序列的第一个数字 算法思路：这里采纳不建树然而借鉴建树的过程，后序遍历第一个结点实际上是左子树最左的结点，咱们只须要一直递归拜访左子树，直到第一次遇到最左的结点即可，这里应用变量c来管制是否是第一次拜访，初始为0，在c==0&&preL==preR阐明是第一次达到最左的结点，那么就输入以后结点并且++c。 留神点：1、测试的工夫在测试点4时而高时而低，无奈通过的多提交几次。提交后果： AC代码：#include<cstdio>#include<vector>using namespace std;struct Node{ int data; Node *left; Node *right;};int N;vector<int> pre,in,post;int c=0; void createTree(int preL,int preR,int inL,int inR){ if(preL>preR||c!=0) return ; int k;// 中序序列中根节点的地位 for(k=inL;k<=inR;++k){ if(pre[preL]==in[k]) break; } int numOfLeft = k-inL; createTree(preL+1,preL+numOfLeft,inL,k-1); createTree(preL+numOfLeft+1,preR,k+1,inR); if(c==0&&preL==preR){ printf("%d",pre[preL]); ++c; return; } return ;}int main(){ scanf("%d",&N); for(int i=0;i<N;++i){ int a; scanf("%d",&a); pre.push_back(a); } for(int i=0;i<N;++i){ int a; scanf("%d",&a); in.push_back(a); } createTree(0,N-1,0,N-1); return 0;}

题目粗心：给出三个名单表格，别离记录考生的在线编程的问题、期中问题和期末问题；须要计算最终问题，而后筛选出可能取得证书的名单，并依照最终问题的降序和ID的升序排列输入。 算法思路：应用Student保留学生的所有相干信息，而后应用map students记录所有的学生id与学生信息的映射,在输出的时候仅仅保留学生的id和分数就好，无需做任何预处理，而后遍历students，将所有能够取得证书的学生增加进汇合qulifiedStudents，具体做法就是对于Gp分数大于等于200的计算其最终问题，而后应用对于最终问题大于等于60分的退出qulifiedStudents汇合中，而后在对qulifiedStudents汇合进行排序输入。 留神点：1、final grade是最终问题不是G_final，而且应用最终问题判断是否大于等于60分的时候肯定得是四舍五入后的后果进行的判断，否则测试点3谬误。2、最初初始化所有的问题为-1，这样没有加入的考生问题天然就是-1，不便输入。如果是0，不放便分辨是得了0分还是没有参加考试。提交后果： AC代码：#include<cstdio>#include<string>#include<iostream>#include<unordered_map>#include<vector>#include<cmath>#include<algorithm>using namespace std;struct Student{ string id; int Gp,G_mid,G_final,G; Student(){ Gp = G_mid = G_final = G = -1; }};unordered_map<string,Student> students;vector<Student> qulifiedStudents;//所有合格的学生 bool cmp(const Student &a,const Student &b){ return a.G!=b.G?a.G>b.G:a.id<b.id;}int main(){ int P,M,N; scanf("%d %d %d",&P,&M,&N); // 输出Gp分数，且肯定都是第一次呈现 string id; for(int i=0;i<P;++i){ cin>>id; cin>>students[id].Gp; students[id].id = id; } // 输出G_mid for(int i=0;i<M;++i){ cin>>id; cin>>students[id].G_mid; students[id].id = id; } // 输出G_final for(int i=0;i<N;++i){ cin>>id; cin>>students[id].G_final; students[id].id = id; } // 遍历所有学生，筛选合格的学生 unordered_map<string,Student>::iterator it; for(it=students.begin();it!=students.end();++it){ if(it->second.Gp>=200){ //Gp大于等于200的学生，再计算最终问题是否是大于等于60 double G; if(it->second.G_mid>it->second.G_final) { G = it->second.G_mid*0.4+it->second.G_final*0.6; }else{ G = it->second.G_final; } it->second.G = (int)round(G); if(it->second.G>=60){ // 最终问题得应用四舍五入的问题来作为判断条件,不然卡测试点3 qulifiedStudents.push_back(it->second); } } } sort(qulifiedStudents.begin(),qulifiedStudents.end(),cmp); for(auto &item:qulifiedStudents){ printf("%s %d %d %d %d\n",item.id.c_str(),item.Gp,item.G_mid,item.G_final,item.G); } return 0;}

题目粗心：给定一个不超过1000位的数字A，如果是回文数，就输入A is a palindromic number.否则就计算该数和其逆置数的和如果在10次计算内其后果C是回文数，就输入每一步的计算过程和C is a palindromic number. 算法思路：因为输出数据不超过1000位，阐明数字的范畴超过了long long，所以得应用string来解决该数字并且编写函数add解决2个字符串的加法操作，并且应用num记录以后计算的次数，只有没有超过10次，就逆置初始字符串s为reverse_s，当s==reverse_s的时候完结层序，否则就取得两数的和c，输入加法操作，而后将s赋值为c，++num。如果退出了循环，阐明无奈在10步计算内失去回文数，输入Not found in 10 iterations.即可。 留神点：1、int范畴的数据对于最初一个测试点会有运行时谬误提交后果： AC代码：#include<algorithm>#include<string>#include<iostream>using namespace std;string add(const string& a,const string& b){ string s; int carry = 0; for (int i = a.size()-1;i>=0;--i) { int r = (a[i]-'0')+(b[i]-'0')+carry; s += to_string(r%10); carry = r/10; } if(carry!=0){ s += to_string(carry); } reverse(s.begin(),s.end()); return s;}int main(){ string s,reverse_s; cin>>s; int num = 0; while (num<10){ reverse_s = s; reverse(reverse_s.begin(),reverse_s.end()); if(reverse_s==s){ cout<<s<<" is a palindromic number."; return 0; } else { string c = add(s,reverse_s); cout<<s<<" + "<<reverse_s<<" = "<<c<<endl; s = c; ++num; } } cout<<"Not found in 10 iterations."; return 0;}

题目粗心：如果一个图的所有边的领接点至多有一个点在汇合中，那么就称为这个汇合为一个vertex cover，现给出一个图的顶点N和边数M，M条边的信息,和K次查问的汇合元素，问以后汇合是否是该图的一个vertex cover。 算法思路：咱们应用edges数组存储输出的M条边，每一次查问的时候就应用unordered_map<int,bool> vertices记录输出的汇合顶点为true，而后遍历每一条边，如果该边的2个领接点有一个不存在汇合中，输入No，否则输入Yes。 提交后果： AC代码:#include<cstdio>#include <unordered_map>using namespace std;struct Edge{ int a,b;}edges[10005];int main(){ int N,M; scanf("%d %d",&N,&M); for (int i = 0; i < M; ++i) { int a,b; scanf("%d %d",&a,&b); edges[i].a = a; edges[i].b = b; } int K; scanf("%d",&K); for (int j = 0; j < K; ++j) { unordered_map<int,bool> vertices; scanf("%d",&N); for (int i = 0; i < N; ++i) { int vertex; scanf("%d",&vertex); vertices[vertex] = true; } bool isCover = true; for(int i=0;i<M;++i){ if(!vertices[edges[i].a]&&!vertices[edges[i].b]){ // 该边的2个顶点都没有呈现在汇合中 isCover = false; break; } } if(isCover){ printf("Yes\n"); } else { printf("No\n"); } } return 0;}

题目粗心：给定一个单链表，节点数目N和阈值K，从新将链表依照如下规定进行排序，节点值小于0的在最右边，[0,K]的在两头，大于K的在最左边,同时同一类别的节点其绝对程序不能扭转. 算法思路:算法思路1:因为题目给出的是动态链表,那么数据和地址实际上是绑定在一起的,next指针根本能够先不思考，咱们给链表上每一个节点设置一个flag和id，别离示意以后节点的类别(0对应小于0的节点，1对应[0,K]的节点，2对应大于K的节点),节点在链表中的地位(用来记录绝对地位)，那么应用nodes数组承受所有的输出节点，而后将不在链表中的节点过滤后增加到list中，而后对list的节点进行排序，排序规定如下：flag小的在前，flag雷同的，id小的在前。而后间接输入list数组即可，只须要留神以后节点不是最初一个节点的话，以后节点的next就是就是下一个节点的地址。 算法思路:开拓第二个链表，第一遍遍历将所有的正数节点增加进新链表，第二次遍历将所有在[0,K]范畴的节点增加进新链表，第三次遍历将残余所有的节点增加进新链表。 留神点：1、须要过滤输出的数据，防止出现有效节点(PAT动态链表的套路)。提交后果： AC代码1：#include<cstdio>#include<vector>#include<algorithm>using namespace std;struct Node{ int address; int data; int next; int flag; int id;}nodes[100005];vector<Node> list;// 链表bool cmp(const Node &a,const Node &b){ return a.flag!=b.flag?a.flag<b.flag:a.id<b.id;}int main(){ int begin_address,N,K; scanf("%d %d %d",&begin_address,&N,&K); int address,data,next; for (int i = 0; i < N; ++i) { scanf("%d %d %d",&address,&data,&next); nodes[address].address = address; nodes[address].data = data; nodes[address].next = next; if(data<0){ nodes[address].flag = 0; } else if(data<=K){ nodes[address].flag = 1; } else { nodes[address].flag = 2; } } // 遍历所有节点，过滤有效节点 int num = 1; while (begin_address!=-1){ nodes[begin_address].id = num++;// 记录绝对地位 list.push_back(nodes[begin_address]); begin_address = nodes[begin_address].next; } sort(list.begin(),list.end(),cmp); for (int j = 0; j < list.size(); ++j) { printf("%05d %d ",list[j].address,list[j].data); if(j==list.size()-1){ printf("-1"); } else { printf("%05d\n",list[j+1].address); } } return 0;}AC代码2:#include<cstdio>#include<cstring>using namespace std;struct Node{ int address; int data; int next;}node1[100005];int main(){ int start,n,k; scanf("%d %d %d",&start,&n,&k); Node nodes[n]; for(int i=0;i<n;++i){ Node nd; scanf("%d %d %d",&nd.address,&nd.data,&nd.next); node1[nd.address] = nd; } int cnt = 0; //第一次找出data为正数的 Node root = node1[start]; while (root.next!=-1){ if (root.data<0){ nodes[cnt++] = root; } root = node1[root.next]; } if (root.data<0){ nodes[cnt++] = root; } //第二次遍历,[0,K]范畴的所有节点 root = node1[start]; while (root.next!=-1){ if (root.data>=0&&root.data<=k){ nodes[cnt++] = root; } root = node1[root.next]; } if (root.data>=0&&root.data<=k){ nodes[cnt++] = root; } //第三次遍历，大于K的所有节点 root = node1[start]; while (root.next!=-1){ if (root.data>k){ nodes[cnt++] = root; } root = node1[root.next]; } if (root.data>k){ nodes[cnt++] = root; } //更新next for (int i=0;i<cnt-1;++i){ nodes[i].next = nodes[i+1].address; } nodes[cnt-1].next = -1; for (int i=0;i<cnt;++i){ printf("%05d %d",nodes[i].address,nodes[i].data); if (nodes[i].next!=-1){ printf(" %05d\n",nodes[i].next); }else { printf(" -1\n"); } } return 0;}

题目粗心：给定一个数字Z，其位数为偶数，在其中间划开，后面的数字为A，前面的数字为B，如果Z能整除A*B，输入Yes,否则输入No。 算法思路：看到宰割问题，首先想到的是字符串宰割，咱们采纳string s来承受输出的数字，而后将其前半部分宰割并转化为整数为a，后半局部宰割并转化为整数为B，并将s转化为整数z,如果z%(a*b)==0，输入Yes,否则输入No。 留神点：1、a和b，也就是除数有可能为0，此时不能做取余运算，否则会最初2个测试点会呈现浮点谬误，间接特判输入No，而后持续下一个循环即可。提交后果： AC代码：#include<cstdio>#include<string>#include<iostream>using namespace std;int main(){ int N; scanf("%d",&N); for (int i = 0; i < N; ++i) { string s; cin>>s; int z = stoi(s); int a = stoi(s.substr(0,s.size()/2)); int b = stoi(s.substr(s.size()/2)); if(a==0||b==0){ printf("No\n"); continue; } if(z%(a*b)==0){ printf("Yes\n"); } else { printf("No\n"); } } return 0;}

题目粗心：给一个无向图，求出从一点到另外一点的最短门路，这里的最短，指的是从终点到起点所经验的点的数目起码，如果有多条，输入中转站点起码的。 算法思路：一开始想到的是用Dijkstra算法求解该问题，然而Dijkstra算法更适宜求解第一标尺为边权相干问题，所以想到了DFS，并设置其参数depth,用来记录在从终点到起点的遍历过程中所经验的结点个数，而后采纳全局量minDepth保留最小的depth,为了不便判断是否是直达结点问题，应用邻接矩阵存储两个连贯的点的边对应的线路，比方2000与2001连通，该边是Line# 4的一部分，则G[2000][2001]=4;应用全局变量$minTranNum$记录乘坐的起码线路数目。 DFS遍历办法：DFS函数中设置参数为以后结点st,起点e和深度depth,应用vector<int> result保留最优的门路,vector<int> path暂存以后门路, 首先拜访以后节点(保留到path中，并设置拜访标记为true)，而后判断是否达到起点，如果是，首先计算以后门路的直达节点数目，这里的计算方法是应用一个set汇合$diffLines$增加所有的 线路，其大小就是乘坐的线路数目(其大小减一就是直达节点数目)，如果minDepth>depth阐明以后门路更短，那么就更新最优门路和最优间隔和乘坐线路数目,如果 长度雷同然而乘坐的线路起码，那么更新最优门路和乘坐线路数目，最初回溯。如果没有达到起点，就递归遍历每一个没有拜访的领接点，如果所有的领接点都曾经拜访结束， 那么就回溯。 留神点：1、每一次查问都得将全局变量minDepth，minTranNum，visited初始化。2、如果程序没有报错，没有输入后果，查看是否DFS函数有回退操作(path.pop_back(),visited[st]=false)提交后果： AC代码：#include<cstdio>#include<vector>#include<unordered_set>#include<cstring>using namespace std;int G[10000][10000];//G[i][j]=4示意i和j相连接的边在第4条地铁上vector<int> path;// 暂存以后搜寻到的门路vector<int> result;// 最优门路vector<int> Adj[10000];// 邻接表bool visited[10000];int minDepth;// 最短长度int minTranNum;//乘坐的起码线路数目void DFS(int st, int e, int depth){ // 首先拜访以后节点 path.push_back(st); visited[st] = true; if(st == e){ // 达到起点 // 计算乘坐的线路数目 unordered_set<int> diffLines;// 不同的线路数目 for (int i = 0; i < path.size() - 1; ++i) { diffLines.insert(G[path[i]][path[i+1]]); } if(minDepth>depth){ // 以后门路更短 result = path; minDepth = depth; minTranNum = diffLines.size(); } else if(minDepth==depth&&minTranNum>diffLines.size()){ // 长度雷同,然而直达次数起码 result = path; minTranNum = diffLines.size(); } // 回溯 path.pop_back(); visited[st] = false; return; } // 拜访每一个领接点 for (int next : Adj[st]) { // 领接点 if(!visited[next]){ DFS(next, e, depth + 1); } } path.pop_back();// 回溯 visited[st] = false;}void print(int start,int end){ printf("%d\n",minDepth); int current_line = G[result[0]][result[1]];// 以后线路 int s = start;// 乘坐以后线路的终点 for (int i = 1; i < result.size()-1; ++i) { if(G[result[i]][result[i+1]]!=current_line){ // i为换乘站 printf("Take Line#%d from %04d to %04d.\n",current_line,s,result[i]); s = result[i]; current_line = G[result[i]][result[i+1]]; } } // 始终没有换乘或者以后位最初一次直达地铁线 printf("Take Line#%d from %04d to %04d.\n",current_line,s,end);}int main(){ int N; scanf("%d",&N); for (int i = 0; i < N; ++i) { int M; scanf("%d",&M); int a,b; for (int j = 0; j < M; ++j) { if(j==0){ scanf("%d",&a); } else { scanf("%d",&b); G[a][b] = G[b][a] = i+1; Adj[a].push_back(b); Adj[b].push_back(a); a = b; } } } int K; scanf("%d",&K); int start,end; for (int k = 0; k < K; ++k) { scanf("%d %d", &start, &end); // 每次查问都得初始化 minDepth = 0x3fffffff; minTranNum = 0x3fffffff; memset(visited,0, sizeof(visited)); path.clear(); result.clear(); DFS(start, end, 0); print(start, end);// 输入出行计划 } return 0;}

题目粗心:当初有N座房子,M个加油站待抉择点,K条边,当初要在M个加油站待抉择点抉择一个加油站进去,要求满足间隔N个房子尽可能远然而同时也得保障房子均在服务范畴Ds中,如果有多个抉择均匀间隔最小的,如果还有多个，抉择编号最小的 。 算法思路：典型的最短距离求解问题,应用Dijkstra算法实现即可,这里得先理解咱们须要取得什么样的信息,咱们通过Dijkstra算法能够取得以后加油站到所有房子的最短距离，由dis数组保留,而后咱们须要取得以下3个信息： 1.所有加油站中距离房子最短的间隔并且处于服务范畴内中的最大间隔(对应于加油站间隔N个房子尽可能远)2.以后加油站到所有房子的均匀最短距离,在1中的间隔相等的时候抉择最小的(通过dis数组能够轻易取得)3.加油站的编号(这个最好失去,每次执行Dijkstra算法的终点就是,依据1和2进行更新，否则不更新)晓得以上三点后,咱们就能够进行如下操作:1、每一个加油站节点GM的节点的编号为N+M。2、对于M个待选加油站咱们每次都进行 Dijkstra算法取得以后加油站到其余点的最短距离,保留在dis数组中,而后判断以后加油站间隔房子的间隔是否有超过服务范畴的,如果没有那么就记录以后加油站到房子的最短距离local_min_dis、到所有房子的均匀最短距离(这里应用总长度来代替)total_dis以及以后节点编号i，最初再重置visited数组就好,如果有超过范畴的，间接pass以后加油站。3、如果以后的最短距离比全局最短距离更大或者相等然而总间隔比全局总间隔更小，更新全局最短距离global_max_dis，总间隔result_total_dis和站点编号result_index。4、如果所有的加油站都超过服务返回就输入No Solution，这里应用result_index是否等于-1来进行判断。 留神点：1、每一次获取最短门路须要初始化visited2、输入节点编号的时候得减去N3、获取最短门路的时候，须要进行N+M次，也即是得加油站自身也是一个实在存在的地点，能够用来优化最短门路。4、最初保留1位小数输入的最短均匀间隔输入值和测试用例不一样然而在提交过程中没有任何问题。5、最初一个测试点呈现运行时谬误是输出外面有G10,得取G前面的字符串而后转化为数字,而不是间接取前面一位，呈现段谬误,是因为maxn设置太小了,呈现答案谬误阐明，判断输出是否为G结尾的办法出错,不能应用字符串的长度进行判断,只能用第一个字符是否为G来进行判断,因为数子是从1位到4位变动,G前面数字是从1到2位变动的,或者maxn设置为了1010及其以下的数字,最小得设置为1011能力通过.提交后果: AC代码：#include<cstdio>#include<vector>#include<algorithm>#include<string>#include<cstring>#include<iostream>using namespace std;int N,M,K,Ds;//房子数目，候选站点数目，路线数目，最大服务间隔int G[1200][1200];// 边权,示意间隔bool visited[1200];// 拜访标记数组 int dis[1200];// 每一个居民间隔终点的最短距离void Dijkstra(int start){ // 初始化 fill(dis,dis+1200,0x3fffffff); dis[start] = 0; // 循环N+M次 for(int i=1;i<=N+M;++i){ // 首先从所有未拜访的点中找到间隔终点最小的点 int nearest,minDis=0x3fffffff; for(int j=1;j<=N+M;++j){ if(!visited[j]&&minDis>dis[j]){ nearest = j; minDis = dis[j]; } } if(minDis==0x3fffffff) return ;// 没有找到，阐明其余点不再连通 // 优化借助nearest到其余未拜访的点的间隔 visited[nearest] = true; for(int j=1;j<=N+M;++j){ if(!visited[j]&&G[nearest][j]!=0&&dis[j]>dis[nearest]+G[nearest][j]){ dis[j] = dis[nearest]+G[nearest][j]; } } } }int main(){ scanf("%d %d %d %d",&N,&M,&K,&Ds); string a,b; int dist; int index_a,index_b; for(int i=0;i<K;++i){ cin>>a>>b>>dist; if(a[0]=='G'){ index_a = stoi(a.substr(1))+N;// G1为N+1 }else { index_a = stoi(a); } if(b[0]=='G'){ index_b = stoi(b.substr(1))+N; }else{ index_b = stoi(b); } G[index_a][index_b] = G[index_b][index_a] = dist; } // 求出每一个站点作为终点，其余房子间隔它的最短距离 int result_index = -1;// 最优加油站 int global_max_dis = -1;// 所有最短距离中的最大间隔 int result_total_dis = 0x3fffffff;// 最优加油站到所有居民房的总间隔 for(int i=N+1;i<=N+M;++i){ memset(visited,0,sizeof(visited));// 每一次遍历都得初始化拜访标记数组 Dijkstra(i); // 取得居民房到以后结点的最短距离后，须要取得以后加油站到所有居民房的最短距离，均匀最短距离(这里应用总间隔代替) int local_min_dis = 0x3ffffff; int total_dis = 0; bool isOutOfRange = false; for(int j=1;j<=N;++j){ if(dis[j]>Ds){ isOutOfRange = true; break; } local_min_dis = min(local_min_dis,dis[j]); total_dis += dis[j]; } if(isOutOfRange) continue;// 以后加油站无奈为所有居民提供服务 if(global_max_dis<local_min_dis){ result_index = i; global_max_dis = local_min_dis; result_total_dis = total_dis; }else if(global_max_dis==local_min_dis&&result_total_dis>total_dis){ result_index = i; result_total_dis = total_dis; } } if(result_index==-1){ printf("No Solution"); return 0; } printf("G%d\n",result_index-N); printf("%.1lf %.1lf",global_max_dis*1.0,result_total_dis*1.0/N); return 0;}

题目粗心:有N个城市，K条无向边,当初须要从某个给定的起始城市登程,返回名为"ROM"的城市，给出每条边所须要耗费的破费,求从起始城市登程,达到城市ROM所须要的起码破费,并输入起码破费的门路。如果这样的门路有多条，则抉择门路上城市的幸福值之和最大的那条门路，如果门路依然不惟一，则抉择门路上城市的均匀幸福值最大的那条 。 算法思路:此题也是典型的Dijkstra算法模板题目,咱们这里的最短门路变动为最小破费,不过实质都一样,仍然应用dis数组存储每一个点到终点的最短距离，咱们通过Dijkstra算法(只掂量第一标尺,也就是只思考破费最短)取得终点到所有节点的最小破费,以及在此门路上的所有节点的所有前驱结点,而后应用DFS遍历前驱结点数组pre(实质上是一颗树),从起点递归拜访每个结点的前驱,当拜访到终点的时候,阐明取得了一条门路,保留在shortest中,而后计算以后门路上的幸福感之和happ，如果以后happy比全局的最大幸福感max_happiness更大,那么更新 max_happiness = happ;min_num = shortest.size()-1;result = shortest;(保留门路),如果一样大然而均匀幸福感(门路长度)比全局的均匀最大幸福感(门路长度)min_num更大,也更新min_num = shortest.size()-1;result = shortest;并且得累计最短门路条数road_num。因为题目没有给定顶点范畴，所以这里采纳cityToIndex和intToCity保留顶点和编号(手动赋值)的双向映射以便于遍历和输入。 留神点：1、均匀幸福值的计算不包含终点,因为终点的幸福值默认没有,所以是除以以后门路的结点数目-1,仔细观察样例的输入后果就晓得了提交后果： AC代码：#include<cstdio>#include<vector>#include<string>#include<iostream>#include<unordered_map>#include<algorithm>using namespace std;int N,K,start=0,e;// 总人数，边数，终点,起点 int happiness[300];// 点权 int cost[300][300];// 边权 int dis[300];// 每一个城市间隔终点的最短距离bool visited[300];// 拜访标记数组vector<int> pre[300];// 每一个结点的所有前驱 vector<int> shortest;//最短门路vector<int> result;// 最优门路unordered_map<string,int> cityToIndex;// 保留城市到编号的映射 unordered_map<int,string> intToCity;// 保留编号到城市的映射int max_happiness = 0;int min_num = 0x3fffffff;// 起码结点数目int road_num = 0;// 最短门路条数 void DFS(int s){ shortest.push_back(s); if(s==start){ ++road_num; // 达到终点 int c = 0; int happ = 0; for(int i=shortest.size()-1;i>=0;--i){ if(i>0){ c += cost[shortest[i]][shortest[i-1]]; } if(i!=shortest.size()-1){ // 终点没有权值 happ += happiness[shortest[i]]; } } if(max_happiness<happ){ max_happiness = happ; min_num = shortest.size()-1; result = shortest; }else if(max_happiness==happ&&min_num>result.size()){ min_num = shortest.size()-1; result = shortest; } shortest.pop_back(); return; } for(int i=0;i<pre[s].size();++i){ DFS(pre[s][i]); } shortest.pop_back();} void Dijkstra(){ // 初始化 fill(dis,dis+300,0x3fffffff); dis[start] = 0; // 循环N+1次 for(int i=0;i<N;++i){ // 首先从所有未拜访的点中找到间隔终点最小的点 int nearest,minDis=0x3fffffff; for(int j=0;j<N;++j){ if(!visited[j]&&minDis>dis[j]){ nearest = j; minDis = dis[j]; } } if(minDis==0x3fffffff) return ;// 没有找到，阐明其余点不再连通 // 优化借助nearest到其余未拜访的点的间隔 visited[nearest] = true; for(int j=0;j<N;++j){ if(!visited[j]&&cost[nearest][j]!=0){ if(dis[j]>dis[nearest]+cost[nearest][j]){ dis[j] = dis[nearest]+cost[nearest][j]; pre[j].clear(); pre[j].push_back(nearest); }else if(dis[j]==dis[nearest]+cost[nearest][j]){ pre[j].push_back(nearest); } } } } }int main(){ string s; cin>>N>>K>>s; cityToIndex[s] = start; intToCity[start] = s; for(int i=1;i<N;++i){ cin>>s>>happiness[i]; cityToIndex[s] = i; intToCity[i] = s; if(s=="ROM") e = i; } string a,b; int C; for(int i=0;i<K;++i){ cin>>a>>b>>C; int index_a = cityToIndex[a]; int index_b = cityToIndex[b]; cost[index_a][index_b] = cost[index_b][index_a] = C; } Dijkstra(); DFS(e); printf("%d %d %d %d\n",road_num,dis[e],max_happiness,max_happiness/min_num); for(int i=result.size()-1;i>=0;--i){ printf("%s",intToCity[result[i]].c_str()); if(i>0) printf("->"); } return 0;}

题目粗心:城市外面有一些公共自行车站,每一个车站最大包容Cmax辆车,如果该车站的车辆当初有Cmax/2辆车,那么阐明它处于perfect状态,当初有一个站点Sp汇报有问题，须要控制中心(PBMC)就会找到一条间隔它最短的门路,携带或者在路上回收多余的车辆带到Sp,使得它是perfect的状态,并且将多余车辆带回PBMC,当初要求找一条从PBMC到Sp的最短门路,如果该门路有多条，抉择从PBMC携带车辆起码的，如果还有多条，抉择从Sp回来的时候带回PBMC车辆起码的,题目保障有且仅有一条数据 。 算法思路：依据题目形容是一个典型的单源最短门路问题,应用Dijstra算法求解最短门路,因为波及到要输入具体的门路,所以采纳Dijstra+DFS的办法,先应用Dijstra算法求得PBMC到Sp的间隔最短的所有门路,而后再用DFS遍历所有门路抉择合乎第二标尺,也就是PBMC携带车辆起码的或者带回PBMC车辆起码的门路. 数据的存储：应用G存储图,visited为拜访标记数组,bikes_number数组为每个结点的点权,pre数组保留每个结点的所有前驱结点,shortest为DFS遍历中保留单条门路，result用来保留最优门路，dis数组保留终点到其余节点的最短距离,min_need_sent_bike示意起码须要终点派送的车辆数目,min_need_back_bike示意须要起码须要从起点送回的车辆数目 Dijkstra算法求解咱们循环N次，每一次循环，首先从所有未拜访的点中找到间隔终点最小的点nearest,而后再优化借助nearest到其余未拜访的点的最短距离，如果借助nearest达到以后点j更短，那么就更新达到j的最短距离，最小消耗和达到j的前驱节点。如果最短距离一样然而通过nearest达到j的消耗更小，那么就更新达到j的最小消耗和j的前驱节点。 DFS算法过程：在遍历所有最短门路的过程中须要重点强调的是调整结点状态的形式，肯定得是从终点开始顺次调整每一个节点的状态，其它的办法基本不可行，间隔终点较近的节点的车辆数目较少，然而间隔终点较远的车辆数目较多且恰好能够满足，这种状况下还是得从终点派送车辆调整车辆少的节点，并且将多余的车辆带回，也就是说，不能应用$n*(Cmax/2)$的形式获得最佳车辆总数,而后用现有门路的车辆总数比拟相减，因为就算最初一个结点有十分多的车辆,也没有方法奉献给在门路后面的结点,题目的原话为 all the stations on the way will be adjusted as well.也就是单向调整的。咱们每次取得一条最短门路，就从终点的下一个节点开始遍历，如果以后车辆过多就须要带走，应用need_back_bike记录带回的车辆数目，如果以后站点车辆过少，就须要先应用在路上收集到的车辆进行填补，如果不够再从终点进行派送，need_sent_bike记录派送的车辆数目，如果以后门路须要派送的车辆数目更少或者派送数目雷同，然而带回车辆数目更少，就更新min_need_sent_bike，min_need_back_bike和result。 留神点：1、调整方向为单向调整，不能应用前面站点多余的车辆填补后面的站点。2、从路上收集的车辆数目不够用的时候，得先填补以后站点车辆的空缺，再将need_back_bike置为0.提交后果： AC代码：#include<cstdio>#include<vector>#include<algorithm>using namespace std;int Cmax,N,Sp,M;// 最大容量，站点个数，问题站点编号，路线数量 int bikes_number[505];// 点权，每一个站点的车辆数目int G[505][505];// 边权，两站点之间消耗工夫bool visited[505];// 拜访标记数组int dis[505];// 每一个站点到终点的间隔 vector<int> pre[505];// 保留每一个站点的前驱结点vector<int> shortest;//最短门路vector<int> result;// 最优门路int min_need_sent_bike = 0x3fffffff;//起码须要终点派送的车辆数目int min_need_back_bike = 0x3fffffff;//起码须要从起点送回的车辆数目 // 应用深度优先搜寻找到须要派送车辆起码的最短门路 void DFS(int start){ // 先拜访以后节点 shortest.push_back(start); if(pre[start].empty()){ // 以后节点是终点，没有前驱,计算该门路上须要派送的车辆 int need_sent_bike = 0;// 须要派送的车辆数目 int need_back_bike = 0;// 须要送回的车辆数目 int perfect_bike = Cmax/2;// 完满状态车辆数目 for(int i=shortest.size()-2;i>=0;--i){// 循环得排除终点 if(bikes_number[shortest[i]]>perfect_bike){ // 车辆过多须要带走 need_back_bike += (bikes_number[shortest[i]]-perfect_bike); }else if(bikes_number[shortest[i]]<perfect_bike){ // 以后站点,车辆过少 int need = perfect_bike-bikes_number[shortest[i]];// 以后站点须要的车辆数目 if(need_back_bike>=need){ // 从路上收集的车辆数目够用 need_back_bike -= need;// 这里得是累减 }else { // 不够用 need_sent_bike += need-need_back_bike;// 须要派送残余须要车辆,这里得是累加 need_back_bike = 0;// 这句话得在前面 } } } if(need_sent_bike<min_need_sent_bike){ // 以后门路须要派送的车辆数目更少 min_need_sent_bike = need_sent_bike; min_need_back_bike = need_back_bike; result = shortest; }else if(need_sent_bike==min_need_sent_bike&&min_need_back_bike>need_back_bike){ // 派送车辆一样，须要送回的车辆更少 min_need_back_bike = need_back_bike; result = shortest; } shortest.pop_back(); return; } for(int i=0;i<pre[start].size();++i){ DFS(pre[start][i]); } // 以后结点及其前驱都拜访结束,回溯 shortest.pop_back(); }void Dijkstra(){ // 初始化 fill(dis,dis+505,0x3fffffff); dis[0] = 0; // 循环N+1次 for(int i=0;i<=N;++i){ // 首先从所有未拜访的点中找到间隔终点最小的点 int nearest,minDis=0x3fffffff; for(int j=0;j<=N;++j){ if(!visited[j]&&minDis>dis[j]){ nearest = j; minDis = dis[j]; } } if(minDis==0x3fffffff) return ;// 没有找到，阐明其余点不再连通 // 优化借助nearest到其余未拜访的点的间隔 visited[nearest] = true; for(int j=0;j<=N;++j){ if(!visited[j]&&G[nearest][j]!=0){ if(dis[j]>dis[nearest]+G[nearest][j]){ dis[j] = dis[nearest]+G[nearest][j]; pre[j].clear(); pre[j].push_back(nearest); }else if(dis[j]==dis[nearest]+G[nearest][j]){ pre[j].push_back(nearest); } } } } } int main(){ scanf("%d %d %d %d",&Cmax,&N,&Sp,&M); for(int i=1;i<=N;++i){ scanf("%d",&bikes_number[i]); } int a,b,time; for(int i=0;i<M;++i){ scanf("%d %d %d",&a,&b,&time); G[a][b] = G[b][a] = time; } Dijkstra(); DFS(Sp);// 从起点开始递归拜访 printf("%d ",min_need_sent_bike); for(int i=result.size()-1;i>=0;--i){ printf("%d",result[i]); if(i>0) printf("->"); } printf(" %d",min_need_back_bike); return 0;}

题目要求:现有N个城市,M条路线,并给出M条路线的间隔和消耗,当初给定终点S和起点D,要求求出终点到起点最短门路、最短距离和消耗,若有多条输入消耗最小的 算法思路:这个是单源最短距离问题，这里应用Dijkstra算法的进行求解，这里须要求解的信息次要有三个，而且存在两个不同优先级的约束条件，那么咱们先应用Dijkstra算法求解取得具备最短距离的所有最短门路，而后应用深度优先遍历所有的最短门路，在其余找出消耗最小的门路即为所求。 数据的存储:这里应用c数组保留每一个城市到终点的最小消耗，cost数组保留任意两个城市之间的消耗 ，pre数组保留每个结点的前驱结点 Dijkstra算法求解咱们循环N次，每一次循环，首先从所有未拜访的点中找到间隔终点最小的点nearest,而后再优化借助nearest到其余未拜访的点的最短距离，如果借助nearest达到以后点j更短，那么就更新达到j的最短距离，最小消耗和达到j的前驱节点。如果最短距离一样然而通过nearest达到j的消耗更小，那么就更新达到j的最小消耗和j的前驱节点。 DFS搜寻：咱们从起点开始搜寻，每次递归就拜访该节点，晓得遇到终点，达到递归边界，shortest保留以后搜寻的最短门路，遍历以后门路上的每一条边，累加所有的边权取得总消耗，如果total_cost==c[D]阐明以后的是最优的，应用result保留最优门路，最初得将入栈节点退栈并返回，递归体为拜访每一个以后节点的前驱节点，拜访结束后也得退栈回溯。 留神点：1、计算消耗的时候只需计算n-1条边，并且在输入的时候得倒着拜访。提交后果： AC代码：#include<cstdio>#include<vector>#include<algorithm>using namespace std;int N,M,S,D;// 顶点数，边数，终点和起点。 int G[505][505];// 边权，其值示意为两点之间的间隔int cost[505][505];// 两点之间的消耗 bool visited[505];// 拜访标记数组int dis[505];// 每一个城市到终点的间隔int c[505];//每一个城市到终点的最小消耗vector<int> pre[505];// 保留每一个站点的前驱结点vector<int> shortest;//最短门路vector<int> result;// 最优门路void DFS(int start){ shortest.push_back(start); if(start==S){ // 以后结点是起点 int total_cost = 0; for(int i=shortest.size()-1;i>0;--i){ total_cost += cost[shortest[i]][shortest[i-1]]; } if(total_cost==c[D]){ // 以后的门路是最优的 result = shortest; } shortest.pop_back(); return; } for(int i=0;i<pre[start].size();++i){ DFS(pre[start][i]); } shortest.pop_back();} void Dijkstra(int start){ // 初始化 fill(dis,dis+505,0x3fffffff); dis[start] = 0; c[start] = 0; // 循环N次 for(int i=0;i<N;++i){ // 首先从所有未拜访的点中找到间隔终点最小的点 int nearest,minDis=0x3fffffff; for(int j=0;j<N;++j){ if(!visited[j]&&minDis>dis[j]){ nearest = j; minDis = dis[j]; } } if(minDis==0x3fffffff) return ;// 没有找到，阐明其余点不再连通 // 优化借助nearest到其余未拜访的点的间隔 visited[nearest] = true; for(int j=0;j<N;++j){ if(!visited[j]&&G[nearest][j]!=0){ if(dis[j]>dis[nearest]+G[nearest][j]){ dis[j] = dis[nearest]+G[nearest][j]; c[j] = c[nearest] + cost[nearest][j]; pre[j].clear(); pre[j].push_back(nearest); }else if(dis[j]==dis[nearest]+G[nearest][j]&&c[j]>c[nearest]+cost[nearest][j]){ c[j] = c[nearest] + cost[nearest][j]; pre[j].push_back(nearest); } } } } } int main(){ scanf("%d %d %d %d",&N,&M,&S,&D); int a,b,distance,C; for(int i=0;i<M;++i){ scanf("%d %d %d %d",&a,&b,&distance,&C); G[b][a] = G[a][b] = distance; cost[b][a] = cost[a][b] = C; } Dijkstra(S); DFS(D); for(int i=result.size()-1;i>=0;--i){ printf("%d ",result[i]); } printf("%d %d",dis[D],c[D]); return 0;}

题目粗心：给出N个城市，M条无向边。每个城市中都有肯定数目的救济小组,所有边的边权均有输出失去,当初给出终点和起点,求从终点到起点的最短门路条数以及最短门路上的救济小组数目之和。如果有多条最短门路,则输入数目之和最大的。 算法思路:本题须要求解从C1到C2的最短门路上的相干信息,那么很天然联想到用Dijstra算法，此题基本上算的上是模板题目,间接套用Dijstra算法的具体过程即可,这里惟一的不同在于存在优化门路的第二标尺,也即是救济队伍数目。 先交代数据的存储：这里应用node_weight[1000]示意每一个城市的救济的团队数目，G1000代表每一条路的长度，dis[1000]示意终点C1到所有点的最短距离，visited[1000]为标记拜访数组，num[1000]为终点到起点最优门路的条数，rescue_teams[1000]为终点到起点最优门路上能够携带的最多营救团队数目 Dijkstra过程：初始化dis[C1] = 0;rescue_teams[C1] = node_weight[C1];num[C1] = 1;而后遍历N次，每次首先寻找到一个没有拜访且间隔终点最短的结点nearest,而后依据nearest结点优化整个图中终点到其余所有节点(没有拜访)的最短距离,当通过nearest能够更短的达到j时，咱们更新最短距离dis[j],num[j],rescue_teams[j],当间隔相等时先更新门路条数num[j],而后判断通过nearest到j的点权是否更大,如果是更新最大点权rescue_teams[j],这里得留神,门路条数num只和最短距离无关. 留神点：1、门路条数num只和最短距离无关，在依据点权作为第二约束条件的时候，无需依据点权来更新。提交后果： AC代码：#include <cstdio>#include <algorithm>using namespace std;int N,M,C1,C2;// 城市数目，路线数目，所在城市，指标城市int node_weight[1000];// 点权，示意每一个城市的救济的团队数目int G[1000][1000];// 边权，代表每一条路的长度int dis[1000];// 终点C1到所有点的最短距离bool visited[1000];// 标记拜访数组int num[1000];// 最优门路的条数int rescue_teams[1000];// 最多营救团队数目void Dijkstra(){ fill(dis,dis+1000,0x3fffffff); dis[C1] = 0;//终点到终点的最短距离 num[C1] = 1;// 初始门路条数为1,C1到本身为一条门路 rescue_teams[C1] = node_weight[C1];// 初始门路的点权之和为C1的点权 // 循环N次 for (int i = 0; i < N; ++i) { // 首先找到一个间隔C1最近的未拜访的节点 int nearest = -1,min_dis = 0x3fffffff; for (int j = 0; j < N; ++j) { if(!visited[j]&&min_dis>dis[j]){ nearest = j; min_dis = dis[j]; } } // 没有找到，阐明前面的点不在连通 if(min_dis==0x3fffffff) return; // 找到间隔C1最近的点了，依据nearest更新C1到其余未拜访的点的间隔 visited[nearest] = true; for(int j=0;j<N;++j){ if(!visited[j]&&G[nearest][j]!=0){ if(dis[j]>dis[nearest]+G[nearest][j]){ dis[j] = dis[nearest]+G[nearest][j]; num[j] = num[nearest]; rescue_teams[j] = rescue_teams[nearest] + node_weight[j]; } else if(dis[j]==dis[nearest]+G[nearest][j]){ // 门路长度雷同，然而携带的救济团队更多 num[j] += num[nearest]; if(rescue_teams[j]<rescue_teams[nearest]+node_weight[j]){ rescue_teams[j] = rescue_teams[nearest] + node_weight[j]; } } } } }}int main(){ scanf("%d %d %d %d",&N,&M,&C1,&C2); for (int i = 0; i < N; ++i) { scanf("%d",&node_weight[i]); } for(int i=0;i<M;++i){ int a,b,length; scanf("%d %d %d",&a,&b,&length); G[a][b] = G[b][a] = length; } Dijkstra(); printf("%d %d",num[C2],rescue_teams[C2]); return 0;}

题目粗心：给出若干人之间的通话长度,依照这些通话将他们分成若干个组。当初给定一个犯罪团伙，而该组内点权最大的人视为喽罗。要求输入犯罪团伙的个数,并且依照喽罗姓名字典序从小到大的程序输入每个犯罪团伙的喽罗姓名和成员个数。 算法思路：这道题的题意得先了解分明, In each gang, the one with maximum total weight is the head.这句话的意思是$maximum$ $total$ $weight$的点为$head$,然而$weight$在题目中是边权,所以这里针对题目的案例进行手动绘图和假如后,比拟正当的解释就是一个点的$total$ $weight$指的是该点出边和入边的边权的和。并且依据语义来说，该图应该是一个无向图，因为通话是建设单方的连贯. 接下来咱们要晓得咱们须要取得那些信息能够求解这些问题,以及通过什么形式取得这些数据,题目要求输入每个犯罪团伙的喽罗姓名和成员个数,首先犯罪团伙的定义是一个团伙(连通重量)其人数大于2并且总边权的和大于K,而后头目标定义是组内点权最大的人视为喽罗,那么咱们要取得信息如下： 1)组内的人数(连通重量的结点个数) 2)组内的通话时间总和(连通重量的总边权) 3)组内通话时间最长的人(连通重量中点权最大的结点编号)当初晓得了须要取得下面3条信息后,就得晓得如何取得3条信息,这些信息都与连通重量无关,在图中咱们取得每个结点或者连通重量信息的办法就是遍历,这里应用了DFS。 在进行DFS遍历之前得先对数据进行预处理:输出的名字是字符串,咱们遍历的是结点编号,同时输入的时候也是字符串,那么得建设名字--->结点编号,结点编号----->名字的双向映射,这里应用unordered_map<int,string> indexToName存储编号到姓名的映射，unordered_map<string,int> nameToIndex存储姓名到编号的映射，具体的做法就是先应用numPerson=0示意以后已知结点的个数,同时也是新退出图中的结点的编号，在每次输出数据的时候先判断以后人的名字是否呈现过,如果没有呈现就建设名字和结点编号的映射和编号和名字的反映射，否则就取出该名字的编号，紧接着就依据编号，累计点权和边权。DFS遍历过程：每一次DFS须要取得以上3条信息并且每次遍历一个连通重量,咱们设置参数start,number,total_time,head别离代表以后拜访结点,以后连通重量的结点个数,边权总和和最大点权的编号,每次拜访结点就累加连通重量的结点个数++number，并且判断以后结点的点权和head的点权哪个更大,如果以后结点更大，更新head，而后再遍历其邻接点,这里有个留神点,因为有可能是有环的图,所以为了计算总边权,咱们先累加以后结点和邻接点的边权,而后再判断邻接点是否能够拜访。并且每一条边只能拜访一次，所以在每次拜访后，就将该条边进行赋值为0，这样保障在反复拜访的时候总边权计算不会出错，之所以先累计边权，看下图即可： 接下来可就是遍历整个图形取得所有连通重量的那3个信息,对于每一个顶点只有没有拜访就调用DFS拜访该连通重量,而后将取得的信息进行解决,只有number>2&&total_time>K阐明是犯罪团伙,那么记录犯罪团伙的喽罗和人数,这里采纳map<string,int> result记录，因为能够主动排序,具体操作为result[indexToName[head]] = number;最初依照要求输入即可 留神点;1.测试点3呈现段谬误,起因在于数组开的太小了,n条边最多有2*n个结点，至多开到2000以上2.没有排序测试点2和5谬误3、没有思考到一个团伙有2个点权一样大输入字典序小的测试点5谬误,间接在遍历图的时候依照结点编号从小到大进行遍历就能够防止4、题目说A name is a string of three capital letters chosen from A-Z，并不是名字都是AAA,BBB这种3个字母都一样的名字,只不过样例给的是这样的,有误导作用,不然只能过2个测试点(不要问我是怎么晓得的，(╥╯^╰╥)) ，所以应用从0开始顺次递增赋值编号是最不便的，字符串hash这里不太实用，容易超内存。提交后果: 很多网上的代码只能通过PAT的测试点,无奈通过牛客网的测试,自己提供的代码,均能通过.AC代码：#include <cstdio>#include <vector>#include <iostream>#include <unordered_map>#include <map>using namespace std;int N,K;//边数和阈值bool visited[2000];//拜访标记数组int G[2000][2000];// 邻接矩阵，其值为边权int node_weight[2000];// 点权unordered_map<int,string> indexToName;// 存储编号到姓名的映射unordered_map<string,int> nameToIndex;// 存储姓名到编号的映射map<string,int> result;// 每一个gang的head和人数汇合int numPerson = 0;//总人数void DFS(int start,int &number,int &total_time,int &head){ visited[start] = true;// 拜访该节点 ++number;// 以后连通重量节点数目加一 if(node_weight[head]<node_weight[start]){ // 更新head head = start; } // 遍历每一个领接点 for(int i=0;i<numPerson;++i){ if(G[start][i]!=0){ // i是start的领接点 total_time += G[start][i];// 先累计总时长,为了防止出现环的时候少拜访一条边 // start->i的边只能拜访一遍,得置为0，避免反复计算影响后果 G[start][i] = G[i][start] = 0; if(!visited[i]){ DFS(i,number,total_time,head); } } }}void DFSTraverse(){ for (int i = 0; i < numPerson; ++i) { if(!visited[i]){ int number = 0;// 每一个gang的人数 int total_time = 0;// 每一个gang的总通话时长 int head = i;// 每一个gang的head,初始得是以后拜访连通块中的点，不能是0 DFS(i,number,total_time,head); if(number>2&&total_time>K){ // 以后连通重量是一个gang result[indexToName[head]] = number; } } } printf("%lu\n",result.size()); map<string,int>::iterator it; for(it=result.begin();it!=result.end();++it){ printf("%s %d\n",it->first.c_str(),it->second); }}int main(){ scanf("%d %d",&N,&K); string a,b; int time,index_a,index_b; for (int i = 0; i < N; ++i) { cin>>a>>b>>time; if(nameToIndex.find(a)==nameToIndex.end()){ // 第一次呈现,赋予编号 index_a = numPerson++; nameToIndex[a] = index_a; indexToName[index_a] = a; } else { // 不是第一次呈现，取出编号 index_a = nameToIndex[a]; } if(nameToIndex.find(b)==nameToIndex.end()){ // 第一次呈现,赋予编号 index_b = numPerson++; nameToIndex[b] = index_b; indexToName[index_b] = b; } else { // 不是第一次呈现，取出编号 index_b = nameToIndex[b]; } // 边权 G[index_a][index_b] += time; G[index_b][index_a] += time; // 点权 node_weight[index_a] += time; node_weight[index_b] += time; } DFSTraverse(); return 0;}

题目粗心：在微博中，每个用户都可能被若干其余用户关注。而当该用户公布一条音讯时，关注他的人就能够看到这条信息并且抉择是否转发它，且转发的音讯也能够被关注他的人再次转发,然而同一用户最多转发该信息一次(信息的最后发布者不能转发该音讯),当初给出N个用户的关注状况以及一个转发层数下限L，并给出最后公布音讯的用户编号，求在转发层数下限内音讯最多会被多少用户转发 算法思路：首先得了解题意 assuming that only L levels of indirect followers are counted.这里的$indirect$ $followers$指的是除了发布者以外的关注他的人,而不是在所有关注者中除了第一个关注者之外的人 calculate the maximum potential amount of forwards for any specific user这句话指的是计算L层内的所有不同的人有多少个,$potential$ $ amount$就是可能转发的意思，其实就是以发布者为核心的L层内的总人数,对于人A有关注A的人B存在,那么A公布的微博B是能够看的到的,那么就存在一条微博传递门路$A->B$,对于输出中$user[i]$和$userlist[i]$实际上是$user[i]$关注了$userlist[i]$,所以有一条$userlist[i]->user[i]$的微博传递门路。 在了解题意后很分明的晓得咱们要求的是在发布者为核心流传L层内的所有人数,很天然就联想到广度优先遍历的办法求解此题。为了不便的记录每一个节点的层数从而统计L层内的人数，咱们建设构造体Node将人员的编号和层数进行绑定，而后在广度优先遍历的时候，每次出队的时候，只有出队节点的层数大于L，间接退出循环，否则就统计除了自己的转发人数。 留神点：1、应用DFS最初一个测试点会超时。2、每一个人只能转发一次，须要去重，能够应用$unordered$_$set$解决，这里应用了入队标记数组。3、每次查问须要初始化$visited$4、存储数组大小得开到1001以上否则最初一组测试点呈现运行时谬误。提交后果： AC代码：#include <cstdio>#include <vector>#include <queue>#include <cstring>using namespace std;struct Node{ int index; int level;};int N,L;//总人数，层数vector<int> G[1001];// 设置为1000会导致测试点4运行时谬误bool visited[1001];// 入队标记数组void BFS(int start){ queue<Node> q; q.push(Node{start,0}); int count = 0;// 统计L层内的人数 visited[start] = true; while(!q.empty()){ Node top = q.front(); q.pop(); if(top.level>L){ break; } else { // 不统计本人 if(top.index!=start) ++count; for(int i=0;i<G[top.index].size();++i){ int next = G[top.index][i]; if(!visited[next]){ visited[next] = true; q.push(Node{next,top.level+1}); } } } } printf("%d\n",count);}int main(){ scanf("%d %d",&N,&L); int num,followed; for (int i = 1; i <= N; ++i) { scanf("%d",&num); for (int j = 0; j < num; ++j) { scanf("%d",&followed); G[followed].push_back(i); } } int K,user; scanf("%d",&K); // K个查问 for(int i=0;i<K;++i){ scanf("%d",&user); memset(visited,0, sizeof(visited)); BFS(user); } return 0;}

题目粗心：给定N座城市,其中有M条边是相连的,如果有其中一个城市被敌人霸占的话,求出须要连贯多少条边让剩下的城市连通. 算法思路:该城市的数据结构很显然是一个图的构造,那么咱们如果将一个顶点去除后，剩下来的顶点会组成若干个连通重量,那么要让这剩下来的结点全副连接起来变成一个图，那么就等价于将若干个连通重量连接成一个连通重量,咱们晓得2个连通重量只须要在这2个连通重量别离取出一个顶点而后相连就变成了一个连通重量,所以须要连贯的边数就是若干连通重量减一的个数。统计连通重量的个数的形式就是在每次DFS完结后累加就好。应用惯例的DFS代码就能够解决了。 留神点：1、不必真正的删除数据节点，不然有可能超时，间接应用一个变量$occupied$保留，在遍历的时候不要拜访就好。2、每一次查问都得初始化$visited$数组，不然后果谬误。3、无向图得存储两边的数据，也就是得初始化$G[a][b] = G[b][a] = 1;$提交后果： AC代码：#include <cstdio>#include <cstring>using namespace std;int G[1005][1005] = {};//邻接矩阵int occupied;// 待攻占的城市bool visited[1005] = {};//拜访标记数组int N,M,K;// 城市数目，门路条数，攻占的城市void DFS(int start){ visited[start] = true; for (int i = 1; i <= N; ++i) { if(G[start][i]!=0&&i!=occupied&&!visited[i]){ // 拜访所有与start连通，没有被攻占，并且没有被拜访的节点 DFS(i); } }}void DFSTraverse(){ int connected_component_count = 0; for (int i = 1; i <= N; ++i) { if(!visited[i]&&i!=occupied){// i不能是被攻占节点 DFS(i); ++connected_component_count; } } printf("%d\n",connected_component_count-1);}int main(){ scanf("%d %d %d",&N,&M,&K); int a,b; for (int i = 0; i < M; ++i) { scanf("%d %d",&a,&b); G[a][b] = G[b][a] = 1; } for (int j = 0; j < K; ++j) { scanf("%d",&occupied); memset(visited,0, sizeof(visited)); DFSTraverse(); } return 0;}

题目粗心：给定一个待排序序列和排序若干次的序列,要求判断是失去指标序列是通过插入排序还是堆排序,而后在输入再排序一次后的序列即可。 算法思路：这里考查的就是插入排序和堆排序的残缺排序的过程，循序渐进的来就好。 插入排序：首先将序列划分为有序序列局部和无序序列局部，初始有序序列为序列中第一个元素，对于长度为N的序列，插入排序会通过N-1趟排序，实现将N-1个无序序列的元素顺次插入到有序序列之中，那么能够看到，插入排序分为内部循环管制趟数，外部循环负责找到插入地位，每次循环应用t暂存待插入元素，而后在$[1,j]$(有序序列)中查问待插入地位loc,只有$t>=temp[j]$，阐明找到插入地位$j+1$，退出内层循环，将$j+1$地位的元素赋值为t即可。 堆排序：因为指标序列是递增系列，那么咱们须要建设大根堆，咱们初始序列作为大根堆的层序遍历序列，而后从最初一个非叶子节点到根节点，顺次向下调整，只有孩子节点中有比当期父节点大的，就替换孩子节点和父节点，并且向下顺次递推查问，直到孩子节点的权重均比父节点小进行调整。这样就实现了初始大根堆的建设过程。堆排序就是将根节点和最初一个节点(未排序节点)进行替换，而后再向下调整根节点。这样就实现了一次堆排序的过程，每一次堆排序都会固定一个最大的元素在最初。 因为题目要求判断已排序局部的序列是插入排序还是堆排序的后果之上再进行一次排序，那么咱们应用$same$标记已排序的局部序列是否是由以后的排序算法失去的，如果在排序实现后，判断$same$为$true$，那么就阐明能够退出排序过程，进行相应的输入。如果$same$为$false$，那么就应用$isSame$函数更新$same$的值。 留神点：1、堆排序的根节点下标为1.2、插入排序的初始插入地位默认为1，是为了解决像3 1这种非凡状况。3、初始序列不参加和局部有序序列的比拟，肯定得先排序一次当前再比拟是否雷同。4、这里题目要求是指标朝着递增序列的方向排序,也即是最初的后果是从小到大,这里得留神堆排序是大根堆排序后才是递增序列,小根堆排序后是递加序列,因为每次都是从根节点和最初一个结点替换,最大(大根堆)或者最小(小根堆)的结点都在前面.提交后果： AC代码：#include <cstdio>#include <algorithm>using namespace std;int N;// 节点个数int init[105];//初始序列int temp[105];//暂存初始序列int partial_sorted[105];//局部排序序列bool isSame(){ for (int i = 1; i <= N; ++i) { if(temp[i]!=partial_sorted[i]){ return false; } } return true;}bool InsertionSort(){ bool same = false; // N-1轮排序 for (int i = 1; i < N; ++i) { int t = temp[i+1];//暂存待插入元素 int loc = 1;// 待插入地位,初始为1，思考3 1的非凡状况 for (int j = i; j >= 1; --j) { if(t<temp[j]){ temp[j+1] = temp[j]; } else { // 找到插入地位 loc = j+1; break; } } temp[loc] = t; if(same){ // 在相等的状况下，又排序了一次 break; } if(isSame()) same = true;//曾经雷同了，再排序一次 } return same;}// 调整[low,high]的节点权重,low从最初一个非叶节点开始始终到1，high为以后堆须要调整的最初一个元素void downAdjust(int low,int high){ int i = low; int j = 2*i;//i的左孩子 while (j<=high){ // 只有左孩子始终存在,就向下调整 if(j+1<=high&&temp[j+1]>temp[j]){ // 右孩子节点更小 j = j+1; } if(temp[j]>temp[i]){ // 孩子节点的值更小 swap(temp[j],temp[i]); i = j; j = 2*i; }else { // 孩子权重更加小，就进行比拟 break; } }}void createHeap(){ for(int i=N/2;i>=1;--i){ downAdjust(i,N); }}void print(){ for(int i=1;i<=N;++i){ printf("%d",temp[i]); if(i<N) printf(" "); }}void HeapSort(){ createHeap();//先建堆 // 将最初的节点和堆顶的节点替换，而后调整 bool same = false; for(int i=N;i>=1;--i){ swap(temp[i],temp[1]); downAdjust(1,i-1); if(same){ printf("Heap Sort\n"); print(); break; } if(isSame()){ same = true; } }}int main(){ scanf("%d",&N); for (int i = 1; i <= N; ++i) { scanf("%d",&init[i]); temp[i] = init[i]; } for (int i = 1; i <= N; ++i) { scanf("%d",&partial_sorted[i]); } if(InsertionSort()){ printf("Insertion Sort\n"); print(); } else { // 重置temp for (int i = 1; i <= N; ++i) { temp[i] = init[i]; } HeapSort(); } return 0;}

题目粗心：有N集体,如果任意2集体的喜好有雷同的(就是有交加),那么这2集体就是属于同一个社交网络,要求输入这N集体组成了几个社交网络,并且输入每个社交网络的人数 算法思路：此题考查的是并查集的应用(并查集次要用来解决 若干个节点，有些节点相互相连，有些节点没有连贯，如何判断其中两个节点是否相连这样的问题)，目前来看，应用并查集求解此题应该是最好的抉择，能够应用构建人与人的关系图，而后遍历有多少个连通重量，每一个连通重量有多少节点，然而这种形式实现起来过于简单。 并查集次要由1个汇合，2个操作所组成，汇合就是father保留每一个节点的父节点，2个操作别离是查问节点x的父亲节点和合并2个节点所在的汇合。入上面代码所示： int father[1005];// 每一个节点的父亲节点// 查问节点x的父亲节点int findFather(int x){ while(x!=father[x]){ x = father[x]; } return x;//father[x]==x的才是根节点}// 合并a和b节点所在的汇合void Union(int a,int b){ int fa = findFather(a); int fb = findFather(b); if(fa!=fb){ father[fa] = fb; }}在此题中，咱们须要构建一个人与人之间互相关联的社交网络，媒介是每一个人所领有的喜好，那么咱们应用$hobbyOwner$记录每一个喜好的所有者，这样在输出每一个喜好的时候，如果以后喜好没有所有者，将以后喜好标记为本人所独有，否则就将该喜好所有者和以后人合并到一个社交网络。在每一个社交网络构建实现后，咱们须要统计社交网络的个数和每一个社交网络的人数，咱们应用$roots(set汇合)$保留每一个社交网络的根节点，其个数即为社交网络的个数，$cluster$保留每一个社交网络的人数，具体做法就是，须要遍历每一个人，找到其根节点$root$，而后增加进$roots$中，并且统计以后社交网络的人数++cluster[root]。最初对cluster进行排序输入即可。 int cluster[1005];// 每一个社交网络的人数unordered_set<int> roots;// 保留每一个根节点// 统计社交网络的个数,也就是根节点的个数for (int k = 1; k <= N; ++k) { int root = findFather(k); ++cluster[root]; roots.insert(root);}留神点：1、有一种状况须要特地留神，如果当初曾经组建好了社交网络A和B，那么当初有一个人的喜好既有A又有B，那么他将作为连贯A和B的桥梁，须要将每一个人的所有喜好都要进行解决，并且因为合并后，只更新了一个社交网络的根节点的父亲，该社交网络的其余节点的父亲仍然没有变动，所以在统计社交网络的人数的时候不能间接应用father数组，肯定得从新遍历每一个节点获取其父亲，否则测试点1，4，5会谬误。提交后果： AC代码：#include <cstdio>#include <unordered_map>#include <unordered_set>#include <algorithm>using namespace std;int father[1005];// 每一个节点的父亲节点unordered_map<int,int> hobbyOwner;//每一个喜好的所有者int cluster[1005];// 每一个社交网络的人数// 初始化每一个节点的父亲void init(){ for (int i = 1; i <= 1000; ++i) { father[i] = i; }}// 查问节点x的父亲节点int findFather(int x){ while(x!=father[x]){ x = father[x]; } return x;//father[x]==x的才是根节点}// 合并a和b节点所在的汇合void Union(int a,int b){ int fa = findFather(a); int fb = findFather(b); if(fa!=fb){ father[fa] = fb; }}bool cmp(int a,int b){ return a>b;}int main(){ init(); int N;// 节点个数 scanf("%d",&N); for (int i = 1; i <= N; ++i) { int K; scanf("%d: ",&K); for (int j = 0; j < K; ++j) { int hobby; scanf("%d",&hobby); if(hobbyOwner[hobby]==0){ // 以后喜好没有人领有 hobbyOwner[hobby] = i; } else { // 曾经领有了，合并拥有者和i Union(hobbyOwner[hobby],i); } } } unordered_set<int> roots;// 保留每一个根节点 // 统计社交网络的个数,也就是根节点的个数 for (int k = 1; k <= N; ++k) { int root = findFather(k); ++cluster[root]; roots.insert(root); } printf("%lu\n",roots.size()); sort(cluster+1,cluster+N+1,cmp); for(int i=1;i<=roots.size();++i){ printf("%d",cluster[i]); if(i<roots.size()) printf(" "); } return 0;}

题目粗心：给定一颗二叉查找树的构造和一些待插入数字,要求输入该二叉树的层序遍历序列 算法思路：道题和1064的思路是一样的,都是紧紧把握一条,就是利用给定的二叉树的信息取得中序遍历的结点的下标序列,对给定的待插入数字进行排序失去中序遍历的结点的数字序列,而后两者一一对应就能够将该二叉查找树结构进去。这里因为输出的是结点的编号,那么用二叉树的动态存储办法比拟不便,应用in数组保留结点中序遍历的编号序列。在输出结束后,对二叉树进行中序遍历,根节点为0,将in数组中的数字依照遍历程序顺次填入到二叉树中，就能够实现二叉树的构建，而后再进行层序遍历并进行输入即可。 提交后果： AC代码：#include<cstdio>#include<queue>#include<algorithm>using namespace std;struct Node{ int data; int left; int right;}node[105];int N;int in[105];//中序遍历序列 int inIndex = 0;//中序序列工作指针 void preTraverse(int root){ if(root==-1) return; preTraverse(node[root].left); node[root].data = in[inIndex++]; preTraverse(node[root].right);}int num=0;//管制空格的输入 void levelTraverse(int root){ queue<int> q; q.push(root); while(!q.empty()){ int t = q.front(); q.pop(); printf("%d",node[t].data); if(num<N-1) printf(" "); ++num; if(node[t].left!=-1){ q.push(node[t].left); } if(node[t].right!=-1){ q.push(node[t].right); } }}int main(){ scanf("%d",&N); for(int i=0;i<N;++i){ scanf("%d %d",&node[i].left,&node[i].right); } for(int i=0;i<N;++i){ scanf("%d",&in[i]); } sort(in,in+N); preTraverse(0); levelTraverse(0); return 0;}

题目粗心：给定N个结点的CBT的每一个结点的值,要求输入对应的层序遍历序列 算法思路：首先明确CBT的概念,这里要求每一次尽可能的满,除了最初一层,这里的定义合乎齐全二叉树,那么咱们能够对这颗齐全二叉树依照档次遍历序列进行编号,这样便于输入层序遍历序列(可能当初还不明确,看到前面就好了),为了不便轻松取得左孩子和右孩子咱们应用1来代表根节点的编号.而后对于给定结点数量N的齐全二叉树,其档次序列的编号是固定的就是1,2,3...n,那么咱们从1到n进行遍历,对于每一个结点i如果有左孩子$2*i<=n$,那么就更新左孩子编号$node[i].left = 2*i$,如果有右孩子$2*i+1<=n$,那么就更新右孩子编号$node[i].right = 2*i+1$,并且初始化所有结点的左右孩子都为-1。接下来就是建树的过程，也是此题惟一的难点，咱们晓得二叉搜寻树的中序遍历序列(数值)是有序的，那么咱们将输出序列进行排序就能够失去中序遍历序列(数值)，同样的，咱们把存储该树的动态数组的下标也进行排序，这样就失去了中序遍历序列数组的下标和数值，将它们一一对应就能够取得这颗树了，可能当初还是不太明确，看下图就好了。其次要操作就是应用了一个num数组存储输出的数据，对其进行排序后就是中序遍历序列，而后咱们将一颗空树进行中序遍历，而后将值一一填入到结点中，就实现了树的创立。仔细观察就晓得，CBT的层序遍历实际上就是动态数组依照程序顺次输入的后果。 提交后果： AC代码：#include<cstdio>#include<queue>#include<algorithm>using namespace std;int N;int num[1005];struct Node{ int data; int left; int right; Node(){ left = right = -1; }}node[1005];int index = 1;// 中序序列指针 void inTraverse(int root){ if(root==-1) return; inTraverse(node[root].left); node[root].data = num[index++]; inTraverse(node[root].right);}int main(){ scanf("%d",&N); for(int i=1;i<=N;++i){ scanf("%d",&num[i]); if(2*i<=N){ // 有左孩子 node[i].left = 2*i; } if(2*i+1<=N){ // 有右孩子 node[i].right = 2*i+1; } } // 将num数组进行排序取得树的中序遍历序列 sort(num+1,num+N+1); // 中序遍历node，将num数组插入其中,根节点默认为1 inTraverse(1); // 输入层序遍历序列 for(int i=1;i<=N;++i){ printf("%d",node[i].data); if(i<N) printf(" "); } return 0;}

题目粗心：现给定一颗N个结点的树,判断该树是否是二叉查找树或者镜像二叉查找树,如果是输入YES并输入该树的后序遍历,否则输入NO 算法思路：咱们首先通过给定的N个结点间接构建一个二叉查找树，而后再取得其先序遍历序列和镜像先序遍历序列，别离判断是否和输出的序列相等，如果输出的序列是先序遍历序列，那么就输入YES并取得其后序遍历序列进行输入，如果输出序列是镜像先序遍历序列，那么就输入YES并取得镜像后序遍历序列进行输入，如果都不是，就输入NO。 构建二叉查找树：这里采纳间接模仿手工构建二叉查找树的过程，首先是依据插入的数据值，新建一个叶子结点，而后从根节点进行查找，如果根节点为空，阐明曾经找到插入地位，将根结点赋值为以后叶子结点即可，如果根节点的数据值小于叶子结点数据值，递归向左子树插入该结点，否则递归向右子树插入该结点。代码如下： struct Node{ int data; struct Node* left; struct Node* right;};// 创立结点 Node* newNode(int data){ Node* node = new Node(); node->data = data; node->left = node->right = nullptr; return node;}// 插入结点到root中 void insert(Node* &root,int data){ if(root==nullptr){ // 查找到插入地位 root = newNode(data); return; } if(root->data>data){ // 在左子树中查找插入地位 insert(root->left,data); }else{ // 在右子树中查找插入地位 insert(root->right,data); }}// 建树 for(int i=0;i<N;++i){ scanf("%d",&num[i]); insert(root,num[i]);}留神点：1、当输出序列为镜像先序查找树的时候，其后序序列为镜像后序序列，样例2就是该状况。提交后果： AC代码：#include<cstdio>#include<vector>using namespace std;struct Node{ int data; struct Node* left; struct Node* right;};int N;int num[1001];// 存储输出序列vector<int> pre,mirrorPre,post,postMirror;// 先序，先序镜像先序，后序序列 ,后序镜像序列 // 创立结点 Node* newNode(int data){ Node* node = new Node(); node->data = data; node->left = node->right = nullptr; return node;}// 插入结点到root中 void insert(Node* &root,int data){ if(root==nullptr){ // 查找到插入地位 root = newNode(data); return; } if(root->data>data){ // 在左子树中查找插入地位 insert(root->left,data); }else{ // 在右子树中查找插入地位 insert(root->right,data); }}void preTraverse(Node* root){ if(root==nullptr) return; pre.push_back(root->data); preTraverse(root->left); preTraverse(root->right);}void preMirrotTraverse(Node* root){ if(root==nullptr) return; mirrorPre.push_back(root->data); preMirrotTraverse(root->right); preMirrotTraverse(root->left);}void postTraverse(Node* root){ if(root==nullptr) return; postTraverse(root->left); postTraverse(root->right); post.push_back(root->data);}void postMirrorTraverse(Node* root){ if(root==nullptr) return; postMirrorTraverse(root->right); postMirrorTraverse(root->left); postMirror.push_back(root->data);}// 判断输出序列是否是先序序列bool isPre(){ for(int i=0;i<N;++i){ if(pre[i]!=num[i]){ return false; } } return true;}// 判断输出序列是否是先序镜像序列bool isPreMirror(){ for(int i=0;i<N;++i){ if(mirrorPre[i]!=num[i]){ return false; } } return true;}int main(){ scanf("%d",&N); Node* root = nullptr; // 建树 for(int i=0;i<N;++i){ scanf("%d",&num[i]); insert(root,num[i]); } preTraverse(root); preMirrotTraverse(root); if(isPre()){ // 是先序序列 printf("YES\n"); postTraverse(root); for(int i=0;i<N;++i){ printf("%d",post[i]); if(i<N-1) printf(" "); } }else if(isPreMirror()){ // 是先序镜像序列 printf("YES\n"); postMirrorTraverse(root); for(int i=0;i<N;++i){ printf("%d",postMirror[i]); if(i<N-1) printf(" "); } }else { printf("NO"); } return 0;}在这里再给出间接建设BST和镜像BST的写法#include<cstdio>#include<cstring>#include<vector>#include<iostream>using namespace std;/*题目要求:现给定一颗N个结点的树,判断该树是否是二叉查找树或者镜像二叉查找树,如果是输入YES并输入该树的后序遍历,否则输入NO 算法思路:因为得输入对应的后序遍历序列,那么就得构建这颗树了,因为有可能有2种合乎题意的树,咱们采纳2次先判断再建设树的形式.1.首先咱们先判断该树是否是BST：这里采纳的是利用先序遍历序列构建BST的过程判断是否是BST的,在以后递归体中,咱们用index保留第一个大于等于根节点的地位,因为根节点前面到index地位都小于根节点,所以只需判断前面index到完结地位是否满足BST的定义就好,也就是说如果右子树中有小于根节点的结点,那么让flag=false(flag是用来判断该树是否是BST的标记),并且return进行递归,如果右子树结点均合乎定义则进行左子树和右子树的递归即可2.如果该树是BST,就构建BST,构建BST树的过程和判断极为类似,咱们在进入递归的时候首先初始化根节点Node* root = new Node;root->data = pre[preL];同样的咱们用index保留第一个大于等于根节点的地位,区间[preL+1,index-1]就是左子树,区间[index,preR]就是右子树,而后顺次构建左子树root->left = create(preL+1,index-1),右子树root->right = create(index,preR),最初返回根结点root即可3.如果该树不是BST,就判断是否是镜像BST,这里只需将index改为保留第一个小于根节点的地位即可,而后在右子树中有大于等于根节点的结点,如果有,那么让flag=false，并且return,如果右子树结点均合乎定义则进行左子树和右子树的递归即可4.如果是镜像BST,则构建镜像BST树,这里与构建BST惟一的区别就是找到第一个小于根节点的地位index,而后左右区间均一样,递归建设树即可5.如果都不是则输入NO6.最初得记得输入后序序列postOrder */const int maxn = 1001;//最多结点数目 struct Node{ int data; Node* left; Node* right;}node[maxn];int pre[maxn];//前序和后序序列 int n;//结点个数 void isBST(int preL,int preR,bool &flag){//依据先序遍历判断该树是否是BST if(preL>preR) return; int index;//保留第一个大于等于根节点的地位 for(index=preL+1;index<=preR;++index){ if(pre[index]>=pre[preL]){ break; } } for(int i=index;i<=preR;++i){ if(pre[i]<pre[preL]){//右子树中有小于根节点的结点 flag = false; return; } } isBST(preL+1,index-1,flag); isBST(index,preR,flag);}void isMirrorBST(int preL,int preR,bool &flag){//依据先序遍历判断该树是否是镜像BST if(preL>preR) return; int index;//保留第一个小于根节点的地位 for(index=preL+1;index<=preR;++index){ if(pre[index]<pre[preL]){ break; } } for(int i=index;i<=preR;++i){ if(pre[i]>=pre[preL]){//右子树中有大于等于根节点的结点 flag = false; return; } } isMirrorBST(preL+1,index-1,flag); isMirrorBST(index,preR,flag);}Node* create(int preL,int preR){//依据先序遍历建设BST if(preL>preR) return NULL; Node* root = new Node; root->data = pre[preL]; root->left = root->right = NULL; int index;//保留第一个大于等于根节点的地位 for(index=preL+1;index<=preR;++index){ if(pre[index]>=root->data){ break; } } root->left = create(preL+1,index-1); root->right = create(index,preR); return root;}Node* createMirror(int preL,int preR){//依据先序遍历建设镜像BST if(preL>preR) return NULL; Node* root = new Node; root->data = pre[preL]; root->left = root->right = NULL; int index;//保留第一个小于根节点的地位 for(index=preL+1;index<=preR;++index){ if(pre[index]<root->data){ break; } } root->left = createMirror(preL+1,index-1); root->right = createMirror(index,preR); return root;}int num = 0;//用来统计输入节点个数并管制输入空格 void postOrder(Node *root){//后序遍历二叉树,并输入后序遍历序列 if(root==NULL) return; postOrder(root->left); postOrder(root->right); printf("%d",root->data); if(num<n-1) printf(" "); ++num; }int main(){ scanf("%d",&n); for(int i=0;i<n;++i){ scanf("%d",&pre[i]); } bool flag1 = true; bool flag2 = true; isBST(0,n-1,flag1); isMirrorBST(0,n-1,flag2); if(flag1||flag2){ printf("YES\n"); Node *root; if(flag1){//阐明是BST root = create(0,n-1); }else{ root = createMirror(0,n-1); } postOrder(root); }else{ printf("NO\n"); } return 0;}

题目粗心：给定一颗树和每个结点的权值,求从所有根结点到叶子结点的门路,使得每条门路上的权值之和等于给定的常数S.如果有多条门路,依照门路的非递增序列输入 算法思路：考查树的遍历，因为需要求从所有根结点到叶子结点的门路，很天然就想到应用先序遍历该树，并且应用$path$保留以后搜寻门路，$result$保留所有符合条件的门路，如果以后结点是叶子结点，那么就先将此结点增加到$path$中，而后再计算$path$总所有结点的总权重，如果和给定的S相等，那么就将$path$增加进$result$中。接着得回退，先将叶子结点退出$path$，而后再返回。如果当期结点不是叶子结点，那么就先将以后结点增加进$path$中，而后再递归遍历其每一个孩子结点，在每一个孩子都遍历结束后就将当期结点退出$path$，这样就实现了整个树的搜寻过程。搜寻完结后，$result$就保留了所有满足条件的门路，接着就是将$result$的每一条门路序列依照字典序从大到小排序，最初再输入即可。 留神点：1、在不排序的状况下，能够取得10分，测试点0和2谬误。2、测试点2的谬误和测试点5的段谬误均是因为排序函数的问题，首先得留神是对权值排序，不是结点的ID(这个很容易搞错)，而后就是对于两个序列的正反比拟逻辑都得写，也就是对于同一个地位i，a[i]>b[i]和a[i]<b[i]的返回值都得明确写进去，并且，对于所有的齐全一样的序列，也得做解决，否则测试点5呈现段谬误，总结一点就是排序函数得对所有的可能状况作出解决。提交后果： AC代码：#include<cstdio>#include<vector>#include<algorithm>using namespace std;struct Node{ int weight; vector<int> child;}node[110];vector<int> path;//以后搜寻门路vector<vector<int> > result;//所有满足条件的解bool cmp(vector<int> a,vector<int> b){ int len = min(a.size(),b.size()); for(int i=0;i<len;++i){ if(node[a[i]].weight>node[b[i]].weight){ return true; }else if(node[a[i]].weight<node[b[i]].weight){//这个不写会呈现测试点2谬误 return false; } } return a.size()>b.size();// 不写这个呈现段谬误 }void preTraverse(int root,int weight){ if(node[root].child.empty()){ // 叶子结点 path.push_back(root); // 计算以后门路的权值 int sum = 0; for(int i=0;i<path.size();++i){ sum += node[path[i]].weight; } if(sum==weight){ result.push_back(path); } //回退 path.pop_back(); return ; } //抉择以后结点 path.push_back(root); for(int i=0;i<node[root].child.size();++i){ preTraverse(node[root].child[i],weight); } path.pop_back();}int main(){ int N,M,S;//结点总数，非叶结点总数 ,待查问权值 scanf("%d %d %d",&N,&M,&S); for(int i=0;i<N;++i){ scanf("%d",&node[i].weight); } int ID,K; for(int i=0;i<M;++i){ scanf("%d %d",&ID,&K); int child; for(int j=0;j<K;++j){ scanf("%d",&child); node[ID].child.push_back(child); } } preTraverse(0,S); // 依照字典序逆序输入result的序列 sort(result.begin(),result.end(),cmp); for(int i=0;i<result.size();++i){ for(int j=0;j<result[i].size();++j){ printf("%d",node[result[i][j]].weight); if(j<result[i].size()-1) printf(" "); } printf("\n"); } return 0;}

题目粗心：给定一颗树,要求求出每一层叶子结点的数目 算法思路：间接遍历这颗树，在遇到叶子节点的时候，就统计以后档次下的叶子节点的个数，这里应用num_leaves_per_level保留每一层叶子节点的数目。遍历完结后，间接输入num_leaves_per_level数组即可。层序遍历代码如下： int num_leaves_per_level[101];//每一层叶子节点的数目int layer = -1;//层数void levelTraverse(int root){ queue<int> q; node[root].level = 1; q.push(root); while (!q.empty()){ int t = q.front(); q.pop(); if(layer<node[t].level){ layer = node[t].level; } if(node[t].child.empty()){ // 叶子节点 ++num_leaves_per_level[node[t].level]; } else {// 这里得进行判断，不然会死循环 for(auto &item:node[t].child){ node[item].level = node[t].level+1; q.push(item); } } }}留神点：层序遍历的时候每次入队都是之前出队的节点。否则会有测试点内存超限和超时。提交后果： AC代码：#include <cstdio>#include <vector>#include <queue>using namespace std;struct Node{ vector<int> child; int level;}node[101];int num_leaves_per_level[101];//每一层叶子节点的数目int layer = -1;//层数void levelTraverse(int root){ queue<int> q; node[root].level = 1; q.push(root); while (!q.empty()){ int t = q.front(); q.pop(); if(layer<node[t].level){ layer = node[t].level; } if(node[t].child.empty()){ // 叶子节点 ++num_leaves_per_level[node[t].level]; } else {// 这里得进行判断，不然会死循环 for(auto &item:node[t].child){ node[item].level = node[t].level+1; q.push(item); } } }}int main(){ int N,M;//节点总数和非叶节点个数 scanf("%d %d",&N,&M); if(N==0) return 0; int ID,K; for (int i = 0; i < M; ++i) { scanf("%d %d",&ID,&K); if(K!=0){ // 非叶子节点 for (int j = 0; j < K; ++j) { int child; scanf("%d",&child); node[ID].child.push_back(child); } } } levelTraverse(1); for (int k = 1; k <= layer; ++k) { printf("%d",num_leaves_per_level[k]); if(k<layer) printf(" "); } return 0;}

题目粗心：给出一颗销售供给树,根结点为0,在树根处售价为P,而后从根节点开始每往子节点走一层就,该层的货物的价格就会在上一层的价格上减少r%,要求取得叶子结点最低售价以及最低售价的个数。 算法思路：此题实质上考查的是树的遍历，该树是由供应商作为根节点，经销商作为子节点，零售商作为叶子节点组成。想要求叶子节点的最低售价及其个数，只需要求出叶子节点的售价，为此，咱们只须要从根节点遍历该树，计算所有节点的售价，这样在遍历到叶子节点的时候就能够间接统计最低售价及其个数。应用先序遍历或者层序遍历都是能够的，这里采纳了先序遍历的办法，代码如下所示： double lowestPrice = 10000000000.0;int numOflowestPrice = 0;void preTraverse(int root,double r){ if(node[root].child.empty()){ // 零售商，叶子节点 if(lowestPrice>node[root].price){ lowestPrice = node[root].price; numOflowestPrice = 1; } else if(lowestPrice==node[root].price){ ++numOflowestPrice; } } double distributorPrice = node[root].price*(1+r/100); for(auto &item:node[root].child){ node[item].price = distributorPrice; preTraverse(item,r); }}提交后果： AC代码：#include <cstdio>#include <vector>using namespace std;struct Node{ vector<int> child; double price;}node[100005];double lowestPrice = 10000000000.0;int numOflowestPrice = 0;void preTraverse(int root,double r){ if(node[root].child.empty()){ // 零售商，叶子节点 if(lowestPrice>node[root].price){ lowestPrice = node[root].price; numOflowestPrice = 1; } else if(lowestPrice==node[root].price){ ++numOflowestPrice; } } double distributorPrice = node[root].price*(1+r/100); for(auto &item:node[root].child){ node[item].price = distributorPrice; preTraverse(item,r); }}int main(){ int N; double P,r;//供应链总人数 scanf("%d %lf %lf",&N,&P,&r); for (int i = 0; i < N; ++i) { int K; scanf("%d",&K); if(i==0){ //供应商 node[i].price = P; } if(K!=0){ //经销商，非叶节点 int child; for (int j = 0; j < K; ++j) { scanf("%d",&child); node[i].child.push_back(child); } } } preTraverse(0,r); printf("%.4lf %d",lowestPrice,numOflowestPrice); return 0;}

题目粗心：输出树结点的个数N,非叶结点个数M,而后输出M个非叶节点的孩子结点,求结点个数最多的那层,输入该层的结点个数和层号. 算法思路：此题也是考查树的遍历，能够应用先序遍历或者层序遍历建设每一层和节点个数的关系，这里采纳了层序遍历，间接在出队节点的时候就先更新以后层的节点个数，而后更新最多节点数目和层数。对应代码如下： int largestGeneration = -1;// 最多节点数目int largestGenerationOfLevel;// largestGeneration对应的层数void levelTraverse(int root){ int levelNum[105] = {};//每一层的节点数目,肯定要初始化 queue<int> q; node[root].level = 1;// 第一层 q.push(root); while (!q.empty()){ int t = q.front(); q.pop(); ++levelNum[node[t].level]; if(largestGeneration<levelNum[node[t].level]){ largestGeneration = levelNum[node[t].level]; largestGenerationOfLevel = node[t].level; } for(auto &item:node[t].child){ node[item].level = node[t].level+1; q.push(item); } }}提交后果： AC代码：#include <cstdio>#include <vector>#include <queue>using namespace std;struct Node{ vector<int> child; int level;}node[1000];int largestGeneration = -1;// 最多节点数目int largestGenerationOfLevel;// largestGeneration对应的层数void levelTraverse(int root){ int levelNum[105] = {};//每一层的节点数目,肯定要初始化 queue<int> q; node[root].level = 1;// 第一层 q.push(root); while (!q.empty()){ int t = q.front(); q.pop(); ++levelNum[node[t].level]; if(largestGeneration<levelNum[node[t].level]){ largestGeneration = levelNum[node[t].level]; largestGenerationOfLevel = node[t].level; } for(auto &item:node[t].child){ node[item].level = node[t].level+1; q.push(item); } }}int main(){ int N,M;//供应链总人数 scanf("%d %d",&N,&M); int ID,K; for (int i = 0; i < M; ++i) { scanf("%d %d",&ID,&K); int child; for (int j = 0; j < K; ++j) { scanf("%d",&child); node[ID].child.push_back(child); } } levelTraverse(1); printf("%d %d",largestGeneration,largestGenerationOfLevel); return 0;}

题目粗心：给出一颗销售供给树,根结点为0,在树根处售价为P,而后从根节点开始,每一层的货物的价格就会在上一层的价格上减少r%,要求输入售价最高的零售商和其个数。 算法思路：此题和1079是一样的题目，采纳树的遍历(先序遍历或者层序遍历)获取所有节点的售价，在遍历到叶子节点的时候就更新最高售价和对应的零售商的个数。 因为给的是以后结点和其父亲的关系,所以每次输出parent的时候,就将其孩子结点增加其中node[parent].child.push_back(i),而后对于parent==-1的状况,应用root=parent,保留根节点地位 留神点：1、尽量不要应用float保留数据。提交后果： AC代码：#include <cstdio>#include <vector>using namespace std;struct Node{ double price;//以后结点的售价 vector<int> child;}node[100005];double highest_price = -1 ;// 最高售价int num;// 最高售价的零售商的个数void preTraverse(int root,double r){ if(node[root].child.empty()){ // 零售商，取得最高售价 if(highest_price<node[root].price){ num = 1; highest_price = node[root].price; } else if(highest_price==node[root].price){ ++num; } return; } double distributor_price = node[root].price*(1+r/100); for (auto &item:node[root].child){ node[item].price = distributor_price; preTraverse(item,r); }}int main(){ int N;//供应链总人数 double P,r;//供应商的单价，增量 scanf("%d %lf %lf",&N,&P,&r); int root,parent; for (int i = 0; i < N; ++i) { scanf("%d",&parent); if(parent==-1){ // 以后节点为根节点,保留地位和售价 root = i; node[i].price = P; } else { // 保留父子关系 node[parent].child.push_back(i); } } preTraverse(root,r); printf("%.2lf %d",highest_price,num); return 0;}

题目粗心：给出一颗销售供给树,根结点为0,在树根处售价为P,而后从根节点开始,每一层的货物的价格就会在上一层的价格上减少r%,给出每个叶结点的货物量,要求计算所有叶结点的销售总额。 算法思路：此题实质上考查的是树的遍历，该树是由供应商作为根节点，经销商作为子节点，零售商作为叶子节点组成。想要求叶子节点的销售总额，只需要求出叶子节点的售价，为此，咱们只须要从根节点遍历该树，计算所有节点的售价，这样在遍历到叶子节点的时候就能够间接累计总售价。应用先序遍历或者层序遍历都是能够的，这里采纳了先序遍历的办法，代码如下所示： double total_sales = 0 ;// 总售价void preTraverse(int root,double r){ if(node[root].child.empty()){ // 零售商，计算总售价 total_sales += node[root].price*node[root].total_amount; return; } double distributor_price = node[root].price*(1+r/100); for (auto &item:node[root].child){ node[item].price = distributor_price; preTraverse(item,r); }}留神点：1、应用float保留数据会有好几个点无奈通过。提交后果： AC代码：#include <cstdio>#include <vector>using namespace std;struct Node{ vector<int> child;//该结点的孩子 int total_amount;//叶子结点的货品数量 double price;//以后结点的售价}node[100005];double total_sales = 0 ;// 总售价void preTraverse(int root,double r){ if(node[root].child.empty()){ // 零售商，计算总售价 total_sales += node[root].price*node[root].total_amount; return; } double distributor_price = node[root].price*(1+r/100); for (auto &item:node[root].child){ node[item].price = distributor_price; preTraverse(item,r); }}int main(){ int N;//供应链总人数 double P,r;//供应商的单价，增量 scanf("%d %lf %lf",&N,&P,&r); int K,id; for (int i = 0; i < N; ++i) { scanf("%d",&K); if(i==0){ // 供应商 node[i].price = P; } if(K==0){ // 零售商 scanf("%d",&id); node[i].total_amount = id; } else { // 经销商和供应商 for (int j = 0; j < K; ++j) { scanf("%d",&id); node[i].child.push_back(id); } } } preTraverse(0,r); printf("%.1lf",total_sales); return 0;}

题目粗心：给定一个二叉树(编号从0到N-1),和每个结点的左右孩子编号,把该二叉树进行反转,而后输入反转二叉树的层序遍历和中序遍历 算法思路：这个题目有两种办法能够求解,一是依照题目要求间接将二叉树进行反转取得新的二叉树,而后再遍历。第二种就是不扭转二叉树,作镜像遍历,也即是之前先遍历左孩子,当初变成先遍历右孩子,毕竟只须要输入遍历的后果,就无需进行二叉树的反转,这里抉择用第二种,当然了,如果想要反转的话,间接应用后序遍历的办法,在最初拜访根节点的操作变动为替换其左右孩子节点即可($swap$函数就能够实现)。 取得根节点的办法：这里应用了一个标记数组$isNotRoot$标记下标为i的节点是否为根节点，不是就是$true$,初始默认都是根节点，在每输出一行数据的时候，就阐明以后的输出节点为其余节点的孩子节点，肯定不是根节点，就将$isNotRoot$置为$true$，而后在输出结束后，遍历$isNotRoot$查找为$false$的下标$i$即为$root$。(实际上是双亲表示法) 提交后果： AC代码：#include <cstdio>#include <string>#include <iostream>#include <queue>using namespace std;struct Node{ int data,left,right;};int N;// 节点个数int root;// 根节点编号bool isNotRoot[20];// 判断节点是否为根节点，不是就是true。Node tree[20];void levelTravese(){ queue<int> q; q.push(root); int num = 0; while (!q.empty()){ int top = q.front(); q.pop(); printf("%d",top); if(num<N-1) printf(" "); ++num; if(tree[top].right!=-1){ q.push(tree[top].right); } if(tree[top].left!=-1){ q.push(tree[top].left); } }}int num = 0;void inOrder(int r){ if(r==-1) return; inOrder(tree[r].right); printf("%d",r); if(num<N-1) printf(" "); ++num; inOrder(tree[r].left);}int main(){ scanf("%d",&N); string s1,s2; for (int i = 0; i < N; ++i) { cin>>s1>>s2; int left,right; tree[i].data = i; if(s1!="-"){ // 是数字 left = stoi(s1); isNotRoot[left] = true;// 为左孩子节点，肯定不是根节点 tree[i].left = left; } else { tree[i].left = -1; } if(s2!="-"){ // 是数字 right = stoi(s2); isNotRoot[right] = true;// 为左孩子节点，肯定不是根节点 tree[i].right = right; } else { tree[i].right = -1; } } // 找到根节点 for (int j = 0; j < N; ++j) { if(!isNotRoot[j]){ root = j; break; } } levelTravese(); printf("\n"); inOrder(root); return 0;}

题目粗心：用栈来模仿一颗二叉树的先序和中序遍历过程,求这课树的后序遍历序列。 算法思路:首先得说一个论断,就是栈的入栈序列就是一颗二叉树的先序遍历,出栈序列就是一颗二叉树的中序遍历序列,那么这个题目就转化为依据先序和中序求后序遍历序列。那么首先就是依据先序和中序建设二叉树，而后依据这个二叉树进行后序遍历取得后序遍历序列。 递归建设二叉树假如递归过程中某步的前序区间是$[beginPre,lastPre]$,中序区间是$[beginIn,lastIn]$,那么根节点为$pre[beginPre]$,首先初始化根节点$root$，接着须要在中序遍历中找到根节点的地位$index_root$,而后计算左子树的个数leftTreeLen = index_root-beginIn;这样左子树和右子树在后序和中序遍历中就离开了,紧接着就是左子树递归: root->left =createTree(beginPre+1,beginPre+leftTreeLen,beginIn,index_root-1);右子树递归: root->right = createTree(beginPre+leftTreeLen+1,lastPre,index_root+1,lastIn);递归的边界就是在区间长度小于0的时候间接返回空即可。 留神点：1、输出的行数为N的2倍。提交后果： AC代码：#include <stack>#include <string>#include <iostream>#include <vector>using namespace std;struct Node{ int data; Node* left; Node* right;};int N;// 节点个数vector<int> pre,In;Node* createTree(int beginPre,int lastPre,int beginIn,int lastIn){ if(beginPre>lastPre) return nullptr; // 初始化根节点 Node* root = new Node; root->data = pre[beginPre]; // 在中序序列 int index_root; for(index_root=beginIn;index_root<=lastIn;++index_root){ if(In[index_root]==root->data) break; } int leftTreeLen = index_root-beginIn; root->left = createTree(beginPre+1,beginPre+leftTreeLen,beginIn,index_root-1); root->right = createTree(beginPre+leftTreeLen+1,lastPre,index_root+1,lastIn); return root;}int num = 0;// 输入节点的个数，用来管制输入void postTraverse(Node* root){ if(root== nullptr) return; postTraverse(root->left); postTraverse(root->right); printf("%d",root->data); if(num<N-1) printf(" "); ++num;}int main(){ scanf("%d",&N); string s; int num; stack<int> st; // 输出的数据有2*N行 for (int i = 0; i < 2*N; ++i) { cin>>s; if(s=="Push"){ scanf(" %d",&num); st.push(num); pre.push_back(num); } else { num = st.top(); st.pop(); In.push_back(num); } } Node* root = createTree(0,N-1,0,N-1); postTraverse(root); return 0;}

题目粗心：给定一个二叉树的后序遍历和中序遍历,要求输入层序遍历 算法思路:首先由后序遍历和中序遍历构建此二叉树,而后层序遍历二叉树. 构建二叉树的思路：应用递归建设二叉树，假如递归过程中某步的后序区间是$[beginPost,lastPost]$,中序区间是$[beginIn,lastIn]$,那么根节点为$post[lastPost]$,首先初始化根节点$root$，接着须要在中序遍历中找到根节点的地位$index_root$,而后计算左子树的个数leftTreeLen = index_root-beginIn,这样左子树和右子树在后序和中序遍历中就离开了,紧接着就是左子树递归root->left = createTree(beginPost,beginPost+leftTreeLen-1,beginIn,index_root-1);右子树递归root->right = createTree(beginPost+leftTreeLen,lastPost-1,index_root+1,lastIn);递归的边界就是在区间长度小于0的时候间接返回空即可。 层序遍历的思路见代码：void leverTraverse(Node* root){ queue<Node*> q; int num = 0;//输入节点的个数，用来管制空格输入 q.push(root); while (!q.empty()){ Node* t = q.front(); q.pop(); printf("%d",t->data); if(num<N-1) printf(" "); ++num; if(t->left!=nullptr){ q.push(t->left); } if(t->right!=nullptr){ q.push(t->right); } }}留神点：1、应用数组in在本地编译器上可能无奈输出数据，CLion上无奈应用，DEV却能够。2、在子树递归的时候，左右子树的区间肯定得分清，不然会导致递归失败，什么都没有输入，并且还不报错。3、空格的输入须要应用一个变量num统计输入的个数，当num<N-1的时候就输入空格提交后果： AC代码：#include <cstdio>#include <queue>using namespace std;struct Node{ int data; Node* left; Node* right;};int N;// 节点个数int post[50],In[50];// 后序和中序遍历序列Node* createTree(int beginPost,int lastPost,int beginIn,int lastIn){ if(beginPost>lastPost){ return nullptr; } Node* root = new Node; root->data = post[lastPost]; // 首先找到根节点在中序序列的地位 int index_root; for (index_root = beginIn; index_root <= lastIn; ++index_root) { if(In[index_root]==root->data){ break; } } int leftTreeLen = index_root-beginIn;//左子树元素个数 root->left = createTree(beginPost,beginPost+leftTreeLen-1,beginIn,index_root-1); root->right = createTree(beginPost+leftTreeLen,lastPost-1,index_root+1,lastIn); return root;}void leverTraverse(Node* root){ queue<Node*> q; int num = 0;//输入节点的个数，用来管制空格输入 q.push(root); while (!q.empty()){ Node* t = q.front(); q.pop(); printf("%d",t->data); if(num<N-1) printf(" "); ++num; if(t->left!=nullptr){ q.push(t->left); } if(t->right!=nullptr){ q.push(t->right); } }}int main(){ scanf("%d",&N); for (int i = 0; i < N; ++i) { scanf("%d",&post[i]); } for (int j = 0; j < N; ++j) { scanf("%d",&In[j]); } Node* root = createTree(0,N-1,0,N-1); leverTraverse(root); return 0;}