刷leetCode算法题+解析（十五）

周末宿舍网卡的一批，游戏玩的也心塞，还不如刷题呢~刷题使我快乐，嘿嘿

乘阶后的0

题目：给定一个整数 n，返回 n! 结果尾数中零的数量。

示例 1:
输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。
示例 2:
输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.
说明: 你算法的时间复杂度应为 O(log n) 。

思路：这道题让我学到了一个数学知识，n！的意思是乘阶。就是n!=1×2×3...xn。
然后这个是前提，知道乘阶是什么玩意了才好往下继续做题。然后知道乘阶的原理就开始分析什么相乘能得0。
首先2 * 5，4 * 5，6 * 5，8 * 5，10。注意的是这些是指1到10之间的可能。而且因为每个数只能用一次，所以这个5和这么多相乘其实没意义，它只能选择一个数相乘。然后不管5选择哪个数，反正是以5做判断的。理理思路:1-10之间，能尾数为0的也就是5，10。同样推：11-20之间能尾数成0的就是15，20这两个数。再仔细看规律:5,10,15,20..看出啥了？没错，都是5的倍数。
你以为只需要这样就完事了？不不不，想想25。25 * 4等于100。这个可不是一个0而是两个0。所以这个规律单纯的判断n中五的倍数的个数是不对的。
那咱们分析为什么25会俩0呢？25有什么特殊的？因为25是5 * 5组成的。相当于这是两个5的倍数。我这么说可能很不好理解，咱们用乘法来讲:比如25 * 4=5 * 5 * 2 * 2。或者换个乘数25 * 8 = 5 * 5 * 2 * 4。你看这个25里是不是包含了两个5（这一块真的很抽象，我能理解但是说不清楚那种，看了这个还不明白建议去百度看看别人的做法吧）。下一个特殊的就是50，50可以拆分为5 * 5 * 2。再下一个特殊 就是75.75可以拆分成5 * 5 * 3.以此类推，到了125又不一样了。因为125可以拆分为5 * 5 * 5. 变成三个五了！你看出这个规律了么？好吧我直接说规律吧，规律就是被5整除后还是5的倍数的数字是特殊的，还可以继续判断。直到不是5的倍数为止。其中每被5整除一次，都可以产生一个0（因为偶数的情况远远多于5，所以不用考虑5 * 几的问题）
其实这个规律对于所以的数字都适用。最开始说的5，10，15不就是被5整除后不能再被5整除，所以才只能产生一个0么?
说到了这，代码怎么写应该很容易了吧？接下来上代码:

class Solution {
    public int trailingZeroes(int n) {
        int result = 0;
        //如果最初n就小于5尾数没0.所以直接返回0也是对的。
        while(n>=5){
            //n中有多少的5的倍数。每一个都能产生一个0
            int x= n/5;
            result += x;
            //可能这5的倍数还能被5整除，所以要继续判断。
            n=n/5;
        }
        return result;
    }
}

其实这个思路不是很复杂，我这里分享一下我是怎么判断的吧。关于这个5的倍数是一开始就有这个想法的，然后用测试案例测。5，6，...一直测到20都没错。自以为对的，还好稳了一手没直接提交，随手写了一个较大的数字（2412这种）提交，结果答案跟自己返回的不一样，有点懵，但是要细心排查，所以我从100开始测试，结果不对，再之后50测，结果不对，因为我之前用20测过了知道结果是对的啊，继续中位数测试，25测试，结果差了1.24测试结果正确。由此可见这个问题就出在了25身上，定位了问题再开始找错就容易多了。其实也没多深奥的排查办法，但是不要着急，一点点排查总比连错误在哪里都不知道要好的多！好了，这道题就到这里，继续下一题！

连表查询？

题目：编写一个 SQL 查询，满足条件：无论 person 是否有地址信息，都需要基于上述两表提供 person 的以下信息：FirstName, LastName, City, State

image.png

思路：我也不知道为啥leetCode刷着刷着刷出一道sql题目。但是既然都点进来了就顺便做了吧。（我就是在题目列表第一页开始所以简单的题目都点进来做）审完题就是一个关联查询而已，直接上sql语句

select p.FirstName,p.LastName,a.City,a.State
 from Person p
 left outer join Address a 
on p.personId = a.personId;

一个简单左外连接查询，题目要求是不管address表有没有数据person表都要有数据，左外最合适了（右外是一样的，只不过两个表换个位置，但是我习惯用左外）。
然后提交了就通过了，其实感觉子查询应该也是可以的，既然做了就去看看大佬在这么简单的题目上能不能有什么新想法：
大神也没啥思路，毕竟简单到没啥可秀的，不过评论区还有很多人不懂为啥直接两个表查询结果不对，这里就多说下：直接select * from A a,B b where a.x = b.x。这种属于内连接，必须A,B 表里都有的才会显示。
这个应该属于sql基础就不太好的。我建议去好好看看连表查询这一块，内连接外连接左外右外全外啥的。下一题吧，这道题好像是来搞笑的。

第二高的薪水

题目：编写一个 SQL 查询，获取 Employee 表中第二高的薪水（Salary） 。

例如上述 Employee 表，SQL查询应该返回 200 作为第二高的薪水。如果不存在第二高的薪水，那么查询应返回 null。

image.png
这个题还稍微有点点意思，因为第二高的薪水。涉及到可能有人薪水一致，所以肯定是不能直接排序取第二个，要用分组。又因为第二高，所以还得排序。最后获取第二条所以我用的分页。一页一条取第二页的，没毛病。只不过这个查询结果不处理的话如果没有是不返回的，题目要求要返回null。所以还要做处理,反而是这个处理让我卡住了，mysql有个ifnull的函数，所以返回null没问题，但是null是字符串啊！如果用了这个函数虽然返回的是null或者其本身的数据，但是数据形式变了，这个还是要报错的。
看了大神思路，是我想复杂了，什么分组啊，一个distinct就搞定了。并且这个返回null问题，可以直接外面再套一个查询就解决了。只能说只要思想不滑坡，办法总比问题多。

select 
    (select distinct Salary 
    from Employee 
    order by Salary Desc 
    limit 1,1) as SecondHighestSalary ;

其实这种知识点就是平时对sql语句的积累和运用，没啥好说的，也没啥可说的。这两道题就当是换个心情了。继续往下做。

超过经理收入的员工

题目

连着好几道题都是sql的，对付这一次刷完得了。虽然有点对不起我文章的名字。
这道题也简单，就是一个自连接。都是基础的东西。直接上sql语句吧:

select e.Name as Employee from Employee e left join Employee ee on e.ManagerId=ee.Id where e.Salary>ee.Salary; 

运行出来性能不咋地，我再看看评论中别人的做法：

select e1.Name as Employee from Employee as e1 ,Employee as e2 where e1.ManagerId=e2.Id AND e1.Salary>e2.Salary

SELECT 
    Name Employee
FROM
    Employee AS a
WHERE
    Salary > (SELECT 
            Salary
        FROM
            Employee
        WHERE
            Id = a.Managerid)

我挨个运行的，性能还不如我的呢，反正这个题也就这样了。

查找重复的电子邮箱

题目

这道题还稍微有那么一丢丢意思，起码跟算法稍微有一点点关系，这个我之前考虑的是按邮箱分组然后每个组中大于1的邮箱就是有重复的。但是后来看到了大佬的想法（直接看的解析），决定用一个自连接也行，如果有id不一样但是邮箱一样的就是重复的了。下面是sql：

select distinct a.Email from Person a, Person b where a.Email = b.Email and a.Id != b.Id 

从不订购的用户

题目
题目

这个题我连答案都没看，反正自己写出来的能运行，虽然贼慢。

select c.Name as Customers from Customers c left join Orders o on c.id=o.CustomerId where o.CustomerId is null;

刚刚看了下，确定到这就没了sql题了，喜大普奔，真的不怎么太想做。
今天就记录到这里，估计也帮不到谁，反正就是看了的亲们点个喜欢点个关注以资鼓励哈~~也祝大家周末愉快，工作顺利！