Huahua's Tech Road

花花酱 LeetCode 422. Find All Duplicates in an Array

By zxi on March 18, 2017

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

<b>Input:</b>

[4,3,2,7,8,2,3,1]

<b>Output:</b>

[2,3]

class Solution {

public:

vector<int> findDuplicates(vector<int>& nums) {

vector<int> ans;

for(auto num : nums) {

int index = abs(num)-1;

if (nums[index] < 0)

ans.push_back(index+1);

nums[index]*=-1;

}

return ans;

}

};

花花酱 LeetCode 128. Longest Consecutive Sequence

By zxi on March 15, 2017

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

class Solution {

public:

int longestConsecutive(vector<int> &num) {

unordered_map<int,int> m;

int ans = 0;

for(auto n : num) {

if(m.count(n)) continue;

if(m.count(n-1) && m.count(n+1)){

int l = m[n-1], r = m[n+1];

m[n] = m[n-l] = m[n+r] = r+l+1;

} else if(m.count(n-1)) {

int l = m[n-1];

m[n] = m[n-l] = l+1;

} else if(m.count(n+1)) {

int r = m[n+1];

m[n] = m[n+r] = r+1;

} else {

m[n] = 1;

}

ans = max(ans, m[n]);

}

return ans;

}

};

花花酱 Leetcode 371. Sum of Two Integers

By zxi on March 15, 2017

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

class Solution {

public:

int getSum(int a, int b) {

return b==0?a:getSum(a^b, (a&b)<<1);

}

};

[ZOJ] 3612: Median

By zxi on March 12, 2017

// 3934633 2017-03-13 10:48:25 Accepted 3612 C++0x 900 540 xxfflower

#include <iostream>

#include <vector>

#include <unordered_map>

#include <algorithm>

#include <queue>

#include <set>

using namespace std;

typedef long long int64;

int main() {

int t,n,x;

char op[20];

cin>>t;

while(t--) {

scanf("%d", &n);

vector<int64> a;

while(n--) {

scanf("%s %d", op, &x);

auto it = lower_bound(a.begin(), a.end(), x);

if(op[0] == 'r') {

if(it==a.end() || *it != x) {

puts("Wrong!");

continue;

} else {

a.erase(it);

if(a.empty()) {

puts("Empty!");

continue;

}

} else if(op[0] == 'a') {

a.insert(it, x);

}

if(a.size()%2==1) {

printf("%lld\n", a[a.size()/2]);

} else {

int64 ans = a[a.size()/2-1] + a[a.size()/2];

if(ans%2==0)

printf("%lld\n", ans/2);

else

printf("%.1lf\n", ans/2.0);

}

return 0;

}

[ZOJ] 3713: In 7-bit

By zxi on March 12, 2017

// 3934609 2017-03-13 08:38:54 Accepted 3713 C++0x 290 6428 xxfflower

#include <iostream>

#include <string>

#include <iomanip>

using namespace std;

void put_hex(int byte) {

cout << hex << uppercase << setfill('0') << setw(2) << byte;

}

void put_str(const string& s) {

for(char c : s)

put_hex(c);

}

void put_len(int length) {

while(length>=128) {

put_hex(length % 128 + 128);

length >>= 7;

}

put_hex(length);

}

int main(int argc, char const *argv[])

{

int n;

cin>>n;

string s;

getline(cin, s);

while(n--) {

getline(cin, s);

put_len(s.length());

put_str(s);

cout<<endl;

}

return 0;

}