2018-06-30

LeetCode解题日志

Algorithms

2. Add Two Numbers

用链表模拟十进制加法运算，linked list有点犯晕，在Eclipse IDE上调试了半天才跑通了，只会瞎用框架和库的人算法方面果然是菜鸟。

一开始出来的结果顺序老是逆着。在网上找了个Function to reverse the linked list，incline到自己那代码里，最后总算在LeetCode上跑过了。

Java

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    	ListNode node1 = l1, node2 = l2;
    	ListNode node = null, tmpNode = null;
    	int sum = 0;
    	boolean b = false;
		while (node1 != null || node2!=null) {
			node = new ListNode(0);
			sum = (node1!=null?node1.val:0) + (node2!=null?node2.val:0);
			if (b) sum++;
			node.val = sum<10?sum:sum%10;
			b = sum>=10 ? true : false;
			if (tmpNode!=null)
				node.next = tmpNode;
			if (node1!=null)
			  node1 = node1.next;
			if (node2!=null)
			  node2 = node2.next;
			tmpNode = node;
		}
		if (b) {
			ListNode node3 = node;
			node = new ListNode(1);
			node.next = node3;
		}
    	ListNode prev = null;
    	ListNode current = node;
    	ListNode next = null;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        node = prev;
        return node;        
    }

/**
 * Definition for singly-linked list.
 */
class ListNode {
	int val;
	ListNode next;
	ListNode(int x) {
		val = x;
	}
}

Submission Detail

1562 / 1562 test cases passed.

写完了过上一段时间，又忘了是怎么做对的，在IDE上debug出来的代码，可能做得比较勉强。

1. Two Sum

Java

Brute Force

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] idxArr = {0,0};
        for(int i=0;i<nums.length;i++) 
        	for(int j=nums.length-1;j>i;j--) {
        		if (nums[j]+nums[i]==target) {
        			idxArr[0] = i;
        			idxArr[1] = j;
        			return idxArr;
        		}
        	}
        
        return idxArr;        
    }
}

Submission Detail

20 / 20 test cases passed.
Your runtime beats 30.47 % of java submissions.

Hash Table

class Solution {
    public int[] twoSum(int[] nums, int target) {
		int a = 0, b = 0;
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < nums.length; i++) {
			int complement = target - nums[i];
			if (map.containsKey(complement)) {
				a = i;
				b = map.get(complement);
			} else {
				map.put(nums[i], i);
			}
		}
		return new int[]{a, b};
    }
}

Submission Detail

29 / 29 test cases passed.
Runtime: 2 ms, faster than 72.04% of Java online submissions for Two Sum.
Memory Usage: 39.2 MB, less than 98.23% of Java online submissions for Two Sum.

Database

175. Combine Two Tables

mysql

1
2
3

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

Submission Detail

7 / 7 test cases passed.
Your runtime beats 84.70 % of mysql submissions.

Transact-SQL

1
2
3

SELECT P.firstName AS 'firstName', P.lastName AS 'lastName', A.city AS 'city', A.state AS 'state' 
FROM Person AS P 
LEFT OUTER JOIN Address AS A ON A.personId = P.personId

Submission Detail

8 / 8 test cases passed.
Your runtime beats 44.40 % of mssql submissions.

176. Second Highest Salary

mysql

1

1 2	select IF(count(distinct Salary)>1,min(t.Salary),null) SecondHighestSalary from (select Salary from Employee order by Salary desc limit 2) t

Submission Detail

7 / 7 test cases passed.
Your runtime beats 90.90 % of mysql submissions.

2

select
(
select distinct Salary from Employee order by Salary desc limit 1,1
) AS SecondHighestSalary

Submission Detail

7 / 7 test cases passed.
Your runtime beats 88.73 % of mysql submissions.

Transact-SQL

SELECT 
CASE 
WHEN COUNT(V.salary) > 1 THEN MIN(V.salary) 
ELSE NULL 
END AS 'SecondHighestSalary' FROM 
(
    SELECT TOP 2 SA.salary FROM 
    (
    SELECT DISTINCT EM.salary 
    FROM Employee AS EM
    ) AS SA 
    ORDER BY SA.salary DESC
) AS V

Submission Detail

8 / 8 test cases passed.
Runtime: 603 ms, faster than 85.83% of MS SQL Server online submissions for Second Highest Salary.
Memory Usage: 0B, less than 100.00% of MS SQL Server online submissions for Second Highest Salary.

177. Nth Highest Salary

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
  DECLARE fromRow INT;
  SET fromRow = N-1;
  RETURN (select (select distinct Salary from Employee order by Salary desc limit 1 offset fromRow));
END

Submission Detail

14 / 14 test cases passed.
Your runtime beats 86.66 % of mysql submissions.

178. Rank Scores

select a.Score,b.`Rank` from Scores a,
(
select t.Score,(@row_number:=@row_number+1) as `Rank` from 
(
select distinct Score from Scores order by Score desc
) t,(SELECT @row_number:=0) t2
) b
where a.Score=b.Score 
order by a.Score desc

Submission Detail

10 / 10 test cases passed.
Your runtime beats 98.24 % of mysql submissions.

181. Employees Earning More Than Their Managers

1	select t.Name as Employee from Employee t where t.Salary>(select e.Salary from Employee e where e.Id=t.ManagerId)

Submission Detail

14 / 14 test cases passed.
Your runtime beats 39.24 % of mysql submissions.

182. Duplicate Emails

1 2	select t.Email as Email from (select Email,count(Email) from Person group by Email having count(Email)>1) t

Submission Detail

15 / 15 test cases passed.
Your runtime beats 76.83 % of mysql submissions.

183. Customers Who Never Order

1

1 2	select c.Name as Customers from Customers c where c.Id not in (select distinct o.CustomerId from Orders o)

Submission Detail

12 / 12 test cases passed.
Your runtime beats 84.65 % of mysql submissions.

2

1
2
3

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

Submission Detail

12 / 12 test cases passed.
Your runtime beats 83.24 % of mysql submissions

196. Delete Duplicate Emails

虽然难度标为Easy，居然也被卡住了，还以为要用临时表，google关键字 mysql delete duplicate rows keep one搜到Delete all Duplicate Rows except for One in MySQL? [duplicate]，原来是自己未完全理解mysql的delete关于多表删除的语法。

DELETE [LOW_PRIORITY] [QUICK] [IGNORE]
tbl_name[.*] [, tbl_name[.*]] ...
FROM table_references
[WHERE where_condition]

Or:

DELETE [LOW_PRIORITY] [QUICK] [IGNORE]
FROM tbl_name[.*] [, tbl_name[.*]] ...
USING table_references
[WHERE where_condition]

看来这种技术问题，google+stack overflow 一点就破，自己坚持独立思考在那里死磕纯属浪费时间。

1

1	delete p from Person as p, Person as t where p.Id>t.Id and p.Email=t.Email;

Submission Detail

22 / 22 test cases passed.
Your runtime beats 18.50 % of mysql submissions.

2

1	delete p from Person as p, Person as t where p.Email=t.Email and p.Id>t.Id;

Submission Detail

22 / 22 test cases passed.
Your runtime beats 83.82 % of mysql submissions.

3

1	delete p from Person as p inner join Person as t where p.Email=t.Email and p.Id>t.Id;

Submission Detail

22 / 22 test cases passed.
Your runtime beats 80.14 % of mysql submissions.

180. Consecutive Numbers

被卡了好几天，百思不得其解，又开始怀疑是不是select还不足以，难道要用到游标与临时表之类，再琢磨下去也是浪费时间，遇到什么问题，就去问google，尤其是这种自己不会别人会的技术问题，搜 mysql consecutive queries 定位到 MySQL query for 3 consecutive integers between records，冥思苦想就是想不对路，一看到人家的解就恍然大悟，自己怎么会想不到这一点，看来自己的sql还是需要外部启发，没有点拨，自己就迷失在思维定势里了。

不过这题有点让人犯糊涂，如果id不连续呢？那是不是还得用计算列row_num?反正题意是id连续

1
2
3

select distinct t.Num as ConsecutiveNums from Logs t
where exists (select 1 from Logs x where x.Id-1=t.Id and x.Num=t.Num) and 
exists(select 1 from Logs x where x.Id+1=t.Id and x.Num=t.Num);

Submission Detail

21 / 21 test cases passed.
Your runtime beats 50.90 % of mysql submissions.

185. Department Top Three Salaries

琢磨了好几天也没思路，问题的难度标为hard，难道用select无法实现？难道要用到cursor与临时表？最后google -> mysql top 3 per group在Stack Overflow找到Get top n records for each group of grouped results，思路顿开，原来还是要用到查询结果序号的计算列，T-SQL与PL/SQL都有Rank()函数，mysql可以用变量模拟实现，在178. Rank Scores中已经用到，只是本题需要用到两个列，需要用两个@变量。

select d.Name as Department,e.Name as Employee,b.Salary as Salary from 
(
select a.DepartmentId,a.Salary from 
(
select t.DepartmentId,t.Salary,(@num:=if(@deptId = t.DepartmentId, @num +1, if(@deptId := t.DepartmentId, 1, 1))) as row_number from 
(
select distinct DepartmentId,Salary from Employee
) t 
CROSS JOIN (select @num:=0, @deptId:=null) c  
order by t.DepartmentId,t.Salary desc
) a 
where a.row_number<=3
) b 
left outer join Employee e using(DepartmentId,Salary) 
inner join Department d on e.DepartmentId=d.Id 
order by b.DepartmentId,b.Salary desc;

Submission Detail

20 / 20 test cases passed.
Your runtime beats 98.70 % of mysql submissions.

184. Department Highest Salary

也蒙了几天，group by得到部门max salary是显然的，怎么得到员工姓名？发现用部门id与salary同时作为join的条件就ok了，用using连接从句显得更自然。

1

select d.Name as Department,e.Name as Employee,t.Salary from Department d 
left outer join (select DepartmentId,Max(Salary) as Salary from Employee group by DepartmentId) t on t.DepartmentId=d.Id 
inner join Employee e on t.Salary=e.Salary and t.DepartmentId=e.DepartmentId 
order by t.Salary desc;

Submission Detail

15 / 15 test cases passed.
Your runtime beats 77.87 % of mysql submissions.

2

select d.Name as Department,e.Name as Employee,t.Salary from Department d 
left outer join (select DepartmentId,Max(Salary) as Salary from Employee group by DepartmentId) t on d.Id=t.DepartmentId 
inner join Employee e on e.DepartmentId=t.DepartmentId and e.Salary=t.Salary 
order by t.Salary desc;

Submission Detail

15 / 15 test cases passed.
Your runtime beats 87.87 % of mysql submissions.

3

select d.Name as Department,e.Name as Employee,t.Salary from Department d 
left outer join (select DepartmentId,Max(Salary) as Salary from Employee group by DepartmentId) t on d.Id=t.DepartmentId 
inner join Employee e using(DepartmentId,Salary) 
order by t.Salary desc;

Submission Detail

15 / 15 test cases passed.
Your runtime beats 91.84 % of mysql submissions.

197. Rising Temperature

这题果然Easy, 不过自己还是在mysql手册里查了下函数DATEDIFF(expr1,expr2)，不用google就ok了，在LeetCode第一次就通过了，此题的问题结构好像跟 180. Consecutive Numbers 类似。

想到人家刷LeetCode都是光用脑子调代码直接在网页上Run，而自己离不开IDE与数据库运行环境，人家那叫刷题，自己只是在做题。

1	select w.Id from Weather w, Weather t where datediff(w.RecordDate,t.RecordDate)=1 and w.Temperature>t.Temperature;

Submission Detail

14 / 14 test cases passed.
Your runtime beats 90.59 % of mysql submissions.

262. Trips and Users

这题又耗了两天，一开始没看懂题意，虽然不能迅速做不出，倒也没怎么被卡住，不过免不了又要在纸上比划一下，还有在mysql上一遍遍执行验证想法，也没啥可以google的，提交Leetcode第一遍就通过了，没想到。自己对left outer join与right outer join的理解似乎有误，这两者是有区别的，自己之前似乎以为这两者是对称的。

1

select b.Request_at as Day,round(IFNull(a.cancel_num,0)/b.total_num,2) as `Cancellation Rate` from 
(
select t.Request_at,count(*) as cancel_num from Trips t 
where t.Client_Id in (select Users_Id from Users where Role='client' and Banned='No') and 
t.Driver_Id in (select Users_Id from Users where Role='driver' and Banned='No') and 
t.Status in ('cancelled_by_driver','cancelled_by_client') and t.Request_at between DATE '2013-10-01' and DATE '2013-10-03' 
group by t.Request_at
) a right outer join 
(
select t.Request_at,count(*) as total_num from Trips t 
where t.Client_Id in (select Users_Id from Users where Role='client' and Banned='No') and 
t.Driver_Id in (select Users_Id from Users where Role='driver' and Banned='No') and t.Request_at between DATE '2013-10-01' and DATE '2013-10-03'  
group by t.Request_at
) b on b.Request_at=a.Request_at;

Submission Detail

9 / 9 test cases passed.
Your runtime beats 82.92 % of mysql submissions.

2

select a.Request_at as Day,round(IFNull(b.cancel_num,0)/a.total_num,2) as `Cancellation Rate` from 
(
select t.Request_at,count(*) as total_num from Trips t 
where t.Client_Id in (select Users_Id from Users where Role='client' and Banned='No') and 
t.Driver_Id in (select Users_Id from Users where Role='driver' and Banned='No') and t.Request_at between DATE '2013-10-01' and DATE '2013-10-03'  
group by t.Request_at
) a left outer join 
(
select t.Request_at,count(*) as cancel_num from Trips t 
where t.Client_Id in (select Users_Id from Users where Role='client' and Banned='No') and 
t.Driver_Id in (select Users_Id from Users where Role='driver' and Banned='No') and 
t.Status in ('cancelled_by_driver','cancelled_by_client') and t.Request_at between DATE '2013-10-01' and DATE '2013-10-03' 
group by t.Request_at
) b on b.Request_at=a.Request_at;

Submission Detail

9 / 9 test cases passed.
Your runtime beats 61.34 % of mysql submissions.

595. Big Countries

这题确实Easy，or条件或用据说性能更好的 union (Set operations)

1

1	select name,population,area from World where area>3000000 or population>25000000;

Submission Detail

4 / 4 test cases passed.

2

1
2
3

select name,population,area from World where area>3000000 
union 
select name,population,area from World where population>25000000;

Submission Detail

4 / 4 test cases passed.

596. Classes More Than 5 Students

这题也Easy，group by + having子句

select t.`class` as `class` from 
(
select `class`,count(distinct student) as n from courses group by `class` having n>=5
) t;

Submission Detail

9 / 9 test cases passed.

601. Human Traffic of Stadium

这题又被卡了好几天，google也没搜到什么直接的线索，PL/SQL与T-SQL有分析函数ROW_NUMBER(), RANK(), and DENSE_RANK()，还以为需要mysql模拟这种功能。

卡在这一步里

select s.* from stadium s where s.people>=100 
and exists(select 1 from stadium t2 where t2.people>=100 and t2.`date`=DATE_SUB(s.`date`,INTERVAL 1 DAY)) 
and exists(select 1 from stadium t3 where t3.people>=100 and t3.`date`=DATE_ADD(s.`date`,INTERVAL 1 DAY));

最后发现用 join + union就好了，显示执行效率不高，可能还有更好的写法

select x.* from 
(
select a.* from 
(select s.* from stadium s where s.people>=100) a,
(
select s.* from stadium s where s.people>=100 
and exists(select 1 from stadium t2 where t2.people>=100 and t2.id=s.id-1) 
and exists(select 1 from stadium t3 where t3.people>=100 and t3.id=s.id+1)
) b 
where a.id=b.id-1  

union 

select s.* from stadium s where s.people>=100 
and exists(select 1 from stadium t2 where t2.people>=100 and t2.id=s.id-1) 
and exists(select 1 from stadium t3 where t3.people>=100 and t3.id=s.id+1)

union 

select c.* from 
(
select s.* from stadium s where s.people>=100 
and exists(select 1 from stadium t2 where t2.people>=100 and t2.id=s.id-1) 
and exists(select 1 from stadium t3 where t3.people>=100 and t3.id=s.id+1)
) b,
(select s.* from stadium s where s.people>=100) c
where c.id=b.id+1
) x order by x.id;

Submission Detail

14 / 14 test cases passed.
Your runtime beats 57.13 % of mysql submissions.

620. Not Boring Movies

这题确实Easy，可以不假思索地写出SQL，但执行效率还是不够高，而且也查了下MOD函数与mod运算符。

1	select * from cinema where id%2=1 and description not like '%boring%' order by rating desc;

Submission Detail

8 / 8 test cases passed.
Your runtime beats 72.39 % of mysql submissions.

Submission Detail

626. Exchange Seats

这题确实Medium，不难，但也不是很简单就能写出，inner join 与 outer join 进行union，执行效率还是不算高。

select * from 
(
select t1.id,t2.student from 
(select * from seat where id%2=1) t1 join 
(select * from seat where id%2=0) t2 on t1.id=t2.id-1 

union 

select IFNULL(t2.id,t1.id) as id,t1.student from 
(select * from seat where id%2=1) t1 left outer join 
(select * from seat where id%2=0) t2 on t1.id=t2.id-1
) t order by id;

Submission Detail

12 / 12 test cases passed.
Your runtime beats 58.11 % of mysql submissions.

627. Swap Salary

算是Easy吧，不过还是看了下mysql的update语法，用IF()函数或者 case 都可以。

1

1	update salary set sex=IF(sex='m','f','m');

Submission Detail

8 / 8 test cases passed.
Your runtime beats 53.28 % of mysql submissions.

2

1	update salary set sex=case sex when 'm' then 'f' when 'f' then 'm' end;

Submission Detail

8 / 8 test cases passed.
Your runtime beats 49.22 % of mysql submissions.

Shell

195. Tenth Line

自己对linux shell果然是一无所知，连这个Easy的题也需要google 搜 linux sh read nth line，到 Bash tool to get nth line from a file，原来有个sed命令可以很简单地实现读第n行，此题存在一题多解，需要举一反三

1
2
3

#!/usr/bin/env bash

sed '10q;d' 'file.txt'

Submission Detail

7 / 7 test cases passed.

193. Valid Phone Numbers

linux shell的题自己本来就不懂，只能从头学起，想也没用，不如google，linux shell regex phone number，直接出来个原题的答案，Regex Coding Exercise – Valid Phone Numbers，一个要点是正则表达式，一个要点是Linux的grep命令，学习了。这篇文章里说用 awk 或 sed 也行。题目要求用1行shell解决，也搜到个 Valid Phone Numbers with shell script 是用shell 的while及if语句来实现。

1
2
3

#!/usr/bin/env bash

grep -P "^((\([0-9]{3}\) )|([0-9]{3}\-))[0-9]{3}\-[0-9]{4}$" file.txt

Submission Detail

26 / 26 test cases passed.

192. Word Frequency

这题标为medium，linux shell自己本来就不了解，又有点难度，独立思考不过是浪费时间，不如看看相关专题博客，google关键字linux shell word frequency，搜到 How to create a frequency list of every word in a file?，参考里面的左试右试总是不太对，又搜到个答案大全 Shell Coding Exercise – Word Frequency，人家高手一题多解给出N种异曲同工的方法，用了很多linux的内置功能命令比如cat, tr, awk, sed, sort,grep, uniq，自己也看不大懂，又参考评论里的解释改了下，原来是要sort两次，第二次逆序sort，终于运行通过，但效率不高。

1	sed -r 's/\s+/\n/g' words.txt \| grep -v "^$" \| sort \| uniq -c \| sort -r \| awk '{print $2" "$1}'

Submission Detail

14 / 14 test cases passed.

194. Transpose File

google关键字shell command transpose，搜到 An efficient way to transpose a file in Bash ，原来是要用awk写一小段程序，还没看懂，只有慢慢消息理解了。

Transposing rows and columns: 3 methods 则提到

Transposing rows and columns is indeed easy if you have the GNU datamash utility on your system.
The mighty text-processing program AWK can also do transposing.

对高手来说，方法多得很，殊途同归，条条道路通罗马。

自己的linux shell要学的东西比sql要多得多，sql好歹工作当中经常用，linux shell用得少就处处是问题，形式上先过上一遍，还得慢慢消化理解。

awk '
{ 
    for (i=1; i<=NF; i++)  {
        a[NR,i] = $i
    }
}
NF>p { p = NF }
END {    
    for(j=1; j<=p; j++) {
        str=a[1,j]
        for(i=2; i<=NR; i++){
            str=str" "a[i,j];
        }
        print str
    }
}' file.txt

Submission Detail

17 / 17 test cases passed.
Your runtime beats 11.53 % of bash submissions.