Ankur's Blog

Data Structure

Ankur's BlogNovember 24, 2018Code Repository, STL No comments

1. Vector

Most common methods:
push_back() -- O(1)
[ ] --> bracket operators -- O(1)
size() -- O(1)

code:

vector<int> v;                   // v = {}

cout << v.size() << endl;   // outputs 0

v.push_back(20);            // v = {20}

v.push_back(10);            // 20, 10

v.push_back(10);            // 20, 10, 10

cout << v[1]<<endl;         // 10

cout << v.size() << endl;   // 3

2. set

Most common methods:

insert() ---> O(logN)
find() ---> O(logN)
size() ---> O(1)

Code:

set<int> s;              // s = {}
cout << s.size() << endl;   // outputs 0
s.insert(20);            // s = {20}
s.insert(10);            // 10, 20
s.insert(10);            // 10, 20
auto it = s.find(10);   // it is an iterator that points to 10
cout << (it != s.end() ? "FOUND" : "")<<endl;         // FOUND
cout << v.size() << endl;   // 2

3. unordered_set

Most common methods:
insert() ---> O(1)
find() ---> O(1)
size() ---> O(1)

Code:

unordered_set<int> s;              // s = {}
cout << s.size() << endl;   // outputs 0
s.insert(20);            // s = {20}
s.insert(10);            // 10, 20 {could in any order}
s.insert(10);            // 10, 20
auto it = s.find(10);   // it is an iterator that points to 10
cout << (it != s.end() ? "FOUND" : "")<<endl;         // FOUND
cout << v.size() << endl;   // 2

for(auto e: s) {...}

for(auto it = s.begin(); it != s.end(); ++it) {...}

4.map

Most common methods:
insert() ---> O(1)-->O(logN)
find() ---> O(1) -->O(logN)
size() ---> O(1) --> O(1)
- [ ] --> bracket operators -->O(logN)
Code:

map<int, int> m;              // s = {}
cout << m.size() << endl;   // outputs 0
m.insert(make_pair(20, 1)); // m = {(20,1)}
m.insert(make_pair(10, 1));   // m = {(10,1), (20,1)}
m[10]++                      // m = {(10,2), (20,1)}
auto it = m.find(10);   // it is an iterator that points to (10,1)
cout << (it != m.end() ? it->second: 0)<<endl; // 2
auto it2 = m.find(10); // it is an iterator that points to (20,1)
cout << (it2 != m.end() ? it2->first: 0)<<endl; // 20
cout << v.size() << endl;   // 2

5. Unordered_map
- Most common methods:
- insert() ---> O(1)-->O(1)
- find() ---> O(1) -->O(1)
- size() ---> O(1) --> O(1)
  - [ ] --> bracket operators -->O(1)
  Code:
  
  map<int, int> m;              // s = {}
  
  cout << m.size() << endl;   // outputs 0
  
  m.insert(make_pair(20, 1)); // m = {(20,1)}
  
  m.insert(make_pair(10, 1));   // m = {(10,1), (20,1)}
  
  m[10]++                      // m = {(10,2), (20,1)}
  
  auto it = m.find(10);   // it is an iterator that points to (10,1)
  
  cout << (it != m.end() ? it->second: 0)<<endl; // 2
  
  auto it2 = m.find(10); // it is an iterator that points to (20,1)
  
  cout << (it2 != m.end() ? it2->first: 0)<<endl; // 20
  
  cout << v.size() << endl;   // 2

Construct the Array

Ankur's BlogNovember 24, 2018DP, Hackerrank, Online Judge No comments

Construct the Array

Topic: DP

Complexity: O(n)

Solution:

Code:

const long long mod = 1000000000+7;
long countArray(int n, int k, int x) {
    // Return the number of ways to fill in the array.
    vector<long long> a(n), b(n);
    a[0] = x == 1 ? 1 : 0;
    b[0] = x == 1 ? 0 : 1;

    for(int i = 1; i < n; i++){
        a[i] = b[i - 1] % mod;
        b[i] = (a[i- 1](k-1) + b[i-1] (k-2) )%mod;
    }
    return a[n-1];
}

1136 - Division by 3

Ankur's BlogNovember 23, 2018LightOJ, Online Judge No comments

1136 - Division by 3

Explanation

#include<bits/stdc++.h>

using namespace std;

int cnt(int n)

{

if(n == 0)return 0;

int res = (n/3)*2;

if(n%3 == 2)res += 1;

return res;

}

int main()

{

int t;

cin >> t;

for(int cs = 1; cs <= t; cs++){

int a,b;

cin >> a >> b;

cout << "Case "<<cs << ": "<< cnt(b) - cnt(a - 1) <<endl;

}

return 0;

}

1182 - Parity

Ankur's BlogNovember 23, 2018LightOJ, Online Judge No comments

1182 - Parity

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin >> t;
    for(int cs = 1; cs <= t; cs++){
        int x;
        cin >> x;
        if(__builtin_parity(x))cout << "Case "<<cs<< ": odd\n";
        else cout << "Case "<<cs<< ": even\n";
    }
    return 0;
}

1133 - Array Simulation

Ankur's BlogNovember 23, 2018LightOJ, Online Judge No comments

1133 - Array Simulation

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

//map<int , int>M;

int main()

{

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

freopen("out.txt", "w", stdout);

#endif

int t;

cin >> t;

for(int cs = 1; cs <= t; cs++){

int n,m;

cin >> n >>m;

int a[n+2];

for(int i = 0; i < n; i++){

cin >> a[i];

}

while(m--){

char x;

int val;

cin >> x;

if(x == 'S'){

cin >> val;

for(int i = 0; i < n; i++)

a[i] += val;

//sum +=vall;

}

else if(x == 'M'){

cin >> val;

for(int i = 0; i < n; i++)

a[i] *= val;

//mul *= val;

}

else if(x == 'D'){

cin >> val;

for(int i = 0; i < n; i++)

a[i] /= val;

//div *= val;

}

else if(x == 'R'){

reverse(a, a+n);

}

else if(x == 'P'){

int y,z;

cin >> y >> z;

swap(a[y], a[z]);

}

//for(int i =0; i < n; i++)cout << a[i]<< " ";

// cout << endl <<"------------"<<endl;

}

cout << "Case "<<cs << ":\n";

for(int i = 0; i < n; i++){

cout << a[i];

if(i < n-1)cout << " ";

}

cout << endl;

}

return 0;

}

773. Sliding Puzzle

Ankur's BlogNovember 22, 2018LeetCode, Online Judge No comments

773. Sliding Puzzle

source

Topic: BFS

Time Complexity: (n*m)!

Solution 01

class Solution{
public:
int slidingPuzzle (vector<vector<int>>& board)
{
    constexpr int row = 2;
    constexpr int col = 3;
    string goal, start;
    for(int i = 0; i < board.size(); i++)
      for(int j = 0; j < board[0].size(); j++){
        start += (board[i][j] + '0');
        goal += (icol + j + 1) % (rowcol) + '0';//12345.....0
      }
      if (start == goal) return 0;

      constexpr int dirs[4][2] = {{-1,0}, {1,0}, {0,1}, {0, -1}};

      set<string> visited{start};
      int steps = 0;
      queue<string>Q;
      Q.push(start);
      while (!Q.empty()){
        steps++;
        int sz = Q.size();
        while(sz-- > 0){
        string s = Q.front();
        Q.pop();
        int p = s.find('0');
        int y = p/col;
        int x = p%col;
        for(int i = 0; i < 4; i++){
          int tx = x + dirs[i][0];
          int ty = y + dirs[i][1];
          if(tx < 0 || ty < 0 || tx >= col || ty >= row) continue;
          int pp = ty * col + tx;
          string t(s);
          swap(t[p], t[pp]);
          if(visited.count(t))continue;
          if(t == goal) return steps;
          visited.insert(t);
          Q.push(t);
         }
        }
      }
      return -1;
}
};

Solution 02

Simplified, only works on 3×2 board

class Solution
{
public:
    int slidingPuzzle (vector<vector<int>> & board){
        const string goal = "123450";
        string start;
        for(int i = 0; i < board.size(); i++)
            for(int j = 0; j < board[0].size(); j++)
                start += (board[i][j] + '0');

            if(start == goal)return 0;

            const vector<vector<int>> idx{{1,3}, {0,2,4}, {1,5}, {0,4}, {1,3,5}, {2,4}};

            set<string> visited{start};
            int steps = 0;
            queue<pair<string,int>> Q;
            Q.emplace(start, start.find('0'));
            while(!Q.empty())
            {
                steps++;
                int sz = Q.size();
                while(sz-- > 0){
                    const auto& p = Q.front();
                    Q.pop();
                    for(int index: idx[p.second]){
                        string t(p.first);
                        swap(t[p.second], t[index])
                        if(visited.count(t))continue;
                        if(t == goal)return steps;
                        visited.insert(t);
                        Q.emplace(t, index);
                    }
                }
            }
            return -1;
    }

};

771. Jewels and Stones

Ankur's BlogNovember 22, 2018LeetCode, Online Judge No comments

771. Jewels and Stones

Solution 01:

Complexity: O(N^2)

class Solution {
public:
    int numJewelsInStones(string J, string S) {
        int cnt = 0;
for(int i = 0; i < S.size(); i++){
    for(int k = 0; k < J.size(); k++){
        if(S[i] == J[k])cnt++;
    }
    }
        return cnt;
    }
};

Solution 02:

complexity: N log(N)

class Solution {
public:
    int numJewelsInStones(string J, string S) {
   int cnt = 0;

unordered_set<char>jewels;

for(int i = 0; i < J.size(); i++){
    jewels.insert(J[i]);
}

for(int i = 0; i < S.size(); i++){
    if(jewels.find(S[i]) != jewels.end()) cnt++;
}
return cnt;
    }
};

Solution 03:

Complexity: O(N)

class Solution {
public:
    int numJewelsInStones(string J, string S) {
   int cnt = 0;
        map<char, bool>jewels;

for(int i = 0; i < J.size(); i++){
    jewels[J[i]] = true;
}

for(int i = 0; i < S.size(); i++){
    if(jewels[S[i]]) cnt++;
}
return cnt;
    }
};

Minimize Max Distance to Gas Station

Ankur's BlogNovember 22, 2018LeetCode, Online Judge No comments

Minimize Max Distance to Gas Station

#include<bits/stdc++.h>
using namespace std;

struct Interval
{
Interval (int d): num(d), den(1), dist(d){}

bool operator< (const Interval &d) const {return dist < d.dist;}
double num,den, dist;
void update(){den++, dist = num/den;}
};

template<typename T>
priority_queue<T> make_priority_queue (vector<int>& v){
vector<int> t(v.size());

adjacent_difference(v.begin(), v.end(), t.begin());
t.erase (t.begin());
return priority_queue<T> (t.begin(), t.end());
}

double minmaxGasDist(vector<int>& stations, int k)
{
auto PQ = make_priority_queue<Interval> (stations);
double mx_dist = (stations.back() - stations.front())/static_cast<double> (k+1);

while(k){
    auto top = PQ.top();
    PQ.pop();
    while(k && (top.dist >= PQ.top().dist || top.dist > mx_dist)){
      top.update();
      k--;
    }
    PQ.push(top);
}
return PQ.top().dist;
}

int main()
{
     #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    vector<int>V;
    int n,k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
      int x;
      cin >> x;
      V.push_back(x);
    }
    cout << minmaxGasDist(V, k)<<endl;

}

779. K-th Symbol in Grammar

Ankur's BlogNovember 22, 2018LeetCode, Online Judge No comments

779. K-th Symbol in Grammar

Nth row = (N-1)th row + (n-1)th Inverse.

Example;
1st row = 0
2nd row = 1st row + 1st row Inverse (01)

Every row will power of two.

Solution:

class Solution {
public:
    int kthGrammar (int N, int k)
{
long s = 1 << (N - 1), flips = 0;

while(s > 2){
    if(k > s/2){
      k -= s/2;
      flips++;
    }
    s /= 2;
}
k--;
//cout << "---------"<<k<<endl;
if(flips&1)k = 1 - k;
return k;
}
};

SpliBST

Ankur's BlogNovember 22, 2018LeetCode, Online Judge No comments

SplitBST

It's a premium problem. So it's not tested;

Solution:

vector<TreeNode> SplitBST(TreeNode root, int V)
{
vector<TreeNode*> ans (2, nullptr)

if(root == nullptr) return ans;

int x = root->val > V ? 1 : 0;
int y = root->val > V ? 0 : 1;
auto& node = root->val > V ? root->left : root->right;
ans[x] = root;
auto t = SplitBST(node, V);
node = t[x];
ans[y] = t[y];
return ans;
}

1. Vector

Most common methods:

push_back() -- O(1)

[ ] --> bracket operators -- O(1)

size() -- O(1)

code:

vector<int> v; // v = {}

cout << v.size() << endl; // outputs 0

v.push_back(20); // v = {20}

v.push_back(10); // 20, 10

v.push_back(10); // 20, 10, 10

cout << v[1]<<endl; // 10

cout << v.size() << endl; // 3

2. set

Most common methods:

insert() ---> O(logN)

find() ---> O(logN)

size() ---> O(1)

Code:

set<int> s; // s = {}cout << s.size() << endl; // outputs 0s.insert(20); // s = {20}s.insert(10); // 10, 20s.insert(10); // 10, 20auto it = s.find(10); // it is an iterator that points to 10cout << (it != s.end() ? "FOUND" : "")<<endl; // FOUNDcout << v.size() << endl; // 2

3. unordered_set

Most common methods:

insert() ---> O(1)

find() ---> O(1)

size() ---> O(1)

Code:

for(auto e: s) {...}

for(auto it = s.begin(); it != s.end(); ++it) {...}

4.map

Most common methods:

insert() ---> O(1)-->O(logN)

find() ---> O(1) -->O(logN)

size() ---> O(1) --> O(1)

[ ] --> bracket operators -->O(logN)

Code:

5. Unordered_map

Most common methods:

insert() ---> O(1)-->O(1)

find() ---> O(1) -->O(1)

size() ---> O(1) --> O(1)

[ ] --> bracket operators -->O(1)

Code:

map<int, int> m; // s = {}

cout << m.size() << endl; // outputs 0

m.insert(make_pair(20, 1)); // m = {(20,1)}

m.insert(make_pair(10, 1)); // m = {(10,1), (20,1)}

m[10]++ // m = {(10,2), (20,1)}

auto it = m.find(10); // it is an iterator that points to (10,1)

cout << (it != m.end() ? it->second: 0)<<endl; // 2

auto it2 = m.find(10); // it is an iterator that points to (20,1)

cout << (it2 != m.end() ? it2->first: 0)<<endl; // 20

cout << v.size() << endl; // 2

Topic: DP

Complexity: O(n)

Solution:

Code:

#include<bits/stdc++.h>

using namespace std;

int cnt(int n)

{

if(n == 0)return 0;

int res = (n/3)*2;

if(n%3 == 2)res += 1;

return res;

}

int main()

{

int t;

cin >> t;

for(int cs = 1; cs <= t; cs++){

int a,b;

cin >> a >> b;

cout << "Case "<<cs << ": "<< cnt(b) - cnt(a - 1) <<endl;

}

return 0;

}

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

//map<int , int>M;

set<int> s; // s = {}
cout << s.size() << endl; // outputs 0
s.insert(20); // s = {20}
s.insert(10); // 10, 20
s.insert(10); // 10, 20
auto it = s.find(10); // it is an iterator that points to 10
cout << (it != s.end() ? "FOUND" : "")<<endl; // FOUND
cout << v.size() << endl; // 2