青梅梦呓

和世界交手的这许多年,你是否光彩依旧,兴致盎然

0%

数组算法训练

准备认真练习算法题目,个人使用Go语言进行练习,这是算法系列文章的第一篇。

LeetCode 数组专项训练

移动零 #283


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

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

1.必须在原数组上操作,不能拷贝额外的数组。
2.尽量减少操作次数。


解法1

参考快速排序的方法,快速排序的思想就是首先确定一个待分割的元素作为中间点X,然后把所有小于x的元素放在左边,大于x的元素放在右边。

我们使用0作为分割点,把不是0的元素(可能是负数)放在左边,等于0的放在其右边,中间点就是0本身。只要使用指针zero和index即可,只有nums[index]不是0,就交换nums[index]nums[zero]。如下动图所示:

移动零

1
2
3
4
5
6
7
8
9
func moveZeroes(nums []int)  {
zero := 0
for index := range nums {
if nums[index] != 0 {
nums[index],nums[zero] = nums[zero],nums[index]
zero++
}
}
}
解法2 快慢指针

利用快慢指针指针,如果快指针所指向的值为0,就把快指针往前走一步;如果不为0,慢指针与快指针所指向的元素进行交换,两个指针均往前走一步。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func moveZeroes(nums []int) {
if len(nums) == 0 {
return
}
fast,slow := 0,0
for fast < len(nums) {
if nums[fast] != 0 {
nums[fast],nums[slow] = nums[slow],nums[fast]
fast++
slow++
} else {
fast++
}
}
}

加一 #66


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

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

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

示例 1:

输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:

输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。


依照常规的想法,从末尾开始遍历,如果值不是9,就把这个值加一并返回数组即可;如果值是9,就把这个值置为0,继续下一次循环即可;如果一直进位(例如:999),就在前面添加个1,然后返回就好。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func plusOne(digits []int) []int {
if len(digits) == 0 {
return []int{1}
}

for index := len(digits) -1 ; index >= 0; index-- {
if digits[index] == 9 {
digits[index] = 0
} else {
digits[index]++
return digits
}
}
return append([]int{1},digits...)
}

两数之和 #1


给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

示例 :

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


  1. 先遍历数组nums,i为当前的下标,我们需要将每一个遍历的值放入map作为key

两数之和

  1. 同时对每个值都进行判断,看map中是否存在keytarget-nums[i]的值。 在第二步的时候9-7 这个时候看到map中是有这个key的。

两数之和

  1. 所以2和7所在的key对应的value,也就是[0,1],也就是我们需要找的两个数组的下标。

所以代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
func twoSum(nums []int,target int) []int {
var result []int
m := make(map[int]int,len(nums))

for index,value := range nums {
if val,ok := m[target-value];ok {
result = append(result,val)
result = append(result,index)
}
m[value] = index
}
return result
}

旋转数组 #189


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

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]


官方题解提供了四种解法,其中环状替代法和反转法是最靓的两种方法