60天带你刷完Leetcode【第10天】584 ~ 575

2017-10-11 CS学渣学酥小混混 北美加群小助手Jogchat 北美加群小助手Jogchat

小编们带来刷题系列第10篇了!这此的题目中,还是有很多是SQL的题目,另外的一些是基本的拓展思路的题目。在这一篇中小编尝试给每一题附上我们的参考code,大家可以在阅读过程中先想一个思路,再和我们的code对照~ 另外,code的质量和style我们还是有信心滴


584

题目题解:按题目使用where clause即可。


583 Delete Operation for Two Strings

题目:给两个string代表两个word,问一次删除一个word的一个letter,求删除到两个word完全相同,最少需要几次。

题解:思路很简单,典型的dynamic programming:用 dp[i][j] 表示把 word1.substr(0, i)word2.substr(0, i) 变成相同的所需要的最小步数,这样递推关系如下:

dp[i][0] = i;

dp[0][j] = j;

dp[i][j] = min(dp[i][j-1], dp[i-1][j]) if(i>0 && j>0 && word1[i-1]!=word2[j-1])

这个因为如果末尾的两个字母不同的话,肯定有其一必须要被去掉。

dp[i][j] = dp[i-1][j-1] if(i>0 && j>0 word1[i-1]==word2[j-1])

如果末尾两个字母相同的话,就都保留,因为这样是最小的.


typedef vector<int> vi;
class Solution {
public:
   int minDistance(string word1, string word2) {
       int n1 = word1.size(), n2 = word2.size();
       vector<vi> dp(n1+1, vi(n2+1,0));
       for(int i=0;i<=n1;++i) for(int j=0;j<=n2;++j){
           if(!i) dp[i][j] = j;
           else if(!j) dp[i][j] = i;
           else{
               dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1;
               if(word1[i-1]==word2[j-1]) dp[i][j] = min(dp[i][j], dp[i-1][j-1]);
           }
       }
       return dp[n1][n2];
   }
};


582 Kill Process

题目:给出n个进程process,每个process用一个unique的PID(process id)表示。另外每个process还有一个PPID(parent process id). 如果kill一个process,那它所有的children process都会被kill,就像一颗binary tree的一个node被delete一样。现在给出两个array分别代表PIDPPID,再给出一个要被kill的process,求所有会被kill的process的list。

题解:其实就是给定一个树,给定树上一个节点,求砍掉该节点之后,有哪些节点被连带砍掉了(也就是求子树)。一个queue就OK了,跟BFS搜索完全一样。

#include<cassert>
class Solution {
public:
   vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
       unordered_map<int, vector<int>> child;
       assert(pid.size() == ppid.size());
       for(int i=0;i<pid.size();++i) child[ppid[i]].push_back(pid[i]);
       vector<int> ans{kill};
       queue<int> Q;
       Q.push(kill);
       while(!Q.empty()){
           int k = Q.front();
           Q.pop();
           for(int j:child[k]){
               ans.push_back(j);
               Q.push(j);
           }
       }
       return ans;
   }
};


581 Shortest Unsorted Continuous Subarray

题目给出一个array,求一段最短的continuous subarray,使得只要sort这段array,那么整个array都会被sort

题解:这是道 easy , 规模 10^5,所以最简单的方法就是把原序列 sort 一遍,然后比较首尾即可。这样做的时间复杂度是 O(n log n) .

以下解法是 O(n) ,自己看,不难理解。

class Solution {
public:
   int findUnsortedSubarray(vector<int>& nums) {
       int ans = nums.size(), n = nums.size(), cnt = 1;
       for(int i=1,m=nums[0];i<n;++i){
           if(nums[i]>=m) ++cnt,m=nums[i];
           else cnt = 0;
       }
       ans -= cnt;
       if(!ans) return 0;
       cnt = 1;
       for(int i=n-2,m=nums[n-1];i>=0;--i){
           if(nums[i]<=m) ++cnt,m=nums[i];
           else cnt = 0;
       }
       ans -= cnt;
       return ans;
   }
};



580

题目给出student table,department table,要求统计各dept有多少student。注意一个dept可以有0个学生。例子:

student table:

| student_id | student_name | gender | dept_id |

|------------|--------------|--------|---------|

| 1          | Jack         | M      | 1       |

| 2          | Jane         | F      | 1       |

| 3          | Mark         | M      | 2       |

department table:

| dept_id | dept_name   |

|---------|-------------|

| 1       | Engineering |

| 2       | Science     |

| 3       | Law         |

The Output should be:

| dept_name   | student_number |

|-------------|----------------|

| Engineering | 2              |

| Science     | 1              |

| Law         | 0              |


题解:此题用LEFT JOIN 可以对两个表格进行比较,选取出dept_id相同的student和department统计每个department的student数量,并用group by和order by来对结果进行分组和排序。


SELECT 
 dept_name, COUNT(student_id) AS student_number
FROM
 department
LEFT JOIN student ON student.dept_id = department.dept_id
GROUP BY department.dept_id
ORDER BY student_number DESC, dept_name ASC;


579

题目:给出员工每个月的工资表,求月累计工资表,并排除最近的月份。比如下面的例子:员工1一月份工资为20,二月份工资为30,那到二月份的累计工资是50.

Input

| Id | Month | Salary |

|----|-------|--------|

| 1  | 1     | 20     |

| 2  | 1     | 20     |

| 1  | 2     | 30     |

| 2  | 2     | 30     |

| 3  | 2     | 40     |

| 1  | 3     | 40     |

| 3  | 3     | 60     |

| 1  | 4     | 60     |

| 3  | 4     | 70     |

Output

| Id | Month | Salary |

|----|-------|--------|

| 1  | 3     | 90     |

| 1  | 2     | 50     |

| 1  | 1     | 20     |

| 2  | 1     | 20     |

| 3  | 3     | 100    |

| 3  | 2     | 40     |

Explanation题解:


SELECT
   E1.id,
   E1.month,
   (IFNULL(E1.salary, 0) + IFNULL(E2.salary, 0) + IFNULL(E3.salary, 0)) AS Salary
FROM
   (SELECT
       id, MAX(month) AS month
   FROM
       Employee
   GROUP BY id
   HAVING COUNT(*) > 1) AS maxmonth
       LEFT JOIN
   Employee E1 ON (maxmonth.id = E1.id
       AND maxmonth.month > E1.month)
       LEFT JOIN
   Employee E2 ON (E2.id = E1.id
       AND E2.month = E1.month - 1)
       LEFT JOIN
   Employee E3 ON (E3.id = E1.id
       AND E3.month = E1.month - 2)
ORDER BY id ASC , month DESC
;



578

题目:给出如下表的input table,每一行代表一个online forum的log,action代表这个log的类型,show代表显示一个问题,answer代表有人回答。求answer rate最高的question_id

Input:

+------+----------+--------------+------------+---------+------------+

| uid  | action   | question_id  | answer_id  | q_num   | timestamp  |

+------+----------+--------------+------------+---------+------------+

| 5    | show     | 285          | null       | 1       | 123        |

| 5    | answer   | 285          | 124124     | 1       | 124        |

| 5    | show     | 369          | null       | 2       | 125        |

| 5    | skip     | 369          | null       | 2       | 126        |

+------+----------+--------------+------------+---------+------------+

Output:

+-------------+

| survey_log  |

+-------------+

|    285      |

+-------------+

题解此题用group by对question分组,然后用order by对每个question的answer rate按降序排序,最后用limit来输出answer rate最高的question即可。

SELECT question_id AS survey_log
FROM survey_log
GROUP BY survey_log.question_id
ORDER BY (COUNT(survey_log.answer_id)/COUNT(IF(survey_log.action='show',1,0))) DESC
LIMIT 1;



577

题目:Implement a MapSum class with insert, and sum methods.

call sum method的时候,打印所有以当前key为prefix的所有value总和。

例子:

Input: insert("apple", 3), Output: Null

Input: sum("ap"), Output: 3

Input: insert("app", 2), Output: Null

Input: sum("ap"), Output: 5

题解:使用Trie Tree的变种。建立 TrieNode {int val; int sum; boolean isAWord; TrieNode[] children;}.

sum存所有以这个key为prefix的value的sum。Insert时候,将所有值加到当前key的prefix所在node里。需要注意的是,如果insert的key已经存在,将所有值从当前key的prefix所在node里remove掉。Sum method即为,Trie Tree的标准search method.


576

题目:m x n的grid, 有个足球在(0, 0)位置。现在这个足球可以上下左右move N steps,问这个足球走出grid 有多少种path。

题解:使用一个二位dp数组 dp[m][n] , 代表第i个step,grid为m x n,有多少种path。遍历 step 1~N, 每次走四个方向,来update dp[m][n]。Running time: O(mxnxN); Space: O(m x n)


class Solution {
   const int mod = 1E9 + 7;
   int n, m, dp[55][55][55], dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
   void add(int &x, int y){
       x += y;
       if(x >= mod) x -= mod;
   }
   int dfs(int i,int j,int rest){
       if(i<0 || j<0 || i>=m || j>=n) return 1;
       if(!rest) return 0;
       if(dp[i][j][rest]>=0) return dp[i][j][rest];
       dp[i][j][rest] = 0;
       for(int k=0;k<4;++k) add(dp[i][j][rest], dfs(i+dx[k], j+dy[k], rest-1) );
       return dp[i][j][rest];
   }
public:
   int findPaths(int m, int n, int N, int i, int j) {
       this->m = m;
       this->n = n;
       memset(dp, -1, sizeof(dp));
       return dfs(i, j, N);
   }
};


575

题目:给一个数组,代表糖果种类。现在把糖果尽量平均地分给哥哥和妹妹,问妹妹最多能分多少种类?比如下面的例子,可以给每个人1,2,3三种candy

Input: candies = [1,1,2,2,3,3]

Output: 3

题解:用一个hashset计算数组中有多少种糖果,如果这个数量大于糖果总数的一半。妹妹最多能分到的种类为糖果总数的一半。反之,妹妹能分到糖果的种类个。Running time: O(n), Space: O(n)


附加题:


查看所有题目:

打开Wechat微信->Contacts[联系人]->Official Accounts[公众号]->北美加群小助手Jogchat->天天刷题



【长按扫码关注北美加群小助手Jogchat.com】


阅读 5715

微信扫一扫
关注该公众号