leetcode 数组简单难度习题一

2019-12-28 by 杜宏伟

leetcode对习题做了分类,数组问题是最常见的一类问题。因为题目较多,分多集。本篇是第一集。

从排序数组中删除重复项

算法时间复杂度空间复杂度
双指针O(n)O(1)

买卖股票的最佳时机 II

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

算法 时间复杂度 空间复杂度
贪婪法 O(n) O(1)

对于这种中间过程没有分叉的情况,可以用贪心算法。

旋转数组

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

反转过程:反转所有数字,反转前K个数字,反转n-k个数字

算法 时间复杂度 空间复杂度
暴力 O(n*k) O(1)
额外的数组 O(n) O(n)
环状替换 O(n) O(1)
反转 O(n) O(1)

存在重复

给定一个整数数组,判断是否存在重复元素。 如果任何值在数组中出现至少两次,函数返回 true。如果数组中每个元素都不相同,则返回 false。

算法 时间复杂度 空间复杂度
排序 O(nlogn) O(1)
哈希表 O(n) O(n)

只出现一次的数字(其它的数字都出现两次)

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

算法 时间复杂度 空间复杂度
哈希表 O(n) O(n)
位操作 O(n) O(1)
数学 O(n) O(n)

位操作,xor异或操作有这样的特性:相同的数字异或为0,0与任何数字异或得到那个数字

数学,2∗(a+b+c)−(a+a+b+b+c)=c

类似

  1. 找缺失的数字

两个数组的交集 II

给定两个数组,编写一个函数来计算它们的交集。

算法 时间复杂度 空间复杂度
两个哈希表 O(n+m) O(n+m)
一个哈希表 O(n+m) O(min(n,m))
排序 O(nlogn+mlogm) O(1)

两个哈希表最容易想到,但完全可以用一个哈希表代替 用一个哈希表注意用较短数组做哈希

加1

给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。

最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外,这个整数不会以零开头。

个位加1后,循环进位

移动零

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

从后面的第一个 非0数字向前移动,遇到0就跳过

有效的数独

如何判断3x3范围内的数字属于一个区域?

可以使用box_index = (row / 3) * 3 + columns / 3,其中 / 是整数除法。 最简单的想法分三次扫描

  1. 判断行内有没有重重元素
  2. 判断列内有没有重复元素
  3. 判断3x3区域内有没有重复元素

也可以一次扫描完成。不过因为9x9格子数是常量,对于这种时间复杂度和空间复杂度一般不敏感的情况,代码清晰优先考虑。

下一个排列

数字是从小到大排列的,下一个排列一定是大的在前面,最后一个排列就是从大到小的排列。

  1. 从右向左找到第一个左比右小的数
  2. 以这个数为界,在右边找到第一个比自己大的数,交换
  3. 把右的数按从小到大排列

搜索旋转排序数组

  1. 找到这个拐点
  2. 对两段分别进行二分

最大连续子序和

算法 时间复杂度 空间复杂度
动态规划 O(n) O(1)
贪心 O(n) O(1)
分冶 O(nlogn) O(logn)

贪心可以,是因为中间没有其它选择,只能选择下一个

杨辉三角

算法 时间复杂度 空间复杂度
动态规划 O(n2) O(n2)

两数之和 II - 输入有序数组

给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。

关键在于有序二字。可以用双指针法。

求众数

算法 时间复杂度 空间复杂度
暴力 O(n2) O(1)
哈希表 O(n) O(n)
排序 O(nlogn) O(1)或O(n)
分治 O(nlogn) O(logn)
投票算法 O(n) O(1)

排好序后,众数一定出现在 n/2的位置上

分冶从一个数开始,计数每个规模下的众数,合并的时候,如果不同,分别计算合并后的两个众数在当前规模下的总数,得出当前规则的众数

投票算法。如果我们把众数记为 +1 ,把其他数记为 −1 ,将它们全部加起来,显然和大于 0 ,从结果本身我们可以看出众数比其他数多。

第三大的数

用一个数组维护前三大的数,一次遍历可解

找到所有数组中消失的数字

给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

除了哈希表,还有一种原地修改的方法。

消失二字可以理解为没有,表示有或没有一对值,可以用正负来表示,可以把正负信息原地存在数组中,同时又可以取到数组原来的信息。

数组中的K-diff数对

这是两数和问题的一个变形

数组拆分1

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

把一个数组一分为二,要想两部分的差值最大,肯定是最大的一组,最小的一组,这时min(ai,bi)的最小,如果要想和最大,需要两部分的差值最小,差值最小的情况就是排好序进行分割的情况

还有一种线性复杂度的算法,桶排序

最短无序连续子数组

算法 时间复杂度 空间复杂度
排序 O(nlogn) O(n)
使用栈 O(n) O(n)
不使用额外空间 O(nlogn) O(n)

找到无序子数组的最小元素和最大元素的位置,这期间的就是解。

种花问题

每一步,虽然有种或不两种种选择,但不种肯定完不成任务,所以其实只有一种种的选择,所以适合用贪心。

提前完成了任务可以提前结束

三个数的最大乘积

两种方法

  1. 排序。只能是最大三个或最小两个与最大一个
  2. 一次遍历找到最小两个与最大三个数

子数组最大平均数 I

给定 n 个整数,找出平均数最大且长度为 k 的连续子数组,并输出该最大平均数。

也就是求子数组K个连续子数组的和。

  1. 累计求和
  2. 滑动窗口

非递减序列

给定一个长度为 n 的整数数组,你的任务是判断在最多改变 1 个元素的情况下,该数组能否变成一个非递减数列。

  1. 贪心算法。遇到需要调整的就调整,看需要调整的次数是否大于1
  2. 暴力。每次改变一个值 a[i+1]=a[i],然后判断整个数组

最长连续递增序列

给定一个未经排序的整数数组,找到最长且连续的的递增序列。

用滑动窗口法

数组的度

给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。

你的任务是找到与 nums 拥有相同大小的度的最短连续子数组,返回其长度。

先找到数组的度。再找到每个元素的最左,最右值,找到区间最小的。

我叫杜宏伟,前端开发。

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

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

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

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