1.数据结构的存储方式数据结构的存储方式只有两种：数组（顺序存储）和链表（链式存储）。这句话怎么理解，不是有哈希表、栈、队列、堆、树、图等数据结构吗？我们在分析问题的时候，一定要有递归的思维，从上到下，从抽象到具体。你就列举了这么多，那些属于“上层建筑”，而数组、链表是“结构基础”。因为那些多样化的数据结构来源于对链表或者数组的特殊操作，API也不一样。例如，“队列”和“栈”这两个数据结构可以使用链表或数组来实现。用数组实现，需要处理扩缩容问题；用链表实现，没有这个问题，但是需要更多的内存空间来存放节点指针。“图”有两种表示方式，邻接表是链表，邻接矩阵是二维数组。邻接矩阵判断连通性比较快，可以进行矩阵运算来解决一些问题，但是如果图比较稀疏的话，非常耗空间。邻接表比较节省空间，但是很多操作的效率肯定不如邻接矩阵。“哈希表”就是通过哈希函数把key映射成一个大数组。而对于解决hash冲突的方法，zipper方法需要链表的特性，操作简单，但是需要额外的空间来存放指针；线性探索法需要数组的特性进行连续寻址，不需要指针的存储空间，但运算稍微复杂一些。一些。“树”，用数组实现的是“堆”，因为“堆”是一棵完全二叉树，不需要节点指针存放在数组中，操作比较简单；用链表实现的是一种很常见的“树”，因为它不一定是完全二叉树，所以不适合数组存储。为此，在这种链表“树”结构之上，衍生出各种巧妙的设计，如二叉搜索树、AVL树、红黑树、区间树、B树等，以应对不同的问题.了解Redis数据库的朋友可能也知道，Redis提供了列表、字符串、集合等几种常见的数据结构，但是对于每一种数据结构，至少有两种底层存储方式，所以根据实际情况存储数据使用适当的存储方法。总结一下，数据结构有很多种，你甚至可以发明自己的数据结构，但底层存储无非就是数组或者链表。两者的优缺点如下：由于数组紧凑连续存储，可以随机访问，通过索引可以快速找到对应的元素，相对节省存储空间。但是因为连续存储，内存空间必须一次性分配足够，所以如果数组需要扩展，需要重新分配更大的空间，然后复制所有数据，时间复杂度为O(N);插入和删除都在数组中间进行，每次都要移动所有后续数据以保持连续性，时间复杂度为O(N)。因为链表的元素不是连续的，而是指针指向下一个元素的位置，所以不存在数组扩容的问题；如果知道一个元素的前驱和后驱，就可以通过操作指针删除该元素或插入新元素，耗时O(1)度。但是正因为存储空间不连续，无法根据索引计算出对应元素的地址，所以不能随意访问；并且由于每个元素都必须存储指向前后元素位置的指针，所以会消耗相对较多的存储空间。2、数据结构的基本操作对于任何数据结构，其基本操作无非就是遍历+访问，更具体地说：增、删、查、改。数据结构的种类很多，但它们的目的都是在不同的应用场景下尽可能高效地进行增删改查。也就是说，这不就是数据结构的使命吗？如何遍历+访问？我们还是看最高层。各种数据结构的遍历+访问无外乎两种形式：线性和非线性。线性用for/while迭代表示，非线性用递归表示。更具体的一步，无非就是以下几个框架：数组遍历框架，典型的线性迭代结构：voidtraverse(int[]arr){for(inti=0;ileft));intright=max(0,oneSideMax(root->right));ans=max(ans,left+right+root->val);returnmax(left,right)+root->val;}你看，这是后序遍历。LeetCode105题，难度中等，让你根据前序遍历和中序遍历的结果恢复一棵二叉树，是一道经典题，主要代码如下：TreeNodebuildTree(int[]preStart,intpreStart,intpreEnd,int[]inorder,intinStart,intinEnd,MapinMap){if(preStart>preEnd||inStart>inEnd)returnnull;TreeNoderoot=newTreeNode(preorder[preStart]);intinRoot=inMap.get(root.val);intnumsLeft=inRoot-inStart;root.left=buildTree(preorder,preStart+1,preStart+numsLeft,inorder,inStart,inRoot-1,inMap);root.right=buildTree(preorder,preStart+numsLeft+1,preEnd,inorder,inRoot+1,inEnd,inMap);returnroot;}别看这个函数的参数很多，只是为了控制数组索引，该算法本质上是一种前序遍历。LeetCode99题，难度Hard，还原一个BST，主要代码如下：voidtraverse(TreeNode*node){if(!node)return;traverse(node->left);if(node->valval){s=(s==NULL)?prev:s;t=node;}prev=node;traverse(node->right);}这不就是中序遍历吗，对于一个BST中序遍历意味着什么，应该不需要解释。你看，Hard难度的称号也不过如此，还有这样的规则可循。你只需要写出框架，然后在相应的位置添加东西即可。这不就是思维方式吗？对于一个懂二叉树的人来说，解决一个二叉树问题并不需要很长时间。所以如果做题不知道怎么做或者害怕，不妨从二叉树开始。前10个问题可能有点难受；结合框架，再做20道题，或许你就有了一点自己的理解；做完整个题目，下一步做什么回到分而治之的题目，你会发现只要涉及到递归问题，就是树问题。再举个例子，说一下我们之前文章写的一些题。动态规划的详解中提到了找零的问题。暴力解就是遍历N叉树：defcoinChange(coins:List[int],amount:int):defdp(n):ifn==0:return0ifn<0:return-1res=float('INF')forcoinincoins:subproblem=dp(n-coin)#子问题无解，跳过ifsubproblem==-1:continueres=min(res,1+subproblem)returnresifres!=float('INF')else-1returndp(amount)What这么多代码看不懂怎么办？把框架抽出来，可以看出核心思想：#只是一个N叉树的遍历问题defdp(n):forcoinincoins:dp(n-coin)其实很多动态规划问题都是遍历一棵树。如果你熟悉树的遍历操作，至少你知道如何将想法转化为代码，你也知道如何从别人的解决方案中提炼出核心思想。让我们再看看回溯算法。上一篇回溯算法的详解简单的说回溯算法就是遍历一棵N叉树的前后遍历的问题，无一例外。比如N皇后问题，主要代码如下：voidbacktrack(int[]nums,LinkedListtrack){if(track.size()==nums.length){res.add(newLinkedList(track））;返回;}for(inti=0;itrack){for(inti=0;i
