21-30

# 21.调整数组顺序使奇数位于偶数前面

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

哈哈，居然做出来了，这题其实最简单的方法就是使用双指针进行替换

# 解法一：双指针

func exchange(nums []int) []int {
	low,high:=0,len(nums)-1
	for low < high {
		// 首先我们找到一个偶数
		for high>low && nums[high]%2 == 0 {
			high--
		}
		// 然后找到一个奇数
		for high>low && nums[low]%2 != 0 {
			low++
		}
		// 然后我们进行替换
		nums[low],nums[high]=nums[high],nums[low]
		// 指针移动
		low++
		high--
	}
	return nums
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 解法二：快慢指针

这个其实和双指针差不多，只不过这里我们直接只遍历一次，我们的块指针每次都指向奇数慢指针指向偶数，然后我们进行交换

func exchange(nums []int) []int {
   // 定义快慢两个指针
   slow,fast:=0,0
   // 遍历直到fast遍历到数组尾巴为止
   for fast < len(nums) {
      // 当我们发送fast为奇数时，我们交换一下内容
      if nums[fast]&1>0 {
         // 因为slow是偶数（fast只会交换奇数，交换后的就是偶数了）
         nums[fast],nums[slow] = nums[slow],nums[fast]
         slow++
      }
      // 移动快指针
      fast++
   }
   return nums
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 22.链表中倒数第K个节点

剑指 Offer 22. 链表中倒数第k个节点 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 解法一：两次循环

第一次循环，我们获取一下链表长度，第二次循环我们找到倒数第k个节点

func getKthFromEnd(head *ListNode, k int) *ListNode {
   root:=head
   // n表示链表长度
   n:=0
   // 第一遍for循环，判断链表长度
   for head != nil {
      n++
      head=head.Next
   }
   // 第二遍，返回倒数倒数第k个节点
   for i := 0; i < n-k; i++ {
      root = root.Next
   }
   // 返回节点
   return root
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 解法二：快慢指针

这里原理也很好理解，我们先让快指针移动，慢指针先不动，只有当我们的慢指针和快指针相差k的时候，我们的慢指针就和快指针同步移动

func getKthFromEnd(head *ListNode, k int) *ListNode {
   // 定义快慢两个节点
   slow,fast:=head,head
   t:=0
   for fast != nil {
      // 只有当t>=k的时候我们才移动慢指针，因为我们的t相当于快指针，我们的慢指针要比快指针要小于k
      if t >= k {
         slow=slow.Next
      }
      // 移动快指针
      fast = fast.Next
      t++
   }
   // 判断越界问题
   if t < k {
      return nil
   }
   return slow
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 24.反转链表

剑指 Offer 24. 反转链表 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 解法一：递归法

这里其实就是直接使用递归到达尾结点，然后我们修改一下结点的顺序，从而达到反转的目的

func reverseList(head *ListNode) *ListNode {
   // 当我们的head为空的时候我们停止循环,这个时候返回我们的头节点（其实就是返回尾结点）
   if head == nil || head.Next == nil {
      return head
   }
   // 开始递归获取尾结点
   node:=reverseList(head.Next)
   // 此时我们修改一下指向的顺序
   // 即当前指针的下一个指针的下一个指针指向当前指针
   head.Next.Next = head
   // 此时头节点相当于尾结点了，我们需要置为nil
   head.Next = nil
   return node
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 解法二：双指针

这个解法我想出来了，比较简单，自己可以画一个草稿来简单演示即可

func reverseList(head *ListNode) *ListNode {
   // 表示前一个指针
   var prev *ListNode
   // curr表示当前指针
   curr := head
   for curr != nil {
      // 先记录下一个指针
      next := curr.Next
      // 反转一下位置
      curr.Next = prev
      // 移动一下指针
      prev = curr
      curr = next
   }
   return prev
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 25.合并两个排序链表

剑指 Offer 25. 合并两个排序的链表 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 解法一：头指针

我们定义一个头指针，然后每次比较大小并把新值接到链表中

func mergeTwoLists1(l1 *ListNode, l2 *ListNode) *ListNode {
   res:=&ListNode{}
   cur:=res
   for l1 != nil && l2 != nil {
      // 比较判断
      if l1.Val < l2.Val {
         cur.Next = l1
         l1=l1.Next
      } else {
         cur.Next = l2
         l2=l2.Next
      }
      cur = cur.Next
   }
   // 判断两个节点是否为空
   if l1!=nil {
      cur.Next = l1
   } else {
      cur.Next = l2
   }
   return res.Next
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# 解法二：使用递归

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode{
   // 如果一个节点为空的情况下，我们返回另外一个非空节点
   if l1 == nil { return l2 }
   if l2 == nil { return l1 }
   if l1.Val < l2.Val {
      l1.Next = mergeTwoLists(l1.Next,l2)
      return l1
   } else {
      l2.Next = mergeTwoLists(l1,l2.Next)
      return l2
   }
}

1
2
3
4
5
6
7
8
9
10
11
12

# 26.树的子结构

剑指 Offer 26. 树的子结构 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

# 方法一：使用递归

这题关键的地方就在于如何判断两颗子树是否相等，我们这里最简单粗暴的方法就是遍历所有A子树的节点，然后依次和B进行比较

func isSubStructure(A *TreeNode, B *TreeNode) bool {
   // 这里我们先判断两个节点是否都不为空
   // 如果不为空的话，我们尝试判断AB这两颗树是否一样
   // 如果不一样我们再判断A的左子树或者A的右子树和B是否一样
   return (A!=nil && B!= nil) && (isSame(A,B) || isSubStructure(A.Left,B) || isSubStructure(A.Right,B))
}

// 判断两颗树是否相等
func isSame(A *TreeNode, B *TreeNode) bool{
   // 当B为空时，此时我们就返回true(因为已经比较完毕了)
   if B == nil { return true }
   // 如果A节点为空，B节点不为空
   // 或者A B两个节点的值不相等，我们就返回false
   if A == nil || A.Val != B.Val {
      return false
   }
   // 然后我们分别判断左右子树，确保左右子树也符合条件
   return isSubStructure(A.Left,B.Left) && isSubStructure(A.Right,B.Right)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 27.二叉树的镜像

剑指 Offer 27. 二叉树的镜像 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题我居然做出来了哈哈哈哈哈！害，我这渣渣也只能做做简单题了

# 解法一：使用递归

递归的思路很简单，其实就是我们在遍历的时候，分别交换一下树左右节点就行了

func mirrorTree(root *TreeNode) *TreeNode {
   // 如果节点为空，那么我们就返回空值
   if root==nil { return root }
   // 遍历左右节点
   right := mirrorTree(root.Right)
   left := mirrorTree(root.Left)
   // 交换在左右节点
   root.Left = right
   root.Right = left
   return root
}

1
2
3
4
5
6
7
8
9
10
11

# 解法二：辅助栈

func mirrorTree(root *TreeNode) *TreeNode {
	// 如果根节点为空，那么我们就返回空
	if root==nil {
		return nil
	}
	// 初始化一个栈
	stack:=list.New()
	// 元素入栈操作
	stack.PushBack(root)
	// 当我们栈为空时表示我们替换结束
	for stack.Len() != 0 {
		// 元素出栈
		node:=stack.Remove(stack.Back()).(*TreeNode)
		// 然后我们判断左右子树是否为空
		if node.Left != nil {
			stack.PushBack(node.Left)
		}
		if node.Right != nil {
			stack.PushBack(node.Right)
		}
		// 交换一下元素
		tmp:=node.Left
		node.Left = node.Right
		node.Right = tmp
	}
	return root
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# 28.对称二叉树

剑指 Offer 28. 对称的二叉树 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题emm，我看了上一题以为是先求镜像树，然后再用镜像树和当前树对比。。看了大佬的题解后不禁感慨，果然是我太菜了。。。。

# 方法一：递归法

不得不说，大佬的思路就是牛逼，这里我们通过一个辅助函数就非常简单的把这些东西给判断出来了

func isSymmetric(root *TreeNode) bool {
   if root == nil {
      return true
   }
   // 判断左右两边是否对称
   return recur(root.Right,root.Left)
}

func recur(l *TreeNode,r *TreeNode) bool {
   // 当左右两边都为空的时候我们返回 true
   if l == nil && r == nil { return true }
   // 当两个节点不相同或者有一个节点为空时，我们退出循环
   if l == nil || r == nil || l.Val != r.Val { return false }
   // 这里我们简单的判断两端是否对称
   return recur(l.Left,r.Right) && recur(l.Right,r.Left)
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 29.顺时针打印矩阵

剑指 Offer 29. 顺时针打印矩阵 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题看到简单我以为我可以了，没想到一做就被打回原形了。。。。我是菜鸡。。。

# 解法一模拟法

说实话，这题其实不算很难，但是这种题目很恶心，需要确定好边界条件，要不然很容易出错

test

func spiralOrder(matrix [][]int) []int {
   if len(matrix) == 0 {
      return []int{}
   }
   // 初始化上下左右
   t,b,l,r:=0,len(matrix)-1,0,len(matrix[0])-1
   // 初始化结果数组
   res:=make([]int,(r+1)*(b+1))
   x :=0
   // 开始进行遍历
   for  {
      // 从左到右
      for i:=l;i<=r;i++ { res[x] = matrix[t][i];x++ }
      if t++; t > b { break }
      // 从上到下
      for i:=t;i<=b;i++ { res[x] = matrix[i][r];x++ }
      if r--; l > r { break }
      // 从右到左
      for i:=r;i>=l;i-- { res[x] = matrix[b][i];x++ }
      if b--; t > b { break }
      // 从下到上
      for i:=b;i>=t;i-- { res[x] = matrix[i][l];x++ }
      if l++; l > r { break }
   }
   return res
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

编辑

上次更新: 2021/04/06, 22:01:45

← 11-20 31-40→

21-30

# 21.调整数组顺序使奇数位于偶数前面

# 解法一： 双指针

# 解法二：快慢指针

# 22.链表中倒数第K个节点

# 解法一： 两次循环

# 解法二： 快慢指针

# 24.反转链表

# 解法一：递归法

# 解法二：双指针

# 25.合并两个排序链表

# 解法一： 头指针

# 解法二： 使用递归

# 26.树的子结构

# 方法一： 使用递归

# 27.二叉树的镜像

# 解法一： 使用递归

# 解法二： 辅助栈

# 28.对称二叉树

# 方法一： 递归法

# 29.顺时针打印矩阵

# 解法一 模拟法

# 解法一：双指针

# 解法一：两次循环

# 解法二：快慢指针

# 解法一：头指针

# 解法二：使用递归

# 方法一：使用递归

# 解法一：使用递归

# 解法二：辅助栈

# 方法一：递归法

# 解法一模拟法