60天带你刷完Leetcode【第9天】596 ~ 585

2017-10-09 PKU竞赛大神 北美加群小助手Jogchat 北美加群小助手Jogchat


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


本周请来了竞赛大神帮你解题,30分钟过10道题,轻轻松松。


596

题目:有一个含有student和class的课表courses,请列出拥有等于或多余5个学生的所有课程。 每门课程不得对同一个学生进行重复计数。

题解:用group by从courses中选取不同的课程,并使用having condition来对选取出的课程进行筛选。count(distinct  student)可以对每门课程的上课人数进行不重复计数。

SELECT

    class

FROM

    courses

GROUP BY class

HAVING count(distinct student) >= 5;


595

题目:用SQL对world集合里的国家进行筛选并输出筛选后国家的名字,人口和面积。要求输出的国家满足area大于300万平方公里或者population多于2500万。

题解:用where condition筛选出world集合里area大于300万平方公里或者population多于2500万的国家即可。

SELECT 

    name, population, area

FROM

    world

WHERE

    population > 25000000 or area > 3000000;


594

题目:Longest Harmonious Subsequence

  • We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.

  • Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.

题解:我们可以用一个map来记录每个数字在序列中出现的次数,再对map进行遍历即可:

class Solution {

public:

    int findLHS(vector<int>& nums) {

        map<int,int> cnt;

        for(auto k:nums) cnt[k]++;

        int ans = 0;

        for(auto p:cnt) if(cnt.count(p.first+1)) 

            ans = max(ans, p.second+cnt[p.first+1]);

        return ans;

    }

};


593

题目:Valid Square

  • Given the coordinates of four points in 2D space, return whether the four points could construct a square.

  • The coordinate (x,y) of a point is represented by an integer array with two integers.

题解: 假如形成正方形, p1 一定为其定点,这样线段p1p3 和 p1p3  一定至少有一个是正方形的一条边。而且我们知道正方形只要有一条边确定了,另外两个顶点也就确定了,设为p5, p6。所以固定一条边之后我们只需要check剩下的两个点跟p5, p6是否match即可。

typedef vector<int> vi;

class Solution {

    bool isSquare(vi &p1, vi&p2, vi&p3, vi&p4){

        if(p1 == p2) return false;

        int dx = p2[0] - p1[0], dy = p2[1] - p1[1];

        vi p5{p1[0]+dy, p1[1]-dx}, p6{p2[0]+dy, p2[1]-dx};

        if((p5==p3&&p6==p4)||(p5==p4&&p6==p3)) return true;

        p5 = vi{p1[0]-dy, p1[1]+dx};

        p6 = vi{p2[0]-dy, p2[1]+dx};

        if((p5==p3&&p6==p4)||(p5==p4&&p6==p3)) return true;

        return false;

    }

public:

    bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {

        return isSquare(p1,p2,p3,p4) || isSquare(p1,p3,p2,p4);

    }

};


592

题目:Fraction Addition and Subtraction

  • Given a string representing an expression of fraction addition and subtraction, you need to return the calculation result in string format. The final result should be irreducible fraction. If your final result is an integer, say 2, you need to change it to the format of fraction that has denominator 1. So in this case, 2 should be converted to 2/1.

    1. The input string only contains '0' to '9', '/', '+' and '-'. So does the output.

    2. Each fraction (input and output) has format ±numerator/denominator. If the first input fraction or the output is positive, then '+' will be omitted.

    3. The input only contains valid irreducible fractions, where the numerator and denominator of each fraction will always be in the range [1,10]. If the denominator is 1, it means this fraction is actually an integer in a fraction format defined above.

    4. The number of given fractions will be in the range [1,10].

    5. The numerator and denominator of the final result are guaranteed to be valid and in the range of 32-bit int.

题解

1,首先需要从原有序列中extract这些数字,把它们变成integer/integer 的形式。这个过程可以用c++中的stoi函数来实现,同时要注意用/  跟+-ba 数据截断。

2,计算过程非常简单,就是正常分数运算,得到的是分母跟分子,但不一定是irreducible的。

3,分子跟分母同时除以他们的最大公约数,就是我们想要得到的结果。

4,注意,分母为负数的情况要单独考虑。

5,输出的时候要把分数转化成字符串,c++可以使用to_string函数。

typedef pair<int, int> ii;

class Solution {

    int gcd(int x,int y){

        if(x<y) swap(x,y);

        if(!y) return x;

        return gcd(y, x%y);

    }

    ii getFraction(ii f1, ii f2){

        int deno=f1.second*f2.second;

        int nume=f1.second*f2.first+f1.first*f2.second;

        int m = gcd(abs(deno), abs(nume));

        if(deno < 0){

            deno *= -1;

            nume *= -1;

        }

        return pair<int,int>(nume/m, deno/m);

    }

public:

    string fractionAddition(string expression) {

        int n1 = stoi(expression);

        auto j = expression.find('/');

        int d1 = stoi(expression.substr(j+1));

        ii ans = ii(n1,d1);

        j = expression.find_first_of("+-",j+1);

        while(j!=string::npos){

            int n2 = stoi(expression.substr(j));

            j = expression.find('/',j+1);

            int d2 = stoi(expression.substr(j+1));

            ans = getFraction(ans, ii(n2,d2));

            j = expression.find_first_of("+-",j+1);

        }

        return to_string(ans.first)+"/"+to_string(ans.second);

    }

};


591

题目:Tag Validator

Given a string representing a code snippet, you need to implement a tag validator to parse the code and return whether it is valid. A code snippet is valid if all the following rules hold:

  1. The code must be wrapped in a valid closed tag. Otherwise, the code is invalid.

  2. A closed tag (not necessarily valid) has exactly the following format : <TAG_NAME>TAG_CONTENT</TAG_NAME>. Among them, <TAG_NAME> is the start tag, and </TAG_NAME> is the end tag. The TAG_NAME in start and end tags should be the same. A closed tag is valid if and only if the TAG_NAME and TAG_CONTENT are valid.

  3. A valid TAG_NAME only contain upper-case letters, and has length in range [1,9]. Otherwise, the TAG_NAME is invalid.

  4. A valid TAG_CONTENT may contain other valid closed tags, cdata and any characters (see note1) EXCEPT unmatched <, unmatched start and end tag, and unmatched or closed tags with invalid TAG_NAME. Otherwise, the TAG_CONTENT is invalid.

  5. A start tag is unmatched if no end tag exists with the same TAG_NAME, and vice versa. However, you also need to consider the issue of unbalanced when tags are nested.

  6. A < is unmatched if you cannot find a subsequent >. And when you find a < or </, all the subsequent characters until the next > should be parsed as TAG_NAME (not necessarily valid).

  7. The cdata has the following format : <![CDATA[CDATA_CONTENT]]>. The range of CDATA_CONTENT is defined as the characters between <![CDATA[ and the first subsequent ]]>

CDATA_CONTENT may contain any characters. The function of cdata is to forbid the validator to parse CDATA_CONTENT, so even it has some characters that can be parsed as tag (no matter valid or invalid), you should treat it as regular characters.

题解:这题没啥意思,突出一个烦,关键是如何熟练运用string的各种操作跟函数。另外就是对题目的理解。

学渣在做这道题的时候发现有一个case死活过不了:"<![CDATA[wahaha]]]><![CDATA[]> wahaha]]>",这其实是两个CDATA blocks连在了一起。学渣的code给出的答案是true,但正确答案是false. 反复看了那组数据,发现完全没有违反上面任何一条规则,所以百思不得其解。最后才注意到第一条,也就是任何code,或者CDATA blocks都必须在一个closed tag里面。

所以做这种题的关键就是对规则的理解跟对string各种操作的熟练掌握。

const string ULett = "QWERTYUIOPASDFGHJKLZXCVBNM";

const string CBeg = "<![CDATA[";

const string CEnd = "]]>";

class Solution {

public:

    bool isValid(string code) {

        stack<string> Tags;

        auto j = code.find_first_of("<");

        if(j) return false;

        while(j<code.size() && j!=string::npos){

            if(j && Tags.empty()) return false;

            if(j+1 == code.size()) return false;

            j = code.find_first_of("<",j);

            if(j+9<=code.size() && code.substr(j,9) == CBeg){

                j = code.find(CEnd,j);

                if(j==string::npos) return false;

                j += 3;

            }

            else{

                auto i = code.find_first_of(">",j);

                if(i==string::npos) return false;

                string tmp_tag = code.substr(j+1,i-j-1);

                if(code[j+1]!='/'){

                    int tmpl = (int)tmp_tag.size();

                    if(!tmpl || tmpl>9 || tmp_tag.find_first_not_of(ULett)!=string::npos)

                        return false;

                    Tags.push(tmp_tag);

                }

                else{

                    tmp_tag = tmp_tag.substr(1);

                    if(Tags.empty() || Tags.top()!=tmp_tag) return false;

                    Tags.pop();

                }

                j = i+1;

            }

        }

        return Tags.empty();

    }

};



588

题目:Design In-Memory File System

Design an in-memory file system to simulate the following functions:

ls: Given a path in string format. If it is a file path, return a list that only contains this file's name. If it is a directory path, return the list of file and directory names in this directory. Your output (file and directory names together) should in lexicographic order.

mkdir: Given a directory path that does not exist, you should make a new directory according to the path. If the middle directories in the path don't exist either, you should create them as well. This function has void return type.

addContentToFile: Given a file path and file content in string format. If the file doesn't exist, you need to create that file containing given content. If the file already exists, you need to append given content to original content. This function has void return type.

readContentFromFile: Given a file path, return its content in string format.

题解:题目很长,但别被吓到,其实很简单。跟Tier(一个多叉树,树的节点用字母标记,用来快速查找string)很类似。首先我们建立一个结构体(struct F),里面包含:isFile 判断这个节点是File 还是directory; fileName 文件名; cont 文件的content,如果这个节点是文件的话;chl 这个节点的子节点,也就是目录,如果这个节点是directory的话。

有了这个结构体,后面的操作就很容易实现了,剩下的就是如何从input string 中得到路径中每一步的文件名。如果对字符串操作很熟悉的话,后面这个其实很简单。

#include<cassert>

class FileSystem {

    struct F{

        bool isFile;

        string fileName;

        string cont;

        map<string, F*> chl;

        F(bool dir, string name):isFile(!dir),fileName(name){}

    };

    F *root;

public:

    FileSystem() {

        root = new F(true, "root");

    }

    

    vector<string> ls(string path) {

        F *p = root;

        auto j = path.find_first_not_of("/");

        while(j<path.size() && j!=string::npos){

            auto i = path.find_first_of("/",j);

            if(i == string::npos) i = path.size();

            string dirName = path.substr(j,i-j);

            assert(p->chl.count(dirName));

            p = p->chl[dirName];

            j = i+1;

        }

        if(p->isFile) return vector<string>{p->fileName};

        vector<string> ans;

        for(auto items:p->chl) ans.push_back(items.first);

        return ans;

    }

    

    void mkdir(string path) {

        F *p = root;

        auto j = path.find_first_not_of("/");

        while(j<path.size() && j!=string::npos){

            auto i = path.find_first_of("/",j);

            if(i == string::npos) i = path.size();

            string dirName = path.substr(j,i-j);

            if(!p->chl.count(dirName)) p->chl[dirName] = new F(true, dirName);

            p = p->chl[dirName];

            j = i+1;

        }

        return;

    }

    

    void addContentToFile(string filePath, string content) {

        F *p = root;

        auto j = filePath.find_first_not_of("/");

        while(j<filePath.size() && j!=string::npos){

            auto i = filePath.find_first_of("/",j);

            if(i == string::npos) i = filePath.size();

            string dirName = filePath.substr(j,i-j);

            if(!p->chl.count(dirName)) p->chl[dirName] = new F(true, dirName);

            p = p->chl[dirName];

            j = i+1;

        }

        if(!p->isFile) p->isFile = true;

        p->cont += content;

        return;

    }

    

    string readContentFromFile(string filePath) {

        F *p = root;

        auto j = filePath.find_first_not_of("/");

        while(j<filePath.size() && j!=string::npos){

            auto i = filePath.find_first_of("/",j);

            if(i == string::npos) i = filePath.size();

            string dirName = filePath.substr(j,i-j);

            if(!p->chl.count(dirName)) p->chl[dirName] = new F(true, dirName);

            p = p->chl[dirName];

            j = i+1;

        }

        if(!p->isFile) p->isFile = true;

        return p->cont;

    }

};


/**

 * Your FileSystem object will be instantiated and called as such:

 * FileSystem obj = new FileSystem();

 * vector<string> param_1 = obj.ls(path);

 * obj.mkdir(path);

 * obj.addContentToFile(filePath,content);

 * string param_4 = obj.readContentFromFile(filePath);

 */


587

题 目:There are some trees, where each tree is represented by (x,y) coordinate in a two-dimensional garden. Your job is to fence the entire garden using the minimum length of rope as it is expensive. The garden is well fenced only if all the trees are enclosed. Your task is to help find the coordinates of trees which are exactly located on the fence perimeter.

题解:可以先选定一个起始 tree(根节点)(比如离原点最近的/最左/最右/最上/最下),然后顺时针/逆时针scan其余tree,这里定义一个direction函数,若是 从起始点顺时针/逆时针到这个点的旋转角度最小,则该点在下一次被选为起始点,继续scan直到起始tree回到根节点。此外,若有tree在 boundary上,用betweentrees()把它放入fence set。

public class Solution {

    public int direction(Point a, Point b, Point c) {

        return (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);

    }

    public boolean betweentrees(Point a, Point i, Point b) {

        boolean a = i.x >= a.x && i.x <= b.x || i.x <= a.x && i.x >= b.x;

        boolean b = i.y >= a.y && i.y <= b.y || i.y <= a.y && i.y >= b.y;

        return a && b;

    }

    public List < Point > outerTrees(Point[] points) {

        HashSet < Point > fence = new HashSet < > ();

        if (points.length < 4) {

            for (Point a: points)

                fence.add(a);

            return new ArrayList<Point>(fence);

        }


        int left_most = 0;

        for (int i = 0; i < points.length; i++){

            if (points[i].x < points[left_most].x)

                left_most = i;

        }

           

        int a = left_most;

        do {

            int b = (a + 1);

            for (int i = 0; i < points.length; i++) {

                if (direction(points[a], points[i], points[b]) < 0) {

                    b = i;

                }

            }

            for (int i = 0; i < points.length; i++) {

                if (i != a && i != b && direction(points[a], points[i], points[b]) == 0 && betweentrees(points[a], points[i], points[b])) {

                    fence.add(points[i]);

                }

            }

            fence.add(points[b]);

            a = b;

        }

        while (a != left_most);

        return new ArrayList<Point>(fence);

    }

}


586

题目:给出一个记录transaction的表,找出提交订单数量做多的顾客

题解:按照题意找出count最大值即可

SELECT customer_number

FROM orders

GROUP BY customer_number

ORDER BY COUNT(order_number) DESC 

LIMIT 1

;


585

题目:给出如下表格,找出符合下列条件的行,再对TIV_2016这一列求和:TIV_2015有和其他行相同,LAT和LON其他行没有出现过。

| PID | TIV_2015 | TIV_2016 | LAT | LON |

|-----|————----|----------|-----|-----|

| 1    | 10       | 5        | 10  | 10  |

| 2   | 20       | 20       | 20  | 20  |

| 3   | 10       | 30       | 20  | 20  |

| 4   | 10       | 40       | 40  | 40  |

题解:这题根据要求的两个条件构造filter即可

SELECT ROUND(sum(TIV_2016), 2) AS TIV_2016

FROM insurance i

WHERE TIV_2015 IN (SELECT TIV_2015 FROM insurance GROUP BY TIV_2015 HAVING COUNT(TIV_2015) > 1) 

    AND (LAT,LON) IN (SELECT LAT,lon FROM insurance GROUP BY LAT,LON HAVING COUNT(LAT) = 1) 

;

长按扫码关注



阅读 5794

微信扫一扫
关注该公众号