r*****t
发帖数: 68 | 1 第一题
Find deepest nodes in a binary tree.
Q: binary search tree? A: no (这个问题好像没什么用……)
Q: all of the deepest nodes, or just one? A: find the right-most deepest
node
第二题
Suppose you have a dictionary of words. Given a abbreviation like “i18n”,
determine if it is unique in the dictionary.
Q: rephrasing the question, determine if no other words can be abbreviated
as "i18n", correct? A: yes |
p*****2
发帖数: 21240 | 2 “i18n” 是什么的abbreviation? |
q****m
发帖数: 177 | 3 第一题是 leetcode上的 level order traversal的一个衍生题目吧？
就是一层层的往下走.
,
【在 r*****t 的大作中提到】
: 第一题
: Find deepest nodes in a binary tree.
: Q: binary search tree? A: no (这个问题好像没什么用……)
: Q: all of the deepest nodes, or just one? A: find the right-most deepest
: node
: 第二题
: Suppose you have a dictionary of words. Given a abbreviation like “i18n”,
: determine if it is unique in the dictionary.
: Q: rephrasing the question, determine if no other words can be abbreviated
: as "i18n", correct? A: yes
|
r*****t
发帖数: 68 | 4 internationalization，所以才会简写:P
【在 p*****2 的大作中提到】
: “i18n” 是什么的abbreviation?
|
q****m
发帖数: 177 | 5 第二道题感觉如何确定 abbreviation 不是很清楚阿。 比如 doctor ,我可以
用 dr.， 也可以用 dctr
,
【在 r*****t 的大作中提到】
: 第一题
: Find deepest nodes in a binary tree.
: Q: binary search tree? A: no (这个问题好像没什么用……)
: Q: all of the deepest nodes, or just one? A: find the right-most deepest
: node
: 第二题
: Suppose you have a dictionary of words. Given a abbreviation like “i18n”,
: determine if it is unique in the dictionary.
: Q: rephrasing the question, determine if no other words can be abbreviated
: as "i18n", correct? A: yes
|
p*****2
发帖数: 21240 | 6
简写都有什么格式？
i18n 是因为i和n之间有18个字母？这是唯一的简写格式？
【在 r*****t 的大作中提到】
: internationalization，所以才会简写:P
|
S*******w
发帖数: 24236 | 7 第一题：
//return the right most deepest node
int deepest (struct node * root, struct node ** result) {
struct node * deepest_l;
struct node * deepest_r;
int l, r;
if(root == NULL) {
*result = NULL;
return 0;
}
l = deepest(root->left, &deepest_l);
r = deepest(root->right, &deepest_r);
if(l > r) {
if(deepest_l != NULL) *result = deepest_l;
else *result = root;
return 1 + l;
} else {
if(deepest_r != NULL) *result = deepest_r;
else *result = root;
return 1 + r;
}
}
请指正。
,
【在 r*****t 的大作中提到】
: 第一题
: Find deepest nodes in a binary tree.
: Q: binary search tree? A: no (这个问题好像没什么用……)
: Q: all of the deepest nodes, or just one? A: find the right-most deepest
: node
: 第二题
: Suppose you have a dictionary of words. Given a abbreviation like “i18n”,
: determine if it is unique in the dictionary.
: Q: rephrasing the question, determine if no other words can be abbreviated
: as "i18n", correct? A: yes
|
e***s
发帖数: 799 | |
e***s
发帖数: 799 | 9 你是想找出树的深度？题目好像不是这样说的啊
【在 S*******w 的大作中提到】
: 第一题：
: //return the right most deepest node
: int deepest (struct node * root, struct node ** result) {
: struct node * deepest_l;
: struct node * deepest_r;
: int l, r;
: if(root == NULL) {
: *result = NULL;
: return 0;
: }
|
e***s
发帖数: 799 | 10 第二题O(n) n = 字典大小？
难点在哪？ |
|
|
C***U
发帖数: 2406 | |
w**z
发帖数: 8232 | 12 二爷一点就透啊，l10n, localization.
【在 p*****2 的大作中提到】
:
: 简写都有什么格式？
: i18n 是因为i和n之间有18个字母？这是唯一的简写格式？
|
p*****2
发帖数: 21240 | 13
大牛有什么想法？感觉建立一个hashmap就可以了？
【在 w**z 的大作中提到】
: 二爷一点就透啊，l10n, localization.
|
S*******w
发帖数: 24236 | 14 result返回deepest node
【在 e***s 的大作中提到】
: 你是想找出树的深度？题目好像不是这样说的啊
|
C***U
发帖数: 2406 | 15 可不可以根据首字母 尾字母 长度构建array? 然后每个位置对应一个linked list?
【在 p*****2 的大作中提到】
:
: 大牛有什么想法？感觉建立一个hashmap就可以了？
|
e***s
发帖数: 799 | 16 但是你return type 是 int啊
【在 S*******w 的大作中提到】
: result返回deepest node
|
r*****t
发帖数: 68 | 17 i18n是唯一的简写格式，表示i跟n之间有18个字母，doctor会被简写成d4r
【在 p*****2 的大作中提到】
:
: 大牛有什么想法？感觉建立一个hashmap就可以了？
|
p*****2
发帖数: 21240 | 18
list?
跟hashmap比有啥好处吗？
【在 C***U 的大作中提到】
: 可不可以根据首字母 尾字母 长度构建array? 然后每个位置对应一个linked list?
|
w***o
发帖数: 109 | 19 来一个不recursive的：
Node findDeepestNode(Node root) {
Stack s = new Stack();
Stack d = new Stack();
int max = -1; Node x = null;
s.push(root); d.push(0);
while(!s.empty()) {
int dep = d.pop();
Node n = s.pop();
if(n.left == null && n.right == null) {
if(dep > max) {
max = dep;
x = n;
}
} else {
if(n.left != null) {s.push(n.left); d.push(dep + 1);}
if(n.right != null) {s.push(n.right); d.push(dep + 1);}
}
}
return x;
} |
w***o
发帖数: 109 | 20 第二题
可不可以把字典里的所有词建一个HashMap，(假设都是小写字母)
hashcode = (str.length * 26 + str[0]) * 26 + str[str.length - 1];
这样，任给一个abbr都能在O（1）返回是否是唯一的。 |
|
|
e***s
发帖数: 799 | 21 我就不懂了，不就是BFS最后一个节点吗？
public static BTNode DeepestRightMostNode(BTNode root)
{
if (root == null)
return null;
Queue queue = new Queue();
queue.Enqueue(root);
BTNode temp = root;
while(queue.Count > 0)
{
temp = queue.Dequeue();
if(temp.Left != null)
queue.Enqueue(temp.Left);
if(temp.Right != null)
queue.Enqueue(temp.Right);
}
return temp;
}
【在 w***o 的大作中提到】
: 来一个不recursive的：
: Node findDeepestNode(Node root) {
: Stack s = new Stack();
: Stack d = new Stack();
: int max = -1; Node x = null;
: s.push(root); d.push(0);
: while(!s.empty()) {
: int dep = d.pop();
: Node n = s.pop();
: if(n.left == null && n.right == null) {
|
e***s
发帖数: 799 | 22 自己要设计Hash Function吗？请问是怎么设计的？
【在 w***o 的大作中提到】
: 第二题
: 可不可以把字典里的所有词建一个HashMap，(假设都是小写字母)
: hashcode = (str.length * 26 + str[0]) * 26 + str[str.length - 1];
: 这样，任给一个abbr都能在O（1）返回是否是唯一的。
|
d**********x
发帖数: 4083 | 23 如果是英文词典，则只要建立两个 52 * 52 的 long long 数组即可，对于每一个长度
，用bitmap。
如果是比较大的字符集，则不用数组，用hashmap.
【在 w***o 的大作中提到】
: 第二题
: 可不可以把字典里的所有词建一个HashMap，(假设都是小写字母)
: hashcode = (str.length * 26 + str[0]) * 26 + str[str.length - 1];
: 这样，任给一个abbr都能在O（1）返回是否是唯一的。
|
m**********0
发帖数: 356 | 24 能具体说说这个hashcode的原理是什么？土人没看明白。谢谢！
【在 w***o 的大作中提到】
: 第二题
: 可不可以把字典里的所有词建一个HashMap，(假设都是小写字母)
: hashcode = (str.length * 26 + str[0]) * 26 + str[str.length - 1];
: 这样，任给一个abbr都能在O（1）返回是否是唯一的。
|
g*****e
发帖数: 282 | 25 dfs自然也可以做。不过应该先访问right sub tree
很多时候dfs/recursive 可以写出看着很cool的code
【在 e***s 的大作中提到】
: 我就不懂了，不就是BFS最后一个节点吗？
: public static BTNode DeepestRightMostNode(BTNode root)
: {
: if (root == null)
: return null;
: Queue queue = new Queue();
: queue.Enqueue(root);
: BTNode temp = root;
: while(queue.Count > 0)
: {
|
w***o
发帖数: 109 | 26 好，比我的要简洁。
【在 e***s 的大作中提到】
: 我就不懂了，不就是BFS最后一个节点吗？
: public static BTNode DeepestRightMostNode(BTNode root)
: {
: if (root == null)
: return null;
: Queue queue = new Queue();
: queue.Enqueue(root);
: BTNode temp = root;
: while(queue.Count > 0)
: {
|
