r*****n
发帖数: 20 | 1 //A full binary tree (sometimes proper binary tree or 2-tree or strictly
binary tree) is a tree in which every node other than the leaves has two
children.
bool isFull(Node *s){
if(!s->L && !s->R)
return true;
if(!s->R || !s->L)
return false;
return isFull(s->L) && isFull(s->R);
}
//A complete binary tree is a binary tree in which every level, except
possibly the last, is completely filled, and all nodes are as far left as
possible.[2]
int minHeight(Node *... 阅读全帖 |
|
r**h
发帖数: 1288 | 2 class Solution {
public:
int maxDepth(TreeNode *root) {
if(root == NULL) return 0;
stack st;
st.push(root);
TreeNode *prev=NULL, *cur;
int maxHeight = 0;
while(st.size()>0){
cur = st.top();
if(prev==NULL || prev->left==cur || prev->right==cur){
if(cur->left != NULL){
st.push(cur->left);
}
else if(cur->right != NULL){
... 阅读全帖 |
|
b***e
发帖数: 1419 | 3 /*
Here's a solution with JS, O(n) time and O(1) space.
You can copy&paste the full body of this post and run it in
a browser console.
*/
var minCandies = function(children) {
var maxHeight = children.length;
var state = 'desc';
var height = maxHeight;
var accumulated = 0;
var count = 0;
for (var i = 0; i < children.length - 1; i++) {
accumulated += height;
count++;
if (state == 'desc') {
if (a[i] > a[i+1]) {
height--;
... 阅读全帖 |
|
l****p
发帖数: 397 | 4 第一通电话：
听口音应该是老印的，有点口音，面试过程中好几次我都没听清反复问。
上来没寒暄几句就写代码：
找出一个树中最深的结点。
明显留了好多细节让我问，于是我开始clarify:
1. 是不是binary tree。答：good question, yes, assume it's a binary tree
2. 是不是balanced binary tree。答：does that matter? 我边想边说，好像没关系
然后我再也想不出其它问题了。开始想算法。想一半，他才提醒我说还有一个细节我没
问：如果有多个最深结点怎么办。回答是返回最右的。这是一个失分的点
然后解释算法，可以用深度优先遍历也可以用广度优先遍历，记录所有叶节点的深度，
然后找出最深的。他问复杂度，我说时间是O(N), 空间是O(N). 他说空间能优化吗？我
说能， 在遍历过程中只记录最深的就行。他问这下的空间复杂度，我说是O(1) 。然后
让我开始写代码，我说深度优先呢还是广度优先，他说有什么区别，我说差不多，然后
想想不对，广度优先需要一个queue，这是O(N)的空间，深度的只要O(lgN)的空间，这
... 阅读全帖 |
|
r*****n
发帖数: 20 | 5 不考虑unicode 我觉得trie还是比较可行的做法：
1、用字典所有words来build up a trie, root是NULL 第一层结点是a,b,c,d,e,....
2、对于第二层结点开始的subtrees, 找各自的maxheight
3、选出两个height最大的substree 就是答案
1. O(n), where n is the number of words in the dictionary
2. O(|E|*m), where m is the (average) total number of nodes in each substree
and |E| is the size of the alphabetic set.
3. O(1) |
|
c********t
发帖数: 5706 | 6 你如果说的是 breadth first travel, 是用queue走一遍，但没法做到分层
如果是层打印，我只会写以下代码，不但需要多次access nodes，还要先求高度。你有
什么办法一次遍历层打印吗？多谢。
public void printLevelOrder() {
for (int i = 1; i <= this.maxHeight(); i++) {
printLevel(this, i);
System.out.println();
}
}
public void printLevel(Node node, int level) {
if (node == null)
return;
if (level == 1)
System.out.print(node.value + " ");
else {
printLevel(node.left, level - 1);
printLevel(node.right, leve... 阅读全帖 |
|
c********t
发帖数: 5706 | 7 你如果说的是 breadth first travel, 是用queue走一遍，但没法做到分层
如果是层打印，我只会写以下代码，不但需要多次access nodes，还要先求高度。你有
什么办法一次遍历层打印吗？多谢。
public void printLevelOrder() {
for (int i = 1; i <= this.maxHeight(); i++) {
printLevel(this, i);
System.out.println();
}
}
public void printLevel(Node node, int level) {
if (node == null)
return;
if (level == 1)
System.out.print(node.value + " ");
else {
printLevel(node.left, level - 1);
printLevel(node.right, leve... 阅读全帖 |
|
k****r
发帖数: 807 | 8 为什么sort by base_area呢？可不可以按A1sort然后dp呢？我试着练一下。create一
个class作为dp的内容including last X2 and current sumH
class dp {
int x2;
int sum;
}
public maxHeight(square[] s) {
sortSquareByA1(s); //sort by A1
int len = s.length;
int[][] dp = new int[len][s.len];
int result;
dp[0][0].sum = square[0].H;
dp[0][0].x2 = square[0].x2;
for(int i = 1; i < len; i++) { //add one more
if (square[i].A2 > square[i - 1].A2) {
dp[i][0].sum = dp[i - 1][0].sum + square[... 阅读全帖 |
|
