专题训练整合
为了提升自己的码力，我会去做一些LeetCode上的专题练习，我认为它们都很有价值，于是专门开一篇文章来记录我刷专题的痕迹。 以下内容按时间升序排列。 dp专题训练查找表类算法专题训练二叉树专题训练数组与字符串专题训练
LeetCode专题训练：数组和字符串
传送门 之前忙着开学，有相当一段时间没有做题了，实在是罪过... 数组 t1寻找数组的中心索引 找到数组中的一个位置，这个位置之前的所有元素和等于这个位置之后的所有元素和。如果没有就返回-1。 感觉思路有点滑动窗口的味道。维护两个变量lsum与rsum，分别表示当前位置左边的元素和与右边的元素和，然后根据题意O(n)遍历判断就行了。 ```cpp class Solution { public: int pivotIndex(vector& nums) { int rsum = 0, lsum = 0; const int n = nums.size(); if(n == 0) return -1; for(auto& el: nums) rsum += el; rsum -= nums[0]; if(rsum == 0) return …
LeetCode专题训练-二叉树
这次要记录的是做leetbook：二叉树的经历，这是一本很小的book，所以决定用一晚上的时间做完。传送门 树的遍历 t1 二叉树的先序遍历 常规操作，简单题要做难，所以考虑用多种方法来写。 递归法 最常规的递归法，按照根->左->右的顺序来写就可以了。 ```cpp class Solution { public: void solve(TreeNode*root, vector& a) { if(root == NULL) return; a.push_back(root->val); solve(root->left, a); solve(root->right, a); } vector preorderTraversal(TreeNode* root) { vector ans; solve(root, ans); return ans; } }; ``` 迭代法 迭代法是用栈模拟递归的操作。因为栈具有先入后弹的特性，所以优先压右儿子进栈。 ```cpp class Solution …
LeetCode专题训练：查找表类算法
LeetBook传送门 LeetCode最近一次更新中更新了大量高质量的LeetBook，做起来很舒心，于是打算开一些博文来记录我刷Book的经历。 集合set的使用 t1两个数组的交集 求两个集合的交集，重复元素计算一次。 思路很简单，C++里set元素具有唯一性，所以用两个set给两个数组去重再求交集即可。 ```cpp class Solution { public: vector intersection(vector& nums1, vector& nums2) { setset1; setset2; vector ans; for(int i = 0; i < nums1.size(); i++) set1.insert(nums1[i]); for(int i = 0; i < nums2.size(); i++) set2.insert(nums2[i]); set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), back_inserter(ans)); return …
dp完全掌握计划
动态规划是一个非常非常重要的算法。众所周知LeetCode周赛中十hard九dp，接触算法那么多年，动态规划始终没有做到完全的掌握，趁着这月LeetCode周赛的主题是dp，也争取完全掌握这门 算法。 内容会不定期更新，初步目标二十道，由易到难。 LeetCode-121:买卖股票的最佳时机 传送门 lc上的dp老题了，其实它只是借用了dp思想而已，和传统的dp有一点点差别。 首先考虑暴力做法。题意不难理解，找出数组中差值最大的两个数，输出他们的差值，要求较小数的下标要小于较大数。那么可以很简洁的写出一个直译： ```cpp class Solution { public: int maxProfit(vector& prices) { int n = prices.size(); int ans = 0; for(int i = 0; i < n; i++) for(int j = i; j < n; j++) ans = max(prices[j]-prices[i], ans); return …