skywalker42345678
BAN USERConcatenate sorted string and original string. Then sort
god->dgogod
dog->dgodog
Result
[0,0]->[1,0]->[1,1]->[1,2]->[1,3]->[2,3]->[3,3]->[3,2]->[4,2]->[5,2]->[5,3]->[5,4]->[5,5]
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;
public class Maze {
public static void main(String[] args) {
//Use 2D array
int[][] maze = new int[6][6];
maze[0] = new int[] { 1, 1, 0, 0, 0, 0 };
maze[1] = new int[] { 0, 1, 0, 0, 0, 0 };
maze[2] = new int[] { 0, 1, 0, 1, 1, 1 };
maze[3] = new int[] { 1, 1, 1, 1, 0, 1 };
maze[4] = new int[] { 0, 1, 0, 0, 0, 1 };
maze[5] = new int[] { 0, 1, 0, 0, 0, 1 };
//This is the start of exit point of maze
Point start = new Point(0,0);
Point exit = new Point(5,5);
//DFS approach
Stack<Point> s = new Stack<Point>();
s.push(start);
Map<Point,Status> visited = new HashMap<Point,Status>();
visited.put(start, Status.VISITING);
while(!s.isEmpty()){
Point currentP = s.peek();
boolean isAllVisited = true;
for (Point p : getAdjacent(currentP.x, currentP.y)){
//It should be y and x, see above array
if (visited.get(p)==null && maze[p.y][p.x]==1){
visited.put(p, Status.VISITING);
isAllVisited = false ;
s.push(p);
if ( p.equals(exit)){
printPath(s);
}
break;
}
}
if (isAllVisited){
visited.put(currentP, Status.VISITED);
s.pop();
}
}
}
private static void printPath(Stack<Point> s){
while (!s.isEmpty()){
System.out.print("->");
Point p = s.remove(0);
System.out.format("[%d,%d]",p.x,p.y);
}
}
private static List<Point> getAdjacent(int x, int y){
List<Point> result = new ArrayList<Point>();
//above point;
if (y-1>=0) {
result.add(new Point(x, y-1));
};
//right point;
if (x+1<=5) {
result.add(new Point(x+1, y));
};
//below point;
if (y+1<=5) {
result.add(new Point(x, y+1));
};
//left point;
if (x-1>=0) {
result.add(new Point(x-1, y));
};
return result;
}
private static class Point {
int x, y;
public Point(int x,int y) {
this.x = x;
this.y = y;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Point other = (Point) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}
}
private static enum Status {
UNVISITED, VISITING, VISITED
};
}
public class ExpandString {
public static void main(String[] args) {
String data ="A2B3C4 ";
char[] arr = data.toCharArray();
expandString(arr);
System.out.println(arr);
}
public static void expandString(char[] arr){
int endOfModified = arr.length -1;
int i = arr.length;
while (i>0){
i--;
if (arr[i]!=' '){
int n = arr[i]-'0';
i--;
char c = arr[i];
//System.out.format("n=%c, c=%c",n,c);
for (int j=1;j<=n;j++){
arr[endOfModified] = c;
endOfModified--;
}
}
}
}
}
I modified my code. Now the O is (mn) which m is individual visitor, n is average stay hours.
public class FindMaxPersons {
public static void main(String[] args) {
List<PersonTime> data = new ArrayList<PersonTime>();
data.add(new PersonTime(0,3));
data.add(new PersonTime(2,3));
data.add(new PersonTime(0,4));
data.add(new PersonTime(1,3));
data.add(new PersonTime(3,5));
data.add(new PersonTime(3,6));
data.add(new PersonTime(4,5));
Map<Integer, Integer> timeCount = new HashMap<Integer,Integer>();
int maxPerson = 0, time = 0;
for (PersonTime pt: data){
for (int i = pt.arrivalTime ; i<= pt.departureTime ; i++){
Integer count = timeCount.get(i);
if (count==null){
count = 1;
timeCount.put(i, count);
} else {
timeCount.put(i, ++count);
}
if (count > maxPerson){
maxPerson = count;
time = i;
}
}
}
System.out.format("time is %d, max person is %d", time, maxPerson);
}
private static class PersonTime {
int arrivalTime;
int departureTime;
public PersonTime(int arrivalTime, int departureTime){
this.arrivalTime = arrivalTime;
this.departureTime = departureTime;
}
}
}
Frank, thanks for the comments. I was in a hurry and did not have time.
Viktor, my code is slightly better since mine did not iterate for 10 times, only hours he/she spent (eg, 0-3 only 4 times)
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class FindMaxPersons {
public static void main(String[] args) {
List<PersonTime> data = new ArrayList<PersonTime>();
data.add(new PersonTime(0,3));
data.add(new PersonTime(2,3));
data.add(new PersonTime(0,4));
data.add(new PersonTime(1,3));
data.add(new PersonTime(3,5));
data.add(new PersonTime(3,6));
data.add(new PersonTime(4,5));
Map<Integer, Integer> timeCount = new HashMap<Integer,Integer>();
for (PersonTime pt: data){
for (int i = pt.arrivalTime ; i<= pt.departureTime ; i++){
Integer count = timeCount.get(i);
if (count==null){
timeCount.put(i, 1);
} else {
timeCount.put(i, ++count);
}
}
}
int maxPerson = 0, time = 0;
for (Map.Entry<Integer, Integer> entry : timeCount.entrySet()){
if (entry.getValue() > maxPerson){
maxPerson = entry.getValue();
time = entry.getKey();
}
}
System.out.format("time is %d, max person is %d", time, maxPerson);
}
private static class PersonTime {
int arrivalTime;
int departureTime;
public PersonTime(int arrivalTime, int departureTime){
this.arrivalTime = arrivalTime;
this.departureTime = departureTime;
}
}
}
- skywalker42345678 April 01, 2013