Dfs

题目要求Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2.**Example:****Input:** [4, 6, 7, 7]**Output:** [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]**Note:**1. The length of the given array will not exceed 15.2. The range of integer in the given array is [-100,100].3. The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.现有一个无序的整数数组，要求找到所有递增的子序列。 ...

深度优先遍历，广度优先遍历，寻求最短路径本例使用邻接矩阵 public class GraphTest { // 节点 public static class Vertex { public String name; private boolean isVisited; public Vertex(String name) { this.name = name; this.isVisited = false; } public void displayName() { System.out.println("name:" + name); } } // 图 public static class Graph { // 存节点数据 private Vertex[] vertices; // 矩阵 private int[][] matrix; // 队列，用于BFS private Queue<Integer> queue = new LinkedList<>(); // 栈，用于DFS private Stack<Integer> stack = new Stack<>(); private Map<Integer, Integer> dependencyMap = new HashMap<>(); public Graph(Vertex[] vertices, int[][] matrix) { this.vertices = vertices; this.matrix = matrix; } // 找到未访问过的邻接点 public List<Integer> getUnvisitedVertex(int i) { List<Integer> unvisitedVertices = new ArrayList<>(); for (int j = 0; j < matrix.length; j++) { if (matrix[i][j] > 0 && !vertices[j].isVisited) { unvisitedVertices.add(j); } } return unvisitedVertices; } // 广度优先 public void bfs(int vertex) { queue.offer(vertex); while (!queue.isEmpty()) { int v = queue.poll(); if (!vertices[v].isVisited) { vertices[v].displayName(); vertices[v].isVisited = true; List<Integer> unvisitedVertices = getUnvisitedVertex(v); unvisitedVertices.forEach(uv -> { queue.offer(uv); dependencyMap.putIfAbsent(uv, v); }); } } } // 深度优先 public void dfs(int vertex) { stack.push(vertex); while (!stack.isEmpty()) { int v = stack.pop(); if (!vertices[v].isVisited) { vertices[v].displayName(); vertices[v].isVisited = true; List<Integer> unvisitedVertices = getUnvisitedVertex(v); unvisitedVertices.forEach(uv -> stack.push(uv)); } } } // 深度优先递归实现 public void dfsRecursion(int vertex) { if (!vertices[vertex].isVisited) { vertices[vertex].displayName(); vertices[vertex].isVisited = true; List<Integer> unvisitedVertices = getUnvisitedVertex(vertex); unvisitedVertices.forEach(this::dfsRecursion); } } public void printShortestPath(int start, int end) { bfs(start); String symbol = "-->"; StringBuilder sb = new StringBuilder(); sb.append(vertices[end].name); sb.append(symbol); while (dependencyMap.get(end) != null) { sb.append(vertices[dependencyMap.get(end)].name); sb.append(symbol); end = dependencyMap.get(end); } String path = sb.substring(0, sb.lastIndexOf(symbol)); System.out.println(path); } public void clear() { stack.clear(); queue.clear(); dependencyMap.clear(); for (int i = 0; i < vertices.length; i++) { vertices[i].isVisited = false; } } } public static void main(String[] args) { Vertex[] vertices = { new Vertex("v0"), new Vertex("v1"), new Vertex("v2"), new Vertex("v3"), new Vertex("v4") }; int[][] matrix = new int[][]{ {0, 0, 1, 1, 0}, {0, 0, 1, 0, 1}, {1, 1, 0, 0, 1}, {1, 0, 0, 0, 1}, {0, 1, 1, 1, 0} }; Graph graph = new Graph(vertices, matrix); System.out.println("广度优先搜索："); graph.bfs(0); graph.clear(); System.out.println("深度优先搜索："); graph.dfs(0); graph.clear(); System.out.println("递归深度优先搜索："); graph.dfsRecursion(0); graph.clear(); System.out.println("打印最短路径："); graph.printShortestPath(0, 4); }}打印结果广度优先搜索：name:v0name:v2name:v3name:v1name:v4深度优先搜索：name:v0name:v3name:v4name:v2name:v1递归深度优先搜索：name:v0name:v2name:v1name:v4name:v3打印最短路径：name:v0name:v2name:v3name:v1name:v4v4-->v2-->v0 ...

题目要求You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list. Example:Input: 1---2---3---4---5---6--NULL | 7---8---9---10--NULL | 11--12--NULLOutput:1-2-3-7-8-11-12-9-10-4-5-6-NULL思路一：递归实现深度优先遍历从深度优先遍历的角度来看，每次遇到一个包含子节点中间双链表节点，就递归的调用展开方法将其展开，并将展开的结果插入到当前节点的后面。这里需要注意双链表前节点前后指针的变更。步骤如下： ...

题目要求Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.Note:The order of returned grid coordinates does not matter.Both m and n are less than 150.Example:Given the following 5x5 matrix: Pacific ~ ~ ~ ~ ~ ~ 1 2 2 3 (5) * ~ 3 2 3 (4) (4) * ~ 2 4 (5) 3 1 * ~ (6) (7) 1 4 5 * ~ (5) 1 1 2 4 * * * * * * AtlanticReturn:[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).假设左上角的所有周围面积为太平洋，右下角的所有面积为大西洋。现在使用数组来表示一大片水域，其中数组的每一个位置上的元素代表某一个小水域的高度。假定水只能从高出流向低处，要求找出所有既可以流向太平洋也可以流向大西洋的水域。 ...

题目要求A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.Given a list of stones’ positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.If the frog’s last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.Note:The number of stones is ≥ 2 and is < 1,100.Each stone’s position will be a non-negative integer < 231.The first stone’s position is always 0.Example 1:[0,1,3,5,6,8,12,17]There are a total of 8 stones.The first stone at the 0th unit, second stone at the 1st unit,third stone at the 3rd unit, and so on…The last stone at the 17th unit.Return true. The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.Example 2:[0,1,2,3,4,8,9,11]Return false. There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.假设有一只青蛙需要过河，河中会有一些石子，青蛙必须踩在石头上才算成功。石头的位置用整数数组来表示。青蛙的行走规则为：假设上一次青蛙跳了k格，则当前青蛙只能跳k-1或k或k+1格，且青蛙只能向前跳，不能向后跳。广度优先遍历可以从起点开始，对从该点出发的所有可能步数进行遍历，并更新从该点可达的点的所有的可行步数。利用Map<Integer, Set<Integer>>数据结构来记录该结果，其中map的key为stone的unit数，它的value对应的是从该key出发的所有的上一步的步长。该遍历思路类似于广度优先遍历，即将该点出发遍历所有的可达点。代码如下： public boolean canCross(int[] stones) { if(stones.length < 2) return true; if(stones.length == 2 && stones[1] == 1) return true; if(stones.length >= 2 && stones[1] != 1) return false; Map<Integer, Set<Integer>> stoneJump = new HashMap<>(); for(int i = 1 ; i<stones.length ; i++) { stoneJump.put(stones[i], new HashSet<>()); } stoneJump.get(1).add(1); int finalStone = stones[stones.length-1]; boolean hasNext = false; for(int i = 1 ; i<stones.length; i++) { for(int step : stoneJump.get(stones[i])) { int next = stones[i] + step - 1; for(int addOn = -1 ; addOn <= 1 ; addOn++) { if(step + addOn != 0) { if(next == finalStone) { return true; } if(stoneJump.containsKey(next)) { stoneJump.get(next).add(step + addOn); hasNext = true; } } next++; } } if(!hasNext) break; hasNext = false; } return false; }深度优先遍历和上一种思路的区别在于，这种方法会尽可能往远处遍历。即只要该点可以到达下一点，则会立刻尝试从一点到达终点。代码如下： public boolean canCross(int[] stones) { for(int i = 1 ; i<stones.length ; i++) { if(stones[i] - stones[i-1] > i) return false; } return canCross2(stones, 1, 1); } public boolean canCross2(int[] stones, int idx, int lastStep) { if(idx == stones.length-1) return true; if(idx < 0 || lastStep <= 0) return false; for(int jump = lastStep + 1 ; jump >= lastStep -1 ; jump–) { if(canCross2(stones, Arrays.binarySearch(stones, stones[idx] + jump), jump)){ return true; } } return false; } ...

题目要求Given an encoded string, return it’s decoded string.The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].Examples:s = “3[a]2[bc]”, return “aaabcbc”.s = “3[a2[c]]”, return “accaccacc”.s = “2[abc]3[cd]ef”, return “abcabccdcdcdef”.将一个字符串解码，要求按照次数展开原字符串中的中括号。如3[a]2[bc]对应的字符串就是aaabcbc，即a展开3次，bc展开2次。注意，源字符串中的括号是允许嵌套的，且展开的字符中不会包含任何数字。思路一：递归其实递归的思路是很明显的，一旦我们遇到一个左括号，我们就可以找到其对应的右括号，然后对括号中的内容递归的展开，再将返回结果给上层，根据上次的次数再次展开。如3[a2[c]]=>3[acc]=>accaccacc。递归这里需要注意的是如何找到当前括号对应的右括号。这里可以采用一个小技巧，即从当前括号位置开始，每遇到一个左括号计数就+1，遇到一个右括号计数就-1，当计数器第一次被减为0时，则该位置上的右括号就是我们所要找的对应的右括号。代码如下： public String decodeString2(String s) { if (s.length() == 0) return “”; StringBuilder sb = new StringBuilder(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c >= ‘0’ && c <= ‘9’) { // 解析次数 int digitStart = i++; while (s.charAt(i) >= ‘0’ && s.charAt(i) <= ‘9’) i++; int num = Integer.parseInt(s.substring(digitStart, i)); // 找到对应的右括号 int strStart = i+1; // number must be followed by ‘[’ int count = 1; i++; while (count != 0) { if (s.charAt(i) == ‘[’) count++; else if (s.charAt(i) == ‘]’) count–; i++; } i–; // 取子字符串 String subStr = s.substring(strStart, i); // 将子字符串解码 String decodeStr = decodeString(subStr); // 将解码的结果拼接到当前的字符串后面 for (int j = 0; j < num; j++) { sb.append(decodeStr); } } else { // 添加首元素 sb.append(c); } } return sb.toString(); }思路二：栈我们知道，有一些递归的思路是可以转化为栈的，这里同样如此。利用栈我们可以存储外围层已持有的字符串以及应当展开的次数。用栈的思路来写要求思路更加严谨，以免出现逻辑错误。首先，我们会用两个指针lft，rgt分别来记录数字的起始位置和结束位置。同时，rgt还作为我们遍历整个字符串的指针。rgt的情形有如下几种可能：rgt指向[rgt指向]rgt指向数字rgt指向字母下面我们来逐个分析各种场景：1. rgt指向[此时左括号的左侧只会有一种情形，它的左边一定是数字。因此当我们遇到左括号时，我们应当记录左括号左边的数字，并将lft指针移动到左括号下一个位置。这里需要额外注意的是，如果当前该括号外围存在父元素，则我们应当将父元素的计数和已有字符串压入栈中。可以将这个操作理解为上下文切换。2. rgt指向]右括号意味着当前的字符展开序列遍历完毕，因此我们需要做以下几件事情：将lft和rgt之间的内容append到当前上下文的字符串中根据展开次数展开当前上下文的字符串如果存在父元素，则从栈中弹出父元素，恢复父级上下文将当前上文得到的结果append到父元素的字符串中3. rgt指向字母我们需要将rgt指向的字母添加到当前的上下文字符串中去。不要忘记将左指针移动到当前位置后面4. rgt指向数字数字将会在遇见[时提取出来，因此我们无需进行任何处理一个具体的例子假如现在输入的字符串为3[a2[c]]，我们有字符串栈s，计数栈c，指针lft，rgt，并用临时变量tmp，number分别记录当前上下文中计数和字符串。运行情况如下：lft=0 rgt=0 : 不执行任何操作lft=0 rgt=1 : 解析当前上下文应当展开的次数 number=3, lft=2lft=2 rgt=2 : 将当前的字符添加到当前的上下文中去，tmp=“a” lft=3lft=3 rgt=3 : 不做任何处理lft=3 rgt=4 : 将父级上下文压入栈中，并解析当前上下文的展开次数 s:[“a”] c:[3] lft=5 tmp="" number=2lft=5 rgt=5 : 将当前的字符添加到当前的上下文中去，tmp=“c” lft=6lft=6 rgt=6 : 展开当前字符串，并恢复父级上下文, tmp=“a”+“cc”, number=3 s:[] c:[] lft=7lft=7 rgt=7 : 展开当前字符串，= 此时没有父级上下文，因此无需恢复。tmp=“accaccacc” number=0代码如下： public String decodeString(String s) { Stack<Integer> count = new Stack<>(); Stack<StringBuilder> letters = new Stack<>(); int lft = 0, rgt = -1; int number = 0; StringBuilder result = null; while(++rgt < s.length()) { char c = s.charAt(rgt); if(c == ‘[’) { if(result != null) { count.push(number); letters.push(result); } result = new StringBuilder(); number = Integer.valueOf(s.substring(lft, rgt)); lft = rgt+1; }else if(c == ‘]’) { result.append(s.substring(lft, rgt)); StringBuilder tmp = new StringBuilder(result); for(int i = 0 ; i<number-1 ; i++) { result.append(tmp); } if(!letters.isEmpty()) { StringBuilder pop = letters.pop(); pop.append(result); result = pop; number = count.pop(); } lft = rgt+1; }else if(Character.isAlphabetic(c)) { if(result==null) { result = new StringBuilder(); } result.append(c); lft = rgt+1; } } if(result == null) { result = new StringBuilder(); } result.append(s.substring(lft, rgt)); return result.toString(); }想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~ ...

ProblemThe n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.Given an integer n, return all distinct solutions to the n-queens puzzle.Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.Example:Input: 4Output: [ [".Q..", // Solution 1 “…Q”, “Q…”, “..Q.”], ["..Q.", // Solution 2 “Q…”, “…Q”, “.Q..”]]Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.Solutionclass Solution { public List<List<String>> solveNQueens(int n) { char[][] board = new char[n][n]; for (int i = 0; i < n; i++) { Arrays.fill(board[i], ‘.’); } List<List<String>> res = new ArrayList<>(); dfs(board, 0, res); return res; } private void dfs(char[][] board, int col, List<List<String>> res) { if (col == board.length) { res.add(construct(board)); return; } for (int row = 0; row < board.length; row++) { if (validate(board, row, col)) { board[row][col] = ‘Q’; dfs(board, col+1, res); board[row][col] = ‘.’; } } } private boolean validate(char[][] board, int row, int col) { for (int i = 0; i < board.length; i++) { for (int j = 0; j < col; j++) { if (board[i][j] == ‘Q’ && ( i+j == row+col || row+j == col+i || row == i )) return false; } } return true; } private List<String> construct(char[][] board) { List<String> res = new ArrayList<>(); for (int i = 0; i < board.length; i++) { String str = new String(board[i]); res.add(str); } return res; }} ...

ProblemGiven a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.Note:If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].All airports are represented by three capital letters (IATA code).You may assume all tickets form at least one valid itinerary.Example 1:Input: [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]]Output: [“JFK”, “MUC”, “LHR”, “SFO”, “SJC”]Example 2:Input: [[“JFK”,“SFO”],[“JFK”,“ATL”],[“SFO”,“ATL”],[“ATL”,“JFK”],[“ATL”,“SFO”]]Output: [“JFK”,“ATL”,“JFK”,“SFO”,“ATL”,“SFO”]Explanation: Another possible reconstruction is [“JFK”,“SFO”,“ATL”,“JFK”,“ATL”,“SFO”]. But it is larger in lexical order.Solutionclass Solution { public List<String> findItinerary(String[][] tickets) { Map<String, PriorityQueue<String>> map = new HashMap<>(); List<String> res = new ArrayList<>(); for (String[] ticket: tickets) { if (!map.containsKey(ticket[0])) map.put(ticket[0], new PriorityQueue<>()); map.get(ticket[0]).add(ticket[1]); } dfs(“JFK”, map, res); return res; } public void dfs(String departure, Map<String, PriorityQueue<String>> map, List<String> res) { PriorityQueue<String> arrivals = map.get(departure); while (arrivals != null && arrivals.size() > 0) { dfs(arrivals.poll(), map, res); } res.add(0, departure); }} ...

ProblemGiven an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.Note:The order of returned grid coordinates does not matter.Both m and n are less than 150.Example:Given the following 5x5 matrix: Pacific ~ ~ ~ ~ ~ ~ 1 2 2 3 (5) * ~ 3 2 3 (4) (4) * ~ 2 4 (5) 3 1 * ~ (6) (7) 1 4 5 * ~ (5) 1 1 2 4 * * * * * * AtlanticReturn:[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).Solutionclass Solution { public List<int[]> pacificAtlantic(int[][] matrix) { List<int[]> res = new ArrayList<>(); if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return res; int m = matrix.length, n = matrix[0].length; boolean[][] pac = new boolean[m][n]; boolean[][] atl = new boolean[m][n]; int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}}; for (int i = 0; i < m; i++) { dfs(matrix, pac, dirs, i, 0); dfs(matrix, atl, dirs, i, n-1); } for (int j = 0; j < n; j++) { dfs(matrix, pac, dirs, 0, j); dfs(matrix, atl, dirs, m-1, j); } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (pac[i][j] && atl[i][j]) res.add(new int[]{i,j}); } } return res; } private void dfs(int[][] matrix, boolean[][] visited, int[][] dirs, int i, int j) { int m = matrix.length, n = matrix[0].length; visited[i][j] = true; for (int[] dir: dirs) { int x = i+dir[0]; int y = j+dir[1]; if (x < 0 || y < 0 || x >= m || y >= n || visited[x][y] || matrix[x][y] < matrix[i][j]) continue; else dfs(matrix, visited, dirs, x, y); } }} ...

题目You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.Operations allowed:Fill any of the jugs completely with water.Empty any of the jugs.Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.Example 1: (From the famous “Die Hard” example)Input: x = 3, y = 5, z = 4Output: TrueExample 2:Input: x = 2, y = 6, z = 5Output: False假设现在有两个杯子，每个杯子分别最多可以装x和y升水，假设现在水的供应量是无限的，问是否有可能用这两个杯子共同承装z升水，可以用两个杯子执行的操作如下：将任何一个杯子装满水倒掉任何一个杯子中的所有水将一个杯子中的水倒进另一个杯子，直到另一个杯子满了或者是当前的杯子已经空了比如，如果现在两个杯子A和B分别能装3升水和5升水，需要在两个杯子中共装4升水。我们可以找到这样一个序列满足题目要求：将B杯倒满水并导入A中，此时A:3 B:2将A杯倒空，并将B中的水倒入A中，此时A:2 B:0将B杯装满并倒A中，此时A:3 B:4将A杯倒掉，此时A:0 B:4思路一：搜索这里可以说我们变相的利用了深度/广度优先搜索来实现。通过深度/广度优先搜索我们可以实现遍历所有可能的场景，直到找到我们最终想要的结果，或者得到该结果无法达到的结论。假设我们知道当前水杯的情况为A最多可以放置x升水，B最多可以放置Y升水，而且A当前水杯中有a升水，B中有b升水，则由当前情况在一次操作之后可能产生以下几种情况：倒光A中的水：A:0 | B:b倒光B中的水：A:a | B:0装满A中的水：A:x | B:b装满B中的水：A:a | B:y将A中的水倒进B中：A:a - min(a, y-b) | B:b + min(a, y-b)将B中的水倒进A中：A:a + min(x-a, y) | B:b - min(x-a, y)最后两种情况需要判断两个杯子的剩余水情况和可倒入水的情况如果以上几种情况都不满足z，则我们再以以上几种情况为基础继续寻找可能的情况。这里可以使用HashSet来避免对情况的重复遍历。代码如下： public class Status{ private int x; private int y; public int getX() { return x; } public int getY() { return y; } public int getWater() { return this.getX() + this.getY(); } public Status(int x, int y) { this.x = x; this.y = y; } @Override public boolean equals(Object o) { if(o==null || !(o instanceof Status)) return false; if(this == o) return true; Status s = (Status) o; return this.getX() == s.getX() && this.getY() == s.getY(); } @Override public int hashCode() { return this.getX() + 17 * this.getY(); } } Set<Status> statusSet = new HashSet<Status>(); public boolean canMeasureWaterDFS(int x, int y, int z) { if(x + y < z) return false; if(x == z || y == z || x + y == z) return true; return canMeasureWaterDFS(x, y , new Status(0, 0), z); } public boolean canMeasureWaterDFS(int x, int y, Status curStatus, int z) { if(statusSet.contains(curStatus)) return false; else if(curStatus.getWater() == z) return true; else{ statusSet.add(curStatus); return canMeasureWaterDFS(x, y, new Status(x, curStatus.getY()), z) || canMeasureWaterDFS(x, y, new Status(curStatus.getX(), y), z) || canMeasureWaterDFS(x, y, new Status(curStatus.getX(), 0), z) || canMeasureWaterDFS(x, y, new Status(0, curStatus.getY()), z) || canMeasureWaterDFS(x, y, new Status( curStatus.getX() - Math.min(curStatus.getX(), y-curStatus.getY()), curStatus.getY() + Math.min(curStatus.getX(), y-curStatus.getY()) ), z) || canMeasureWaterDFS(x, y, new Status( curStatus.getX() + Math.min(x - curStatus.getX(), curStatus.getY()), curStatus.getY() - Math.min(x - curStatus.getX(), curStatus.getY()) ), z); } }思路二：数学这里使用了一个数学结论叫做Bézout’s identity，在该理论中，假设数字a和b有一个最大公约数d，则一定存在x和y满足ax+by=d。x,y的其它组合所得到的值一定是d的倍数。这里x为负值时代表将杯子倒空，x为正值时代表将杯子装满。 public boolean canMeasureWater(int x, int y, int z) { if(x == z || y == z || x + y == z) return true; if(x + y < z) return false; while( (x %= y) != 0 && (y %= x) != 0); return z % (x+y) == 0; } ...