【golang】leetcode初级-加一&移动零
第一题 加一
题目信息
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1：
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
示例 2：
输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
示例 3：
输入：digits = [0]
输出：[1]
提示：
1 <= digits.length <= 100
0 <= digits[i] <= 9
解题思路
对于一个数加一，有以下几种情况
1.没有发生进位
2.不断发生进位，直到某一位不需要进位的时候停下回到第一种情况
3.数字首位为9且需要进位，则应将数组长度加一
因此我们可以将进位过程写入函数中，在有需要的时候可以随时调用
代码
func inc(digits []int,n int) []int{
if digits[n]<9{
digits[n]++
return digits
}else{
if n==0{
digits=append(digits,0)
copy(digits[1:len(digits)-1],digits[:len(digits)-2])
digits[0]=1
digits[1]=0
return digits
}else {
digits[n] = 0
return inc(digits, n-1)
}
}
}
func plusOne(digits []int) []int {
n:=len(digits)-1
return inc(digits,n)
}复杂度分析
时间复杂度：O(n) 最坏情况为数组每个元素都发生进位，进行了n次函数调用
空间复杂度：O(n^2) 每次函数调用需要数组长度的空间
文章图片
显然，选择函数递归调用实质是牺牲空间换取时间的做法
官方题解
文章图片
显然 这个解题思路比起上面的解法更炫酷
代码
func plusOne(digits []int) []int {
n := len(digits)
for i := n - 1;
i >= 0;
i-- {
if digits[i] != 9 {
digits[i]++
for j := i + 1;
j < n;
j++ {
digits[j] = 0
}
return digits
}
}
// digits 中所有的元素均为 9digits = make([]int, n+1)
digits[0] = 1
return digits
}
复杂度分析
时间复杂度：O(n)，其中 n 是数组digits 的长度。
空间复杂度：O(1)。返回值不计入空间复杂度。
空间使用比起函数调用明显得到了很大的优化
第二题 移动零 题目信息
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
解题思路
双指针
指针b查找数组的非零元素
指针a记录非零元素
在b完成遍历之后，将数组在a之后的部分置零
代码
func moveZeroes(nums []int){
a,b:=0,0
for b复杂度分析
【【golang】leetcode初级-加一&移动零】
文章图片
时间复杂度：O(n) b完成对数组的遍历，a最差结果为数组的所有元素都为零
空间复杂度：O(2)。定义了ab两个变量
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长