today's mission： 231 - 221
231: pow of two
判断一个数是不是2的幂，这个题目如果用bit 运算来做，很简单， 因为如果一个数是2的幂，那么n-1的话除了第一位不是1， 其余位全都是1， 直接返回 ！（n & n-1）就可以。
Note： 要注意n <= 0 的情况，这种情况直接返回false。
230： kth smallest element in BST
这是一道BST的题目，利用的是BST inorder traversal 得到的是一个ascending order的array, 可以利用inorder， 没遇到一个root节点， k--，如果k=1的时候，就是第k小的元素了。 时间复杂度： O（n）
这个题目有个follow up 问 如何优化，这个题目其实时间复杂度可以到O（h), 如果我们修改bst node的结构，增加一个变量表示任意一个node左子树有多少节点，右子树有多少节点，那么就可以更好地利用BST的性质了，如果当前节点的左子树节点数目 + 1== k，那么current node 就是kth smallest element， 如果当前节点的左子树节点数目 > k， 那么kth smallest element就在左子树，直接遍历左子树，如果当前节点左子树节点数目 < k, 那么kth smallest element 就在右子树，直接遍历右子树，直到当前node == NULL 停止。
229： Majority elementII
这个题目要找到出现次数在 L/3 以上的元素。 这个题目还是利用的majority element I（出现次数超过最多） 的思想，但是需要维护两个结果的变量，pair<int, int>, pair<int, int> 该元素和元素的counter, 最后剩下的这两个元素只是可能是majority， 还需要再扫描一遍array，分别count这两个元素，如果这两个值出现的次数 > length/3, 就是一个majority element了。得到最后的结果。
228： Summary ranges
这个题目是各一个数组，里面数都是sort好的，求出里面的range,也就是求连续数字的范围，很明显用start , end两个指针来标记范围，虽然简单，但还是有一些容易出错的问题需要注意。
Note : 1. 如果用start 和 end来做这个题目，要注意处理如果最后一个range是要包括最后那个元素的，所以在处理的时候，两种情况下，都需要push_back range， case1：找到了一个连续的range, case2 : 检测到了最后一个元素，不管最后那个元素是否是连续的，直接push_back range
2. int 转化成string,直接用to_string(int)来转换，不要用int + '0'来做，这样容易出错， 因为对于负数这样转换是错的。
227： Basic caculatorII
计算string, 含有 +， - , *, /，这个题目没有（， ），与下面不同的是需要考虑计算符的优先级，不需要考虑（， ）的情况。怎么处理计算付的优先级呢？ 如果当前运算符的优先级，比op的top（）要高，那么不进行计算直接把这个push, 否则正常计算。同时注意对字符串最后一个字符的处理，对于最后一个字符，不管它的优先级怎么样都是需要进行最后计算的，这一点与下面那题也不同。
224: basic caculatorI
计算string， 含有 +， -， （， ），不用考虑运算符的优先级，利用两个stack,一个记录 val， 一个记录 op，如果遇到下一个字符的时候开始计算， 由于可能存在 多个连续的（， ），所以每次需要将stack op里的运算符全部计算完再去继续下面的计算。
226: invert binary tree
这个题目属于很基础的树的recursion的操作题， 关键操作就是对每一个node， swap left subtree and right subtree，至于想采用哪种tree traversal的方法就看个人了。time complexity: O(n)
这个题目也可以用iterative的方法来做，层次遍历树，并且每次遍历到一个Node的时候，swap这个node的左右child node.需要用到queue
225: implement stack using queues
这个题目在上一篇implement queue using stacks谈到过，算法思路跟那个也差不多， 但是要注意的是对于top()，操作，queue一定要恢复成之前的样子， 这是跟pop不同的地方。
223: rectangular area
两个矩形覆盖的面积 = 两个矩形面积之和 - 重合的那部分面积。
要注意判断两个矩形不重合的情况，这种情况下覆盖面积就是这两个矩形面积之和。
222: count complete tree nodes
要结合complete tree的特点，只有最后一层不满，其他层都是满树，可以通过树的高度求node的个数，那么怎么判断能不能用树的高度求呢？ 如果最左子树最右子树的高度相同，很显然是可以直接求，因为左右子树高度相同就是满树，否则，只能通过左右子树count nodes+1来求tree nodes.
求子树的高度，之前是用的O（n）的recursion的方法求得，但是这个题目如果仍然用这个方法来求时间复杂度太高，其实这个题目求高度可以不那么严格，只要一个node go to left的nodes 数目，和这个node go to right的Nodes 数目就可以判断是不是一个full binary tree.可以用iterative的方法, 时间复杂度是O（h^2)
221: maximum square
0, 1 矩阵maximum square， 找到所有由1组成的square, 要求maximum的值，是属于0,1 矩阵的dp题，关键是在于找induction rule，dp题分析可以由最小的问题慢慢扩大到大一些的问题， 11 111
11 111
111
这个题目的induction rule: M[i][j] = min(min(M[i][j-1], M[i-1][j]) , M[i-1][j-1]) + 1
M[i][j] represents the maximum square that can be formed as matrix[i][j] as the right corner.
No comments:
Post a Comment