今天一天都可以做题，所以尽量多做一些！
137 - 121:
买卖股票系列：
121：Best time to buy and sell stock
买卖股票，只能买进卖出一次，问最大的利润。这个问题很容易可以分析出：只要找到在当天i之前的股票最小值，那么当天的股票最大利润就是当天的股票值-之前的最小值。 是属于一维dp的思想，但是我们可以优化，最后时间复杂度O（n）， 空间复杂度O（1）
method1:
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() == 0) return 0;
int mins = prices[0];
int global_max = 0;
for (int i = 1; i < prices.size(); i++) {
global_max = max(global_max, prices[i]-mins);
mins = min(mins, prices[i]);
}
return global_max;
}
};
method2: 计算相邻两天的差价，求最大子段和。
122: Best time to buy and sell stockII
这个题目在I的基础上，可以多次买卖股票， 最开始想到的方法是一维dp linear往回看，第i天最大利润是所有可能利润的最大值，这种想法是基于上一题算法的，但是这种Linear 往回看的方法时间复杂度太高，O（n^2），能不能优化到O（n）呢？
O（n^2） :
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() == 0) return 0 ;
int M[prices.size()];
M[0] = 0;
int global = 0;
for (int i = 1; i < prices.size(); i++) {
int gmax = 0;
for (int j = i-1; j >= 0; j--) {
if (prices[i] > prices[j]) {
gmax = max(gmax, prices[i]-prices[j] + M[j]);
}
}
M[i] = gmax;
global = max(global, M[i]);
}
return global;
}
};
这个题目也可以在method2上面改进，当可以多次买卖的时候，其实就是所以正差价的和。
时间复杂度： O(N) 空间复杂度： O（1）
这个方法是在时间和空间上最优的，并且最容易实现的算法！
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() == 0) return 0;
int solu = 0;
for (int i = 0; i < prices.size()-1; i++) {
if (prices[i+1] - prices[i] > 0) {
solu += prices[i+1] - prices[i];
}
}
return solu;
}
};
123: Best time to buy and sell stockIII
这个题目的限制最多，最多只能两次买卖股票， 这两次买卖股票的区间肯定不同， 相当于是在两个不相交的区间内分别做一次买卖股票，使得这两次的和最大。 一维数组，要找不相交的两个区间，之前也是有很多题目都有这个思想，可以从左往右从右往左两次扫描数组，分别求做一次股票买卖的最大利润，在做第二次扫描的时候，可以顺便把最大利润和求出来，也就是最后的答案。
其实考察这种思想的题目之前也做过很多，但是要分析题目的情景，分析出题目是让求什么，才能看出题目所考查的思想。
时间复杂度： O(2*n) 空间复杂度： O(n) 只需要用一个数组存从左往右的值。
以后对于array里面分两段的solution， 考虑到从左往右从右往左，岔开区间来解。
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() == 0) return 0;
int M[prices.size()];//M[i] represent the maximum profit until i
int local = 0;
int gmax = 0;
int rst = 0;
//from left to right
M[0] = 0;
local = prices[0];
for (int i = 1; i < prices.size(); i++) {
M[i] = max(gmax, prices[i] - local);
local = min(local, prices[i]);
}
//from right to left
rst = max(rst, M[prices.size()-1]);
local = prices[prices.size()-1];
gmax = 0;
for (int i = prices.size()-1; i >= 1; i--) {
gmax = max(gmax, local-prices[i]);
rst = max(rst, gmax + M[i-1]);
local = max(local, prices[i]);
}
return rst;
}
};
Best time to buy and sell stock IV
这个题目是III的一个general求解， 最多可进行k次交易，求可能的最大profit 。
124: binary tree maximum path sum
求一个binary tree里面从任意节点到任意节点的最大路径和。
这个题目跟之前那个判断任意节点到任意节点的路径和是否等于target是不同的， 这个题目要简单很多，方法是用树的recursion中最常见的方法： bottom - up recursion. 1. want what from children, 2. do what in current level, 3. return what to its parent
这个里面want what from children， 是指 左边子树的path sum 的maximum， 右边子树的path sum的maximum， 在current level， 要计算global_max的值，而由于binary tree里面的val值可能存在负数，所以global_max的取值在, global_max, left+root->val, right+ root->val, root->val, root->val + left + right中取最大值。 在当前层给parent返值是要返回以当前节点为路径上的一点的maximum path， 这个值是在 root->val, root->left, root->right，这三者之间取最大值。
时间复杂度： O（n）空间复杂度： O（logn）
class Solution {
private:
int helper(TreeNode* root, int &global_max) {
if (root == NULL) return 0;
int left = helper(root->left, global_max);
int right = helper(root->right, global_max);
global_max = max(global_max,max(root->val, max(max(root->val + left, root->val + right), root->val + left + right)));
return max(max(left, right) + root->val, root->val);
}
public:
int maxPathSum(TreeNode* root) {
if (root == NULL) return 0;
int global_max = INT_MIN;
helper(root, global_max);
return global_max;
}
};
125: valid palindrome
唉，永远记得这个题目惨痛的教训！ 当时就是因为没有更新做Leetcode，导致挂在这个题目上。这个题目是在含有各种字符的string中， 针对alpha 或者 digit 的char进行回文，并且忽略大小写。这个题目其实不难，但是要注意各种case的分析，如果是不需要考虑的字符，直接跳过不去进行判断就好了。做这个题目利用了一个小技巧就是不管是大写还是小写，是数字还是字母，直接先把left 和 right的char转化成lower letter来进行比较。 字母和数字也可以直接进行比较不需要区分。
class Solution {
public:
bool isPalindrome(string s) {
int left = 0;
int right = s.size()-1;
while (left <= right) {
if ((isalpha(s[left]) || isdigit(s[left])) && (isalpha(s[right]) ||isdigit(s[right]))) {
if (tolower(s[left]) != tolower(s[right])) {
return false;
} else {
left++;
right--;
}
}
if (!isalpha(s[left]) && !isdigit(s[left])) {
left++;
}
if (!isalpha(s[right]) && !isdigit(s[right])) {
right--;
}
}
return true;
}
};
126： word ladder
这个题目是很明显的best first search, 由于search的路径path值都为1， 所以退化成breadth first search, 时间复杂度也会改进， 但是要注意一个问题： 如果利用breadth first search来求shortest path的话，写法要注意， path的增加是在进入下一层开始，同一层上path是不会增加的，所以需要用到level order traversal的方法来进行BFS。
还有一点，不管是利用Best first search 还是利用breadth first search， 很重要的一点就是要知道expand rule是什么，对于一个状态，如何expand到下一个状态， 这点是利用这两种算法来进行解题的关键点。
class Solution {
public:
int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
queue<string> explore;
unordered_set<string> visit;
int path = 0;
explore.push(beginWord);
visit.insert(beginWord);
while (!explore.empty()) {
int size1 = explore.size();
path++;
for (int k = 0; k < size1; k++) {
string tmp = explore.front();
explore.pop();
if (tmp == endWord) {
return path;
}
for (int i = 0; i < tmp.size(); i++) {
string buf = tmp;
for (int j = 0; j < 26; j++) {
if (buf[i] != ('a'+j)) {
buf[i] = 'a' + j;
if (visit.find(buf) == visit.end() && wordDict.find(buf) != wordDict.end()) {
explore.push(buf);
visit.insert(buf);
}
}
}
}
}
}
return 0;
}
};
时间复杂度： O（n^k） : n是单词的个数，k是每一个单词的长度。
空间复杂度： O（n）
127: word ladderII
这个题目要求求出所有最短路径的解集合。
128: longest consecutive sequence
这个题目的算法思想也是很重要的， 连续的值是否在array里面， 为了能在O(1)的时间内进行判断，可以使用unordered_set来存储数据。 然后我们只要对每一个元素找在array里面连续的值的个数就可以了。 但是要注意的是，为了防止计算重复，每次我们找到一个连续的数就需要把它在unordered_set里面删除。
time complexity: O(n)
129: sum leaf to root numbers
这种leaf to root的path, 一般都是用DFS的来解，但是对于Leaf node之前也总结过，一定要分两种情况，一种是该node是leaf node, 一种是该node不是leaf node. 只有在leaf node的时候返回。
130: surrounded regions
被包围的棋子，这个题目要注意逆向思维过程，以及dfs 的iteration的写法！ dfs iteration的写法还是经常被考的内容，写dfs的时候要注意， iteration能防止stack 溢出。
下面的palindrome partitionI 和 palindrome partition II 与 word breakI 和 word breakII的题型和follow up 以及运用的算法思想是非常类似的。
131: palindrome partitionI
这个题目是DP + DFS
在DFS里面利用DP的结果进行剪枝。
这个题目中也可以看到 常见的对string 进行dfs遍历找到所有可能连续子串的思想， 利用两个变量， start ： 取子串的start position; i : 以start 为起点的子串的长度
这个题目里面的DFStree可以画成下面这样:
abc
level0: start = 0 a ab abc
level1: start = laststart+1 b bc c
level 2: start = laststart+1 c
所有可能的子串组合： a,b,c a,bc ab, c abc
132: palindrome partitionII
这个题目的代码可以写的很巧妙，双重DP， 在一个forfor循环里面进行判断， 时间复杂度是O（n^2), 空间复杂度O(n^2)
133: word break
DP , 绳子分割问题，一维DP + linear 往回看， 时间复杂度O（n^2）, 空间复杂度O（n）
134: word breakII
跟palindrome partitionI 做法类似：DP+DFS
相同的DFS 分割string的方法， start position + len ， 每次进行下一步DFS之前要看是否能够在这一步进行break。 这个题目要bug free感觉还是有点困难。
135：candy
134 : gas station
这两道题很有意思，属于实际情景题，要分析出题目里面包含的算法是什么，
candy: 这个题目需要看Neighbors, 很容易分析出来连续增加的rating， 分到的candy也是连续增加的， 我们可以从左往右， 从右往左扫描数组，对于连续增加的rating， 分给连续的candy，最后每个人分配的candy最少是这两次扫描之后每个位置的较大值。
gas station: 这个题目其实是利用排除法的思想来做的，要找到能到达的gas station， 我们可以排除一些不能到达的station， 从第一个加油站出发，开始走，如果走到某一个加油站，发现remaining gas < 0 说明在这个加油站之前的那些加油站是不可能走到的，那么我们就排除了很多的加油站，一直这样做下去，直到到了最后那个加油站， 肯定是有一个可能的start, 最后再判断如果从这个start开始走，有没有可能走完，如果可以，那么这个就是最后的结果， 如果不能， 就说明每个加油站都不能走完。
120-110:
110： balanced binary tree
这个题目是一个很典型的bottom up 的 tree recursion， 时间复杂度O（n）
111: minimal depth of binary tree
这个题目也是很典型的bottom up的 tree recursion， 但是根据题目的要求要有所改变， 跟maximum depth of binary tree做法不同，稍微难一点， 因为从下面往上返值的时候可能存在left 或者right有一个为0的情况， 这个时候不再是简单取最小值了，而是哪个不为0 返回那个+1。
class Solution {
private:
int helper(TreeNode* root) {
if (root == NULL) {
return 0;
}
int left = helper(root->left);
int right = helper(root->right);
if (left && right) {
return min(left, right)+1;
} else {
return left ? left+1 : right+1;
}
}
public:
int minDepth(TreeNode* root) {
return helper(root);
}
};
112: path sum
root->leaf path: 这种path的求解不再利用bottom up recursion了， 而是需要利用 preorder的顺序遍历tree， 从root->leaf每一条path都能得到一个total的值，每次遍历到Leaf node得到那个total的值之后与sum进行比较， 如果相等就返回true。
特别要注意的是： 如果是要求path里有leaf node，必须要分两种情况来讨论： case1： 当前节点是leaf node （root->left == NULL && root->right == NULL）， case2: 当前节点不是leaf node, 这种case里面包括3种情况，一种root->left && root->right , 另外两种： root->left || root->right . 这个判断经常容易忽视，所以一定要注意。
113： path sum II
这个题目是上面那个题目的follow up， 需要找到所有可能组合，属于树的dfs的题目， 但是解法一直不是最快的，这个题目的方法可能下次还有待改进。
114：flattern binary tree to linked list
serialize tree的问题， 这种问题属于将binary tree转化成Linked list的serialize tree 问题， 一般这类问题有一个通用的解法：
1.定义一个head
2. 定义一个pre
3. 选择符合题意的tree traversal 算法
4. 每次在current node的时候进行pre与current node的指针操作， 首先要确定Head节点， if（pre == NULL) head = root; else {//进行pre与current node的操作}
但是针对不同的题目要求， 会稍微有一些改变。
类似的题目还有将一个Binary tree转化成double linked list
115: distinct subsequence
116: populating next pointer in binary tree I
117： populating next pointer in binary tree II
这两个题目很明显，最简单通用的方法就是level order traversal， 但是这样做的时间复杂度是O（nlogn),有没有更好的方法呢？ 是有的，因为我们可以利用多出来的那个next指针来进行level order的遍历，利用上一层和下一层之间节点的关系，维护两个指针，两层同时遍历，并且更新指针。这样做的时间复杂度是O（2n）, 每个节点 最多遍历2次。
I:
class Solution {
public:
void connect(TreeLinkNode *root) {
if (root == NULL) return;
TreeLinkNode* cur = root;
while (cur) {
TreeLinkNode* cur1 = cur;
TreeLinkNode* cur2 = NULL;
TreeLinkNode* next = NULL;
while (cur1) {
if (cur1->left) {
cur2 = cur1->left;
if(next == NULL) next = cur2;
else {
next->next = cur2;
next = cur2;
}
}
if (cur1->right) {
cur2 = cur1->right;
next->next = cur2;
next = cur2;
}
cur1 = cur1->next;
}
cur = cur->left;
}
}
};
II :
II 只需要在I的代码上做一点小的改动就可以。
当binary tree不是perfect的话，要加上一些corner case的处理，需要找到下一层链表的起点。
class Solution {
public:
void connect(TreeLinkNode *root) {
if (root == NULL) return;
TreeLinkNode* cur = root;
while (cur) {
TreeLinkNode* cur1 = cur;
TreeLinkNode* cur2 = NULL;
TreeLinkNode* next = NULL; //the next node of the list in next level
TreeLinkNode* curhead = NULL; //the head of the list in next level
while (cur1) {
if (cur1->left) {
cur2 = cur1->left;
if (curhead == NULL) curhead = cur2;
if(next == NULL) next = cur2;
else {
next->next = cur2;
next = cur2;
}
}
if (cur1->right) {
cur2 = cur1->right;
if (curhead == NULL) curhead = cur2;
if (next == NULL) next = cur2;
else {
next->next = cur2;
next = cur2;
}
}
cur1 = cur1->next;
}
cur = curhead;
}
}
};
118: Pascal's Triangle
119: Pascal's TriangleII
这两个题目属于观察题，看每一行数据组成的规矩，发现两头都是1， 中间的数与上一行的数有关，并且是连续两个数的和，这样就很简单了。
II 相当于是I的一个follow up，怎样去节省空间获得某一行的数据，其实这个题目里面计算每一行的数据只与前一行的数据有关，所以只需要用一个vector记录前一行的值就可以了。
120： Triangle
这个题目要求最短路径，最开始想到的是Best first search， 但是发现空间复杂度是不满足要求的， 后来又想到求最小值还有一种方法是DP，但是dp就没有好好想怎么找induction rule了。 其实DP的分析也是有套路的，1.依据题目所求定义子问题， M[i]的含义。 2. 从最小问题出发，找到n-1-> n的规律，即induction rule. 其实，DP的解法是会把问题的所有解求出来只是在每一步获得了一个最优解。
这个题目很明显子问题是在这个triangle里面到达某个点的最短路径，而由于下一层的解只需要上一层解就可以解决，所以只需要用一层的解作为子问题， M[i]是到i这个数字的最短路径，而M[I]怎么解呢？ 如果只有一层，如果只有两层，如果只有三层，....这样分析可以发现有两条路径可以到达i,所以最短路径是这两条子路径的较小值+这个数本身，这个就是Induction rule.
这个题目有个小技巧就是从最后一层向最上一层求解，这样可以避免到最后一层的时候需要再去遍历求最小值。
No comments:
Post a Comment