60天带你刷完Leetcode【第11天】574 ~ 564

2017-10-27 CS竞赛大神 北美加群小助手Jogchat 北美加群小助手Jogchat

每天30分钟 关注【北美加群小助手Jogchat.com】小编们带你60天刷完,学渣学酥也能跻身硅谷一线公司、升职加薪、当上总经理、出任CEO、迎娶白富美、从此走上人生巅峰!想想还有点小激动😏


574

题目:

Table: Candidate

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

| id  | Name    |

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

| 1   | A       |

| 2   | B       |

| 3   | C       |

| 4   | D       |

| 5   | E       |

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

Table: Vote

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

| id  | CandidateId  |

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

| 1   |     2        |

| 2   |     4        |

| 3   |     3        |

| 4   |     2        |

| 5   |     5        |

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

id is the auto-increment primary key,

CandidateId is the id appeared in Candidate table.

Write a sql to find the name of the winning candidate, the above example will return the winner B.

+------+

| Name |

+------+

| B    |

+------+

Notes:

  1. You may assume there is no tie, in other words there will be at most one winning candidate.

题解:

SELECT

    name AS 'Name'

FROM

    Candidate

        JOIN

    (SELECT

        Candidateid

    FROM

        Vote

    GROUP BY Candidateid

    ORDER BY COUNT(*) DESC

    LIMIT 1) AS winner

WHERE

    Candidate.id = winner.Candidateid

;


在Vote表中查询获取获胜者的ID,然后将其与候选表join获取名称。

  •   @Chaoran W @Yicheng S @Chen Y 


573. Squirrel Simulation

题目:如下图,某松鼠要搜集所有的 Nuts松树下,求最短路径:

题解:Manhattan distance的操作,很简单,one pass 就够了。

class Solution {

    inline int manhattan(vector<int> &p1, vector<int> &p2){ return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1]); }

public:

    int minDistance(int height, int width, vector<int>& tree, vector<int>& squirrel, vector<vector<int>>& nuts) {

        int ans = 0, diff = manhattan(squirrel, nuts[0]) - manhattan(nuts[0], tree);

        for(auto p:nuts){

            ans += 2*manhattan(p, tree);

            diff = min(diff, manhattan(squirrel, p) - manhattan(p, tree));

        }

        return ans + diff;

    }

};



572. Subtree of Another Tree

题目:判断 t 是否是 ssubtree

题解:Recursive, 很简单,几行搞定。下面做法中 isSame 用来判断两棵树是否相同。

class Solution {

    bool isSame(TreeNode *s, TreeNode*t){

        if(!t || !s) return !t && !s;

        return s->val==t->val&&isSame(s->left, t->left)&&isSame(s->right, t->right);

    }

public:

    bool isSubtree(TreeNode* s, TreeNode* t) {

        if(!s) return !t;

        return isSame(s,t) || isSubtree(s->left,t) || isSubtree(s->right,t);

    }

};


571 (SQL)

题目:The Numbers table keeps the value of number and its frequency.

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

|  Number  |  Frequency  |

+----------+-------------|

|  0       |  7          |

|  1       |  1          |

|  2       |  3          |

|  3       |  1          |

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

In this table, the numbers are 0, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 3, so the median is (0 + 0) / 2 = 0.

+--------+

| median |

+--------|

| 0.0000 |

+--------+

Write a query to find the median of all numbers and name the result as median.


题解:建立Table1按照Number升序排列,并加入两列分别统计之前出现的数字个数以及到目前为止出现的数字的总数,建立Table2找出median所在位置,然后通过where筛选出表格Numbers中的median。此处要注意,当有奇数个数时,中位数为第(n+1)/2的数;当有偶数个数时,中位数为第n/2的数和第(n/2+1)的数的平均值。

SET @total_frequency = 0;


SELECT CONVERT(avg(Table1.Number),DECIMAL(10,4)) as median

FROM

    (SELECT Number, Frequency, @preNumber_Frequency:=@total_frequency AS PreNumber_Frequency, @total_frequency:=@total_frequency+Frequency AS total_frequency

    FROM Numbers

    ORDER BY Number) as Table1,

    (SELECT FLOOR((SUM(Numbers.Frequency)+1)/2) AS Index1, FLOOR((SUM(Numbers.Frequency)+2)/2) AS Index2

     FROM Numbers) as Table2

WHERE (Table1.PreNumber_Frequency < Table2.Index1 AND Table1.total_frequency >= Table2.Index1) OR (Table1.PreNumber_Frequency < Table2.Index2 AND Table1.total_frequency >= Table2.Index2);


570 (SQL)

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

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

|Id    |Name           |Department |ManagerId |

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

|101   |John           |A               |null      |

|102   |Dan           |A               |101       |

|103   |James           |A               |101       |

|104   |Amy           |A               |101       |

|105   |Anne           |A               |101       |

|106   |Ron           |B               |101       |

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

Given the Employee table, write a SQL query that finds out managers with at least 5 direct report. For the above table, your SQL query should return:

+-------+

| Name  |

+-------+

| John  |

+-------+

Note:

No one would report to himself.


题解:用JOIN找出表格中ManagerId和员工Id相对应并且满足ManagerId出现次数大于5次的员工name

SELECT Table1.name as Name

FROM Employee AS Table1 JOIN Employee AS Table2 ON Table1.Id = Table2.ManagerId

GROUP BY Table1.Name

HAVING COUNT(Table2.ManagerId >= 5);



569 (SQL)

题目:The Employee table holds all employees. The employee table has three columns: Employee Id, Company Name, and Salary.

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

|Id   | Company    | Salary |

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

|1    | A          | 2341   |

|2    | A          | 341    |

|3    | A          | 15     |

|4    | A          | 15314  |

|5    | A          | 451    |

|6    | A          | 513    |

|7    | B          | 15     |

|8    | B          | 13     |

|9    | B          | 1154   |

|10   | B          | 1345   |

|11   | B          | 1221   |

|12   | B          | 234    |

|13   | C          | 2345   |

|14   | C          | 2645   |

|15   | C          | 2645   |

|16   | C          | 2652   |

|17   | C          | 65     |

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

Write a SQL query to find the median salary of each company. Bonus points if you can solve it without using any built-in SQL functions.

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

|Id   | Company    | Salary |

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

|5    | A          | 451    |

|6    | A          | 513    |

|12   | B          | 234    |

|9    | B          | 1154   |

|14   | C          | 2645   |

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


题解:先对Employee表格按照公司,工资和Id排序行程Table1,此外计算出每个公司的median所在行成Table2,然后通过JOIN将两个表格里company相同的记录相连接,最后用where选择出每个公司的median salary。此处要注意,当有奇数个数时,中位数为第(n+1)/2的数;当有偶数个数时,中位数为第n/2的数和第(n/2+1)的数的平均值。

SELECT Table1.Id AS Id, Table1.Company AS Company, Table1.Salary AS Salary

FROM 

    (SELECT Employee.Id AS Id, Employee.Company AS Company, Employee.Salary AS Salary, IF(@pre_company=Employee.Company, @row_Number:=@row_Number + 1, @row_Number:=1) as row_Number, @pre_company := Employee.Company

    FROM Employee, (SELECT @row_Number:=0, @pre_company:=0) as var

    ORDER BY Employee.Company, Employee.Salary, Employee.Id) AS Table1 JOIN

    (SELECT Employee.Company AS Company, COUNT(Employee.Company) AS NumOfEmployees, FLOOR((COUNT(Employee.Company)+1)/2) AS Index1, FLOOR((COUNT(Employee.Company)+2)/2) AS Index2

    FROM Employee

    GROUP BY Employee.Company) AS Table2 ON Table1.Company = Table2.Company

WHERE (Table1.row_Number =  Table2.Index1) OR (Table1.row_Number = Table2.Index2);



568. Maximum Vacation Days

题目:LeetCode wants to give one of its best employees the option to travel among N cities to collect algorithm problems. But all work and no play makes Jack a dull boy, you could take vacations in some particular cities and weeks. Your job is to schedule the traveling to maximize the number of vacation days you could take, but there are certain rules and restrictions you need to follow.

Rules and restrictions:

  1. You can only travel among N cities, represented by indexes from 0 to N-1. Initially, you are in the city indexed 0 on Monday.

  2. The cities are connected by flights. The flights are represented as a N*N matrix (not necessary symmetrical), called flightsrepresenting the airline status from the city i to the city j. If there is no flight from the city i to the city j, flights[i][j] = 0; Otherwise, flights[i][j] = 1. Also, flights[i][i] = 0 for all i.

  3. You totally have K weeks (each week has 7 days) to travel. You can only take flights at most once per day and can only take flights on each week's Monday morning. Since flight time is so short, we don't consider the impact of flight time.

  4. For each city, you can only have restricted vacation days in different weeks, given an N*K matrix called days representing this relationship. For the value of days[i][j], it represents the maximum days you could take vacation in the city i in the week j.

You're given the flights matrix and days matrix, and you need to output the maximum vacation days you could take during K weeks.

Note:

  1. N and K are positive integers, which are in the range of [1, 100].

  2. In the matrix flights, all the values are integers in the range of [0, 1].

  3. In the matrix days, all the values are integers in the range [0, 7].

  4. You could stay at a city beyond the number of vacation days, but you should work on the extra days, which won't be counted as vacation days.

  5. If you fly from the city A to the city B and take the vacation on that day, the deduction towards vacation days will count towards the vacation days of city B in that week.

  6. We don't consider the impact of flight hours towards the calculation of vacation days.

题解:题很长,慢慢看,加油。实际上很简单,不明白为啥是hard,一个 dp 就O了。(难点可能在于那个flight不是双向的。本学渣在比赛的时候下意识的以为是双向,结果错了一次,被扣了5min。)dp[i][k] 表示第如果第 k 周的周一呆在第 i 个city,剩下的数周中,最大的vacation天数。

class Solution {

    int N, K;

    vector<vector<int>> E;

    int dp[105][105];

    int dfs(int i,int k, vector<vector<int>>& d){

        if(k == K) return 0;

        if(dp[i][k] >= 0) return dp[i][k];

        dp[i][k] = dfs(i, k+1, d) + d[i][k];

        for(int j:E[i]) dp[i][k] = max(dp[i][k], dfs(j,k+1,d) + d[j][k]);

        return dp[i][k];

    }

public:

    int maxVacationDays(vector<vector<int>>& flights, vector<vector<int>>& days) {

        N = flights.size(), K = days[0].size();

        E.resize(N);

        for(int i=0;i<N;++i) for(int j=0;j<N;++j) if(flights[i][j]) E[i].push_back(j);

        memset(dp,-1,sizeof(dp));

        return dfs(0,0,days);

    }

};


567. Permutation in String

题目:Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

题解:Slide Window (用一个map记录某一段长度的s2中的字母的个数,然后one pass得到结果)

class Solution {

public:

    bool checkInclusion(string s1, string s2) {

        if(s1.size()>s2.size()) return false;

        map<char, int> ref, window;

        for(int i=0;i<s1.size();++i) ref[s1[i]]++,window[s2[i]]++;

        for(int i=0;i+s1.size()<s2.size() && window!=ref;++i){

            window[s2[i]]--;

            if(!window[s2[i]]) window.erase(s2[i]);

            window[s2[i+s1.size()]]++;

        }

        return window==ref;

    }

};


566. Reshape the Matrix

题目:In MATLAB, there is a very useful function called 'reshape', which can reshape a matrix into a new one with different size but keep its original data.

You're given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.

The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the 'reshape' operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.

题解:简单推下坐标变换关系即可。解法如下:能四行写完的code应该不难。

class Solution {

public:

    vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {

        if(nums.size()*nums[0].size() != r*c) return nums;

        vector<vector<int>> ans(r, vector<int>(c,0));

        for(int i=0;i<r*c;++i) ans[i/c][i%c] = nums[i/nums[0].size()][i%nums[0].size()];

        return ans;

    }

};


564. Find the Closest Palindrome

题目:Given an integer n, find the closest integer (not including itself), which is a palindrome. 

The 'closest' is defined as absolute difference minimized between two integers.

题解:这道题稍稍有点难度,思路不难,但写起来麻烦。思路是把可能的candidates全部放在一个set里面,最后区刚好比目标大的那个跟刚好比目标小的那个。(其实直接更新上确界跟下确界更快一些,但本学渣比较懒,懒得重写一个新的解法了,反正两个解法很类似,各位自由发挥。)

这时问题是如何得到这些candidates: 举一个例子:123754612453

看它的某一个 prefix , 当然这个 prefix 长度小于等于 (原长+1)/2, 比如说1237. (先说小于)这时离该数比较近的palindrome 只可能是 123699...96321, 123800…08321 或者 直接包涵原 prefix。这样前两个确定了,所以我们把它们添加到开始定义的那个 set 里面。对于第三种,我们只需要把 prefix 长度增加1,然后 check 新的 prefix. 当 prefix 长度刚好等于 (原长+1)/2 的时候 i.e. 123754 ,我们把三种情形得到的数字 123753357321 , 123755557321123754457321 全部放进那个 set 里面。这样就构建出了一个set,由于 string 不长,只有18, 所以没有超时的危险。

原理就是 palindrome 如果前半部分固定了,本身也就固定了。

写起来比较烦,认真耐心点,没有问题。

class Solution {

    inline string addOne(string n){ return to_string(stol(n)+1); }

    inline string minusOne(string n){ return to_string(stol(n)-1); }

    string makePal(string prefix, int l, char c){

        int l1 = prefix.size();

        string ans = prefix + string(max(0,l-2*l1), c);

        if(l1*2 == l+1) ans.pop_back();

        reverse(prefix.begin(), prefix.end());

        ans += prefix;

        return ans;

    }

public:

    string nearestPalindromic(string n) {

        if(n.size()==1) return (n=="0"? "1":string{char(n[0]-1)});

        int l = n.size();

        set<long> ans;

        for(int i=0;i<(l+1)/2;++i){

            string tmp = n.substr(0, i+1);

            string s_up=addOne(tmp), s_low=minusOne(tmp);

            if(s_low=="0") s_low.clear();

            int l_up = l, l_low = l;

            if(s_up.size()>tmp.size()) l_up++;

            if(s_low.size()<tmp.size()) l_low--;

            ans.insert(stol(makePal(s_up,l_up,'0')));

            ans.insert(stol(makePal(s_low,l_low,'9')));

            if(i==(l-1)/2) ans.insert(stol(makePal(tmp,l,'0')));

        }

        long k = stol(n);

        if(ans.count(k)) ans.erase(k);

        auto t1 = ans.upper_bound(k);

        long k1 = *t1--;

        long k2 = *t1;

        if(k1 - k < k - k2) return to_string(k1);

        else return to_string(k2);

        

    }

};

附加题:

有兴趣的同学可以做一做


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


阅读 5762

微信扫一扫
关注该公众号