w******j
发帖数: 185 | 1 来个java的吧，带parent pointer和不带的，preorder和inorder的
import java.util.NoSuchElementException;
import java.util.Stack;
public class BST {
private Node root;
private static class Node {
int key;
Node left, right, parent;
Node(int key) {
this.key = key;
}
}
public BST(){
}
public BSTIterator inorderIterator() {
return new InorderIterator();
}
public BSTIterator preorderIterator() {
return new PreorderI... 阅读全帖 |
|
w******j
发帖数: 185 | 2 来个java的吧，带parent pointer和不带的，preorder和inorder的
import java.util.NoSuchElementException;
import java.util.Stack;
public class BST {
private Node root;
private static class Node {
int key;
Node left, right, parent;
Node(int key) {
this.key = key;
}
}
public BST(){
}
public BSTIterator inorderIterator() {
return new InorderIterator();
}
public BSTIterator preorderIterator() {
return new PreorderI... 阅读全帖 |
|
j**7
发帖数: 143 | 3 5.多层链表压扁及还原
// 没有测试过。
public static Node flatten(Node head, Node tail) {
Node start = head;
while (head != tail.next) {
Node next = head.next;
if (head.down != null) {
Node leftMost = leftMost(head.down);
Node rightMost = rightMost(head.down);
head.down.up = null;
head.down = null;
head.next = leftMost;
leftMost.prev = head;
rightMost.next = next... 阅读全帖 |
|
i*********7
发帖数: 348 | 4 int* findmaxsumarray(int *array, int length, int maxsum){
int *sum = new int[length + 1];
sum[0] = 0;
for(int i = 1; i <= length; i++)
sum[i] = sum[i - 1] + array[i - 1];
int *max = new int[length + 1];
int *min = new int[length + 1];
for(int i = 0;i<=length;i++)
cout<
cout<
max[0] = 0;
for(int i = 1; i < length + 1;i++)
{
max[i] = std::max(max[i - 1], sum[i]);
}
min[length] = sum[length];
for(int i = ... 阅读全帖 |
|
l*********8
发帖数: 4642 | 5 left_most, right_most这个思路不错，学习了。
还可以简化一下：
void traverse(TreeNode * root, bool leftMost = true, bool rightMost = true) {
if (!root) return;
if (leftMost || (!rightMost && !root->left && !root->right))
print(root);
traverse(root->left, leftMost, false);
tarverse(root->right, false, rightMost);
if (rightMost && !leftMost)
print(root);
} |
|
d****v
发帖数: 458 | 6 我不是大牛，我是小猪，这个是我写的
主要idea是rightMost不一定是左边的最大值，leftMost不一定是右边的最小值
但是没关系，root和他比就行了。
bool isBST(Node n)
{
if(n == null)
return true;
return isBST(n.left) && (n.left==null || n.value>rightMost(n.left))
&&
isBST(n.right) && (n.right==null || n.value
}
int/double rightMost(Node n)
{
if(n==null)
throw exception;
if(n.right==null)
return n.value;
return leftMax(n.right);
}
int/double leftMost(Node n)
{
if(n==null)
|
|
I**A
发帖数: 2345 | 7 这个我大致看过
int minValue(struct node* node) {
struct node* current = node;
/* loop down to find the leftmost leaf */
while (current->left != NULL) {
current = current->left;
}
return(current->data);
}
int maxValue(struct node* node) {
struct node* current = node;
/* loop down to find the leftmost leaf */
while (current->right != NULL) {
current = current->left;
}
return(current->data);
}
这俩function，肯定有一个有问题。。。
再说了，这样求max and min也不make sense，因为只要在保证left or right是BST的
情况下才能 |
|
i**********e
发帖数: 1145 | 8 You said use minHeap, that's fine :)
But how to age out the oldest one? You have to search for the heap right?
The key to answering this problem is remove the leftmost element as
efficient as possible.
Hint: Hash table
Deng107:
You're doing a linear search in the heap. The worst case would happen such that your cache won't help at all. So you need O(w) to remove the leftmost element in each pass.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i**********e
发帖数: 1145 | 9 The minHeap maintain the order when an element is being inserted. The insert
operation takes O(lg N) time complexity.
>> Hash table can help remove the leftmost element ...
Could you explain how? Many people know that the minHeap is the right data structure, but how hash table helps to accomplish removing the leftmost element in O(1) time is the heart of this problem.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
i******e
发帖数: 273 | 10 关于第一章的N*N矩阵向右旋转90度的题。 怎么也得不到想要的结果，我按照答案修改
了我的程序，可是还是不对。
我得到的结果是：
Original matrix:
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59
60 61 62 63 64 65 66 67 68 69
70 71 72 73 74 75 76 77 78 79
80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99
After rotation:
99 81 72 63 54 45 36 27 18 0
91 88 72 63 54 45 36 27 11 1
92 82 77 63 54 45 36 22 12 2
93 83 73 66 5... 阅读全帖 |
|
|
d*******u
发帖数: 186 | 12 Question one:
Tree::_InOrderIterator::operator++()
{
TreeNode* node = this->Node->right();
stack itstack;
//leftmost of right child.
while(node != NULL)
{
itstack.Push(node);
node = node->left();
}
leftmost of right child.
node = itstack.Pop();
if (node == NULL)
{
node = end; //reserved end n... 阅读全帖 |
|
d*******u
发帖数: 186 | 13 Question one:
Tree::_InOrderIterator::operator++()
{
TreeNode* node = this->Node->right();
stack itstack;
//leftmost of right child.
while(node != NULL)
{
itstack.Push(node);
node = node->left();
}
leftmost of right child.
node = itstack.Pop();
if (node == NULL)
{
node = end; //reserved end n... 阅读全帖 |
|
d*******u
发帖数: 186 | 14 Question one:
Tree::_InOrderIterator::operator++()
{
TreeNode* node = this->Node->right();
stack itstack;
//leftmost of right child.
while(node != NULL)
{
itstack.Push(node);
node = node->left();
}
leftmost of right child.
node = itstack.Pop();
if (node == NULL)
{
node = end; //reserved end n... 阅读全帖 |
|
d*******u
发帖数: 186 | 15 Question one:
Tree::_InOrderIterator::operator++()
{
TreeNode* node = this->Node->right();
stack itstack;
//leftmost of right child.
while(node != NULL)
{
itstack.Push(node);
node = node->left();
}
leftmost of right child.
node = itstack.Pop();
if (node == NULL)
{
node = end; //reserved end n... 阅读全帖 |
|
z****p
发帖数: 18 | 16
Sorry about the handwaving. My thought was that in order for the recursive
function to work, the list should be very long. That is, in C = 9/10*1 + 1/
10*(1+C), we put the same C on both sides, which implies that C is
independent of the length of the list. This is of course not true, but only
an approximation.
The boundary case, which behaves different from the general cases, is when
the leftmost digit is 9 and when we need to extend the list length by 1. But
the time complexity for extending t... 阅读全帖 |
|
c***u
发帖数: 4107 | 17 Implement an iterator over a binary search tree (BST). Your iterator will be
initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() should run in average O(1) time and uses O(h)
memory, where h is the height of the tree.
高人的程序是:
public class BSTIteratorInorder {
private Stack stack = new Stack<>();
public BSTIteratorInorder(TreeNode root) {
pushLeftChildren(root); // find the first node (le... 阅读全帖 |
|
h*********d
发帖数: 1054 | 18 来自主题: Programming版 - 问题请教 4. traverse a binary tree in a left-first order, that is, start from the
root, traverse the leftmost path, then start from the root again, and
traverse the second leftmost path, and so on.
在jobhunting版发现了这个问题，不明白这个遍历。不知道是要遍历所有从根开始的路
径并打印出整个路径，还是仅仅打印以前没有打印过的节点。
多谢了 |
|
p*****e
发帖数: 5165 | 19 let me do it 笨笨的ly
suppose we divide one edge into n shares,
consider vertical line on leftmost:
the chance they meet is (n/2) : n *(n/2+1) = 1/(n+2)
leftmost 2nd: 2/ (n+2)
....
middle: (n/2) / (n+2)
so average: 2* sigma (1 to n/2)(i /(n+2)) / n =
(n/2)(n/2+1)/(n*(n+2))
n->... above -> 1/4?
看起来不象四分之一的，经过偶的计算，居然就是四分之
一。但是由于偶之计算，十中之对，难有其一，所以还
是不象四分之一。 |
|
f**d
发帖数: 768 | 20 这是一本计算神经科学的优秀著作，全文拷贝这里（图和公式缺），有兴趣的同学可以
阅读
如需要，我可以分享PDF文件（－－仅供个人学习，无商业用途）
From Computer to Brain
William W. Lytton
From Computer to Brain
Foundations of Computational Neuroscience
Springer
William W. Lytton, M.D.
Associate Professor, State University of New York, Downstato, Brooklyn, NY
Visiting Associate Professor, University of Wisconsin, Madison
Visiting Associate Professor, Polytechnic University, Brooklyn, NY
Staff Neurologist., Kings County Hospital, Brooklyn, NY
In From Computer to Brain: ... 阅读全帖 |
|
V****n
发帖数: 651 | 21 Norg Haven 19catsandcounting • 2 days ago
I have looked into a number of historical texts.
I've also read "Eugenics: A Reassessment", "The Bell Curve: Intelligence and
Class Structure in American Life", "Dysgenics: Genetic Deterioration in
Modern Populations", "The 10,000 Year Explosion: How Civilization
Accelerated Human Evolution", and "The Global Bell Curve: Race, IQ, and
Inequality Worldwide".
Thanks to racial integration, Black America currently resides within a
nation that was princ... 阅读全帖 |
|
发帖数: 1 | 22 这是2017年的旧闻
By Dylan Matthews on September 12, 2017 5:00 pm
希拉里·克林顿（Hillary Clinton）在竞选回忆录《发生了什么》（What Happened）
中最令人震惊的一段话中，揭示了她与员工共同制定但从未实际发布的竞选建议：由碳
和金融交易税资助的美国人的普遍基本收入。
她在接受Vox的埃兹拉·克莱因（Ezra Klein）采访时说：“我非常想传达一个承诺，
试图找出增加收入的方法。” “阿拉斯加模型每年都会根据有关石油和天然气收入的
公式向每一个阿拉斯加人写一张支票，这对我来说真的很有趣。”
这是本书的相关段落，第239页：
在竞选总统之前，我读过一本书，作者是彼得·巴恩斯（Peter Barnes）着的《为所有
人带来自由和红利：如何在工作不足时挽救我们的中产阶级》一书，探讨了创建一个新
基金的想法，该基金将利用共享国家资源以向每个公民派发红利，就像阿拉斯加常设基
金每年如何分配该州的石油使用费一样。共享的国家资源包括从公共土地中提取的石油
和天然气以及广播公司和移动电话公司使用的公共无线电波，但这只能使您走得... 阅读全帖 |
|
c****e
发帖数: 2097 | 23 on a interstate, and in NY, I thought no one would really care, as long as u
r driving fast.
in NJ and PA, I used to be more cautious. there're 2 lane high ways, and you
don't want to block people.
if there are 3-4 lanes, wtf.
as a courtesy though, I usually move out of the leftmost lane for a faster
driver to pass, when I can do it comfortably. |
|
f*******i
发帖数: 8492 | 24 In North American terminology, the passing lane is often known as a left
lane or leftmost lane, due to left hand drive (driving on the right). In
British/Irish terminology, the passing lane is termed an outer lane or
outside lane, while a normal lane nearer the hard shoulder is termed an
inner lane (or inside lane).
http://en.wikipedia.org/wiki/Passing_lane
英国是右舵车，在北美，都是左舵车，所以我觉得左边是里道吧
不对的地方，请指正 |
|
b****n
发帖数: 3343 | 25 图方便直接转到左边倒数第二条lane is ok as long as there is only one left
turn lane.
If I were in the leftmost lane of two left turn lanes, I would 左转到最左边
的lane per 交规 guidelines. |
|
t**********1
发帖数: 7316 | 26 ☆─────────────────────────────────────☆
icbchsbc (爱存不存,还是不存) 于 (Fri Jun 17 14:36:38 2011, 美东) 提到:
本人现在驾驶2003 accord coupe v6, 昨日在2线路上的左线直线以30mph速度行使, 被
右面一辆正在超车的2010 highlander突然撞击. 当时路面限速40.
爱车损伤了整个右侧, 撞击部分是右前方轮胎附近, 由于被撞后仍在直线行使中, 整个
右侧有一道很大的划痕. 右侧镜被折回, 没碎. 车门削掉了highlander的一层铁皮(仍
夹在车门前侧), 右侧车门现在还无法打开. 车没有失控.
highlander的前bumper被撞掉, 左前方轮胎前的部位车皮被挂掉, 暴露机械部位.
看了眼受伤的爱车, 固然酸楚, 再看看对方的惨状, 心里一股暖流 -- 爱车争气了!
☆─────────────────────────────────────☆
FDTD (忆江南) 于 (Fri Jun 17 14:50:44 2011, 美东) 提到... 阅读全帖 |
|
h*********e
发帖数: 56 | 27 来自主题: JobHunting版 - 一道面试题 should the rightmost one in a level point to NULL, or to the leftmost one in
the next level? |
|
b****j
发帖数: 78 | 28 来自主题: JobHunting版 - 一道面试题 NULL, if it were the leftmost one in the next level, the code could be furth
er simplified.
in |
|
d****v
发帖数: 458 | 29 完全没看我写的啊
不是说了么比较rightMost和leftMost就行，不用找左右最大和最小的
就那个还有牛人说复杂呢 |
|
l******c
发帖数: 2555 | 30 copy & paste from web site, anybody can explain?
Algorithm:
step 1:
add next character to string
Optimize string
if we have a substring
Record substring if its the best so far
step 2:
remove leftmost character from string
If we still have a substring
Optimize substring
Record substring if its the best so far
goto step 2
goto step 1 |
|
k****n
发帖数: 369 | 31 I have following observations:
the longest subsequence must be one of following cases:
1) the whole sequence
2) starts from one end and ends at some middle point
3) starts from mid point A and ends at mid point B
1) is trivial
2) is also easy, in O(n) time can do
so what we need to do is find the longest subsequence for case 3)
suppose the longest subsequence is
b_i, b_i+1, ..., b_j-1, b_j
where 1
one immediate conclusion is b_i-1 and b_j+1 cannot b... 阅读全帖 |
|
d******a
发帖数: 238 | 32 reverse a int number given a int number
how do you determine overflow(see the leftmost bit or compare with INT_MAX)?
if overflowed, what should we do? just give the error message?
. Given two sorted integer array, how to find the intersection.
what is best comparision number and worst comparison number.
best: length of the shorter array ?
worst: O(m + n) ? |
|
k*****a
发帖数: 188 | 33 Hash table can help remove the leftmost element, but how to make sure the
heap is sorted? |
|
k*****a
发帖数: 188 | 34 Maintain a hash table so that given the value of leftmost element, you can
know the position in minHeap |
|
a******7
发帖数: 106 | 35 I think we only need check the bits on the boundary, which means the
leftmost, rightmost column and bottom row, normally these won't be large
than 32bits or 64bits. |
|
y******5
发帖数: 43 | 36 I mean, we need to find a way to construct histogram, and we can start from
min of leftmost and rightmost. Suppose current value a[i] is no less than
next value (a[i-1] or a[i+1]), then overwrite the next value with a[i]. At
the end, you will have n-1 histograms. |
|
s*******y
发帖数: 44 | 37 我一开始也是这个思路，顺序遍历，找到左右overlap的interval，然后删除、插入。
查找过程可以用binary search优化到logn。
vector insert(vector &intervals, Interval
newInterval) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size = intervals.size();
if (size == 0) {
intervals.push_back(newInterval);
return intervals;
}
int i=0, pos;
while (i < size && intervals[i].end < newInterval.start) i++; //
lef... 阅读全帖 |
|
s*******y
发帖数: 44 | 38 我一开始也是这个思路，顺序遍历，找到左右overlap的interval，然后删除、插入。
查找过程可以用binary search优化到logn。
vector insert(vector &intervals, Interval
newInterval) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size = intervals.size();
if (size == 0) {
intervals.push_back(newInterval);
return intervals;
}
int i=0, pos;
while (i < size && intervals[i].end < newInterval.start) i++; //
lef... 阅读全帖 |
|
w****x
发帖数: 2483 | 39 "写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。"
有parent就可以做, 往上爬的时候看是左节点还是右节点, 左节点就打印, 在往下爬到
右子树的leftmost, 是右节点的话就再往上爬 |
|
w****x
发帖数: 2483 | 40 "写二叉树的结构体，要求装载的数据可以是任意类型。然后写出
preorder遍历的递归版本，非递归版本，非递归并且空间是O(1)的版本。"
有parent就可以做, 往上爬的时候看是左节点还是右节点, 左节点就打印, 在往下爬到
右子树的leftmost, 是右节点的话就再往上爬 |
|
i*********7
发帖数: 348 | 41 不需要stack。
其实树的遍历可以不需要递归和stack。
第一个元素是树的leftmost节点，然后hasnext就是另一个经典题：中序遍历的
successor，这样遍历是不需要stack的。 |
|
l*****a
发帖数: 14598 | 42 你搞了些flag看着不舒服
i will goto leftmost, then each time call FindInOrderNext() |
|
E*******0
发帖数: 465 | 43 // NextPermutation.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include
#include
using namespace std;
#include
bool myfunction (int i,int j) { return (i>j); }
bool nextPermutation(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
//If vector size is 1, permutation is its self.
if (1==num.size())
return true;
// rit is the iterator indicates current ite... 阅读全帖 |
|
y****g
发帖数: 5 | 44 Isn't the answer leftmost node of target node's right child tree?? |
|
l*****a
发帖数: 14598 | 45 有一道著名的面世题不知到你做没做过
给BT中一node,找inOrderTraverse的next
然后就用这个结果从leftmost开始就成了 |
|
l***i
发帖数: 1309 | 46 max production subarray
1. we can see the array as subarrays delimited by 0, and each of those
subarrays can be processed indepdent of each other.
2. For each subarray without 0, if the count of negative elements is even,
then the value of this subarray is the product of all elements. If the count
of negative elements is odd, then we need to throw away one negative
element, this one is either the leftmost negative element, or the rightmost
negative element.
input: int A[], int N;
// assume empty... 阅读全帖 |
|
s**x
发帖数: 7506 | 47 found this
http://www.dsalgo.com/2013/03/longest-subarray-with-equal-numbe
Longest subarray with equal number of ones and zeros
Problem
You are given an array of 1's and 0's only. Find the longest subarray which
contains equal number of 1's and 0's.
Solution
We will keep a running sum of "no of ones minus no of zeros" for each index
of the array. For any two indices, if the running sum is equal, that means
there are equal number of ones and zeros between these two indices. We will
store the runn... 阅读全帖 |
|
l*n
发帖数: 529 | 48 if (node has right child) {
find its leftmost grandchild
} else {
find the minimum grandancestor that's greater than node from root
} |
|
S*******C
发帖数: 822 | 49 Input: WORD.LST
And a randomly picked 1000 words from the same WORD.LST for querying.
This is a list of > 100,000 English words. It is sorted alphabetically.
Your task is to create a Compact Trie. Each node of trie will contain,
(1) A leading character (possibly empty (for root))
(2) String Label (possibly null (for root))
(3) Boolean IsWord , indicating whether the current node represents a whole
word or not (this is helpful when one word may be a prefix of another).
(4) Node *RightSIbling
(5)... 阅读全帖 |
|
p*u
发帖数: 136 | 50 sliding window那个题，rocket fuel的烙印不让用STL，非要手写heap，还要求删除任
意元素的复杂度也是O(logn)
一般不都是鼓励用库的么！g家onsite有个稍麻烦点但是最后也用heap的题，用STL面试
官就很满意啊。。。
更新下题目：
You are given an array of size n. There is a sliding window of size k(
Return an array containing max element in each window position(from leftmost
window position to rightmost).
Eg.
input: A=4,7,3,6,8,2,4,3,2,5,4 k=4
output:B=7,8,8,8,8,4,5,5 |
|
