59. 螺旋矩阵 II

题目描述 给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。 示例: 输入: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] https://leetcode-cn.com/problems/spiral-matrix-ii/ 解法1 本题目与“54. 螺旋矩阵”相似,但本题目给出矩阵的维度,要求生成螺旋矩阵。因为题目给出的是方阵,那么我们不需要考虑54题中内部出现孤立的一行或一列的情况。但会出现孤立一个元素的情况。 我们按照顺时针的顺序一次从左到右、从上到下遍历round圈即可。通过举例子的方式,我们可以算出round=ceil(n/2)。下面我们来说如何处理孤立元素的情况。例如上述3×3的方阵,当遍历完外面一圈的数字后将会只留下一个数字。那么如何判定循环遇到这种情况了呢?以3×3的矩阵为例,当round=1时中心只剩下一个元素,而矩阵遍历完一圈会消耗掉左右两个数字。因此,我们可以推测当n-2*round=1时,矩阵遍历到中心元素。这是一个corner case,我们需要独立处理这种情况,全部代码如下所示。

Read more

54. 螺旋矩阵

题目描述 给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。 示例 1: 输入: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] 输出: [1,2,3,6,9,8,7,4,5] 示例 2: 输入: [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ] 输出: [1,2,3,4,8,12,11,10,9,5,6,7] https://leetcode-cn.com/problems/spiral-matrix/ 解法1 我们首先举3个例子来分析如何实现矩阵的螺旋顺序遍历. 我们分别以3×3, 3×4与4×3的矩阵为例. 我们将遍历步骤分为水平从左到右遍历、垂直从上向下遍历、水平从右向左遍历与垂直从下向上遍历。如果遇到内部只包含一行或一列的情况,那么就全部遍历该行或列。 上面只是大概思路。当时现实时,我们会遇到另一个问题:“按照环形遍历几圈结束”?如果我们多举几个例子,可以容易地推测“圈数=ceil(max(row, col)/2)”. 另一个问题:“每一圈的起点是如何计算的?”我们可以从图上看出,每次我轮都从(0,0)、(1,1)、(2,2)……为起点遍历的。因此,我们取(round,round)作为遍历的起点。我们记当前的行号列号为(row,col),如果水平向右就遍历matrix[row][col++],如果垂直向下就遍历matrix[row++][col]以此类推。经过上面的分析,我们就能编写出矩阵按照螺旋遍历的代码了。

Read more

9. 回文数

题目描述 判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。 示例 1: 输入: 121 输出: true 示例 2: 输入: -121 输出: false 解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 示例 3: 输入: 10 输出: false 解释: 从右向左读, 为 01 。因此它不是一个回文数。进阶:你能不将整数转为字符串来解决这个问题吗? https://leetcode-cn.com/problems/palindrome-number/ 解法 我们按照进阶的要求,不将整数转化为字符串。代码模板中,变量x是int类型的。那么,将其反转结果使用long类型存放是不会溢出的。题目提到了一个case为“-121”,逆序读“121-”不是回文串。那么我们就可以推测,负数一定不是回文数。 我们按照“7.整数反转”这道题的技巧,判断反转后的数字与原数字是否一致来判定是否为回文数字即可。

Read more

7. 整数反转

题目描述 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。 示例 1: 输入: 123 输出: 321  示例 2: 输入: -123 输出: -321 示例 3: 输入: 120 输出: 21 注意: 假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231,  231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。 https://leetcode-cn.com/problems/reverse-integer/ 解法 首先说明一点,如果直接转成StringBuffer,然后reverse以下再转成int就没意思了。我们尽可能不要使用这种straightforward的方法去做,才能够学到东西。 变量x存放了要被反转的数字,假设x=123.我们让x对10取余就能获得末尾数字,然后再另x=x/10,直到x为0. 例如:123%10==3,123->12; 12%10==2, 12->1; 1%10==1, 1->0循环结束。让我们对取过来对数字3、2、1记为n,分别带入公式result = result*10 + n,其中result初值为0。列如:分别带入3、2、1,0*10+3==3;3*10+2==32;32*10+1==321。 这样,我们通过一次循环就能逆序取出x的各位数字,然后带入result = result*10 + n就能得到逆序后的数字。还有一点是,题目要求发生溢出返回0。为了能够判定溢出,我们就要用比int范围更广的类型来存储逆序后的结果。每次循环,都要判定result变量是否小于Integer.MIN_VALUE或大于Integer.MAX_VALUE。

Read more

6. Z 字形变换

将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时,排列如下: L C I R E T O E S I I G E D H N 之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:”LCIRETOESIIGEDHN”。 请你实现这个将字符串进行指定行数变换的函数: string convert(string s, int numRows); 示例 1: 输入: s = “LEETCODEISHIRING”, numRows = 3 输出: “LCIRETOESIIGEDHN” 示例 2: 输入: s = “LEETCODEISHIRING”, numRows = 4 输出: “LDREOEIIECIHNTSG” 解释: L D R E O E I I…

Read more