算法面试 - 水壶问题 _算法面试

给你一个装满水的 8 升满壶和两个分别是 5 升、3 升的空壶，请想个优雅的办法，使得其中一个水壶恰好装 4 升水，每一步的操作只能是倒空或倒满。

文章插图

手动推算每种情况

每走一步，杯中不重复的状态变化

文章插图

实现代码

import JAVA.util.ArrayList;import java.util.List;// 水壶问题public class Kettle {private static class Status {int[] kettles = new int[3];Status(int k0, int k1, int k2) {kettles[0] = k0;kettles[1] = k1;kettles[2] = k2;}Status(Status status) {kettles[0] = status.kettles[0];kettles[1] = status.kettles[1];kettles[2] = status.kettles[2];}public boolean isSuccess(int code) {return kettles[0] == code || kettles[1] == code || kettles[2] == code;}@Overridepublic boolean equals(Object obj) {Status status = (Status) obj;return kettles[0] == status.kettles[0] && kettles[1] == status.kettles[1] && kettles[2] == status.kettles[2];}}static int successCode = 4;// 最终需要包含的状态static int[] capitals = {8, 5, 3};// 水壶容量static Status initStatus = new Status(8, 0, 0);// 初始值static List<Status> statuses = new ArrayList<Status>() {{// 初始数组add(new Status(initStatus));}};static List<List<Status>> results = new ArrayList<>();// 结果数组static void iterate(Status status, List<Status> statuses) {if (status.isSuccess(successCode)) {results.add(new ArrayList<>(statuses));return;}for (int i = 0; i < capitals.length; i++) {for (int j = 0; j < capitals.length; j++) {if (i == j) continue;if (status.kettles[i] == 0 || status.kettles[j] == capitals[j]) continue;int difference = Math.min(status.kettles[i], capitals[j] - status.kettles[j]);status.kettles[i] -= difference;status.kettles[j] += difference;if (!statuses.contains(status)) {statuses.add(new Status(status));iterate(status, statuses);statuses.remove(status);}status.kettles[i] += difference;status.kettles[j] -= difference;}}}public static void main(String[] args) {iterate(initStatus, statuses);System.out.println("结果数量：" + results.size());results.forEach(statuses -> {statuses.forEach(status -> System.out.print(" -> " + status.kettles[0] + ", " + status.kettles[1] + ", " + status.kettles[2]));System.out.println();});}}

【算法面试 - 水壶问题】