leetcode的explore中有一个Top Interview Questions，列出了一些简单的热门面试问题。今天从数组类中挑选一部分讲解。
数组轮转
题目
给一个数组nums，例如[1,2,3,4]，要求向右轮转k次后返回。例如，轮转一次的结果是[4,1,2,3]。
解法
最容易想到的解法应该是：再创建一个数组result，长度和nums相等，然后将nums中的每个元素下标i进行转换 (i+k)%len(nums) ，填入新的数组中即可。
这种方法的时间复杂度O(n)，空间复杂度O(n)
进阶1
要求空间复杂度为O(1)
既然要求原地（in place），就只能在原数组上进行元素交换。最简单的方法是每次移动一位，重复k次。伪代码：
for i:=0; i<k; i++ {
for j:=len(nums)-1; j>=0; j-- { // 从后向前遍历
exchange(nums[j], nums[(j+1)%len(nums)])，// 相邻两项交换
}
}
这个方法的空间复杂度显然是O(1)，但时间复杂度比上面的方法要高，是O(nk)
进阶2
要求in place的同时，时间复杂度仍然是O(n)。
题目中的向右轮转k次，实际上相当于把数组以右数第k个为分界线分成两块，这两块交换了一下位置，但每块内部的顺序不变。
这就需要用到一个技巧：把整个数组反转，再将两块分别反转，即可达到这样的效果。伪代码：
// 入口函数
func resolve(nums []int, k) {
reverseSubArray(nums, 0, len(nums)-1) // 反转整个数组
reverseSubArray(nums, 0, k-1) //反转前k个
reverseSubArray(nums, k, len(nums)-1) //反转后n-k个
}
func reverseSubArray(nums []int, i, j int) { // 将nums中从i到j的部分进行反转
for i < j {
nums[i], nums[j] = nums[j], nums[i]
}
}
两数之和等于目标值
题目
给定一个target，求数组中哪两个数之和等于这个target，求这两个下标（两个数可以相等，但下标必须不同）
解法
从前向往后遍历数组，用一个map存储值与下标的对应关系
再次从前往后遍历数组，检查map中是否存在target-x，且下标与当前值不同。若有则返回。伪代码：
mp := make(map[int]int)
for i, x := range nums {
mp[x] = i
}
for i, x := range nums {
ind := mp[target-x] > 0
if ind > 0 && ind != i {
return i, ind //找到了
}
}
注意对于结果两个数相等的情况，第一次遍历，在map中后面的值会覆盖前面的；第二次遍历，会先遍历到前面的值，因此这种情况不会漏掉。
其他问题
有序数组中删除重复数字
这道题要求空间复杂度O(1)，思路也很简单，只要用两个指针，遍历数组即可解决。比较简单不细说。
买卖股票的最佳时间
题目：用一个数组表示每天股票的价钱，一开始没有持有股票，最多持有一股，可以不交易。求最大收益。
分析：虽然题目描述有些复杂，但其实很简单，就是找出每一次上涨，把这些上涨加起来就是最大收益。
解法：从下表1开始遍历数组，如果比上一个数大，则把差值加在sum中即可。
数组中是否包含重复元素
数组转成set，遍历一下即可
如果要求原地，可以排序后依次比较相邻两项是否相等。
单独的数字
其他数字都有两个，只有一个数字只有一个，求这个数字是多少。
技巧：异或
旋转矩阵
题目：二维数组两个纬度的长度相等，将二维数组对应的矩阵右转90度。
由于要求原地，因此旋转的时每移动一个元素，应该同时把旋转后对应位置的四个元素全部移动完成，这样才不需要额外的空间进行记录。
关键点有两个
- 找到原坐标对应旋转90\180\270度后的坐标
- 外层循环只需要遍历1/4个矩阵即可，要确定这个范围。
网友评论