ryangurney
BAN USERYou can expand fib into a tail recursive function, and then from that into a simple iterative loop. From there it's pretty straightforward. O(n).
public static int fibTermsBeforeN(int n)
{
int val = 0;
int prev = 1;
int count = 0;
for(; val < n; ++count)
{
val = val + prev;
prev = val - prev;
}
return count;
}
Also, you could also do this using a single queue with two counters, which would be more efficient. In this case you would only have a space complexity of O(n).
- ryangurney December 08, 2015import java.util.LinkedList;
/**
* Created by Ryan on 12/8/2015.
*/
public class Test
{
public static class Node
{
int data;
Node[] children;
public Node( int data, Node[] children )
{
this.data = data;
this.children = children;
}
}
public static void main(String args[])
{
//Testy test
/*
0
/|\
1 2 3
/ /\
4 5 6
/ /|\
7 8 9 10
*/
Node leaf1 = new Node(4, null);
Node leaf2 = new Node(7, null);
Node leaf3 = new Node(8, null);
Node leaf4 = new Node(9, null);
Node leaf5 = new Node(10, null);
Node inner5 = new Node(6, new Node[]{leaf3, leaf4, leaf5});
Node inner4 = new Node(5, new Node[]{leaf2});
Node inner3 = new Node(3, null);
Node inner2 = new Node(2, new Node[]{inner4, inner5});
Node inner1 = new Node(1, new Node[]{leaf1});
Node root = new Node(0, new Node[]{inner1, inner2, inner3});
printTree(root);
}
public static void printTree(Node root)
{
LinkedList<Node> current = new LinkedList<>();
if(root == null)
return;
current.add(root);
while(current.size() > 0)
{
printLevel(current);
LinkedList<Node> parents = current;
current = new LinkedList<>();
for(Node parent : parents)
{
if( parent.children != null)
{
for (Node c : parent.children)
{
current.add(c);
}
}
}
}
}
public static void printLevel( LinkedList<Node> level)
{
if(level.size() <= 0)
{
return;
}
StringBuilder str = new StringBuilder();
for(Node c : level)
{
if (str.length() > 0)
{
str.append(", ");
}
str.append(c.data);
}
System.out.println(str);
}
}
Hi!
I'm a little confused by some of the answers I'm seeing here.
Are we assuming then that the nodes in the tree already contain a level property in them?
So if I am iterating through the nodes, I could check the current node's level by
curr.level
? That seems too easy.
- ryangurney December 08, 2015This isn't O(n) time.
- ryangurney November 05, 2015static class Coord
{
public final int X;
public final int Y;
public Coord(int x, int y)
{
this.X = x;
this.Y = y;
}
}
public static void exploreAdjLand(int[][] world, int landX, int landY, int[][] map)
{
Stack<Coord> toVisit = new Stack<>();
toVisit.push( new Coord(landX, landY));
map[landX][landY] = 1;
while( !toVisit.isEmpty() ) //Loop through adj. land discovery
{
Coord currCoords = toVisit.pop();
int x = currCoords.X;
int y = currCoords.Y;
if( x-1 >= 0 && map[x-1][y] != 1 && world[x-1][y] == 'X' ) // bounds, already discovered, and type check
{
map[x-1][y] = 1;
toVisit.push(new Coord(x-1,y));
}
if( x+1 < map.length && map[x+1][y] != 1 && world[x+1][y] == 'X' )
{
map[x+1][y] = 1;
toVisit.push(new Coord(x+1,y));
}
if( y-1 >= 0 && map[x][y-1] != 1 && world[x][y-1] == 'X' ) // bounds, already discovered, and type check
{
map[x][y-1] = 1;
toVisit.push(new Coord(x,y-1));
}
if( y+1 < map[x].length && map[x][y+1] != 1 && world[x][y+1] == 'X' )
{
map[x][y+1] = 1;
toVisit.push(new Coord(x,y+1));
}
}
}
public static int findIslands(int[][] world)
{
int[][] map = new int[world.length][world[0].length];
int islandCount = 0;
for(int x = 0; x < world.length; x++)
{
for(int y = 0; y < world[x].length; y++)
{
if(map[x][y] != 1 && world[x][y] == 'X')
{
islandCount++;
exploreAdjLand(world, x, y, map);
}
}
}
return islandCount;
}
string = "ddoge" substring = "dog"
- ryangurney October 20, 2015Yep, I was pretty surprised this wasn't mentioned earlier.
- ryangurney October 20, 2015
Replisafergusona, Consultant at Myntra
I am Lisa from Chicago,I am working as a Show host in the New World. I also work Performs ...
RepHello friends my name Neha Nanda from India Chandigarh city. Doing work in SEO line in Softsys company.
Repsheenaamajors, System Administrator at Achieve Internet
Teach art classes to a diverse array of students of varying ages and abilities. Strong desire to incorporate a multidimensional ...
RepShirleyCWest, Software Engineer at Agilent Technologies
Hello, me Shirley and I from Savage. I am an artist and I love to doing art and I am ...
RepCliftonMalone, Android Engineer at ABC TECH SUPPORT
Hello, I am a Seo Analyst with 5 years of experience in helping large ecommerce websites reach higher organic positions ...
RepI am an energetic sales professional with a track record of consistently increasing sales revenue in a competitive market. Contract ...
RepAnnetteOwens, Email Customer Service at Axiom Sources
Hi , I am Annette, a Data Processor with a comprehensive knowledge of data management and analysis. As I am a ...
RepDeanSims, Associate at ASU
DeanSims a hardworking Tire builder . expert in this work working at Magna Architectural Design . I am also a part of ...
2. in ruby
- ryangurney October 23, 2017