本文共 3426 字，大约阅读时间需要 11 分钟。

问题与解答

1. 问题描述

最近，我在做LeetCode上的题目，遇到了两个中等难度的问题，分别是“最小的路径体力消耗”（题号：1631）和“根据二进制位排序数组”（题号：1356）。这两个题目分别用了不同的方法解决，我在思考过程中也学到了不少东西，想和大家分享一下。

2. 解答思路

• leetcode1631：这个问题需要找到从起点到终点的路径，使得体力消耗最小。每个节点的体力消耗等于该点高度与相邻点高度差的绝对值。为了找到最优路径，我选择了BFS（广度优先搜索）的方法来记录到达每个节点的最小体力消耗。

代码解析：

• 使用一个队列来进行BFS遍历，每次处理一个节点时，检查其上下左右四个方向的相邻节点。

• 对于每个方向，计算当前节点与相邻节点的体力消耗。

• 如果相邻节点还没有被访问过，或者已经被访问过但体力消耗更小，则更新体力消耗并将该节点加入队列。

• 最终，返回到达终点所需的最小体力消耗。

• leetcode1356：这个问题需要将一个数组按照二进制位的1的个数进行排序。也就是说，数组中的每个数转化为二进制后，统计1的个数作为排序键。

代码解析：

• 首先，遍历数组中的每个数，将其转换为二进制字符串。
• 统计每个数的二进制中1的个数，并将这些信息存储在一个哈希表中。
• 根据哈希表中的1的个数对数组进行排序。如果两个数的1的个数相同，则按原数值进行排序。

3. 代码示例

以下是两个问题的解决代码：

leetcode1631：

import java.util.*;class Solution {    public int minimumEffortPath(int[][] heights) {        Map
   
     map = new HashMap<>();        Queue
    
      queue = new LinkedList<>();        map.put("0,0", 0);        queue.offer("0,0");        while (!queue.isEmpty()) {            String temp = queue.poll();            String[] idxs = temp.split(",");            int row = Integer.valueOf(idxs[0]);            int col = Integer.valueOf(idxs[1]);            // 上方            if (row > 0) {                String top = row - 1 + "," + col;                int len = Math.max(Math.abs(heights[row][col] - heights[row - 1][col]), map.get(temp));                if (map.getOrDefault(top, Integer.MAX_VALUE) > len) {                    map.put(top, len);                    queue.offer(top);                }            }            // 左方            if (col > 0) {                String left = row + "," + (col - 1);                int len = Math.max(Math.abs(heights[row][col] - heights[row][col - 1]), map.get(temp));                if (map.getOrDefault(left, Integer.MAX_VALUE) > len) {                    map.put(left, len);                    queue.offer(left);                }            }            // 下方            if (row < heights.length - 1) {                String bottom = row + 1 + "," + col;                int len = Math.max(Math.abs(heights[row][col] - heights[row + 1][col]), map.get(temp));                if (map.getOrDefault(bottom, Integer.MAX_VALUE) > len) {                    map.put(bottom, len);                    queue.offer(bottom);                }            }            // 右方            if (col < heights[0].length - 1) {                String right = row + "," + (col + 1);                int len = Math.max(Math.abs(heights[row][col] - heights[row][col + 1]), map.get(temp));                if (map.getOrDefault(right, Integer.MAX_VALUE) > len) {                    map.put(right, len);                    queue.offer(right);                }            }        }        return map.get(heights.length - 1 + "," + (heights[0].length - 1));    }}
    
   

leetcode1356：

import java.util.*;class Solution {    public int[] sortByBits(int[] arr) {        Map
   
     oneCount = new HashMap<>();        Integer[] arr_copy = IntStream.of(arr).boxed().toArray(Integer[]::new);        for (int i = 0; i < arr.length; i++) {            String binary = Integer.toBinaryString(arr[i]);            oneCount.put(arr[i], binary.length() - binary.replaceAll("1", "").length());        }        Arrays.sort(arr_copy, (a, b) -> oneCount.get(a) == oneCount.get(b) ? a - b : oneCount.get(a) - oneCount.get(b));        return Arrays.stream(arr_copy).mapToInt(Integer::valueOf).toArray();    }}
   

4. 总结

通过这两个问题的解答，我对BFS算法在路径问题中的应用有了更深入的理解，同时也掌握了如何根据二进制位对数组进行排序。解决过程中，我还学会了如何优化代码结构，使其更高效。希望这些代码和解答思路对你有所帮助！