Arrays类Arrays类是Java中用来操作数组的模块他的使用方法是在Java类中使用import java.util.Arrays进行导入，并使用Arrays.方法（）进行调用方法！Arrays类的fill方法fill方法有两种用途！第一种就是填充数组，将数组中的全部元素转换为所输入的元素第二种就是替换数组元素，将数组中某个元素进行单个替换用fill方法填充数组在初始化一个数组之后，如果没有给数组的元素赋值，那么这个数组中的元素默认是为0的，那么我们一个个进行赋值又会略显麻烦，会堆积代码！所以我们就需要用到fill方法进行填充，但是这么做会让全部元素变成同一个数值！import java.util.Arrays; //这里导入Arrays类public class Fill{public static void main(String[] args){int[] mylist = new int[5]; //这里创建一个名称为mylist的数组，数组的元素个个数为5Arrays.fill(mylist,3); //为数组填充3，格式为fill(列表,数值)for(int x:mylist){System.out.println(x);} //通过for each来遍历数组元素}}上面的for each在以前的文章中介绍过！用fill方法替换数组元素在给元素赋值完或者是填充完元素之后，如果想对某个元素进行修改，那么我们就要重新赋值或者是替换元素，但是重新赋值会增加代码，让代码显得更繁琐，所以Arrays类中提供了替换元素的方法fill！import java.util.Arrays;public class Fill{public static void main(String[] args){int[] mylist = {1,2,3,4};Arrays.fill(mylist, 1,2,4);for(int x:mylist){System.out.println(x);}} //这是一个特殊的格式Arrays.fill(列表名称,空格正向索引,反向索引,改变的数值）1}这里的正反向索引指向的一定要是同一个元素！Arrays类的复制数组方法在Java程序的使用过程中，有时候会需要一个含有相同或者是部分相同元素的数组，但是重新创建数组的话就会增加代码长度，减少代码可读性，那么我们就可以使用到复制数组或者是部分数组的方法！用copyOf复制数组☄️copyOf方法提供了多种重载的方法，用以复制数组，增加代码可读性。该方法不受数组长度的限制，若超出，则多处部分为0！import java.util.Arrays;public class Fill{public static void main(String[] args){int[] mylist = {1,2,3,4};int[] justlist = Arrays.copyOf(mylist,4); //将复制后的数组赋值给justlist//格式Arrays.copyOf(列表,复制后的长度)for(int x:justlist){System.out.println(x);}System.out.println(mylist);System.out.println(justlist); //这里输出两个数组的内存空间进行检查} //这是一个特殊的格式Arrays.fill(列表名称,空格正向索引,反向索引,改变的数值）1}解：从以上结果可以看出赋值成功了，并且内存空间不同（下面我会解释为什么要输出内存空间）用copyOfRange方法复制部分数组有时候在编辑代码的时候只需要中间一部分代码，但是copyOf方法只能复制以前面部分为开头的元素，而不能直接复制中间的代码，为了解决这一个问题，这个类提供了另一个方法copyOfRange方法（中文意思：选择复制）利用这个方法就可以解决这一个问题！import java.util.Arrays;public class Fill{public static void main(String[] args){int[] mylist = {1,2,3,4};int[] justlist = Arrays.copyOfRange(mylist,1,3);//Arrays类的方法使用形式Arrays.copyOfRange(列表,第一个索引位置,第二个索引位置)for(int x:justlist){System.out.println(x);}}}注：在末尾有问题解答！Arrays类对数组进行排序在代码编译过程中，有时候会需要用到有序的一组数组才能进行更好的操作，但是我们重新进行编译会增加代码数量，所以我们要对代码进行排序，Java中提供了sort方法对数组的元素进行升序排序！用sort方法进行升序排序在Java编译过程中，有顺序的数组会让你的编译更加方便，使得你自己以及其他参与编译的人更加清楚，尤其是适合那些大基数的数组更为适用和实用！import java.util.Arrays;public class Fill{public static void main(String[] args){    int[] mylist = {1,7,33,4};    Arrays.sort(mylist);    //方式为Arrays.sort(列表)    for(int x:mylist){        System.out.println(x);    }}}问题解答为什么要在fill方法中加空格：因为不加空格就会使他执行不正确，无法达到效果为什么要输出内存空间吗：如果在同一个内存空间，一个数组改变之后另一个也会随之改变，会影响后续程序执行copyOfRange方法如果超出索引最大限度会怎么样：如果超出，则超出部分默认为0！为什么有些要方法要创建新数组有些不用：因为有些方法是对一个数组进行改变，有些是要重新创建数组！————————————————版权声明：本文为CSDN博主「Code Writers」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/m0_71905144/article/details/126250825

首先来了解桶排序将数组分成若干类  分这个类的条件  我们自己决定这里我们用的是 每隔5个数分为一类如20~24  25~29 30~34...数组中的元素满足这样的条件就会被放在相应的桶中如: 23会被放在20~24的桶中假设我们有这样一个数组int arr[15] = { 34,36,31,78,65,32,33,34,89,90,91,67,52,71,77};我们决定桶的数量 为确保数组中的元素都能如桶   一般设定为  :原数组中的最大值-最小值+1 想判断当前数组元素应该入哪个桶  我们这里的条件是:当前元素的值-最小值/5   为他要入的桶的下标如  最小元素20 当前元素40  那么他要进去的桶的下标为 (40-20)/5=4我们这里所谓的桶  其实就是一个哈希数组 这里用的是链式存储法 (每一个元素都是一个链表的头)如相应的桶  就是 把元素添加到哈希数组的相应下标上的链表上去  在这里我们添加用的是链表插入的方式  直接根据节点的值将节点插入到相应的位置   完成排序 之后我们只需要 遍历哈希数组并遍历哈希数组元素  吧 哈希数组中的元素都放回到原数组中去这样就实现了桶排序桶排序完整代码如下#include<iostream>using namespace std;#define  jiange 5struct List{    int id;    List* pNext;}; void Insert(List*&pHead,int value){    List* pTemp=new List;    pTemp->id = value;    pTemp->pNext = NULL;    //链表中没有节点    if (pHead == NULL)    {        pHead = pTemp;        return;    }    //链表中的头节点比当前节点的值大      //头插入    if (pTemp->id < pHead->id)    {        pTemp->pNext=pHead;        pHead = pTemp;        return;    }    //链表的头的值比当前要插入的节点的值小    //遍历链表  找到要插在谁的后面            List* pMark = pHead;        while (pMark->pNext != NULL)        {            if (pMark->pNext->id > pTemp->id)            {                pTemp->pNext = pMark->pNext;                pMark->pNext = pTemp;                return;            }            pMark = pMark->pNext;        }        //遍历到最后一个节点  都没找到比当前节点大的节点  插在最后        pMark->pNext = pTemp;         }void BuckeSort(int arr[],int nLen){    int begin = arr[0];    int end =arr[0];    //参数校验    if (arr == NULL || nLen <= 10)    {        return;    }    //找到最大值和最小值确定桶的数量    for (int i = 0; i < nLen; i++)    {        if (arr[i] < begin)            begin = arr[i];        if (arr[i] > end)            end = arr[i];    }    int nBucketCount =  end -begin + 1;    //开辟空间    List** Hash = new List*[nBucketCount];    ::memset(Hash, 0, sizeof(List*)* nBucketCount);    //遍历数组入桶    for (int i = 0; i < nLen; i++)    {        //入桶函数        Insert(Hash[(arr[i]-begin)/jiange], arr[i]);    }    //出桶     int j = 0;    for (int i = 0; i < nBucketCount; i++)    {                while (Hash[i])        {            List* pDel = Hash[i];            Hash[i] = Hash[i]->pNext;             arr[j++] =pDel->id;            delete pDel;            pDel = NULL;                                }    }    delete Hash;    Hash = NULL;       } int main(){    int arr[15] = { 34,36,31,78,65,32,33,34,89,90,91,67,52,71,77};    BuckeSort(arr, 15);    for (int val : arr)    {        cout << val << " ";    }    return 0;}基数排序:可以看做是桶排序的另一种优化  只不过 他的如桶条件变了 而且需要额外创建一个记录链表的尾的哈希数组;  用于添加节点尾入  头出思想:先把数组中的元素根据个位入桶出桶放入原数组在把数组中的元素根据十位入桶出桶放入原数组...直到把数组中的元素根据  数组中的最大的元素的最高位  入桶出桶放入原数组   结束这样一来  数组自己就排序好了基数排序:代码如下#include<iostream>using namespace std;#define  jiange 5struct List{    int id;    List* pNext;}; void AddNode(List*& pHead, List*& pEnd ,int value){    List* pTemp = new List;    pTemp->id = value;    pTemp->pNext = NULL;    //链表中没有节点    if (pHead == NULL)    {        pHead = pTemp;            }    //链表有节点      //尾插入    else     {        pEnd->pNext = pTemp;     }                  pEnd = pTemp;      }void RadixSort(int arr[], int nLen){        //参数校验    if (arr == NULL || nLen <= 10)    {        return;    }    //找到最大值    int max = arr[0];    for (int i = 0; i < nLen; i++)    {        if (arr[i] > max)        {            max = arr[i];        }    }    int base = 1;        //创建桶中链表的头节点数组    List** pHeadarr = new List * [10];    //创建桶中链表的尾节点数组    List** pEndarr = new List * [10];    ::memset(pHeadarr, 0, sizeof(List*) * 10);    ::memset(pEndarr, 0, sizeof(List*) * 10);    while (max / base != 0)    {        //arr的元素放入桶中        for (int i = 0; i < nLen; i++)        {                        //链表尾部添加            AddNode(pHeadarr[arr[i] / base % 10], pEndarr[arr[i] / base % 10], arr[i]);        }        //出桶        int j = 0;        for (int i = 0; i < 10; i++)        {            while (pHeadarr[i])            {                List* pDel = pHeadarr[i];                                pHeadarr[i] = pHeadarr[i]->pNext;                                    arr[j++] = pDel->id;                delete pDel;                pDel = NULL;            }        }        base *= 10;     }       } int main(){    int arr[15] = { 34,36,31,78,65,32,33,34,89,90,91,67,52,71,77 };    RadixSort(arr, 15);    for (int val : arr)    {        cout << val << " ";    }    return 0;————————————————版权声明：本文为CSDN博主「van9527」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/van9527/article/details/126232966

1、数据处理的基本操作：增、删、查其中，增和删又可细分为在数据结构中间的增和删，以及在数据结构最后进行增和删，区别在于原始数据的位置是否发生改变。查找又可分为按照位置条件的查找和按照数值特征的查找。2、线性表结构的增删查（1）线性表是 n 个数据的有限序列，最常用的是线性链表，即链表。（2）链表有单向链表、循环链表、双向链表、双向循环链表。（3）链表新增、删除操作都比较容易，可以在 O(1)的时间复杂度内完成。但查找操作需要 O(n)的时间复杂度，不管是按照位置条件还是数值条件的查找。然而，链表的新增、 删除操作通常都伴随着查找操作。（4）当数据的元素个数不确定，且需要经常进行数据的新增和删除时，那么链表会比较合 适。（5）线性表案例：①单向链表的翻转：双指针。②给定一个奇数个元素的链表，查找出这个链表中间位置的结点的数值：暴力方法、快慢指 针方法。③判断链表是否有环：快慢指针方法。3、栈（先进后出的线性表）如何实现增、删、查？（1）栈是个限制版的线性表，限制的功能是，只允许数据从栈顶进出。不管是顺序栈（依赖数组）还是链式栈（依赖链表），对于数据的新增操作和删除操作的时间复杂度都是 O(1)，而对于查找操作则需要 O(n)的时间复杂度。（2）栈具有后进先出的特性，当面对的问题需要高频使用新增、删除操作，且新增和删除 操作的数据执行顺序具备后来居上的相反顺序时，栈就是个不错的选择。例如：浏览器页面的前进和后退、括号匹配等问题。4、队列（先进先出的线性表）如何实现增删查？（1）队列也是一种加了限制的线性表，它值允许从队尾插入数据，从队头删除数据，通常 有顺序队列（数组方式）和链式队列（链表方式）。队列通常用 front 指针指向队头， 用 rear 指针指向队尾。（2）顺序队列有普通队列和循环队列，循环队列可以防止出现“假溢出”问题。（3）链式队列的头结点不存放数据，是为了避免当队列为空时 front 和 rear 成为野指针。4）在时间复杂度上，循环队列和链式队列的新增、删除操作都为 O(1)，查找操作为 O(n)。 在空间性能方面，循环队列必须有一个固定的长度，因此存储的元素数量有限制且有时会造成空间浪费，而链式队列则更为灵活一些。（5）约瑟夫环可以用循环队列来解决。5.数组：如何实现基于索引的查找？（1）链表、栈、队列都是线性表，而数组可以看成线性表的一种推广，属于另外一种数据 结构。（2）数组增删查操作的特点：①增加：若插入数据在最后，则时间复杂度为 O(1)；若不是， 则时间复杂度为 O(n)。②删除：对应位置的删除，时间复杂度为 O(n)。③查找：如果 只根据索引值进行查找，则时间复杂度为 O(1)；若根据数值条件进行查找，则时间复 杂度为 O(n)。 （3）数组需要在定义时（3）数组需要在定义时就确定长度，且在内存中是按顺序存储的；而链表的长度灵活可变， 且在内存中随机存储。（4）数组更适合在数据量确定，且较少需要进行数据的增加、删除操作的场景下使用。同 时也更适合在数据对位置敏感的场景下使用。链表对数据的增加、删除操作的时间复 杂度更低。6.字符串匹配（1）字符串是由 n 个字符组成的有序整体，字符串的存储结构与线性表相同，也有顺序存储和链式存储两种。（2）字符串增删查的特点：①增加：和数组非常相似，正常情况下时间复杂度为 O(n)，若在最后插入（也叫连接），则为 O(1)。②删除：同样是 O(n)和 O(1)。③查找（字符串匹配），若主串的长度为 n，模式串的长度为 m，则时间复杂度为 O(nm)。（3）案例：字符串翻转，给定一个字符串，逐个翻转字符串中每个单词，例如，输入“the sky is blue”，输出“blue is sky the”。#include <stdio.h>#include <string.h>#include <stdlib.h>void str_reverse(char *str,char* rev){    int len=strlen(str),i,j,left=0,index;    for(i=0;i<=len;i++){        if(str[i]==''||str[i]=='\0'){            index=len-i;            for(j=left;j<i;j++){                rev[index]=str[j];                index++;//直接越位            }            if(left==0)                rev[index]='\0';            else                rev[insex]='';            left=i+1;//左端设置        }    }}void main(){    char str[]="the sky si blue";    char* rev=(char*)malloc(strlen(str)+1);    str_reverse(str,rev);    printf("The outis:%s\n", rev);}12345678910111213141516171819202122232425262728297.树和二叉树：分支关系与层次结构下，如何有效实现增删查？（1）树是由结点和边组成的，不存在环的一种数据结构。（2）相关概念：根结点、父结点、子结点、兄弟结点、叶子结点、深度、层。（3）二叉树：每个结点最多有两个分支，其中有两个特殊类型：①满二叉树。②完全二叉树：除了最后一层外，其他层的结点个数都达到最大，并且最后一层的叶 子结点都靠左排列。（4）二叉树有两种存储方法：链式存储法顺序存储法（下标为 i 的左子结点为 2i，右子 结点为 2i+1）（5）二叉树的基本操作：①遍历：前序遍历、中序遍历、后序遍历。时间复杂地为 O(n)。②增加和删除：时间复杂度位 O(1)==类似链表（6）二叉查找（搜索）树（BST）①任意一个结点的的左子树的每个结点的值都小于该结点的值，右子树的每个结点的 值都大于该结点的值。对二叉查找树进行中序遍历，即可输出一个从小到大的有序数据队列。②二叉查找树的查找操作、插入操作（包含查找位置）的时间复杂度为 O(logn)。③删除操作比较复杂：a.要删除某个叶子结点，则直接删除，将其父结点指针指向 NULL。b.要删除的结点只有一个子结点，则将其父结点指针指向其子结点的指针。c.要删除的结点有两个子结点，第一种方法是找到这个结点的左子树中的最大结点来替换该结点；第二种方法是找到这个结点的右子树中的最小 结点来替换该结点。（7）Trie 树/字典树：根结点不包含字符、其他结点都只包含一个字符；从根结点到某一叶子结点，路径上经过的字符连接起来，即为集合中的某个字符串。8.哈希表：高效率查找的利器（1）哈希表也叫散列表，是一种特殊的数据结构，其核心思想是：如果有一种方法，可以实现”地址” = f(关键字)的映射关系，那么就可以快速完成基于数据的数值查找了。但 哈希表不可避免地会产生哈希冲突，即不同的关键字得到相同的地址。（2）常用的设计哈希函数的方法:①直接定制法：哈希函数为关键字到地址的线性函数，如 H(key) = a * key + b。②数字分析法：假设关键字集合中的每个关键字 key 都是由 s 位数字组成的，从中提 取分布均匀的若干为组成哈希地址。③平方取中法：如果关键字的每一位都有重复的数字出现，并且频率很高，就可以先求关键字的平方值，扩大差异，然后取中间几位作为存储地址。④折叠法：如果关键字的位数很多，可以将关键字分割为几个等长的部分，取它们的 叠加和的值（舍去进位）作为哈希地址。⑤除留余数法：预先设置一个数 p，然后对关键字进行取余运算，即地址 为 key mod p。（3）常用解决哈希冲突的方法：①开放定址法：当一个关键字和另一个关键字产生冲突时，使用某种探测技术在哈希表中形成一个探测序列，然后沿着这个探测序列一次查找下去，当碰到空的单元时则插入其中。常用的探测方法是线性探测法。②链地址法：将哈希地址相同的记录存储在一张线性链表中。（拉链法）（4）哈希表可以提供非常快速的插入、删除、查找，无论多少数据，插入和删除只需要接 近常量的时间，查找的速度比树还快。但哈希表中的数据没有顺序的概念，同时 key 是不允许重复的。（5）在很多高级语言中，哈希函数、哈希冲突都已完成了黑盒化处理，是不需要开发者自 己设计的。————————————————版权声明：本文为CSDN博主「栋哥修炼日记」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/weixin_47397155/article/details/126233587

一、常见数据结构非线程安全的数据结构：ArrayList,LinkedList,ArrayQueue,HashMap,HashSet线程安全的数据结构：Vector,Stack,Hashtable,CopyOnWriteArrayList,ConcurrentHashMap二、ArrayList2-1 线程不安全的原因看源码public boolean add(E e) {    ensureCapacityInternal(size + 1);  // Increments modCount!!    // 该方法是容量保障，当容纳不下新增的元素时会进行扩容    elementData[size++] = e;    return true;}分析:当数组长度为10，而size = 9时，此时A线程判断可以容纳，B线程也来判断发现可以容纳（这是因为add非原子操作）。当A添加完之后，B线程再添加的话，就会报错（数组越界异常）而且这一步elementData[size++] = e也非原子性的.可以拆分为elementData[size] = e 和 size ++;在多线程的情况下很容易出现elementData[size] = e1; elementData[size] = e2; size++; size++; 的情况2-2 Vector实现安全Vector的add()源码：    public synchronized void addElement(E obj) {        modCount++;        ensureCapacityHelper(elementCount + 1);        elementData[elementCount++] = obj;    }分析: Vector的add方法加了synchronized ，而ArrayList没有，所以ArrayList线程不安全，但是，由于Vector加了synchronized ，变成了串行，所以效率低。回到目录…三、CopyOnWriteArrayListCopyOnWrite容器即写时复制的容器。// java.util.concurrent包下List<String> list = new CopyOnWriteArrayList<String>();123-1 如何实现线程安全？ 通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。 这样做的好处是我们可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。3-2 特征CopyOnWriteArrayList（写数组的拷贝）是ArrayList的一个线程安全的变体，CopyOnWriteArrayList和CopyOnWriteSet都是线程安全的集合，其中所有可变操作（add、set等等）都是通过对底层数组进行一次新的复制来实现的。它绝对不会抛出ConcurrentModificationException的异常。因为该列表（CopyOnWriteArrayList）在遍历时将不会被做任何的修改。CopyOnWriteArrayList适合用在“读多，写少”的并发场景中，比如缓存、白名单、黑名单。它不存在“扩容”的概念，每次写操作（add or remove）都要copy一个副本，在副本的基础上修改后改变array引用，所以称为“CopyOnWrite”，因此在写操作要加锁，并且对整个list的copy操作时相当耗时的，过多的写操作不推荐使用该存储结构。读的时候不需要加锁，如果读的时候有多个线程正在向CopyOnWriteArrayList添加数据，读还是会读到旧的数据，因为开始读的那一刻已经确定了读的对象是旧对象。3-3 缺点在写操作时，因为复制机制，会导致内存占用过大。不能保证实时性的数据一致，“脏读”。回到目录…四、HashMap4-1 底层原理不清楚的小白看看之前两篇文章，就可以很容易搞懂HashMap的底层实现原理了。 Java数据结构之哈希表 JDK中的Set和Map解析4-2 线程不安全的原因单看 HashMap 中的 put 操作：JDK1.7头插法 –> 将链表变成环 –> 死循环JDK1.8尾插法 –> 数据覆盖回到目录…五、ConcurrentHashMap// java.util.concurrent包下Map<Integer, String> map = new ConcurrentHashMap<>();125-1 实现原理JDK1.7时，采用分段锁JDK1.8时，只针对同一链表内互斥，不是同一链表内的操作就不需要互斥。但是一旦遇到需要扩容的时候，涉及到所有链表，此时就不是简单的互斥了。扩容的过程：当A线程put 操作时发现需要扩容，则它自己创建一个扩容后的新数组。A线程只把当前桶中的节点重新计算哈希值放入新数组中，并且标记该桶元素已经迁移完成。由于其它桶中的元素还没有迁移，所以暂时还不删除旧数组。等其它线程抢到锁并在桶内做完操作时，需要义务的将该桶节点全部搬移并标记桶。直到最后一个线程将最后一桶节点搬移完毕，则它需要把旧数组删除。5-2 与Hashtable的区别HashTable和HashMap的实现原理几乎一样，差别在于：HashTable不允许key和value为null；HashTable是线程安全的。 但是HashTable线程安全的策略实现代价却比较大，get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把全表锁。当一个线程访问或操作该对象，那其他线程只能阻塞。 所以说，Hashtable 的效率低的离谱，几近废弃。————————————————版权声明：本文为CSDN博主「一只咸鱼。。」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/qq15035899256/article/details/125961682

前言OK，今天是一个简单的应用题材分析，算法的学习需要我们不断的去思考，今天的题目依然来自leecode。1.数组反转1.1 leecode题目-旋转数组给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。示例：输入: nums = [1,2,3,4,5,6,7], k = 3输出: [5,6,7,1,2,3,4]解释:向右轮转 1 步: [7,1,2,3,4,5,6]向右轮转 2 步: [6,7,1,2,3,4,5]向右轮转 3 步: [5,6,7,1,2,3,4]1.2 分析题目数组元素有序轮转，即轮转位置k,意味着，每个元素向后移k位，且长度n-k~n-1位置的元素会被挪移至最前方；k为非负整数，所以，不存在向左轮转;1.3解题思路在不使用额外数组的前提下，我们可以有如下思考，设数组长度为length，则需要轮转k位，即数组的最后k位会进行挪移至数组前方，即，当我们反转数组后，可以得知[0,k-1],[k,lenth-1]这两个数组,即为轮转之后的对应数组，但是，两个数组中的元素排序是反的；接下来，依次反转[0,k-1],[k,lenth-1]，这两个数组，得到的数组就是答案了1.4 代码const reverseArray = (nums, start, end) => {  while (start < end) {    const temp = nums[start];    nums[start] = nums[end];    nums[end] = temp;    start += 1;    end -= 1;  }  return nums;};var reverseFunction = function(nums, k) {  let length  = nums.length;  nums = reverseArray(nums, 0, length - 1);  nums = reverseArray(nums, 0, k - 1);  nums = reverseArray(nums, k, length - 1);};reverseFunction([1,2,3,4,5,6,7],3);输出：[5,6,7,1,2,3,4]1.5 复杂度分析时间复杂度：时间复杂度：O(n)，其中 nn 为数组的长度。每个元素被翻转两次，一共 n 个元素，因此总时间复杂度为 O(2n)=O(n)。空间复杂度：O(1)。只需要常数空间存放若干变量。1.6 其他解法思路：既然轮转k位，即[length-1-k,length-1]位置的元素变为[0,k-1][0,length-1-k]位置的元素变为[length-1-k,length-1]所以我们只需要将原数组拆分为[0,k-1]，[length-1-k,length-1]，然后将其按照[length-1-k,length-1]+[0,k-1]组装成一个数组即可代码var reverseFunction2 = function(nums, k) {  let length  = nums.length;  let arrayLeft = nums.slice(0,length-k);  let arrayRight = nums.slice(length-k);  // return [...new Set([...arrayRight,...arrayLeft])];  return arrayRight.concat(arrayLeft);};reverseFunction2([1,2,3,4,5,6,7],3);大家会发现上述代码中，我注释了一行，因为，绝对诱人会想使用new Set方法去合并两个数组，那么，请注意，千万不能使用，因为，new Set方法，会讲两个数组进行合并后去重，如果原数组中出现相同元素，则，new Set将会给使用者狠狠上一课！总结算法的逻辑不同的人有不同的想法，但是殊途同归，答案是一致的，前提是，一定要靠清楚问题，仔细分析，验证的时候也要考虑各种情况。寄语算法的验证，必要且一定，好的算法，少不了单元测试————————————————版权声明：本文为CSDN博主「乾复道」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/Long861774/article/details/126214914

题目给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。示例 1：输入：nums = [2,3,1,1,4]输出：true解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2：输入：nums = [3,2,1,0,4]输出：false解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。方法一：正向遍历，计算每个位置开始能到达的最高处class Solution {public:    bool canJump(vector& nums) {        int reach=0;//记录当前能到达的最远处        //i遍历数组，i要始终处于能到达的位置，如果reach已经大于nums边界已经可以退出循环        for(int i=0;i<=reach&&reach<nums.size();i++)        {            reach=max(reach,i+nums[i]);//当前位置的最远边界为当前位置能加最大步数和最远边界，二者取较大        }        return reach+1>=nums.size();//边界是数组下标，从0开始，所以要加1    }};时间复杂度O(n)空间复杂度O(1)思路对于数组中的任意一个位置y，只要当前位置x加上x处可走的最大步数，二者之和大于y，则可以到达y一次遍历数组，维护当前的最远边界最后比较最远边界是否可以到达数组大小，如果是则返回true法二：逆向遍历数组，从末尾看能不能下降到0class Solution {public:    bool canJump(vector& nums) {        int left=nums.size()-1;//左边界        //从后往前遍历数组，如果i所指的位置加上当前数组值大于lef，则当前的左边界为i        for(int i=nums.size()-2;i>=0;i--)        {            if(nums[i]+i>=left) left=i;        }        //最后判断左边界能否小于0，即从终点能否回到起点        return left<=0;    }};法三：动态规划class Solution {public:    bool canJump(vector& nums) {        vector f(nums.size(),0);        f[0]=nums[0]-1;//初始位置可以到达的最远距离就是0加上当前可以走的步数        //依次确定经过每一个位置的最远距离        for(int i=1;i<nums.size();i++)        {            f[i]=max(f[i-1],i+nums[i-1]);            if(f[i]==i) return false;//表示不能往后走了，返回false        }        return true;    }};时间复杂度O(n)空间复杂度O(n)思路f[i]表示当前位置可以到达的最远位置状态转移方程：f[i]=max(f[i-1],i+nums[i-1])当前位置可以到达的最远位置有两种情况，如果不到达当前位置则是前一个位置可以到达的最远位置即f[i-1]，如果从当前位置出发则是i+nums[i]，二者取最大值每次比较当前位置可以到达的最远位置是否与当前位置相同，如果相同则表示无法继续向后走，返回false如果for循环正常退出则表示可以走到末尾，返回true————————————————版权声明：本文为CSDN博主「Mirevas」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/weixin_45781228/article/details/126202831

给定两个单链表 L1​=a1​→a2​→⋯→an−1​→an​ 和 L2​=b1​→b2​→⋯→bm−1​→bm​。如果 n≥2m，你的任务是将比较短的那个链表逆序，然后将之并入比较长的那个链表，得到一个形如 a1​→a2​→bm​→a3​→a4​→bm−1​⋯ 的结果。例如给定两个链表分别为 6→7 和 1→2→3→4→5，你应该输出 1→2→7→3→4→6→5。输入格式：输入首先在第一行中给出两个链表 L1​ 和 L2​ 的头结点的地址，以及正整数N (≤105)，即给定的结点总数。一个结点的地址是一个 5 位数的非负整数，空地址 NULL 用 -1 表示。随后 N 行，每行按以下格式给出一个结点的信息：Address Data Next其中 Address 是结点的地址，Data 是不超过 105 的正整数，Next 是下一个结点的地址。题目保证没有空链表，并且较长的链表至少是较短链表的两倍长。输出格式：按顺序输出结果链表，每个结点占一行，格式与输入相同。输入样例：00100 01000 702233 2 3489100100 6 0000134891 3 1008601000 1 0223300033 5 -110086 4 0003300001 7 -1输出样例：01000 1 0223302233 2 0000100001 7 3489134891 3 1008610086 4 0010000100 6 0003300033 5 -1分析：用vector<int> L1、L2存储题目中给定的两个链表，vector<int> ans保存合并后的链表。将较长的一个链表存储在L1中，如果原本L1较短，则将L1与L2用swap函数互相置换~在链表合并的过程中，i从0开始，将L1中每个结点添加到ans中，如果当前i是奇数（i & 1不等于0）就把L2的一个结点添加到ans中，直到L2中没有剩余元素~如此反复，就大功告成啦。#include <iostream>#include <vector>using namespace std;struct node {    int data, next;}A[100000];vector<int> L1, L2, ans;int sa, sb, n, a, ta, tb, c;int main() {    cin >> sa >> sb >> n;    for (int i = 0; i < n; i++) {        cin >> a >> A[a].data >> A[a].next;    }    ta = sa;    while (ta != -1) {        L1.push_back(ta);        ta = A[ta].next;    }    tb = sb;    while (tb != -1) {        L2.push_back(tb);        tb = A[tb].next;    }    if (L1.size() < L2.size()) swap(L1, L2);    for (int i = 0, c = L2.size() - 1; i < L1.size(); i++) {        ans.push_back(L1[i]);        if (i & 1 && c >= 0) ans.push_back(L2[c--]);    }    for (int i = 1; i < ans.size(); i++) {        printf("%05d %d %05d\n", ans[i-1], A[ans[i-1]].data, ans[i]);    }    printf("%05d %d -1", ans.back(), A[ans.back()].data);    return 0;}————————————————版权声明：本文为CSDN博主「柳婼」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/liuchuo/article/details/126209963

C/C++后端实习经验大礼包文章目录C/C++后端实习经验大礼包一、前言二、实习面试宝典1.自我介绍2.深挖个人项目(多个问题不同角度)3.有用过STL吗?常用哪些STL?4.介绍一下你对STL的理解5.深挖STL底层6.Qt有接触过吗?Qt下Tcp通信的整个流程是怎么样的?7.设计模式的问题8.编译原理的简单问题9.讲一下dijkstra算法10.谈一下你对STL的理解11.STL的使用场景12.C++11语法熟悉吗13.工程里面的回溯是什么?14.Widget::Widget(QWidget *parent) :QWidget(parent)什么意思15.算法题:跳台阶(找规律可以发现是个斐波那契数列)16.算法题: 餐厅(区间贪心)17.反问面试官环节三、实习工作分享1.实习专有名词及分析篇1.1SDK：软件开发工具包(Software Development Kit)1.2API:应用程序接口（Application Programming Interface)举例:windows串口通信函数API1.3上位机1.4下位机1.5上位机与下位机区别四、总结一、前言这篇文章是C/C++后端实习经验大礼包的第一弹,后面会持续更新,谢谢大家支持~~撒花,前面说过博主目前在一家互联网公司实习,今天给大家带来第一弹C/C++后端实习经验大礼包,希望大家喜欢。123二、实习面试宝典流程:投简历->简历筛选->笔试->技术电话面->技术视频面->hr面(有些公司可能在中间环节比较多,比如两次技术电话面,两次技术视频面等,视频面多为主管之类的,ps:主管面会参考之前的部门对你面试的评价)1.自我介绍2.深挖个人项目(多个问题不同角度)3.有用过STL吗?常用哪些STL?回答:用过,平时用的比较多,常用vector,map,unordered_map,stack,queue,deque，set,multiset,unordered_set,priority_queue,bitset,list之类的4.介绍一下你对STL的理解回答:STL就是标准模板库,可以提高程序的开发效率和复用性。5.深挖STL底层vector:底层存储是一个可变大小的数组,支持O(1)的随机访问,在尾部之外的位置插入和删除操作时间复杂度是 O(n)；deque:双端队列，支持O(1)随机访问在头部和尾部之外的位置插入和删除的时间复杂度是O(n)；list： 双向链表,不支持随机访问,只支持顺序访问,在任意位置的插入和删除速度很快；forward_list:单向链表；array是固定大小的数组（vector是可变大小的数组）；string:与vector类似，可以理解为特殊的vector,专门用来存储字符,支持随机访问,在尾部之外的位置插入的时间复杂度是O(n)；6.Qt有接触过吗?Qt下Tcp通信的整个流程是怎么样的?有的,主要从服务器端和客户端两方面介绍:1.服务器端创建用于监听的套接字(Socket)Socket可以看成在两个程序进行通讯连接中的一个端点,一个程序将一段信息写入Socket中,该Socket将这段信息发送给另外一个Socket中,使这段信息能传送到其他程序中。给套接字设置监听如果有连接到来, 监听的套接字会发出信号newConnected接收连接, 通过nextPendingConnection()函数, 返回一个QTcpSocket类型的套接字对象(用于通信)使用用于通信的套接字对象通信1 发送数据: write2. 接收数据: readAll/read客户端方面:创建用于通信的套接字连接服务器: connectToHost连接成功与服务器通信1 发送数据: write2.接收数据: readAll/read7.设计模式的问题后面我会专门写文章来讲8.编译原理的简单问题后面我会专门写文章来讲9.讲一下dijkstra算法回答:。dijkstra算法是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。时间复杂度:朴素版写法O(V方) 进阶写法:基于优先队列的写法（适用于稀疏图）总复杂度为 O(V log E)Edge:边 Vertex:顶点10.谈一下你对STL的理解C++ STL 做为C++的一个标准类库,包含了复用性最高的数据结构(容器)与算法(模板函数)。STL的容器可以分为以下几个大类:一:序列容器,有vector, list, deque,string.二:关联容器可以分为 set（集合）和 map（映射表）两大类，及其衍生体 multiset 和 multimap。这些容器的底层机制均以 RB-tree（红黑树）实现。RB-tree 也是一个独立容器，但并不开放使用。SGI STL 还提供一个不在标准规格的关联式容器 hash_table（散列表），以及以 hash_table 为底层机制而完成的 hash_set散列集合、hash_map散列映射表、hash_multiset散列多键集合、hash_multimap散列多键映射表。关联容器，类似关联式数据库，每个元素都有一个键值key和一个实值value。关联式容器的内部结构是一个平衡二叉树，包括 AVL-tree、RB-tree、AA-tree，STl 中运用的是 RB-tree红黑树。11.STL的使用场景vector(可变长的动态数组)适用场景：需要快速查找,不需要频繁插入/删除的场景string：string 类型支持长度可变的字符串,实际上就是vector，便于程序员操作字符串的类库。也可以认为string是一个类：string封装了char* ,管理这个字符串，是一个char* 型的容器；array：数组 使用场景:类似vector，比数组更安全（不担心越界），但是内容在栈上，且属于定长容器。deque：（double-ended queue，双端队列）是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。使用场景:头尾增删元素很快，随机访问比vector慢一点，因为内部处理堆跳转。中间插入和删除效率交较高。但因为他是list和vector的结合体,出场次数不多。forward_list：使用场景：需要list的优势，但只要向前迭代list：需要频繁插入/删除，不需要快速查找queue：FIFO（先进先出）~( First Input First Output)。底层容器可以是list或deque。set/multiset:需要元素有序，查找/删除/插入性能一样。红黑树效率都是O(logN)。即使是几个亿的内容，最多也查几十次。map/multimap 映射/多重映射：需要key有序将值关联到key，O(logN)查找/删除/插入性能一样12.C++11语法熟悉吗回答:还行,之后问了std::function,我回答是std::function是一个函数包装模板，可以包装下列这几种可调用元素类型：函数、函数指针、类成员函数指针或任意类型的函数对象（例如定义了operator()操作并拥有函数闭包）。std::function对象可被拷贝和转移，并且可以使用指定的调用特征来直接调用目标元素。当std::function对象未包裹任何实际的可调用元素，调用该std::function对象将抛出std::bad_function_call异常。13.工程里面的回溯是什么?回答:用git一直备份版本有需要就回退一下14.Widget::Widget(QWidget *parent) :QWidget(parent)什么意思由于构造函数是指在创建一个新对象的时候,自动执行,因此通常用来实现一些默认操作。此处“Widget::Widget(QWidget *parent) ”定义派生类的构造函数；:QWidget(parent)基类的有参构造函数最终达到:调用基类的有参构造函数,实现对象树上基类的功能15.算法题:跳台阶(找规律可以发现是个斐波那契数列)一个楼梯共有 n 级台阶，每次可以走一级或者两级，问从第 0 级台阶走到第 n 级台阶一共有多少种方案。输入格式共一行，包含一个整数 n。输出格式共一行，包含一个整数，表示方案数。数据范围1≤n≤15输入样例：5输出样例：8#include<bits/stdc++.h>using namespace std;int a=1,b=2,c;int main(){    int n;    cin>>n;    int w=n-2;    if(n==1) cout<<1;    else if(n==2) cout<<2;    else    {        while(w--)        {            c=a+b;            a=b,b=c;        }        cout<<b;    }}123456789101112131415161718192016.算法题: 餐厅(区间贪心)一家餐厅收到了 n 个客人的预约订单。每个订单都有开始时间和结束时间。对于每个订单，餐厅有权利接单，也有权利拒单。接受的订单，两两之间不得有任何时间交集，甚至不得有时刻交集，即如果一个订单的开始时间和另一个订单的结束时间相同，则两订单也不得同时接受。为了赚更多钱，餐厅需要尽可能多的接单。请问，餐厅最多可以接多少单？输入格式第一行包含一个整数 n。接下来 n 行，每行包含两个整数 l,r，表示一个订单的开始时间和结束时间。输出格式输出可以接受的最大订单数量。数据范围1≤n≤5×105,1≤l≤r≤109输入样例1：27 114 7输出样例1：1输入样例2：51 22 33 44 55 6输出样例2：3输入样例3：64 81 54 72 51 36 8输出样例3：2#include<bits/stdc++.h>using namespace std;struct node{    int l,r;};int n;bool cmp(node x,node y){    return x.r<y.r;}int main(){    cin>>n;    node a[n+1];    int i;    for(i=0;i<n;i++)    {        cin>>a[i].l>>a[i].r;    }    sort(a,a+n,cmp);    int temp=a[0].r;    int tot=1;    for(i=1;i<n;i++)    {        if(a[i].l>temp)        {            temp=a[i].r;            tot++;        }    }    cout<<tot;}123456789101112131415161718192021222324252627282930313217.反问面试官环节自由发挥即可,可以提前准备一些大众问题和自己关心的问题。三、实习工作分享1.实习专有名词及分析篇实习中你肯定会接触到很多自己没不熟悉的名词,在这里算法小学徒给大家分享一些cpp后端专有名词的解释:1.1SDK：软件开发工具包(Software Development Kit)软件开发工具包一般都是一些软件工程师为特定的软件包、软件框架、硬件平台、操作系统等建立应用软件时的开发工具的集合。SDK相当于是一个开发者集成的环境,作为APP供应链中重要的一环,在提升App兼容性和灵活性、节约开发成本方面表现卓著。一个产品想实现某些特定功能如消息推送,便可以找到相关的第三方SDK,工程师直接接入SDK,不用再重新开发。这样,工程师可以将更多的时间和精力投入到其他产品业务相关功能的开发上。1.2API:应用程序接口（Application Programming Interface)API又称为应用编程接口，就是软件系统不同组成部分衔接的约定。由于近年来软件的规模日益庞大，常常需要把复杂的系统划分成小的组成部分，编程接口的设计十分重要。程序设计的实践中，编程接口的设计首先要使软件系统的职责得到合理划分。良好的接口设计可以降低系统各部分的相互依赖，提高组成单元的内聚性，降低组成单元间的耦合程度，从而提高系统的维护性和扩展性。简单地说:API就是接口，就是通道，负责一个程序和其他软件的沟通，本质是预先定义的函数。举例:windows串口通信函数API1.CreateFile - 打开串口；2.SetupComm-初始化一个指定的通信设备的通信参数3.ReadFile - 读数据；4.WriteFile - 写数据；5.CloseHandle - 关闭串口；6.GetCommState - 取得串口当前状态；7.SetCommState - 设置串口状态；8.PurgeComm - 清除串口缓冲区 ；9.ClearCommError - 清除串口错误或者读取串口现在的状态；10.SetCommMask - 设置串口通信事件；1.3上位机上位机是指可以直接发出操控命令的计算机。1.4下位机下位机是直接控制设备获取设备状况的计算机。1.5上位机与下位机区别1.上位机一般是集中管理监控机，下位机是指现场直接控制器或控制机。上位机面向管理级用户，下位机面向底层设备控制。2.上位机:上位监视系统，一般为计算机系统（监控软件;下位机:控制系统的现场执行系统，一般为PLC等设备。3上位机是指工业控制中位于较高层次的计算机，一般是指电脑;而下位机是直接控制设备获取设备状况的的计算机，一般是指PLC/单片机之类的。4.经验：通常工控机，工作站，触摸屏作为上位机;而通信控制PLC，单片机等作为下位机，从而控制相关设备元件和驱动装置。四、总结后面博主会继续为大家带来 C/C++后端实习经验大礼包的其他内容,希望大家喜欢,撒花~~,另外根据博主的亲身实习经验,自学能力不管是面试还是实习过程中都非常受青睐, 程序员行业是一个需要终身学习的行业，大部分时间别人教你的东西只能作为一个参考,而且自学这种能力可以让人感觉到了无限的可能和创造性,跨越认识边界,不受限制的感觉真的很奇妙每日一句:不是因为有希望才去努力,而是努力了,才能看到希望。成功重在努力与坚持,抓住时机,就趁现在!与大家共勉!!!————————————————版权声明：本文为CSDN博主「算法小学徒」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/wyhplus/article/details/125771094

文章目录四. 插值查找4.1 简介4.2 代码实现五. 斐波那契查找5.1 简介5.2 算法实现四. 插值查找4.1 简介上一篇的二分查找中，每次查找都是从待查序列的中间开始，那么就很容易想到一个问题或者场景：假设我有一个数组0~999，我要查找的数为900，如果按照二分查找，那我每次取中间值要查找好一会，我们从上帝视角看明显可以从靠后的位置去查。于是针对这种情况，出现了插值查找。基本思路  插值查找是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的 查找方法，其核心就在于插值的计算公式 (key-array[low])/(array[high]-array[low])*(high-low)。简而言之，基于二分查找算法，将查找点的选择改进为自适应选择。复杂度分析时间复杂性：如果元素均匀分布，则O(log(logn))，在最坏的情况下可能需要O(n)。空间复杂度：O(1)。优缺点分析  对于长度比较长、关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。区别对比：① 插值查找类似于二分法，但插值查找每次从自适应 mid 处开始查找；② 二分查找种mid为(left+right) / 2， 插值查找则是通过公式计算得来；③ 插值查找公式：int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;low表示左边索引left,high表示右边索引right. key 就是需要查找的值。插值查找特点：① 查找序列有序；② 数据量大、关键字分布均匀的有序序列，插值查找快；③ 对于分布不均匀的有序序列来说，不一定比二分查找好。4.2 代码实现① 迭代法查找：private static int insertSearch1(int arr[],int target){    /*初始化左右搜索边界*/       int left=0,right=arr.length-1;       int mid;       while(left<=right){           mid=left+(target-arr[left])/(arr[right]-arr[left])*(right-left);           /*arr[mid]大于target，即要寻找的元素在左半边，所以需要设定右边界为mid-1，搜索左半边*/           if(target<arr[mid]){               right=mid-1;           /*arr[mid]小于target，即要寻找的元素在右半边，所以需要设定左边界为mid+1，搜索右半边*/              }else if(target>arr[mid]){               left=mid+1;           /*搜索到对应元素*/           }else if(target==arr[mid]){               return mid;           }       }       /*搜索不到返回-1*/       return -1;    }② 递归法实现：private static int insertSearch2(int array[],int left,int right,int target){    if(left<=right){        int mid=left+(target-array[left])/(array[right]-array[left])*(right-left);        /*搜索到对应元素*/        if(array[mid]==target){            return mid;        }else if(array[mid]<target){            /*array[mid]小于target，即要寻找的元素在右半边，所以需要设定左边界为mid+1，搜索右半边*/            return insertSearch2(array,mid+1,right,target);        }else{            /*array[mid]大于target，即要寻找的元素在左半边，所以需要设定右边界为mid-1，搜索左半边*/            return insertSearch2(array,left,mid-1,target);        }    }else{        return -1;    }}uniapp uView u-picker组件三级联动Demozip0星超过10%的资源555KB下载五. 斐波那契查找5.1 简介斐波那契查找又名黄金分割查找算法。什么是黄金分割？黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618.由于按此比例设计的造型十分美丽，因此称为黄金分割，也称中外比。什么是斐波那契数列？斐波那契数列{1, 1, 2, 3, 5, 8, 13, 21, 34, 55…}发现斐波那契数列的两个相邻数的比例，无限接近黄金分割值0.618算法原理：斐波那契查找原理与二分查找算法和插值查找算法非常相似，仅仅改变了中间节点(mid)的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1(F代表斐波那契数列)。？？？怎么理解这里的mid由斐波那契数列F[k] = F[k-1] + F[k-2]的性质，可以得到(F[k]-1) = (F[k-1]-1) + (F[k-2]-1) + 1. 该式说明：只要顺序表的长度为F[k]-1，则可以将该表分成长度为F[k-1]-1 和F[k-2]-1的两段，如上图所示。从而中间位置为mid=low+F(k-1)-1.类似的，每一字段也可以用相同的方式分割但顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1.这里的k值只要能使F[k]-1恰好大于或等于n即可，由以下代码得到，顺序表长度增加后，新增的位置(从n+1 到 F[k]-1位置)，都赋为n位置的值即可while(n>fib(k)-1){  k++;}123复杂度分析最坏情况下，时间复杂度为O(logn)，且其期望复杂度也为O(logn)。5.2 算法实现public class FibonacciSearch {        public static int FLENGTH = 20;    public static void main(String[] args) {        int [] arr = {1,8,10,89,100,134};        int target = 89;        System.out.println("目标元素在数组中位置是：" + fibSearch(arr, target));            }    public static int[] fib() {        int[] f = new int[FLENGTH];        f[0] = 1;        f[1] = 1;        for (int i = 2; i < FLENGTH; i++) {            f[i] = f[i-1] + f[i-2];        }        return f;    }        public static int fibSearch(int[] arr, int target) {        int low = 0;        int high = arr.length - 1;        int k = 0;         int mid = 0;         int f[] = fib();        /*获取最相邻的斐波那契数组中元素的值，该值略大于数组的长度*/        while(high > f[k] - 1) {            k++;        }        /*因为 f[k]值可能大于arr的长度。如果大于时，需要构造一个新的数组temp[]，将arr数组中的元素拷贝过去，不足的部分会使用0填充*/        int[] temp=Arrays.copyOf(arr, f[k]);        /*然后将temp后面填充的0，替换为最后一位数字         *如将temp数组由{1,8,10,89,100,134,0,0}变换为{1,8,10,89,100,134,134,134}*/        for(int i = high + 1; i < temp.length; i++) {            temp[i] = arr[high];        }                while (low <= high) {             mid = low + f[k - 1] - 1;            if(target < temp[mid]) {                 high = mid - 1;                /*因为f[k]=f[k-1]+f[k-2]，所以k--就相当于取temp数组的左边部分*/                k--;            } else if ( target > temp[mid]) {                 low = mid + 1;                /*同理，f[k]=f[k-1]+f[k-2]，k -= 2就相当于取temp数组的右边部分*/                k -= 2;            } else {                /*原arr数组中的值*/                if(mid <= high){                    return mid;                /*在temp中，扩展出来的高位的值*/                }else{                    return high;                }            }        }        return -1;    }}这里的算法实现可以理解可以看这位博主————————————————版权声明：本文为CSDN博主「Pisces_224」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/qq_36256590/article/details/126176644

选择排序、冒泡排序、插入排序【十大经典排序算法】利用对数器验证结果【选用Arrays.sort()系统提供的来】1 选择排序【选最小】//选择排序【每次选出一个最小的】public static void selectSort(int[] arr){    if(arr == null || arr.length < 2){        return;    }    for (int i = 0; i < arr.length - 1; i++){        int min = i;//假设i位置为最小值        for (int j = i+1; j < arr.length; j++) {            if(arr[j] < arr[min]){                min = j;            }        }        swap(arr, i, min);    }}1234567891011121314152 冒泡排序【选最大】//冒泡排序[每次选出最大的]public static void bubbleSort(int[] arr){    if(arr == null || arr.length < 2){        return;    }    for (int i = 0; i < arr.length - 1; ++i){        for(int j = 0; j < arr.length - i - 1; ++j){            if(arr[j] > arr[j+1]){                swap(arr, j, j+1);            }        }    }}123456789101112133 插入排序【前面有序】//插入排序[保证前面部分全部有序]public static void insertSort(int[] arr){    if(arr == null || arr.length < 2){        return;    }    for(int i = 1; i < arr.length; ++i){ //保证[0, i]位置上有序        for(int j = i - 1; j >= 0; j--){            if(arr[j] > arr[j+1]){                swap(arr, j, j+1);            }        }    }}123456789101112134 对数器4.1 gernateRandomArr(int maxSize, int maxValue)Math.random() -> [0,1) 所有的小数，等概率返回一个Math.random() * N -> [0,N) 所有小数，等概率返回一个(int)(Math.random() * N) -> [0,N-1] 所有的整数，等概率返回一个arr[i] = (int)((Math.random()+1) * maxValue - Math.random() * maxValue);【保证有正有负】//构建随机数组public static int[] generateRandomArr(int maxSize, int maxValue){    // Math.random() -> [0,1) 所有的小数，等概率返回一个    // Math.random() * N -> [0,N) 所有小数，等概率返回一个    // (int)(Math.random() * N) -> [0,N-1] 所有的整数，等概率返回一个    int[] arr = new int[(int)(Math.random() * (maxSize + 1))];    for (int i = 0; i < arr.length; i++) {        arr[i] = (int)((Math.random()+1) * maxValue - Math.random() * maxValue);    }    return arr;}12345678910114.2 copy(int[] arr)//复制数组public static int[] copy(int[] arr){    if(arr == null){        return null;    }    int[] res = new int[arr.length];    int i = 0;    for (int num : arr) {        res[i++] = num;    }    return res;}1234567891011124.3 isEq//判断数组是否相等public static boolean isEq(int[] arr1, int[] arr2){     if((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)){         return false;     }     if(arr1 == null && arr2 == null){         return true;     }     if(arr1.length != arr2.length){         return false;     }     for(int i = 0; i < arr1.length; ++i){         if(arr1[i] != arr2[i]){             return false;         }     }     return true;}————————————————版权声明：本文为CSDN博主「NPE~」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/weixin_45565886/article/details/126185609

什么是数据？1.所有能被输入到计算机中，且能被计算机处理的符号的总称。如：实数、整数、字符（串）、图形和声音等。2.是计算机操作对象的集合。3.是计算机处理的信息的某种特定的符号表示形式。算法的五种性质1.有穷性2.确定性3.有效性4.输入5.输出算法设计的目标1.正确性2.可读性3.健壮性4.高效率（时间与空间）算法的描述方式：1.自然语言2.程序设计语言3.伪代码4.流程图多项式时间算法的时间复杂度有哪些形式？1.常量阶:O(1)2.线性阶:O(n)3.平方阶:O(n2)4.立方阶5.对数阶6.线性对数阶按照数据元素之间逻辑关系的特性可分为哪几类(作简要说明)？1.集合集合中数据元素之间除了“同属于一个集合”的特性外，数据元素之间无其他关系，它们之间的关系称为是松散性的2.线性结构线性结构中数据元素之间存在“一对一”的关系3.树形结构树形结构中数据元素之间存在“一对多”的关系4.图形结构图形结构中数据元素之间存在“多对多”的关系列举几个常见的链表(至少三个)？1.单链表1.循环链表2.双向链表3.双向循环链表顺序表与链表的比较1.链表比较灵活，插入和删除操作效率较高，但空间利用率低，适用于实现动态的线性表；2.顺序表实现比较简单，并且空间利用率也较高，可高效的进行随机存取，但顺序表不易扩充，插入和删除操作效率较低，适合于实现相对“稳定”的静态线性表。静态查找与动态查找分别是什么？静态查找表：查找表的操作不包含对表的修改操作。也就是仅对查找表进行查找或读表元操作。动态查找表：若在查找的同时插入了表中不存在的记录，或从查找表中删除了已存在的记录。动态表查找有什么特点？表结构本身是在查找过程中动态生成的，即对于给定值key，若表中存在关键字值等于key的记录，则查找成功返回；否则插入关键字值等于key的记录。什么是二叉排序树？二叉排序树或者是一棵空树，或者是一颗具有下列性质的二叉树：① .若左子树不空，则左子树上所有结点的值均小于根结点的值;② .若右子树不空，则右子树上所有结点的值均大于根结点的值;③ .它的左右子树也都是二叉排序树简述什么是结点的平衡因子。结点的平衡因子：该结点的左子树深度与右子树深度之差，又称为平衡度。① .平衡二叉树也就是树中任意结点的平衡因子的绝对值小于等于1的二叉树。② .在AVL树中的结点平衡因子可能有3种取值：-1、0、1在哈希表查找中，对数字的关键字常用的哈希函数有哪些(不少于5个)1. 除留余数法2. 平方取中法3. 直接定址法4. 折叠法5. 数字分析法6. 随机数法在哈希表查找中，常用的处理哈希冲突的方法有哪些(不少于3个)1. 开放定址法2. 链地址法3. 公共溢出区法4. 再哈希法computed 和 watch 的区别computed： 是计算属性，依赖其它属性值，并且 computed 的值有缓存，只有它依赖的属性值发生改变，下一次获取 computed 的值时才会重新计算 computed 的值；watch： 更多的是“观察”的作用，类似于某些数据的监听回调，每当监听的数据变化时都会执行回调进行后续操作；vue-router 路由模式有几种？vue-router 有 3 种路由模式：hash、history、abstract各模式的说明如下：hash: 使用 URL hash 值来作路由。支持所有浏览器，包括不支持 HTML5 History Api 的浏览器；history : 依赖 HTML5 History API 和服务器配置。具体可以查看 HTML5 History 模式；abstract : 支持所有 JavaScript 运行环境，如 Node.js 服务器端。如果发现没有浏览器的 API，路由会自动强制进入这个模式.vue中为什么data是一个函数组件的data写成一个函数，数据以函数返回值形式定义，这样每复用一次组件，就会返回一份新的data，类似于给每个组件实例创建一个私有的数据空间，让各个组件实例维护各自的数据。如果单纯的写成对象形式，就使得所有组件实例共用了一份data，这样一个实例中更新数据会导致其他实例数据改变。v-if 和 v-show 的区别v-if 在编译过程中会被转化成三元表达式，条件不满足时不渲染此节点。v-show 会被编译成指令，条件不满足时控制样式将此节点隐藏请列举几个vue内部指令，并说明其作用(至少五个)1. v-bind：绑定属性，动态更新HTML元素上的属性。例如 v-bind:class；2. v-on：用于监听DOM事件。例如 v-on:click v-on:keyup；3. v-text：更新元素的textContent；4. v-model：用来在 input、select、textarea、checkbox、radio 等表单控件元素上创建双向数据绑定，根据表单上的值，自动更新绑定的元素的值；5. v-for：循环指令编译出来的结果是 -L 代表渲染列表。优先级比v-if高最好不要一起使用，尽量使用计算属性去解决；6. v-show：使用指令来实现 -- 最终会通过display来进行显示隐藏；你建不建议v-if和v-for一起使用？为什么？v-for和v-if不要在同一标签中使用，因为解析时先解析v-for在解析v-if。如果遇到需要同时使用时可以考虑写成计算属性的方式。v-for为什么要加keyv-for遍历时，key是Vue中vnode的唯一标记，通过这个 key，我们的 diff 操作可以更准确、更快速。更准确是因为带 key时，在sameNode函数进行key值对比中可以避免就地复用的情况。所以会更加准确。更快速是利用 key 的唯一性生成 map 对象来获取对应节点，比遍历方式更快什么是微服务框架？微服务架构就是将单体的应程序分成多个应程序，这多个应程序就成为微服务，每个微服务运行在自己的进程中，并使用轻量级的通信机制。这些服务围绕业务能力来划分，并通过自动化机制来独立部署。汶些服务可以使用不同的编程语言，不同数据库，以保证最低限度的集中式管理Spring Cloud是什么Spring Cloud是一系列框架的有序集合，它利用Spring Boot的开发便利性巧妙的简化了分布式系统基础设施的开发，如服务发现、配置中心、智能路由、消息总线、负载均衡等，都可以用Spring Boot的开发风格来做到一键部署和启动。Spring Cloud将各家公司开发的比较成熟的服务框架组合起来，通过Spring Boot风格进行再封装，屏蔽掉了复杂的配置和实现原理，最终给开发者一套易懂、易部署和易维护的分布式系统开发工具包。Spring Cloud和Spring Boot的区别Spring Boot专注于快速方便的开发单个个体微服务。Spring Cloud关注全局，它将Spring Boot开发的单体微服务整合并管理起来Spring Cloud为各个微服务之间提供配置管理、服务发现、路由、熔断、降级等等集成服务。Spring Boot可以离开Spring Cloud独立使用开发项目，Spring Cloud离不开Spring Boot，属于依赖关系Spring Boot专注于微服务个体，Spring Cloud关注全局的微服务治理SpringCloud Alibaba有哪些主要功能？分布式配置：分布式系统的外部配置管理，配置中心可视化、分环境配置控制。配置动态更新能力。服务注册与发现：适配SpringCloud标准的服务注册与服务发现管理。服务限流与降级：可通过控制台进行实时的修改限流降级的规则，实时的Metrics监控。支持多种协议消息驱动：基于RocketMQ实现消息驱动的业务场景开发。分布式事务：开源Seata使用@GlobalTransactional注解，零侵入的实现分布式事务的支持。SpringCloud Alibaba核心组件有哪些？Nacos (配置中心与服务注册与发现)Sentinel (分布式流控)RocketMQ (消息队列)Seata (分布式事务)Dubbo (RPC)Nacos是什么，他有哪些关键特性？Nacos用于服务的注册发现与服务的配置管理，它提供了简单易用的Web Console。可以帮助开发者快速的实现服务发现、服务配置管理、服务元数据等需求它的关键特性主要有：服务发现和服务健康监测动态配置服务动态 DNS 服务服务及其元数据管理Sentinel是什么，它有什么作用？Sentinel是一个高可用的流量控制与防护组件，保障微服务的稳定性。Sentinel分为两个部分，sentinel-core与sentinel-dashboard。sentinel-core 部分能够支持在本地引入sentinel-core进行限流规则的整合与配置。sentinel-dashboard 则在core之上能够支持在线的流控规则与熔断规则的维护与调整等。熔断和降级的区别？服务降级有很多种降级方式！如开关降级、限流降级、熔断降级!服务熔断属于降级方式的一种！当发生下游服务不可用的情况，熔断和降级必定是一起出现。服务降级大多是属于一种业务级别的处理，熔断属于框架层级的实现什么是Feign？Feign是一个声明web服务客户端，这使得编写web服务客户端更容易Feign将我们需要调用的服务方法定义成抽象方法保存在本地就可以了，不需要自己构建Http请求，直接调用接口即可，不过要注意的是，调用的方法要和本地抽象方法的签名完全一致。Spring Cloud Gateway是什么，它有什么作用？Spring Cloud Gateway是Spring Cloud官方推出的第二代网关框架，取代Zuul网关。网关作为流量控制组件，在微服务系统中有着非常重要的作用，网关常见的功能有转发、权限校验、限流控制等作用什么是Redis，它有哪些基本数据类型？Redis是用C语言开发的一个开源的高性能键值对（key-value）数据库。它通过提供多种键值数据类型来适应不同场景下的存储需求，Redis支持的基本数据类型如下：字符串类型 string散列类型 hash列表类型 list集合类型 set有序集合类型 sortedset有哪些场景可以使用 RabbitMQ？服务间异步通信顺序消费定时任务请求削峰RabbitMQ有哪几种常见的工作模式？Work queuesPublish/Subscribe：发布订阅模式Routing：路由模式TopicsHeaderRPCMQ的优点有哪些？异步处理 - 相比于传统的串行、并行方式，提高了系统吞吐量。应用解耦 - 系统间通过消息通信，不用关心其他系统的处理。流量削锋 - 可以通过消息队列长度控制请求量；可以缓解短时间内的高并发请求。日志处理 - 解决大量日志传输。消息通讯 - 消息队列一般都内置了高效的通信机制，因此也可以用在纯的消息通讯。————————————————版权声明：本文为CSDN博主「陶然同学」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/weixin_45481821/article/details/126163199

上一期为大家区分了 NETCONF 和 YANG  ，分别阐述了他们出现的缘由。因为YANG还是很重要的，所以本期多说些，给大家介绍下YANG的树形语法结构。.  Yang的语法结构YANG模型是一种树形结构，是由无数的叶子、列表、叶列表、容器组成的描述整个设备的一棵树。具体来说，YANG模型有四种主要类型的数据节点，包括叶节点（leaf）、列表节点（list）、叶列表节点（leaf-list）和容器节点（container）：    叶子                      列表                           叶列表                      容器                  除了以上四种主要类型的数据节点外，组（grouping）、分支（choice）、基础数据类型和派生类型（typedef）也是YANG模型其中一部分的相关功能定义语句。    组                      分支                      基础数据类型                      派生类型                  .本期大家知道了Yang的树形结构，树形结构比于数组、链表、队列和栈等线性结构要复杂些，通过设定条件和限制就可以定义出一种新类型的树。但是树形结构其实很形象，并且不同的树也有很多有趣的特点，如果大家感兴趣，可以自行了解一下。下一期重点来了，大家可以提前思考：OpenConfig Yang和IETF Yang 到底是什么？为什么有两种模型？是哪些人创造了它们？在使用上会有什么要求呢？让我们后面逐步解答...*注：部分文档来源于网络.上一篇：《Yang的缘起》下一遍：待更新.iMaster NCE AOC社区入口：    中文版社区      /    英文版社区 

（1）27.移除元素题目：给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。解题思路：确定当前非val值，先前覆盖，尾指针位置自增即可class Solution:    def removeElement(self, nums: List[int], val: int) -> int:        len_ = len(nums)        if len_ == 0:            return 0        idx = 0        for i in range(len_):            if nums[i] != val:                nums[idx] = nums[i]                idx += 1        return idx（2）26.移除元素中的重复项题目：给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。思路：同（1），还是一个指针确定当前不重复的尾部位置，另一个指针去找寻符合条件的值。class Solution:    def removeDuplicates(self, nums: List[int]) -> int:        len_nums = len(nums)        if len_nums <= 1:            return len_nums                idx = 0        for i in range(1, len_nums):            if nums[idx] != nums[i]:                idx += 1                nums[idx] = nums[i]                        return idx+1class Solution(object):    def removeDuplicates(self, nums):        for i in range(len(nums) - 1, 0, -1):            if nums[i] == nums[i - 1]:                del nums[i]                        return len(nums)（3）283.移动零题目：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。解题思路：找出所有非零值向前移动，记录尾指针位置，将尾指针之后所有元素置零class Solution:    def moveZeroes(self, nums: List[int]) -> None:        len_nums = len(nums)        if len_nums <= 1:            return        idx = 0        for i in range(len_nums):            if nums[i] != 0:                nums[idx] = nums[i]                idx += 1        while idx < len_nums:            nums[idx] = 0            idx += 1（4）844.比较含退格的字符串题目：给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。注意：如果对空文本输入退格字符，文本继续为空。解题思路：异常处理前端无用"#"，然后处理字符串即可class Solution:    def backspaceCompare(self, s: str, t: str) -> bool:        s_list, t_list = [], []        s, t = s.lstrip("#"), t.lstrip("#")                for i in s:            if i != "#":                s_list.append(i)            else:                s_list = s_list[:-1]        for i in t:            if i != "#":                t_list.append(i)            else:                t_list = t_list[:-1]        return True if t_list == s_list else False（5）有序数组的平方题目：给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。解题思路：lambda的妙用，绝对值大小排序即可class Solution:    def sortedSquares(self, nums: List[int]) -> List[int]:        nums.sort(key = lambda x:abs(x), reverse = False)        for i in range(len(nums)):            nums[i] = nums[i] ** 2        return nums————————————————版权声明：本文为CSDN博主「Dustw1nd」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/qq_35668477/article/details/126148442

如果想要更详细的了解指针原理、用途，请自行阅读《The C Programming Language》第 5 章。指针是什么指针其实就是一个包含一个变量的地址的变量。如何定义指针定义指针的方式很简单：类型 *指针名称;即可。比如来声明一个变量名为a，类型为int的指针：int *a;1也就是比平时声明变量多了一个型号*。但是这里需要注意的是，声明时候的*a表示的是指针a包含的内存地址指向的内容，而a包含的则是地址。 这个地址开始的一部分连续的空间将会划分给指针，以供存储地址，划出的大小由类型int决定，一般int为 2 个字节（这里的一个字节在有些英文文档中被称为“cell”）。如何获取一个变量的地址刚才说到指针其实就是一个包含一个变量的地址的变量。那么如何获取一个变量的地址呢？这样才可以给指针赋值。方法很简单，使用&符号，如下（a就是上文声明的指针）：a=&b;1通过以上表达式，就将变量b的地址赋值给指针a，如果这时候使用*a输出，就会发现输出的是b的值。而且修改b，输出*a的值也会发生改变。如果a并不是指针，那么变量a将会以十六进制存储变量b的地址（一般是十六进制，有些环境、设备可能会有不同）。下面展示输出一个变量地址的方法：#include <stdio.h>int main(){    int a=10;        printf("%x\n",&a);        return 0;}12345678910输出结果如下：bfeff2c8Program ended with exit code: 012可以看到，第一行的bfeff2c8就是变量a的地址。赋值给一个指针指针只负责存储地址，具体的值还是由变量存储。所以赋值给指针，就是将一个变量的地址赋值给它。如下：#include <stdio.h>int main(){    int a=10;    int *b;        b=&a;        printf("%d\n",*b);        return 0;}12345678910111213输出：10Program ended with exit code: 012指针的用途听了上述描述，可能你会觉得指针的作用好像就是新建了一个软连接（symbolic link）或者创建了一个别名（alias）。但是指针最大的作用其实是搭配数组使用。通过指针来使用数组因为一个数组的地址其实是数组第一个元素的地址，而数组在地址上是连续存放的，所以可以对地址加 1 来实现控制数组。如下（实际运行的时候可能会提醒，但是这里出于研究目的忽略提醒）：#include <stdio.h>int main(){    int a[5]={1,2,3,4,5};    int *b;        b=&a;        printf("数组地址：%x\n",&a);    printf("数组第一个元素：%d\n",*b);    b=b+1;    printf("是不是数组第二个元素：%d\n",*b);        return 0;}12345678910111213141516输出：数组地址：bfeff2b0数组第一个元素：1是不是数组第二个元素：2Program ended with exit code: 01234这里说明一下，如果在开发过程中，指针指向数组的话，请使用b=&a[0];，这样不会出现提醒。字符串和指针字符串也是数组的一部分，所以也可以使用指针来实现一些功能，例如对比字符串（这个虽然不用指针也能写，但是使用指针的话，代码会变得更简洁）。下面来演示一下指针访问字符串的例子（记得把指针类型换一下，换成char，不然int存放的会是 ASCII编码，而不是字符串的内存地址）：#include <stdio.h>int main(){    char a[20]="Hello! World!";    char *b;        b=&a[0];        printf("字符串的地址：%x\n",&a);    printf("字符串的第一个字符：%c\n",*b);    b=b+5;    printf("字符串的第六个字符：%c\n",*b);        return 0;}12345678910111213141516输出：字符串的地址：bfeff2b0字符串的第一个字符：H字符串的第二个字符：!Program ended with exit code: 01234其他用途还有一些其他的用途，但是有上述的知识也不用过多解释了，讲一下思路即可。更多维度的数组C 语言支持二维数组，但是有时候需要更多维度，那么就需要使用指针来嵌套数组，这样可以实现更多维度的数组。一般就是将指向多个数组的多个指针存放在一个数组中，然后通过上述方法来使用。处理命令选项这个一般使用不多，因为现在也没多少人使用命令行，都用图形化了，但是我还是要说一下。先看一下我的另一篇博客《C语言中函数main的参数argc和argv是什么》。argv是一个指向一个字符串数组的指针，数组包含了参数，每个字符串就是一个参数，最后一个元素为0。不过一般习惯使用多级指针来操作字符串。这里介绍一下，一般的命令行程序，使用起来的命令如下：程序名 -短选项 --长选项 内容1短选项为-加一个字母，长选项一般为--加一个单词。现在有些程序的短选项会省略-。短选项一般可以写到一起，举个例子：ls -a -f也可以写成ls -af。而这一功能的实现就需要使用指针（首先这是个存放了指向字符串指针的数组，其次指针真的更方便）。————————————————版权声明：本文为CSDN博主「zhonguncle」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/qq_33919450/article/details/126129081

“利用GPU计算TOP10”这件事情不一定非要用核函数，还可以用Thrust的CUDA加速工具库：cub和Thrust其实也是可以排序的良方呢！CUDA Thrust的资料在这里：https://docs.nvidia.com/cuda/thrust/index.html我们先做个排序的尝试。首先，张小白搜到了这个：https://blog.csdn.net/qq_23123181/article/details/122116099里面有个例子，于是张小白就用自己的Nano上的Juputer做了尝试：这是用cmake编译的，有以下文件：CMakeLists.txtCMAKE_MINIMUM_REQUIRED(VERSION 3.5) PROJECT(thrust_examples) set(CMAKE_BUILD_TYPE Release) find_package(CUDA) include_directories(${CUDA_INCLUDE_DIRS}) message(STATUS "${CUDA_INCLUDE_DIRS}") message(STATUS "${CUDA_LIBRARIES}") cuda_add_executable(thrust_examples sort.cu)sort.cu这个张小白加了点打印信息，这样可以看得清楚些：#include <thrust/host_vector.h> #include <thrust/device_vector.h> #include <thrust/generate.h> #include <thrust/sort.h> #include <thrust/copy.h> #include <algorithm> #include <vector> #include <time.h> #define TOPK 20 int main(void) { thrust::host_vector<int> h_vec(10000*1000); std::generate(h_vec.begin(), h_vec.end(), rand); std::cout<< "size()=" << h_vec.size() <<std::endl; std::vector<int> vec(h_vec.size()); // h_vec->vec thrust::copy(h_vec.begin(), h_vec.end(), vec.begin()); // h_vec->d_vec thrust::device_vector<int> d_vec=h_vec; clock_t time1,time2; //sort d_vec //std::cout<< "d_vec.size()=" << d_vec.size() <<std::endl; std::cout<< "before sort d_vec..." <<std::endl; for(int i = 0; i < TOPK; ++i) { std::cout << d_vec << " "; } std::cout << std::endl; std::cout << std::endl; time1 = clock(); thrust::sort(d_vec.begin(), d_vec.end()); time2 = clock(); std::cout<<(double)(time2-time1)/CLOCKS_PER_SEC*1000<< " ms"<<std::endl; std::cout << std::endl; std::cout<< "after sort d_vec..." <<std::endl; for(int i = 0; i < TOPK; ++i) { std::cout << d_vec << " "; } std::cout << std::endl; std::cout << std::endl; //sort vec //std::cout<< "vec.size()=" << vec.size() <<std::endl; std::cout<< "before sort vec..." <<std::endl; for(int i = 0; i < TOPK; ++i) { std::cout << vec << " "; } std::cout << std::endl; std::cout << std::endl; time1 = clock(); std::sort(vec.begin(),vec.end()); time2 = clock(); std::cout<<(double)(time2-time1)/CLOCKS_PER_SEC*1000<< " ms"<<std::endl; std::cout << std::endl; std::cout<< "after sort vec..." <<std::endl; for(int i = 0; i < TOPK; ++i) { std::cout << vec << " "; } std::cout << std::endl; std::cout << std::endl; //sort h_vec //std::cout<< "h_vec.size()=" << h_vec.size() <<std::endl; std::cout<< "before sort h_vec..." <<std::endl; for(int i = 0; i < TOPK; ++i) { std::cout << h_vec << " "; } std::cout << std::endl; std::cout << std::endl; time1 = clock(); thrust::sort(h_vec.begin(), h_vec.end()); time2 = clock(); std::cout<<(double)(time2-time1)/CLOCKS_PER_SEC*1000<< " ms"<<std::endl; std::cout << std::endl; std::cout<< "after sort h_vec..." <<std::endl; for(int i = 0; i < TOPK; ++i) { std::cout << h_vec << " "; } std::cout << std::endl; return 0; }这里面分别对三种类型进行了排序：1.host_vector（thrust的）2.vector（STL的）3.device_vector（thrust的）我们先执行下，看看效果：解读一下：该代码先申请了一个host_vector类型的h_vec，并且随机生成了1000万条记录。然后分别申请了vector类型的vec和 device_vector类型的d_vec，并将值赋成跟h_vec完全一致。然后分别使用thrust::sort(d_vec.begin(), d_vec.end());std::sort(vec.begin(),vec.end());thrust::sort(h_vec.begin(), h_vec.end());分别给这三个1000万随机数排序（目前是升序）并打印出了最小的10个数（与TOP10相对应，可能应该叫BOTTOM10吧？张小白这么想。。。）其中第二个sort并非thrust库的。第一个和第三个sort用的是thrust库。从最终算出的时间结果也可以看出：标准库的sort耗时最长——2085.9msHOST上的thrust sort耗时较长——886.99msDEVICE上的thrust sort耗时最短——26.672ms。这样看起来，貌似比昨天作业中所有的测试都出色了。昨天TOP10的数据在这里：我们来把代码落实一下：那就开干吧！原代码如下：sort2.cu#include <stdio.h> #include <stdlib.h> #include <time.h> #include "error.cuh" #define BLOCK_SIZE 256 #define N 1000000 #define GRID_SIZE ((N + BLOCK_SIZE - 1) / BLOCK_SIZE) #define topk 10 __managed__ int source_array[N]; __managed__ int _1pass_results[topk * GRID_SIZE]; __managed__ int final_results[topk]; __device__ __host__ void insert_value(int* array, int k, int data) { for (int i = 0; i < k; i++) { if (array == data) { return; } } if (data < array[k - 1]) return; for (int i = k - 2; i >= 0; i--) { if (data > array) array[i + 1] = array; else { array[i + 1] = data; return; } } array[0] = data; } __global__ void top_k(int* input, int length, int* output, int k) { } void cpu_result_topk(int* input, int count, int* output) { /*for (int i = 0; i < topk; i++) { output = INT_MIN; }*/ for (int i = 0; i < count; i++) { insert_value(output, topk, input); } } void _init(int* ptr, int count) { srand((unsigned)time(NULL)); for (int i = 0; i < count; i++) ptr = rand(); } int main(int argc, char const* argv[]) { int cpu_result[topk] = { 0 }; cudaEvent_t start, stop; CHECK(cudaEventCreate(&start)); CHECK(cudaEventCreate(&stop)); //Fill input data buffer _init(source_array, N); printf("\n***********GPU RUN**************\n"); CHECK(cudaEventRecord(start)); top_k << <GRID_SIZE, BLOCK_SIZE >> > (source_array, N, _1pass_results, topk); CHECK(cudaGetLastError()); top_k << <1, BLOCK_SIZE >> > (_1pass_results, topk * GRID_SIZE, final_results, topk); CHECK(cudaGetLastError()); CHECK(cudaDeviceSynchronize()); CHECK(cudaEventRecord(stop)); CHECK(cudaEventSynchronize(stop)); float elapsed_time; CHECK(cudaEventElapsedTime(&elapsed_time, start, stop)); printf("Time = %g ms.\n", elapsed_time); CHECK(cudaEventDestroy(start)); CHECK(cudaEventDestroy(stop)); cpu_result_topk(source_array, N, cpu_result); int ok = 1; for (int i = 0; i < topk; ++i) { printf("cpu top%d: %d; gpu top%d: %d \n", i + 1, cpu_result, i + 1, final_results); if (fabs(cpu_result - final_results) > (1.0e-10)) { ok = 0; } } if (ok) { printf("Pass!!!\n"); } else { printf("Error!!!\n"); } return 0; }先将代码框架移植到cmake编译器上：CMakeLists.txtCMAKE_MINIMUM_REQUIRED(VERSION 3.5) PROJECT(thrust_examples) set(CMAKE_BUILD_TYPE Release) find_package(CUDA) include_directories(${CUDA_INCLUDE_DIRS}) message(STATUS "${CUDA_INCLUDE_DIRS}") message(STATUS "${CUDA_LIBRARIES}") cuda_add_executable(thrust_examples sort2.cu)其实很简单，将sort.cu改为sort2.cu即可。然后给sort2.cu加上sort.cu头文件:#include <stdio.h> #include <stdlib.h> #include <time.h> #include "error.cuh" #include <thrust/host_vector.h> #include <thrust/device_vector.h> #include <thrust/generate.h> #include <thrust/sort.h> #include <thrust/copy.h> #include <algorithm> #include <vector>并注释掉GPU RUN的那部分代码。并在GPU RUN的地方加入 thrust的相关代码。 printf("\n***********GPU RUN**************\n"); CHECK(cudaEventRecord(start)); //定义host_vector thrust::host_vector<int> h_vec; //遍历source_array,并赋值给host_vector for(int i= 0; i< N; i++) { h_vec.push_back(source_array); } printf("h_vec push ok!\n"); //定义device_vector,将host_vector复制到device_vector thrust::device_vector<int> d_vec=h_vec; printf("d_vec init ok!\n"); CHECK(cudaGetLastError()); //给device_vector排序 thrust::sort(d_vec.begin(), d_vec.end()); printf("d_vec sort ok!\n"); for (int i = 0; i < topk ; i++) { final_results = d_vec[vec.size()-1-i]; } printf("vec sort ok!\n");后面与原来的代码一样，就是打印CPU TOP10，以及cudaEvent_t通过计算GPU时间.我们全部显示一下：sort2.cu#include <stdio.h> #include <stdlib.h> #include <time.h> #include "error.cuh" #include <thrust/host_vector.h> #include <thrust/device_vector.h> #include <thrust/generate.h> #include <thrust/sort.h> #include <thrust/copy.h> #include <algorithm> #include <vector> #define BLOCK_SIZE 256 #define N 10000000 #define GRID_SIZE ((N + BLOCK_SIZE - 1) / BLOCK_SIZE) #define topk 10 __managed__ int source_array[N]; __managed__ int _1pass_results[topk * GRID_SIZE]; __managed__ int final_results[topk]; __device__ __host__ void insert_value(int* array, int k, int data) { for (int i = 0; i < k; i++) { if (array == data) { return; } } if (data < array[k - 1]) return; for (int i = k - 2; i >= 0; i--) { if (data > array) array[i + 1] = array; else { array[i + 1] = data; return; } } array[0] = data; } __global__ void top_k(int* input, int length, int* output, int k) { } void cpu_result_topk(int* input, int count, int* output) { /*for (int i = 0; i < topk; i++) { output = INT_MIN; }*/ for (int i = 0; i < count; i++) { insert_value(output, topk, input); } } void _init(int* ptr, int count) { srand((unsigned)time(NULL)); for (int i = 0; i < count; i++) ptr = rand(); } int main(int argc, char const* argv[]) { int cpu_result[topk] = { 0 }; cudaEvent_t start, stop; CHECK(cudaEventCreate(&start)); CHECK(cudaEventCreate(&stop)); //Fill input data buffer _init(source_array, N); printf("\n***********GPU RUN**************\n"); CHECK(cudaEventRecord(start)); //定义host_vector thrust::host_vector<int> h_vec; //遍历source_array,并赋值给host_vector for(int i= 0; i< N; i++) { h_vec.push_back(source_array); } printf("h_vec push ok!\n"); //定义device_vector,将host_vector复制到device_vector thrust::device_vector<int> d_vec=h_vec; printf("d_vec init ok!\n"); CHECK(cudaGetLastError()); //给device_vector排序 thrust::sort(d_vec.begin(), d_vec.end()); printf("d_vec sort ok!\n"); //取出倒排的10位存入final_results数组 for (int i = 0; i < topk ; i++) { final_results = d_vec[d_vec.size()-1-i]; } printf("final_results set ok!\n"); /* top_k << <GRID_SIZE, BLOCK_SIZE >> > (source_array, N, _1pass_results, topk); top_k << <1, BLOCK_SIZE >> > (_1pass_results, topk * GRID_SIZE, final_results, topk); CHECK(cudaGetLastError()); */ //CHECK(cudaDeviceSynchronize()); CHECK(cudaEventRecord(stop)); CHECK(cudaEventSynchronize(stop)); float elapsed_time; CHECK(cudaEventElapsedTime(&elapsed_time, start, stop)); CHECK(cudaEventDestroy(start)); CHECK(cudaEventDestroy(stop)); cpu_result_topk(source_array, N, cpu_result); int ok = 1; for (int i = 0; i < topk; ++i) { printf("cpu top%d: %d; gpu top%d: %d \n", i + 1, cpu_result, i + 1, final_results); if (fabs(cpu_result - final_results) > (1.0e-10)) { ok = 0; } } if (ok) { printf("Pass!!!\n"); } else { printf("Error!!!\n"); } printf("GPU Time = %g ms.\n", elapsed_time); return 0; }编译执行：执行没问题。只是，貌似确实有点耗时。主要是代码中先从source_array数组拷贝到 host_vector的h_vec，再从host_vector的h_vec拷贝到device_vector的d_vec，然后再排序的。我们仔细打印下具体时间: printf("\n***********GPU RUN**************\n"); CHECK(cudaEventRecord(start)); //定义host_vector thrust::host_vector<int> h_vec; //遍历source_array,并赋值给host_vector for(int i= 0; i< N; i++) { h_vec.push_back(source_array); } printf("h_vec push ok!\n"); CHECK(cudaGetLastError()); CHECK(cudaEventRecord(stop1)); CHECK(cudaEventSynchronize(stop1)); float elapsed_time; CHECK(cudaEventElapsedTime(&elapsed_time, start, stop1)); printf("h_vec push Time = %g ms.\n", elapsed_time); //定义device_vector,将host_vector复制到device_vector thrust::device_vector<int> d_vec=h_vec; printf("d_vec init ok!\n"); CHECK(cudaGetLastError()); CHECK(cudaEventRecord(stop2)); CHECK(cudaEventSynchronize(stop2)); CHECK(cudaEventElapsedTime(&elapsed_time, stop1, stop2)); printf("d_vec init Time = %g ms.\n", elapsed_time); //给device_vector排序 thrust::sort(d_vec.begin(), d_vec.end()); printf("d_vec sort ok!\n"); CHECK(cudaGetLastError()); CHECK(cudaEventRecord(stop3)); CHECK(cudaEventSynchronize(stop3)); CHECK(cudaEventElapsedTime(&elapsed_time, stop2, stop3)); printf("d_vec sort Time = %g ms.\n", elapsed_time); //取出倒排的10位存入final_results数组 for (int i = 0; i < topk ; i++) { final_results = d_vec[d_vec.size()-1-i]; } printf("final_results set ok!\n"); CHECK(cudaGetLastError()); CHECK(cudaEventRecord(stop4)); CHECK(cudaEventSynchronize(stop4)); CHECK(cudaEventElapsedTime(&elapsed_time, stop3, stop4)); printf("final_results set Time = %g ms.\n", elapsed_time); CHECK(cudaEventDestroy(start)); CHECK(cudaEventDestroy(stop1)); CHECK(cudaEventDestroy(stop2)); CHECK(cudaEventDestroy(stop3)); CHECK(cudaEventDestroy(stop4));重新编译执行：具体时间为：从source_array数组拷贝到 host_vector：206ms从host_vector拷贝到device_vector：89msdevice_vector排序：257ms复制结果到final_results：6ms（以上数据存在抖动的可能性）不过张小白试过想把source_array数组直接拷贝到device_vector，不过没有成功。比如将代码写出这样： float elapsed_time; printf("\n***********GPU RUN**************\n"); CHECK(cudaEventRecord(start)); //定义host_vector /* thrust::host_vector<int> h_vec; //遍历source_array,并赋值给host_vector for(int i= 0; i< N; i++) { h_vec.push_back(source_array); } printf("h_vec push ok!\n"); CHECK(cudaGetLastError()); CHECK(cudaEventRecord(stop1)); CHECK(cudaEventSynchronize(stop1)); CHECK(cudaEventElapsedTime(&elapsed_time, start, stop1)); printf("h_vec push Time = %g ms.\n", elapsed_time); */ //定义device_vector,将host_vector复制到device_vector //thrust::device_vector<int> d_vec=h_vec; thrust::device_vector<int> d_vec; //遍历source_array,并赋值给device_vector for(int i= 0; i< N; i++) { d_vec.push_back(source_array); } printf("d_vec init ok!\n"); CHECK(cudaGetLastError()); CHECK(cudaEventRecord(stop2)); CHECK(cudaEventSynchronize(stop2)); //CHECK(cudaEventElapsedTime(&elapsed_time, stop1, stop2)); CHECK(cudaEventElapsedTime(&elapsed_time, start, stop2)); printf("d_vec init Time = %g ms.\n", elapsed_time); //给device_vector排序 thrust::sort(d_vec.begin(), d_vec.end()); printf("d_vec sort ok!\n"); CHECK(cudaGetLastError()); CHECK(cudaEventRecord(stop3)); CHECK(cudaEventSynchronize(stop3)); CHECK(cudaEventElapsedTime(&elapsed_time, stop2, stop3)); printf("d_vec sort Time = %g ms.\n", elapsed_time); //取出倒排的10位存入final_results数组 for (int i = 0; i < topk ; i++) { final_results = d_vec[d_vec.size()-1-i]; } printf("final_results set ok!\n"); CHECK(cudaGetLastError()); CHECK(cudaEventRecord(stop4)); CHECK(cudaEventSynchronize(stop4)); CHECK(cudaEventElapsedTime(&elapsed_time, stop3, stop4)); printf("final_results set Time = %g ms.\n", elapsed_time); CHECK(cudaEventDestroy(start)); CHECK(cudaEventDestroy(stop1)); CHECK(cudaEventDestroy(stop2)); CHECK(cudaEventDestroy(stop3)); CHECK(cudaEventDestroy(stop4));运行的时候就直接卡死了，也不知道是什么原因：或许哪位大侠知道，可以告知我一下。