leetCode进阶算法题+解析（三十）
唔，不得不说leetcode上的每日一题还是很有必要的，可以给人增加信心~哈哈。好了好了，正式开始刷题了。
完全二叉树的节点个数
题目：给出一个完全二叉树，求出该树的节点个数。
说明：
完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
题目截图
思路：额，首先单纯的实现简单的不得了，直接遍历树算节点就行了。方式方法多种多样，递归迭代都行。但是这个题目中二叉树已经是完全二叉树了，其实是不是只要知道层数。再知道最后一层的个数就行了呢？但是这样想知道最后一层的个数也需要层次遍历啊.反正想不出不遍历整个树的方法，我去试着写写代码吧。
第一个版本的层次遍历，虽然性能不行，但是对付着实现了：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
int res = 0;
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()){
int size = queue.size();
res += size;
for(int i = 0;i<size;i++){
TreeNode t = queue.poll();
if(t.left!=null) queue.add(t.left);
if(t.right!= null) queue.add(t.right);
}
}
return res;
}
}
然后我觉得这个完全二叉树的条件肯定是要用到的，具体怎么用我这边再想想。一点点分析：首先除了最后一层剩下的元素数都知道，主要就是最后一层有几个，或者换个说法，最后一层差几个。而最后一层差几个不用遍历的方式，只能用树的形式判断。我有点模糊的思路，但是还不太成熟。我去写写代码试试。
额，最终我还是看了题解，这个题怎么说呢，用到了分治的思想。首先这个树如果是完全二叉树，则肯定左右子树有一个是满树，依次类推，我画个图表示：
图示分治思路
就这样一层一层直到当前节点为null停止。然后代码实现：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
int l = getTreeH(root.left);
int r = getTreeH(root.right);
int res = 0;
if(l==r){//左子树是满树，递归右子树
res += (1<<l) + countNodes(root.right);
}else{//右子树是满树，递归左子树
res += (1<<r) + countNodes(root.left);
}
return res;
}
//获取一个树的高（因为满足完全二叉树，所以左树高就是树高）
public int getTreeH(TreeNode root){
if(root==null) return 0;
return getTreeH(root.left)+1;
}
}
其实这个题怎么说呢，单独的每行代码都能看懂，但是自己想确实思路没这么灵活。这样其实是少了一半的遍历数量的。只需要确定好遍历哪一边，另一边直接计算就好。算是学到了吧。另外刷题以来，二叉树，平衡二叉树，完美二叉树，完全二叉树，二叉搜索树感觉也不知不觉学到了好多知识，以后更加加油吧！下一题了。
矩形面积
题目：在二维平面上计算出两个由直线构成的矩形重叠后形成的总面积。每个矩形由其左下顶点和右上顶点坐标表示，如图所示。
题目截图
思路：这个题其实思路就是取交集吧。我目前的想法就是取相交部分的交集，然后算出面积，两个长方形面积和减去重合面积，然后就是结果。其实这个借用二维坐标算出长宽还是蛮容易的。我而且算出重合的长度和宽度就是在范围中取交集。数学知识很好理解，我去代码实现了。
我活生生用数学知识实现了，简直佩服自己。哎，写的比较恶心，还有优化的空间，我先把第一版本的代码贴出来：
class Solution {
public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
//第一个长方形 长度
int l1 = Math.abs(C-A);
//第一个长方形的宽
int r1 = Math.abs(D-B);
//第二个长方形长宽
int l2 = Math.abs(E-G);
int r2 = Math.abs(F-H);
int res = l1*r1 + l2*r2;
//在最左的左和最右的右都是没交集
if(Math.min(E,G)>Math.max(A,C) || Math.max(E,G)<Math.min(A,C)) return res;
//最上的上 和最下的下也会没交集
if(Math.min(B,D)>Math.max(F,H) || Math.max(B,D)<Math.min(F,H)) return res;
//到这说明肯定有交集，只要知道交集是多少就行了。
int[] l = new int[]{A,C,E,G};
int[] r = new int[]{B,D,F,H};
Arrays.sort(l);
Arrays.sort(r);
int c = Math.abs(l[1]-l[2])*Math.abs(r[1]-r[2]);
return res-c;
}
}
我去优化一下。额，优化完了，主要是我审题不清，我这里判断的是四个点分别是长方形的顶点。但是其实左下，右上已经确定了，所以其实我这里好多Math.abs（）都是不用判断的。我附上最终版的代码（思路是差不多的，只不过我这里多了很多没必要的判断）：
class Solution {
public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
int m = 0;
if((Math.min(C,G)>Math.max(A,E))&&(Math.min(D,H)>Math.max(B,F))){
m =(C-A)*(D-B)+(G-E)*(H-F)-(Math.min(C,G)-Math.max(A,E))*(Math.min(D,H)-Math.max(B,F));
}
else{
m =(C-A)*(D-B)+(G-E)*(H-F);
}
return m;
}
}
然后这个题就这样了，其实难倒是不难，就是很复杂。这道题过了。下一题吧。
基本计算器2
题目：实现一个基本的计算器来计算一个简单的字符串表达式的值。字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。
示例 1:
输入: "3+2*2"
输出: 7
示例 2:
输入: " 3/2 "
输出: 1
示例 3:
输入: " 3+5 / 2 "
输出: 5
说明：
你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。
思路：这个题首先从最基本的讲，字符串拆分成字符数组是没跑了。然后就是符号的记录和数字的拼接是需要代码控制的。因为已经确定是有效的表达式，而且还都是非负数，甚至还只有加减乘除没有括号，所以这里的运算顺序应该是加减后算，先保留。然后遇到乘除可以直接算了保存结果。重点就是加减怎么算。其实换个角度，减去一个正数等于加上这个数的负数。所以总体来讲是一次遍历的事。对了比如3454这种连续的数字，要还原。反正整体来讲我觉得不难。我去代码实现下试试。
这个题简直无言以对，思路没问题，我不知道出题人为什么会让字符串中带空格?考验想象力？反正第一次提交栽在空格身上了，第二次ac了。其实这个题就是麻烦而不是难，所以我直接贴代码了。
class Solution {
public int calculate(String s) {
char[] c = s.toCharArray();
char f = '+';
//保存上一个数字
Stack<Integer> stack = new Stack<Integer>();
for(int i = 0;i<c.length;i++){
if(c[i]==' ') continue;
if(c[i]>='0'){
int t = c[i]-'0';
i++;
while(i<c.length && c[i]>='0') {
t = t*10+(c[i]-'0');
i++;
}
if(f == '+') stack.push(t);
if(f == '-') stack.push(-t);
if(f == '*' || f == '/') stack.push(res(f,stack.pop(),t));
i--;
}else{
f = c[i];
}
}
int sum = 0;
for(int i : stack){
sum += i;
}
return sum;
}
private int res(char op, int a, int b){
if(op == '*') return a * b;
return a / b;
}
}
这里一开始我有两个遗漏点：一个是空格问题。如果不加上遇到空格continue则回报栈异常。第二个是0的问题，一开始我看都是正整数，所以我这里是char[i]>'0'判断的，后来遇到2048才发现0也可能出现，所以换成了大于等于。剩下没别的问题了，这道题就这么过吧。下一题。
汇总区间
题目：给定一个无重复元素的有序整数数组，返回数组区间范围的汇总。
示例 1:
输入: [0,1,2,4,5,7]
输出: ["0->2","4->5","7"]
解释: 0,1,2 可组成一个连续的区间; 4,5 可组成一个连续的区间。
示例 2:
输入: [0,2,3,4,6,8,9]
输出: ["0","2->4","6","8->9"]
解释: 2,3,4 可组成一个连续的区间; 8,9 可组成一个连续的区间。
思路：这个题，我还是打算一次遍历啊，没有任何时间空间条件，不知道是我飘了还是真的今天遇到的题都简单，反正我觉得这道题一次遍历就能解决啊。下一个元素是连续元素继续往下判断，直到不是连续元素则闭合字符串添加到结果集的list，再继续往下。我去代码实现了。
好了，写完了，这个题没什么坑，我直接贴代码：
class Solution {
public List<String> summaryRanges(int[] nums) {
List<String> res = new ArrayList<String>();
for(int i = 0;i<nums.length;i++){
int t = nums[i];
int r = t+1;
i++;
while(i<nums.length && nums[i] == r){
i++;
r++;
}
//走出while循环说明不连续了
i--;
r--;
if(r != t){
res.add(t+"->"+r);
}else{
res.add(String.valueOf(t));
}
}
return res;
}
}
我这个题性能有点问题，我怀疑可能是字符串直接相加这块的，毕竟都已经O(n)了，不可能时间复杂度上有问题了，也就是细节处理，我决定直接看性能排行第一的代码了：
class Solution {
public List<String> summaryRanges(int[] nums) {
int index = 0;
List<String> res = new ArrayList<>();
while(index<nums.length){
StringBuffer bf = new StringBuffer();
boolean flag = false;
bf.append(nums[index]);
index++;
while(index<nums.length){
if(nums[index]==nums[index-1]+1){
if(!flag){
bf.append("->");
}
index++;
flag = true;
}else{
break;
}
}
if(flag){
bf.append(nums[index-1]);
}
res.add(bf.toString());
}
return res;
}
}
哎，我现在仿佛开了光啊，果然是字符串处理这块的问题，然后代码逻辑也就这样，这个题比较简单，所以不多说了，就这么过，下一题。
求众数2
题目：给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。
示例 1:
输入: [3,2,3]
输出: [3]
示例 2:
输入: [1,1,1,3,3,2,2,2]
输出: [1,2]
思路：额，这个题单纯的实现简单的不得了，没接触过算法的也能手到擒来。但是这个额外要求时间复杂度O(n)一次遍历，空间复杂度O(1)不占用额外空间可能会稍微复杂点？一点点分析，首先按这个答案最多两个（因为个数要超过三分之一）。我记得我做过一个类似的，就是超过全数组的一半以上的元素。是用个计数器来实现的。首先这个元素出现加1.不是这个元素-1.计数为0从新计数。最后遍历完剩下的元素就是出现次数最多的元素（如果最多的元素确实是超过一半以上）。不过这个题是三分之一，我不知道是不是一个道理，我去试试代码。
首先思路没问题，其次面向测试案例编程,我先贴代码：
class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
if(nums.length==0) return res;
int c1 = 0;
int c2 = 0;
int v1 = 0;
int v2 = 0;
for(int i :nums){
if(i == v1){
c1++;
}else if(i == v2){
c2++;
}else if(c1 == 0){
c1 = 1;
v1 = i;
}else if(c2 == 0){
c2 = 1;
v2 = i;
}else{//不是v1也不是v2都减1
c1--;
c2--;
}
}
if(v1==v2){
res.add(v1);
return res;
}
//计数
c1 = 0;
c2 = 0;
for(int i : nums){
if(i==v1) c1++;
if(i==v2) c2++;
}
if(c1>nums.length/3) res.add(v1);
if(c2>nums.length/3) res.add(v2);
return res;
}
}
这里其实有两点都是在提交的时候发现的问题：如果数组中只有一个元素值，那么v1=v2,就不要再计数了，直接放进结果集返回就行了。第二个是数组没有元素直接返回空。
剩下的这个其实举一反三，三分之一会做了，我感觉四分之一我也会了，哈哈。反正这个思路确实想了好久，我记得求众数1中过半元素好像就是这个做法。反正这个题就这样了，这个小技巧记住就行了（如果没有过半值或者过三分之一的值，这两个v1，v2就是靠后的吃香，所以不再计数一遍是不能确定的）。最后一题了。
二叉搜索树中第K小的元素
题目：给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。说明：你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
题目截图
思路：怎么说呢，这道题说好做就是单纯的前序遍历二叉搜索树就是一个升序集，第k小就是第k个元素。但是进阶条件频繁的增删应该就是重要考点了。首先这个题全便利肯定是很low的做法，其实最理想的是想找第k小，那么直接前序遍历遍历到第k个就好。不过怎么实现我想不到。参考上面那道完全二叉树的思路，是不是可以一个树分左树右树？遍历只遍历一半，判断k在哪边，然后再去找具体的值？我去写代码试试。
性能超过百分百，今天第一个一次就过而且性能贼好的题，开心~~哈哈，果然不要用常规办法解题，当然也可能是这道题比较简单，尤其是下午那道完全二叉树的思路还在，我直接贴代码了：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int kthSmallest(TreeNode root, int k) {
int l = getNodeNum(root.left);
if(l==k-1){//第k个就是根节点
return root.val;
}else if(l<k){//k在右树上
return kthSmallest(root.right,k-l-1);
}else{//k在左树上
return kthSmallest(root.left,k);
}
}
public int getNodeNum(TreeNode root){
if(root==null) return 0;
return getNodeNum(root.left)+getNodeNum(root.right)+1;
}
}
其实这个题我感觉直接全便利应该也不错，毕竟题目就是简单，就是在遍历过程中数数，直接到了第k个然后返回。。想想可能比现在这样性能还好。不过因为做法比较常规，我就不再写一遍了。
今天的笔记就记到这里了，如果稍微帮到你了记得点个喜欢点个关注，另外也祝大家工作顺顺利利，生活健健康康！每天进步一点点啊~！
