Spiral Matrix II
Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
For example,
Given n = 3
,
You should return the following matrix:
[ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]
class Solution { public: vector<vector<int> > generateMatrix(int n) { if (n == 0) return vector<vector<int> >(); static const int dy[] = {0,1,0,-1}; // right, down, left, up static const int dx[] = {1,0,-1,0}; vector<vector<int> > res; res.resize(n); for (int i = 0; i < n; ++i) res[i].resize(n,0); int cur = 1; for (int i = 0; i < n; ++i) res[0][i] = cur++; for (int i = 1; i < n; ++i) res[i][n-1] = cur++; for (int i = n-2; i >= 0; --i) res[n-1][i] = cur++; int y = n-1, x = 0, dir = 3; int t = n*n; while (cur <= t) { if (res[y+dy[dir%4]][x+dx[dir%4]] != 0) { dir++; continue; } y += dy[dir%4]; x += dx[dir%4]; res[y][x] = cur++; } return res; } };
@2013-10-03
class Solution { public: vector<vector<int> > generateMatrix(int n) { vector<vector<int> > res(n); for (int i = 0; i < n; i++) res[i].resize(n); gen(1, 0, n - 1, 0, n - 1, res); return res; } void gen(int start, int left, int right, int top, int bot, vector<vector<int> >& a) { if (left > right || top > bot) return; if (left == right) { a[left][top] = start ++; return; } else { for (int i = left; i <= right; i++) a[top][i] = start++; for (int i = top + 1; i < bot; i++) a[i][right] = start++; for (int i = right; i >= left; i--) a[bot][i] = start++; for (int i = bot - 1; i > top; i--) a[i][left] = start++; gen(start, left + 1, right - 1, top + 1, bot - 1, a); } } };
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
You should return [1,2,3,6,9,8,7,4,5]
.
class Solution { public: vector<int> spiralOrder(vector<vector<int> > &matrix) { vector<int> res; int n = matrix.size(); if (n == 0) return res; int m = matrix[0].size(); gen(res, 0, 0, n-1, m-1, matrix); return res; } void gen(vector<int>& res, int left, int top, int bottom, int right, vector<vector<int> >& a) { if (left > right || top > bottom) return; if (left == right) { for (int i = top; i <= bottom; i++) res.push_back(a[i][left]); return; } else if (top == bottom) { for (int i = left; i <= right; i++) res.push_back(a[top][i]); return; } else { for (int i = left; i <= right; i++ ) res.push_back(a[top][i]); for (int i = top + 1; i < bottom; i++) res.push_back(a[i][right]); for (int i = right; i >= left; i--) res.push_back(a[bottom][i]); for (int i = bottom - 1; i > top; i--) res.push_back(a[i][left]); gen(res, left + 1, top + 1, bottom - 1, right - 1, a); } } };
相关推荐
15 | [3 Sum](https://leetcode.com/problems/3sum/) | [C++](./C++/3sum.cpp) [Python](./Python/3sum.py) | _O(n^2)_ | _O(1)_ | Medium || Two Pointers 16 | [3 Sum Closest]...
leetcode category other hot keywords:Palindrome(mic), Subsequence Array 螺旋矩阵Spiral Matrix 顺时针打印矩阵 Next Permutation Product of Array Except Self 189.rotate-array 283.move-zero Range Sum ...
Spiral Matrix com.leetcode.list Linked List Cycle Linked List Cycle II Remove Duplicates from Sorted List com.leetcode.string Single Number com.leetcode.tree Balanced Binary Tree Maximum Depth of ...
leetcode 答案螺旋矩阵 返回二维数组中整数元素的顺时针螺旋列表 [答案击败 100% Java LeetCode 运行时提交] [答案击败 100% Java LeetCode 内存使用提交] 大(O)= O(N)
1 两和容易2 加两个数中5 最长回文子串中6 ZigZag 转换介质7 反转整数简单8 字符串到整数 (atoi) 中9 回文数容易11 盛水介质最多的容器12 整数到罗马中号13 罗马到整数简单14 最长公共前缀 简单15 3Sum 中18 4Sum 中...
多线程 leetcode 前言 ...Spiral Matrix Path Sum II Copy List with Random Pointer Building H2O Fizz Buzz Multithreaded hard Merge k Sorted Lists Reverse Nodes in k-Group Trapping Rain Water
Spiral Matrix medium O 66 Plus One easy O O 118 Pascal's Triangle easy O O 119 Pascal's Triangle II easy O 要满足只用一个array大小空间O(k) k为input大小来完成,须具备backtracking概念 151 Reverse Words ...
leetcode LeetCode Solutions 算法 - Algorithms 排序算法:快速排序、归并排序、计数排序 搜索算法:回溯、递归、剪枝技巧 图论:最短路、最小生成树、网络流建模 动态规划:背包问题、最长子序列、计数问题 基础...
leetcode 530 力码 全部的: 易(173/237+x) 中(144/437+x) 硬(4/x) 问题 1.Two Sum(dict) 7.(跳过)(数学) 9.(跳过)(串串技巧) 11.盛水最多的容器 12.(跳过)(问题不好) 13.(跳过)(蛮力) 14.(跳过)...
1.position 2.sequence Sell Stock 区间型 矩阵坐标 Word Ladder Add Two Numbers Matrix Spiral Matrix Mergesort [Algorithm Swap](Mergesort/Algorithm swap.md) Numbers Queue Stack Toposort Trie Tree Two ...
这是我准备面试时建议的个人问题清单。...https://leetcode.com/problems/spiral-matrix/ https://leetcode.com/problems/search-a-2d-matrix/ https://leetcode.com/problems/set-matrix-zeroes/ 弦乐 ...
1、leetcode解析 2、代码实现 class Solution: def spiralOrder(self, matrix: List[List[int]]) -> List[int]: if not matrix:return [] m,n = len(matrix),len(matrix[0]) x = y = di = 0 dx = [0,1,0,-1] ...
对于每一道算法题会总结代码、时间复杂度以及一些好的blog排序(sort)...Spiral Matrix IILeetCode 53 Maximum SubarrayLeetCode 152 Maximum Product SubarrayLintCode 138 Subarray SumLintCode 139 Subarray Sum ...
Spiral Matrix II ZigZag Conversion Divide Two Integers Text Justification Max Points on a Line Community QQ 群: 237669375 Github: https://www.github.com/soulmachine/algorithm-essentials 微博: @...