8000 half finish Spiral Matrix - leetcode - medium · jacobklo/jalgorithmCPP@3dc4e6e · GitHub
[go: up one dir, main page]
Skip to content

Commit 3dc4e6e

Browse files
jacobklojacobklo
committed
half finish Spiral Matrix - leetcode - medium
1 parent c5458f2 commit 3dc4e6e

File tree

4 files changed

+247
-1
lines changed

4 files changed

+247
-1
lines changed

‎.idea/codeStyles/Project.xml

Lines changed: 29 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -53,6 +53,7 @@ unlike normal projects.
5353
* [Diagonal Traverse - Leetcode - Medium](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/Implementation/Array/DiagonalTraverse.h)
5454
* [Larry's Array - Hackerrank](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/Implementation/Array/LarrysArray.h)
5555
* [MinSwap](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/Implementation/Array/MinSwap.h)
56+
* [Spiral Matrix - Leetcode - MEDIUM](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/Implementation/Array/SpiralMatrix.h)
5657
***
5758

5859

‎src/CMakeLists.txt

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -61,5 +61,7 @@ add_executable(jalgorithmCPP
6161
Algorithm/DynamicProgramming/Knapsack.h
6262
Implementation/Array/DiagonalTraverse.h
6363
Algorithm/Greedy/JumpGame.h
64-
Implementation/Trie/ImplementTrie.h)
64+
Implementation/Trie/ImplementTrie.h
65+
Implementation/Array/SpiralMatrix.h
66+
)
6567

‎src/Implementation/Array/SpiralMatrix.h

Lines changed: 214 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,214 @@
1+
//
2+
// Created by Jacob Lo on Feb 13, 2019
3+
//
4+
5+
// MEDIUM
6+
// https://leetcode.com/problems/spiral-matrix/
7+
8+
/*
9+
* Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
10+
11+
Example 1:
12+
13+
Input:
14+
[
15+
[ 1, 2, 3 ],
16+
[ 4, 5, 6 ],
17+
[ 7, 8, 9 ]
18+
]
19+
Output: [1,2,3,6,9,8,7,4,5]
20+
21+
Input:
22+
[
23+
[1, 2, 3, 4],
24+
[5, 6, 7, 8],
25+
[9,10,11,12]
26+
]
27+
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
28+
*/
29+
#pragma once
30+
31+
#include <deque>
32+
#include <vector>
33+
#include <iostream>
34+
35+
using namespace std;
36+
37+
// TODO: works locally but not on Leetcode
38+
// TODO: optimize
39+
namespace SpiralMatrix {
40+
void calcRows(vector<vector<int>> &matrix, deque<deque<int>> &result) {
41+
42+
for (int i = 0, j = 0, k = matrix.size() - 1; i < matrix.size(); i++) {
43+
44+
if (i % 2 == 0) {
45+
result.push_back(deque<int>(matrix[j].begin(), matrix[j].end()));
46+
j++;
47+
48+
} else {
49+
result.push_back(deque<int>(matrix[k].begin(), matrix[k].end()));
50+
k--;
51+
}
52+
}
53+
}
54+
55+
void calcColumn(vector<vector<int> > &matrix, deque<deque<int>> &result) {
56+
57+
for (int i = 0, x = matrix[0].size() - 1, y = 0; i < matrix[0].size(); i++) {
58+
59+
if (i % 2 == 0) {
60+
deque<int> tmpCol;
61+
for (int r = 0; r < matrix.size(); r++) {
62+
tmpCol.push_back(matrix[r][x]);
63+
}
64+
result.push_back(tmpCol);
65+
x--;
66+
} else {
67+
deque<int> tmpCol;
68+
for (int r = 0; r < matrix.size(); r++) {
69+
tmpCol.push_back(matrix[r][y]);
70+
}
71+
result.push_back(tmpCol);
72+
y++;
73+
}
74+
}
75+
}
76+
77+
void calcRemoveRow(deque<deque<int>> &result) {
78+
79+
int i = 0;
80+
for (int m = 0, n = 0; i < result.size(); i++) {
81+
82+
if (m >= (result[0].size() - n)) {
83+
break;
84+
}
85+
if (m > 0) {
86+
result[i].erase(result[i].begin(), result[i].begin() + m);
87+
}
88+
if (n > 0) {
89+
result[i].erase(result[i].begin() + (result[i].size() - n), result[i].end());
90+
}
91+
92+
if (i % 2 == 1) {
93+
m++;
94+
} else if (i % 2 == 0) {
95+
n++;
96+
}
97+
}
98+
99+
result.erase(result.begin() + i, result.end());
100+
}
101+
102+
void calcRemoveCol(deque<deque<int>> &result) {
103+
104+
int i = 0;
105+
for (int m = 1, n = 0; i < result.size(); i++) {
106+
107+
if (m > (result[0].size() - n)) {
108+
break;
109+
}
110+
if (m > 0) {
111+
result[i].erase(result[i].begin(), result[i].begin() + m);
112+
}
113+
if (n > 0) {
114+
result[i].erase(result[i].begin() + (result[i].size() - n), result[i].end());
115+
}
116+
117+
if (i % 2 == 1) {
118+
m++;
119+
} else if (i % 2 == 0) {
120+
n++;
121+
}
122+
}
123+
124+
result.erase(result.begin() + i, result.end());
125+
}
126+
127+
void calcFlip(deque<deque<int>> &result) {
128+
129+
for (int i = 0; i < result.size(); i++) {
130+
if (i % 2 == 1) {
131+
deque<int> tmp = result[i];
132+
result[i] = deque<int>(tmp.rbegin(), tmp.rend());
133+
}
134+
}
135+
}
136+
137+
138+
vector<int> spiralOrder(vector<vector<int>> &matrix) {
139+
if (matrix.empty()) return vector<int>();
140+
141+
deque<deque<int> > rrrows, cccol;
142+
calcRows(matrix, rrrows);
143+
calcRemoveRow(rrrows);
144+
calcFlip(rrrows);
145+
calcColumn(matrix, cccol);
146+
calcRemoveCol(cccol);
147+
calcFlip(cccol);
148+
149+
vector<int> result;
150+
151+
int i = 0, j = 0, k = 0;
152+
for (; i < j < rrrows.size() && k < cccol.size(); i++) {
153+
154+
if (i % 2 == 0) {
155+
for (int x = 0; x < rrrows[j].size(); x++) {
156+
result.push_back(rrrows[j][x]);
157+
}
158+
j++;
159+
} else {
160+
for (int x = 0; x < cccol[k].size(); x++) {
161+
result.push_back(cccol[k][x]);
162+
}
163+
k++;
164+
}
165+
}
166+
167+
if (j < rrrows.size()) {
168+
for (int x = 0; x < rrrows[j].size(); x++) {
169+
result.push_back(rrrows[j][x]);
170+
}
171+
}
172+
if (k < cccol.size()) {
173+
for (int x = 0; x < cccol[k].size(); x++) {
174+
result.push_back(cccol[k][x]);
175+
}
176+
}
177+
return result;
178+
}
179+
180+
void test() {
181+
vector<vector<vector<int> > > ms
182+
{
183+
{
184+
{1, 2, 3, 4},
185+
{5, 6, 7, 8},
186+
{9, 10, 11, 12},
187+
{13, 14, 15, 16},
188+
{17, 18, 19, 20},
189+
{21, 22, 23, 24}
190+
},
191+
{
192+
{1, 2, 3, 4, 100},
193+
{5, 6, 7, 8, 200},
194+
{9, 10, 11, 12, 300},
195+
{13, 14, 15, 16, 400},
196+
{17, 18, 19, 20, 500},
197+
{21, 22, 23, 24, 600}
198+
},
199+
{
200+
{1}, {2}, {3}, {4}, {5}, {6}
201+
},
202+
{
203+
{1}, {2}, {3}, {4}, {5}, {6}, {7}
204+
},
205+
{}
206+
};
207+
208+
for (auto m : ms) {
209+
// cout << spiralOrder(m) << endl << endl;
210+
211+
212+
}
213+
}
214+
}

0 commit comments

Comments
 (0)
0