f*****a
发帖数: 781 | 1 1. 2D matrix, sorted on each row, first element of next row is larger(or
equal) to the last element of previous row, now giving a target number,
returning the position that the target locates within the matrix
2. Given a binary tree where all the right nodes are leaf nodes, flip it
upside down
* and turn it into a tree with left leaf nodes.
*
* for example, turn these:
*
* 1 1
* / /
* 2 3 2 3
* /
* 4 5
* /
* 6 7
*
* into these:
*
* 1 1
* / /
* 2---3 2---3
* /
* 4---5
* /
* 6---7
*
* where 6 is the new root node for the left tree, and 2 for the right tree.
* oriented correctly:
*
* 6 2
* / /
* 7 4 3 1
* /
* 5 2
* /
* 3 1
*/ |
r*******k
发帖数: 1423 | 2 谢谢分享
【在 f*****a 的大作中提到】
: 1. 2D matrix, sorted on each row, first element of next row is larger(or
: equal) to the last element of previous row, now giving a target number,
: returning the position that the target locates within the matrix
: 2. Given a binary tree where all the right nodes are leaf nodes, flip it
: upside down
: * and turn it into a tree with left leaf nodes.
: *
: * for example, turn these:
: *
: * 1 1
|
l*****a
发帖数: 14598 | 3 这个期待什么结果
1
/
2 3
4
【在 f*****a 的大作中提到】
: 1. 2D matrix, sorted on each row, first element of next row is larger(or
: equal) to the last element of previous row, now giving a target number,
: returning the position that the target locates within the matrix
: 2. Given a binary tree where all the right nodes are leaf nodes, flip it
: upside down
: * and turn it into a tree with left leaf nodes.
: *
: * for example, turn these:
: *
: * 1 1
|
m****9
发帖数: 492 | 4 LZ好人，谢谢分享，Bless. 答案是要在google doc里写吗？ |
t*******i
发帖数: 4960 | 5 第二题保证除了第一层每层都有２个节点么？
【在 f*****a 的大作中提到】
: 1. 2D matrix, sorted on each row, first element of next row is larger(or
: equal) to the last element of previous row, now giving a target number,
: returning the position that the target locates within the matrix
: 2. Given a binary tree where all the right nodes are leaf nodes, flip it
: upside down
: * and turn it into a tree with left leaf nodes.
: *
: * for example, turn these:
: *
: * 1 1
|
e*****i
发帖数: 182 | 6 <=2
【在 t*******i 的大作中提到】
: 第二题保证除了第一层每层都有２个节点么？
|
j*******t
发帖数: 223 | |
t*******e
发帖数: 274 | 8 第一题中的equal条件有什么陷阱么？还是说和leetcode上那道search 2D matrix是一
样的？ |
f*****a
发帖数: 781 | 9 统一回复：
1. 电面不用Gdoc，用CollabEdit
2. 第一题其实是LC原题的变种，等于的边界情况稍微处理一下就可以了
【在 f*****a 的大作中提到】
: 1. 2D matrix, sorted on each row, first element of next row is larger(or
: equal) to the last element of previous row, now giving a target number,
: returning the position that the target locates within the matrix
: 2. Given a binary tree where all the right nodes are leaf nodes, flip it
: upside down
: * and turn it into a tree with left leaf nodes.
: *
: * for example, turn these:
: *
: * 1 1
|
j*****8
发帖数: 3635 | 10 第一题，按照cc150的解法，从右上角开始向左或向下二分查找的话，针对这个首尾可
能相等的情况不需要额外的 处理把
【在 f*****a 的大作中提到】
: 统一回复：
: 1. 电面不用Gdoc，用CollabEdit
: 2. 第一题其实是LC原题的变种，等于的边界情况稍微处理一下就可以了
|
|
|
x******u
发帖数: 259 | |
j**********3
发帖数: 3211 | |
t*******e
发帖数: 274 | 13 同问如果target正好是重复值，该返回哪个位置？
【在 j*****8 的大作中提到】
: 第一题，按照cc150的解法，从右上角开始向左或向下二分查找的话，针对这个首尾可
: 能相等的情况不需要额外的 处理把
|
y**********a
发帖数: 824 | 14 第一题：
List binarySearch(int[][]mx, int k) {
List rel=new ArrayList<>();
for (int m=mx.length,n=mx[0].length,l=0,r=m*n-1;l<=r;) {
int mid=l+(r-l)/2;
int y=mid/n,x=mid%n;
if (mx[y][x]==k) {rel.add(y);rel.add(x);break;}
else if (mx[y][x]
else r=mid-1;
}
return rel;
}
第二题：
TreeNode reverseTree(TreeNode root) {
TreeNode p=null,c=root;
while (c!=null) {
TreeNode t1=c.left,t2=c.right;
c.left=t2;c.right=p;p=c;c=t1;
}
TreeNode rel=p;
while (p.right!=null) {
p.left=p.right.left;
p.right.left=null;
p=p.right;
}
return rel;
} |
l*****a
发帖数: 14598 | 15 第一题如果相等怎么办
第二题，如果是三楼的情况返回什么
【在 y**********a 的大作中提到】
: 第一题：
: List binarySearch(int[][]mx, int k) {
: List rel=new ArrayList<>();
: for (int m=mx.length,n=mx[0].length,l=0,r=m*n-1;l<=r;) {
: int mid=l+(r-l)/2;
: int y=mid/n,x=mid%n;
: if (mx[y][x]==k) {rel.add(y);rel.add(x);break;}
: else if (mx[y][x]: else r=mid-1;
: }
|
y**********a
发帖数: 824 | 16
第一题要进一步 clarify
第二题是
1 2
/ \ -> / \
2 3 3 1
【在 l*****a 的大作中提到】
: 第一题如果相等怎么办
: 第二题，如果是三楼的情况返回什么
|
l*****a
发帖数: 14598 | 17 没看清题？这个期待什么结果
1
/
2 3
4
【在 y**********a 的大作中提到】
:
: 第一题要进一步 clarify
: 第二题是
: 1 2
: / \ -> / \
: 2 3 3 1
|
l*****a
发帖数: 14598 | 18 原题已经告诉你有equal的情况
所以你的code不能得分
【在 y**********a 的大作中提到】
:
: 第一题要进一步 clarify
: 第二题是
: 1 2
: / \ -> / \
: 2 3 3 1
|
y**********a
发帖数: 824 | 19
改了一下第一题。
boolean equal(int[][]mx, int i, int j) {
int m=mx.length,n=mx[0].length;
if (i<0||j>=m*n||j<0||i>=m*n) return false;
return mx[i/n][i%n]==mx[j/n][j%n];
}
int binarySearchBound(int[][]mx, int k, boolean lower) {
for (int m=mx.length,n=mx[0].length,l=0,r=m*n-1;l<=r;) {
int mid=l+(r-l)/2;
if (mx[mid/n][mid%n]==k) {
if (lower)
if (!equal(mx, mid, mid-1)) return mid;
else r=mid-1;
else
if (!equal(mx, mid, mid+1)) return mid;
else l=mid+1;
} else if (mx[mid/n][mid%n]
else r=mid-1;
}
return -1;
}
public List> binarySearch(int[][]mx, int k) {
int n=mx[0].length;
int lb=binarySearchBound(mx, k, true), ub=binarySearchBound(mx, k,
false);
List> rel=new ArrayList<>();
if (lb==-1)return rel;
for (int i=lb;i<=ub;++i) {
int y=i/n,x=i%n;
List t=new ArrayList<>();
t.add(y);t.add(x);
rel.add(t);
}
return rel;
}
【在 l*****a 的大作中提到】
: 原题已经告诉你有equal的情况
: 所以你的code不能得分
|
l****s
发帖数: 75 | 20 第二题其实就是一个reverse linked list的变种。
TreeNode* flipUpsideDown2(TreeNode* root)
{
if (!root) return NULL;
TreeNode* dummy = new TreeNode(0);
dummy->left = root;
TreeNode* right = root->right;
root = root->left;
dummy->left->left = NULL;
dummy->left->right = NULL;
while (root)
{
TreeNode* tmp = root;
root = root->left;
tmp->left = right;
right = tmp->right;
tmp->right = dummy->left;
dummy->left = tmp;
}
root = dummy->left;
delete dummy;
return root;
}
【在 y**********a 的大作中提到】
: 第一题：
: List binarySearch(int[][]mx, int k) {
: List rel=new ArrayList<>();
: for (int m=mx.length,n=mx[0].length,l=0,r=m*n-1;l<=r;) {
: int mid=l+(r-l)/2;
: int y=mid/n,x=mid%n;
: if (mx[y][x]==k) {rel.add(y);rel.add(x);break;}
: else if (mx[y][x]: else r=mid-1;
: }
|
|
|
s**x
发帖数: 7506 | 21 第一题估计出题的人都晕了， 你自己想想吧， 就是不折不扣的 binary search. 2D
array in that case is exactly 1D sorted array! no trick at all, exactly the
same.
1 2 3
4 5 6
is the same as 1 2 3 4 5 6!
【在 j*****8 的大作中提到】
: 第一题，按照cc150的解法，从右上角开始向左或向下二分查找的话，针对这个首尾可
: 能相等的情况不需要额外的 处理把
|
p*****2
发帖数: 21240 | 22 第二题这样怎么样
TreeNode dfs(TreeNode node, TreeNode parent){
if(node==null) return null;
TreeNode left_res = dfs(node.left,node);
if(parent!=null){
node.left = parent.right;
node.right = parent;
}
return left_res!=null?left_res:node;
}
TreeNode convert(TreeNode root){
return dfs(root,null);
} |
m*****k
发帖数: 731 | 23 出题的人就是想看面试者能否把这个larger(or
equal)条件用上而不是fall into
the other one 吧。
the
【在 s**x 的大作中提到】
: 第一题估计出题的人都晕了， 你自己想想吧， 就是不折不扣的 binary search. 2D
: array in that case is exactly 1D sorted array! no trick at all, exactly the
: same.
: 1 2 3
: 4 5 6
: is the same as 1 2 3 4 5 6!
|
m*****k
发帖数: 731 | 24 how about
1
3
what is the result?
【在 l*****a 的大作中提到】
: 没看清题？这个期待什么结果
: 1
: /
: 2 3
: 4
|
m*****k
发帖数: 731 | 25 reverse(TreeNode n)
{
if (n==null){
return null;
}
if(n.left==null){
return n;
}
Node root = reverse(n.left);
n.left.left = n.right;
n.right = null;
n.left.right = n;
n.left = null;
return root;
} |
p****a
发帖数: 447 | |
t*****a
发帖数: 106 | 27 第一题是leetcode原题，不是search index, 是Search for a Range。直接返回一个
range |
f*****a
发帖数: 781 | 28 1. 2D matrix, sorted on each row, first element of next row is larger(or
equal) to the last element of previous row, now giving a target number,
returning the position that the target locates within the matrix
2. Given a binary tree where all the right nodes are leaf nodes, flip it
upside down
* and turn it into a tree with left leaf nodes.
*
* for example, turn these:
*
* 1 1
* / /
* 2 3 2 3
* /
* 4 5
* /
* 6 7
*
* into these:
*
* 1 1
* / /
* 2---3 2---3
* /
* 4---5
* /
* 6---7
*
* where 6 is the new root node for the left tree, and 2 for the right tree.
* oriented correctly:
*
* 6 2
* / /
* 7 4 3 1
* /
* 5 2
* /
* 3 1
*/ |
r*******k
发帖数: 1423 | 29 谢谢分享
【在 f*****a 的大作中提到】
: 1. 2D matrix, sorted on each row, first element of next row is larger(or
: equal) to the last element of previous row, now giving a target number,
: returning the position that the target locates within the matrix
: 2. Given a binary tree where all the right nodes are leaf nodes, flip it
: upside down
: * and turn it into a tree with left leaf nodes.
: *
: * for example, turn these:
: *
: * 1 1
|
l*****a
发帖数: 14598 | 30 这个期待什么结果
1
/
2 3
4
【在 f*****a 的大作中提到】
: 1. 2D matrix, sorted on each row, first element of next row is larger(or
: equal) to the last element of previous row, now giving a target number,
: returning the position that the target locates within the matrix
: 2. Given a binary tree where all the right nodes are leaf nodes, flip it
: upside down
: * and turn it into a tree with left leaf nodes.
: *
: * for example, turn these:
: *
: * 1 1
|
|
|
m****9
发帖数: 492 | 31 LZ好人，谢谢分享，Bless. 答案是要在google doc里写吗？ |
t*******i
发帖数: 4960 | 32 第二题保证除了第一层每层都有２个节点么？
【在 f*****a 的大作中提到】
: 1. 2D matrix, sorted on each row, first element of next row is larger(or
: equal) to the last element of previous row, now giving a target number,
: returning the position that the target locates within the matrix
: 2. Given a binary tree where all the right nodes are leaf nodes, flip it
: upside down
: * and turn it into a tree with left leaf nodes.
: *
: * for example, turn these:
: *
: * 1 1
|
e*****i
发帖数: 182 | 33 <=2
【在 t*******i 的大作中提到】
: 第二题保证除了第一层每层都有２个节点么？
|
j*******t
发帖数: 223 | |
t*******e
发帖数: 274 | 35 第一题中的equal条件有什么陷阱么？还是说和leetcode上那道search 2D matrix是一
样的？ |
f*****a
发帖数: 781 | 36 统一回复：
1. 电面不用Gdoc，用CollabEdit
2. 第一题其实是LC原题的变种，等于的边界情况稍微处理一下就可以了
【在 f*****a 的大作中提到】
: 1. 2D matrix, sorted on each row, first element of next row is larger(or
: equal) to the last element of previous row, now giving a target number,
: returning the position that the target locates within the matrix
: 2. Given a binary tree where all the right nodes are leaf nodes, flip it
: upside down
: * and turn it into a tree with left leaf nodes.
: *
: * for example, turn these:
: *
: * 1 1
|
j*****8
发帖数: 3635 | 37 第一题，按照cc150的解法，从右上角开始向左或向下二分查找的话，针对这个首尾可
能相等的情况不需要额外的 处理把
【在 f*****a 的大作中提到】
: 统一回复：
: 1. 电面不用Gdoc，用CollabEdit
: 2. 第一题其实是LC原题的变种，等于的边界情况稍微处理一下就可以了
|
x******u
发帖数: 259 | |
j**********3
发帖数: 3211 | |
t*******e
发帖数: 274 | 40 同问如果target正好是重复值，该返回哪个位置？
【在 j*****8 的大作中提到】
: 第一题，按照cc150的解法，从右上角开始向左或向下二分查找的话，针对这个首尾可
: 能相等的情况不需要额外的 处理把
|
|
|
y**********a
发帖数: 824 | 41 第一题：
List binarySearch(int[][]mx, int k) {
List rel=new ArrayList<>();
for (int m=mx.length,n=mx[0].length,l=0,r=m*n-1;l<=r;) {
int mid=l+(r-l)/2;
int y=mid/n,x=mid%n;
if (mx[y][x]==k) {rel.add(y);rel.add(x);break;}
else if (mx[y][x]
else r=mid-1;
}
return rel;
}
第二题：
TreeNode reverseTree(TreeNode root) {
TreeNode p=null,c=root;
while (c!=null) {
TreeNode t1=c.left,t2=c.right;
c.left=t2;c.right=p;p=c;c=t1;
}
TreeNode rel=p;
while (p.right!=null) {
p.left=p.right.left;
p.right.left=null;
p=p.right;
}
return rel;
} |
l*****a
发帖数: 14598 | 42 第一题如果相等怎么办
第二题，如果是三楼的情况返回什么
【在 y**********a 的大作中提到】
: 第一题：
: List binarySearch(int[][]mx, int k) {
: List rel=new ArrayList<>();
: for (int m=mx.length,n=mx[0].length,l=0,r=m*n-1;l<=r;) {
: int mid=l+(r-l)/2;
: int y=mid/n,x=mid%n;
: if (mx[y][x]==k) {rel.add(y);rel.add(x);break;}
: else if (mx[y][x]: else r=mid-1;
: }
|
y**********a
发帖数: 824 | 43
第一题要进一步 clarify
第二题是
1 2
/ \ -> / \
2 3 3 1
【在 l*****a 的大作中提到】
: 第一题如果相等怎么办
: 第二题，如果是三楼的情况返回什么
|
l*****a
发帖数: 14598 | 44 没看清题？这个期待什么结果
1
/
2 3
4
【在 y**********a 的大作中提到】
:
: 第一题要进一步 clarify
: 第二题是
: 1 2
: / \ -> / \
: 2 3 3 1
|
l*****a
发帖数: 14598 | 45 原题已经告诉你有equal的情况
所以你的code不能得分
【在 y**********a 的大作中提到】
:
: 第一题要进一步 clarify
: 第二题是
: 1 2
: / \ -> / \
: 2 3 3 1
|
y**********a
发帖数: 824 | 46
改了一下第一题。
boolean equal(int[][]mx, int i, int j) {
int m=mx.length,n=mx[0].length;
if (i<0||j>=m*n||j<0||i>=m*n) return false;
return mx[i/n][i%n]==mx[j/n][j%n];
}
int binarySearchBound(int[][]mx, int k, boolean lower) {
for (int m=mx.length,n=mx[0].length,l=0,r=m*n-1;l<=r;) {
int mid=l+(r-l)/2;
if (mx[mid/n][mid%n]==k) {
if (lower)
if (!equal(mx, mid, mid-1)) return mid;
else r=mid-1;
else
if (!equal(mx, mid, mid+1)) return mid;
else l=mid+1;
} else if (mx[mid/n][mid%n]
else r=mid-1;
}
return -1;
}
public List> binarySearch(int[][]mx, int k) {
int n=mx[0].length;
int lb=binarySearchBound(mx, k, true), ub=binarySearchBound(mx, k,
false);
List> rel=new ArrayList<>();
if (lb==-1)return rel;
for (int i=lb;i<=ub;++i) {
int y=i/n,x=i%n;
List t=new ArrayList<>();
t.add(y);t.add(x);
rel.add(t);
}
return rel;
}
【在 l*****a 的大作中提到】
: 原题已经告诉你有equal的情况
: 所以你的code不能得分
|
l****s
发帖数: 75 | 47 第二题其实就是一个reverse linked list的变种。
TreeNode* flipUpsideDown2(TreeNode* root)
{
if (!root) return NULL;
TreeNode* dummy = new TreeNode(0);
dummy->left = root;
TreeNode* right = root->right;
root = root->left;
dummy->left->left = NULL;
dummy->left->right = NULL;
while (root)
{
TreeNode* tmp = root;
root = root->left;
tmp->left = right;
right = tmp->right;
tmp->right = dummy->left;
dummy->left = tmp;
}
root = dummy->left;
delete dummy;
return root;
}
【在 y**********a 的大作中提到】
: 第一题：
: List binarySearch(int[][]mx, int k) {
: List rel=new ArrayList<>();
: for (int m=mx.length,n=mx[0].length,l=0,r=m*n-1;l<=r;) {
: int mid=l+(r-l)/2;
: int y=mid/n,x=mid%n;
: if (mx[y][x]==k) {rel.add(y);rel.add(x);break;}
: else if (mx[y][x]: else r=mid-1;
: }
|
s**x
发帖数: 7506 | 48 第一题估计出题的人都晕了， 你自己想想吧， 就是不折不扣的 binary search. 2D
array in that case is exactly 1D sorted array! no trick at all, exactly the
same.
1 2 3
4 5 6
is the same as 1 2 3 4 5 6!
【在 j*****8 的大作中提到】
: 第一题，按照cc150的解法，从右上角开始向左或向下二分查找的话，针对这个首尾可
: 能相等的情况不需要额外的 处理把
|
p*****2
发帖数: 21240 | 49 第二题这样怎么样
TreeNode dfs(TreeNode node, TreeNode parent){
if(node==null) return null;
TreeNode left_res = dfs(node.left,node);
if(parent!=null){
node.left = parent.right;
node.right = parent;
}
return left_res!=null?left_res:node;
}
TreeNode convert(TreeNode root){
return dfs(root,null);
} |
m*****k
发帖数: 731 | 50 出题的人就是想看面试者能否把这个larger(or
equal)条件用上而不是fall into
the other one 吧。
the
【在 s**x 的大作中提到】
: 第一题估计出题的人都晕了， 你自己想想吧， 就是不折不扣的 binary search. 2D
: array in that case is exactly 1D sorted array! no trick at all, exactly the
: same.
: 1 2 3
: 4 5 6
: is the same as 1 2 3 4 5 6!
|
|
|
m*****k
发帖数: 731 | 51 how about
1
3
what is the result?
【在 l*****a 的大作中提到】
: 没看清题？这个期待什么结果
: 1
: /
: 2 3
: 4
|
m*****k
发帖数: 731 | 52 reverse(TreeNode n)
{
if (n==null){
return null;
}
if(n.left==null){
return n;
}
Node root = reverse(n.left);
n.left.left = n.right;
n.right = null;
n.left.right = n;
n.left = null;
return root;
} |
p****a
发帖数: 447 | |
t*****a
发帖数: 106 | 54 第一题是leetcode原题，不是search index, 是Search for a Range。直接返回一个
range |
g********r
发帖数: 89 | 55 Can the code handle?
1
/
2 3
4
【在 p*****2 的大作中提到】
: 第二题这样怎么样
: TreeNode dfs(TreeNode node, TreeNode parent){
: if(node==null) return null;
: TreeNode left_res = dfs(node.left,node);
:
: if(parent!=null){
: node.left = parent.right;
: node.right = parent;
: }
: return left_res!=null?left_res:node;
|
g********r
发帖数: 89 | 56 What about this:
TreeNode *flipTree(TreeNode *root)
{
if(!root) return NULL;
if(root->left){ // recursively deal with left child
TreeNode *newRoot = flipTree(root->left);
root->left->left = root->right;
root->left->right = root;
return newRoot;
}
else if(root->right){ //no left child, has right child, can only happen
at left most node
root->right->right = root;
return root->right;
}
else{ //left most node is leaf
return root;
}
}
after calling flipTree, do not forget to set root->left and root->right to
NULL.
【在 g********r 的大作中提到】
: Can the code handle?
: 1
: /
: 2 3
:
: 4
|
f**********t
发帖数: 1001 | 57 // Given a binary tree where all the right nodes are either leaf nodes with
a sibling (a left node that shares the same parent node) or empty, flip it
upside down and turn it into a tree where the original right nodes turned
into left leaf nodes. Return the new root.
// {1,2,3,4,5}, to [4,5,2,#,#,3,1]
class BiTree {
struct Node {
char val;
Node *left, *right;
Node(char c) : val(c), left(nullptr), right(nullptr) {}
};
Node *_root;
public:
BiTree(string s) {
queue qu;
if (s.empty()) {
_root = nullptr;
return;
}
_root = new Node(s[0]);
qu.push(_root);
auto it = s.begin();
while (!qu.empty()) {
Node *cur = qu.front();
qu.pop();
if (++it == s.end()) {
return;
}
if (*it != '#') {
cur->left = new Node(*it);
qu.push(cur->left);
}
if (++it == s.end()) {
return;
}
if (*it != '#') {
cur->right = new Node(*it);
qu.push(cur->right);
}
}
}
void Dump() {
if (!_root) {
return;
}
queue qu;
qu.push(_root);
string s{_root->val};
while (!qu.empty()) {
Node *cur = qu.front();
qu.pop();
if (cur->left) {
s.push_back(cur->left->val);
qu.push(cur->left);
} else {
s.push_back('#');
}
if (cur->right) {
s.push_back(cur->right->val);
qu.push(cur->right);
} else {
s.push_back('#');
}
}
cout << "dump: " << s << endl;
}
void Flip() {
if (!_root) {
return;
}
Node *cur = _root;
stack sk;
while (cur) {
sk.push(cur);
cur = cur->left;
}
_root = sk.top();
sk.pop();
cur = _root;
while (!sk.empty()) {
cur->right = sk.top();
cur->left = sk.top()->right;
cur->left->left = nullptr;
cur->left->right = nullptr;
cur = cur->right;
sk.pop();
}
cur->left = nullptr;
cur->right = nullptr;
}
Node* FlipR(Node *root) {
if (root->left) {
Node *r = FlipR(root->left);
root->left->left = root->right;
root->left->right = root;
root->left = nullptr;
root->right = nullptr;
return r;
} else {
return root;
}
}
void FlipRecusion() {
if (!_root) {
return;
}
_root = FlipR(_root);
}
};
void BiTreeTest() {
BiTree bt("12345");
bt.Dump();
bt.FlipRecusion();
bt.Dump();
} |
