pyai's blog
0%

leetcode刷题

Posted on Edited on In Views:

LeetCode难度三个等级：

1，简单：Easy

1，中等：Medium

3，困难：Hard

最近比较忙，再加上要期末考试了，暂时刷的都是Easy的。

分割线
#### 2019-06-10

题目链接 771. Jewels and Stones Easy

水题，就是求字符串$S$中有多少字母在字符串$J$中，字符串$J$中的字母各不相同。

代码如下:复杂度$O(S.length+J.length)$。

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int numJewelsInStones(string J, string S) {
        int sum=0;
        unordered_set<char>se(J.begin(),J.end());
        for(auto i : S) sum+=se.count(i);
        return sum;
    }
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Jewels and Stones.

Memory Usage: 8.6 MB, less than 56.84% of C++ online submissions for Jewels and Stones.

分割线
#### 2019-06-11

题目链接938. Range Sum of BST Easy

题意就是题目的名字，给你一个建好的二叉搜索树($BST$)的根节点$root$，让你计算值位于$L$和$R$之间节点的值的和。

$$
ans=\sum{node.value\ which\ L\le node.value\le R}
$$

然后代码就是一个简单的后序遍历加类似于二分的剪枝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int rangeSumBST(TreeNode* root, int L, int R) {
        int sum=0;
        if(root){
            if(root->val>=L) sum+=rangeSumBST(root->left,L,R);
            if(root->val<=R) {
                sum+=rangeSumBST(root->right,L,R);
                if(root->val>=L) sum+=root->val;
            }
        }
        return sum;
    }
};

Runtime: 144 ms, faster than 90.39% of C++ online submissions for Range Sum of BST.

Memory Usage: 41.3 MB, less than 41.58% of C++ online submissions for Range Sum of BST.

分割线
#### 2019-06-12 23:51

题目链接709. To Lower Case Easy

水题，简单字符串，返回全部小写的字符串。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    string toLowerCase(string str) {
        int len=str.length();
        string ret;
        for(int i=0;i<len;i++){
            ret.push_back(tolower(str[i]));
        }
        return ret;
    }
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for To Lower Case.

Memory Usage: 8.4 MB, less than 32.20% of C++ online submissions for To Lower Case.

分割线
#### 2019-06-13 22:57

题目链接1021. Remove Outermost Parentheses Easy

题目大意就是在一堆有(和)组成的字符串中，并且这些字符串是有效的，有效的定义就是所有的括号都可以唯一配对等，具体意思看题目和样例即可理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string removeOuterParentheses(string S) {
        int cnt=0;
        string ans;
        for(int i=0;i<S.length();i++){
            if(S[i]=='('){
                if(cnt>0) ans.push_back(S[i]);
                cnt++;
            }else{
                cnt--;
                if(cnt>0) ans.push_back(S[i]);
            }
        }
        return ans;
    }
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Remove Outermost Parentheses.

Memory Usage: 9 MB, less than 57.55% of C++ online submissions for Remove Outermost Parentheses.

分割线
#### 2019-06-14 四题

题目链接804. Unique Morse Code Words Easy

  • 计算机图形学实验课太没意思，刷个题吧。

就是26个小写字母每个都映射到一个摩斯代码，给你几个字符串，每个字母都换成它们对应的摩丝代码，计算摩丝代码组成新的字符串有几个是互相不同的。Return the number of different transformations among all words we have.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int uniqueMorseRepresentations(vector<string>& words) {
        string str[26]={".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        unordered_set<string>se;
        int ilen=words.size();
        for(int i=0;i<ilen;i++){
            string cur;
            int jlen=words[i].size();
            for(int j=0;j<jlen;j++){
                cur.append(str[(words[i][j]-'a')]);
            }
            se.insert(cur);
        }
        return se.size();
    }
};

Runtime: 4 ms, faster than 93.96% of C++ online submissions for Unique Morse Code Words.

Memory Usage: 9 MB, less than 70.09% of C++ online submissions for Unique Morse Code Words.

题目链接 242. Valid AnagramEasy

返回字符串$s$和$t$是否由相同的小写字母组成。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isAnagram(string s, string t) {
        int a[26];
        memset(a,0,sizeof a);
        for(auto i : s) a[(i-'a')]++;
        for(auto i : t) a[(i-'a')]--;
        for(int i=0;i<26;i++){
            if(a[i]) return false;
        }
        return true;
    }
};

Runtime: 8 ms, faster than 98.40% of C++ online submissions for Valid Anagram.

Memory Usage: 9.4 MB, less than 54.89% of C++ online submissions forValid Anagram.

题目链接 349. Intersection of Two ArraysEasy

返回一个去重的$vector$,里面包含$nums1$和$nums2$中相同的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        int pointer1=0,pointer2=0;
        int len1=nums1.size(),len2=nums2.size();
        vector<int>ve;
        ve.clear();
        while(pointer1<len1&&pointer2<len2){
            if(nums1[pointer1]==nums2[pointer2]) {
                ve.push_back(nums1[pointer1]);
                pointer1++;
                pointer2++;
            }
            else if(nums1[pointer1]<nums2[pointer2]) pointer1++;
            else pointer2++;
        }
        ve.erase(unique(ve.begin(),ve.end()),ve.end());//对vector去重
        return ve;
    }
};

Runtime: 4 ms, faster than 99.68% of C++ online submissions for Intersection of Two Arrays.

Memory Usage: 9.1 MB, less than 83.39% of C++ online submissions forIntersection of Two Arrays.

下面是别人的代码，借助了$set$。没我那个快！😄

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int>ve;
        unordered_set<int>n1(nums1.begin(),nums1.end());
        unordered_set<int>n2(nums2.begin(),nums2.end());
        for(auto i : n1){
            if(n2.count(i)) ve.push_back(i);
        }
        return ve;
    }
};

Runtime: 8 ms, faster than 90.58% of C++ online submissions for Intersection of Two Arrays.

Memory Usage: 9.8 MB, less than 10.57% of C++ online submissions forIntersection of Two Arrays.

题目链接 350. Intersection of Two Arrays IIEasy

题意和上面那个一样，就是不去重了，正好把我的那代码去重那一步的ve.erase(unique(ve.begin(),ve.end()),ve.end());删掉就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        int pointer1=0,pointer2=0;
        int len1=nums1.size(),len2=nums2.size();
        vector<int>ve;
        ve.clear();
        while(pointer1<len1&&pointer2<len2){
            if(nums1[pointer1]==nums2[pointer2]) {
                ve.push_back(nums1[pointer1]);
                pointer1++;
                pointer2++;
            }
            else if(nums1[pointer1]<nums2[pointer2]) pointer1++;
            else pointer2++;
        }
        return ve;
    }
};

Runtime: 4 ms, faster than 99.72% of C++ online submissions for Intersection of Two Arrays II.

Memory Usage: 9.2 MB, less than 69.69% of C++ online submissions forIntersection of Two Arrays II.

分割线
#### 2019-06-15

刚考完四级考试，作文是参观小学，翻译是灯笼🏮，很难受。

题目链接 21. Merge Two Sorted Lists Easy

就是合并两个有顺序的链表并返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* ret=new ListNode(0);
        ListNode* p=ret; 
        while(l1&&l2){
            if(l2->val<=l1->val){
                p->next=l2;
                l2=l2->next;
            }else{
                p->next=l1;
                l1=l1->next;
            }
            p=p->next;
        }
        if(l1) p->next=l1;
        if(l2) p->next=l2;
        return ret->next;
    }
};

Runtime: 4 ms, faster than 99.65% of C++ online submissions for Merge Two Sorted Lists.

Memory Usage: 9.1 MB, less than 47.10% of C++ online submissions forMerge Two Sorted Lists.

题目链接 50. Pow(x, n) Medium

题目就是求$x^n$ 。快速幂，注意小数情况就可以了。好像有个坑点是$n$会爆$int$的上界。因为$n$的范围是$[-2^{31},2^{31}-1]$，而我的代码有一步是$n=-n$，然后如果$n=-2^{31}$就凉了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    double myPow(double x, int n) {
        long long nn=n;
        if(x==1) return 1;
        if(n==0){
            if(x==0) return 0;
            return 1;
        }
        if(x==0) return 0;
        int flag=0;
        if(nn<0) {
            flag=1;
            nn=-nn;
        }
        double ret=1;
        while(nn){
            if(nn&1) ret*=x;
            x*=x;
            nn>>=1;
        }
        if(flag) return 1/ret;
        return ret;
    }
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Pow(x, n).

Memory Usage: 8.3 MB, less than 70.62% of C++ online submissions forPow(x, n).

  • 分割线<div style="background:gray;height=5px;border-radius:20px"><center><font color="white">分割线</font></center></div>
  • Easy<strong style="background:#5cb85c;color:white;border-radius:10px;padding:1px 3px">Easy</strong>
  • Medium<strong style="background:#f0ad4e;color:white;border-radius:10px;padding:1px 3px">Medium</strong>
  • Hard<strong style="background:#d9534f;color:white;border-radius:10px;padding:1px 3px">Hard</strong>