LeetCode刷题-127. 单词接龙
题目链接：127. 单词接龙
¶题解：
是上一道题的简化版，只需要记录方案数即可！
¶题目简述：
和上一题一样，给定起始和终止单词和一个字典，求每次只能改变一个单词并且该单词存在于字典可以到达终止单词的方案数！
¶题解：
具体见上一题： 可以通过博客上方搜索功能搜索或者使用文章下方上一篇按钮跳转！
由于只需要记录方案数，所以我们只需要上一道题的最短路的过程即可，即只需要BFS并在中途计数既可！
最终答案：if(t == endWord) return dist[t];
时间复杂度：同样见上一题分析，为O(26nL^2 + nL)即O(nL^2)
¶AC代码：
12345678910111213141516171819202122232425262728class Solution {public: int ladderLength(string beginWord, string endWord, vector<string>& wordList) { unordered_set<string> S; unord ...
LeetCode刷题-126. 单词接龙 II
题目链接：126. 单词接龙 II
¶题解：
是一道难题，DFS和BFS的结合使用！
¶题目简述：
给定两个不一样的单词和一个字典，找到所有从一个单词到另一个单词的序列！
单词的变化每次转换只能改变一个字母，字典中不一定存在起始单词！
¶题解：
这道题本质是一道求最短路的问题：即从起始单词到结束单词的最短路，并且边权为一，可以使用BFS来求最短路！
这道题不仅仅要求最短路的长度，而是要记录出所有最短路的路径，这里需要使用DFS来搜索路径！
关于建图方法： 假设单词数为n，单词长度为L
枚举所有单词，判断两两单词（n^2）是否只有一位不同（L），为 n^2L
枚举每个单词，每个单词的每一位（26nL）判断是否只有一位不同，哈希表优化判断存在或使用过，为 26nL^2
简单计算： 当26L < n 时，使用第二种，否则使用第一种，本题的数据为n > 26L，所以要使用第二种，否则超时
进入正题！！！本题思路：
DFS + BFS：
使用BFS来求一个dist数组，表示当前点到起始点的最短路径长度
使用第二种建图方式，即要枚举每一位的二十六种变化即可，若该点在字 ...
LeetCode刷题-125. 验证回文串
题目链接：125. 验证回文串
¶题解：
简单回文串的验证！
¶题目简述：
验证一个字符串是不是回文串，只考虑数字和大小写字母！
¶题解：
简单双指针：
一个指针从前向后，一个指针从后向前
遇到不少字母和数字则向后或向前移动
由于题目忽略大小写的存在，我们将其全部转化为小写字母比较即可！
注意：
tolower() 和 toupper()：位于cctype或ctype.h头文件
时间复杂度：O(n)
¶AC代码：
1234567891011121314class Solution {public: bool check(char c){ return c >= '0' && c <= '9' || c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z'; } bool isPalindrome(string s) { for(int i = 0, j = s.size() - 1; i < j; i++ ...
LeetCode刷题-124. 二叉树中的最大路径和
题目链接：124. 二叉树中的最大路径和
¶题解：
很是巧妙的递归求解路径问题！
¶题目简述：
非空二叉树返回最大路径和！路径定义为从任意一个节点出发到任意一个节点序列！
¶题解：
思考： 如何将所有路径遍历全面（注意：路径是任意点到任意点，不一定是要经过根节点或者叶子节点）！
对于一条路径，该路径的最高点是一定的，所以我们来枚举它的最高点！
对于该最高点的路径有几种情况：res = max(res, left + root->val + right)
根节点
根节点和左子树最大值
根节点和右子树最大值
根节点和左右子树最大值
对于计算左右子树的最大值：
int dfs(TreeNode* root)：计算当前根节点的最大路径
return root->val + max(left, right)：返回根节点和左右子树最大值的和
left = max(0, dfs(root->left))：保证往下走是可以增大路径的，和0取一下max。若为负值，即不走当前路径
right = max(0, dfs(root->right))：同理
时间复杂度 ...
LeetCode刷题-123. 买卖股票的最佳时机 III
题目链接：123. 买卖股票的最佳时机 III
¶题解：
上一题的再次进阶版！
¶题目简述：
给定一个序列，从中选择两次交易（保证：后者大于前者，并且下一次交易前必须把当前股票卖出），求其最大值作为股票的最大利润！
上上一题只能交易一次，上一题可以交易多次，这题只能交易两次！
¶题解一：较好理解的
贪心 + 动态规划：
贪心解释： 将区间按每个点分为两部分，每部分计算一下只交易一次的最大收益，最终答案就是每个点分为的两部分和的最大值！
状态表示： l和r数组分别表示区间为0 ~ i和i + 1 ~ n - 1交易一次的最大收益！
状态计算：
对于l[i]：就是前面0 ~ i - 1的最小值和当前值的差
对于r[i]：就是后面i + 2 ~ n - 1的最大值与当前值的差
最终答案： max(res, l[i] + r[i])
注意：
l和r数组的区间范围
时间复杂度： O(n)
空间复杂度： O(n)
¶AC代码一：
123456789101112131415161718192021// i为第一段的末尾下标 0 ~ i i + 1 ~ n - 1class Solu ...
LeetCode刷题-122. 买卖股票的最佳时机 II
题目链接：122. 买卖股票的最佳时机 II
¶题解：
上一题的进化版！
¶题目简述：
给定一个序列，从中选择多次两点（保证：后者大于前者，并且下一次交易前必须把当前股票卖出），求其最大值作为股票的最大利润！
上一题只能交易一次，这题可以交易多次！
¶题解：
**贪心：**类似上一题
首先给出结论： 一个区间的交易可以拆分为单天的交易！
证明：
1234假设i,j,k三点，i < j < k，对于区间[i, j],[j, k]，以及[i, k]，可以发现：他们的收益分别为 j - i + k - j 和 k - i会发现是一样的！所以：一个区间的收益，可以简化为每一天的收益和！
要想使得股票收益最大，我们只需要将单天收益为正值的累加起来即可！即res += max(0, prices[i] - prices[i - 1])
时间复杂度：O(n)
¶AC代码：
123456789class Solution {public: int maxProfit(vector<int>& prices) { int res = 0; ...
LeetCode刷题-121. 买卖股票的最佳时机
题目链接：121. 买卖股票的最佳时机
¶题解：
简单的贪心问题！
¶题目简述：
给定一个序列，从中选择两点（保证：后者大于前者），求其最大值作为股票的最大利润！
¶题解：
贪心： res表示0 ~ i区间的最大股票收益，minv表示该区间的最小值。
求最大值，则当前区间的最小值和当前区间的最后一个值的差自然就是该区间的最大股票收益了，遍历一遍该数组即可得到最大股票收益！
得到1 ~ i - 1的最小值minv
做差即可：price[i] - minv
时间复杂度：O(n)
¶AC代码：
1234567891011class Solution {public: int maxProfit(vector<int>& prices) { int res = 0, minv = INT_MAX; for(int i = 0; i < prices.size(); i++){ res = max(res, prices[i] - minv); minv = min(minv, p ...
LeetCode刷题-120. 三角形最小路径和
题目链接：120. 三角形最小路径和
¶题解：
简单动态规划题！
¶题目简述：
给定一个三角形，求自顶向下的最小路径！
¶题解：
动态规划：
状态表示： 使用原数组f[i][j]表示该位置到达最底部的最小距离！
状态计算： 只能移动到下一行正下方和右下方，所以该值为f[i][j] += min(f[i + 1][j], f[i + 1][j + 1])，即当前值加上从最下面到达当前层的下一层的距离！
最终答案： f[0][0]
注意： 最后一行不必处理！处理也可以！
时间复杂度：O(n^2)
空间复杂度：O(1)
¶AC代码：
12345678910class Solution {public: int minimumTotal(vector<vector<int>>& f) { int n = f.size(); for(int i = n - 2; i >= 0; i--) for(int j = 0; j <= i; j++) f[i][j] ...
LeetCode刷题-119. 杨辉三角 II
题目链接：119. 杨辉三角 II
¶题解：
类似于上一个杨辉三角！
¶题目简述：
赶回第k行杨辉三角，要求空间O(k)
¶题解一：普通版
思路：
为了省空间到O(k)，我么使用滚动数组解决
一个数组记录上一层，一个数组记录下一层，来回滚动即可
时间复杂度：O(n^2)
¶AC代码一：
123456789101112131415class Solution {public: vector<int> getRow(int rowIndex) { vector<int> res, last; for(int i = 0; i <= rowIndex; i++){ res.clear(); for(int j = 0; j <= i; j++){ if(!j || j == i) res.push_back(1); else res.push_back(last[j] + last[j - 1]); ...
LeetCode刷题-118. 杨辉三角
题目链接：118. 杨辉三角
¶题解：
简单的杨辉三角！
¶题目简述：
给定一个数，生成杨辉三角的那几行！
¶题解：
递推：
对于每一行第一个和最后一个都是1，即!j || j == i
其他数字，都等于该数正上方和左上方的和，即res[i - 1][j - 1] + res[i - 1][j]
时间复杂度：O(n^2)
¶AC代码：
123456789101112131415class Solution {public: vector<vector<int>> generate(int numRows) { vector<vector<int>> res; for(int i = 0; i < numRows; i++){ vector<int> level; for(int j = 0; j <= i; j++){ if(!j || j == i) level.push_back(1); ...
LeetCode刷题-117. 填充每个节点的下一个右侧节点指针 II
题目链接：117. 填充每个节点的下一个右侧节点指针 II
¶题解：
上一题的进阶版，二叉树变得更加的普通！
¶题目简述：
给定一棵非常普通的二叉树，每个节点多一个next指针，我们需要将其指向同一行紧挨着的下一个节点！
要求空间O(1)
¶题解：
不要求空间则可以通过简单BFS实现！
和上一题思想类似： 不过这个题我么无法直接通过上一层来找到下一层的对应关系，但是我们可以对下一层进行构造横向链表！
若下一层存在：构建虚拟头结点以及尾指针，进行尾插法形成下一层单链表
若上一层节点左儿子存在，则尾插法插入该节点
若上一层节点右儿子存在，则尾插法插入该节点
走向下一层，cur = head->next，由于head为虚拟头节点
时间复杂度：同样每个节点遍历一次，为O(n)
¶AC代码：
12345678910111213141516171819202122232425262728293031323334/*// Definition for a Node.class Node {public: int val; Node* left; Node* ...
LeetCode刷题-116. 填充每个节点的下一个右侧节点指针
题目链接：116. 填充每个节点的下一个右侧节点指针
¶题解：
类似链表的操作题！
¶题目简述：
给定一个二叉树，该二叉树每个节点多一个next指针用来横着指向下一个节点！
要求：空间O(1)
¶题解：
类似BFS：
该题要求空间O(1)，所以使用很简单的栈实现的BFS就不能使用了！
思路：
若下一层存在，则通过上一层的每个节点p来链接下一层之间的关系：
先连接上一层根节点的左儿子为其右儿子，即 p->left->next = p->right
若上一层有后一个节点：（即此时为两个父亲四个儿子正中间的情况），即p->right->next = p->next->left
接下来，走到下一层，即level = level->left
时间复杂度：每个节点遍历一次为O(n)
¶AC代码：
123456789101112131415161718192021222324252627282930313233/*// Definition for a Node.class Node {public: int val; N ...
