小编们带来刷题系列第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分别代表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】