小编们带来刷题系列第10篇了!这此的题目中,还是有很多是SQL的题目,另外的一些是基本的拓展思路的题目。在这一篇中小编尝试给每一题附上我们的参考code,大家可以在阅读过程中先想一个思路,再和我们的code对照~ 另外,code的质量和style我们还是有信心滴
584
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分别代表PID和PPID,再给出一个要被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】
微信扫一扫
关注该公众号