oscarsanchez1937
BAN USERThis is an Objective-C solution, the idea is get leaves from each tree and then compare each other in order to get non-matching leaves, I came with this solution considering the case when tree1 has 2 levels and tree 2 has 4 levels
-(NSMutableArray *)getNotMatchingLeaves:(TreeNode *)root1 and:(TreeNode *)root2{
if(root1 == nil && root2 == nil){
return nil;
}
NSMutableArray *stack1 = [NSMutableArray new];
NSMutableArray *stack2 = [NSMutableArray new];
[stack1 addObject:root1];
[stack2 addObject:root2];
NSMutableArray *leaves1 = [NSMutableArray new];
NSMutableArray *leaves2 = [NSMutableArray new];
while([stack1 count] > 0 || [stack2 count] > 0){
if([stack1 count] > 0){
root1 = [stack1 objectAtIndex:0];
[stack1 removeObjectAtIndex:0];
if(root1.left == nil && root1.rigth == nil){
[leaves1 addObject:[NSNumber numberWithInt:root1.value]];
}
if(root1.left != nil){
[stack1 addObject: root1.left];
}
if(root1.rigth != nil){
[stack1 addObject: root1.rigth];
}
}
if([stack2 count] > 0){
root2 = [stack2 objectAtIndex:0];
[stack2 removeObjectAtIndex:0];
if(root2.left == nil && root2.rigth == nil){
[leaves2 addObject:[NSNumber numberWithInt:root2.value]];
}
if(root2.left != nil){
[stack2 addObject: root2.left];
}
if(root2.rigth != nil){
[stack2 addObject: root2.rigth];
}
}
}
leaves1 = [leaves1 sortedArrayUsingSelector:@selector(compare:)];
leaves2 = [leaves2 sortedArrayUsingSelector:@selector(compare:)];
NSMutableArray *result = [self getUniqueItemsFromArray:leaves1 andArray:leaves2];
return result;
}
-(NSMutableArray *)getUniqueItemsFromArray:(NSMutableArray *)array1 andArray:(NSMutableArray *)array2{
int i = 0;
int j = 0;
NSMutableArray *result = [NSMutableArray new];
while(i < [array1 count] && j < [array2 count]){
if([array1[i] intValue] > [array2[j] intValue]){
[result addObject:[NSNumber numberWithInt:[array2[j] intValue]]];
j++;
}
else if([array1[i] intValue] < [array2[j] intValue]){
[result addObject:[NSNumber numberWithInt:[array1[i] intValue]]];
i++;
}
else{
i++;
j++;
}
}
while(i < [array1 count]){
[result addObject:[NSNumber numberWithInt:[array1[i] intValue]]];
}
while(j < [array2 count]){
[result addObject:[NSNumber numberWithInt:[array2[j] intValue]]];
}
return result;
}
This is an Objective-C solution in O(log n) time and O(i) space
-(NSString *)reverseWords:(NSString *)value{
NSString *result;
NSMutableArray *tempArray = [NSMutableArray arrayWithArray:[value componentsSeparatedByString:@" "]];
for(int i = 0; i < [tempArray count] / 2; i++){
[tempArray exchangeObjectAtIndex:((int)[tempArray count] - i - 1) withObjectAtIndex:i];
}
result = [[tempArray valueForKey:@"description"] componentsJoinedByString:@" "];
return result;
}
This is an Objective-C solution, time O(n)
-(void)getPivotFrom:(NSMutableArray *)array{
if ([array count] == 0) {
NSLog(@"No Pivot found");
}
int totalSum = 0;
for(int i = 0; i < [array count]; i++){
totalSum += [array[i] intValue];
}
int leftSum = 0;
int rightSum = totalSum - [array[0] intValue];
if(leftSum == rightSum){
NSLog(@"Pivot found at index 0");
return;
}
for(int i = 1; i < [array count]; i++){
leftSum += [array[i - 1] intValue];
rightSum -= [array[i] intValue];
if(leftSum == rightSum){
NSLog(@"Pivot found at index: %i", i);
return;
}
}
NSLog(@"No Pivot found");
}
This is an Objective-C solution
-(NSMutableArray *)getMinValueOfSubstringsInArray:(NSMutableArray *)array withSize:(int)k{
if([array count] == 0 || k <= 0){
return nil;
}
NSMutableArray *temp = [NSMutableArray new];
NSMutableArray *result = [NSMutableArray new];
int min = 0;
for(int i = 0; i < [array count]; i++){
if([temp count] >= k){
min = [[[temp sortedArrayUsingSelector:@selector(compare:)] firstObject] intValue];
[result addObject:[NSNumber numberWithInt:min]];
}
if(i >= k){
[temp removeObject:array[i-k]];
}
[temp addObject:array[i]];
}
if([temp count] >= k){
min = [[[temp sortedArrayUsingSelector:@selector(compare:)] firstObject] intValue];
[result addObject:[NSNumber numberWithInt:min]];
}
return result;
}
This is an Objective-C solution
-(void)getSubArray:(NSMutableArray *)array withSum:(int)sum{
int tempSum = [array[0] intValue];
int i;
int start = 0;
for(i = 1; i < [array count]; i++){
while(tempSum > sum && start < i + 1){
tempSum -= [array[start] intValue];
start++;
}
if(tempSum == sum){
NSLog(@"FOUND SUM FROM INDEX %i TO %i", start, i - 1);
return;
}
if(i < [array count]){
tempSum += [array[i] intValue];
}
}
NSLog(@"NOT FOUND");
}
This is an Objective-C solution using recursion
-(TreeNode *)getLowestCommonAncestor:(TreeNode *)root andNode1:(TreeNode *)n1 andNode2:(TreeNode *)n2{
if(root == nil){
return nil;
}
if(root == n1 || root == n2){
return root;
}
TreeNode *leftNode = [self getLowestCommonAncestor:root.left andNode1:n1 andNode2:n2];
TreeNode *rigthNode = [self getLowestCommonAncestor:root.rigth andNode1:n1 andNode2:n2];
if(leftNode != nil && rigthNode != nil){
return root;
}
else if(leftNode == nil && rigthNode == nil){
return nil;
}
return leftNode != nil ? leftNode : rigthNode;
}
This is an Objective-C solution O(n) time and O(n) extra space using a queue and stack and traverse the tree by level.
-(void)getLevelOrderTraversalReverse:(TreeNode *)root{
if(root == nil){
return;
}
NSMutableArray *queue = [NSMutableArray new];
NSMutableArray *stack = [NSMutableArray new];
NSMutableString *result = [[NSMutableString alloc] init];
[queue addObject:root];
while ([queue count] > 0) {
root = [queue objectAtIndex:0];
[queue removeObjectAtIndex:0];
if(root.rigth != nil){
root.rigth.level = root.level + 1;
[queue addObject:root.rigth];
}
if(root.left != nil){
root.left.level = root.level + 1;
[queue addObject:root.left];
}
[stack addObject:root];
}
while([stack count] > 0){
root = [stack lastObject];
[stack removeLastObject];
[result appendString:[NSString stringWithFormat:@"%i ", root.value]];
}
NSLog(@"\n\nBy Level Reverse: %@\n", result);
}
This is an Objective-C solution using recursion
-(void)getAllPathsFromRoot:(TreeNode *)root andResult:(NSMutableArray *)result andTemp:(NSMutableArray *)temp{
if(root == nil){
return;
}
[temp addObject:[NSNumber numberWithInt:root.value]];
if(root.left == nil && root.rigth == nil){
[result addObjectsFromArray:temp];
[result addObject:@"|"];
}
else{
if(root.left != nil){
[self getAllPathsFromRoot:root.left andResult:result andTemp:temp];
}
if(root.rigth != nil){
[self getAllPathsFromRoot:root.rigth andResult:result andTemp:temp];
}
}
[temp removeLastObject];
}
This is an Objective-C solution in O(n) time and O(1) space, since the integers in the array are not greater than the size of the array we can use them as an index of the same array and mark each number in index as negative and then if we found that X number is already negative that is a duplicate number
-(void)findDuplicatesInArray:(NSMutableArray *)array{
for(int i = 0; i < [array count]; i++){
int temp = abs([array[i] intValue]);
if([array[temp] intValue] >= 0){
array[temp] = [NSNumber numberWithInt:-abs([array[temp] intValue])];
}
else{
NSLog(@"%i", abs([array[i] intValue]));
}
}
}
This is an Objective-C solution in O(n), the key is sort all intervals first and merge those who overlap each other
-(int)getTotalTimeFromIntervals:(NSMutableArray *)array{
NSMutableArray *result = [NSMutableArray new];
// FIRST SORT ALL INTERVALS
array = [array sortedArrayUsingComparator:^(id a, id b){
return [[a objectAtIndex:0] compare:[b objectAtIndex:0]];
}];
NSMutableArray *temp = array[0];
NSMutableArray *current;
// TRAVERSE ALL INTERVALS TO MERGE IN CASE SOME OF THEM OVERLAP
for(int i = 0; i < [array count]; i++){
current = array[i];
if([current[0] intValue] > [temp[1] intValue]){
[result addObject:temp];
temp = current;
}
else{
NSMutableArray *merged = [[NSMutableArray alloc] initWithObjects:
[NSNumber numberWithInt:[temp[0] intValue]],
[NSNumber numberWithInt:fmax([temp[1] intValue], [current[1] intValue])], nil];
temp = merged;
}
}
[result addObject:temp];
// SUM OUR FINAL INTERVALS
int total = 0;
for(int i = 0; i < [result count]; i++){
total += [result[i][1] intValue] - [result[i][0] intValue];
}
return total;
}
This is an Objective-C solution using recursion
-(int)getTreeHeigth:(TreeNode *)root{
if(root == nil){
return 0;
}
return fmax([self getTreeHeigth:root.left] + [self getTreeHeigth:root.rigth]) + 1;
}
This is an Objective-C solution, basically, iterate by level using a queue and store in a dictionary the level of the X and Y value found and then check if those are in the same level
@interface TreeNode : NSObject
@property (nonatomic, assign) int value;
@property (nonatomic, strong) TreeNode *left;
@property (nonatomic, strong) TreeNode *rigth;
@property (nonatomic, assign) int level;
-(instancetype)initWithValue:(int)value;
@end
-(BOOL)find:(TreeNode *)root andX:(int)x andY:(int)y{
if(root == nil){
return false;
}
NSMutableArray *queue = [NSMutableArray new];
NSMutableDictionary *dic = [NSMutableDictionary new];
[queue addObject:root];
while ([queue count] > 0) {
root = [queue objectAtIndex:0];
[queue removeObjectAtIndex:0];
NSLog(@"\n\n%i\nLEVEL: %i\n", root.value, root.level);
if(root.value == x){
[dic setObject:[NSNumber numberWithInt:root.level] forKey:@"X"];
}
if(root.value == y){
[dic setObject:[NSNumber numberWithInt:root.level] forKey:@"Y"];
}
if([dic count] == 2){
if([[dic objectForKey:@"X"] intValue] == [[dic objectForKey:@"Y"] intValue]){
return true;
}
}
if(root.left != nil){
root.left.level = root.level + 1;
[queue addObject:root.left];
}
if(root.rigth != nil){
root.rigth.level = root.level + 1;
[queue addObject:root.rigth];
}
}
return false;
}
From my point of view they want to "split" a string into groups separated by dash and tehy provide the number of elements in the group so assuming that please find below my solution:
//FUNCTION TO SPLIT A STRING WITH A DASH GIVEN THE NUMBER OF ELEMENTS PER GROUP
-(NSString *)getFormatString:(NSString *)string withSplitItems:(int)split{
NSMutableString *result = [NSMutableString new];
//REPLACE ALL DASHES SINCE THEY DO NOT MENTION TO KEEP IT
string = [string stringByReplacingOccurrencesOfString:@"-" withString:@""];
int length = (int)[string length];
int j = -1;
//ITERATE BETWEEN ALL CHARACTERS IN THE STRING FROM THE END TO THE START
for(int i = length - 1; i >= 0; i--){
//IF OUR SECONDARY COUNTER IS EQUAL TO THE GIVEN INDEX SET A DASH
j++;
if(j == split){
result = [result stringByAppendingString:@"-"];
j = 0;
}
//ADD EACH CHARACTER
[result insertString:[string substringWithRange:NSMakeRange(i, 1)] atIndex:0];
}
return result;
}
This is an Objective-C solution in O(n), since is a circular array we need to find the max difference between index and value so the result should be the difference plus current index of the max difference.
Consider follow cases:
2, 3, 0, 1
0, 0, 0, 4, 0
1, 0, 0
-1, 2, 0
- oscarsanchez1937 November 23, 2016