leetcode 数组简单难度习题二

2020-01-01 by 杜宏伟

leetcode习题第二集

寻找数组的中心索引

给定一个整数类型的数组 nums,请编写一个能够返回数组“中心索引”的方法。

我们是这样定义数组中心索引的:数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。

如果数组不存在中心索引,那么我们应该返回 -1。如果数组有多个中心索引,那么我们应该返回最靠近左边的那一个。

S 是数组的和,当索引 i 是中心索引时,位于 i 左边数组元素的和 leftsum 满足 S - nums[i] - leftsum。 我们只需要判断当前索引 i 是否满足 leftsum==S-nums[i]-leftsum 并动态计算 leftsum 的值。

使用最小花费爬楼梯

数组的每个索引做为一个阶梯,第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。

每当你爬上一个阶梯你都要花费对应的体力花费值,然后你可以选择继续爬一个阶梯或者爬两个阶梯。

您需要找到达到楼层顶部的最低花费。在开始时,你可以选择从索引为 01 的元素作为初始阶梯。

最基础的动态规划题目。

至少是其他数字两倍的最大数

在一个给定的数组nums中,总是存在一个最大元素 。

查找数组中的最大元素是否至少是数组中每个其他数字的两倍。

如果是,则返回最大元素的索引,否则返回-1。

线性扫描两次。

托普利茨矩阵

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

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

方法一: 对角线法

首先要想明白的是怎么判断 (r1, c1 和 (r2, c2) 这两个点属于一条对角线。通过观察可以发现,在满足 r1 - c1 == r2 - c2 的情况下,这两个点属于同一条对角线。

在上面的问题搞清楚的情况下,很容易就可以想到:让 groups[r-c] 存储每条对角线上遇到的第一个元素的值,如果之后遇到的任何一个值不等于之前存储的值,那么这个矩阵就不是托普利茨矩阵,否则就是。

方法二: 检查左上邻居

对于对角线上的元素来说,如果当前元素不是第一个出现的元素,那么它前面的元素一定在当前元素的左上角。可以推出,对于位于坐标 (r, c) 上的元素,只需要检查 r == 0 OR c == 0 OR matrix[r-1][c-1] == matrix[r][c] 就可以了。

到最近的人的最大距离

输入:[1,0,0,0,1,0,1]

输出:2

解释:如果坐在第二个空位(seats[2])上,到离最近的人的距离为 2 。 如果坐在其它任何一个空位上,到最近的人的距离为 1 。 因此,到离他最近的人的最大距离是 2

算法:找到相邻的1的位置,算出相邻的1之前的距离d,如果d 是奇数 (d-1)/2,如果是偶数(d-2)/2,减1是因为得坐一个人,需要一个位置,减2是因为除数应该为偶数,这样才能直接得到结果

公平的糖果交换

给定两个数组,编写一个函数来计算它们的交集。 爱丽丝和鲍勃有不同大小的糖果棒:A[i] 是爱丽丝拥有的第 i 块糖的大小,B[j] 是鲍勃拥有的第 j 块糖的大小。

因为他们是朋友,所以他们想交换一个糖果棒,这样交换后,他们都有相同的糖果总量。(一个人拥有的糖果总量是他们拥有的糖果棒大小的总和。)

返回一个整数数组 ans,其中 ans[0] 是爱丽丝必须交换的糖果棒的大小,ans[1] 是 Bob 必须交换的糖果棒的大小。

如果有多个答案,你可以返回其中任何一个。保证答案存在。

两数和问题的变形。SA,SB表示总数,EA,EB表示交换的量,假设SA比较大,交换的量为 SA-SB/2=EA-EB,所以选EA后,看有没有EB就行了。

按奇偶排序数组

给定一个非负整数数组 A,返回一个数组,在该数组中, A 的所有偶数元素之后跟着所有奇数元素。

你可以返回满足此条件的任何数组作为答案。

方法一

按模2的余数进行排序

方法二

双指针。

按奇偶排序数组 II

给定一个非负整数数组 A, A 中一半整数是奇数,一半整数是偶数。

对数组进行排序,以便当 A[i] 为奇数时,i 也是奇数;当 A[i] 为偶数时, i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

双指针。遇到不对的就交换,交换一次就可以解决两个位置。

有效的山脉数组

给定一个整数数组 A,如果它是有效的山脉数组就返回 true,否则返回 false。

让我们回顾一下,如果 A 满足下述条件,那么它是一个山脉数组:

A.length >= 3

0 < i < A.length - 1 条件下,存在 i 使得:

A[0] < A[1] < ... A[i-1] < A[i]

A[i] > A[i+1] > ... > A[B.length - 1]

双指针。线性扫描也行。

斐波那契数

斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

F(0) = 0, F(1) = 1

F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

给定 N,计算 F(N)

虽然简单,但是非常重要。要牢记,因为是递归和动态规划的最简示例题目。

排序数组的平方

给定一个按非递减顺序排序的整数数组 A,返回每个数字的平方组成的新数组,要求也按非递减顺序排序。

双指针。因为负数平方后是降序排列,正好从数组的末尾开始插入。

数组形式的加法

对于非负整数 X 而言,X 的数组形式是每位数字按从左到右的顺序形成的数组。例如,如果 X = 1231,那么其数组形式为 [1,2,3,1]

给定非负整数 X 的数组形式 A,返回整数 X+K 的数组形式。

解释:因为X非常大,所以需要用数组表示,K是可以正常表示的数,既使加上10以内的数也不会溢出。

算法:把K和数组的高位相加,保留个位,其余的作为进位加到下一位。

我叫杜宏伟,前端开发。

一直想写博客,在2018的年的最后几天,终于上线了。

对于前端开发,一个特点就是太零散,很容易会了后面忘了前面,所以归纳总结很重要。再有就是分享,做前端好多年,以前都是看你们写的文章, 现在我也开始写一些,希望可以帮到入行的小伙伴。微信号 duhongwei5775

欢迎转载,只需注明作者,出处即可

版权说明:署名 4.0 国际(CC BY 4.0)