Как зациклить двумерный массив против часовой стрелки? - PullRequest
Новая
       2

Как зациклить двумерный массив против часовой стрелки?

0 голосов
/ 11 октября 2018

Учитывая двумерный массив измерения mxn, как я могу проходить через них против часовой стрелки?

Например: 

matrix = [
  [   1,    2,   3,    4  ],
  [   5,    6,   7,    8  ],
  [   9,   10,  11,   12  ],
  [  13,   14,  15,   16  ]
]

1st loop: 1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2
2nd loop: 6, 10, 11, 7, 6

Я действительно не против, если реализацияуказывается в ruby ​​или js

Мое текущее решение выглядит следующим образом: 

  (1..rotate).each do
    bottom_left_corner = i
    top_right_corner   = j
    start_nth_layer = 1; end_nth_layer = matrix.length - 2
    matrix.reverse_each do
      matrix[bottom_left_corner].unshift(matrix[bottom_left_corner - 1].shift) if bottom_left_corner > 0
      matrix[top_right_corner] << matrix[top_right_corner + 1].pop if top_right_corner < matrix.length - 1

      bottom_left_corner -= 1; top_right_corner += 1
    end

    nth_layer(matrix, start_nth_layer, end_nth_layer)

  end

Обновление

Формат вывода не имеет значения, если онвыводит правильный порядок.

Цель задачи

Цель этой задачи - обходить эти массивы против часовой стрелки, слой за слоем, пока не останется больше слоев.Для каждого обхода мы сдвигаем значения против часовой стрелки.Например: 

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

Ответы [ 6 ]

0 голосов
/ 12 октября 2018

Ниже приведена модификация моего ответа на этот вопрос SO , который отличается от этого только тем, что массив пересекается в противоположном направлении. 

arr = matrix.map(&:dup).transpose
out = []
loop do
  out = out + arr.shift
  break out if arr.empty?
  arr = arr.transpose.reverse
end
  #=> [1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2, 6, 10, 11, 7]

Шагиследующие: 

arr = matrix.map(&:dup).transpose
  #=> [[1, 5, 9, 13], [2, 6, 10, 14], [3, 7, 11, 15], [4, 8, 12, 16]]

Я дублировал элементы matrix, чтобы последние не были видоизменены. 

out = []

out = out + arr.shift
  #=> [1, 5, 9, 13]
arr
  #=> [[2, 6, 10, 14], [3, 7, 11, 15], [4, 8, 12, 16]]    

arr = arr.transpose.reverse
  #=> [[14, 15, 16], [10, 11, 12], [6, 7, 8], [2, 3, 4]]
out = out + arr.shift
  #=> [1, 5, 9, 13, 14, 15, 16]
arr
  #=> [[10, 11, 12], [6, 7, 8], [2, 3, 4]]

arr = arr.transpose.reverse
  #=> [[12, 8, 4], [11, 7, 3], [10, 6, 2]]
out = out + arr.shift
  #=> [1, 5, 9, 13, 14, 15, 16, 12, 8, 4]
arr
  #=> [[11, 7, 3], [10, 6, 2]]

arr = arr.transpose.reverse
  #=> [[3, 2], [7, 6], [11, 10]]
out = out + arr.shift
  #=> [1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2]
arr
  #=> [[7, 6], [11, 10]]


arr = arr.transpose.reverse
  #=> [[6, 10], [7, 11]]
out = out + arr.shift
  #=> [1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2, 6, 10]
arr
  #=> [[7, 11]]

arr = arr.transpose.reverse
  #=> [[11], [7]]
out = out + arr.shift
  #=> [1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2, 6, 10, 11]
arr
  #=> [[7]]

arr = arr.transpose.reverse
  #=> [[7]]
out = out + arr.shift
  #=> [1, 5, 9, 13, 14, 15, 16, 12, 8, 4, 3, 2, 6, 10, 11, 7]
arr
  #=> []

Поскольку arr теперь пусто, мы break и возвращаем out. 

arr
arr = arr.transpose.reverse

out = out + arr.shift
arr
arr = arr.transpose.reverse

out = out + arr.shift
arr
arr = arr.transpose.reverse

out = out + arr.shift
arr
arr = arr.transpose.reverse

out = out + arr.shift
arr
arr = arr.transpose.reverse

out = out + arr.shift
arr
arr = arr.transpose.reverse
0 голосов
/ 11 октября 2018

Вот как я это сделал в ruby: 

def counter_clockwise!(arr)
  return arr if arr.size <= 1
  rotation = [
    arr.map(&:shift)
      .concat(arr.pop,
              arr.map(&:pop).reverse,
              arr.shift.reverse).compact
  ]
  rotation.push(*send(__method__,arr)) unless arr.all?(&:empty?)
  rotation 
end

def counter_clockwise(arr)
  counter_clockwise!(arr.map(&:dup))
end

Пример: 

arr = [
  [   1,    2,   3,    4  ],
  [   5,    6,   7,    8  ],
  [   9,   10,  11,   12  ],
  [  13,   14,  15,   16  ],
  [  17,   18,  19,   20  ],
  [  21,   22,  23,   24  ]
]
counter_clockwise(arr)
#=> [[1, 5, 9, 13, 17, 21, 22, 23, 24, 20, 16, 12, 8, 4, 2, 3], 
#    [6, 10, 14, 18, 19, 15, 11, 7]]

Этот метод рекурсивно обрабатывает внешние края в группы ("Циклы" в исходном сообщении).Очевидно, что если вам нужна спираль против часовой стрелки без групп, вы можете сгладить возвращаемое значение.

Это также будет обрабатывать не M x N Матрицы, такие как: 

arr = [
  [   1,    2,   3,    4  , 72 ],
  [   5,    6,   7,    8  , 73 ],
  [   9,   10,        11  , 12 ],
  [  13,   14,        16  , 75 ],
  [  17,   18,  19,   20  , 76 ],
  [  21,   22,  23,   24  , 77 ]
]

counter_clockwise(arr) 
#=> [[1, 5, 9, 13, 17, 21, 22, 23, 24, 77, 76, 75, 12, 73, 72, 4, 3, 2],       
#   [6, 10, 14, 18, 19, 20, 16, 11, 8, 7]]

Если вы хотите каждыйкрай и может гарантировать M x N, тогда это тоже будет работать 

def counter_clockwise_edges(arr)
  return arr if arr.size == 1
  arr = arr.transpose
  [arr.shift].push(*send(__method__,arr.map(&:reverse))) 
end
counter_clockwise_edges(arr)
#=> [[1, 5, 9, 13, 17, 21], 
     [22, 23, 24], 
     [20, 16, 12, 8, 4], 
     [3, 2], 
     [6, 10, 14, 18], 
     [19, 15, 11, 7]]
0 голосов
/ 11 октября 2018

Учитывая массив: 

array = 
  [
    [ '00', '01', '02', '03', '04', '05'],
    [ '10', '11', '12', '13', '14', '15'],
    [ '20', '21', '22', '23', '24', '25'],
    [ '30', '31', '32', '33', '34', '35']
  ]

Возвращает внешний цикл: 

external_ccw_round = [array.map(&:shift), array.pop, array.map(&:pop).reverse, array.shift.reverse].flatten
#=> ["00", "10", "20", "30", "31", "32", "33", "34", "35", "25", "15", "05", "04", "03", "02", "01"]

Оставляя только ядро ​​

array #=> [["11", "12", "13", "14"], ["21", "22", "23", "24"]]

Для матрицы с более чем однимстрока.

Это метод с рекурсивной реализацией

Работает на любой матрице 2D. 

def ccw_scan(array, result=[])
  return array if array.size <= 1
  result << [array.map(&:shift), array.pop, array.map(&:pop).reverse, array.shift.reverse]
  if array.size >= 2
    then ccw_scan(array, result)
  else result << array
  end
  result.flatten.compact
end

Вызовите метод для массива:

ccw_scan(array)
#=> ["00", "10", "20", "30", "31", "32", "33", "34", "35", "25", "15", "05", "04", "03", "02", "01", "11", "21", "22", "23", "24", "14", "13", "12"]
0 голосов
/ 11 октября 2018

Я бы написал это многоуровнево, написав логику транспонирования матрицы (то есть переворачивая матрицу по диагонали северо-запад-юго-восток), используя это и простой reverse для построения вращения матрицы против часовой стрелки,используя это вращение, чтобы построить спираль по часовой стрелке, и, наконец, снова использовать transpose вдоль спирали по часовой стрелке, чтобы построить спираль против часовой стрелки.

Я выбрал этот порядок, потому что спираль по часовой стрелке чаще запрашивается, но это будетбыть достаточно легким, чтобы построить спираль против часовой стрелки напрямую. Подсказка : rotateClockwise = m => transpose(reverse(m)). 

const reverse = a => [...a].reverse();
const transpose = m => m[0].map((c, i) => m.map(r => r[i]))
const rotateCounter = m => reverse(transpose(m))
const spiralClockwise = m => m.length < 2
  ? m[0]
  : m[0].concat(spiralClockwise(rotateCounter(m.slice(1))))
const spiralCounter = m => spiralClockwise(transpose(m))

console.log(spiralCounter([
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12]
]))

Обратите внимание, что промежуточные функции здесь вполне могут быть полезны сами по себе.Поэтому мне кажется, что это хороший способ решить проблему.

0 голосов
/ 11 октября 2018

Этот подход должен поддерживать любые размеры matrix и matrix[n].Попробуйте это с различными тестовыми примерами, если это работает для вас.

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

var arr = [
  [   1,    2,   3,    4  ],
  [   5,    6,   7,    8  ],
  [   9,   10,  11,   12  ],
  [  13,   14,  15,   16  ]
],
result = [];

while ( arr.flat().length ) {
  var res = [];

  // 1. Left side
  arr.forEach(x => res = res.concat( x.splice(0, 1) ));

  // 2. Bottom side
  if (arr.length) {
    res = res.concat( ...arr.splice(arr.length - 1, 1) );
  }

  // 3. Right side
  var tmp = [];
  if (arr.flat().length) {
    arr.forEach(x => tmp.push( x.splice(arr.length - 1, 1) ));
    res = res.concat( ...tmp.reverse() );
  }

  // 4. Top side
  if (arr.length) {
    tmp = [].concat( ...arr.splice(0, 1) );
    res = res.concat( tmp.reverse() );
  }

  result.push(res);
}

console.log(result);
0 голосов
/ 11 октября 2018

Это проблема вращения матричного слоя.Вот мое полное решение: 

function matrixRotation(matrix, rotate) {
    var r = matrix.length, c = matrix[0].length;
    var depth = Math.min(r,c)/2;
    for(var i=0;i<depth;i++) {
        var x = i, y = i, n = (r-i*2 - 2)*2 + (c-i*2-2)*2+4, dir = 'down', index=0;
        var buf = [];
        while(index < n) {
            buf.push(matrix[x][y]);
            if(dir == 'down') {
                if(x+1 >= r-i) {
                    dir = 'right';
                    y++;
                } else {
                    x++;
                }
            } else if(dir == 'right') {
                if(y+1 >= c-i) {
                    dir = 'up';
                    x--;
                } else {
                    y++;
                }
            } else if(dir == 'up') {
                if(x-1 <= i-1) {
                    dir = 'left';
                    y--;
                } else {
                    x--;
                }
            } else if(dir == 'left') {
                y--;
            }
            index++;
        }
        var move = rotate%n;
        buf = [...buf.slice(buf.length-move), ...buf.slice(0, buf.length-move)]
        x = i, y = i, dir = 'down', index = 0;
        while(index < n) {
            matrix[x][y] = buf[index];
            if(dir == 'down') {
                if(x+1 >= r-i) {
                    dir = 'right';
                    y++;
                } else {
                    x++;
                }
            } else if(dir == 'right') {
                if(y+1 >= c-i) {
                    dir = 'up';
                    x--;
                } else {
                    y++;
                }
            } else if(dir == 'up') {
                if(x-1 <= i-1) {
                    dir = 'left';
                    y--;
                } else {
                    x--;
                }
            } else if(dir == 'left') {
                y--;
            }
            index++;
        }
    }
    matrix.map(row => console.log(row.join(' ')));
}

const matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
// rotate count
const r = 3

matrixRotation(matrix, r);
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...