数据结构与算法学习（十六）

1、最长公共前缀

1.1、题目描述

编写一个函数来查找字符串数组中的最长公共前缀，如果不存在公共前缀，返回空字符串 ""。

1.2、解题思路

创建一个变量 result，这个变量存放结果，初始化为第一个字符串
用 result 去与剩下的字符串进行比较，截取它们公共的前缀
以此类推，在与最后一个字符串进行比较并截取后，result 就是最后的结果，如果在此过程中 result 的长度变为 0 ，那么证明没有最长公共前缀

1.3、解题代码

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) {
        return "";
    }
    char[] chars = strs[0].toCharArray();
    // 这个变量用于确定最长公共前缀的长度，初始化为一个最大值
    int min = Integer.MAX_VALUE;
    for (String str : strs) {
        char[] temp = str.toCharArray();
        // 用于判断第一个字符串和其他字符串的公共前缀长度
        int index = 0;
        while (index < temp.length && index < chars.length) {
            // 如果两个数组中指定下标的字符不相同，那么证明找到的公共前缀结束
            if (chars[index] != temp[index]) {
                break;
            }
            index++;
        }
        // 更新最长公共前缀，取最小值
        min = Math.min(min, index);
        // 如果在对比过程中发现 min 为 0 ，证明此时最长公共子串已经不存在，可以不用继续下去了
        if (min == 0) {
            return "";
        }
    }
    return strs[0].substring(0, min);
}

2、两数之和

2.1、题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

2.2、解题思路

使用哈希表完成

循环遍历数组，得到整数目标值 target 与当前遍历元素 current 的差，记为 difference ，然后去哈希表中查找有没有关于 difference 的记录，哈希表中以值为键，以该值在数组中的下标为值

如果有，那么此时就找到了一个结果，将结果返回即可
如果没有，我们需要将当前值 current 作为键，以 current 对应下标作为值，将这条记录放入哈希表中

使用双指针求解

对数组进行排序
初始化两个指针，左指针指向数组开头的元素，而右指针指向数组结尾元素，对此时指针指向的两个元素进行相加，查看得到的和 sum

如果 sum < target ，那么让左指针 left 右移
如果 sum > target ，那么让右指针 right 左移
如果 sum == target ，那么返回此时两个数在原来数组的下标即可。

2.3、解题代码

使用哈希表求解

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> memo = new HashMap<>();
    for(int i = 0;i < nums.length;i++) {
        int difference = target - nums[i];
        if (memo.containsKey(difference)) {
            return new int[] {memo.get(difference), i};
        }
        memo.put(nums[i], i);
    }
    return null;
}

使用双指针进行求解

public int[] twoSum(int[] nums, int target) {
    // 使用一个数组保存原数组中的数据
    List<Integer> result = new ArrayList<>();
    int[] origin = new int[nums.length];
    System.arraycopy(nums, 0, origin, 0, origin.length);
    Arrays.sort(nums);
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum < target) {
            left++;
        } else if(sum > target) {
            right--;
        } else {
            break;
        }
    }
    for (int i = 0;i < nums.length;i++) {
        if (origin[i] == nums[left] || origin[i] == nums[right]) {
            result.add(i);
        }
    }
    int[] res = new int[result.size()];
    for (int i = 0; i < result.size(); i++) {
        res[i] = result.get(i);
    }
    return res;
}

3、三数之和

3.1、题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

3.2、解题思路

这个问题从两数之和演进而来，我们参考两数之和中双指针的解题思路，先对数组排序，然后让一根指针 P 指向数组最左侧

此时我们将 P 指针指向的元素作为三元组的第一个数，此时题目就可以转换为在剩下的元素中找和为 target - nums[P] 的两个数

在得到以 nums[P] 作为第一个元素的所有三元组后，让 P 后移，此时如果发现 nums[P] 与前一个数相等，那么直接跳过；
重复以上流程，当一次循环结束后，我们就找到了所有符合条件的三元组
在指针移动 P 移动到 i 时，我们只需要从剩下的 [i + 1,nums.length - 1] 中找二元组即可

这是因为当 P 在 [0, i] 时，已经将前面的答案都试过了

当指针 P 指向的元素大于 target 时，此时可以终止流程，因为上述流程是在有序数组中进行的，当 nums[P] 大于 target 时，后面的元素一定大于 target ，所以不可能存在和为 target - nums[P] 的二元组

3.3、解题代码

public List<List<Integer>> threeSum(int[] nums) {
    return threeSum(nums, 0);
}
/***
 * 找出数组中和为 target 的所有不重复的三元组
 * @param nums
 * @param target
 * @return
 */
public List<List<Integer>> threeSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums == null || nums.length == 0) return result;
    // 对数组进行排序
    Arrays.sort(nums);
    int index = 0;
    while (index < nums.length - 2) {
        if (nums[index] > target) {
            break;
        }
        // 只有当当前数不等于上一个数时，才进行答案收集
        if (index == 0 || nums[index] != nums[index - 1]) {
            List<List<Integer>> twoSumList = twoSum(nums, index + 1, target - nums[index]);
            for (List<Integer> cur : twoSumList) {
                cur.add(0, nums[index]);
                result.add(cur);
            }
        }
        index++;
    }
    return result;
}
/**
 * 从 nums 下标为 [index,nums.length - 1] 的元素中，找出和为 target 的所有二元组
 * 注意，这里的 nums 数组应是有序的
 * @param nums
 * @param index
 * @param target
 * @return
 */
public List<List<Integer>> twoSum(int[] nums, int index, int target) {
    List<List<Integer>> result = new ArrayList<>();
    if (nums == null || nums.length == 0) return result;
    if (index < 0 || index > nums.length - 1) return result;
    // 对数组进行排序
    int left = index, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum < target) {
            left++;
        } else if (sum > target) {
            right--;
        } else {
            // 只有当 left 指针指向的值不等于它前面的值时，才进行收集
            // 否则会出现重复值
            if (left == index || nums[left - 1] != nums[left]) {
                List<Integer> current = new ArrayList<>();
                current.add(nums[left]);
                current.add(nums[right]);
                result.add(current);
            }
            left++;
        }
    }
    return result;
}

4、电话号码的字母组合

4.1、题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例一

1 2	输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例二

1 2	输入：digits = "2" 输出：["a","b","c"]

4.2、解题思路

先列出每个数字对应的字母列表
使用回溯算法，找出每个字母下对应的字符串数组，分别递归，查找出所有的可能性

比如说用户输入了 “23” ，那么先深度遍历 2 对应的字符数组，即 [‘a’,’b’,’c’] ，然后遍历 2 对应的字符数组中元素的过程中，又对 3 对应的字符数组进行遍历，组成所有结果并收集

4.3、解题代码

public char[][] phoneCharArray = {
        //0
        {},
        //1
        {},
        //2
        {'a','b','c'},
        //3
        {'d','e','f'},
        //4
        {'g','h','i'},
        //5
        {'j','k','l'},
        //6
        {'m','n','o'},
        //7
        {'p','q','r','s'},
        //8
        {'t','u','v'},
        //9
        {'w','x','y','z'}
};
public List<String> letterCombinations(String digits) {
    List<String> result = new ArrayList<>();
    if (digits == null || digits.length() == 0) return result;
    char[] str = digits.toCharArray();
    char[] path = new char[str.length];
    find(str, 0, path, result);
    return result;
}


private void find(char[] str, int index, char[] path, List<String> result) {
    // index 代表当前正在访问 str 数组中下标为 index 的元素
    // 如果此时 index == str.length - 1 ，代表访问到最后一个元素
    if (index == str.length) {
        // 此时可以收集答案，我们将答案放在 path 数组中
        result.add(String.valueOf(path));
    } else {
        // 通过 str[index] 拿到数字对应的字符数组，这里需要 - '0' ，从数字字符转换为数字
        char[] charArray = phoneCharArray[str[index] - '0'];
        for (char current : charArray) {
            path[index] = current;
            // 以当前字符为前一个元素，查找下一个元素的所有可能性
            find(str, index + 1, path, result);
        }
    }
}

5、有效的括号

5.1、题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例一

1 2	输入：s = "{[]}" 输出：true

示例二

1 2	输入：s = "(]" 输出：false

示例三

1 2	输入：s = "([)]" 输出：false

5.2、解题思路

使用一个栈来解决这个问题

当遇到左括号类型的符号（包括小括号、中括号、大括号）时，直接压栈，遇到右括号类型的符号，就弹栈，需要此时弹出栈的左括号能与此时遇到的右括号能进行匹配，如果不匹配，那么直接返回 false ，如果要返回 true ，那么必须符合三个条件

栈为空
期间没有发生不匹配情况
遍历到字符串末尾

5.3、解题代码

public boolean isValid(String s) {
    if (s == null || s.length() == 0) return true;
    Stack<Character> stack = new Stack<>();
    char[] chars = s.toCharArray();
    // 循环遍历字符数组
    for (char c : chars) {
        if (isLeft(c)) {
            // 如果当前遍历到的元素为 左括号类型的字符，那么直接压栈
            stack.push(c);
        } else {
            // 如果当前遍历到的元素为右括号类型的字符，那么我们需要首先判断一下栈是否为空
            // 如果为空，直接返回 false，因为此时栈中没有左括号与其匹配，有多余的右括号
            if (stack.isEmpty()) {
                return false;
            }
            // 如果不为空，那么我们从栈中弹出一个左括号，然后判断左右括号是否相匹配
            char left = stack.pop();
            // 如果不匹配直接返回 false 
            if (!isValid(left, c)) {
                return false;
            }
        }
    }
    // 在循环结束后，我们还要判断栈是否为空，如果不为空，那么证明有多余的左括号，此时返回 false 
    if (stack.isEmpty()) {
        return true;
    }
    return false;
}

/**
 * 判断传入的符号是否为左括号类型的字符
 * @param ch
 * @return
 */
public boolean isLeft(char ch) {
    return ch == '(' || ch == '[' || ch == '{';
}

/**
 * 传入左右括号，判断这两个括号是否匹配
 * @param left 左括号
 * @param right 右括号
 * @return 是否匹配
 */
public boolean isValid(char left, char right) {
    return (left == '(' && right == ')') ||
           (left == '[' && right == ']') ||
           (left == '{' && right == '}');
}

6、合并 K 个有序节点

6.1、题目描述

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

6.2、解题思路

使用小顶堆来解决这个问题，小顶堆的加入和弹出操作的时间复杂度都是 O(logN)

将每个链表的头节点放入小顶堆
弹出当前小根堆中的元素，将这个节点加入到结果链表中，检查这个元素是从哪个链表中弹出来的，然后将该链表的下一个节点加入到小顶堆中

重复以上操作，直到小根堆中没有元素，结果链表就将所有链表中的元素有序地结合起来了

6.3、解题代码

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    // 创建一个小顶堆
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
    // 将当前链表列表中的所有头节点加入到小顶堆中
    for (int i = 0; i < lists.length; i++) {
        if (lists[i] != null) {
            minHeap.add(lists[i]);
        }
    }
    if (minHeap.isEmpty()) return null;
    // 结果链表中的头节点为当前小顶堆中的堆顶元素
    ListNode head = minHeap.poll();
    // 这个指针用来为结果链表添加元素
    ListNode pre = head;
    // 将小顶堆弹出的元素的下一个元素放入到小顶堆中
    if (pre.next != null) {
        minHeap.add(pre.next);
    }

    // 当堆不为空时进行循环
    while (!minHeap.isEmpty()) {
        // 将堆中的最小的元素弹出
        ListNode current = minHeap.poll();
        // 将弹出的元素加入到结果链表中
        pre.next = current;
        // 让 pre 指针后移
        pre = pre.next;
        // 将弹出元素的下一个节点加入到小顶堆中
        if (current.next != null) {
            minHeap.add(current.next);
        }
    }
    // 最后返回 head 即可
    return head;
}

7、接雨水

7.1、题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例一

1
2
3

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例二

1 2	输入：height = [4,2,0,3,2,5] 输出：9

7.2、解题思路

第一个柱子和最后一个柱子上一定没有水
i 位置的柱子最多能接多少水？这个值由三个因素决定，我们设这个值为 water [i]

高度数组 height 从 [0, i - 1] 的最大值
高度数组 height 从 [i + 1, height.length - 1] 的最大值
i 的最大值

water[i] = max {0, min{ max{height[0,i - 1]},max{height[i + 1,height.length - 1] }}}

min{ max{height[0,i - 1]},max{height[i + 1,height.length - 1] }} 可以这样理解，如果左边的高度最大值为 10 ，而右边高度最大值为 20 ，那么如果 i 位置有水，则水 + 柱子的高度一定小于等于左边的 10 （超过 10 水会从左边溜出去）
max {0, ...} 可以这样理解，如果 i 位置柱子的高度大于左右边界的值，由于水的量是 min{ max{height[0,i - 1]},max{height[i + 1,height.length - 1] }} - height[i] ，此时得到的水会是一个负数，所以当 i 位置的柱子高度大于左右边界值时，直接将当前柱子的水置为 0

从上面的分析中，我们需要知道数组中下标从 [0,i - 1] 的柱子高度最大值，同时知道数组中下标从 [i + 1,height.length - 1] 的柱子高度最大值。
使用双指针，初始化左指针 L 指向下标为 1 的数，初始化右指针 R 指向下标为 height.length - 2 的数（第一个柱子和最后一个柱子没有水）

记 L 左边边界最大值为 leftMax ，记 R 右边界的最大值为 rightMax ，则当

leftMax < rightMax 时，结算 L 位置的水量

这是因为 L 位置的左边界最大值是确定的，而 L 的右边界的最大值虽然是不确定的，但是 L 右边界的最大值不会小于 rightMax ，此时可以确定 L 位置的水

leftMax > rightMax 时，结算 R 位置的水量

同理，这是因为 R 位置的右边界的最大值已经确定，而 R 位置的左边界的最大值虽然是不确定的，但是 R 的左边界的最大值不会小于 leftMax ，此时可以确定 R 位置的水

leftMax == rightMax 时，此时可以结算 L 和 R 两个位置的值

左指针右移，右指针左移，当 L == R 时，循环结束，此时得到了所有位置上的水

7.3、解题代码

public int trap(int[] height) {
    // 如果 height 的长度小于 3 ，直接返回 0 ，此时存不住水
    if (height == null || height.length < 3) return 0;
    int len = height.length;
    // 左指针从 1 下标开始
    int leftPoint = 1;
    // 右指针从 len - 2 下标开始
    int rightPoint = len - 2;
    // 初始化左指针左边界最大值 max{height[0:leftPoint - 1]} 为数组第一个元素的值
    int leftMax = height[0];
    // 初始化右指针右边界最大值 max{height[rightPoint + 1:len - 1]} 为数组最后一个元素的值
    int rightMax = height[len - 1];
    // 创建一个变量来表示结果水量
    int water = 0;
    // 当两个指针重合时，也需要进行计算
    while (leftPoint <= rightPoint) {
        if (leftMax <= rightMax) {
            // 计算出当前 leftPoint 指向的位置上可以存的水
            water += Math.max(0, leftMax - height[leftPoint]);
            // 更新 L 左边界的最大高度，和当前指向的位置作比较
            leftMax = Math.max(leftMax, height[leftPoint]);
            // 左指针右移
            leftPoint++;
        } else {
            water += Math.max(0, rightMax - height[rightPoint]);
            rightMax = Math.max(rightMax, height[rightPoint]);
            rightPoint--;
        }
    }
    return water;
}

8、全排列

8.1、题目描述

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

1 2	输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

8.2、解题思路

这道题使用到了回溯算法，假设给定数组长度为 3 ，先确定第一个位置的数，然后在剩下的数中确定第二个位置的数，然后剩下的数就是第三个数，然后回过头来修改第二个位置的数，将第三个数与第二个数进行交换，获取到两个结果，后面再修改第一个数的值…

9、跳跃游戏

9.1、题目描述

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度，判断你是否能够到达最后一个下标。

示例 1：

1
2
3

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

1
2
3

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

9.2、解题思路

初始化一个变量 max 为 nums[0] ，这个变量记录了当前下标 i 能能够到达的最大位置
循环遍历数组，在进行遍历时需要判断当前能否到达 i 位置，如果 i > max 的值，那么说明此时无法到达 i 位置，直接返回 false 即可

比如说数组中第一个元素的值为 0 ，那么由于它无法到达下标为 1 的位置，所以直接返回 false 即可

在遍历时，如果发现在当前位置能到达的位置 > max 的位置，那么更新 max

假设现在有一个数组为 {3,1,1,1,0,0,0,1} ，那么初始化 max 为数组的第一个元素的值，即 3 ，代表在 0 位置最大能跳到下标为 3 的位置，当遍历到 i = 1 的元素时，发现此时在 i = 1 位置能到达的最大下标 positionI 为 2 ，此时由于 positionI <= max ，所以不更新
当 i = 2 时， positionI 为 3 ，此时仍然不更新，当 i = 3 时， positionI 为 4 ，此时更新 max 为 4 ，当 i = 4 时，此时 positionI 为 4 ，不更新 max ，当 i = 5时，由于 i > max ，此时证明无法到达 i == 5 的位置，此时直接返回 false 即可。

9.3、解题代码

public boolean canJump(int[] nums) {
    // 如果数组为空或者数组的长度小于等于 1 ，那么直接返回 true
    if (nums == null || nums.length <= 1) {
        return true;
    }
    // 初始化 max 为 数组第一个元素的值
    int max = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (i > max) {
            return false;
        } else {
            // nums[i] + i 代表从 i 位置能到达的最大位置
            max = Math.max(nums[i] + i, max);
        }
    }
    return true;
}

10、跳跃游戏 II

10.1、题目描述

给你一个非负整数数组 nums ，你最初位于数组的第一个位置，数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置，假设你总是可以到达数组的最后一个位置。
说明：你总是能到达数组的最后一个位置。

示例一：

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例二：

1 2	输入: nums = [2,3,0,1,4] 输出: 2

10.2、解题思路

与上一题不同，这道题的小人总是能到达终点，但本题要求小人在每次跳跃中做出选择，这个选择能让他到达终点所用的总次数最少，下面以数组 {2,3,1,1,4,3,2,5} 为例

小人永远从下标为 0 的位置起跳，此时我们标出在下标为 0 的位置可以到达的下标标记出来

小人在下标为 0 处能到达的下标范围为 [0, nums[0]]，然后我们遍历小人能到达的下标范围，更新小人下一步能到达的最大位置，小人下一步能到达的最大位置 newMax 的值为 max(i + nums[i])，在上面的例子中，第一步小人能到达的范围是 [0,2]

在下标为 0 - 2 的范围内，newMax 的值会被更新为 4 (1 + 3)，表示小人下一步能远能到达下标为 4 的位置

同理，查看在第三步能到达的最远位置，此时我们找到下标为 4 的位置，更新下一步能到达的最远位置为 8 (4 + 4)

由于此时 8 已经超过了数组的最后一个下标 7 ，所以我们直接返回 3

10.3、解题代码

public int jump(int[] nums) {
    // 定义三个变量
    //1 nextMax 存储下一步能到达的最远下标
    int nextMax = 0;
    //2 currentMax 存储当前步能到达的最远下标
    int currentMax = 0;
    //3 step 存储跳跃次数
    int step = 0;
    for(int i = 0;i < nums.length - 1;i++) {
        // 求出下一步能到达的最远下标的最大值
        nextMax = Math.max(nextMax, i + nums[i]);
        // 如果进入这个 if 块，证明小人已经来到了跳跃点，此时可以进行起跳
        if (i == currentMax) {
            step++;
            // 更新当前能到达的最远下标
            currentMax = nextMax;
        }
        // 如果更新当前步能到达的最远下标后，发现当前步覆盖的数组下标大于等于数组的最大下标，那么说明已经跳到了终点
        // 直接 break 即可
        if (currentMax >= nums.length - 1) {
            break;
        }
    }
    return step;
}

11、最长同值路径

11.1、题目描述

给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。
这条路径可以经过也可以不经过根节点，两个节点之间的路径长度由它们之间的边数表示

示例一：

输入：

输出：2

示例二：

输入：

输出：2

11.2、解题思路

使用二叉树的递归来解决这个问题，路径长度 = 路径上的节点数 - 1 ，所以这个问题可以等价于求路径上的节点数
以 root 为根节点的树，它的最长同值路径可能与 root 无关（路径不经过 root 节点，比如示例二）。

此时以 root 为根节点的树，它的最长同值路径要么是它左子树的最长同值路径，要么是它右子树的最长同值路径

以 root 为根节点的树，它的最长同值路径可能与 root 有关（路径经过 root）

当以 root 为根节点的树，它的最长同值路径长度只包括 root 时，此时结果为 1 ，这种情况下， root 和 root 左右节点的值均不相等。
当以 root 为根节点的树，它的最长同值路径只包括 root 和 root 的左/右子树时，此时只需要求出以 root 的左/右子节点的最长通知路径再 + 1 即可

这种情况下，root 的值需要和 root 的左/右子节点的值相等

当以 root 为根节点的树，它的最长同值路径既包括 root 的左子树，也包含 root 的右子树时，这个时候的结果为 root 左子树的最长同值路径 + root 右子树的最长同值路径 + 1

这种情况下，root 、root.left 和 root.right 三者的值必须相等。

上面六种情况中的最大值，就是我们要求的值

11.3、解题代码

包装一个静态内部类 Info ，它封装了左右子树需要向根节点返回的信息

路径必须包含 x 时，同值路径的最大距离，为属性 len

在最长同值路径包含 root 节点时，我们需要的属性为 len 属性，因为这个时候要求 root 子节点的值也必须为 root.val

路径不要求包含 x 时，同值路径的最大距离，为属性 max

当最长同值路径不包含 root 时，我们需要的属性为 max 属性，因为这个时候不要求 root 子节点的值为 root.val

private static class Info {
    public int len;
    public int max;
    public Info(int len, int max) {
        this.len = len;
        this.max = max;
    }
}

完整解题代码如下

public int longestUnivaluePath(TreeNode root) {
    Info result = process(root);
    int resultVal = Math.max(result.max, result.len);
    // 需要减一，因为算的是边
    return resultVal == 0 ? 0 : resultVal - 1;
}


public Info process(TreeNode node) {
    if (node == null) return new Info(0,0);
    TreeNode left = node.left;
    TreeNode right = node.right;
    Info leftInfo = process(left);
    Info rightInfo = process(right);
    int len = 1;
    // 如果左子树的值等于当前节点的值，就可以往左边探索
    if (left != null && left.val == node.val) {
        len = leftInfo.len + 1;
    }
    if (right != null && right.val == node.val) {
        len = Math.max(len, rightInfo.len + 1);
    }
    // 不比包含当前节点的同值路径长度最大值为左右子树的max的最大值
    int max = Math.max(Math.max(leftInfo.max, rightInfo.max), len);
    if (left != null && right != null && left.val == node.val && right.val == node.val) {
        max = Math.max(max, leftInfo.len + rightInfo.len + 1);
    }
    return new Info(len, max);
}
private static class Info {
    public int len;
    public int max;
    public Info(int len, int max) {
        this.len = len;
        this.max = max;
    }
}

12、字母异位词分组

12.1、题目描述

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母都恰好只用一次。

如果两个字符串中的字符一致且字符的出现次数一致，那么我们称这两个字符串为同形词，这道题要求我们将同形词放在一个 List 中
“abc”，”bca” 两个词互为同形词，而 “aabc” 和 “abc” 则不算。

12.2、解题思路

如何判断两个字符串是否为同形词？

将两个字符串排完序后使用 equals 判断即可

创建一个哈希表，**其中将排完序后的字符串作为 key **，将存放该种类同形词的 List 作为 value

循环遍历字符数组，对每个字符串的字符数组进行排序，然后将排好序的字符数组构造成字符串，将这个构造出来的字符串作为 key ，到哈希表中判断这个 key 是否存在，如果不存在，那么需要创建一个全新的列表，将当前遍历的字符串加入到列表中，然后将列表放回到哈希表中；如果存在，根据 key 拿出对应的列表，将当前遍历的字符串加入到列表中就可以了。

12.3、解题代码

public List<List<String>> groupAnagrams(String[] strs) {
    List<List<String>> result = new ArrayList<>();
    if (strs == null || strs.length == 0) return result;
    Map<String, List<String>> map = new HashMap<>();
    for (String str : strs) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        // 如果哈希表中没有过对应的key，那么需要创建一个列表，将当前 str 放入列表中，然后再将列表放入哈希表中
        if (!map.containsKey(key)) {
            List<String> value = new ArrayList<>();
            value.add(str);
            map.put(key, value);
        } else {
            // 否则直接加入到对应的列表中即可
            map.get(key).add(str);
        }
    }
    // 将哈希表中的所有 value 加入到结果集中
    result.addAll(map.values());
    return result;
}

13、Pow(x, n)

13.1、题目描述

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xⁿ），其中 x 为一个 Double 类型的数，n 是一个整数

13.2、解题思路

如何快速计算 xⁿ ？我们将 n 拆为二进制形式

假设我们现在要计算 a⁷⁵ ，75 = (1001011)₂ ，用一个变量来保存 a¹ ，记这个数为 t ，让 t 与自己相乘，将得到的数记为 t₁ ，t₂ = a² ，同理 t₃ = a⁴、t₃ = a⁸…t₆ = a⁶⁴，然后我们只需要将 1001011 中为 1 的那些数对应的值乘起来即可，即 a⁷⁵ = a⁶⁴ * a⁸ * a² * a¹ = t₆ * t₃ * t₁ * t

使用右移和 & 运算来简化运算

将次方数绝对值 pow 与 0 进行 & 运算，如果结果为 0 ，证明 pow 二进制形式的最后一位为 0 ，如果结果为 1 ，那么证明 pow 二进制形式的最后一位为 1
在每次进行 & 运算后，将 pow 右移一位，这样做既可以来控制循环次数（当 pow 为 0 时，循环结束），又可以遍历到 pow 二进制形式中的任何一个数

13.3、解题代码

public double myPow(double x, int n) {
    long pow = n;
    if (pow == 0) return 1D;
    boolean flag = pow < 0;
    pow = Math.abs(pow);
    // 使用一个变量 temp 来保存每一次的乘方数，即 a^1、a^2...，初始化为 a^1
    // 保存结果
    double result = 1;
    // 当 pow 不为 0 时循环
    while (pow != 0) {
        if ((pow & 1) != 0) {
            // 此时代表 pow 转换而成的二进制的位数为 1 ，此时需要进行相乘
            result *= x;
        }
        // 让 pow 右移，砍去最后一位，这也做有两个好处
        //1 通过 pow 的位数来控制循环
        //2 起到遍历 pow 二进制形式的作用
        pow >>= 1;
        x *= x;
    }
    return flag ? 1.0 / result : result;
}