Background on the problem: If you\'re familiar with the app 2048, this should be
ID: 3564290 • Letter: B
Question
Background on the problem:
If you're familiar with the app 2048, this should be easy to imagine.
You have two classes: Board, and Tile. Board is a class that holds a 2D array of tiles, and has various methods like shift(), clear(), etc..
Tile is a class that holds a value attribute, and other helpful methods that you probably don't need to know.
Tiles can have different values. When you shift a board in a certain direction (up, down, left, right), all tiles shift as far as possible in that directions. Tiles that collide and have an equal value are merged into a new tile with double the that value. As you can probably tell, a shift method in class Board would have a time complexity of O(R * C), where R: # of rows, and C: # of cols.
The class below is similar to Board except that instead of using 2D arrays, it uses 2D linked lists. Give a Big-O estimate for the run-time complexity of the partial implementation of shiftLeft().
NOTE: Below is Java Code, not C/C++.
public class LLBoard {
private LinkedList> tiles;
public Tile tileAt(int row, int col){
return tiles.get(row).get(col);
}
public int shiftLeft(){
for(int row=0; row
// find the first tile in the row
Tile first = null;
int col;
for(col=0; col
first = tileAt(row,col);
if(first != null){ break; } // found first
}
if(first == null){ continue; } // empty row
for(col=col; col<tiles.get(row).size(); cols++){
Tile other = tileAt(row,col);
// constant statements to follow.
}
}
}
}
Explanation / Answer
O(row*col)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.