[数据结构与算法]Leetcode 第91，93，95，102，107，109，128，130，131，139题(Java解法)

第91题 解码方法

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，“11106” 可以映射为：
“AAJF” ，将消息分组为 (1 1 10 6)
“KJF” ，将消息分组为 (11 10 6)
注意，消息不能分组为 (1 11 06) ，因为 “06” 不能映射为 “F” ，这是由于 “6” 和 “06” 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。

示例 1：

解释：它可以解码为 “AB”（1 2）或者 “L”（12）。

示例 2：

解释：它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

示例 3：

解释：没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 ‘J’ -> “10” 和 ‘T’-> “20” 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。

解题思路

本题使用动态规划求解，每一个位置处的解码方法有2种情况，一是单个数字组成一个字母，二是；两个数字组成一个字母，所以当前位置的解码方法取决去前两个位置的解码方法之和，因此f[i]=f[i-1]+f[i-2]，只要满足数字在1-26之间，就可认为是一个字母。

代码

// 解码方法：动态规划
class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        // a = f[i-2], b = f[i-1], c=f[i]
        int a = 0, b = 1, c = 0;
        for (int i = 1; i <= n; ++i) {
            c = 0;//起始方法数设为0
            if (s.charAt(i - 1) != '0') {//第一种情况，一个数字组成解码
                c += b;
            }
            if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {//第二种情况，两个数字组成解码，当字符串i-2处的值不为0，并且i前面两个位置组成的数字小于26，则认定当前可以由2位数字组成解码
                c += a;
            }
            a = b;
            b = c;
        }//改变新的位置的解码方法数
        return c;
    }
}

时间复杂度为O(n)，n为字符串长度
空间复杂度为O(1)

第93题 复原 IP 地址

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。
例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。

示例 1：

示例 2：

示例 3：

示例 4：

示例 5：

解题思路

用回溯法，如果找到了4段IP地址且遍历完了数组，则找到了一个答案，如果找到4段IP地址，但是还没有遍历完数组，则重新找，当没有找到4段时，如果当前遍历到了单个0，则将0单独作为一段，否则判断当前数字是否超出范围，没有则加入一段。

代码

// 复原 IP 地址：回溯
class Solution {
    static final int SEG_COUNT = 4;//4段
    List<String> ans = new ArrayList<String>();
    int[] segments = new int[SEG_COUNT];
    public List<String> restoreIpAddresses(String s) {
        segments = new int[SEG_COUNT];//每一段
        dfs(s, 0, 0);//dfs搜索
        return ans;
    }
    public void dfs(String s, int segId, int segStart) {
        // 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
        if (segId == SEG_COUNT) {//找到4段
            if (segStart == s.length()) {//长度刚好等于字符串长度
                StringBuffer ipAddr = new StringBuffer();
                for (int i = 0; i < SEG_COUNT; ++i) {
                    ipAddr.append(segments[i]);//加入每一段
                    if (i != SEG_COUNT - 1) {
                        ipAddr.append('.');//除最后一个位置，其余段之间加入.
                    }
                }
                ans.add(ipAddr.toString());//将结果加入结果数组中
            }
            return;
        }
        // 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
        if (segStart == s.length()) {//没有找到4段。但是长度已经遍历完，则重新开始
            return;
        }
        // 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
        if (s.charAt(segStart) == '0') {//如果当前遍历的一段结果为0，则直接将0单独作为一段
            segments[segId] = 0;
            dfs(s, segId + 1, segStart + 1);//找下一段，以及下一个字符
        }
        // 一般情况，枚举每一种可能性并递归
        int addr = 0;
        for (int segEnd = segStart; segEnd < s.length(); ++segEnd) {
            addr = addr * 10 + (s.charAt(segEnd) - '0');
            if (addr > 0 && addr <= 0xFF) {
                segments[segId] = addr;//加入一段
                dfs(s, segId + 1, segEnd + 1);//找下一段以及下一个字符
            } else {
                break;//超出范围
            }
        }
    }
}

时间复杂度为O(3^SEG_COUNT×∣s∣)，s为字符串长度，SEG_COUNT为4
空间复杂度为O(SEG_COUNT)

第95题 不同的二叉搜索树 II

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案

示例 1：

示例 2：

解题思路

先找出全是左子树的一个集合以及全是右子树的一个集合，然后从左子树和右子树各选出一个子树拼接成根节点。

代码

// 不同的二叉搜索树 II：回溯
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new LinkedList<TreeNode>();
        }
        return generateTrees(1, n);//开始为1，结束为n
    }
    public List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> allTrees = new LinkedList<TreeNode>();
        if (start > end) {//如果开始大于结束，则加入null,并返回结果
            allTrees.add(null);
            return allTrees;
        }
        // 枚举可行根节点
        for (int i = start; i <= end; i++) {
            // 获得所有可行的左子树集合
            List<TreeNode> leftTrees = generateTrees(start, i - 1);
            // 获得所有可行的右子树集合
            List<TreeNode> rightTrees = generateTrees(i + 1, end);
            // 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    TreeNode currTree = new TreeNode(i);
                    currTree.left = left;
                    currTree.right = right;
                    allTrees.add(currTree);
                }
            }
        }
        return allTrees;
    }
}

时间复杂度为O(4^n/n(1/2))，n为数字大小
空间复杂度为O(4^n/n(1/2))

第102题 二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例 1：

解题思路

使用BFS，即队列，先将根节点入队，然后将根节点出队，加入当前层级，当前层级大小等于当前队列的长度，每次出队一个节点，都将该节点值加入当前层级的结果中，然后将它的左右子节点加入队列，直到遍历完所有节点

代码

// 二叉树的层序遍历：BFS
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();//建立队列
        queue.offer(root);//加入根节点
        while (!queue.isEmpty()) {//队列不为空时
            List<Integer> level = new ArrayList<Integer>();//建立层级
            int currentLevelSize = queue.size();//队列长度
            for (int i = 1; i <= currentLevelSize; ++i) {//遍历当前层级长度
                TreeNode node = queue.poll();//出队
                level.add(node.val);//层级加入出队的值
                if (node.left != null) {//加入左右节点的值
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);//将当前层级的值加入结果
        }      
        return ret;
    }
}

时间复杂度为O(n),n为节点数
空间复杂度为O(n)

第107题 二叉树的层序遍历 II

给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例 1：

解题思路

本题和102题类似，只是在将每层的结果加入数组中时，有所不同，102题是加入数组后面，而本题是加入到数组前面。

代码

// 二叉树的层序遍历 II：BFS
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();
        if (root == null) {
            return levelOrder;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                TreeNode left = node.left, right = node.right;
                if (left != null) {
                    queue.offer(left);
                }
                if (right != null) {
                    queue.offer(right);
                }
            }
            levelOrder.add(0, level);//将当前层的结果添加到数组首部
        }
        return levelOrder;
    }
}

时间复杂度为O(ln)，n为节点数
空间复杂度为O(n)

第109题 有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例 1：

解题思路

采用分治算法，每次将长度分成左右两部分，将中间数做为根节点，不断找新的左右子树。

代码

// 有序链表转换二叉搜索树：分治
class Solution {
    ListNode globalHead;
    public TreeNode sortedListToBST(ListNode head) {
        globalHead = head;
        int length = getLength(head);
        return buildTree(0, length - 1);//分治算法
    }
    public int getLength(ListNode head) {//获取链表长度
        int ret = 0;
        while (head != null) {
            ++ret;
            head = head.next;
        }
        return ret;
    }
    public TreeNode buildTree(int left, int right) {
        if (left > right) {
            return null;
        }
        int mid = (left + right + 1) / 2;//找中间数
        TreeNode root = new TreeNode();
        root.left = buildTree(left, mid - 1);//分治成左右两边，每次将中间节点作为根节点
        root.val = globalHead.val;
        globalHead = globalHead.next;
        root.right = buildTree(mid + 1, right);
        return root;
    }
}

时间复杂度为O(n),n为链表长度
空间复杂度为O(log n)

第128题 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

示例 1：

解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

解题思路

代码

// 最长连续序列：哈希表
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> num_set = new HashSet<Integer>();
        for (int num : nums) {
            num_set.add(num);
        }//将数字加入到哈希表中
        int longestStreak = 0;
        for (int num : num_set) {//遍历哈希表
            if (!num_set.contains(num - 1)) {//判断当前数字的前一数字是否存在
                int currentNum = num;//不存在的话就将currentNum设为num
                int currentStreak = 1;//将当前连续数设为1
                while (num_set.contains(currentNum + 1)) {//然后一直查是否存在后一数字，存在就将currentNum设为下一数字，将当前连续数加1
                    currentNum += 1;
                    currentStreak += 1;
                }
                longestStreak = Math.max(longestStreak, currentStreak);//每一次都查询最大连续数
            }
        }
        return longestStreak;
    }
}

时间复杂度为O(n),n为数组的长度
空间复杂度为O(n)

第130题 被围绕的区域

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

示例 1：

解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

解题思路

本题用DFS搜索四条边上是否有O，有则标记为A，然后在标记为A的四周找是否有O的，有则也标记为A，然后重新遍历整个二维数组，如果碰到O，则标记为X，遇到A则标记为O。

代码

// 被围绕的区域：DFS
class Solution {
    int n, m;
    public void solve(char[][] board) {
        n = board.length;
        if (n == 0) {
            return;
        }
        m = board[0].length;
        for (int i = 0; i < n; i++) {//深度搜索第一列和最后一列
            dfs(board, i, 0);
            dfs(board, i, m - 1);
        }
        for (int i = 1; i < m - 1; i++) {//深度搜索第一行和最后一行
            dfs(board, 0, i);
            dfs(board, n - 1, i);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'A') {//标记为A，代表未被包围，则将A再变成O
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {//如果不是A二是O则代表被包围了，标记为X
                    board[i][j] = 'X';
                }
            }
        }
    }
    public void dfs(char[][] board, int x, int y) {//深度搜索4条边是否有O，有则标记为A，然后如果等于O，则找该位置的四周是否有O，有则也标记为O，这里的意思是要排除边上有位置为O，且该位置的四周有O的情况
        if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O') {
            return;
        }
        board[x][y] = 'A';
        dfs(board, x + 1, y);
        dfs(board, x - 1, y);
        dfs(board, x, y + 1);
        dfs(board, x, y - 1);//搜索四个方向
    }
}

时间复杂度为O(mn),m，n为数组的行和列
空间复杂度为O(mn)

第131题 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。

示例 1：

示例 2：

解题思路

利用回溯算法，不断查找是否为回文串，然后将子串加入ans中，直到遍历完字符串，如果都满足，则将ans加入到ret中，然后继续从头遍历，中间加入了剪枝操作，避免出现相同结果。

代码

// 分割回文串：回溯
class Solution {
    boolean[][] f;
    List<List<String>> ret = new ArrayList<List<String>>();//结果数组
    List<String> ans = new ArrayList<String>();//回文子串数组
    int n;
    public List<List<String>> partition(String s) {
        n = s.length();//数组长度
        f = new boolean[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(f[i], true);//数组加入单个字符
        }
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                f[i][j] = (s.charAt(i) == s.charAt(j)) && f[i + 1][j - 1];//如果数组前后字符相等且后续字符不为空则标记为true，否则标记为false
            }
        }
        dfs(s, 0);//dfs搜索
        return ret;
    }
    public void dfs(String s, int i) {
        if (i == n) {
            ret.add(new ArrayList<String>(ans));
            return;//如果遍历完整个数组则将结果加入结果数组中
        }
        for (int j = i; j < n; ++j) {
            if (f[i][j]) {
                ans.add(s.substring(i, j + 1));//如果当前字符串满足前后相同则加入ans中
                dfs(s, j + 1);//继续遍历下一个数
                ans.remove(ans.size() - 1);//剪枝
            }
        }
    }
}

时间复杂度为O(n·2^n)，n为字符串长度
空间复杂度为O(n^2)

第139题 单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：

解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。

示例 2：

解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。
注意你可以重复使用字典中的单词。

示例 3：

解题思路

一段一段判断是否在字符串中出现

代码

// 单词拆分：动态规划
public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);//哈希集合
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;//将首字母设为合法
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {//如果前面的字符串合法免责判断是否存在下一个字符串是否合法
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

时间复杂度为O(n^2)，n为字符串长度
空间复杂度为O(n)