每日一题计划

  • 做个水题爽一下,每天做每天爽

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$之间节点的值的和。

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

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>