算法笔记

0003.无重复字符的最长子串.md

关键字 : 字符串 重复 最长子串 滑动窗口

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

public int lengthOfLongestSubstring(String s) {
    if (s.length() <= 1){
        return s.length();
    }
    // 子串起点
    int startIndex = 0;
    // 记录最长子串长度
    int maxLen = 1;
    // 窗口右边界不断右移
    for (int endIndex = 1; endIndex < s.length(); endIndex++) {
        int tempLen = 1;
        // 每次右边界右移一位就需要判断窗口中是否存在当前右边界字符
        // 如果窗口中存在右边界字符, 则窗口左移动到窗口中重复元素的后一个位置
        for (int i = startIndex; i < endIndex ; i++) {
            if (s.charAt(i) == s.charAt(endIndex)){
                startIndex = i+1;
                break;
            }
        }
        // 更新答案
        maxLen = Math.max(maxLen, endIndex-startIndex+1);
    }
    return maxLen;
}

0005.最长回文子串.md

关键字 : 字符串 最长回文串 动归

给你一个字符串 s，找到 s 中最长的回文子串。

public String longestPalindrome(String s) {
    // 特殊用例判断
    int len = s.length();
    if (len < 2) {
        return s;
    }
    int maxLen = 1;
    int start = 0;
    // dp[i][j] 表示 s[i, j] 是否是回文串
    boolean[][] dp = new boolean[len][len];
    char[] charArray = s.toCharArray();
    // 单个的字符肯定是回文串
    for (int i = 0; i < len; i++) {
        dp[i][i] = true;
    }
    // 计算dp[i][j]
    for (int j = 1; j < len; j++) {
        for (int i = 0; i < j; i++) {
            if (charArray[i] != charArray[j]) {
                dp[i][j] = false;
            } else {
                if (j - i < 3) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }
            // 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此时记录回文长度和起始位置
            if (dp[i][j] && j - i + 1 > maxLen) {
                maxLen = j - i + 1;
                start = i;
            }
        }
    }
    return s.substring(start, start + maxLen);
}

0007.K个一组反转链表.md

关键字 : 链表 反转

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

// 使用一个固定长度的栈
public static ListNode reverseKGroup(ListNode head, int k) {
    ListNode p = head;
    // 栈的大小为k
    ArrayDeque<ListNode> stack = new ArrayDeque<>(k);
    ListNode pt = new ListNode(-1);
    ListNode ans = pt;
    // p指针往后走的过程中, 将节点入栈
    while (p != null){
        stack.addFirst(p);
        p = p.next;
        // 栈中有K个节点了
        if (stack.size() == k){
            // 对栈中节点进行反转
            // pt指向的是当前反转的最后一个节点
            while (!stack.isEmpty()){
                pt.next = stack.removeFirst();
                pt = pt.next;
            }
        }
    }
    // 最后栈中还有元素, 处理剩下的不满k个的节点
    // 此处处理方式是, 保留原链表顺序, 即将stack以队列方式出队
    while (!stack.isEmpty()){
        pt.next = stack.removeLast();
        pt = pt.next;
    }
    pt.next = null;
    return ans.next;
}

0009. 数组中的第K个最大元素.md

关键字 : 数组 第k大 快排 堆排序 优先队列

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

方法一

// 使用优先队列(默认底层实现为最小堆)
public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int i = 0; i < k; i++) {
        pq.add(nums[i]);
    }
    for (int i = k; i < nums.length; i++) {
        if (!pq.isEmpty() && nums[i] > pq.peek()){
            pq.remove();
            pq.add(nums[i]);
        }
    }
    return pq.peek();
}

方法二

// 利用快排过程
private int k;
private int ans;
public int findKthLargest1(int[] nums, int k) {
    this.k = k;
    sort(nums, 0, nums.length-1);
    return ans;
}
public void sort(int[] arr, int left, int right){
    if (left >= right) return;
    int p = partition(arr, left, right);
    // 第k大的对应第arr.length - k小的(从0开始算)
    if (p == arr.length - k){
        ans = arr[p];
        return;
    }
    // 左边排序
    sort(arr, left, p-1);
    // 右边排序
    sort(arr, p+1, right);
}
private int partition(int[] arr, int left, int right) {
    // 优化点 : 随机选取枢轴元素. 将选中的枢轴元素交换到最左边
    int p = left + (new Random()).nextInt(right-left+1);
    swap(arr, left, p);
    // 双指针移动
    int i = left+1, j = right;
    while (true){
        // 从左往右找到第一个比枢纽元素大的, 注意循环条件
        while (i <= j && arr[i] < arr[left])
            i++;
        // 从右往左找到第一个比枢纽元素小的,注意循环条件
        while (i <= j && arr[j] > arr[left])
            j--;
        // 循环终止条件
        if (i >= j) break;
        // 交换两个位置的元素
        swap(arr, i, j);
        // i往后走一步, j往前走一步, 继续循环
        i++;
        j--;
    }
    // 最后交换枢纽元素和j停留的位置
    swap(arr, left, j);
    return j;
}
private void swap(int[] arr, int i, int j){
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

0015.三数之和.md

关键字 : 数组 三数之和 排序 双指针

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

注意：答案中不可以包含重复答案。

思路 : 排序+双指针

时间复杂度 O(n^2)

public static List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    // 先排序
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 1; i++) {
        // 如果首元素大于0, 则后面不可能找出两个数的和=-首元素
        if(nums[i] > 0) return ans;
        // 跳过重复解
        if (i>0 && nums[i] == nums[i-1]){
            continue;
        }
        int l = i+1;
        int r = nums.length-1;
        while (l<r){
            if (nums[l] + nums[r] + nums[i] < 0){
                ++l;
            }else if (nums[l] + nums[r] + nums[i] > 0){
                --r;
            }else {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(nums[i]);
                list.add(nums[l]);
                list.add(nums[r]);
                ans.add(list);
                // 跳过重复解
                while (l<r && nums[l] == nums[l+1]){
                    ++l;
                }
                ++l;
                while (l<r && nums[r] == nums[r-1]){
                    --r;
                }
                --r;
            }
        }
    }
    return ans;
}

附赠两数之和

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

0031.下一个排列.md

关键字 下一个 字典序

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须 原地 修改，只允许使用额外常数空间。

示例

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

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

class Solution{
    public static void nextPermutation(int[] nums) {
        int n = nums.length;
        // 从后往前找第一个变小的数字
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i+1]){
            i--;
        }
        // 除了while循环，有两种情况，一是i==-1了， 二是找到了num[i] < num[i+1]
        if (i >= 0){
            // 从后往前找第一个比num[i]大的数，与num[i]交换
            for (int j = n-1; j > i; j--){
                if (nums[j] > nums[i]){
                    // 找到了
                    swap(nums, i, j);
                    break;
                }
            }
        }
        // 交换完后，需要把后面一部分整体反转，使后面一部分是最小的
        reverse(nums, i+1, n-1);
    }
    private static void swap(int[] nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
    // 反转数组区间[lo, hi]
    private static void reverse(int[] nums, int lo, int hi){
        while (lo < hi){
            swap(nums, lo++, hi--);
        }
    }
}

0032. 最长有效括号.md

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

思路 : 动态规划

我们定义 dp[_i] 表示以下标 _i* 字符结尾的最长有效括号的长度。因此我们知道以 ‘(’ 结尾的子串对应的 dp 值必定为 0 ，我们只需要求解 ‘)’ 在 dp 数组中对应位置的值。

我们从前往后遍历字符串求解 dp 值:

当s[i] = ‘)’ 的时候, 有两种情况 :

1. s[i - 1] =‘(’ : 这种情况我们可以推出 : dp[i]=dp[i−2]+2
2. s[i - 1] =‘)’ : 这种情况时又分两种情况
   1. s[ i - dp[i-1] - 1 ] = ‘(‘ : 这种情况我们可以推出 : dp[i] = dp[i−1] +2 + dp[ i− dp[i−1] − 2 ]
   2. s[ i - dp[i-1] - 1 ] = ‘)’ : dp[i] = 0

public static int longestValidParentheses(String s) {
    int[] dp = new int[s.length()];
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '('){
            dp[i] = 0;
        }else { // ')'
            if (i > 0 && s.charAt(i-1) == '('){
                if (i-2>=0)
                    dp[i] = dp[i-2] + 2;
                else
                    dp[i] =  2;
            }else if (i > 0 && s.charAt(i-1) == ')'){   // ....))
                // 判断 i-dp[i-1]-1 是否是'('
                if (i-dp[i-1]-1 >= 0 && s.charAt(i-dp[i-1]-1) == '('){
                    if (i-dp[i-1]-2 >= 0)
                        dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2];
                    else
                        dp[i] = dp[i-1] + 2;
                }else {
                    dp[i] = 0;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < s.length(); i++) {
        ans = Math.max(ans, dp[i]);
    }
    return ans;
}

0033. 搜索旋转排序数组.md

关键字 : 旋转数组 有序数组 二分查找

整数数组 nums 按升序排列，数组中的值 互不相同 。nums 在预先未知的某个下标 k上进行了 旋转.

例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = (right - left) / 2 + left;
        // 找到直接返回
        if (nums[mid] == target) {
            return mid;
        }
        // 如果nums[mid] >= nums[left], 说明mid在旋转点的左边
        if (nums[mid] >= nums[left]) {
            if (nums[mid] > target && target >= nums[left]) {    // 去左边找
                right = mid - 1;
            } else {    // 去右边找
                left = mid + 1;
            }
        } else {    // 说明mid在旋转点的右边
            if (nums[mid] < target && target <= nums[right]) {    // 去右边找
                left = mid + 1;
            } else {    // 去左边找
                right = mid - 1;
            }
        }
    }
    return -1;
}

0041.缺失的第一个正整数.md

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数(严格大于0的数)。

实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

方法一 : 排序 + 二分查找

时间复杂度 O(n log n) + O(log n) = O(n log n) 空间复杂度 O(1)

代码略

方法二 : 将数字交换到它应该在的位置上去

时间复杂度为 O(n) 空间复杂度 O(1)

将 num[i] 移动到原数组下标为 num[i]-1 的地方去

public int firstMissingPositive(int[] nums) {
    int len = nums.length;
    // 循环一遍, 交换数字到应该在的位置
    for (int i = 0; i < len; i++) {
        while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
            // 满足在指定范围内、并且没有放在正确的位置上，才交换
            // 例如：数值 3 应该放在索引 2 的位置上
            swap(nums, nums[i] - 1, i);
        }
    }
    // 遍历一遍, 找到第一个位置不符合的元素返回
    for (int i = 0; i < len; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    // 上面for循环没有返回, 则说明缺失的是最大的那个数 即数组长度 + 1
    return len + 1;
}
private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[index2] = temp;
}

0042. 接雨水.md

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

输入：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 个单位的雨水（蓝色部分表示雨水）。

思路 : 对于每一列上积攒的雨水量的计算方法是 : 找出当前列左边的最高处, 和右边的最高处, 取二者较小者就是水高线

因此, 方法一就是暴力求解, 对于每一个格子(列), 分别找它左边右边的最高点, 然后减去它自身的高度, 就是当前格子里的积水量, 然后累加在一起即可.

方法一 : 暴力解法

public int trap1(int[] height) {
    int ans = 0;
    for (int i = 0; i < height.length-1; i++) {
        int leftMaxHi = findMax(height, 0, i);
        int rightMaxHi = findMax(height, i+1, height.length-1);
        int cur = Math.min(leftMaxHi, rightMaxHi) - height[i];
        if (cur>0) ans += cur;
    }
    return ans;
}
// 在[left, right]区间找最大值
private int findMax(int[] arr, int left, int right) {
    int ret = arr[left];
    while (left <= right){
        ret = Math.max(ret, arr[left]);
        left++;
    }
    return ret;
}

方法二 : 动归

思路与方法一一样, 只是用了两个辅助数组分别记录num[i]左右最高点

public int trap2(int[] height) {
    int n = height.length; if (n <= 1) return 0;
    int[] leftMax = new int[n];
    int[] rightMax = new int[n];
    // 记录num[i]左边最大值(包含i)
    leftMax[0] = height[0];
    for (int i = 1; i < n; i++) {
        leftMax[i] = Math.max(leftMax[i-1], height[i]);
    }
    // 记录num[i]右边最大值(包含i)
    rightMax[n -1] = height[n -1];
    for (int i = n -2; i >= 0; i--){
        rightMax[i] = Math.max(rightMax[i+1], height[i]);
    }
    // 求结果
    int ans = 0;
    for (int i = 0; i < n - 1; i++) {
        ans += Math.min(leftMax[i], rightMax[i]) - height[i];
    }
    return ans;
}

0046. 全排列.md

关键字 : 数组 字符串 全排列 回溯 深度优先

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

注 : 如果给定一个字符串, 求字符全排列, 则将字符串转成char数组

public List<List<Integer>> permute(int[] nums) {
    int len = nums.length;
    boolean[] used = new boolean[len];
    List<List<Integer>> ans = new ArrayList<>();
    dfs(nums, used, len, 0, ans, new ArrayList<>());
    return ans;
}
private void dfs(int[] nums, boolean[] used, int len, int depth, List<List<Integer>> ans, List<Integer> list){
    if (len == depth){
        ans.add(new ArrayList<>(list));
        return;
    }
    for (int i = 0; i < len; i++) {
        if (!used[i]){
            list.add(nums[i]);
            used[i] = true;
            dfs(nums, used, len, depth+1, ans, list);
            used[i] = false;
            list.remove(Integer.valueOf(nums[i]));
        }
    }
}

0053. 最大子序和.md

关键字 : 数组 最大子序列和 连续子序列和 动归

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

public int maxSubArray(int[] nums) {
    int maxSum = nums[0];
    // 记录以num[i]结尾的最大子序列和
    for (int i = 1; i < nums.length; i++) {
        // 如果以nums[i-1]结尾的最大子序列和>0, 则以nums[i]结尾的最大子序列和累加上上一个, 否则就是它本身
        if (nums[i-1] > 0){
            nums[i] += nums[i-1];
        }
        // 更新答案
        if (nums[i] > maxSum){
            maxSum = nums[i];
        }
    }
    return maxSum;
}

或者 :

f(i)=max{f(i−1)+nums[i],nums[i]}

public int maxSubArray(int[] nums) {
    int pre = 0, maxAns = nums[0];
    for (int x : nums) {
        pre = Math.max(pre + x, x);
        maxAns = Math.max(maxAns, pre);
    }
    return maxAns;
}

0054. 螺旋矩阵.md

关键字 : 螺旋矩阵 顺时针打印 二维数组 模拟

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

思路 : 一层一层从外到里打印, 使用四个变量 r1, r2, c1, c2 分别存储上下左右边界值，从而定义当前最外层。

注意只有在 r1 != r2 时才打印最下一行，也就是在当前最外层的行数大于 1 时才打印最下一行

public List<Integer> printMatrix(int[][] matrix) {
    List<Integer> ans = new ArrayList<>();
    int r1 = 0, c1 = 0;
    int r2 = matrix.length - 1, c2 = matrix[0].length - 1;
    while (r1 <= r2 && c1 <= c2) {
        // 上
        for (int i = c1; i <= c2; i++)
            ans.add(matrix[r1][i]);
        // 右
        for (int i = r1 + 1; i <= r2; i++)
            ans.add(matrix[i][c2]);
        if (r1 != r2)
            // 下
            for (int i = c2 - 1; i >= c1; i--)
                ans.add(matrix[r2][i]);
        if (c1 != c2)
            // 左
            for (int i = r2 - 1; i > r1; i--)
                ans.add(matrix[i][c1]);
        r1++; r2--; c1++; c2--;
    }
    return ans;
}

0056.合并区间.md

关键词 : 数组 合并 区间合并 排序

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]

public int[][] merge(int[][] intervals) {
    if (intervals.length == 0) return new int[0][2];
    // 按照区间第一位排序
    Arrays.sort(intervals, (interval1, interval2) -> interval1[0] - interval2[0]);
    List<int[]> ans = new ArrayList<int[]>();
    for (int[] interval : intervals) {
        int L = interval[0], R = interval[1];
        // 列表为空或者列表中最后一个区间右边界小于当前区间左边界，则表示不能与列表中的区间合并，新添加一个区间
        if (ans.size() == 0 || ans.get(ans.size() - 1)[1] < L) {
            ans.add(new int[]{L, R});
        } else {    // 否则当前区间可以与列表中最后一个区间合并
            ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], R);
        }
    }
    return ans.toArray(new int[ans.size()][]);
}

0069.x的平方根.md

关键词 : 开方 平方根 二分

实现 sqrt(int x)

public int mySqrt(int x) {
    int l = 0, r = x, ans = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if ((long) mid * mid <= x) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}

0076.最小覆盖子串.md

关键词 : 字符串 子串 最短覆盖子串 滑动窗口

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

public String minWindow(String s, String t) {
    if (s.length() == 0 || t.length() == 0 || s.length() < t.length()){
        return "";
    }
    int[] need = new int[128];
    //记录需要的字符的个数
    for (int i = 0; i < t.length(); i++) {
        need[t.charAt(i)]++;
    }
    //l是当前左边界，r是当前右边界，size记录窗口大小，count是需求的字符个数，start是最小覆盖串开始的index
    int left = 0, right = 0, windowSize = s.length()+1, needCharCount = t.length(), start = 0;
    //遍历所有字符
    while (right < s.length()) {
        char c = s.charAt(right);
        if (need[c] > 0) {  //需要字符c
            needCharCount--;
        }
        // 进入窗口的所有字符都加入need数组，如果need[index]<0 , 说明是不需要的冗余字符
        need[c]--;//把右边的字符加入窗口
        if (needCharCount == 0) {//窗口中已经包含所有字符
            while (left < right && need[s.charAt(left)] < 0) {
                // 只要遇到冗余字符，则将该字符从窗口中移除，并且left++
                need[s.charAt(left)]++;//释放右边移动出窗口的字符
                left++;//指针右移
            }
            // 出了while循环表示窗口无法再缩小了，此时更新答案
            if (right - left + 1 < windowSize) {//不能右移时候挑战最小窗口大小，更新最小窗口开始的start
                windowSize = right - left + 1;
                start = left;//记录下最小值时候的开始位置，最后返回覆盖串时候会用到
            }
            //更新完答案后，将left继续向左移动一位，使得窗口不满足要求，需要继续right右移寻找新的答案
            need[s.charAt(left)]++;
            left++;
            needCharCount++;
        }
        right++;
    }
    return windowSize == s.length()+1 ? "" : s.substring(start, start + windowSize);
}

0093. 复原 IP 地址.md

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

输入：s = "0000"
输出：["0.0.0.0"]

// 回溯
private List<String> ans = new ArrayList<>();
public List<String> isIp(String s) {
    int n = s.length();
    if (n > 12 || n < 4) return ans;
    // 队列
    Deque<String> path = new ArrayDeque<>(4);
    dfs(s, 0, 4, path);
    return ans;
}
private void dfs(String s, int start, int segment, Deque<String> path) {
    int n = s.length();
    if (start == n && segment == 0) {
        StringBuilder sb = new StringBuilder();
        for (String str : path) {
            sb.append(str).append(".");
        }
        sb.deleteCharAt(sb.length()-1);
        ans.add(sb.toString());
        return ;
    }
    // 最多3位组成一个段， i位当前段的尾部下标
    for (int i=start;i<start+3;i++) {
        if (i >= n) break;
        // 判断剩下的字符串长度是否比要组成的段的最大长度还长，如果是，则当前答案无效，继续下一次循环
        if (segment * 3 < n - i) continue;
        if (isIpSegment(s, start, i)) {
            // 当前段有效，加入队列
            String currentSegment = s.substring(start, i + 1);
            path.addLast(currentSegment);
            // 关键， 下一段从下标为i+1的位置开始，总段数-1
            dfs(s, i + 1, segment - 1, path);
            // 回溯
            path.removeLast();
        }
    }
}
private boolean isIpSegment(String s, int left, int right) {
    // 如果字符串长度大于1， 且第一位是0，则不可为ip段
    if (right - left + 1 > 1 && s.charAt(left) == '0') return false;
    int res = Integer.parseInt(s.substring(left, right+1));
    return res >= 0 && res <= 255;
}

0098.验证是否为二叉搜索树.md

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

中序遍历即可

private int preNum = Integer.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
    if (root == null) return true;
    boolean left = isValidBST(root.left);
    if (!left){
        return false;
    }
    if (root.val <= preNum){    // 不满足中序有序规律
        return false;
    }
    preNum = root.val;
    return isValidBST(root.right);
}

0101.对称二叉树.md

关键词 : 二叉树 对称

给定一个二叉树，检查它是否是镜像对称的。

如

    1
   / \
  2   2
 / \ / \
3  4 4  3

public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    return isSymmetric(root.left, root.right);
}
public boolean isSymmetric(TreeNode node1, TreeNode node2) {
    if (node1 == null && node2 == null) return true;
    if (node1 == null || node2 == null) return false;
    // 先序判断值相等
    if (node1.val == node2.val){
        // 然后判断node1的左孩子是否和node2的右孩子对称
        boolean f1 = isSymmetric(node1.left, node2.right);
        // 然后判断node1的右孩子是否和node2的左孩子对称
        boolean f2 = isSymmetric(node1.right, node2.left);
        return f1 && f2;
    }else 
        return false;
}

0104. 二叉树的最大深度.md

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

思路 : DFS, 后序递归

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    if (root.left == null && root.right == null )
        return 1;
    else if (root.left == null){
        // 左树为空, 则返回右树高度+1
        return maxDepth(root.right)+1;
    }else if (root.right == null){
        // 右树为空, 则返回左树高度+1
        return maxDepth(root.left)+1;
    }else {
        // 去左右子树高度最大值+1
        return Math.max(maxDepth(root.right)+1, maxDepth(root.left)+1);
    }
}

0105. 从前序与中序遍历序列构造二叉树.md

关键词 : 二叉树 重建 前序中序

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

// 缓存中序遍历数组每个值对应的索引
private Map<Integer, Integer> indexForInOrders = new HashMap<>();
public TreeNode buildTree(int[] pre, int[] in) {
    // 存中序节点索引
    for (int i = 0; i < in.length; i++)
        indexForInOrders.put(in[i], i);
    return buildTree(pre, 0, pre.length - 1, 0);
}
// 只需要前序，前序中当前子树的左右范围，中序左右范围
private TreeNode buildTree(int[] pre, int preL, int preR, int inL) {
    if (preL > preR)
        return null;
    // 当前子树的根
    TreeNode root = new TreeNode(pre[preL]);
    // 从中序中找出根的位置
    int inIndex = indexForInOrders.get(root.val);
    // 当前子树中左子树的节点数量
    int leftTreeSize = inIndex - inL;
    // 递归
    root.left = buildTree(pre, preL + 1, preL + leftTreeSize, inL);
    root.right = buildTree(pre, preL + leftTreeSize + 1, preR, inL + leftTreeSize + 1);
    return root;
}

0106. 从中序与后序遍历序列构造二叉树.md

关键词 : 二叉树 重建 后序中序

根据一棵树的中序遍历与后序遍历构造二叉树。

// 缓存中序遍历数组每个值对应的索引
HashMap<Integer,Integer> indexForInOrders = new HashMap<>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
    // 存中序节点索引
    for(int i = 0;i < inorder.length; i++)
        indexForInOrders.put(inorder[i], i);
    return buildTree(postorder ,0, 0, postorder.length - 1);
}
public TreeNode buildTree(int[] postorder, int inL, int postL, int postR) {
    if(postR < postL) return null;
    // 当前子树的根
    TreeNode root = new TreeNode(postorder[postR]);
    // 从中序中找出根的位置
    int inIndex = indexForInOrders.get(root.val);
    root.left = buildTree(postorder ,inL, postL, postL + inIndex - inL - 1);
    root.right = buildTree(postorder ,inIndex + 1, postL + inIndex - inL, postR - 1);
    return root;
}

0110. 平衡二叉树.md

给定一个二叉树，判断它是否是高度平衡的二叉树。

思路 : 后序递归

public boolean isBalanced(TreeNode root) {
    int i = treeHeight(root);
    return i != -1;
}
private int treeHeight(TreeNode node){
    if (node == null) return 0;
    // 计算左子树的高度
    int leftHeight = treeHeight(node.left);
    // 如果左子树高度为-1, 说明左子树不平衡
    if (leftHeight == -1) return -1;
    // 计算右子树的高度
    int rightHeight = treeHeight(node.right);
    // 如果右子树高度为-1, 说明右子树不平衡
    if (rightHeight == -1) return -1;
    // 如果左子树右子树的高度差不超过1, 则返回最大高度, 超过1则返回-1表示不平衡
    return Math.abs(leftHeight-rightHeight)<=1 ? Math.max(leftHeight, rightHeight)+1 : -1;
}

0111. 二叉树的最小深度.md

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

// BFS
public int minDepth(TreeNode root) {
    if (root == null) return 0;
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.addLast(root);
    // 初试深度设为1
    int depth = 1;
    while (!queue.isEmpty()){
        // 当前所在层有多少个节点
        int curLevelNodeNum = queue.size();;
        for (int i = 0; i < curLevelNodeNum; i++) {    // 将一层节点全部出完之后, 深度+1
            TreeNode node = queue.removeFirst();
            if (node.left == null && node.right == null) return depth;
            if (node.left != null) queue.addLast(node.left);
            if (node.right != null) queue.addLast(node.right);
        }
        // 出完一层, 深度++
        depth++;
    }
    return depth;
}

0112.路径总和.md

关键字 : 二叉树 路径总和 递归

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。

public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) {
        return false;
    }
    if (root.left == null && root.right == null) {
        return sum == root.val;
    }
    return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}

扩展, 找出所有路径总和=targetSum 的路径

List<List<Integer>> ans = new ArrayList<>();
Deque<Integer> path = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    dfs(root, targetSum);
    return ans;
}
public void dfs(TreeNode root, int targetSum) {
    if (root == null) {
        return;
    }
    path.addLast(root.val);
    targetSum -= root.val;    // targetSum - 当前节点值
    // 到达叶子结点, 且targetSum减到0, 添加一个答案
    if (root.left == null && root.right == null && targetSum == 0) {
        ans.add(new ArrayList<Integer>(path));
    }
    dfs(root.left, targetSum);
    dfs(root.right, targetSum);
    // 
    path.removeLast();
}