C++ Exercises: Data Structure I

Exercises: 448. Find All Numbers Disappeared in an Array

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.
Solution: use set to record all numbers had showed and find the the rest disappeared numbers.

#include <iostream>
#include <set>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        set<int> arr;
        for( auto value: nums ){
            arr.insert( value );
        }

        const int len = nums.size()+1;
        vector<bool> vis;
        for( int i = 0; i < len; ++i ){
            vis.push_back( false );
        }
        for( auto value: arr ){
            vis[value] = true;
        }
        vector<int> ans;
        for( int i = 1; i <= nums.size(); ++i ){
            if( !vis[i] ){
                ans.push_back( i );
            }
        }
        return ans;
    }
};

int main()
{
    vector<int> nums{ 4,3,2,7,8,2,3,1 };
    Solution solver;
    auto ans = solver.findDisappearedNumbers( nums );
    for( auto value: ans ){
        cout << value << " ";
    }
    cout << "\n";
    return 0;
}

Tips: you can also increase the index by n that number had showed, then find all the numbers which are smaller than n.

Exercises: 48. Rotate Image

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
Solution: find the ruler about new position. For matrix nxm, just visit elements by 1->m on the columns and n->1 on the rows.

#include <iostream>
#include <set>
#include <vector>
using namespace std;

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        vector<int> elements;
        for( auto row : matrix ){
            for( auto value: row ){
                elements.push_back( value );
            }
        }

        for( int i = 0; i < n; ++i ){ // col
            for( int j = n-1; j >=0; --j ){ //row
                matrix[i][n-1-j] = elements[j*n+i];
            }
        }
    }
};
int main()
{
    vector<vector<int>> matrix{ {1,2,3},{4,5,6},{7,8,9} };
    Solution solver;
    solver.rotate( matrix );
    for( auto row : matrix ){
        for( auto value: row ){
            cout << value << " ";
        }
        cout << endl;
    }
    return 0;
}

Tips: you can also flip the matrix horizontally and diagonally.

Exercises: 240. Search a 2D Matrix II

Write an efficient algorithm that searches for a target value in an m x n integer matrix.
Solution: find the target number by binary search algorithm diagonally in two dimensions system.

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    bool searchHorizontally(vector<vector<int>>& matrix, int target, int startIndex){
        int l = startIndex;
        int r = matrix[startIndex].size() - 1;
        while( r >= l )
        {
            int mid = (l+r)>>1;
            if( matrix[startIndex][mid] == target ){
                return true;
            }
            else if( matrix[startIndex][mid] < target ){
                l = mid+1; // +1 if it's integer search
            }
            else{
                r = mid-1;
            }
        }
        return false;
    }

    bool searchVertically(vector<vector<int>>& matrix, int target, int startIndex){
        int l = startIndex;
        int r = matrix.size() - 1;
        while( r >= l )
        {
            int mid = (l+r)>>1;
            if( matrix[mid][startIndex] == target ){
                return true;
            }
            else if( matrix[mid][startIndex] < target ){
                l = mid+1; // +1 if it's integer search
            }
            else{
                r = mid-1;
            }
        }
        return false;
    }

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int diagLen = min( matrix.size(), matrix[0].size() );
        for( int i = 0; i < diagLen; ++i )
        {
            if( searchHorizontally( matrix, target, i ) || searchVertically( matrix, target, i ) ){
                return true;
            }
        }
        return false;
    }
};

int main()
{
    vector<vector<int>> matrix{{1,4,7,11,15},{2,5,8,12,19},{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
    Solution solver;
    cout << solver.searchMatrix( matrix, 5 ) << endl;
    return 0;
}

Exercises: 769. Max Chunks To Make Sorted

You are given an integer array arr of length n that represents a permutation of the integers in the range [0, n – 1].We split arr into some number of chunks (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array.Return the largest number of chunks we can make to sort the array.
Solution: just split and count the blocks.

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    bool useAllPosition( vector<int> arr, int index ){
        if( arr.size() < 1 ) return false;
        sort( arr.begin(), arr.end() );
        for( int i = 0; i < arr.size(); ++i ){
            if( arr[i] != i+index ){
                return false;
            }
        }
        return true;
    }

    int maxChunksToSorted(vector<int>& arr) {
        if( arr.size() == 0 ) return 0;
        if( arr.size() == 1 ) return 1;

        int maxValue = 1;
        for( int i = 0; i < arr.size(); ++i ){
            vector<int> arr0;
            for( int j = 0; j <= i; ++j ){
                arr0.push_back( arr[j] );
            }
            vector<int> arr1;
            for( int j = i+1; j < arr.size(); ++j ){
                arr1.push_back( arr[j] );
            }

            if( useAllPosition(arr0, 0) && useAllPosition(arr1, i+1) ){
                maxValue = max(maxValue, maxChunksToSorted( arr0 ) + maxChunksToSorted( arr1 ) );
            }
        }
        return maxValue;
    }
};

int main()
{
    vector<int> arr{1,0,2,3,4};
    Solution solver;
    cout << solver.maxChunksToSorted( arr ) << endl;
    return 0;
}