c**y
发帖数: 73 | 1 1)给的一个double linkedlist，给定一个array，包含若干double linkedlist的节点
的地址，统计这个array包含的互相独立部分的数目。用例子说明吧。
一个double linkedlist是A<>B<>C<>...<>X<>Y<>Z（一共26个节点，从A到Z）。
如果array是{A，Z}，那个return 2，因为A和Z两个不相邻的。
如果array是{A，B，D}，那个return 2，因为AB是一个部分，D是另外一个独立的部分。
如果array是{A，B，C，。。。，Y，Z}，那么return 1，因为AtoZ是一个独立的部分。
2)从给定的sorted的array如何build的一个balanced的binary tree？
开始给了一个recursive的方法，后来要一个iterative。
iterative的解法：
a.先建立一个空的balanced binary tree
建立这个空的balanced binary tree的方法可以参见如何用array来表示一个heap的方
法。具体是对于节点i，它的left和right child可以是节点2*i和2*i+1。这里i必须是
从1开始的，不能是0，所以不能直接用array中元素的idx。
b.然后traverse这个空的binary tree，把sorted array的值一个一个拷贝进去。
for (TreeNode *node = minBST(root); node != NULL; node = successorBST(node))
{
node->value = sortedArray[i++];
}
3)reservoir sampling的题。一个无限长的数组，一个buffer有K个cells，如何scan这
个数组一次，并且以相同概率采样K个元素到这个buffer里。 |
r*******e
发帖数: 7583 | 2 第1题跟那个找数列最长连续子序列一样把
把array所有元素都放进hashset
对每一个元素，如果在hashset里，往左扫，往右扫，把遇到的元素都从hashset里删掉
扫完了计数器加一
分。
))
【在 c**y 的大作中提到】
: 1)给的一个double linkedlist，给定一个array，包含若干double linkedlist的节点
: 的地址，统计这个array包含的互相独立部分的数目。用例子说明吧。
: 一个double linkedlist是A<>B<>C<>...<>X<>Y<>Z（一共26个节点，从A到Z）。
: 如果array是{A，Z}，那个return 2，因为A和Z两个不相邻的。
: 如果array是{A，B，D}，那个return 2，因为AB是一个部分，D是另外一个独立的部分。
: 如果array是{A，B，C，。。。，Y，Z}，那么return 1，因为AtoZ是一个独立的部分。
: 2)从给定的sorted的array如何build的一个balanced的binary tree？
: 开始给了一个recursive的方法，后来要一个iterative。
: iterative的解法：
: a.先建立一个空的balanced binary tree
|
r**h
发帖数: 1288 | 3 我觉得第一题从左往右扫一轮就行了
【在 r*******e 的大作中提到】
: 第1题跟那个找数列最长连续子序列一样把
: 把array所有元素都放进hashset
: 对每一个元素，如果在hashset里，往左扫，往右扫，把遇到的元素都从hashset里删掉
: 扫完了计数器加一
:
: 分。
: ))
|
w**********o
发帖数: 140 | 4 第一輪， 可不可以直接用strongly connected components 來。 |
r*******e
发帖数: 7583 | 5 不要被给的例子误导了
array里面的指针不一定按照list order来
删掉
【在 r**h 的大作中提到】
: 我觉得第一题从左往右扫一轮就行了
|
s********x
发帖数: 914 | 6 如果给的array是sorted的话，yes
不是的话，sort要nlogn， 用hash 是linear
【在 r**h 的大作中提到】
: 我觉得第一题从左往右扫一轮就行了
|
r**h
发帖数: 1288 | 7 嗯。。。是我搞错了
不过题目要求的是双向链表中相邻的元素在array中也相邻，还是说只是看链表中所有
被array映射到的节点分成几个连续子段呢？
{A, B, Z, C, D}算2还是3
【在 r*******e 的大作中提到】
: 不要被给的例子误导了
: array里面的指针不一定按照list order来
:
: 删掉
|
B**L
发帖数: 33 | |
s********x
发帖数: 914 | 9 2吧
class CharNode {
private char value;
private CharNode next;
private CharNode previous;
public CharNode getPrevious() {
return previous;
}
public void setPrevious(CharNode previous) {
this.previous = previous;
}
public char getValue() {
return value;
}
public void setValue(char value) {
this.value = value;
}
public CharNode getNext() {
return next;
}
public void setNext(CharNode next) {
this.next = next;
}
}
public static int findHowManyContinousIntervalInArray(CharNode listRoot,
char[] array)
{
// Key is char, value is the index of the group count
Map map = new HashMap();
for (char a : array)
{
map.put(a, 0);
}
int count = 0;
for (CharNode n = listRoot; n != null; n = n.getNext())
{
char key = n.getValue();
if (map.containsKey(key))
{
CharNode prev = n.getPrevious();
if (prev != null && map.containsKey(prev.getValue()) && map.
get(prev.getValue()) != 0)
{
map.put(key, map.get(prev.getValue())); // use previous
char's group index
continue;
}
CharNode next = n.getNext();
if (next != null && map.containsKey(next.getValue()) && map.
get(next.getValue()) != 0)
{
map.put(key, map.get(next.getValue())); // use next char
's group index
continue;
}
map.put(key, ++count);
}
}
return count;
}
public static void main(String[] args) {
CharNode root = new CharNode();
root.setValue('A');
CharNode prev = root;
for(int i = 1; i < 26; i++)
{
CharNode n = new CharNode();
n.setValue((char)('A' + i));
prev.setNext(n);
n.setPrevious(prev);
prev = n;
}
char[] a = new char[] {'A', 'B', 'Z', 'C', 'D' };
int c = findHowManyContinousIntervalInArray(root, a);
System.out.print(c);
}
【在 r**h 的大作中提到】
: 嗯。。。是我搞错了
: 不过题目要求的是双向链表中相邻的元素在array中也相邻，还是说只是看链表中所有
: 被array映射到的节点分成几个连续子段呢？
: {A, B, Z, C, D}算2还是3
|
h*****a
发帖数: 1718 | 10 2）iteratively的建一个空树和原问题一个难度吧。你能把你的code show show么？感
觉如果硬要去掉递归，还不如用个栈来机械的模拟递归。
分。
【在 c**y 的大作中提到】
: 1)给的一个double linkedlist，给定一个array，包含若干double linkedlist的节点
: 的地址，统计这个array包含的互相独立部分的数目。用例子说明吧。
: 一个double linkedlist是A<>B<>C<>...<>X<>Y<>Z（一共26个节点，从A到Z）。
: 如果array是{A，Z}，那个return 2，因为A和Z两个不相邻的。
: 如果array是{A，B，D}，那个return 2，因为AB是一个部分，D是另外一个独立的部分。
: 如果array是{A，B，C，。。。，Y，Z}，那么return 1，因为AtoZ是一个独立的部分。
: 2)从给定的sorted的array如何build的一个balanced的binary tree？
: 开始给了一个recursive的方法，后来要一个iterative。
: iterative的解法：
: a.先建立一个空的balanced binary tree
|
|
|
p*****2
发帖数: 21240 | 11
简单点用个queue就行了吧？
【在 h*****a 的大作中提到】
: 2）iteratively的建一个空树和原问题一个难度吧。你能把你的code show show么？感
: 觉如果硬要去掉递归，还不如用个栈来机械的模拟递归。
:
: 分。
|
p*****2
发帖数: 21240 | 12
这个说的不错。我也被误导了。这样的话，你的解法应该可以。
【在 r*******e 的大作中提到】
: 不要被给的例子误导了
: array里面的指针不一定按照list order来
:
: 删掉
|
h*****a
发帖数: 1718 | 13 Not obvious to me. Can you post the code?
【在 p*****2 的大作中提到】
:
: 这个说的不错。我也被误导了。这样的话，你的解法应该可以。
|
s********x
发帖数: 914 | 14 大概是这个思路吧，没有测
public static TreeNode sortedArrayToBST(int[] a)
{
TreeNode root = new TreeNode();
int left = 0, right = a.length - 1;
Queue indexes = new LinkedList();
Queue nodes = new LinkedList();
nodes.add(root);
indexes.add(left);
indexes.add(right);
while (!indexes.isEmpty())
{
left = indexes.poll();
right = indexes.poll();
TreeNode p = nodes.poll();
int mid = left + (right - left) >>> 1;
p.setValue(a[mid]);
TreeNode leftChild = null, rightChild = null;
if (left <= mid - 1)
{
leftChild = new TreeNode();
indexes.add(left);
indexes.add(mid - 1);
nodes.add(leftChild);
}
if (mid + 1 < right)
{
rightChild = new TreeNode();
indexes.add(mid+1);
indexes.add(right);
nodes.add(rightChild);
}
p.setLeft(leftChild);
p.setRight(rightChild);
}
return root;
}【 在 halfsea (tough) 的大作中提到: 】 |
a******e
发帖数: 710 | 15 既然是2，那这个数组{A,B,Z,C,D}就跟{A,B,C,D,Z}一样喽？
那从左到右扫一遍可以么？
【在 s********x 的大作中提到】
: 2吧
: class CharNode {
: private char value;
: private CharNode next;
: private CharNode previous;
: public CharNode getPrevious() {
: return previous;
: }
: public void setPrevious(CharNode previous) {
: this.previous = previous;
|
r**h
发帖数: 1288 | 16 数组存的是链表节点的地址啊，没办法sort
除非你额外做一个hash之类把链表节点的地址映射成该节点在链表中的位置
【在 a******e 的大作中提到】
: 既然是2，那这个数组{A,B,Z,C,D}就跟{A,B,C,D,Z}一样喽？
: 那从左到右扫一遍可以么？
|
c**y
发帖数: 73 | 17 {A, B, Z, C, D}是算2
解法：用一个HashTable来记录array中已经被处理过的元素（即地址(pointer)）。每
次处理一个新的元素，把这个地址加入HashTable。
每次处理一个array里新的地址（元素），看看这个地址是不是已经HashTable里了，如
果是的话，就不更新count，因为已经处理过了。直接跳过。
如果不在HashTable中，根据这个地址，找到相应元素的两个neighbor（还是地址，有
可能为空）。
如果两个neighbor都不空而且不在HashTable中，count加1，因为是一个新的独立部分。
如果有只有一个neighbor在HashTable中的话，count不变，因为这个新的地址的节点属
于已经处理的独立部分中的一个。
如果两个neighbor都在的话，count减1，因为这个地址的元素可以把原来两个独立的部
分连接成一个（即merge）。
处理完这个元素e.g.地址，把这个地址加进HashTable中。
这样只要scan这个array一次，用一个HashTable。算法复杂度是O(m)，m是array中地址
的个数。
另一种解法是scan这个double linkedlist（楼上提到过了），也可以用hashtable来存
储是否在array中的记录。因为每个节点访问一次，所以是0(n)，n是list中节点的数目。 |
c**y
发帖数: 73 | 18 可以用如下方法建立一个空的balanced的binary tree，复杂度是O(n)，n是给定sorted
array中元素的个数。TreeNode的定义可以参照leetcode上的binary tree的定义。如
果方便后面步骤的traversal，需要加入一个parent指针元素在TreeNode的定义中。
TreeNode **pp_node = (TreeNode **)malloc(n * sizeof(TreeNode *));
for (int i = 0; i < n; i++) {
pp_node[i] = new TreeNode(0);
}
// build a balanaced binary tree by linking them
for (int i = 1; i <= n; i++) {
if (2 * i <= n) {
// link left child node
pp_node[i - 1]->left = pp_node[2 * i - 1];
// link back to parent node
pp_node[2 * i - 1]->parent = pp_node[i - 1];
}
if (2 * i + 1 <= n) {
// linlke right child node
pp_node[i - 1]->right = pp_node[2 * i + 1 - 1];
// link back to parent node
pp_node[2 * i + 1 - 1]->parent = pp_node[i - 1];
}
}
pp_node[0]指向这个空树的root
【在 h*****a 的大作中提到】
: 2）iteratively的建一个空树和原问题一个难度吧。你能把你的code show show么？感
: 觉如果硬要去掉递归，还不如用个栈来机械的模拟递归。
:
: 分。
|
q********s
发帖数: 1032 | 19 第三题是错的，怎么可能uniformly sampling from infinitely many discrete set.
【在 c**y 的大作中提到】
: 1)给的一个double linkedlist，给定一个array，包含若干double linkedlist的节点
: 的地址，统计这个array包含的互相独立部分的数目。用例子说明吧。
: 一个double linkedlist是A<>B<>C<>...<>X<>Y<>Z（一共26个节点，从A到Z）。
: 如果array是{A，Z}，那个return 2，因为A和Z两个不相邻的。
: 如果array是{A，B，D}，那个return 2，因为AB是一个部分，D是另外一个独立的部分。
: 如果array是{A，B，C，。。。，Y，Z}，那么return 1，因为AtoZ是一个独立的部分。
: 2)从给定的sorted的array如何build的一个balanced的binary tree？
: 开始给了一个recursive的方法，后来要一个iterative。
: iterative的解法：
: a.先建立一个空的balanced binary tree
|
c**y
发帖数: 73 | 20 改了说明。
【在 q********s 的大作中提到】
: 第三题是错的，怎么可能uniformly sampling from infinitely many discrete set.
|
|
|
a******e
发帖数: 710 | 21 这个方法很漂亮啊。
sorted
【在 c**y 的大作中提到】
: 可以用如下方法建立一个空的balanced的binary tree，复杂度是O(n)，n是给定sorted
: array中元素的个数。TreeNode的定义可以参照leetcode上的binary tree的定义。如
: 果方便后面步骤的traversal，需要加入一个parent指针元素在TreeNode的定义中。
: TreeNode **pp_node = (TreeNode **)malloc(n * sizeof(TreeNode *));
: for (int i = 0; i < n; i++) {
: pp_node[i] = new TreeNode(0);
: }
: // build a balanaced binary tree by linking them
: for (int i = 1; i <= n; i++) {
: if (2 * i <= n) {
|
a******e
发帖数: 710 | 22 开始只是想到了O(n)的算法。 O(m)的算法可以这么实现
#include
#include
using namespace std;
struct DListNode {
char val;
DListNode *prev;
DListNode * next;
DListNode(char v): val(v), prev(nullptr), next(nullptr) {}
};
void printList(DListNode* head){
while (head!=nullptr) {
cout<val<<", ";
head = head->next;
}
cout<
}
void printSet(unordered_set &s) {
for (auto iter=s.begin(); iter!=s.end(); ++iter)
cout<<(*iter)->val<<", ";
cout<
}
// 这个函数每次把s中第一个元素所在的connected component所含元素从s中删除。
// 这样s中的connected component数量减少1.
void explore(unordered_set &s) {
DListNode* prev = *(s.begin());
DListNode* next = prev;
s.erase(prev);
while (prev!=nullptr) {
if (s.find(prev->prev)!=s.end()) {
prev = prev->prev;
s.erase(prev);
} else {
prev = nullptr;
}
}
while (next!=nullptr) {
if (s.find(next->next)!=s.end()) {
next = next->next;
s.erase(next);
} else {
next = nullptr;
}
}
}
int numOfConnectedComponent(DListNode *head, unordered_set &s) {
int count = 0;
while (!s.empty()) {
explore(s);
++count;
}
return count;
}
int main()
{
DListNode *head = new DListNode('A');
DListNode *prev = head;
unordered_set set_ptr;
for (int i=1; i<26; ++i) {
DListNode *new_n = new DListNode(i+'A');
new_n->prev = prev;
prev->next = new_n;
prev = prev->next;
if (rand()%100<60) set_ptr.insert(prev);
}
printList(head);
printSet(set_ptr);
cout<<"Number of connected componet is "<
set_ptr)<
return 0;
}
分。
【在 c**y 的大作中提到】
: {A, B, Z, C, D}是算2
: 解法：用一个HashTable来记录array中已经被处理过的元素（即地址(pointer)）。每
: 次处理一个新的元素，把这个地址加入HashTable。
: 每次处理一个array里新的地址（元素），看看这个地址是不是已经HashTable里了，如
: 果是的话，就不更新count，因为已经处理过了。直接跳过。
: 如果不在HashTable中，根据这个地址，找到相应元素的两个neighbor（还是地址，有
: 可能为空）。
: 如果两个neighbor都不空而且不在HashTable中，count加1，因为是一个新的独立部分。
: 如果有只有一个neighbor在HashTable中的话，count不变，因为这个新的地址的节点属
: 于已经处理的独立部分中的一个。
|
q********s
发帖数: 1032 | 23 有放回的话，(m-1)/m 选之前的数，1/m选新数m.
【在 c**y 的大作中提到】
: 改了说明。
|
h*****a
发帖数: 1718 | 24 不错，不过值得注意的是这样build的tree和递归建的树形状可能是不同的。但都是
balanced。
public TreeNode buildIteratively(int[] a) {
int n = a.length;
TreeNode root = createTreeOfN(n);
Stack s = new Stack();
TreeNode cur = root;
int i=0;
while (cur != null || !s.isEmpty()) {
if (cur == null) {
cur = s.pop();
cur.val = a[i++];
cur = cur.right;
} else {
s.push(cur);
cur = cur.left;
}
}
return root;
}
private TreeNode createTreeOfN(int n) {
if (n==0) return null;
TreeNode[] nodes = new TreeNode[n];
for (int i=n-1; i>=0; i--) {
nodes[i] = new TreeNode(0);
if (i*2+1 < n) {
nodes[i].left = nodes[i*2+1];
}
if (i*2+2 < n) {
nodes[i].right = nodes[i*2+2];
}
}
return nodes[0];
}
sorted
【在 c**y 的大作中提到】
: 可以用如下方法建立一个空的balanced的binary tree，复杂度是O(n)，n是给定sorted
: array中元素的个数。TreeNode的定义可以参照leetcode上的binary tree的定义。如
: 果方便后面步骤的traversal，需要加入一个parent指针元素在TreeNode的定义中。
: TreeNode **pp_node = (TreeNode **)malloc(n * sizeof(TreeNode *));
: for (int i = 0; i < n; i++) {
: pp_node[i] = new TreeNode(0);
: }
: // build a balanaced binary tree by linking them
: for (int i = 1; i <= n; i++) {
: if (2 * i <= n) {
|
r*********n
发帖数: 4553 | 25 1)给的一个double linkedlist，给定一个array，包含若干double linkedlist的节点
的地址，统计这个array包含的互相独立部分的数目。用例子说明吧。
一个double linkedlist是A<>B<>C<>...<>X<>Y<>Z（一共26个节点，从A到Z）。
如果array是{Z,A}，那个return 2，因为A和Z两个不相邻的。
如果array是{A,D,B}，那个return 2，因为AB是一个部分，D是另外一个独立的部分。
如果array是{A，B，C，。。。，Y，Z}，那么return 1，因为AtoZ是一个独立的部分。
不能理解这个题意呢。LZ的例子里面a-z都是相连的，为什么
array是{Z,A}，那个return 2
相互独立 = 不相邻？ |
p*****2
发帖数: 21240 | 26
http://leetcode.quora.com/Convert-Sorted-Array-to-Binary-Search
【在 h*****a 的大作中提到】
: Not obvious to me. Can you post the code?
|
f*********m
发帖数: 726 | 27 第一题也可以用bfs，dfs来给每个元素上色吧？颜色一样的就在一个类里面，最后算有
多少种颜色。
【在 r*******e 的大作中提到】
: 第1题跟那个找数列最长连续子序列一样把
: 把array所有元素都放进hashset
: 对每一个元素，如果在hashset里，往左扫，往右扫，把遇到的元素都从hashset里删掉
: 扫完了计数器加一
:
: 分。
: ))
|
h****p
发帖数: 87 | |
Z**********4
发帖数: 528 | 29
【在 c**y 的大作中提到】
: 1)给的一个double linkedlist，给定一个array，包含若干double linkedlist的节点
: 的地址，统计这个array包含的互相独立部分的数目。用例子说明吧。
: 一个double linkedlist是A<>B<>C<>...<>X<>Y<>Z（一共26个节点，从A到Z）。
: 如果array是{A，Z}，那个return 2，因为A和Z两个不相邻的。
: 如果array是{A，B，D}，那个return 2，因为AB是一个部分，D是另外一个独立的部分。
: 如果array是{A，B，C，。。。，Y，Z}，那么return 1，因为AtoZ是一个独立的部分。
: 2)从给定的sorted的array如何build的一个balanced的binary tree？
: 开始给了一个recursive的方法，后来要一个iterative。
: iterative的解法：
: a.先建立一个空的balanced binary tree
|
a*****n
发帖数: 158 | |
|
|
l*****a
发帖数: 14598 | 31 早就有结果了。
【在 a*****n 的大作中提到】
: 感觉不是太难啊。。希望有好消息。。。
|
R*********d
发帖数: 34 | 32 结果如何？
【在 l*****a 的大作中提到】
: 早就有结果了。
|
f******n
发帖数: 279 | |
b****f
发帖数: 138 | |
w*********x
发帖数: 3 | 35 赞分享,有个问题关于第一题,"统计这个array包含的互相独立部分的数目".所以连着的
算一个部分?
如果array是ADB算2部分,ADBC也算2个部分,还是1个部分?array里有重复ADBCD算几个? |
