maillist.danielyin
BAN USERDo not need to check if left child or right child is null. Already included in the base case
- maillist.danielyin October 22, 2013Here I`ll post a non-recursive way.
int height(TreeNode * root){
if (!root) return 0;
stack<TreeNode *> s;
TreeNode * current = root;
int maxHeight = 0;
while(true){
if (current){
s.push(current);
current = (current->left != NULL)?current->left:current->right;
}
else{
maxHeight = s.size()>maxHeight?s.size():maxHeight;
current = s.top();
s.pop();
if (s.empty()) break;
if (current == s.top()->left){
current = s.top()->right;
}
else{
current = NULL;
}
}
}
return maxHeight;
}
Just to clarify, is it allowed to change the data structure? Or just implement like iterator to flattenly access to the elements?
- maillist.danielyin October 22, 2013Besides, this is used to generating numbers, thus I think we need to modify the tree to store the number of leaf nodes a certain node has. This will avoid unnecessary search following branches which are already of full leaf nodes.
- maillist.danielyin October 08, 2013I don`t think it is necessary to store all phone numbers except a new number is generated.
- maillist.danielyin October 08, 2013Be careful of the loops baby. You are copying nodes repeatedly.
- maillist.danielyin October 06, 2013I totally did not get what your code is doing. pOld->random is supposed to be a node in the linkedlist, whose next is another node right behind it. I did not see you modify the next pointer. Besides, you cannot trace the nodes by random pointer, what if some nodes` random pointers are NULL?
- maillist.danielyin October 06, 2013@vstudio Agree! Can work it out based on quick select method on a single array.
- maillist.danielyin October 06, 2013@EOF array has its own capacity, which means you cannot simply combine their elements. The problem specified no extra arrays.
- maillist.danielyin October 06, 2013#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <map>
#include <string.h>
//method one:use map, since no hashmap, we can use stl c++ map implemented by rb tree.
typedef std::map<int,bool> Map;
int removeDup(int * a, int length){
if (!a ||length <=1) return length;
std::cout<<"Not null"<<std::endl;
Map m;
Map::iterator it;
int index = 0;
for (int i = 0;i<length;i++){
it = m.find(a[i]);
if (it == m.end()){
m[a[i]]=true;
//std::cout<<"Not dup "<<
if (index != i){
a[index] = a[i];
}
index++;
}
}
std::cout<<index<<std::endl;
return index;
}
Note:c++ has no hashmap, so here I use the stl map which is implemented by RB tree. If the number of elements are not quite large, look up and insertion can be considered as constant. However, one can implement his own hashmap to do this. The time complexity is O(n).
Awesome. Really want to know how you come up with such a fancy idea.
- maillist.danielyin October 05, 2013#include <stdlib.h>
#include <stdio.h>
#include <iostream>
void printHelper(int i, int range){
if (i>range) return;
if (i != 0){
std::cout<<i<<std::endl;
}
int next = i*10;
if (next <=range){
for (int k = 0;k<=9 & (next+k<=range);k++){
printHelper(next+k,range);
}
}
}
void printNumber(int N){
for (int i = 1;i<10;i++){
printHelper(i,N);
}
}
int main(){
int N;
std::cin>>N;
printNumber(N);
}
~
Well time complexity is not O(n) if you search in cum_sum. Let`s say you wanna find element which equals to cum_sum[0], you need to iterate through the array which is O(n), if not found, again you have to pick up cum_sum[1] and do it again. The time complexity is O(n2). To solve this, we need a hashmap of which key is the sum and value is subarray indices.
- maillist.danielyin October 02, 2013@Cerberuz. The Sieve of erasthotenes works from 2 to the limit instead of a certain range. It is not possible to calculate the primes between start and end without referring to primes between 2 and start.
- maillist.danielyin September 30, 2013a 6k
b 6k+1
c 6k+2
d 6k+3
e 6k+4
f 6k+5 = 6k-1
6k = 2*3k cannot be prime
6k+1 possible prime
6k+2 = 2(3k+1) cannot be prime
6k+3 = 3(2k+1) cannot be prime
6k+4 = 2(3k+2) cannot be prime
6k-1 possible prime
The same theory to 3k+1, 3k+2, but it gives you a larger step and we can ignore more numbers
Well it`s not about inserting the second half into the first half, we are merging them to a new head pointer, which is easier than inserting into the first half.
- maillist.danielyin September 28, 2013Check if the list is null or it is sorted, if yes, return.
Otherwise, have a pointer starting from the beginning, iterate until find the beginning of the second half, call it p2. Have p1 pointing at the beginning of the array, merge them to a new linkedlist by manipulating the pointers.
So based on the example you give, they are not exactly first half and second half. Should be the first part and second part.
- maillist.danielyin September 27, 2013
hi simply compare the string is not working.
- maillist.danielyin October 26, 2013For example for 94,9 and 4, in the result 9 comes before 94 and 4 comes after 94, while they are both smaller than 94 if you treat them as strings.