RexKing6's Note

LeetCode记录

发表于 更新于 分类于 阅读次数：
23k 21 分钟

Shell

195. Tenth Line

How would you print just the 10th line of a file?
For example, assume that file.txt has the following content:

1
2
3
4
5
6
7
8
9
10
Line 1
Line 2
Line 3
Line 4
Line 5
Line 6
Line 7
Line 8
Line 9
Line 10

Your script should output the tenth line, which is:

Line 10

Solutions

sed

sed -n '10p' file.txt

awk

awk 'FNR==10' file.txt

tail

tail -n+10 file.txt|head -1

head -n+10 file.txt|tail -1

手动

1
2
3
4
5
6
7
8
cnt=0
while read line && [ $cnt -le 10 ]; do
  let 'cnt = cnt + 1'
  if [ $cnt -eq 10 ]; then
    echo $line
    exit 0
  fi
done < file.txt

193. Valid Phone Numbers

Given a text file file.txt that contains list of phone numbers (one per line), write a one liner bash script to print all valid phone numbers.

You may assume that a valid phone number must appear in one of the following two formats: (xxx) xxx-xxxx or xxx-xxx-xxxx. (x means a digit)

You may also assume each line in the text file must not contain leading or trailing white spaces.

For example, assume that file.txt has the following content:

1
2
3
987-123-4567
123 456 7890
(123) 456-7890

Your script should output the following valid phone numbers:

1
2
987-123-4567
(123) 456-7890

Solutions

一开始写的时候只注意到了EREs不能用\d、\w，然后就老老实实地换成了[[:digit:]]：

egrep "(^\([[:digit:]]{3}\)[[:space:]]|^[[:digit:]]{3}\-)[[:digit:]]{3}\-[[:digit:]]{4}$" file.txt

之后看别人提交才发现加”-P”就可以换成PREs，就可以用\d、\w，这是别人的提交：

grep -P '^(\d{3}-|\(\d{3}\) )\d{3}-\d{4}$' file.txt

192. Word Frequency

Write a bash script to calculate the frequency of each word in a text file words.txt.

For simplicity sake, you may assume:

  • words.txt contains only lowercase characters and space ' ' characters.
  • Each word must consist of lowercase characters only.
  • Words are separated by one or more whitespace characters.
    For example, assume that words.txt has the following content:
    1
    2
    the day is sunny the the
    the sunny is is
    Your script should output the following, sorted by descending frequency:
    1
    2
    3
    4
    the 4
    is 3
    sunny 2
    day 1
    Note:
    Don’t worry about handling ties, it is guaranteed that each word’s frequency count is unique.

    Solutions

    cat words.txt | tr ' ' '\n' | tr -s '\n'| sort | uniq -c | sort -r | awk '{print $2,$1}'
    不难，切成一行一个单词，然后排序计数，再排序就好了。

194. Transpose File

Given a text file file.txt, transpose its content.

You may assume that each row has the same number of columns and each field is separated by the ' ' character.

For example, if file.txt has the following content:

1
2
3
name age
alice 21
ryan 30

Output the following:
1
2
name alice ryan
age 21 30

要用到awk的高级用法，一脸懵逼，答案是网上的：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

Database

595. Big Countries

There is a table World

1
2
3
4
5
6
7
8
9
+-----------------+------------+------------+--------------+---------------+
| name            | continent  | area       | population   | gdp           |
+-----------------+------------+------------+--------------+---------------+
| Afghanistan     | Asia       | 652230     | 25500100     | 20343000      |
| Albania         | Europe     | 28748      | 2831741      | 12960000      |
| Algeria         | Africa     | 2381741    | 37100000     | 188681000     |
| Andorra         | Europe     | 468        | 78115        | 3712000       |
| Angola          | Africa     | 1246700    | 20609294     | 100990000     |
+-----------------+------------+------------+--------------+---------------+

A country is big if it has an area of bigger than 3 million square km or a population of more than 25 million.

Write a SQL solution to output big countries’ name, population and area.

For example, according to the above table, we should output:

1
2
3
4
5
6
+--------------+-------------+--------------+
| name         | population  | area         |
+--------------+-------------+--------------+
| Afghanistan  | 25500100    | 652230       |
| Algeria      | 37100000    | 2381741      |
+--------------+-------------+--------------+

Solutions

SELECT name,population,area FROM World WHERE population>25000000 OR area>3000000;
很容易，注意million是百万。

627. Swap Salary

Given a table salary, such as the one below, that has m=male and f=female values. Swap all f and m values (i.e., change all f values to m and vice versa) with a single update query and no intermediate temp table.

For example:

1
2
3
4
5
6
| id | name | sex | salary |
|----|------|-----|--------|
| 1  | A    | m   | 2500   |
| 2  | B    | f   | 1500   |
| 3  | C    | m   | 5500   |
| 4  | D    | f   | 500    |

After running your query, the above salary table should have the following rows:
1
2
3
4
5
6
| id | name | sex | salary |
|----|------|-----|--------|
| 1  | A    | f   | 2500   |
| 2  | B    | m   | 1500   |
| 3  | C    | f   | 5500   |
| 4  | D    | m   | 500    |

Solutions

sql还是学得太基础了，我自己用的很蠢的方法：

1
2
3
UPDATE salary SET sex='s' WHERE sex='f';
UPDATE salary SET sex='f' WHERE sex='m';
UPDATE salary SET sex='m' WHERE sex='s';

看了别人的答案才知道SQL有case when then else end用法：
1
2
3
4
5
6
7
8
9
--简单Case函数
CASE sex
         WHEN '1' THEN '男'
         WHEN '2' THEN '女'
ELSE '其他' END
--Case搜索函数
CASE WHEN sex = '1' THEN '男'
         WHEN sex = '2' THEN '女'
ELSE '其他' END

所有这题用上来就是：
1
2
3
4
5
6
7
update salary
    set sex=(
        case when sex = 'f' then 'm'
				when sex = 'm' then 'f'
				else sex
    end
    )

620. Not Boring Movies

X city opened a new cinema, many people would like to go to this cinema. The cinema also gives out a poster indicating the movies’ ratings and descriptions.

Please write a SQL query to output movies with an odd numbered ID and a description that is not ‘boring’. Order the result by rating.

For example, table cinema:

1
2
3
4
5
6
7
8
9
+---------+-----------+--------------+-----------+
|   id    | movie     |  description |  rating   |
+---------+-----------+--------------+-----------+
|   1     | War       |   great 3D   |   8.9     |
|   2     | Science   |   fiction    |   8.5     |
|   3     | irish     |   boring     |   6.2     |
|   4     | Ice song  |   Fantacy    |   8.6     |
|   5     | House card|   Interesting|   9.1     |
+---------+-----------+--------------+-----------+

For the example above, the output should be:
1
2
3
4
5
6
+---------+-----------+--------------+-----------+
|   id    | movie     |  description |  rating   |
+---------+-----------+--------------+-----------+
|   5     | House card|   Interesting|   9.1     |
|   1     | War       |   great 3D   |   8.9     |
+---------+-----------+--------------+-----------+

Solutions

SELECT * FROM cinema WHERE id%2=1 AND description!='boring' ORDER BY rating DESC;

182. Duplicate Emails

Write a SQL query to find all duplicate emails in a table named Person.

1
2
3
4
5
6
7
+----+---------+
| Id | Email   |
+----+---------+
| 1  | a@b.com |
| 2  | c@d.com |
| 3  | a@b.com |
+----+---------+

For example, your query should return the following for the above table:
1
2
3
4
5
+---------+
| Email   |
+---------+
| a@b.com |
+---------+

Note: All emails are in lowercase.

Solutions

这题有点搞不懂，一开始是想过GROUP BY的，但是GROUP BY的结果貌似是多个子表的，我以为结果是要一张表的，所以一开始思路就奔着整表和去重表求差集再去重的。然后又因为MySQL没有差集和交集的操作，又陷入LEFT JOIN的坑中。

看了下解答才知道用GROUP BY：

1
2
3
4
SELECT Email
FROM Person
GROUP BY Email
HAVING COUNT(Email) > 1;

175. Combine Two Tables

Table: Person

1
2
3
4
5
6
7
8
+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| PersonId    | int     |
| FirstName   | varchar |
| LastName    | varchar |
+-------------+---------+
PersonId is the primary key column for this table.

Table: Address
1
2
3
4
5
6
7
8
9
+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| AddressId   | int     |
| PersonId    | int     |
| City        | varchar |
| State       | varchar |
+-------------+---------+
AddressId is the primary key column for this table.

Write a SQL query for a report that provides the following information for each person in the Person table, regardless if there is an address for each of those people:
FirstName, LastName, City, State

Solutions

因为是由Person找Address的，所以允许Address为空，用LEFT JOIN：
SELECT FirstName, LastName, City, State FROM Person LEFT JOIN Address ON Person.PersonId=Address.PersonId;

181. Employees Earning More Than Their Managers

The Employee table holds all employees including their managers. Every employee has an Id, and there is also a column for the manager Id.

1
2
3
4
5
6
7
8
+----+-------+--------+-----------+
| Id | Name  | Salary | ManagerId |
+----+-------+--------+-----------+
| 1  | Joe   | 70000  | 3         |
| 2  | Henry | 80000  | 4         |
| 3  | Sam   | 60000  | NULL      |
| 4  | Max   | 90000  | NULL      |
+----+-------+--------+-----------+

Given the Employee table, write a SQL query that finds out employees who earn more than their managers. For the above table, Joe is the only employee who earns more than his manager.
1
2
3
4
5
+----------+
| Employee |
+----------+
| Joe      |
+----------+

Solutions

1
2
3
4
5
6
7
8
9
10
SELECT
    a.Name AS 'Employee'
FROM
    Employee AS a,
    Employee AS b
WHERE
    a.ManagerId = b.Id
    AND
    a.Salary > b.Salary
;

601. Human Traffic of Stadium

X city built a new stadium, each day many people visit it and the stats are saved as these columns: id, date, people

Please write a query to display the records which have 3 or more consecutive rows and the amount of people more than 100(inclusive).

For example, the table stadium:

1
2
3
4
5
6
7
8
9
10
11
12
+------+------------+-----------+
| id   | date       | people    |
+------+------------+-----------+
| 1    | 2017-01-01 | 10        |
| 2    | 2017-01-02 | 109       |
| 3    | 2017-01-03 | 150       |
| 4    | 2017-01-04 | 99        |
| 5    | 2017-01-05 | 145       |
| 6    | 2017-01-06 | 1455      |
| 7    | 2017-01-07 | 199       |
| 8    | 2017-01-08 | 188       |
+------+------------+-----------+

For the sample data above, the output is:
1
2
3
4
5
6
7
8
+------+------------+-----------+
| id   | date       | people    |
+------+------------+-----------+
| 5    | 2017-01-05 | 145       |
| 6    | 2017-01-06 | 1455      |
| 7    | 2017-01-07 | 199       |
| 8    | 2017-01-08 | 188       |
+------+------------+-----------+

Note:
Each day only have one row record, and the dates are increasing with id increasing.

Solutions

看到题目很懵逼，看到别人的解答，才知道思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
select distinct t1.*
from stadium t1, stadium t2, stadium t3
where t1.people >= 100 and t2.people >= 100 and t3.people >= 100
and
(
      (t1.id - t2.id = 1 and t1.id - t3.id = 2 and t2.id - t3.id =1)  -- t1, t2, t3
    or
    (t2.id - t1.id = 1 and t2.id - t3.id = 2 and t1.id - t3.id =1) -- t2, t1, t3
    or
    (t3.id - t2.id = 1 and t2.id - t1.id =1 and t3.id - t1.id = 2) -- t3, t2, t1
)
order by t1.id
;

子查询难做，考虑先得到所有情况之后后再筛选情况，分解出来就是：

  1. 所有组合先筛选出3天都超过100人的；
  2. 再通过id来判断是否连续，存在3种连续情况。

183. Customers Who Never Order

Suppose that a website contains two tables, the Customers table and the Orders table. Write a SQL query to find all customers who never order anything.

Table: Customers.

1
2
3
4
5
6
7
8
+----+-------+
| Id | Name  |
+----+-------+
| 1  | Joe   |
| 2  | Henry |
| 3  | Sam   |
| 4  | Max   |
+----+-------+

Table: Orders.
1
2
3
4
5
6
+----+------------+
| Id | CustomerId |
+----+------------+
| 1  | 3          |
| 2  | 1          |
+----+------------+

Using the above tables as example, return the following:
1
2
3
4
5
6
+-----------+
| Customers |
+-----------+
| Henry     |
| Max       |
+-----------+

Solutions

不难，用in：
SELECT name AS 'Customers' FROM Customers WHERE Customers.Id not in (SELECT CustomerId FROM Orders);

197. Rising Temperature

Given a Weather table, write a SQL query to find all dates’ Ids with higher temperature compared to its previous (yesterday’s) dates.

1
2
3
4
5
6
7
8
+---------+------------+------------------+
| Id(INT) | Date(DATE) | Temperature(INT) |
+---------+------------+------------------+
|       1 | 2015-01-01 |               10 |
|       2 | 2015-01-02 |               25 |
|       3 | 2015-01-03 |               20 |
|       4 | 2015-01-04 |               30 |
+---------+------------+------------------+

For example, return the following Ids for the above Weather table:
1
2
3
4
5
6
+----+
| Id |
+----+
|  2 |
|  4 |
+----+

Solution

这题跟上面一道求连续3天100以上的题目类似，之后有些不一样的地方是，题目没有说明Date是连续递增的，也即是说不能用Id来确定第二天。另外Date的相减不能直接相减，用DATEDIFF()：

1
SELECT a2.Id FROM Weather as a1, Weather as a2 WHERE a2.Temperature>a1.Temperature and DATEDIFF(a2.Date, a1.Date)=1;

178. Rank Scores

Write a SQL query to rank scores. If there is a tie between two scores, both should have the same ranking. Note that after a tie, the next ranking number should be the next consecutive integer value. In other words, there should be no “holes” between ranks.

1
2
3
4
5
6
7
8
9
10
+----+-------+
| Id | Score |
+----+-------+
| 1  | 3.50  |
| 2  | 3.65  |
| 3  | 4.00  |
| 4  | 3.85  |
| 5  | 4.00  |
| 6  | 3.65  |
+----+-------+

For example, given the above Scores table, your query should generate the following report (order by highest score):
1
2
3
4
5
6
7
8
9
10
+-------+------+
| Score | Rank |
+-------+------+
| 4.00  | 1    |
| 4.00  | 1    |
| 3.85  | 2    |
| 3.65  | 3    |
| 3.65  | 3    |
| 3.50  | 4    |
+-------+------+

Solutions

题目很难，查了下大佬们的博客，大致有两种方法：

  1. 用自定义变量：

    1
    2
    3
    4
    5
    6
    SELECT Score,Rank FROM   
    (SELECT Score,  
    @Rank := IF(@prevScore = Score,@Rank,@Rank+1) AS Rank,  
    @prevScore := Score FROM Scores  
    ORDER BY Score DESC) s,   
    (SELECT @Rank := 0, @prevScore := NULL) r;

    然后用IF定义Rank的规则，但是我看不懂，转载自【leetcode Database】178. Rank Scores。

  2. 计数大于等于自己的个数有多少：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    SELECT Score, (  
      SELECT COUNT(*)   
      FROM (  
        SELECT DISTINCT Score S   
        FROM Scores  
      ) AS Tmp  
      WHERE S >= Score  
    ) AS Rank  
    FROM Scores  
    ORDER BY Score DESC;

    膜拜这位大佬，这方法太巧妙了，转载自leetcode 178. Rank Scores

180. Consecutive Numbers

Write a SQL query to find all numbers that appear at least three times consecutively.

1
2
3
4
5
6
7
8
9
10
11
+----+-----+
| Id | Num |
+----+-----+
| 1  |  1  |
| 2  |  1  |
| 3  |  1  |
| 4  |  2  |
| 5  |  1  |
| 6  |  2  |
| 7  |  2  |
+----+-----+

For example, given the above Logs table, 1 is the only number that appears consecutively for at least three times.
1
2
3
4
5
+-----------------+
| ConsecutiveNums |
+-----------------+
| 1               |
+-----------------+

Solutions

有了之前的套路，这种题照着做就好了：

1
2
3
4
5
6
SELECT DISTINCT l1.Num AS ConsecutiveNums 
    FROM Logs AS l1, Logs AS l2, Logs AS l3 
    WHERE l1.Num=l2.Num 
        AND l2.Num=l3.Num 
        AND l3.Id-l2.Id=1 
        AND l2.Id-l1.Id=1;

596. Classes More Than 5 Students

There is a table courses with columns: student and class

Please list out all classes which have more than or equal to 5 students.

For example, the table:

1
2
3
4
5
6
7
8
9
10
11
12
13
+---------+------------+
| student | class      |
+---------+------------+
| A       | Math       |
| B       | English    |
| C       | Math       |
| D       | Biology    |
| E       | Math       |
| F       | Computer   |
| G       | Math       |
| H       | Math       |
| I       | Math       |
+---------+------------+

Should output:
1
2
3
4
5
+---------+
| class   |
+---------+
| Math    |
+---------+

Solutions

不难，注意row有可能重复的，去下重：

1
2
3
4
5
6
7
SELECT class 
FROM (
    SELECT DISTINCT * 
    FROM courses
    ) Dc 
    GROUP BY class 
    HAVING count(*)>=5;

196. Delete Duplicate Emails

Write a SQL query to delete all duplicate email entries in a table named Person, keeping only unique emails based on its smallest Id.

1
2
3
4
5
6
7
8
+----+------------------+
| Id | Email            |
+----+------------------+
| 1  | john@example.com |
| 2  | bob@example.com  |
| 3  | john@example.com |
+----+------------------+
Id is the primary key column for this table.

For example, after running your query, the above Person table should have the following rows:
1
2
3
4
5
6
+----+------------------+
| Id | Email            |
+----+------------------+
| 1  | john@example.com |
| 2  | bob@example.com  |
+----+------------------+

Solutions

题目不难，一开始往着GROUP BY之后取Id的最小值就好。之后才注意题目要求的是，经过运行语句之后，Person表的样子，所以默认应该是读取Person表，所以这里应该用DML：

1
2
3
4
DELETE p1 FROM Person p1,
    Person p2
WHERE
    p1.Email = p2.Email AND p1.Id > p2.Id

176. Second Highest Salary

Write a SQL query to get the second highest salary from the Employee table.

1
2
3
4
5
6
7
+----+--------+
| Id | Salary |
+----+--------+
| 1  | 100    |
| 2  | 200    |
| 3  | 300    |
+----+--------+

For example, given the above Employee table, the query should return 200 as the second highest salary. If there is no second highest salary, then the query should return null.
1
2
3
4
5
+---------------------+
| SecondHighestSalary |
+---------------------+
| 200                 |
+---------------------+

Solutions

1
2
3
4
5
6
7
SELECT
    IFNULL(
      (SELECT DISTINCT Salary
       FROM Employee
       ORDER BY Salary DESC
        LIMIT 1 OFFSET 1),
    NULL) AS SecondHighestSalary

一开始是想按之前算名次的方法算的，但是绕不过来，就看解答了，原来还有OFFSET这个东西。OFFSET是跳过n行，LIMIT是提取n行。然后再用IFNULL()给没有时加NULL。

184. Department Highest Salary

The Employee table holds all employees. Every employee has an Id, a salary, and there is also a column for the department Id.

1
2
3
4
5
6
7
8
+----+-------+--------+--------------+
| Id | Name  | Salary | DepartmentId |
+----+-------+--------+--------------+
| 1  | Joe   | 70000  | 1            |
| 2  | Henry | 80000  | 2            |
| 3  | Sam   | 60000  | 2            |
| 4  | Max   | 90000  | 1            |
+----+-------+--------+--------------+

The Department table holds all departments of the company.
1
2
3
4
5
6
+----+----------+
| Id | Name     |
+----+----------+
| 1  | IT       |
| 2  | Sales    |
+----+----------+

Write a SQL query to find employees who have the highest salary in each of the departments. For the above tables, Max has the highest salary in the IT department and Henry has the highest salary in the Sales department.
1
2
3
4
5
6
+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Max      | 90000  |
| Sales      | Henry    | 80000  |
+------------+----------+--------+

Solutions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
SELECT
    Department.name AS 'Department',
    Employee.name AS 'Employee',
    Salary
FROM
    Employee
        JOIN
    Department ON Employee.DepartmentId = Department.Id
WHERE
    (Employee.DepartmentId , Salary) IN
    (   SELECT
            DepartmentId, MAX(Salary)
        FROM
            Employee
        GROUP BY DepartmentId
    )
;

177. Nth Highest Salary

Write a SQL query to get the nth highest salary from the Employee table.

1
2
3
4
5
6
7
+----+--------+
| Id | Salary |
+----+--------+
| 1  | 100    |
| 2  | 200    |
| 3  | 300    |
+----+--------+

For example, given the above Employee table, the nth highest salary where n = 2 is 200. If there is no nth highest salary, then the query should return null.
1
2
3
4
5
+------------------------+
| getNthHighestSalary(2) |
+------------------------+
| 200                    |
+------------------------+

Solutions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
  SET N = N - 1;
  RETURN (
    SELECT CASE 
    WHEN COUNT(Salary) >= 1 THEN (
      SELECT DISTINCT Salary 
      FROM Employee
      ORDER BY Salary DESC 
      LIMIT N, 1) 
    ELSE NULL
    END AS NthSalary
    FROM Employee
  );
END

185. Department Top Three Salaries

The Employee table holds all employees. Every employee has an Id, and there is also a column for the department Id.

1
2
3
4
5
6
7
8
9
10
+----+-------+--------+--------------+
| Id | Name  | Salary | DepartmentId |
+----+-------+--------+--------------+
| 1  | Joe   | 70000  | 1            |
| 2  | Henry | 80000  | 2            |
| 3  | Sam   | 60000  | 2            |
| 4  | Max   | 90000  | 1            |
| 5  | Janet | 69000  | 1            |
| 6  | Randy | 85000  | 1            |
+----+-------+--------+--------------+

The Department table holds all departments of the company.
1
2
3
4
5
6
+----+----------+
| Id | Name     |
+----+----------+
| 1  | IT       |
| 2  | Sales    |
+----+----------+

Write a SQL query to find employees who earn the top three salaries in each of the department. For the above tables, your SQL query should return the following rows.
1
2
3
4
5
6
7
8
9
+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Max      | 90000  |
| IT         | Randy    | 85000  |
| IT         | Joe      | 70000  |
| Sales      | Henry    | 80000  |
| Sales      | Sam      | 60000  |
+------------+----------+--------+

Solutions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
SELECT
    d.Name AS 'Department', e1.Name AS 'Employee', e1.Salary
FROM
    Employee e1
        JOIN
    Department d ON e1.DepartmentId = d.Id
WHERE
    3 > (SELECT
            COUNT(DISTINCT e2.Salary)
        FROM
            Employee e2
        WHERE
            e2.Salary > e1.Salary
                AND e1.DepartmentId = e2.DepartmentId
        )
;

262. Trips and Users

The Trips table holds all taxi trips. Each trip has a unique Id, while Client_Id and Driver_Id are both foreign keys to the Users_Id at the Users table. Status is an ENUM type of (‘completed’, ‘cancelled_by_driver’, ‘cancelled_by_client’).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
+----+-----------+-----------+---------+--------------------+----------+
| Id | Client_Id | Driver_Id | City_Id |        Status      |Request_at|
+----+-----------+-----------+---------+--------------------+----------+
| 1  |     1     |    10     |    1    |     completed      |2013-10-01|
| 2  |     2     |    11     |    1    | cancelled_by_driver|2013-10-01|
| 3  |     3     |    12     |    6    |     completed      |2013-10-01|
| 4  |     4     |    13     |    6    | cancelled_by_client|2013-10-01|
| 5  |     1     |    10     |    1    |     completed      |2013-10-02|
| 6  |     2     |    11     |    6    |     completed      |2013-10-02|
| 7  |     3     |    12     |    6    |     completed      |2013-10-02|
| 8  |     2     |    12     |    12   |     completed      |2013-10-03|
| 9  |     3     |    10     |    12   |     completed      |2013-10-03| 
| 10 |     4     |    13     |    12   | cancelled_by_driver|2013-10-03|
+----+-----------+-----------+---------+--------------------+----------+

The Users table holds all users. Each user has an unique Users_Id, and Role is an ENUM type of (‘client’, ‘driver’, ‘partner’).
1
2
3
4
5
6
7
8
9
10
11
12
+----------+--------+--------+
| Users_Id | Banned |  Role  |
+----------+--------+--------+
|    1     |   No   | client |
|    2     |   Yes  | client |
|    3     |   No   | client |
|    4     |   No   | client |
|    10    |   No   | driver |
|    11    |   No   | driver |
|    12    |   No   | driver |
|    13    |   No   | driver |
+----------+--------+--------+

Write a SQL query to find the cancellation rate of requests made by unbanned clients between Oct 1, 2013 and Oct 3, 2013. For the above tables, your SQL query should return the following rows with the cancellation rate being rounded to two decimal places.
1
2
3
4
5
6
7
+------------+-------------------+
|     Day    | Cancellation Rate |
+------------+-------------------+
| 2013-10-01 |       0.33        |
| 2013-10-02 |       0.00        |
| 2013-10-03 |       0.50        |
+------------+-------------------+

Solutions

1
2
3
4
5
6
SELECT t.Request_at AS 'Day', 
ROUND(SUM(IF(t.Status = 'completed', 0, 1)) / COUNT(*), 2) AS 'Cancellation Rate' 
FROM Trips t INNER JOIN Users u ON t.Client_Id = u.Users_Id 
WHERE t.Request_at BETWEEN '2013-10-01' AND '2013-10-03' 
AND u.Banned = 'No' AND u.Role = 'client' 
GROUP BY t.Request_at ORDER BY t.Request_at;

Algorithms

535. Encode and Decode TinyURL

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.

Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

Solutions

这个题目要求是将长url转化成短url，还要求编码和解码。长到短的编码是容易的，短到长的解码我记得是不大可能的，压缩算法好像可以，也针对的是稀疏矩阵。所以寻找的短url和长url之间的关系要么是容易的，要么是记录下来，hash。接下来的参考了LeetCode一个高票讨论，我只是负责转化理解一下。
首先是容易的对应关系就是存为数组，根据数组的长度来转化短url。

1
2
3
4
5
6
7
8
9
10
11
class Codec:

    def __init__(self):
        self.urls = []

    def encode(self, longUrl):
        self.urls.append(longUrl)
        return 'http://tinyurl.com/' + str(len(self.urls) - 1)

    def decode(self, shortUrl):
        return self.urls[int(shortUrl.split('/')[-1])]

作者说这样有几个缺点：

  1. 当重复的长url再度查找时，将会浪费新的短url和存储空间
  2. 别人能够知道总共有多少个url
  3. 别人也可能重复发送同一个长url来得到他们想要的短url
  4. 短url只由数字组成，数量很有限，（另外一个我觉得限制住的是int转换时的数值限制）

所以研究了下题目给的短urlhttp://tinyurl.com/KtLa2U，总共6位，由数字大小字母组成，所以总共有(10+26*2)6=56,800,235,584，然后每次随机选择一个6位长的短url，我自己觉得用hash算法可能更好，不确定。建立两个字典，双向对应，一个是解码，一个是判断是否之前出现过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Codec:

    alphabet = string.ascii_letters + '0123456789'

    def __init__(self):
        self.url2code = {}
        self.code2url = {}

    def encode(self, longUrl):
        while longUrl not in self.url2code:
            code = ''.join(random.choice(Codec.alphabet) for _ in range(6))
            if code not in self.code2url:
                self.code2url[code] = longUrl
                self.url2code[longUrl] = code
        return 'http://tinyurl.com/' + self.url2code[longUrl]

    def decode(self, shortUrl):
        return self.code2url[shortUrl[-6:]]

话说到这里，LeetCode对于这道题的判定是不严格的。因为题目也没有要求说一定要6位长，所以………………空算法也能直接过。

461. Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 231.

Example:

1
2
3
4
5
6
7
8
9
10
Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ?   ?

The above arrows point to positions where the corresponding bits are different.

Solutions

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int hammingDistance(int x, int y) {
        int res = x ^ y;
        int count = 0;
        for(int i = 0; i < 32;i++)
        {
            if((res&1)!=0)
                count++;
            res >>= 1;
        }
        return count;
    }
};

尝试着用c++做，先用异或，1和0为1，0和0为1，1和1为1。之后为了判断最后一个位是否是1，是1的话计数，和1取并操作，当最后一位为1时，结果为1，计数。之后右移一位，判断下一位。最后返回结果。

617. Merge Two Binary Trees

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

Note: The merging process must start from the root nodes of both trees.

Solutions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(t1==NULL && t2==NULL)
            return NULL;
        else if(t1==NULL && t2!=NULL)
            return t2;
        else if(t2==NULL && t1!=NULL)
            return t1;
        else
        {
            t1->val+=t2->val;
            t1->left = mergeTrees(t1->left, t2->left);
            t1->right = mergeTrees(t1->right, t2->right);
            return t1;
        }

    }
};

判断一下各自为不为空的情况，迭代下去即可。

561. Array Partition I

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1:

1
2
3
4
Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:

  1. n is a positive integer, which is in the range of [1, 10000].
  2. All the integers in the array will be in the range of [-10000, 10000].

Solutions

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def arrayPairSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        sum=0
        for i in range(0,len(nums),2):
            sum+=nums[i]
        return sum

排列后按顺序每两个取小求和

537. Complex Number Multiplication

Given two strings representing two complex numbers.

You need to return a string representing their multiplication. Note i2 = -1 according to the definition.

Example 1:

1
2
3
Input: "1+1i", "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

Example 2:
1
2
3
Input: "1+-1i", "1+-1i"
Output: "0+-2i"
Explanation: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i, and you need convert it to the form of 0+-2i.

Note:

  1. The input strings will not have extra blank.
  2. The input strings will be given in the form of a+bi, where the integer a and b will both belong to the range of [-100, 100]. And the output should be also in this form.

Solutions

一开始觉得挺难的，后来发现-是作为符号，运算都写+。另外-1还表示为+-1，这就好办了。分割字符串最后拼接就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def complexNumberMultiply(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        a1=int(a.split('+')[0])
        a2=int(a.split('+')[1].strip('i'))
        b1=int(b.split('+')[0])
        b2=int(b.split('+')[1].strip('i'))
        c1=a1*b1-a2*b2
        c2=a1*b2+a2*b1
        return str(c1)+'+'+str(c2)+'i'

这道题要是用c++做，切割字符串这点可能就要蛋疼许久。
leetcode的提交好像没看到c++的，然后百度了下，好像还是没有，那我也就心安了。

相关文章
一分一毛，也是心意。