j**7
发帖数: 143 | 1 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 | 2 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 | 3 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);
} |
|
J***6
发帖数: 3 | 4 来自主题: BrainTeaser版 - 一道数字题 Using each of the numbers 1, 2, 3, 4, 5, 6, 7, 8, 9 only once, form a nine
digit number A that can satisfy the following criteria:
- A is exactly divisible by 9.
- Removing the rightmost digit from A forms an eight digit number B that is
exactly divisible by 8.
- Removing the rightmost digit from B forms a seven digit number C that is
exactly divisible by 7.
- Removing the rightmost digit from C forms a six digit number D that is
exactly divisible by 6.
- Removing the rightmost digit from D form |
|
d****v
发帖数: 458 | 5 我不是大牛，我是小猪，这个是我写的
主要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)
|
|
l*****a
发帖数: 14598 | 6 这样好不好
有一道著名的题 find next node in InOrder Traverse.
Now we can implement it's opposite action.
find previous node in InOrder Traverse.
node * FindNthNode(node * root,int n)
{
if((root==null)||(n<=0)) return null;
find rightmost;
if(n==1) return rightmost;
node * current=rightmost;
for(int i=2;i<=n;i++)
{
current=GetInOrderPreNode(current);
if(current==null) return null;
}
return current;
} |
|
b*****e
发帖数: 474 | 7 不是，就是每层记录下访问到的最右边的节点 （the rightmost node visited).
这样的话，递归的时候遇到同层的新节点时就联上link，再更新 the rightmost node.
所以我这个 array 总共需要 O(depth) space 就可以了。
BFS 的 memory 要求比 DFS 要高好多，所以不建议。 |
|
i******e
发帖数: 273 | 8 关于第一章的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... 阅读全帖 |
|
g**e
发帖数: 6127 | 9 XOR, O(n) time O(1) space. Similar way to find two repating numbers.
final public static void find2missingInt(int[] array) {
int xor = 0;
for(int i=0; i
xor ^= array[i];
//start from 1 to n, watch the upper limit
for (int i=1; i<=array.length+2; i++)
xor ^= i;
/* Get the rightmost set bit in set_bit_no */
... 阅读全帖 |
|
a*****g
发帖数: 19398 | 10 #!/usr/bin/env pike
// legal.pike - Count the number of legal go boards.
// Copyright 2005 by Gunnar Farneb?ck
// [email protected]
/* */
//
// You are free to do whatever you want with this code.
//
//
// This program computes the number of legal go board configurations
// for a rectangular board of a given size. It is efficient enough to
// handle boards up to 8x8 within minutes and up to 11x11 in less than
// 24 hours (on a fast computer). For rectangular boa... 阅读全帖 |
|
a*****g
发帖数: 19398 | 11 【 以下文字转载自 Programming 讨论区 】
发信人: ananpig (●○ 围棋数学一把抓的安安猪), 信区: Programming
标 题: 计算围棋棋盘合法图案的源代码
发信站: BBS 未名空间站 (Fri Jan 22 10:39:02 2016, 美东)
#!/usr/bin/env pike
// legal.pike - Count the number of legal go boards.
// Copyright 2005 by Gunnar Farneb?ck
// [email protected]
/* */
//
// You are free to do whatever you want with this code.
//
//
// This program computes the number of legal go board configurations
// for a rectangular board of a given size. It is ef... 阅读全帖 |
|
f**d
发帖数: 768 | 12 这是一本计算神经科学的优秀著作，全文拷贝这里（图和公式缺），有兴趣的同学可以
阅读
如需要，我可以分享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: ... 阅读全帖 |
|
c**********l
发帖数: 606 | 13 of course not. way too far from it.
even obama is probably close to the rightmost extreme of the spectrum, if
compared with other developped countries, any other developped countries in
europe, asia, or america.
your ignorance (of the rest of the world, just as the rednecks) is not your
fault, stating it out loudly as facts is. |
|
T*U
发帖数: 22634 | 14 http://www.pe.com/local-news/columns/on-the-road-headlines/2011
Q: Riverside's William Anderson disputes an answer given in a prior column
to a reader who asked about right-of-way where traffic is entering a freeway.
California Highway Patrol Lt. Michael Soubirous had answered that neither a
driver on the freeway nor the driver merging onto the freeway has right-of-
way and that both parties have to "work it out" so traffic merges seamlessly
into a single lane.
"According to the California Depar... 阅读全帖 |
|
n*****o
发帖数: 849 | 15 贴一个我LP用过的申诉信，后来申诉成功了，希望有帮助！
To Whom It May Concern,
Violation Number:
Date: mm/dd/year
License Plate:
My vehicle has been issued the above violation on for not
paying the proper toll on . I’m writing to formally challenge
this penalty charge for the following reasons.
Firstly, there was no sign indicating which way would lead me to the CASH
window in the toll station, plus it was dark at night, I did not see any
EZPass sign. As I wa... 阅读全帖 |
|
h*********e
发帖数: 56 | 16 来自主题: JobHunting版 - 一道面试题 should the rightmost one in a level point to NULL, or to the leftmost one in
the next level? |
|
d****v
发帖数: 458 | 17 完全没看我写的啊
不是说了么比较rightMost和leftMost就行，不用找左右最大和最小的
就那个还有牛人说复杂呢 |
|
r****o
发帖数: 1950 | 18 the rightmost node in one level can also be the left child of a node in the
above level. |
|
i**9
发帖数: 351 | 19 一道老题，求最大square 可以用 DP
http://geeksforgeeks.org/?p=6257
Let the given binary matrix be M[R][C]. The idea of the algorithm is to
construct an auxiliary size matrix S[][] in which each entry S[i][j]
represents size of the square sub-matrix with all 1s including M[i][j] and
M[i][j] is the rightmost and bottommost entry in sub-matrix.
1) Construct a sum matrix S[R][C] for the given M[R][C].
a) Copy first row and first columns as it is from M[][] to S[][]
b) For other entries, use foll... 阅读全帖 |
|
a******7
发帖数: 106 | 20 cool man! Thanks! I think you can definitely get an offer.
About the data structure for tetris game, my idea is to use a bitmap to
express each shape, and store 4 rotated shaped in circular double link
list, each time when rotate function is called, it either point to the
left and right elem, which is pre-computed bitmap.
The board is also a bitmap, say M*M, so as long as we have the position
of the shape on board, say the rightmost coordinates (x,y), and the size
of the shape bitmap N*N. For ea... 阅读全帖 |
|
a******7
发帖数: 106 | 21 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 | 22 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********x
发帖数: 914 | 23 // MaxHeap: heapArray starts from index 0
public static void heapSort(int[] a){
// Trickling Down in Place: start at node n/2-1, the rightmost node
with children
// O(n/2*log(n))
for (int i=(a.length/2-1) ; i>=0 ; i--)
trickleDown(a,i, a.length);
// remove max from heap and insert it at the end
// O(n*log(n))
for (int i= a.length - 1; i> 0; i--){
int max = a[0];
a[0] = a[i];
trickleDown(a,0, i... 阅读全帖 |
|
j***y
发帖数: 2074 | 24 Sorry, forgot to mention that the rightmost bit is bit 0. |
|
c*******n
发帖数: 63 | 25 Oh, so we should know the # of bits of N first.
T = N
L = 0
while( (T>>=1) > 0) ++L;
N = ( N ^ ~(1<<(L-5)) ) | (( N >> (L-6)) | M ) << (L-6))
//keep the tailing bits set M
N = 100001000, M = 10101
L = 8 (the rightmost bit is 0th)
first keep the tailing bits:
~(1<<3) = 11
N^11 = 00
set M:
N >> 2 = 1000010
1000010 | M = 1010101
1010101 << 2 = 101010100
101010100 | 00 = 101010100 |
|
s*******y
发帖数: 44 | 26 我一开始也是这个思路，顺序遍历，找到左右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 | 27 我一开始也是这个思路，顺序遍历，找到左右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... 阅读全帖 |
|
E*******0
发帖数: 465 | 28 // 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... 阅读全帖 |
|
o****o
发帖数: 1398 | 29 如果没有准备过，估计很多人面试遇到位运算的题目都会头疼，包括我自己，所以在此
总结一下位运算相关题目吧，从leetcode,careercup还有本版学到的，留个纪念：
1. Toggle 5th-8th bit of a 32bit Integer 这是我自己编的题，不过对于理解XOR操
作有帮助
Ans: a = a ^ 0x000000F0;
2. 交换第i与第j位
这个思路是直接：抠出第i位和第j位，交换之后再置位，可是实现比较麻烦啊，分情况
考虑比较好：
（1）如果第i位和第j位相同，不用换
（2）如果不同，用题1的方法，来个掩码，仅toggle第i位和第j位
Ans:
//Assume i,j start from 0
int exchange(int a, int i, int j) {
if( ((a>>i)&1) != ((a>>j)&1) ) {
a = a ^ ((1<
}
return a;
}
3. Turn off the rightmost 1-bit
Ans: x = x & (x-1)... 阅读全帖 |
|
y****n
发帖数: 192 | 30 用java写了一下，切磋一下哈
main:
// a[0] = （1， 2）-> （7， 9）
// a[1] = （1， 3) -> （4， 5）
// a[2] = （12， 15）
// a[3] = （15， 20）
Interval[] intervals = new Interval[4];
intervals[0] = new Interval(1, 2);
intervals[0].next = new Interval(7, 9);
intervals[1] = new Interval(1, 3);
intervals[1].next = new Interval(4, 5);
intervals[2] = new Interval(12, 15);
intervals[3] = new Interval(15, 20);
Interval result = getUnifiedIntervals(... 阅读全帖 |
|
s********x
发帖数: 914 | 31 那我写一下吧
public static Node mergeKSortedLists(Node[] l) {
// heapify: Make it a heap: Trickling Down in Place: start at node n
/2-1, the rightmost node with children
// O(n)
for (int i = (l.length / 2 - 1); i >= 0; i--)
trickleDown(l, i, l.length);
int heapSize = l.length; // size of the heap
// use an extra dummy node as the head
Node dummy = new Node();
Node pre = dummy;
while (heapSize > 0) {... 阅读全帖 |
|
z****p
发帖数: 18 | 32 Here is the O(log N) solution:
Key observations:
-The solution is "monotonic" in the following sense: if the query "range" is
29.9 and the solution is 100 points, then when the query "range" becomes 30
, the solution is guaranteed to be >= 100.
-We can "pre-compute" the answers to all the possible query "ranges", put
them in a data structure, and look up the data structure when a new query "
range" is asked for.
Solution details: (W.L.O.G., assuming query "range" <= 180 degree)
1. For each PAIR ... 阅读全帖 |
|
l***i
发帖数: 1309 | 33 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*******e
发帖数: 1630 | 34 很有启发，不过对于[0,-1,0]这样的，最大就刚好是0
另外，如果是int[]还好，万一有小数，就又麻烦些了
count
rightmost |
|
p*u
发帖数: 136 | 35 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 |
|
h*******e
发帖数: 1377 | 36 这样的话，看代码的意思， 镂空的内沿就不算了，题目主要让计算左边，右边 加上叶
子节点 。楼主leftmost rightmost两个 状态参数用得好，这样就inplace 一次遍历成
功结果也不用在外面存了。谢谢楼主。 |
|
f******s
发帖数: 659 | 37 //no recursion, no string manipulation
//space O(1), time O(n)
boolean isPalindrome(int num){
if(num<0) return false;
int rev = 0; //reverse num
int num0 = num; //original value
while (num>0){
rev = rev * 10 + num % 10; //get the rightmost digit of num
num /= 10;
}
return rev==num0;
} |
|
l*****a
发帖数: 14598 | 38 1) sorted array, find rightmost occurrence index for target number
how to modify to find leftmost ......
2) remove duplicate characters in given string,keep the first one |
|
p*******8
发帖数: 158 | 39 It's absolute normal since you select consulates in China at the beginning
of online DS160. If you want English version, there is language selection
on the rightmost top of webpage and choose English..
You and your wife could be co-inviter, no preference. |
|
m*******i
发帖数: 8711 | 40 the rightmost lane is for you.
Wait, you don't even drive on 101. |
|
i*********5
发帖数: 19210 | 41 这篇文章写于去年，一位妈妈在去幼儿园接孩子的路上被一辆右转的卡车压死了（她自
己也在那里右转）。
YOU OWN YOUR SPACE: Tips from a former bike courier on staying alive as a
Toronto cyclist
On this particular afternoon, it’s really easy to vicariously relate
ourselves (or our loved ones) to the woman who was crushed to death on
Dundas West and Sterling earlier today. It’s easy to think, “Wow, that
could have been me instead of her.”
Well, it wasn’t you, and be glad for that. Dwelling on the “could have
beens” is of no help to the victim, her fam... 阅读全帖 |
|
s****y
发帖数: 267 | 42 The rightmost has a huge fake boom. |
|
x******2
发帖数: 4034 | 43 Illegal formation:
Fewer than 7 players line up on the line of scrimmage (NFL/High School);
more than four players in the backfield (NCAA only); eligible receivers fail
to line up as the leftmost and rightmost players on the line in the NFL; or
when five properly numbered ineligible players fail to line up on the line. |
|
u*********r
发帖数: 2735 | 44 u rightmost 25
Rw3 leftmost
left 2nd pet |
|
|
N*C
发帖数: 1987 | 46 Lenovohas Lenovo Z40 Laptop on sale, choose and add model 59425582 (
rightmost) (Intel core i7-4510U, 8GB DDR3, 500GB HDD, 14" 1920x1080, 2GB
NVIDIA GeForce GT820M, DVD Dual Layer Recordable) for $649 - $30 off eCoupon
code "D2BZ40" =$619. Shipping is free. |
|
r***u
发帖数: 241 | 47 You can just ignore the rightmost column, OK? |
|
d********t
发帖数: 9628 | 48
Go to the rightmost on your upper panel. |
|
a**u
发帖数: 5 | 49 i suggest use split and get the rightmost element |
|
S**I
发帖数: 15689 | 50 do you notice the tiny vertical bar at rightmost of the task bar? try that.
of |
|
