leetcode刷第3遍今天满满鸡血开刷！🐔🐔🐔
在刷第二遍的时候已经基本把每道题的思路和解法都记录下来了， 在刷第三遍的时候，重点放在那些解法不熟的题目上面，并且对于这些解法不熟的题目，要再次做一些记录，加强理解，强化思维。恩，就酱！2周做完，希望26号end。期待10月份就能有勇气找老师内推了。
240 - 223 (20 题)
241： different ways to add parentheses
在string的不同地方加括号，得到的计算结果是不同的， 括号是加在 operator前面或者后面的。这就是括号可以加的位置。
这个题目用的思想是 divide and conquer， 也就是recursion的解法，只要对string里面的任何一个操作符，用括号分割，分别计算left part result and right part result，最后对这些可能的result进行组合就能得到结果。
这个题目放松了一步，string里面的所有数其实都是正数，没有负数的情况，如果存在负数的话，那对string处理就挺难了。
240：search matrix II
这个题目这边做的时候，有好好分析了下，恩， 感觉比第二遍想的更清晰了些，为什么要从右上到左下的对角线来进行search呢？ 其实原因是这样的， 这与整个matrix数的走向有关，从左到右， 数字依次递增，从上到下依次递增，所以如果从左上角开始，往下或者往右走都是递增，不能控制走向，如果从右下角开始走，往左或者往上都是递减，也不能控制走向，再看左下角和右上角，这两个起点的两个走向是可以严格控制顺序的， 所以我们最后选择以这两个点为起点开始走。时间复杂度是O(n)
这个题目还有一个 O(nlogn)的解法， 由于对于左上到右下的对角线上的元素都是递增的，所以我们可以先在对角线上找到target元素存在的范围，然后就可以cut掉3/4的元素了， 再用这种方法继续找，这种方法是divide and conquer， 也是recursion的解法，大问题化小问题的解。
239: sliding window maximum （1BUG）
用deque来模拟window, deque里面维护一个单调递减的序列，每次检测到一个数比当前的back数大，那么需要把deque里面所有比当前的数小的都pop出来，为什么要从back开始呢？因为deque里存的都是单调递减的数，back的数是最小的，当然应该从最小的开始比较，然后比较较大的。因为是window，所以当window size超过了K, 需要pop front，这就是为什么我们需要用到deque的原因。
这个sliding window的题目没有一次性写对，调了一次bug，因为 在用了deque.front()之前没有对deque isEmpty进行判断，导致 runtime error了。
这个bug 其实是不应该犯的，很明显的bug，之后在写程序·的时候还是要先检查下有没有明显的bug再去提交，不要指望编译器给你debug.
时间复杂度： O(n)
sliding window的题目很容易出bug，因为需要考虑的问题有点多， 涉及到比较复杂的deque的操作， 还有index的操作，写的时候要注意。
231：pow of two
要注意n <= 0 return false; 这个要特殊处理
230： kth smallest element in a BST (BUG BUG BUG)
每次做这个题目都快要被自己气死，第一遍总不能得到正确答案，然后看一眼代码，找不出错误，然后各种乱调，最后才发现，就是那个k，k在这个recursion里面应该可以看做是一个全局变量，因为不然的话，返回到上一层的时候k又会变成在那一层上的值，这样就会出现rst被返回修改的可能， 所以，k传进函数的应该是reference， 而不是 value
229：majority numberII
这个题目虽然知道用vote algoritm + two candidates来做，但是第三遍做的时候逻辑还是不太清晰，这个vote的过程要能模拟出来，要掌握。
注意： 当值与两个candidates都不想等时，两个candidates的counter都需要-1.
228: summary ranges
做这个题目的时候，想的肯定是去找连续的数，就是比较后面那个数和前面那个数，如果相等就再看下一个数，但是这里有两个选择，一种选择是将判断条件放在for循环语句上，只找到size-2的元素为止，但是这样的话对于最后一个元素是不能进行判断的，另一种选择是for循环的条件仍然到 size-1,但是在判断连续值的时候，在条件判断里加上 i +1 < size-1的限制，这样做是很好地，因为既可以对最后那个元素进行判断，也可以判断连续的值。
227: calculator II
224：calculator I
这两个题目这是做的第三遍，但还是每次看到这个题目都有点害怕，因为这两个题目不容易些对啊，各种往stack里面push， pop的情况，一想到都觉得好麻烦， 但是， 无奈，要冷静下来仔细分析，往往这样的题目做透了就是增强能力的时候！这种题目更要好好分析。
calcuator I : 2个stack， 分别存int， 和 op, 算法是，在加入第二个op的时候才进行第一次的运算，要注意（, 直接push, )的情况下，要pop出（.
这个题目很繁琐，但是总的思路还是清晰的，分为两步， 第一步，把val_stk里面的数填好，第二步， 处理op_stk， 在push一个op之前，先把op_stk里面已经有的那些操作符全部进行计算完毕， 之后才能将下一个op push进去。 并且此时更新val_stk top的元素。
为什么需要把op_stk里面的所有已有的op全都计算完再加新的呢？因为运算符里有（, 对于(的处理可能使得运算有先后之分了，需要先把（)里面的内容计算完才能进行下一步的计算。
class Solution {
private:
int cal(int val1, int val2, char op) {
switch(op) {
case '+' : return val1 + val2;
case '-' : return val1 - val2;
}
}
public:
int calculate(string s) {
if (s.size() == 0) return 0;
stack<int> val_stk;
stack<char> op_stk;
for (int i = 0; i <= s.size(); i++) {
// put int into val_stk
if (i < s.size() && isdigit(s[i])) {
int val = 0;
while (i < s.size() && isdigit(s[i])) {
val *= 10;
val += s[i] - '0';
i++;
}
val_stk.push(val);
i--;
} else {
//handle with the op, and put op into op_stk
//cal the result
if (i == s.size() || (s[i] == '+' || s[i] == '-' || s[i] == ')' || s[i] == '(')) {
while (!op_stk.empty() && s[i] != '(' && (op_stk.top() == '+' || op_stk.top() == '-')) {
int val2 = val_stk.top();
val_stk.pop();
val_stk.top() = cal(val_stk.top(), val2, op_stk.top());
op_stk.pop();
}
if (i < s.size()) {
if (s[i] == ')') op_stk.pop();
else op_stk.push(s[i]);
}
}
}
}
return val_stk.top();
}
};
calculator II: 和第一个的区别，要区分各个op的优先级，写了个函数 isOK比较op的优先级，就几种情况，当前的op和下一个op分几种情况进行比较就可以了。
class Solution {
private:
int cal(int val1, int val2, char op) {
switch(op) {
case '+' : return val1 + val2;
case '-' : return val1 - val2;
case '*' : return val1 * val2;
case '/' : return val1 / val2;
}
}
bool isOK(char next, char cur) {
if (cur == '*' || cur == '/') return true;
return (next == '+' || next == '-');
}
public:
int calculate(string s) {
if (s.size() == 0) return 0;
stack<int> val_stk;
stack<char> op_stk;
for (int i = 0; i <= s.size(); i++) {
if (i < s.size() && isdigit(s[i])) {
int val = 0;
while (i < s.size() && isdigit(s[i])) {
val *= 10;
val += s[i] - '0';
i++;
}
val_stk.push(val);
i--;
} else {
if (i == s.size() ||(s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/')) {
while (!op_stk.empty() && (i == s.size() || isOK(s[i], op_stk.top()))) {
int tmp = val_stk.top();
val_stk.pop();
val_stk.top() = cal(val_stk.top(), tmp, op_stk.top());
op_stk.pop();
}
if (i < s.size()) {
op_stk.push(s[i]);
}
}
}
}
return val_stk.top();
}
};
226: invert binary tree
这个题目看树的结构很简单，就是swap左右子树，可以用树里面bottom-up recursion的思想，先把左右子树invert下，然后交换，但是树里面pointer的交换和int 的交换是不同的，pointer的交换不能仅仅写成int swap的形式，而是需要用pointer 指向那个区域。否则仅仅只是将一个pointer 变量变化了下，并没有改变root left, right的指向。
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
TreeNode* tmp = left;
root->left = right;
root->right = tmp;
return root;
}
225： implement stack using queues
这个题目要注意pop和 top这两个函数的区别，pop是直接把最后那个值pop出去就好了，但是top，需要access最后那个元素，记录那个元素的值，然后还需要把那个元素又放在queue的末尾， 来进行下一次的操作。
223: rectangle area
这个题目求两个长方形cover的面积， 其实有两种情况存在，这两个长方形不相交，这两个长方形相交，其实在判断两个长方形不相交的时候有一点小偷懒，如果重合的那个长方形的长和宽《=0不就说明这个长方形不存在吗，这是最简单的判断两个长方形不重合的条件了。
int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
//check the area
int area1 = abs(A-C) * abs(B-D);
int area2 = abs(G-E) * abs(H-F);
if (min(C,G) <= max(A,E) || (min(D,H) <= max(B,F))) {
return area1 + area2;
}
//compute the area
int width = min(C, G) - max(A, E);
int height = min(D, H) - max(B, F);
int carea = width * height;
int total = area1 + area2 - carea;
return total;
}
No comments:
Post a Comment