Преобразование элементов СТД контейнеры из прочих ЗППП контейнеров


Проблема

В этот HackerRank проблему мы попросили, чтобы повернуть элементы матрицы следующим образом: enter image description here

Пример входных и выходных

Первая и вторая записи, указать размер матрицы и третья запись, сколько раз он должен быть повернут. В качестве примера, следующий входной сигнал:

4 4 2
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

даст следующий вывод:

3 4 8 12
2 11 10 16
1 7 6 15
5 9 13 14

Решение

Моя идея заключалась в том, чтобы повернуть эти кольца.

#include <vector>
#include <iostream>
#include <algorithm>

using Matrix = std::vector<std::vector<int>>;

void rotate_mat (Matrix &mat, int r){
    auto m = mat.size(); // Number of rows
    auto n = mat[0].size(); // Number of columns
    auto n_rings = std::min(m,n)/2; // Number of rings
    for(auto ring_i=0; ring_i<n_rings; ++ring_i){
        // The elements of the ring are stored sequentially 
        // in v_ring so it can be rotated with std::rotate 
        std::vector<int>  v_ring;
        // v_ring_ptr points to the original places in the matrix,
        // so the rotation of v_ring can be assigned back to the matrix
        std::vector<int*> v_ring_ptr;
        // Top side of the ring
        for(auto j=ring_i; j<=(n-1)-ring_i; ++j) {
            v_ring.push_back(mat[ring_i][j]);
            v_ring_ptr.push_back(&mat[ring_i][j]);
        }
        // Right side of the ring
        for(auto i=ring_i+1; i<=(m-1)-ring_i; ++i) {
            v_ring.push_back(mat[i][(n-1)-ring_i]);
            v_ring_ptr.push_back(&mat[i][(n-1)-ring_i]);
        }
        // Bottom size of the ring
        for(auto j=(n-1)-ring_i-1; j>ring_i; --j) {
            v_ring.push_back(mat[(m-1)-ring_i][j]);
            v_ring_ptr.push_back(&mat[(m-1)-ring_i][j]);
        }
        // Left size of the ring
        for(auto i=(m-1)-ring_i; i>ring_i; --i) {
            v_ring.push_back(mat[i][ring_i]);
            v_ring_ptr.push_back(&mat[i][ring_i]);
        }

        std::rotate(v_ring.begin(),v_ring.begin()+r%v_ring.size(),v_ring.end());
        // Update the rotated values in the original matrix
        for (auto i=0; i<v_ring.size(); ++i){
            *v_ring_ptr[i] = v_ring[i];
        }
    }
};

Matrix read_matrix(int m, int n) {
    Matrix mat;
    mat.reserve(m);
    for(auto i=0; i<m; ++i) {
        mat.push_back(std::vector<int>{});
        mat[i].reserve(n);
        for(auto j=0; j<n; ++j) {
            int x; std::cin >> x;
            mat[i].push_back(x);
        }
    }
    return mat;
};

void print_matrix(Matrix &mat){
    for (auto& i : mat){
        for (auto& j : i) {
            std::cout << j << " ";
        }
        std::cout << "\n";
    }
};

int main() {
    int m,n; std::cin >> m >> n;
    int r; std::cin >> r;

    auto mat = read_matrix(m,n);
    rotate_mat(mat,r);
    print_matrix(mat);

    return 0;
}

Вопросы

Моя главная проблема заключается в том, что я хотел бы избежать v_ring скопировать эту часть:

for (auto i=0; i<v_ring.size(); ++i){
    *v_ring_ptr[i] = v_ring[i];
}

Есть ли способ, чтобы хранить ссылки на содержимое исходной матрицы, так что превращение в построенной кольца будут автоматически отражаться? Я попытался с std::reference_wrapper. Это почти работает, я могу изменить элементы в кольцо например с ++ оператор, но я не могу делать назначения, ни std::rotate имеет на них никакого влияния.

Любые идеи? Я также заинтересован в любой другой подход, который может прийти на ум! Я думал, что это так легко выразить в коде



268
7
задан 25 января 2018 в 08:01 Источник Поделиться
Комментарии
4 ответа

Некоторые вещи, чтобы отметить :


  • Как вы сказали, есть std::min(m,n)/2; кольца.

  • кольцо R(r, p) есть 2*(r+p-2) элементы.

  • в верхней левой части кольца всегда координаты (x,x). Это видно в коде :) j = ring_i; v_ring.push_back(mat[ring_i][j]);

  • Ваш код использует достаточно эффективный объем памяти Для в-месте трансформации, и работает за o(М*N) времени, которое является наилучшим.

  • Производительности улучшение будет использовать один вектор для данных матрицы такие, что m(x,y) = m.data[x * cols + y]

Мы можем сделать это по-другому ?

Учитывая местную систему координат, где (0, 0) находится в верхнем левом углу ринга

qt example of this coordinate

Координаты (i,j), 0<=i<w, 0<=j<h, j == 0 || i == 0 на стороне кольца, могут быть перемещены на одну позицию с помощью функции

std::pair<int, int>
rotated_local_next(int i, int j, int w, int h)
{
if(j == 0) //top , special case top-right
{
return i == w-1 ? std::make_pair(i, ++j) : std::make_pair(++i, j);
}
if(i == w-1) //right, special case bottom-right
{
return j == h-1 ? std::make_pair(--i, j) : std::make_pair(i, ++j);
}
if(j == h-1) //bottom, special case bottom-left
{
return i == 0 ? std::make_pair(i, --j) : std::make_pair(--i, j);
}
if(i == 0) //left, special case top-left
{
return j == 0 ? std::make_pair(++i, j): std::make_pair(i, --j);
}

// cannot happen
throw std::exception{};
}

Теперь вы можете реализовать в матрице координат

std::pair<int, int>
rotated_matrix_next(int x, int y, int ring_i, int height, int width )
{
auto local_point = rotated_local_next(x-ring_i, y-ring_i, width-2*(ring_i), height-2*(ring_i));
return std::make_pair(local_point.first + ring_i, local_point.second + ring_i);
}

Все, что вам нужно сделать сейчас, чтобы реализовать итераторы сытно MoveAssignable и MoveConstructible. Начало твое кольцо-элемент в постановке кольца, кольцо, которое тоже конец кольца.

struct RingView
{
//ring start at 0
RingView(std::vector<std::vector<int>>& mat, int ringnumber)
: matrix(mat)
, rows(mat.size())
, cols(mat[0].size())
, ring(ringnumber)
{}

std::vector<std::vector<int>>& matrix;
int rows;
int cols;
int ring;

class ring_iterator : public std::iterator<std::forward_iterator_tag, int>
{
public:

ring_iterator(RingView* v = nullptr, int xpos = 0, int ypos = 0)
: view(v)
, x(xpos)
, y(ypos)
{}

ring_iterator(const ring_iterator& other) = default;
ring_iterator(ring_iterator&& other) = default;
ring_iterator& operator =(ring_iterator const&) = default;
ring_iterator& operator=(ring_iterator&&) = default;
virtual ~ring_iterator() = default;

RingView* view;
int x;
int y;

// Forward
ring_iterator& operator++() {
auto posnext = rotated_matrix_next(x, y, view->ring, view->cols, view->rows);

x = posnext.first;
y = posnext.second;
return *this;
}

ring_iterator operator++(int) {
auto posnext = rotated_matrix_next(x, y, view->ring, view->cols, view->rows);
ring_iterator next_iter = *this;
next_iter.x = posnext.first;
next_iter.y = posnext.second;
return next_iter;
}

bool operator==(const ring_iterator& other) const {
if(view == nullptr ){
return other.view == nullptr;
}
return view->ring == other.view->ring && x == other.x && y == other.y;
}

bool operator!=(const ring_iterator& other) const {
return !(*this == other);
}

// usually required
int& operator*() {
return view->matrix[x][y];
}
int* operator->() {
return &(view->matrix[x][y]);
}
};

ring_iterator begin()
{
return ring_iterator(this, ring, ring);
}

ring_iterator end()
{
return begin();
}

int size() const
{
return 2*(rows+cols -2) - 4 * ring;
}
};

Теперь вы можете вращать матрицу с помощью зрения. Чтобы иметь возможность вращаться в обе стороны (положительные по часовой стрелке, отрицательное-против часовой стрелки) мы используем

r' = (r % view.size() + view.size()) % view.size();

void rotate_mat (Matrix &mat, int r){
auto n_rings = std::min(mat.size(),mat[0].size())/2; // Number of rings
for(auto ring_i=0; ring_i<n_rings; ++ring_i){
RingView view(mat,ring_i);
int r_modulo = (r % view.size() + view.size()) % view.size();
auto next_location = view.begin();
std::advance(next_location, r_modulo);
std::rotate(view.begin(),next_location,view.end());
}
}

Полный код : https://ideone.com/I3vg5v

4
ответ дан 25 января 2018 в 05:01 Источник Поделиться

У меня есть решение, которое я искал из StackOverflow (проверьте это здесь). Сейчас ей не нужны лишние копии. Я ожидал, что это не так многословен. Я думаю, что они могут использовать алгоритмы на вектор ссылок может быть полезной функцией.

#include <vector>
#include <iostream>
#include <algorithm>

using Matrix = std::vector<std::vector<int>>;

/**
* Class implementing std::reference_wrapper that
* cannot be rebound after creation.
**/
template <class T>
class single_bind_reference_wrapper {

// pointer to the original element
T *p_;

public:

// typedefs
using type = T;

// Construct/Copy/Destroy
single_bind_reference_wrapper(T& ref) noexcept : p_(std::addressof(ref)) {}
single_bind_reference_wrapper(T&&) = delete;

// Enable implicit convertsion from ref<T> to ref<const T>,
// or ref<Derived> to ref<Base>
template <class U, std::enable_if_t<std::is_convertible<U*, T*>{}, int> = 0>
single_bind_reference_wrapper(const single_bind_reference_wrapper<U>& other) noexcept :
p_(&other.get()) { }

// Assignment
template <class U>
decltype(auto) operator=(U &&u) const
noexcept(std::is_nothrow_assignable<T, U>{}) {
return get() = std::forward<U>(u);
}

decltype(auto) operator=(const single_bind_reference_wrapper& other) const
noexcept(std::is_nothrow_assignable<T, T>{}) {
return get() = other.get();
}

// Access
operator T& () const noexcept { return *p_; }
T& get() const noexcept { return *p_; }
};

template <class T>
void swap(single_bind_reference_wrapper<T> &lhs,
single_bind_reference_wrapper<T> &rhs)
noexcept(std::is_nothrow_move_constructible<T>::value &&
std::is_nothrow_move_assignable<T>::value){
auto tmp = std::move(lhs.get());
lhs = std::move(rhs.get());
rhs = std::move(tmp);
}

void rotate_mat (Matrix &mat, int r){
auto m = mat.size(); // Number of rows
auto n = mat[0].size(); // Number of columns
auto n_rings = std::min(m,n)/2; // Number of rings
for(auto ring_i=0; ring_i<n_rings; ++ring_i){
// The elements of the ring are stored sequentially
// in v_ring so it can be rotated with std::rotate
std::vector<single_bind_reference_wrapper<int>> v_ring;
// Top side of the ring
for(auto j=ring_i; j<=(n-1)-ring_i; ++j) {
v_ring.push_back(mat[ring_i][j]);
}
// Right side of the ring
for(auto i=ring_i+1; i<=(m-1)-ring_i; ++i) {
v_ring.push_back(mat[i][(n-1)-ring_i]);
}
// Bottom size of the ring
for(auto j=(n-1)-ring_i-1; j>ring_i; --j) {
v_ring.push_back(mat[(m-1)-ring_i][j]);
}
// Left size of the ring
for(auto i=(m-1)-ring_i; i>ring_i; --i) {
v_ring.push_back(mat[i][ring_i]);
}
std::rotate(v_ring.begin(),v_ring.begin()+r%v_ring.size(),v_ring.end());
}
};

Matrix read_matrix(int m, int n) {
Matrix mat;
mat.reserve(m);
for(auto i=0; i<m; ++i) {
mat.push_back(std::vector<int>{});
mat[i].reserve(n);
for(auto j=0; j<n; ++j) {
int x; std::cin >> x;
mat[i].push_back(x);
}
}
return mat;
};

void print_matrix(Matrix &mat){
for (auto& i : mat){
for (auto& j : i) {
std::cout << j << " ";
}
std::cout << "\n";
}
};

int main() {
int m,n; std::cin >> m >> n;
int r; std::cin >> r;

auto mat = read_matrix(m,n);
rotate_mat(mat,r);
print_matrix(mat);

return 0;
}

2
ответ дан 26 января 2018 в 12:01 Источник Поделиться

"Я думал, что это так легко выразить в коде". К сожалению, что просто писать не всегда легко читать. Шесть петель, шесть однобуквенные переменные, без комментариев... честно говоря, я не могу следовать (т. е. я не стараюсь следовать, если я действительно нужно) и я не уверен, что вы сможете понять это сами в две недели.

Вы должны попробовать, чтобы лучше документировать свой код, либо через комментарии или, лучше, через имена переменных и тип.

Еще, пожалуй, проще - подход должен быть для создания функции изменения индекса по которой матрица доступна. Например, если вы хотите, чтобы элемент (0,0) матрицы, который был когда-то повернут, вам нужен элемент (0,1) базовой матрицы.

Вот мое мнение (я не положил много времени в алгоритм, но пытался сделать его легким для чтения):

struct Coordinates {int row=0, col=0; }; 
using Matrix_size = Coordinates;

// determine the ring to which those coordinates belongs
int ring_number(Coordinates coord, Matrix_size m_size, int offset=0) {
if ( coord.row == 0+offset
|| coord.col == 0+offset
|| coord.row == m_size.row-1-offset
|| coord.col == m_size.col-1-offset
) return 0;
return 1 + ring_number(coord, m_size, offset+1);
}

// return the coordinates of north-west and southwest angles of the ring
std::pair<Coordinates, Coordinates> ring_coordinates(Coordinates coord, Matrix_size m_size) {
auto rn = ring_number(coord, m_size);
return { Coordinates{rn, rn}, Coordinates{m_size.row-rn-1, m_size.col-rn-1} };
}

Coordinates rotate_coordinates(Coordinates c, Matrix_size m_size, int step=1) {
auto [min, max] = ring_coordinates(c, m_size);
step %= 2*(max.row-min.row+max.col-min.col); // number of elements in the ring;
for (int i = 0; i < step; ++i) {
if (c.row == min.row && c.col < max.col) ++c.col;
else if (c.col == max.col && c.row < max.row) ++c.row;
else if (c.row == max.row && c.col > min.col) --c.col;
else --c.row;
}
return c;
}

Затем вы можете использовать его, чтобы вывод повернутой матрицы таким образом:

#include <iostream>
#include <vector>

int main() {
std::vector<std::vector<int>> data = { {1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16} };
Matrix_size msz = {4, 4};
for (int row = 0; row < msz.row; ++row) {
for (int col = 0; col < msz.col; ++col) {
auto rc = rotate_coordinates(Coordinates{row, col}, msz, 1);
std::cout << data[rc.row][rc.col] << " ";
}
std::cout << '\n';
}
}

1
ответ дан 25 января 2018 в 01:01 Источник Поделиться

Полный код:

на самом деле главная задача и алгоритм для поворота показателей: преобразование (i, j) -> (_i, _j) по заданной матрице размера MxN и R. также важным условием является min(M, N) % 2 == 0.

поэтому нужно сначала построить массив перестановок M, N, Rдля этого нам не нужно самой матрицы.

#include <malloc.h>
#include <cstring>

typedef unsigned int UINT;

struct S
{
UINT i, j;
};

void rotate(UINT M, UINT N, UINT R, S* u)
{
u += M*N;
bool f = M > N;

UINT i = M, _i = 0;

do
{
--i; // i + _i == M - 1;

UINT j = N, _j = 0;

do
{
--j; // j + _j == N - 1;

UINT s; // side in {0,1,2,3}

if (f)
{
// (N < M) => (min(M, N)==N) => (j != _j)
// (j == _j) => (2*j == N - 1) => (min(M, N) == 2*j+1)

if (j > _j)
{
if (_i < _j) s = 2;
else if (i <= _j) s = 0;
else s = 3;

// (_i < _j) && (i <= _j) && (_j < j) =>
// (_i < _j) && (i < j) =>
// (i+_i < j+_j)
// (M < N)
}
else // j < _j
{
if (_i <= j) s = 2;
else if (i < j) s = 0;
else s = 1;

// (_i <= j) && (i < j) && (j < _j) =>
// (_i < _j) && (i < j) =>
// (i+_i < j+_j)
// (M < N)
}
}
else
{
// (M <= N) => (min(M, N)==M) => (i!=_i)
// (i==_i) => (2*i==M-1) => (min(M, N)==2*i+1)

if (i > _i)
{
if (_i >= _j) s = 3;
else if (_i > j) s = 1;
else s = 2;

// (_i >= _j) && (_i > j) && (i > _i) =>
// ( i > _j) && (_i > j) =>
// (i+_i > j+_j)
// (M > N)
}
else // i < _i
{
if (i > _j) s = 3;
else if (i >= j) s = 1;
else s = 0;

// (i > _j) && ( i >= j) && (_i > i) =>
// (i > _j) && (_i > j) =>
// (i+_i > j+_j)
// (M > N)
}
}

UINT r, Di, Dj, L, l;

switch (s)
{
case 0:
r = i;
l = j;
break;
case 1:
r = j;
l = _i;
break;
case 2:
r = _i;
l = _j;
break;
case 3:
r = _j;
l = i;
break;
// default: __assume(false);
}

l -= r, r <<= 1, Di = M - r - 1, Dj = N - r - 1;

L = R % ((Di + Dj) << 1);

UINT ii = i, jj = j;

switch (s)
{
for (;;)
{
case 0:
if (L <= l)
{
jj -= L;
goto __end;
}
jj -= l, L -= l, l = Di;
case 1:
if (L <= l)
{
ii += L;
goto __end;
}
ii += l, L -= l, l = Dj;
case 2:
if (L <= l)
{
jj += L;
goto __end;
}
jj += l, L -= l, l = Di;
case 3:
if (L <= l)
{
ii -= L;
goto __end;
}
ii -= l, L -= l, l = Dj;
}
// default: __assume(false);
}

__end:
u--, u->i = ii, u->j = jj;

} while (_j++, j);

} while (_i++, i);
}

это O(M*N) - у нас есть цикл по М и внутри его петли для Н. но для R у нас есть максимум 5 итераций. для каждой точки (Я,J) вычисляем его стороны (0,1,2,3) и кольцо. и сдвиг.

функции для визуализации перестановки:

void PrintPermutation(UINT M, UINT N, UINT R)
{
S* u = new S[M*N];

rotate(M, N, R, u);

UINT i = 0;

do
{
UINT j = 0;

do
{
printf("(%u,%u)->(%u, %u) ", i+1, j+1, 1+u->i, 1+u->j);
u++;
} while (++j<N);

printf("\n");

} while (++i<M);

delete [] (u - M*N);
}

сказать

PrintPermutation(4, 5, 1);

у нас

(1,1)->(2, 1) (1,2)->(1, 1) (1,3)->(1, 2) (1,4)->(1, 3) (1,5)->(1, 4) 
(2,1)->(3, 1) (2,2)->(3, 2) (2,3)->(2, 2) (2,4)->(2, 3) (2,5)->(1, 5)
(3,1)->(4, 1) (3,2)->(3, 3) (3,3)->(3, 4) (3,4)->(2, 4) (3,5)->(2, 5)
(4,1)->(4, 2) (4,2)->(4, 3) (4,3)->(4, 4) (4,4)->(4, 5) (4,5)->(3, 5)

что соответствует

enter image description here

с этой функцией уже легко реализовать матрицу поворота:

void RotateMatrix(UINT M, UINT N, UINT R, UINT mtx[])
{
UINT mn = M * N;

S* u = new S[mn];

UINT* _mtx = new UINT[mn];

std::memcpy(_mtx, mtx, mn * sizeof(UINT));

rotate(M, N, R, u);

UINT i = 0, j;

do
{
j = 0;

do
{
mtx[N * u->i + u->j] = *_mtx++;
u++;
} while (++j<N);

} while (++i<M);

delete [] (_mtx - mn);
delete [] (u - mn);
}

void PrintMatrix(UINT M, UINT N, const UINT mtx[])
{
UINT i = M, j;

do
{
j = N;
do
{
printf("%02u ", *mtx++);
} while (--j);

printf("\n");

} while (--i);
}

void RotateAndPrintMatrix(UINT M, UINT N, UINT R, UINT mtx[])
{
printf("\n===============\n");
PrintMatrix(M, N, mtx);
printf("---------------\n");
RotateMatrix(M, N, R, mtx);
PrintMatrix(M, N, mtx);
}

сначала мы выделяем и построить массив перестановок u
чем сделать копию матрицы _mtx
и, наконец, делать в цикле

    mtx[N * u->i + u->j] = *_mtx++;
u++;

тест № 1:

UINT mtx[] = {
1, 2, 3, 4,
5, 6, 7, 8,
9, 10, 11, 12,
13, 14, 15, 16
};
RotateAndPrintMatrix(4, 4, 2, mtx);

и результат:

01 02 03 04 
05 06 07 08
09 10 11 12
13 14 15 16
=============
03 04 08 12
02 11 10 16
01 07 06 15
05 09 13 14

тест № 2: (Пример входных данных #02)

UINT mtx[]= {
1, 2, 3, 4,
7, 8, 9, 10,
13, 14, 15, 16,
19, 20, 21, 22,
25, 26, 27, 28
};
RotateAndPrintMatrix(5, 4, 7, mtx);

и результат:

01 02 03 04 
07 08 09 10
13 14 15 16
19 20 21 22
25 26 27 28
=============
28 27 26 25
22 09 15 19
16 08 21 13
10 14 20 07
04 03 02 01

для RotateAndPrintMatrix(5, 4, 14*6, mtx); 14*6=((4+3)*2)*((2+1)*2) матрица, как и должен быть неизменным

01 02 03 04 
07 08 09 10
13 14 15 16
19 20 21 22
25 26 27 28
=============
01 02 03 04
07 08 09 10
13 14 15 16
19 20 21 22
25 26 27 28

1
ответ дан 27 января 2018 в 07:01 Источник Поделиться