【算法】LeetCode刷题记录 Part.01


在这里记录下我的LeetCode刷题记录

1.两数之和

给定一个整数数列,找出其中和为特定值的那两个数。
你可以假设每个输入都只会有一种答案,同样的元素不能被重用。

示例

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路

每个数都在其后面寻找一遍有没有合适的,有则确定答案。

代码


7.颠倒整数

给定一个范围为 32 位 int 的整数,将其颠倒。

示例

例 1:

例 2:

例 3:

注意:
假设我们的环境只能处理 32 位 int 范围内的整数。根据这个假设,如果颠倒后的结果超过这个范围,则返回 0。

解题思路

本体难点在于超过32位int的范围时,返回0

解决方法 如果当前的tmp/10与tmp不等,则说明已经超过int范围,于是直接返回0 (超过取值范围从负从新开始)

代码


292.Nim游戏

您和您的朋友,两个人一起玩 Nim游戏:桌子上有一堆石头,每次你们轮流拿掉 1 到 3 块石头。 拿掉最后一块石头的人就是胜利者。由您来开局。

你们两个都是聪明人,相信都有最佳的游戏策略。 请编写一个函数,来判断您是否可以在给定的石头数量的情况下赢得游戏。

比方说,如果堆中有4块石头,那么你永远不会赢得比赛:无论你拿走的是 1块,2块 还是 3块 石头,最后一块石头总是会被你的朋友拿走。

解题思路

本题看上去难,实际上是数学问题,观察可以发现,由于双方都很聪明,若1 2 3三种情况,则我必赢, 4 的情况下,不管怎样拿,都是输,5 6 7 三种情况,必赢。8 时则我必输...

通过这样可以发现,只有为4的倍数时我会输,其他情况必赢

所以只用判断n是否是4的倍数

代码


344.反转字符串

请编写一个函数,其功能是将输入的字符串反转过来。

示例

解题思路

只用把得到的字符串从后往前,每次在StringBuffer后接上当前字符就好

不过有个比较坑的地方是,如果不用StringBuffer或StringBuilder,直接用String+=这种形式的话,会超时

因为StringBuffer耗时最少,所以选择StringBuffer

代码


461.汉明距离

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y,计算它们之间的汉明距离。

示例

解题思路

每次把一个数%2,即可得到它的当前二进制的最低位,每次比较两个数的最低位,然后两个数/2到下一位,即可得出结果

代码


728.自除数

自除数 是指可以被它包含的每一位数除尽的数。

例如,128 是一个自除数,因为 128 % 1 == 0,128 % 2 == 0,128 % 8 == 0。

还有,自除数不允许包含 0 。

给定上边界和下边界数字,输出一个列表,列表的元素是边界(含边界)内所有的自除数。

示例

解题思路

用了一个比较蠢的办法,就不解释了

代码


557.反转字符串中的单词 III

给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。

示例

解题思路

把字符串按空格分成几个字符串,然后挨个倒序,最后把每个后面加空格加到最后一个中

一个比较坑的地方,输出样例最后一个字母后是没有空格的,所以代码中手动删去了这个空格。

代码


561.数组拆分 I

给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ,使得从1 到 n 的 min(ai, bi) 总和最大。

示例

解题思路

看起来比较复杂,观察规律后可发现只用把这些数排序一次后把奇数个的数加起来就好
如 1 2 3 4 的结果是 1+3=4

代码


657.判断路线成圈

初始位置 (0, 0) 处有一个机器人。给出它的一系列动作,判断这个机器人的移动路线是否形成一个圆圈,换言之就是判断它是否会移回到原来的位置。

移动顺序由一个字符串表示。每一个动作都是由一个字符来表示的。机器人有效的动作有 R(右),L(左),U(上)和 D(下)。输出应为 true 或 false,表示机器人移动路线是否成圈。

示例

解题思路

用x y两个变量来记录当前坐标
每次向北则是y+1 向南则是y-1 向东是x+1 向西是x-1
这样,遍历字符串,最后得到了它最后的位置,如果是0,0 说明成了圈

代码


771.宝石与石头

给定字符串J 代表石头中宝石的类型,和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。

J 中的字母不重复,J 和 S中的所有字符都是字母。字母区分大小写,因此"a"和"A"是不同类型的石头。

示例

解题思路

两层循环,外层遍历前面的字符串,每次获取到宝石的字符都在后面的字符串寻找,找到则结果加一

代码


500.键盘行

给定一个单词列表,只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。
Keyboard

示例

解题思路

遍历字符串,每次个字符串先找到第一个字母所在行,若后面的字母都在该行,则结果List中加入该行

代码


806.写字符串需要的行数

我们要把给定的字符串 S 从左到右写到每一行上,每一行的最大宽度为100个单位,如果我们在写某个字母的时候会使这行超过了100 个单位,那么我们应该把这个字母写到下一行。我们给定了一个数组 widths ,这个数组 widths[0] 代表 'a' 需要的单位, widths[1] 代表 'b' 需要的单位,..., widths[25] 代表 'z' 需要的单位。

现在回答两个问题:至少多少行能放下S,以及最后一行使用的宽度是多少个单位?将你的答案作为长度为2的整数列表返回。

示例

解题思路

只用遍历字符串,则当前的字符在widths数组中的索引即为该字符减去'a'字符所得的值

用索引获取该字符宽度,若宽度能放入,则该行宽度加上该字符宽度,不能则换行,行数++,行宽度清零并加上该字符宽度。

代码


171.Excel表列序号

给定一个Excel表格中的列名称,返回其相应的列序号。

示例

解题思路

遍历字符串,每找到一个字符,sum都相当于它乘以26再加上当前字母的序列

代码


766.托普利茨矩阵

如果一个矩阵的每一方向由左上到右下的对角线上具有相同元素,那么这个矩阵是托普利茨矩阵。

给定一个 M x N 的矩阵,当且仅当它是托普利茨矩阵时返回 True。

示例

解题思路

遍历每个元素,判断与右下角的是否相同,不同直接return false

代码


566.重塑矩阵

在MATLAB中,有一个非常有用的函数 reshape,它可以将一个矩阵重塑为另一个大小不同的新矩阵,但保留其原始数据。

给出一个由二维数组表示的矩阵,以及两个正整数r和c,分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。

如果具有给定参数的reshape操作是可行且合理的,则输出新的重塑矩阵;否则,输出原始矩阵。

示例

解题思路

无法转化的是由于要转化的矩阵的元素个数比原来更多(如2 * 4>2 * 2)

所以如果元素个数比原来多的直接return原来的矩阵。

可以转化的就把原来的矩阵转化为一维,然后依次赋值到新的矩阵。

代码


575.分糖果

给定一个偶数长度的数组,其中不同的数字代表着不同种类的糖果,每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。

示例

解题思路

可以发现,如果妹妹可以拿的糖果数量比糖果种类数量多,则可以把每种糖果都拿完,如果少的话,只能拿走她能拿的个数种糖果
所以,只用找出糖果的种类数,并与糖果个数的一半(妹妹能拿的糖果数比较即可)

代码


476.数字的补数

给定一个正整数,输出它的补数。补数是对该数的二进制表示取反。

注意:

1.给定的整数保证在32位带符号整数的范围内。
2.你可以假定二进制数不包含前导零位。

示例

解题思想

异或可以用于取反,只用获得该数的二进制位数,弄出一个二进制和这个位数相同的全是1的数,与原数异或,便可得到答案

代码


463.岛屿的周长

给定一个包含 0 和 1 的二维网格地图,其中 1 表示陆地 0 表示水域。网格中的格子水平和垂直方向相连(对角线方向不相连)。整个网格被水完全包围,但其中恰好有一个岛屿(或者说,一个或多个表示陆地的格子相连组成的岛屿)。岛屿中没有“湖”(“湖” 指水域在岛屿内部且不和岛屿周围的水相连)。格子是边长为 1 的正方形。网格为长方形,且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]

image

解题思路

遍历地图,从第一个方块开始一层层向下搜索,每个1的方块都向四个方向判断,四个方向有几个1,它的周长就减去几,这些方块的周长的和即为岛屿的周长

代码


412.Fizz Buzz

写一个程序,输出从 1 到 n 数字的字符串表示。

  1. 如果 n 是3的倍数,输出“Fizz”;

  2. 如果 n 是5的倍数,输出“Buzz”;

  3. 如果 n 同时是3和5的倍数,输出 “FizzBuzz”。

示例

解题思路

过于简单,不解释了

代码

485.最大连续1的个数

给定一个二进制数组, 计算其中最大连续1的个数。

示例

解题思路

把每段1的长度都弄进List中,最后在这个List中找最大值

代码


283.移动零

给定一个数组 nums, 编写一个函数将所有 0 移动到它的末尾,同时保持非零元素的相对顺序。

例如, 定义 nums = [0, 1, 0, 3, 12],调用函数之后, nums 应为 [1, 3, 12, 0, 0]。

注意事项:

  1. 必须在原数组上操作,不要为一个新数组分配额外空间。
  2. 尽量减少操作总数。

示例

解题思路

遍历数组,将非0的全部放到前面,再把剩下的位置填上0

代码


258.各位数

给一个非负整数 num,反复添加所有的数字,直到结果只有一个数字。

例如:

设定 num = 38,过程就像: 3 + 8 = 11, 1 + 1 = 2。 由于 2 只有1个数字,所以返回它。

示例

解题思路

用递归的方式,直到只有一位
遇到特殊值0则直接返回0

代码


520.检测大写字母

给定一个单词,你需要判断单词的大写使用是否正确。

我们定义,在以下情况时,单词的大写用法是正确的:

全部字母都是大写,比如"USA"。
单词中所有字母都不是大写,比如"leetcode"。
如果单词不只含有一个字母,只有首字母大写, 比如 "Google"。
否则,我们定义这个单词没有正确使用大写字母。

示例

解题思路

通过前两个字母判断它是哪种情况,并进行相应的判断

需要注意的是比较坑的数据

单个字母。直接返回true

如果第一个是小写,第二个是大写,就直接返回false

代码


本部分完结


Android Developer in GDUT