编码过程中首先要校验输入数据的合法性。

写代码之前首先想好有哪些测试用例，要提高代码的测试覆盖率。

3. 数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

2 <= n <= 100000

如果使用Map，则时间复杂度为O(n), 空间复杂度为O(n)。题目中的关键信息为长度为n的数组，且所有数字都在0~n-1的范围内，所以可以不用额外开辟空间。

 1func findRepeatNumber(nums []int) int {
 2	var tmp int
 3	for i, v := range nums {
 4		if v != i {
 5			if nums[v] == v {
 6				return v
 7			}
 8			tmp = nums[v]
 9			nums[v] = v
10			nums[i] = tmp
11		}
12	}
13	return -1
14}
15
16// 时间复杂度为O(n),空间复杂读为O(1)

4. 二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

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

给定 target = 5，返回 true。

给定 target = 20，返回 false。

限制：

0 <= n <= 1000

0 <= m <= 1000

矩阵从左到右递增，从上到下递增。如果右上角看，则往左递减，往下递增，很像一棵搜索二叉树。

[思考]： 递增 or 非递减

 1func findNumberIn2DArray(matrix [][]int, target int) bool {
 2	n := len(matrix)
 3	if n == 0 {
 4		return false
 5	}
 6	m := len(matrix[0])
 7	if m == 0 {
 8		return false
 9	}
10	for j, i := m-1, 0; j >= 0 && i < n; {
11		tmp := matrix[i][j]
12		if tmp == target {
13			return true
14		} else if tmp > target {
15			j--
16		} else {
17			i++
18		}
19	}
20	return false
21}
22
23// 时间复杂度为O(m+n)，空间复杂度为O(1)

5. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例 1：

1输入：s = "We are happy."
2输出："We%20are%20happy."

限制：

0 <= s 的长度 <= 10000

  • 直接使用内置函数
1func replaceSpace(s string) string {
2    return strings.ReplaceAll(s," ","%20")
3}
  • 使用bytes.Buffer
 1func replaceSpace(s string) string {
 2	l := len(s)
 3	newStr := bytes.Buffer{}
 4	for i := 0; i < l; i++ {
 5		v := s[i]
 6		if v == ' ' {
 7			newStr.WriteString("%20")
 8			continue                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   
 9		}
10		newStr.WriteByte(v)
11	}
12	return newStr.String()
13}

6. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

1输入：head = [1,3,2]
2输出：[2,3,1]

限制：

0 <= 链表长度 <= 10000

  • 使用栈, 先入后出
 1func reversePrint(head *ListNode) []int {
 2   res := make([]int, 0)
 3   for head != nil {
 4      res = append(res, head.Val)
 5      head = head.Next
 6   }
 7   for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
 8      res[i],res[j] = res[j], res[i]
 9   }
10   return res
11}
  • 链表反转

7. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

1前序遍历 preorder = [3,9,20,15,7]
2中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

1   3
2  /  \
3 9    20
4/      \
515       7

限制：

0 <= 节点个数 <= 5000

 1//* Definition for a binary tree node.
 2type TreeNode struct {
 3	Val   int
 4	Left  *TreeNode
 5	Right *TreeNode
 6}
 7
 8func buildTree(preorder []int, inorder []int) *TreeNode {
 9
10	if len(preorder) == 0 {
11		return nil
12	}
13
14	if len(preorder) == 1 {
15		return &TreeNode{
16			Val:   preorder[0],
17			Left:  nil,
18			Right: nil,
19		}
20	}
21
22	val := preorder[0] // root val
23	index := 0         // inorder root index
24	for i, v := range inorder {
25		if val == v {
26			index = i
27			break
28		}
29	}
30	root := TreeNode{
31		Val:   val,
32		Left:  buildTree(preorder[1:index+1], inorder[0:index]),
33		Right: buildTree(preorder[index+1:], inorder[index+1:]),
34	}
35	return &root
36}

9. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

输入：

1["CQueue","appendTail","deleteHead","deleteHead"]
2[[],[3],[],[]]
3输出：[null,null,3,-1]

示例 2：

输入：

1["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
2[[],[],[5],[2],[],[]]
3输出：[null,-1,null,null,5,2]

提示：

11 <= values <= 10000
2最多会对 appendTail、deleteHead 进行 10000 次调用

使用 List的Double List作为Stack

 1type CQueue struct{
 2    stack1, stack2 *list.List
 3}
 4
 5func Constructor() CQueue{
 6    return CQueue{
 7        list.New(),
 8        list.New(),
 9    }
10}
11
12func (q *CQueue) AppendTail(value int){
13    q.stack1.PushBack(value)
14}
15
16func (q *CQueue) DeleteHead() int{
17    if q.stack2.Len() == 0{
18        for this.stack1.Len() > 0{
19            this.stack2.PushBack(this.stack1.Remove(this.stack1.Back()))
20        }
21    }
22}

自定义Stack

 1type CQueue struct{
 2    stack1, stack2 Stack
 3}
 4
 5func Constructor() CQueue{
 6    return CQueue{
 7        Stack{},
 8        Stack{},
 9    }
10}
11
12func (q *CQueue) AppendTail(value int){
13    q.stack1.Push(value)
14}
15
16func (q *CQueue) DeleteHead() int{
17    if q.stack2.Len== 0{
18        for q.stack1.Len > 0 {
19            q.stack2.Push(q.stack1.Pop())
20        }
21    }
22    if q.stack2.Len != 0{
23        return q.stack2.Pop()
24    }
25    return -1
26}
27
28
29type Stack struct {
30    Values []int
31    Len int
32}
33
34func(s *Stack) Push(value int){
35    if len(s.Values) < (s.Len+1){
36        s.Values = append(s.Values,0)
37    }
38    s.Values[s.Len] =  value
39    s.Len++   
40}
41
42func(s *Stack) Pop()int{
43    e := s.Values[s.Len-1]
44    s.Len--
45    return e
46}

53. 在排序数组中查找数字

59. 滑动窗口的最大值

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

 1输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
 2输出: [3,3,5,5,6,7] 
 3解释: 
 4
 5  滑动窗口的位置                最大值
 6---------------               -----
 7[1  3  -1] -3  5  3  6  7       3
 8 1 [3  -1  -3] 5  3  6  7       3
 9 1  3 [-1  -3  5] 3  6  7       5
10 1  3  -1 [-3  5  3] 6  7       5
11 1  3  -1  -3 [5  3  6] 7       6
12 1  3  -1  -3  5 [3  6  7]      7

提示：

你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

 1package main
 2
 3import (
 4	"container/heap"
 5	"sort"
 6)
 7
 8var a []int
 9
10type hp struct{ sort.IntSlice }
11
12func (h hp) Less(i, j int) bool  { return a[h.IntSlice[i]] > a[h.IntSlice[j]] }
13func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
14func (h *hp) Pop() interface{}   { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }
15
16func maxSlidingWindow(nums []int, k int) []int {
17	a = nums
18	q := &hp{make([]int, k)}
19	for i := 0; i < k; i++ {
20		q.IntSlice[i] = i
21	}
22	heap.Init(q)
23
24	n := len(nums)
25	ans := make([]int, 1, n-k+1)
26	ans[0] = nums[q.IntSlice[0]]
27	for i := k; i < n; i++ {
28		heap.Push(q, i)
29		for q.IntSlice[0] <= i-k {
30			heap.Pop(q)
31		}
32		ans = append(ans, nums[q.IntSlice[0]])
33	}
34	return ans
35}
36
37func main() {
38	maxSlidingWindow([]int{1, 3, 9, -3, 5, 3, 6, 7}, 3)
39}