第一题 加一
题目信息
给定一个由 整数 组成的 非空 数组所示意的非负整数，在该数的根底上加一。
最高位数字寄存在数组的首位， 数组中每个元素只存储单个数字。
你能够假如除了整数 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 中所有的元素均为 9 digits = 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<len(nums){ if nums[b]!=0{ nums[a]=nums[b] a++ } b++ } for a<len(nums){ nums[a]=0 a++ }}复杂度剖析
工夫复杂度：O(n) b实现对数组的遍历，a最差后果为数组的所有元素都为零
空间复杂度：O(2)。定义了ab两个变量