Leetcode junior others

大半夜的又睡不着了。。。

玩也是玩,再写几道题吧

1、位1的个数

(1).传送门

传送门:位1的个数

(2).结果

超过98.61%

(3).代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int hammingWeight(uint32_t n) {
int p = 0;
while(1) {
if(!n)
break;
if(n%2)
p++;
n /= 2;
}
return p;
}
};

2、汉明距离

(1).传送门

传送门:汉明距离

(2).结果

超过89.85%

一开始竟然读错题了,我还奇怪这么简单的题我都错。。。

(3).代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int hammingDistance(int x, int y) {
int p = 0,a,b;
for(int i = 0;i < 32;i++) {
a = x%2; x /= 2;
b = y%2; y /= 2;
if(a != b) {
p++;
}
}
return p;
}
};

3、颠倒二进制位

(1).传送门

传送门:颠倒二进制位

(2).结果

超过98.80%

使用位运算解决

question:如果多次调用这个函数,你将如何优化你的算法?
一时没想到更好的解决方法,以后或许可以回头再看一看这个问题

(3).代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t m = 0;
for(int i = 0;i < 32;i++) {
m <<= 1;
m = m|(n&1);
n >>= 1;
}
return m;
}
};

4、帕斯卡三角形

(1).传送门

传送门:帕斯卡三角形

(2).结果

超过100.00%

对于二维vector需要事先申请空间

(3).代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int> > v(numRows);
for(int i = 0;i < numRows;i++) {
for(int j = 0;j <= i;j++) {
if(j == 0 || j == i)
v[i].push_back(1);
else {
v[i].push_back(v[i-1][j-1]+v[i-1][j]);
}
}
}
return v;
}
};

5、有效的括号

(1).传送门

传送门:有效的括号

(2).结果

超过100.00%

代码写的有点丑

(3).代码

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
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
bool isValid(string s) {
vector<char> v;
int flag = 0;
int si = s.size();
if(si == 0)
return true;
v.push_back(s[0]);
for(int i = 1;i < si;i++) {
if(s[i] == '(' || s[i] == '[' || s[i] == '{') {
v.push_back(s[i]);
flag++;
}
else {
if(s[i] == ')') {
if(s[i]-v[flag] == 1) {
v.pop_back();
flag--;
}
else {
return false;
}
}
else {
if(s[i]-v[flag] == 2) {
v.pop_back();
flag--;
}
else {
return false;
}
}
}
}
if(!v.empty())
return false;
return true;
}
};

6、缺失数字

(1).传送门

传送门:缺失数字

(2).结果

超过48.57%

时间O(n)

空间O(1)

(3).代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int missingNumber(vector<int>& nums) {
int si = nums.size();
int temp = si;
for(int i = 0;i < si;i++)
{
temp ^= i;
temp ^= nums[i];
}
return temp;
}
};

6、缺失数字

(1).传送门

传送门:缺失数字

(2).结果

超过48.57%

时间O(n)

空间O(1)

(3).代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int missingNumber(vector<int>& nums) {
int si = nums.size();
int temp = si;
for(int i = 0;i < si;i++)
{
temp ^= i;
temp ^= nums[i];
}
return temp;
}
};