posted in 二叉树  leetcode 

问题

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

例如,给定如下二叉搜索树:  root = \([6,2,8,0,4,7,9,null,null,3,5]\)

示例 1:

\(输入:\) root = \([6,2,8,0,4,7,9,null,null,3,5]\), p = \(2\), q = \(8\)
\(输出:\) 6
\(解释:\) 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

\(输入:\) root = \([6,2,8,0,4,7,9,null,null,3,5]\), p = 2, q = 4
\(输出:\) 2
\(解释:\) 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉搜索树中。

解法

比较简单,递归判断当前节点是否在p、q之间即可。不过需要注意的是,测试用例中有p>q的,所以,需要先进行一次反转。

代码

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        //如果p>q先进行一次反转
        if (p.val > q.val) {
            return lowestCommonAncestor(root, q,p);
        }
        if (p.val <= root.val && q.val >=root.val) {
            return root;
        }
        if (p.val > root.val) {
            return lowestCommonAncestor(root.right, p,q);
        } else {
            return lowestCommonAncestor(root.left,p,q);
        }
    }
}

问题

给定一个二叉树,它的每个结点都存放一个 0-9 的数字,每条从根到叶子节点的路径都代表一个数字。

例如,从根到叶子节点路径 \(1->2->3\) 代表数字 \(123\)。

计算从根到叶子节点生成的所有数字之和。

说明: 叶子节点是指没有子节点的节点。
示例 1:
输入: \([1,2,3]\)

    1
   / \
  2   3

输出: 25
解释:
从根到叶子节点路径 \(1->2\) 代表数字 \(12\).
从根到叶子节点路径 \(1->3\) 代表数字 \(13\).
因此,数字总和 = \(12 + 13 = 25\).
示例 2:
输入:\([4,9,0,5,1]\)

    4
   / \
  9   0
 / \
5   1

输出: \(1026\)
解释:
从根到叶子节点路径 \(4->9->5\) 代表数字 \(495\).
从根到叶子节点路径 \(4->9->1\) 代表数字 \(491\).
从根到叶子节点路径 \(4->0\) 代表数字 \(40\).
因此,数字总和 = \(495 + 491 + 40 = 1026\).

解法

整体难度不大,使用深度优先搜索算法递归即可

代码

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int result = 0;
    public int sumNumbers(TreeNode root) {
        dfs(root,0);
        return result;
    }
    
    private void dfs(TreeNode root, int curr) {
        if (root == null) {
            return;
        }
        //需要注意的是这里要乘10再加。
        curr = curr *10 + root.val;
        if(root.left ==null && root.right == null) {
            result += curr;
            return;
        }
        //递归左子树
        bfs(root.left, curr);
        //递归右子树
        bfs(root.right,curr);
    }
}
posted in leetcode  二叉树 

问题

翻转一棵二叉树。
示例:
输入:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

解法

很简单的递归调用即可。

代码

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root ==null) {
            return root;
        }
        invert(root);
        return root;
        
    }
    
    private void invert(TreeNode root) {
        if (root ==null) {
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invert(root.left);
        invert(root.right);
    }
}

逸闻

这道题是HomeBrew的作者 Max Howell 的一条推特中的题。

给定一个二叉树,返回它的中序 遍历。

示例:
输入: \([1,null,2,3]\)

   1
    \
     2
    /
   3

输出: \([1,3,2]\)

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

解法(递归)

经典的算法题,没什么可说的。

代码(递归)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        mid(root, result);
        return result;
    }
    private void mid(TreeNode root, List<Integer> result) {
        if (root ==null) {
            return;
        }
        //先递归左子树
        mid(root.left,result);
        //递归完成后加入本节点
        result.add(root.val);
        //再递归右子树
        mid(root.right, result);
    }
}

解法(迭代)

构建一个栈,只要有左子树就一直压栈,直到左子树为空,出栈后将结果加入到result,然后将当前指针指向当前节点的右子树,进行下一轮压栈处理。

代码(迭代)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.empty()) {
            //左子树一直压栈
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            //出栈
            root = stack.pop();
            result.add(root.val);
            //切换到右子树进行下一轮
            root = root.right;
        }
        return result;
    }
}
posted in leetcode 

问题

给定字符串 \(S\),找出最长重复子串的长度。如果不存在重复子串就返回 \(0\)。
示例 1:

输入:\("abcd"\)
输出:\(0\)
解释:没有重复子串。

示例 2:

输入:\("abbaba"\)
输出:\(2\)
解释:最长的重复子串为 \("ab"\) 和 \("ba"\),每个出现 \(2\) 次。

示例 3:

输入:\("aabcaabdaab"\)
输出:\(3\)
解释:最长的重复子串为 \("aab"\),出现 \(3\) 次。

示例 4:

输入:\("aaaaa"\)
输出:\(4\)
解释:最长的重复子串为 \("aaaa"\),出现 \(2\) 次。
 

提示:

  • 字符串 \(S\) 仅包含从 \(a\) 到 \(z\) 的小写英文字母。
  • \(1 <= S.length <= 1500\)

解法1(暴力循环)

\(O(n^3)\)的解决方案。三层循环,最里面一层判断是否为重复子串。

代码1(暴力循环)

class Solution {
    public int longestRepeatingSubstring(String str) {
        int len = str.length();
        int res = 0;
        // 大循环
        for (int i = 0; i < len; i++) {
            // 控制相同字符串第二串的起始索引,注意是i+1的。
            for (int j = i + 1; j < len; j++) {
                // 本层循环里面的重复字符串长度
                int currLen = 0;
                for (int k = 0; j + k < len; k++) {
                    // 第三个变量向前推进,直到不相等为止
                    if (str.charAt(i + k) == str.charAt(j + k)) {
                        currLen++;
                        //判断长度与保存的长度大小
                        res = Math.max(res, currLen);
                    } else {
                        //不符合直接跳出该层循环
                        break;
                    }
                }
            }
        }
        return res;
    }
}

解法2(动态规划)

设\(f(i,j)\)为\(S[i:i+k]与S[j:j+k]\)重复字符串的长度,并且\(S[i] == S[j]\),那么会有
\(f(i,j) = f(i - 1, j - 1) + 1\)。
换句话说就是,如果\(S[i]==S[j]\),那么\(i-1\)与\(j-1\)原有的重复字符串长度需要\(+1\)。
这一考虑的空间复杂度为\(O(N)\),时间复杂度为\(O(N^2)\)

代码2(动态规划)

class Solution {
    public int longestRepeatingSubstring(String str) {
        int len = str.length();
        char[] chars = str.toCharArray();
        int res = 0;
        //第一层没什么特殊的,直接循环即可,需要注意的一点是跳出条件为len-res,因为当i超过len-res时,已经绝对不可能再出现大于res的结果了。直接跳出即可。
        for (int i = 0; i < len - res; i++) {
            int curr = 0;
            //注意这里j要从i+1开始计算,因为重复字符串肯定不能从相同起始索引比较起
            for (int j = i + 1, k = 0; j < len - res + curr; j++, k++) {
                // 注意这里比较的是k与j,
                if (chars[k] == chars[j]) {
                    curr++;
                    res = Math.max(res, curr);
                } else {
                    curr = 0;
                }
            }
        }
        return res;
    }
}
posted in leetcode 

问题

请你来实现一个 \(atoi\) 函数,使其能将字符串转换成整数。

首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字组合起来,作为该整数的正负号;假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符,这些字符可以被忽略,它们对于函数不应该造成影响。

注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换。

在任何情况下,若函数不能进行有效的转换时,请返回 0。

说明:

假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 \([−2^{31},  2^{31} − 1]\)。如果数值超过这个范围,qing返回  INT_MAX (\(2^{31} − 1\)) 或 INT_MIN (\(−2^{31}\)) 。

解法

注意看说明,首先我们可以排除一些特殊情况,字符串为空或者长度为0,直接返回0即可。
接下来注意到需要丢弃掉开头的空格字符串。那么可以先用一个while循环,来处理应该跳过的字符数量,在接下来的循环中作为初始索引进行循环。这里还需要注意的一点是可能字符串全是空格,这也是个跳出点。不要进入后面的循环了。
接下来,判断初始索引的第一个字符是什么,如果是'+'(没错,用例中真有+1这种奇葩字符,要当成正数1来处理)或'-',还需要一个特殊处理,设置一个boolean值,代表正负号,并且索引值前进1,如果不是数字,那么需要跳出循环处理。
接下来拼接数字,拼接比较简单,假设\(num\)为当前索引指代的数字,无非就是\(result = result * 10 + num\)。但是,有可能溢出,所以需要考虑如何处理溢出,我们知道Integer.MAX_VALUE = \(2^{31}-1\) 即\(2147483647\), 那么如何才会溢出呢?必然是result > MAX_VALUE/10或者 result == MAX_VALUE && num>7时才会溢出,那么溢出后,判断返回值的正负,直接返回对应的值就可以了。
跳出循环后直接返回result即为结果。

代码

java

class Solution {
    public int myAtoi(String str) {
        //处理特殊情况
        if (str == null || str.length() == 0) {
            return 0;
        }
        
        int i = 0;
        // 排除前面空格
        while(i < str.length() && str.charAt(i) == ' ') {
            i++;
        }
        
        // 处理字符串全为空格的情况
        if (i == str.length()) {
            return 0;
        }
        
        // 当接下来的第一个字符为正负号或者在0~9之间时,进入循环
        if (str.charAt(i) == '-' || str.charAt(i) == '+' || (str.charAt(i)>='0' && str.charAt(i) <= '9')) {
            // 未溢出时的返回值
            int result = 0;
            // 正负的判断
            boolean negative = str.charAt(i) == '-';
            // 判断溢出的情况
            int overflowCtl = Integer.MAX_VALUE / 10;
            // 如果为正负号,索引需要前进一步
            if (str.charAt(i) == '-' || str.charAt(i) == '+') i++;
            
            //开始循环
            while (i < str.length()) {
                // 如果是数字
                if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
                    //获得当前的数字
                    int num = str.charAt(i++) - '0';
                    // 如果溢出,那么返回最大最小值
                    if (result > overflowCtl || (result  == overflowCtl && num>7)) {
                        if (negative) {
                            // 如果是负数,返回最小值
                            return Integer.MIN_VALUE;
                        } else {
                            // 否则返回最大值
                            return Integer.MAX_VALUE;
                        }
                    }
                    // 没溢出 直接累加
                    result = result * 10 + num;
                } else {
                    // 非数字,直接跳出
                    break;
                }
            }
            // 注意正负号就可以了
            return negative? -result : result;
        }
        // 兜底策略
        return 0;
    }
}

问题

给定一个二叉树,返回它的 前序 遍历。

示例:
输入: \([1,null,2,3]\)

   1
    \
     2
    /
   3 

输出: \([1,2,3]\)

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

解法

没什么可说的。直接上代码吧。

代码

递归

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> result = new LinkedList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return result;
        }
        preorder(root);
        return result;
    }
    
    public void preorder(TreeNode root) {
        if (root == null) {
            return;
        }
        //先将root.val加入result
        result.add(root.val);
        //递归左子树
        preorder(root.left);
        //递归右子树
        preorder(root.right);
    }
}

迭代

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> result = new LinkedList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            //需要注意这里right要先压栈 其他的基本无压力。
            if (node.right !=null) {
                stack.push(node.right);
            }
            if (node.left !=null) {
                stack.push(node.left);
            }
        }
        return result;
    }
}
posted in leetcode  数组 

问题

数组 \(A\) 是 \([0, 1, ..., N - 1]\) 的一种排列,\(N\) 是数组 \(A\) 的长度。全局倒置指的是 \(i,j\) 满足 \(0 <= i < j < N\) 并且 \([i] > A[j]\) ,局部倒置指的是 \(i\) 满足 \(0 <= i < N\) 并且 \(A[i] > A[i+1]\) 。

当数组 \(A\) 中全局倒置的数量等于局部倒置的数量时,返回 \(true\) 。

示例 1:

输入: \(A = [1,0,2]\)
输出: \(true\)
解释: 有 1 个全局倒置,和 1 个局部倒置。

示例 2:

输入: \(A = [1,2,0]\)
输出: false
解释: 有 2 个全局倒置,和 1 个局部倒置。

注意:

  • \(A\) 是 \([0, 1, ..., A.length - 1]\) 的一种排列
  • \(A\) 的长度在 \([1, 5000]\)之间
  • 这个问题的时间限制已经减少了。

解法

一开始想法比较简单,既然是求逆序对的数量,那么双层for循环一个\(O(n^2)\)的解法就完了。但是第三项注意事项中说了时间限制已经减少,所以毫无意外的超时了。
此时考虑逆序对的性质,全局倒置一定是局部倒置。
对一个\([0,1,...,A.length - 1]\)的排序数组而言,索引\(i\),如果满足\(abs(A[i]-i) <=1\),那么,说明\(i\)只是左移或者右移了一位(或者没变),全局倒置与局部倒置至少同时加一(或者保持不变),仍然满足条件;如果\(abs(A[i] - i) >= 2\),那么,说明\(A[i]\)至少左移或者右移了两位,意味着右边至少有两个比自己小的数(或者左边必然有来2个比自己大且不相邻的数,其中至少一个不相邻)局部(必然<)全局所以造成一定不等,此时不满足条件,直接返回false。

代码

java

class Solution {
    public boolean isIdealPermutation(int[] A) {
        if (A.length <3) {
            return true;
        }
        for (int i = 0; i < A.length; i++) {
            if (Math.abs(A[i] - i) >= 2) {
                return false;
            }
        }
        return true;
    }
}
posted in leetcode  数组  双指针 

问题

给定两个数组,编写一个函数来计算它们的交集。
示例 1:

输入: nums1 = \([1,2,2,1]\), nums2 = \([2,2]\)
输出: \([2,2]\)

示例 2:

输入: nums1 = \([4,9,5]\), nums2 = \([9,4,9,8,4]\)
输出: [4,9]

说明:

  • 输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致。
  • 我们可以不考虑输出结果的顺序。

进阶:

  • 如果给定的数组已经排好序呢?你将如何优化你的算法?
  • 如果 nums1 的大小比 nums2 小很多,哪种方法更优?
  • 如果 nums2 的元素存储在磁盘上,磁盘内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?

解法

问题比较简单。可以遍历两个数组,获得数字出现的频次,然后对比两个频次即可。或者可以直接排序两个数组,然后使用两个指针分别遍历数组即可。

解法

频次法

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if(nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        //这里使用hashmap,因为数字是不定长的。
        Map<Integer, Integer> map1 = new HashMap<>(nums1.length);
        for (Integer i: nums1) {
            Integer count = map1.get(i);
            if (count == null) {
                map1.put(i, 1);
            } else {
                map1.put(i, count+1);
            }
        }
        Map<Integer, Integer> map2 = new HashMap<>(nums2.length);
        for (Integer i: nums2) {
            Integer count = map2.get(i);
            if (count == null) {
                map2.put(i, 1);
            } else {
                map2.put(i, count+1);
            }
        }
        Iterator iter = map1.entrySet().iterator(); 
        List<Integer> result = new LinkedList();
        //遍历两个频次map即可,这里使用小的那个map遍历。可以减少查询次数
        while(iter.hasNext()) {
            Map.Entry<Integer, Integer> entry = (Map.Entry) iter.next(); 
            Integer key = entry.getKey(); 
            Integer val1 = entry.getValue(); 
            Integer val2 = map2.get(key);
            if(val2 != null) {
                int count = Math.min(val1, val2);
                while (count-- > 0) {
                    result.add(key);
                }
            }
        }
        
        //最终生成结果,因为没有用从List到int[]的方便转换方法。
        int[] res = new int[result.size()];
        for(int m=0;m<res.length;m++)
        {
            res[m]=result.get(m);
        }
        return res;
    }
}

排序遍历法

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if(nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        List<Integer> result = new LinkedList();
        
        //排序两个数组
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        //遍历两个数组
        for (int i = 0,j=0; i<nums1.length && j<nums2.length;) {
            //相等则加入result
            if (nums1[i] == nums2[j]) {
                result.add(nums1[i]);
                i++;
                j++;
            } else if (nums1[i] < nums2[j]){
                // 这里注意只有其中一个往前推进。
                i++;
            } else {
                j++;
            }
        }
        
        int[] res = new int[result.size()];
        for(int m=0;m<res.length;m++)
        {
            res[m]=result.get(m);
        }
        return res;
    }
}
posted in leetcode  数组 

问题

给定仅有小写字母组成的字符串数组 A,返回列表中的每个字符串中都显示的全部字符(包括重复字符)组成的列表。例如,如果一个字符在每个字符串中出现 3 次,但不是 4 次,则需要在最终答案中包含该字符 3 次。

你可以按任意顺序返回答案。

示例 1:

输入:\(["bella","label","roller"]\)
输出:\(["e","l","l"]\)

示例 2:

输入:\(["cool","lock","cook"]\)
输出:\(["c","o"]\)

提示:

  1. \(1 <= A.length <= 100\)
  2. \(1 <= A[i].length <= 100\)
  3. \(A[i][j]\) 是小写字母

解法

首先需要将每一个字符串进行字母的数量统计。然后遍历数量数组,获取每个字符的最小出现次数,即为答案。
数量统计有多种做法,二维数组、hashmap。此题中使用了二维数组。

代码

java

class Solution {
    public List<String> commonChars(String[] A) {
        //生成一个二维数组用于保存词频
        int[][] array = new int[A.length][26];
        //词频统计
        for (int i = 0; i < A.length; i++) {
            String s = A[i];
            for (char c : s.toCharArray()) {
                array[i][c - 97]++;
            }
        }
        List<String> result = new LinkedList<>();
        for (int i = 0; i < 26; i++) {
            if(array[0][i]==0) {
                continue;
            }
            //得到第一组词频
            int count = array[0][i];
            for (int j = 1; j < A.length; j++) {
                if (array[j][i] == 0){
                    count = 0;
                    break;
                }
                count = Math.min(count, array[j][i]);
            }
            //如果词频大于0,那么加入结果中
            if (count > 0) {
                char c = (char) (97 + i);
                String s = Character.toString(c);
                while (count-- >0) {
                    result.add(s);
                }
            }
        }
        return result;
    }
}