锐客网

  1. 首页 > it技术 > >

leetCode进阶算法题+解析（三十一）

二叉树的最近公共祖先
题目：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” leetCode进阶算法题+解析（三十一）
文章图片
题目截图 思路：额，分两种情况：一种是pq存不存在上下级关系，存在则答案就是上级的那个。不存在则找最近的交叉点。我目前有个想法：首先判断这两个节点在根节点的左右哪边。如果是一边则继续判断root.left或root.right。如果是两边则直接返回根节点。虽然我觉得这样做可能时间复杂度比较高，但是目前为止没有太好的办法，我先去实现再说别的。
卧槽，居然实现了！！！我自己都惊呆了啊，毕竟写着写着觉得越来越不对。。。哈哈，我直接贴代码：

/** * 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 == p || root == q) return root; //都在左递归左 if(isContains(root.left,p) && isContains(root.left,q)){ return lowestCommonAncestor(root.left,p,q); } //都在右递归右 if(isContains(root.right,p) && isContains(root.right,q)){ return lowestCommonAncestor(root.right,p,q); } //一左一右，返回当前节点 return root; } public boolean isContains(TreeNode root,TreeNode sub){ if(root == null) return false; if(root == sub) return true; return isContains(root.right,sub) || isContains(root.left,sub); } }

leetCode进阶算法题+解析（三十一）
文章图片
性能截图
讲真，我想知道我后面那百分之五的兄弟都是什么思路啊。哈哈，这个写着写着发现了问题，该说不说我绝对是做了double的判断啊。应该一次递归实现？我去试着优化了。
好了， 我现在感觉贼准确。之前思路还凑合，但是处理绝对有问题，我要先用contains遍历一遍，再用主方法的递归再遍历一遍。现在合成一次遍历了。我直接贴代码:
/** * 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; if(root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left,p,q); TreeNode right = lowestCommonAncestor(root.right,p,q); if(left != null && right != null) return root; if(left != null) return left; if(right != null) return right; return null; } }

如上代码，如果p，q分布在根节点两边，则left，right都不是空，则返回根节点。否则说明分布在一边。然后分别以左右节点为根遍历，直到遍历到分布在某一节点的两边（包括自身是其中一个节点）。逻辑其实很清楚，尽量去理解就行了，全靠脑补。
多说两句，其实二叉树这一块的题我觉得一个好的解决办法就是脑补，毕竟代码中哪怕调试也不是很明了清晰的。或者随意画画图，只要自己理解就好。树这块的题目我觉得不是很难，毕竟不是客观基础上的不会，不知道，比较不偏向于数学吧。多尝试，多想想，就这样，下一题。
除自身以外数组的乘积
题目：给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
【leetCode进阶算法题+解析（三十一）】思路：这道题怎么说呢，说实话看到输入输出我瞬间的想法是求出数组整个的乘积，然后到某个元素这个乘积除某个元素。还挺美，毕竟这么想时间复杂度也是O(n)，然后下一行告诉我们不要用除法，真的是，我记得不直接用除法的话位移是个好选择。我去试试吧。讲真，位运算永远是短板。
额，这个题我看了题解。然后发现其实也没那么难，比如正常算要从头乘到尾然后除当前数。但是我们也可以直接出了当前数别的相乘。也算是动归的一种，用数组记录中间过程。我直接去写代码，然后再来说。
class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] res = new int[n]; int val = 1; //这一层循环让res对应的值是nums对应元素前面的元素乘积 for(int i = 0; i=0; i--){ res[i] *= val; val *= nums[i]; } return res; } }

只能说思路真的很重要，说实话这道题我自己的想法就是位运算啊。代替除法啊。但是看了题解，真的只看了文字部分，扫了一眼大概是前后乘积相乘。然后手撸代码五分钟写完。这就说明思路是多重要了。而且完美的符合题目要求，常量额外空间。O(n)时间复杂（O(2n)是可以看成O(n)的）。并且这段代码性能超过百分百。
多做题其实不一定在代码上有什么进步，除了一些api的调用剩下大多数都是对思路的开拓。继续下一题了！
搜索二维矩阵2
题目：编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性： 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
思路：额，我很烦这种靠感觉做题的。因为没有明确的标准。怎么说呢，单纯的实现一次遍历怎么都ok了，但是重点是高效。是不是只要不是全遍历就算高效了？两个升序条件，可以确定了这个数的范围。小于0 ，0大于m-1,n-1就肯定是不存在的。其次就只能顺着找了，因为两个数组都是从小到大排序的，所以想要确定一个数的范围想要越来越小只能从下往上逼近。我目前的想法从最后一行开始定位，如果比给定值小则往上走，最终走不下去是false，不然就找到给定值了true。我去代码实现下。
class Solution { public boolean searchMatrix(int[][] matrix, int target) { if(matrix.length==0 || matrix[0].length == 0) return false; if(targetmatrix[matrix.length-1][matrix[0].length-1]) return false; int l = matrix.length-1; int r = 0; while(r=0){ if(matrix[l][r]>target){//当前值大了，往上缩圈 l--; }else if(matrix[l][r]

性能超过百分之九十，将将及格，思路没问题。就是这个范围我是多次测试。比较麻烦。一开始我是想用最后一个元素作为起始坐标。后来发现往前走可以往上也可以往前，出现岔路了，所以改成最后一排第一个了，这样大了小了都只有一条路可以走。反正最终版就是上面的代码，我去看看性能排行第一的是思路比较好还是代码的细节处理比较好。
有点神奇啊，你们都想不到性能排行第一的代码居然就是硬生生的遍历？？？我直接贴出来：
class Solution { public boolean searchMatrix(int[][] matrix, int target) { if(matrix.length == 0 || matrix[0].length == 0){ return false; } int n = matrix[0].length - 1; for(int i = 0; i < matrix.length; i++){ for(; n >=0; n--){ if(matrix[i][n] == target){ return true; }else if(matrix[i][n] < target){ break; }else{ continue; } } } return false; } }

并且同样的代码我提交也是7ms，和我上面的性能是一样的。有点奇怪。不过这个题看起来好像也就这样了，所以过了，下一题。
为运算表达式设置优先级
题目：给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
示例 1:
输入: "2-1-1"
输出: [0, 2]
解释:
((2-1)-1) = 0
(2-(1-1)) = 2
示例 2:
输入: "23-45"
输出: [-34, -14, -10, -10, 10]
解释:
(2(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)5) = 10
思路：额，怎么说呢，我第一反应是回溯。dp，然后才是具体这个题。我感觉没两个数字可以分为两种情况，直接运算，不直接运算。所以用dp是可以解决的。如果不说结果的话，首先两个数只有一种结果！其次三个数，可以先计算两个数的值，剩下的又是两个数了。只不过三个数中先计算两个数有两种可能，所以三个数会有两个结果。再之后是四位数。四位数选出两个数先计算，是有三种可能选出这两个数的。正常来讲四个数应该会有3乘2，也就是六个结果。但是我仔细看了下，有一些式子会出现多次，比如上面示例2的第二个解释，先算2乘3 和先算 4乘5都会走到这个式子。所以具体情况我觉得还是要再判断一下。我现在能想到的最low的办法就是放进set，然后再挨个计算，最后放到结果集，我先去试试
好吧，我第一反应是dp，但是真正到了写代码的时候却发现dp麻烦的不行。尤其是判重环节还要处理，所以临时又有了新的思路，分治。其实也不能算新的思路，我一直在看这个图中规律，其实也可以看成两个数两个数的分别治理。两个数是某个符号左边的和右边的。这么说思路就很清楚了。也就是每个符号可以将整个式子分成两个，左边的和右边的。如果某边还有多个数继续分，反正我感觉这个思路的代码好写的多，我继续去试试。
第一版本的代码出来了，果然分治比较容易写，一会儿我再用dp实现下比较比较性能：
class Solution { public List diffWaysToCompute(String input) { List res = new ArrayList(); //当前部分不含有符号，说明是一个数字了 if(!input.contains("+") && !input.contains("-") && !input.contains("*")){ res.add(Integer.valueOf(input)); return res; } for(int i = 0; i

思路就是上面 说的思路。任何一个式子都可以分两部分，把所有的组合情况用双层循环列出来，再分别组合。感觉这个逻辑稍微好理解一点。好了，我再去用dp试试怎么实现，我觉得这个题dp肯定是没问题的。
咳咳，大型打脸现场~~我写了半个小时，dp还是没实现。。总有问题，然后要下班了，我也不想调试了。这个题就这样吧，不过我还是要说这个题绝对dp是可以实现的。也算是留下个作业，啥时候我有时间了想起来了会继续做的（大概率是就此烂尾了）。
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，顺便祝大家工作顺顺利利！生活健健康康！

    推荐阅读


    上一篇：走出丧

    下一篇：娘家路