章节主要目的
主要是围绕高质量代码，完成性、规范性和鲁棒性。 测试用例的编写，通常情况，我们为了完成单元测试覆盖率都是草草了事，学习这一章我们可以发现，我们之前的测试用例实用性很差，只有正常情况的用例，并且很多时候只有一个。之后我也跟着用例从三方面来运行：1、功能测试，2、负面测试，3、边界测试。负面测试可以理解为错误测试，异常情况的测试。
正式开始第三章
面试题11:数值的整数次方
leetcode-cn.com/problems/shu-zhi-d... 按照题意，很容易写出来基本的逻辑代码。
代码语言：javascript复制func myPow(x float64, n int) float64 {
var result = 1.0
if n < 0 {
x = 1 / x
n = -n
}
for i := 0; i < n; i {
result *= x
}
return result
}可惜，会提示超时，尴尬的很，于是乎看了一遍原文的逻辑，重新实现一遍，逻辑如下： 快速幂 算法 算法流程： 当 x = 0 时：直接返回 0 （避免后续 x = 1 / x操作报错）。 初始化 res = 1 当 n < 0 时：把问题转化至 n≥0 的范围内，即执行 x = 1/x ，n = - n ； 循环计算：当 n = 0时跳出； 当 n & 1 == 1 时：将当前 x乘入 res （即 res *= x）； 执行 x = x^2 （即 x *= x） 执行 n 右移一位（即 n >>= 1）。 返回 res
代码语言：javascript复制func myPow(x float64, n int) float64 {
var result = 1.0
if n < 0 {
x = 1 / x
n = -n
}
for ; n > 0; {
if n&1 == 1 { //又学了一招位运算，等价于 n % 2 == 1
result *= x
}
x *= x
n >>= 1 // 指数减半
}
return result
}面试题12: 打印1到最大的n位数
leetcode-cn.com/problems/da-yin-co... 虽然能通过leetcode，但是不符合书本上出题的目的，因为要考虑大数的情况下才行，书上给出的思路是转换成字符串来进行输出
代码语言：javascript复制func printNumbers(n int) []int {
res := make([]int,0)
var count = 1
for i := 1; i < n; i {
count *= 10
}
for i := 0; i < count; i {
res = append(res,i)
}
return res
}这不包括大数，不是书本出题的本意，修改如下： 考察的是代码的完整性 返回就不能是[]int 而应该是[]string，看具体代码，没办法在leetcode验证，只能自己打印日志看了。
代码语言：javascript复制func printNumbers(n int) []string {
if n <= 0 {
return nil
}
res := make([]int, 0)
result := make([]string, 0)
number := make([]int, n)
for !increment(number) {
for i := 0; i < len(number); i {
res = append(res, number[i])
}
}
//数组按n位切分成而为数组
temp := make([]int, 0)
for i := 0; i < len(res); i {
temp = append(temp, res[i])
if (i 1)%n == 0 { // 3余数是0 。说明是n的整数倍
result = append(result, getString(temp))
temp = make([]int, 0)
}
}
return result
}
func getString(number []int) string {
var res string
isBegin := false
for i := 0; i < len(number); i {
if number[i] != 0 {
isBegin = true
}
if isBegin {
res = fmt.Sprintf("%d", number[i])
}
}
return res
}
func increment(number []int) bool {
var isOverFlow = false //是否溢出结束
var nTakeOver = 0 // 进位
var nLength = len(number)
for i := nLength - 1; i >= 0; i-- {
nSum := number[i] nTakeOver
if nLength-1 == i {
nSum
}
if nSum >= 10 {
if i == 0 {
isOverFlow = true
} else {
nSum -= 10
nTakeOver = 1
number[i] = nSum
}
} else {
number[i] = nSum
break
}
}
return isOverFlow
}面试题13: 在O(1)时间删除链表节点
leetcode-cn.com/problems/shan-chu-... leetcode要求比书本上的低，没有时间复杂度的要求
代码语言：javascript复制// 先不考虑O（1），遍历是最直接的
func deleteNode(head *ListNode, val int){
if head == nil {
return
}
for head.Next != nil {
if head.Next.Val == val {
head.Next = head.Next.Next
}
head = head.Next
}
}链表少不了假头、新链表、双指针等辅助，目前就是使用假头的最佳实例，和书上的不一样哈，课本上的删除就完了，不用返回，力扣是要删除后返回头节点的
代码语言：javascript复制func deleteNode(head *ListNode, val int) *ListNode {
//for head.Next != nil {
// if val == head.Next.Val {
// head = head.Next.Next//删除节点 课本上这就结束了。
// }
//}
dummy := &ListNode{}// 生成一个新链表
tail := dummy
for head != nil {
if head.Val != val {
//添加到新的链表中
tail.Next = head
tail = head
}
head = head.Next
}
tail.Next = nil //设置尾部为空
return dummy.Next
}上面的例子中，空间复杂度是O(n),想要是1的话，只能按照课本上的参数传递才行，否者不可实现
代码语言：javascript复制func deleteNode(head *ListNode, deleteNode *ListNode) {
if head == nil || deleteNode == nil {
return
}
if deleteNode.Next != nil {//不是尾节点
//删除的节点下一个值，替换需要删除的节点，然后删除下一个节点，等同于删除当前节点
deleteNode.Val = deleteNode.Next.Val
deleteNode.Next = deleteNode.Next.Next
}else if head == deleteNode {//删除的是头节点，只有一个节点
head = nil
}else{ // 多个节点，删除的是尾节点 第一个if条件难道不包括吗？
for head.Next != deleteNode {
head = head.Next
}
head.Next = nil
}
}面试题14: 调整数组顺序使奇数位于偶数前面
leetcode-cn.com/problems/diao-zhen... 思路：两个指针，一个指向头，一个指向尾部，两边同时向中间移动，如果头指针的值偶数，尾指针是奇数就交换 通用性：判断条件改为函数来判断，分离出来nums[left]&1 == 1和nums[right]&1 == 0换成函数就可以了，很简单，自行添加一下。
代码语言：javascript复制func exchange(nums []int) []int {
if len(nums) == 0 {
return nil
}
var left = 0
var right = len(nums) - 1
for left < right {
for left < right && nums[left]&1 == 1 { //奇数，右移left
left
}
for left < right && nums[right]&1 == 0 { //偶数，左移right
right--
}
if left < right { //交换
nums[left], nums[right] = nums[right], nums[left]
}
}
return nums
}面试题15: 链表中倒数第k个节点
leetcode-cn.com/problems/lian-biao... 思路：两个指针，一个指向头，一个先走k步，简称：快慢指针
代码语言：javascript复制func getKthFromEnd(head *ListNode, k int) *ListNode {
if head != nil {
return nil
}
var first = head
var second = head
for i := 0; i < k; i {
second = second.Next
}
for second != nil {
first = first.Next
second = second.Next
}
return first
}面试题16: 反转链表
leetcode-cn.com/problems/UHnkqh/ 这题，如果没有限制返回头节点，仅仅是输出的话，实现方式是N多种，数组也是可以的。但是这里的要求是返回反转后的头节点，所以，需要辅助手段。
代码语言：javascript复制//需要把节点保存起来，断开之后防止找不到
func reverseList(head *ListNode) *ListNode {
var prevHead *ListNode //保存遍历的前一个节点
var currentNode = head //保存遍历的当前节点
for currentNode != nil {
nextNode := currentNode.Next
currentNode.Next = prevHead
prevHead = currentNode
currentNode = nextNode
}
return prevHead
}按照课本上的做法，我临摹过来的代码，但是，这个代码我感觉有点小问题，却又不知道问题在哪，各位朋友知道的还望指出来，并改正一下，不胜感激。
代码语言：javascript复制func reverseList(head *ListNode) *ListNode {
var reversedHead *ListNode //反转后的头节点
var prev *ListNode
var node = head
for node != nil {
next := node.Next
if next == nil {
reversedHead = node
}
node.Next = prev
prev = node
node = next
}
return reversedHead
}面试题17: 合并两个排序的链表
leetcode-cn.com/problems/he-bing-l... 同样利用了链表的假头和新链表作为辅助
代码语言：javascript复制func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{}
tail := dummy
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
tail.Next = l1
l1 = l1.Next
} else {
tail.Next = l2
l2 = l2.Next
}
tail = tail.Next
}
if l1 != nil {// 如果l1还有，直接拼接到后面
tail.Next = l1
tail = tail.Next
l1 = l1.Next
}
if l2 != nil {//如果l2还有，直接拼接后面
tail.Next = l2
tail = tail.Next
l2 = l2.Next
}
return dummy.Next
}面试题18: 树的子结构
leetcode-cn.com/problems/shu-de-zi... 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构) 主要和树相关的，就没有简单级别的，当然，和递归相关的也都是没有简单的。不熟悉递归和树的，这题需要点时间去理解。
代码语言：javascript复制func isSubStructure(A *TreeNode, B *TreeNode) bool {
var result = false
if A != nil && B != nil {
//先比较根节点，再比较左右子树节点
if A.Val == B.Val {
//根节点满足，判断不是子结构
result = isStructure(A,B) //不用递归，也可写成左右子树的判断
}
//比较左子树为根节点，开始遍历比较
if !result {
result = isSubStructure(A.Left,B)
}
//比较右子树为根节点，开始遍历比较
if !result {
result = isSubStructure(A.Right,B)
}
}
return result
}
func isStructure(a *TreeNode, b *TreeNode) bool {
if b == nil {//说明树 B 已匹配完成（越过叶子节点），因此返回 true
return true
}
if a == nil {//说明已经越过树 A 叶子节点，即匹配失败，返回 false
return false
}
if a.Val != b.Val {//值不同，匹配失败，返回 false
return false
}
return isStructure(a.Left,b.Left) && isStructure(a.Right,b.Right)
}
``````go
func isSubStructure(A *TreeNode, B *TreeNode) bool {
var result = false
if A != nil && B != nil {
//先比较根节点，再比较左右子树节点
if A.Val == B.Val {
//根节点满足，判断不是子结构
result = isStructure(A,B) //不用递归，也可写成左右子树的判断
}
//比较左子树为根节点，开始遍历比较
if !result {
result = isSubStructure(A.Left,B)
}
//比较右子树为根节点，开始遍历比较
if !result {
result = isSubStructure(A.Right,B)
}
}
return result
}
func isStructure(a *TreeNode, b *TreeNode) bool {
if b == nil {//说明树 B 已匹配完成（越过叶子节点），因此返回 true
return true
}
if a == nil {//说明已经越过树 A 叶子节点，即匹配失败，返回 false
return false
}
if a.Val != b.Val {//值不同，匹配失败，返回 false
return false
}
return isStructure(a.Left,b.Left) && isStructure(a.Right,b.Right)
}
``````go
func isSubStructure(A *TreeNode, B *TreeNode) bool {
var result = false
if A != nil && B != nil {
//先比较根节点，再比较左右子树节点
if A.Val == B.Val {
//根节点满足，判断不是子结构
result = isStructure(A,B) //不用递归，也可写成左右子树的判断
}
//比较左子树为根节点，开始遍历比较
if !result {
result = isSubStructure(A.Left,B)
}
//比较右子树为根节点，开始遍历比较
if !result {
result = isSubStructure(A.Right,B)
}
}
return result
}
func isStructure(a *TreeNode, b *TreeNode) bool {
if b == nil {//说明树 B 已匹配完成（越过叶子节点），因此返回 true
return true
}
if a == nil {//说明已经越过树 A 叶子节点，即匹配失败，返回 false
return false
}
if a.Val != b.Val {//值不同，匹配失败，返回 false
return false
}
return isStructure(a.Left,b.Left) && isStructure(a.Right,b.Right)
}接下来的算法都是非常难的，我也不知道多久能研究透彻，可以确定的是更新时间肯定比第二第三章要晚。
本作品采用《CC 协议》，转载必须注明作者和本文链接
