In ma trận mxn thành hình xoắn ốc

ltd · September 11, 2016, 6:00pm

Đây là bài tập khá cơ bản, nhưng không ngờ lại có trên Leetcode, thôi thì sẵn giải luôn cho vui nhé mọi người

Cho vào cái ma trận thế này

[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]

In ra thế này

[1,2,3,6,9,8,7,4,5]

Độ khó: medium

Chú ý:

Đừng xem hướng dẫn trên Leetcode hay các hướng dẫn có sẵn khác.
Thử giải cách khác cách trên Leetcode hướng dẫn xem sao
Chấp nhận mọi ngôn ngữ
Cần giải thích thuật toán

thangngoc89 · September 11, 2016, 6:47pm

Để em thử sức với JS

"use strict";

function run(input, result) {
		result = result || []
    if (input.length == 0) {
        return result;
    }
    
    if (input.length === 1) {
    		result.push(input[0][0])
        return result
    }

    result = result.concat(input.shift());

    input.forEach(function(rightEnd) {
        result.push(rightEnd.pop());
    });

    result = result.concat(input.pop().reverse());

    var tmp = [];
    input.forEach(function(leftEnd) {    
        tmp.push(leftEnd.shift());
    });
    result = result.concat(tmp.reverse());

    return run(input, result);
}

console.log(
	'3x3', 
  run(
    [[ 1, 2, 3 ],
     [ 4, 5, 6 ],
     [ 7, 8, 9 ]]
  )
)

console.log(
	'4x4', 
  run(
    [[1,  2,   3,  4],
     [5,  6,   7,  8],
     [9,  10, 11, 12],
     [13, 14, 15, 16]]
  )
);

giải thích:

Cho hàng đầu tiên vào result theo thứ tự
Lấy phần tử cuối của mỗi hàng theo thứ tự cho vào result
Đảo ngược hàng cuối cùng rồi cho vào result
Lấy phần tử đầu của các hàng còn lại

Tới đây là đi được vòng ngoài của ma trận, đệ quy tiếp tục với ma trận (m-1)x(n-1)

Bonus cái jsfiddle để chạy code nếu lười (hoặc là mở console panel của trình duyệt ra)

https://jsfiddle.net/uun5qvwk/

Giải thích vài hàm xử lí mảng của JS nếu bạn không quen:

Array.prototype.push : thêm vào cuối của mảng
Array.prototype.concat : thêm vào cuối của mảng (tạo mảng mới, non-mutation)
Array.prototype.reverse : đảo ngược
Array.prototype.shift : bỏ phần tử đầu
Array.prototype.pop : bỏ phần tử cuối

Zzero · September 11, 2016, 8:27pm

Mình dùng 4 cạnh của hình vuông(HCN) để giới hạn mảng, sau mỗi vòng lặp thì bán kính HV(HCN) thu nhỏ lại 1 đ.vị, cứ thế in mãi đến khi đủ số lượng phần tử của mảng thì dừng.

Code này áp dụng cho cả ma trận m x n bình thường chứ ko nhất thiết phải ma trận vuông, code C++:

#include <iostream>
using namespace std;

void In(int arr[][3], int soDong, int soCot)
{
	int dong = soDong - 1, cot = soCot - 1;
	int i = 0, j = 0;
	int dem = 0;

	while (dem != soDong * soCot)
	{
		for (int k = j; k <= cot; k++)
			cout << arr[i][k] << '\t';
		i++;
		for (int k = i; k <= dong; k++)
			cout << arr[k][cot] << '\t';;
		cot--;
		for (int k = cot; k >= j; k--)
			cout << arr[dong][k] << '\t';;
		dong--;
		for (int k = dong; k >= i; k--)
			cout << arr[k][j] << '\t';;
		j++;

		dem++;
	}
}

Chạy thử:

  int main()
    {
    	int a[][3] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

    	In(a, 3, 3);

            int b[][3] = { 3,4,7,6,8,3,4,9,0, 6, 7, 8};

     	In(b, 4, 3);

    	system("pause");
    	return 0;
    }

ngoisaochip · September 12, 2016, 1:31am

Code của em

   int iarr[3][3];
    	int iValue = 1;
    	int iTenGiDo = 0;
    	int iColumn = 3;
    	int iRow = 3;

    	while ( iTenGiDo <= 3 / 2 )
    	{
    		for (int x = iTenGiDo; x < iColumn; x++)
    			iarr[iTenGiDo][x] = iValue ++;

    		for (int y = iTenGiDo + 1; y < iRow - 1; y++)
    			iarr[y][iColumn - 1] = iValue ++;

    		for (int x = iColumn - 1; x > iTenGiDo; x--)
    			iarr[iRow - 1][x] = iValue ++;

    		for (int y = iRow - 1; y > iTenGiDo; y--)
    			iarr[y][iTenGiDo] = iValue ++;

    		iTenGiDo ++;
    		iColumn --;
    		iRow --;
    	}

    	for (int y = 0; y < 3; y++)
    	{
    		for (int x = 0; x < 3; x++)
    		{
    			printf("%-3d", iarr[y][x]);
    		}

    		printf("\n");
    	}

Ý tưởng

tcm · September 16, 2016, 7:10am

Đây hình như là bài con của bài này đúng không anh @ltd ?