力扣106-数据结构经典作业:从中序与后序遍历序列构造二叉树 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。 示例1 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 输出：[3,9,20,null,null,15,7] 示例2 输入：inorder = [-1], postorder = [-1] 输出：[-1] 提示： 1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorder 和 postorder 都由 不同 的值组成postorder 中每一个值都在 inorder 中inorder 保证是树的中序遍历postorder 保证是树的后序遍历力扣题目链接思路写代码之前我们要先保证自己能过根据中序遍历&后序遍历构造出原二叉树： 以后序遍历数组的最后一个元素为切割点，先切割中序遍历数组，然后根据中序遍历数组切割后序遍历数组。如此往复，每次后续数组中的最后一个元素为切割点。当数组大小为1时，直接返回其值为该子树根节点。（分割后的前段构造左子树，后段构造右子树） 示例1流程如下： 中序：9，3，15，20，7 后序：9，15，7，20，3 后续数组最后一个元素为： 3 切割之后 中序前段：9 中序后段：15，20，7 后序前段：9 后序后段：15，7，20 此时应当注意到中序数组切割与后序数组切割后的大小是相同的 前段数组长度为1则直接返回，继而对后段数组对进行重复操作切割点为：20 中序前段：15 中序后段：7 后序前段：15 后序后段：7 前后段数组元素数都为 1 ，二叉树构造完成 3 / \ 9 20 / \ 15 7图示可能更好理解（图源：代码随想录 点击前往 ） 代码实现很明显，这是一个递归的逻辑；我们采取的是前序遍历，首先确定中间节点，然后递归构造左、右子树。那么下面我们按照递归三要素一步步来实现代码。首先确定递归函数的参数和返回值传入中后续遍历数组，返回指向节点的指针。TreeNode* traversal (vector<int>& inorder, vector<int>& postorder)确定终止条件如果遍历数组为空，那么直接返回null，表示该子树为空如果遍历数组中只有一个元素，那么该节点为叶子节点，该子树构造完成，直接返回if(postorder.size() == 0) { return nullptr; } int rootValue = postorder[postorder.size() - 1]; TreeNode* node = new TreeNode(rootValue); if(postorder.size() == 1){ return node; }确定单层遍历逻辑找到切割点，即后序遍历数组最后一个元素,并切割中序、后序遍历数组int delimitIndex; for(delimitIndex = 0; delimitIndex < inorder.size(); delimitIndex++){ if(inorder[delimitIndex] == rootValue){ break; } } vector<int> leftInorder (inorder.begin(),inorder.begin() + delimitIndex); vector<int> rightInorder (inorder.begin() + delimitIndex + 1, inorder.end()); postorder.resize(postorder.size() - 1);//舍弃后序遍历数组末尾元素，作为分割点已经参与构造 vector<int> leftPostorder (postorder.begin(),postorder.begin() + leftInorder.size()); vector<int> rightPostorder (postorder.begin() + leftInorder.size(), postorder.end());这里需要特别注意数组切割的边界值问题，一定要使用一致的划分原则。上述代码中我使用的是左闭右开级 [0, delimiterIndex)接下便可以进入递归逻辑node->left = traversal(leftInorder,leftPostorder); node->right = traversal(rightInorder,rightPostorder);下面是完整代码class Solution { private: TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) { if (postorder.size() == 0) return NULL; // 后序遍历数组最后一个元素，就是当前的中间节点 int rootValue = postorder[postorder.size() - 1]; TreeNode* root = new TreeNode(rootValue); if (postorder.size() == 1) return root; // 找到中序遍历的切割点 int delimiterIndex; for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) { if (inorder[delimiterIndex] == rootValue) break; } // 切割中序数组 // 左闭右开区间：[0, delimiterIndex) vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex); // [delimiterIndex + 1, end) vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() ); // postorder 舍弃末尾元素 postorder.resize(postorder.size() - 1); // 切割后序数组 // 依然左闭右开，注意这里使用了左中序数组大小作为切割点 // [0, leftInorder.size) vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size()); // [leftInorder.size(), end) vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end()); root->left = traversal(leftInorder, leftPostorder); root->right = traversal(rightInorder, rightPostorder); return root; } public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { if (inorder.size() == 0 || postorder.size() == 0) return NULL; return traversal(inorder, postorder); } };

双指针法-力扣151 反转字符串中的单词 力扣151-反转字符串中的单词 给定一个字符串，逐个翻转字符串中的每个单词。示例 1：输入: "the sky is blue"输出: "blue is sky the"示例 2：输入: " hello world! "输出: "world! hello"解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。示例 3：输入: "a good example"输出: "example good a"解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。提示：1 <= s.length <= 10^4s 包含英文大小写字母、数字和空格 ' 's 中 至少存在一个单词思路首先剔除字符串中多余的空格，多余的空格存在于字符串开头、末尾以及中间两个或以上连续的空格。开头和末尾的空格直接去除即可，而中间连续空格则需要保留一个。第二步，将整个字符串反转。如此，实现了各单词整体位置上的反转。那么最后便是将各单词内部字母反转。代码实现在这里我们实现一种时间复杂度为O(n)，空间复杂度为O(1)(原地对字符串进行修改，不额外分配空间)为实现原地进行修改，我们用到双指针法。定义快慢指针，快指针赋值为字符串中第一个非空格下标，慢指针为字符串开头。使用快指针遍历字符串，判断值是否符合要求。符合则将其存入慢指针，同时，慢指针移动最后判断遍历完成后的字符串尾部是否存在多余空格，若存在则将其去除。并更新字符串长度。int fast = 0, slow = 0; while(s.size() > 0 && fast < s.size() && s[fast] == ' ' ){ fast++; } for(;fast < s.size(); fast++){ if(fast - 1 > 0 && s[fast-1] == ' ' && s[fast] == ' '){ continue; }else{ s[slow++] = s[fast]; } } if(s[slow-1] == ' ' && slow -1 >0){ s.resize(slow-1); }else{ s.resize(slow); }反转整个字符串，可以自行编写，也可调用库函数，这不是本题的重点所在。对单词内部字母的反转，只需要考虑好什么时候对哪一部分进行反转。这里我使用一种相似于双指针的方法。快慢指针同时指向字符串开头，快指针对字符串进行遍历。当快指针遍历元素为空格时，对慢指针到快指针-1的元素进行反转，同时慢指针改为指向快指针+1。for(int start = 0,end = 0; end <= s.size(); end++){ if(s[end] == ' ' || end == s.size()){ reserve(s,start,end-1); start = end+1; } }下面是可以在力扣网站中直接提交通过的完整代码class Solution { public: string reverseWords(string s) { int fast = 0, slow = 0; while(s.size() > 0 && fast < s.size() && s[fast] == ' ' ){ fast++; } for(;fast < s.size(); fast++){ if(fast - 1 > 0 && s[fast-1] == ' ' && s[fast] == ' '){ continue; }else{ s[slow++] = s[fast]; } } if(s[slow-1] == ' ' && slow -1 >0){ s.resize(slow-1); }else{ s.resize(slow); } reserve(s,0,s.size()-1); for(int start = 0,end = 0; end <= s.size(); end++){ if(s[end] == ' ' || end == s.size()){ reserve(s,start,end-1); start = end+1; } } return s; } private: void reserve(string& s,int start,int end){ for(int i = start, j = end; i < j; i++, j--){ swap(s[i],s[j]); } } };总结其实在各种高级语言中有很多功能强大的库函数，我们应该熟悉这些库函数，但是在我们做算法题时应该考虑使用库函数对题目的影响。如果库函数只能解决题目中的一小步，或者你对这个库函数的内部运作原理已经非常熟悉，那么直接调用也无伤大雅。例如题解中的reserve函数是我自行编写的，没有调用库函数，是因为我想要加强一下对反转操作的印象。(我刚在 反转字符串 以及 反转字符串II 两题中使用) 但是reserve函数中我却调用了swap函数进行互换，因为我认为我对swap函数的认识已经足够清晰，同时这也显然不是本题的意图所在。事实上，如果使用Python，本题仅用几行代码即可解决。另外，在C++中可以使用erase直接删除字符串中元素，但是时间复杂度会有所变化。

梦开始的地方-力扣001 两数之和 力扣001题-两数之和 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。示例:给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]暴力解法看到题目第一眼想到的是嵌套循环，很简单，代码如下：class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { for(int i = 0; i<nums.size(); i++){ for(int j = 0; j<nums.size(); j++){ if(nums[i]+nums[j] == target && i!=j){ return {i,j}; } } } return {}; } };显然双循环写法时间复杂度为O(n^2),下面我们来看一种时间复杂度为O(n)的解法。哈希表法这种解法我们利用C++中unordered_map这种数据结构的哈希表底层实现，以O(n)时间复杂度来解出这题。首先，我们要知道什么是哈希表。哈希表是根据关键码的值而直接进行访问的数据结构。这种说法可能难以理解，简单地说，数组其实也是一种哈希表。数组的下标就是它的关键码，通过下标的值可以直接访问其数据。常见的哈希结构有三种：数组、unordered_set、unordered_map。本题使用unordered_map,那么为什么选择这种结构呢？数组：大小固定，当元素很少而哈希值很大时将会造成内存浪费unordered_set:是一个集合，只能存放key值，而本题既要判断某值是否存在还要记录它的下标unordered_map:key value存储结构，本题中用key保存数值，用value保存其下标思路遍历数组，判断map中是否存在与当前遍历元素相加等于target的元素。有，则返回下标；无，则将当前遍历元素存入map。代码如下：class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { std::unordered_map<int,int> map; for(int i = 0; i<nums.size(); i++){ auto temp = map.find(target-nums[i]); if(temp != map.end()){ return {temp->second,i}; } map.insert(pair<int,int>(nums[i],i)); } return {}; } };总结什么时候应该想到使用哈希表？当我们需要查询一个元素是否出现过或是否存在于某个集合，我们就应该想到使用哈希表。本题中，我们需要一个集合来存放遍历过的元素，在遍历过程中我们又需要判断某元素是否是否遍历过，即判断某元素是否存在于集合。

Day01-力扣59 螺旋矩阵 力扣题目地址 给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 这题并不涉及什么算法和思想，但是很考验对代码掌握程度。看似简单，但要完整的写出运行免不了磕碰。 首先要确定遍历每一条边时边界的选择，最好每条边采取一致的边界处理。这里我选择的是每一条边保留最后一个作为下一条边的开始，例如n=4,第一条边遍历只处理nums0至nums0，第二条边处理nums0至nums2;如此往复。 例外需要注意的是，当n为奇数时，矩阵中央会剩余一个需要另外进行赋值。class Solution { public: vector<vector<int>> generateMatrix(int n) { int startx=0,starty=0;//遍历从何处开始 int offset=1;//遍历从何处结束 int loop=n/2;//需要进行多少次画圈循环 int count=1; vector<vector<int>> nums(n, vector<int>(n, 0));//定义一个二维数组 int i,j; int temp=n%2; while(loop--){ i=startx; j=starty; //每一行/列都保留最后一个给下一行/列处理 for(j=starty;j<n-offset;j++){ nums[startx][j]=count++; } for(i=startx;i<n-offset;i++){ nums[i][j]=count++; } for(;j>starty;j--){//此时i，j都已经到达正确位置（即矩阵中右下角）不需要进行处理 nums[i][j]=count++; } for(;i>startx;i--){ nums[i][j]=count++; } startx++; starty++; offset+=1; } if(temp==1){ nums[n/2][n/2]=count; } return nums; } };