本章包含如下内容
1. 进制转换
2. 括号匹配校验
3. 迷宫求解
-
进制转换
/**
* 进制转换
* @param target 待转换元素
* @param format 转换进制
*/
private String conversion(int target, int format) {
Stack<Integer> stack = new StackImpl<>();
while (target != 0) {
stack.push(target % format);
target = target / format;
}
StringBuilder stringBuilder = new StringBuilder();
while (!stack.isEmpty()) {
stringBuilder.append(stack.pop());
}
return stringBuilder.toString();
}
-
括号匹配校验
private boolean match(String target) throws Exception {
Stack<Character> stack = new StackImpl<>();
for (int i = 0; i < target.length(); i++) {
char c = target.charAt(i);
switch (c) {
case '(':
stack.push(c);
break;
case '{':
stack.push(c);
break;
case '[':
stack.push(c);
break;
case ')':
if (stack.pop() != '(') {
return false;
}
break;
case '}':
if (stack.pop() != '{') {
return false;
}
break;
case ']':
if (stack.pop() != '[') {
return false;
}
break;
default:
throw new Exception("只能支持'(' ')' '{' '}' '[' ']' ");
}
}
return true;
}
- 迷宫求解
迷宫用二维数组来表示,总体思想就是优先往上走，上走不通往左走，左走不通往下走。已经走过上的只能往左走，已经走过左的只能往下走，已经走过下的只能出栈
public class Maze {
class Location {
private final int x;
private final int y;
//限制方向
//0:可以往任何方向走
//1:不能往上走
//2:不能往左,上走
//3:都不能走，等待弹出
private int label;
public int getLabel() {
return label;
}
public void setLabel(int label) {
this.label = label;
}
Location(int x, int y, int label) {
this.x = x;
this.y = y;
this.label = label;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Location location = (Location) o;
return x == location.x &&
y == location.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
}
@Test
public void maze() {
int[][] maze = {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 0, 1, 1, 1, 0, 1, 0},
{0, 1, 1, 0, 1, 1, 1, 0, 1, 0},
{0, 1, 1, 1, 1, 0, 0, 1, 1, 0},
{0, 1, 0, 0, 0, 1, 1, 1, 1, 0},
{0, 1, 1, 1, 0, 1, 1, 1, 1, 0},
{0, 1, 0, 1, 1, 1, 0, 1, 1, 0},
{0, 1, 0, 0, 0, 1, 0, 0, 1, 0},
{0, 0, 1, 1, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};
System.out.println(maze[1][3]);
System.out.println(maze(maze, new Location(1, 1, 0), new Location(8, 8, 0)));
}
boolean maze(int[][] maze, Location beginLocation, Location endLocation) {
Stack<Location> stack = new StackImpl<>();
stack.push(beginLocation);
while (!stack.isEmpty()) {
Location current = stack.getTop();
if (current.equals(endLocation)) {
return true;
}
//不能走则弹出
if (maze[current.y][current.x] == 0) {
stack.pop();
continue;
}
//从上走,已经走过上的不能再走
if (current.label < 1) {
if (current.y - 1 >= 0 ) {
//限制不能往上走
current.setLabel(1);
//可以往上,左
stack.push(new Location(current.x, current.y - 1, 0));
continue;
}
}
//向左走，已经走过左的不能再走
if (current.label < 2) {
if (current.x + 1 < maze[0].length ) {
//限制不能往左走
current.setLabel(2);
//可以上,左,下
stack.push(new Location(current.x + 1, current.y, 0));
continue;
}
}
//向下走
if (current.label < 3) {
if (current.y + 1 < maze.length) {
//这个位置已经往下走过了
current.setLabel(3);
//不能往上走,可以左,下
stack.push(new Location(current.x, current.y + 1, 1));
continue;
}
}
//都不能走
stack.pop();
}
return false;
}
}
