09-08字节跳动2,3题其中2题没有跑，3题应该没问题
都是自己理解的不对勿喷
//这个题主要还是理解题意，一排方块，里面有自然数，<,>三种情况。走到数字后数字减一，走到0时摧毁这个方块然后继续走，走到<>时改变方向，若下一个也为<>摧毁当前方块
package AMain;
import java.util.Arrays;
import java.util.LinkedList;
public class MainB {
static LinkedList list = new LinkedList();
public static void main(String[] args) {
while (true) {
String[] temp = new String[]{"", "4", "7", ">", "9", "8", "3", "", "9", "4", "1"};
int nn = (int) (Math.random() * 10);
int mm = 10;
int l = (int) (Math.random() * nn);
int r = (int) (Math.random() * nn);
if (l > r) {
l = 0;
}
String[] arr = new String[nn];
for (int i = 0; i < arr.length; i++) {
arr[i] = temp[(int) (Math.random() * temp.length)];
}
if (arr.length == 0) {
continue;
}
arr = new String[]{">", "2", "2", "<"};
System.out.println( "数组：" + Arrays.toString( arr ) + "--left:" + l + "--right:" + r );
process( 0, 3, arr );
System.out.println( list.get( 0 ) );
list.clear();
}
}
//核心方法
private static void process(int l, int r, String[] arr) {
int count = 0;
int i = l;
//思路：我用-1代表这个方块已经被摧毁
boolean flag = true;//走向：true往右走，false往左走
while (true) {
if (i > r || i < l) {//越界
list.add( count );
return;
} else {
if (arr[i].equals( ">" )) {
int temp = i;//临时变量，当下一步为时需要将当前摧毁
i++;
while (i <= r && arr[i].equals( "-1" )) {//一直找直到不是摧毁方块
i++;
}
if (i > r) {//先判断是否越界
list.add( count );
return;
} else if (arr[i].equals( ">" )) {
flag = true;//更改走向
arr[temp] = "-1";//上一个方块摧毁
} else if (arr[i].equals( "<" )) {//同上
flag = false;
arr[temp] = "-1";
}
} else if (arr[i].equals( "<" )) {//同上
int temp = i;
i--;
while (i >= l && arr[i].equals( "-1" )) {
i--;
}
if (i < l) {
list.add( count );
return;
} else if (arr[i].equals( ">" )) {
flag = true;
arr[temp] = "-1";
} else if (arr[i].equals( "<" )) {
flag = false;
arr[temp] = "-1";
}
} else if (Integer.valueOf( arr[i] ) == -1) {//为摧毁方块，需要判断方向
if (flag) {
i++;
} else {
i--;
}
} else {
int temp = Integer.valueOf( arr[i] );//为数字时，先加数字，在减一
count += temp;
arr[i] = String.valueOf( temp - 1 );
if (flag) {
i++;
} else {
i--;
}
}
}
}
}
}给三个没有刻度只知道最大容量的桶，假设容量分别为xyz桶可以盛满水，可以倒掉，可以两桶之间倒水(直到一桶倒空或者倒满)请求出最快需要多少步能够量出k的容量
假设这三个桶的容量为3 5 8 要求量出4升最短为 0 0 0—0 5 0—3 2 0—0 2 0—2 0 0—2 5 0—3 4 0
DFS然后列出所有情况，放入队列中一个一个对比是否为结果
package AMain;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<Node> list = new LinkedList<>( );
int x = 3,y=5,z=8,res = 4;
Node node = new Node(0,0,0,0);
list.add( node );
while(!list.isEmpty()){
Node n = list.pollFirst();
if(n.x==res || n.y==res || n.z ==res){//结束
System.out.println(n.index);
return;
}else{
//以下为倒水的所有情况
if(n.x == 0){//x空
Node n1 = new Node(x,n.y,n.z,n.index+1);
list.add( n1 );
}
if(n.y==0){//y空
Node n1 = new Node(n.x,y,n.z,n.index+1);
list.add( n1 );
}
if(n.z == 0){//z空
Node n1 = new Node(n.x,n.y,z,n.index+1);
list.add( n1 );
}
if(n.x!=0 && n.y<y){//x有水且可以往y中倒入
Node n1 = null;
if(y-n.y>=n.x){//倒入后x没有剩余
n1 = new Node(0,n.y+n.x,n.z,n.index+1);
}else{//有剩余
n1 = new Node(n.x-(y-n.y),y,n.z,n.index+1);
}
list.add( n1 );
}
if(n.x!=0 && n.z<z){//x有水且可以往z中倒入
Node n1 = null;
if(z-n.z>=n.x){//倒入后x没有剩余
n1 = new Node(0,n.y,n.z+n.x,n.index+1);
}else{//有剩余
n1 = new Node(n.x-(z-n.z),n.y,z,n.index+1);
}
list.add( n1 );
}
if(n.y!=0 && n.x<x){//y有水且可以往x中倒入
Node n1 = null;
if(x-n.x>=n.y){//倒入后y没有剩余
n1 = new Node(n.x+n.y,0,n.z,n.index+1);
}else{//有剩余
n1 = new Node(x,n.y-(x-n.x),n.z,n.index+1);
}
list.add( n1 );
}
if(n.y!=0 && n.z<z){//y有水且可以往z中倒入
Node n1 = null;
if(z-n.z>=n.y){//倒入后y没有剩余
n1 = new Node(n.x,0,n.z+n.y,n.index+1);
}else{//有剩余
n1 = new Node(n.x,n.y-(z-n.z),z,n.index+1);
}
list.add( n1 );
}
if(n.z!=0 && n.x<x){//z有水且可以往x中倒入
Node n1 = null;
if(x-n.x>=n.z){//倒入后z没有剩余
n1 = new Node(n.x+n.z,n.y,0,n.index+1);
}else{//有剩余
n1 = new Node(x,n.y,n.z-(x-n.x),n.index+1);
}
list.add( n1 );
}
if(n.z!=0 && n.y<y){//z有水且可以往y中倒入
Node n1 = null;
if(y-n.y>=n.z){//倒入后z没有剩余
n1 = new Node(n.x,n.y+n.z,0,n.index+1);
}else{//有剩余
n1 = new Node(n.x,y,n.z-(y-n.y),n.index+1);
}
list.add( n1 );
}
}
}
System.out.println(-1);
}
}
class Node {
int x;
int y;
int z;
int index ;
public Node(int x,int y,int z,int index){
this.x = x;
this.y = y;
this.z = z;
this.index = index;
}
}#笔试题目##笔经##秋招##Java##校招##字节跳动#
