开始图论刷题！先把图论的理论和DFS、BFS的代码框架学了下，刷了一道可达路径。要练习ACM模式，利用邻接矩阵构造了图，深搜法（和回溯差不多）找出所有路径，并输出（循环，打印）。昨天实验室聚餐去了，几个月没去见导师，被训了一下午，开始催我们写毕业论文了。晚上二十个人坐了一个大圆桌，幸好我机智，坐在进门靠左的位置，一上菜就能吃到，这小子真抠门啊，酒水自带就算了，连花生米和冲泡的玉米汁粉都带来了。。后面让我们去加菜，我一点不客气的加了肥肠、滋补羊肉、蒜香排骨。菜上来之后说他从来不吃内脏不吃下水，从小就不吃羊肉。。爱吃不吃，反正我爱吃哈哈！

42、接雨水（超经典）：接雨水就是求凹槽的面积，每一列凹槽的面积由它左边的第一个比它高的柱子和右边第一个比它高的柱子决定的，两者的最小值减去当前列的柱子高度即为凹槽的高度，所以很适合用单调栈求解。单调递增栈，如果新元素比栈顶元素小或相等则入栈（下标入栈），说明还没找到右边第一根比它高的柱子；如果新元素比栈顶元素大，则说明找到了栈顶元素的右边第一根比它高的柱子，左边比它高的柱子则已经在栈里了。84、柱状图中最大的矩形：关键是要找到每根柱子左右两边第一个更小的柱子。单调递减栈：当比栈顶元素大或相等则入栈，小则取栈顶元素作为矩形的高度，宽度则为左右两边更小的柱子的下标差。在数组首尾分别加上0，方便计算宽度

单调栈的三道题：739、每日温度：单调栈里只存下标，遍历数组元素与栈顶元素进行比较，若小于等于栈顶元素就入栈（保证栈单调递增），否则得到结果（返回两个下标之差，并继续和栈顶元素（不为空的话）比较）496、下一个更大元素I：数组1是数组2的子集，求数组1的元素值在数组2中的下一个更大的值。利用unordered_map来做映射，方便找出nums2中与nums1相等的值且返回其下标。503、下一个更大元素II：循环数组，所以循环一遍之后，再循环一遍与单调栈（单调递增）中剩余的元素进行比较，这次只取当前元素大于栈顶元素的结果。单调栈的题目的核心都是计算当前结果需要跟它左右两边（任意一边或同时需要）第一次小于/大于它的元素进行比较。

647、回文子串：//动态规划解法：布尔类型的二维dp数组//dp[i][j]：区间范围[i,j]（左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。//递推公式：主要分为s[i]和s[j]相等和不相等的情况//不相等时：dp[i][j] = false;//相等时：//1、i=j时为单个字符，所以dp[i][j] = true//2、j-i=1时为两个相同的字符，所以dp[i][j] = true//3、看dp[i][j]是否为true，可以由dp[i+1][j-1]推导出来//初始化：全初始化为false，后面再去判断更新//遍历顺序：由于dp[i][j]要由dp[i+1][j-1]推导出来，所有i从大到小，j从小到大遍历（因为是字符串区间，所以j一定要大于i）516、回文子序列：//回文子序列不要求连续//dp[i][j]：区间范围[i,j]（左闭右闭）的子串的最长回文子序列//递推公式：主要看s[i]和s[j]是否相等//如果相等，则dp[i][j] = dp[i+1][j-1] + 2;//注意单个字符和两个字符的情况//不相等，则dp[i][j] = max(dp[i+1][j], dp[i][j-1]);//初始化：全初始化为0；//遍历顺序i--,j++

115、不同的子序列：//dp[i][j]：以i-1结尾的字符串s中有多少个以j-1结尾的字符串t//递推公式：删除s中的字符以匹配t。//两元素相等时，可以考虑在s中使用该元素，或者不使用该元素。//if(s[i-1] == t[j-1]) dp[i][j] = dp[i-1][j-1] + dp[i-1][j];//else dp[i][j] = dp[i-1][j];//初始化：dp[i][0]（t为空字符串）初始化为1，dp[0][j](s为空字符串)初始化为0583、两个字符串的删除操作，使得word1与word2相同//两个字符串的删除操作，就相当于找到两个字符串的最长公共子序列//dp[i][j]：长度[0,i-1]的s1和长度[0,j-1]的s2的最长公共子序列的长度72、编辑距离//要将word1转换为word2难点是当两个元素不相等时，分别取增删替操作中最小的//dp[i][j]：以i-1结尾的word1转换成以j-1结尾的word2最小编辑次数//递推公式：主要分为相等和不相等两种情况的操作//if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];//else dp[i][j] = min(dp[i-1][j] + 1,//word1删除当前字符//                    min(dp[i-1][j-1] + 1,//word1替换当前字符//                    dp[i][j-1] + 1))//word1插入一个字符//初始化：dp[i][0](word2为空字符，所以要删掉所有word1的元素)初始化为i//dp[0][j](word1为空字符，所以要插入所有word2的元素)初始化为j

完成了动规子序列的四道题（最长公共子序列和不相交的线其实就算是一道题，判断子序列则是在最长公共子序列的基础上加个判断即可、最大子序和dp[i] = max(dp[i-1]+nums[i], nums[i]); ）。这几道题都不是很难，多想想当前dp值应该由前面哪些值推出来即可。开始学redis了，后面继续workflow，从今天开始边复习基础知识，边准备八股文！加油！

今天完成了三道动规的子序列题，有点难度。最长递增子序列：//dp[i]：下标为i时的最长递增子序列的长度//递推公式：//if(nums[i] > nums[j]) dp[i] = max(dp[j] + 1, dp[i]);//初始化：全初始化为1//遍历顺序，两层for循环，外层i，内层j（j < i）if(nums.size() == 0) return 0;vector<int> dp(nums.size(), 1);int result = 1;for(int i = 1; i < nums.size(); i++){for(int j = 0; j < i; j++){if(nums[i] > nums[j]){dp[i] = max(dp[j] + 1, dp[i]);}}result = max(result, dp[i]);}return result;//不一定是以最后一个元素为结尾时是最长子序列最长连续递增子序列：简单两个数组间的最长重复数组：//dp[i][j]：以i-1为结尾的A和以j-1为结尾的B的最长重复子数组的长度//注意： “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串//递推公式：//if(nums[i] == nums[j]) dp[i][j] = dp[i-1][j-1] + 1;//初始化，全初始化为0，因为dp[i][0],dp[0][j]其实没有意义，而其他的则会被覆盖//遍历顺序：两层for循环if(nums1.size() == 0 || nums2.size() == 0) return 0;vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));int result = 0;for(int i = 1; i <= nums1.size(); i++){for(int j = 1; j <= nums2.size(); j++){if(nums1[i-1] == nums2[j-1])//是i-1，j-1时的元素相等{dp[i][j] = dp[i-1][j-1] + 1;}result = max(dp[i][j], result);//持续记录最大值}}return result;这几天终于把Reactor框架学完了！

继续完成了买卖股票的题（最多交易k次、冷冻期、手续费）最多交易k次：//动态规划，最多只能买卖k次--分情况考虑（奇数持有，偶数卖出）//dp[i][j]：i为第几天，j为状态，奇数时是持有，偶数时是不持有//递推公式：//dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j] - prices[i]);//今天之前就持有了或者今天才买入//dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1] + prices[i]);//昨天就不持有或者今天才卖出//初始化：第0天的所有状态都要初始化，偶数为0，奇数为-prices[0];//遍历顺序：外层遍历天数i，内层遍历j状态.if(prices.size() == 0) return 0;vector<vector<int>> dp(prices.size(), vector<int>(2*k+1, 0));for(int j = 1; j < 2*k; j+=2)//更新奇数情况下第0天的值{dp[0][j] = -prices[0];}for(int i = 1; i < prices.size(); i++){for(int j = 0; j < 2*k-1; j+=2){dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j] - prices[i]);dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1] + prices[i]);}}return dp[prices.size() - 1][2*k];冷冻期：//动态规划--不限交易次数，但有冷冻期，即卖出的第二天不能操作//分情况考虑--持有、不持有、冷冻期//递推公式：//持有：昨天已持有、今天买昨天之前就卖了、今天买昨天冷冻期//dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i], dp[i-1][3] + prices[i]);//不持有：保持卖出状态(前一天就是保持卖出状态，或者前一天是冷冻期)//dp[i][1] = max(dp[i-1][1], dp[i-1][3]);//不持有：今天卖//dp[i][2] = dp[i-1][0] + prices[i];//冷冻期：昨天卖//dp[i][3] = dp[i-1][2];//初始化：第0天全初始化为0if(prices.size() == 0) return 0;vector<vector<int>> dp(prices.size(), vector<int>(4, 0));dp[0][0] = -prices[0]; // 持股票for(int i = 1; i < prices.size(); i++){dp[i][0] = max(dp[i-1][0], max(dp[i-1][1] - prices[i], dp[i-1][3] - prices[i]));dp[i][1] = max(dp[i-1][1], dp[i-1][3]);dp[i][2] = dp[i-1][0] + prices[i];dp[i][3] = dp[i-1][2];}return max(dp[prices.size() - 1][1], max(dp[prices.size() - 1][2], dp[prices.size() - 1][3]));手续费：简单，在卖出时再减去手续费就行。

买卖股票的三道题（最多交易1次，2次，不限次数）--动态规划法最多交易1次：//动态规划解题（其实贪心会更简单）//dp[i][0]:第i天持有股票的最大利润（持有不代表今天买入）//dp[i][1]:第i天不持有股票的最大利润//递推公式：//当天仍然持有，要么是前面买入的，要么是今天刚买入的//dp[i][0] = max(dp[i-1][0], -prices[i]);//当天不再持有，要么是前面就已经不持有（没买过或者已经卖了），要么是今天卖了//dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);//初始化：dp[0][0] = -prices[0]; dp[0][1] = 0;交易不限次数：与交易1次唯一不同的点是//当天仍然持有，要么是前面买入的，要么是今天刚买入的(今天可能不是第一次买了)//dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]);最多交易两次：//动态规划，最多只能买卖两次--分情况考虑//每天可能处在5种状态//dp[i][0]：没有操作（其实可以不写，后面4种情况包含了当天啥也没干的情况）//dp[i][1]：第一次持有股票，要么今天刚买入，要么前面已经买入，但还没卖过//dp[i][2]：第一次不持有，要么今天第一回卖出，要么前面已经卖了一回了，今天啥也没干//dp[i][3]：第二次持有，要么今天第二次买入，要么前面已经买了第二次了，到今天还没卖//dp[i][4]：第二次不持有，要么今天第二次卖出，要么前面已经卖第二次了，今天啥也没干//递推公式：dp[i][0] = dp[i-1][0];dp[i][1] = max(-prices[i], dp[i-1][1]);dp[i][2] = max(dp[i-1][1] + prices[i], dp[i-1][2]);dp[i][3] = max(dp[i-1][2] - prices[i], dp[i-1][3]);dp[i][4] = max(dp[i-1][3] + prices[i], dp[i-1][4]);//初始化：dp[0][0] = 0; dp[0][1] = -prices[0]; dp[0][2] = 0;//今天买今天卖//dp[0][3] = -prices[0];今天第二回买。dp[0][4] = 0;//今天第二回卖

打家劫舍三道题：街道题递推公式：dp[i] = max(dp[i-2] + nums[i], dp[i-1])（当前这户偷还是不偷）；围城题就要分两种情况去考虑，分别是不含首元素，和不含尾元素，其它和前面一致；二叉树题比较难，如下：vector<int> traversal(TreeNode* cur){vector<int> dp(2, 0);//递归出口if(cur == nullptr) return {0, 0};//左vector<int> leftdp = traversal(cur->left);//右vector<int> rightdp = traversal(cur->right);//中//不偷当前结点，那么就要考虑偷左右孩子结点（不是一定偷，主要是取最大值）int val1 = max(leftdp[0], leftdp[1]) + max(rightdp[0], rightdp[1]);//偷当前结点，那么左右孩子结点一定不能偷了int val2 = cur->val + leftdp[0] + rightdp[0];return {val1, val2};}int rob(TreeNode* root) {//打家劫舍二叉树//递归采用后序遍历的方式，因为决定偷不偷当前结点是由左右子节点偷不偷决定的//定义一个包含两个元素的一维dp数组(每层递归里都有个dp数组)//dp[0]表示不偷当前结点盗取的最大金额，dp[1]表示偷当前结点盗取的最大金额//递归函数最后返回的也是一个dp数组，表示偷不偷根节点（所有子节点都遍历完了）vector<int> result = traversal(root);return max(result[0], result[1]);}

动规题刷出一点手感了！这几天把面向对象的PC、基于对象的PC、面向对象的线程池封装、基于对象的线程池封装、以及C++11线程库函数实现以上PC封装、线程池封装的代码都敲了一遍。

对动规题目有点感觉了！

动规好难，打起精神来，坚持刷完一遍！

面试，感觉凉了。。