面试遇到一个算法问题,寻求思路
本文介绍了面试遇到一个算法问题,寻求思路的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
问 题
更新【2016-05-13 12:10】
这是我用穷举的方式实现的,达不到最快的方法
主类:SortBlock.java
package demo;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class SortBlock {
public static void main(String[] args) {
Random random = new Random();
int count = 0;
Block[][] blocks = {
{ new Block(ColorEnum.Y), new Block(ColorEnum.R), new Block(ColorEnum.B), new Block(ColorEnum.B) },
{ new Block(ColorEnum.R), new Block(ColorEnum.R), new Block(ColorEnum.B), new Block(ColorEnum.B) },
{ new Block(ColorEnum.R), new Block(ColorEnum.R), new Block(ColorEnum.B), new Block(ColorEnum.B) },
{ new Block(ColorEnum.R), new Block(ColorEnum.R), new Block(ColorEnum.B), new Block(ColorEnum.B) } };
System.out.println("开始:");
printBlock(blocks);
while (!isFinish(blocks)) {
String[] position = getMoveBlockPosition(blocks).split("-");
int i = Integer.parseInt(position[0]);
int j = Integer.parseInt(position[1]);
int derection = getMoveDirection(random, i, j);
// System.out.println("第" + count + "步 - 移动位置[" + i + "," + j + "] -
// 方向[" + direction + "]");
blocks = updateBlock(blocks, derection, i, j);
count++;
}
System.out.println("");
System.out.println("");
System.out.println("");
System.out.println("总计:" + count + "步");
System.out.println("");
System.out.println("");
System.out.println("");
System.out.println("结果:");
printBlock(blocks);
}
// 打印所有块
public static void printBlock(Block[][] blocks) {
for (int i = 0; i < blocks.length; i++) {
for (int j = 0; j < blocks[i].length; j++) {
if (j == blocks[i].length - 1) {
System.out.print(blocks[i][j].blockColor);
} else {
System.out.print(blocks[i][j].blockColor + " - ");
}
}
System.out.println("");
}
}
// 更新黄色块移动后所有块的位置
public static Block[][] updateBlock(Block[][] blocks, int derection, int i, int j) {
ColorEnum temp;
if (derection == 0) {
temp = blocks[i][j - 1].blockColor;
blocks[i][j - 1].blockColor = ColorEnum.Y;
blocks[i][j].blockColor = temp;
} else if (derection == 1) {
temp = blocks[i - 1][j].blockColor;
blocks[i - 1][j].blockColor = ColorEnum.Y;
blocks[i][j].blockColor = temp;
} else if (derection == 2) {
temp = blocks[i][j + 1].blockColor;
blocks[i][j + 1].blockColor = ColorEnum.Y;
blocks[i][j].blockColor = temp;
} else if (derection == 3) {
temp = blocks[i + 1][j].blockColor;
blocks[i + 1][j].blockColor = ColorEnum.Y;
blocks[i][j].blockColor = temp;
}
return blocks;
}
// 随机获取黄色块的可移动方向
public static int getMoveDirection(Random random, int i, int j) {
// 左边:0
// 上边:1
// 右边:2
// 下边:3
List<Integer> arrs = new ArrayList<>();
if (i == 0) {
if (j == 0) {
arrs.add(2);
arrs.add(3);
} else if (j == 3) {
arrs.add(0);
arrs.add(3);
} else {
arrs.add(0);
arrs.add(2);
arrs.add(3);
}
} else if (i == 3) {
if (j == 0) {
arrs.add(1);
arrs.add(2);
} else if (j == 3) {
arrs.add(0);
arrs.add(1);
} else {
arrs.add(0);
arrs.add(1);
arrs.add(2);
}
} else {
if (j == 0) {
arrs.add(1);
arrs.add(2);
arrs.add(3);
} else if (j == 3) {
arrs.add(0);
arrs.add(1);
arrs.add(3);
} else {
arrs.add(0);
arrs.add(1);
arrs.add(2);
arrs.add(3);
}
}
return arrs.get(random.nextInt(arrs.size()));
}
// 获取黄色块的当前位置
public static String getMoveBlockPosition(Block[][] blocks) {
for (int i = 0; i < blocks.length; i++) {
for (int j = 0; j < blocks[i].length; j++) {
if (blocks[i][j].canMove()) {
return i + "-" + j;
}
}
}
return null;
}
// 判断是否达到最终的效果
public static boolean isFinish(Block[][] blocks) {
if (blocks[0][0].blockColor.equals(ColorEnum.Y) && blocks[0][1].blockColor.equals(ColorEnum.B)
&& blocks[0][2].blockColor.equals(ColorEnum.R) && blocks[0][3].blockColor.equals(ColorEnum.B)
&& blocks[1][0].blockColor.equals(ColorEnum.B) && blocks[1][1].blockColor.equals(ColorEnum.R)
&& blocks[1][2].blockColor.equals(ColorEnum.B) && blocks[1][3].blockColor.equals(ColorEnum.R)
&& blocks[2][0].blockColor.equals(ColorEnum.R) && blocks[2][1].blockColor.equals(ColorEnum.B)
&& blocks[2][2].blockColor.equals(ColorEnum.R) && blocks[2][3].blockColor.equals(ColorEnum.B)
&& blocks[3][0].blockColor.equals(ColorEnum.B) && blocks[3][1].blockColor.equals(ColorEnum.R)
&& blocks[3][2].blockColor.equals(ColorEnum.B) && blocks[3][3].blockColor.equals(ColorEnum.R)) {
return true;
}
return false;
}
}
工具类:Block.java
package demo;
public class Block {
ColorEnum blockColor;
public Block(ColorEnum blockColor) {
this.blockColor = blockColor;
}
public boolean canMove() {
if (this.blockColor.equals(ColorEnum.Y)) {
return true;
}
return false;
}
}
工具类:ColorEnum.java
package demo;
public enum ColorEnum {
Y, R, B
}
解决方案
其实这个你每天都见着的。不要把黄色看做方块,直接看成是一个空,有了空就可以移动那些方块。这样一看有没有想到是什么东西?其实就是手机桌面,然后排列桌面图标。为了好好解释下,我还特意把我的手机apps排了一下。不知道你小时候有没有玩过这种拼图,4x4只有15个方块。
这篇关于面试遇到一个算法问题,寻求思路的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文