其实没做过LeetCode的 contest
url: https://leetcode.com/contest/leetcode-weekly-contest-14
今天头疼就virtual一场结果脸比较好 抽到的题很简单….
Score 3:
Number Complement : 简单的把一个数二进制下0换成1 1换成0
xjb写 由于人比较蠢不会用位运算就全算出来了
My_Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int findComplement(int num) {
vector<int>q;
while(num){
q.push_back(num%2);
num/=2;
}
int ss=q.size();
for(int i=ss-1;i>=0;i--){
if(q[i]==1) q[i]=0;
else q[i]=1;
}
int ans=0;
for(int i=ss-1;i>=0;i--){
ans*=2;
ans+=q[i];
}
return ans;
}
};
|
Score 6:
Magical String ：一个魔法字符串仅由1和2组成，这个字符串是自生成的。
魔法字符串：“1221121221221121122”
分组后：1 22 11 2 1 22 1 22 11 2 11 22..
每组中个数为：1 2 2 1 1 2 1 2 2 1 2 2
你会发现以上三个都是同一个字符串（无视空格）
N不超过100000
XJB模拟一瞎就好了…详情见代码
My_Code:
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
| class Solution {
public:
int magicalString(int n) {
if (n == 0) {
return 0;
}
if (n >= 1 && n <= 3) {
return 1;
}
int count = 1, num = 1, head = 2, tail = 3;
int* arr = new int[n + 1];
arr[0] = 1;
arr[1] = arr[2] = 2;
while (tail < n) {
for (int i = 0; i < arr[head]; i++) {
arr[tail] = num;
if (tail < n && num == 1) {
count++;
}
tail++;
}
num = num ^ 3;
head++;
}
return count;
}
};
|
Score 7:
License Key Formatting :
给一个有大小写字母和’-‘的字符串 要你按照K个一组将他恢复成最开始的样子 最前的一组可以不满足K
随便模拟一下
My_Code:
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:
string licenseKeyFormatting(string S, int K) {
string tmp;
int ss=S.size();
for(int i=0;i<ss;i++){
if(S[i]=='-') continue;
else if(S[i]>='a'&&S[i]<='z') tmp+=S[i]-'a'+'A';
else tmp+=S[i];
}
int st=tmp.size();
string ans;
int cnt=0;
for(int i=st-1;i>=0;i--){
ans+=tmp[i];
cnt++;
if(cnt==K&&i!=0){
cnt=0;
ans+='-';
}
}
reverse(ans.begin(),ans.end());
return ans;
}
};
|
Score 9:
Sliding Window Median : 唯一一个难一点的题
给一个数组，再给一个K长度的滑窗要，这个滑窗一点点向后移动，求滑窗内中位数。
一开始想是平衡树，再看看感觉两个heap就够了，对于没用的数我们不一定要从heap里拿掉，可以标记一下。
类似题：POJ 3784 Running Median
详情见code
My_Code:
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
| class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
vector<double> medians;
unordered_map<int, int> hash;
priority_queue<int, vector<int>> bheap;
priority_queue<int, vector<int>, greater<int>> theap;
int i = 0;
while (i < k) bheap.push(nums[i++]);
for (int count = k/2; count > 0; --count) theap.push(bheap.top()); bheap.pop();
while (true) {
if (k % 2) medians.push_back(bheap.top());
else medians.push_back( ((double)bheap.top() + theap.top()) / 2 );
if (i == nums.size()) break;
int m = nums[i-k], n = nums[i++], balance = 0;
if (m <= bheap.top()) { --balance; if (m == bheap.top()) bheap.pop(); else ++hash[m]; }
else { ++balance; if (m == theap.top()) theap.pop(); else ++hash[m]; }
if (!bheap.empty() && n <= bheap.top()) { ++balance; bheap.push(n); }
else { --balance; theap.push(n); }
if (balance < 0) { bheap.push(theap.top()); theap.pop(); }
else if (balance > 0) { theap.push(bheap.top()); bheap.pop(); }
while (!bheap.empty() && hash[bheap.top()]) { --hash[bheap.top()]; bheap.pop(); }
while (!theap.empty() && hash[theap.top()]) { --hash[theap.top()]; theap.pop(); }
}
return medians;
}
};
|
总结：我好菜啊 WA了好多次….最后一题做的也好慢….我死了