抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

链表

  1. 一个操作可能产生新的头节点，则可以尝试在链表的最前面添加一个哨兵节点来简化代码逻辑，降低代码出现问题的可能性。
  2. 双指针是解决与链表相关的面试题的一种常用技术。前后双指针思路让一个指针提前走若干步，然后将第2个指针指向头节点，两个指针以相同的速度一起走。快慢双指针让快的指针每次走两步而慢的指针每次只走一步。
  3. 大部分与链表相关的面试题都是考查单向链表的操作。单向链表的特点是只能从前往后遍历而不能从后往前遍历。如果不得不从后往前遍历链表，则可以把链表反转之后再遍历。
  4. 如果链表中的节点除了有指向下一个节点的指针，还有指向前一个节点的指针，那么该链表就是双向链表。由于双向链表的操作牵涉到的指针比较多，因此应聘者在解决面试题的时候要格外小心，确保每个指针都指向了正确的位置。
  5. 循环链表是一种特殊形态的链表，它的所有节点都在一个环中。在解决与循环链表相关的面试题时需要特别注意避免死循环，遍历链表时等所有节点都遍历完就要停止，不能一直在里面绕圈子出不来。
算法

第一道题

ZWdEW0

前言

序列化：二叉树被记录成文件的过程叫做序列化

反序列化：通过文件内容重建原来二叉树的过程叫做反序列化

问题1

问题描述：递归的过程中，传递了一个切片作为参数，每次我们都需要对切片切取首元素，之后递归回来的时候发现切片中的元素还是没有切取首元素，是一个很严重的逻辑错误。

问题解决：我们递归函数使用切片作为参数的时候，我们直接传入切片的地址。因为切片每次删除元素，地址也会改变。当切片增加元素引起扩容，地址也会发生改变，而如果只传入切片我们只是引用最开始的时候的切片的地址，因此会发现切片没有任何改变。

例如我们自己写的二叉树序列化和反序列化代码：在最开始只是传递一个切片，但是后来传递切片的地址进去发现代码逻辑正常运行。

代码 
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//方法一：使用先序遍历进行序列化和反序列化
//进行序列化
func PreorderSerialize(root *TreeNode) string {
	if root == nil {
		return "#!"
	}

	var ret string

	ret += strconv.Itoa(root.Val) + "!"
	ret += PreorderSerialize(root.Left)
	ret += PreorderSerialize(root.Right)
	return ret
}

//进行反序列化
func PreorderDeserialize(ret string) *TreeNode {
	strs := strings.Split(ret, "!")

	//注意点：由于切片在执行过程中有可能会因为增加和删除元素而造成切片不是原来那个切片，但是我们递归回去的时候还是指向原来的切片，因此会有问题
	//所以这里我们传递的是切片的地址
	//因为切片扩容可能会生成一个新的底层数组，并且由于切片移除了元素，因此对应的头部地址一定会改变，所以会造成地址的改变
	root := ReconstructTreeFromPreorder(&strs)
	return root
}

//根据我们分割后的字符串建立二叉树
func ReconstructTreeFromPreorder(strs *[]string) *TreeNode {
	if (*strs)[0] == "#" {
		(*strs) = (*strs)[1:]
		return nil
	}

	//首先将该值对应的字符串转换为int
	val, _ := strconv.Atoi((*strs)[0])
	//建立一个针对于该值的节点
	node := &TreeNode{
		Val: val,
	}

	//去掉我们建立过的节点的值
	(*strs) = (*strs)[1:]
	//之后进行递归建立左右子树
	node.Left = ReconstructTreeFromPreorder(strs)
	node.Right = ReconstructTreeFromPreorder(strs)

	return node
}

题目描述

给定一个数组，求如果排序之后，相邻两数的最大差值，要求时 间复杂度O(N)，且要求不能用非基于比较的排序

注意不基于比较哦

思路

思路：桶排序
  1. 假设数组长度为n，准备n+1个桶
  2. 遍历该数组，将最小值放入到第1个位置，将最大值放入到最后一个位置
  3. 将剩下的数等分成等分成n-1份依次放入剩下对应范围的桶中，
  4. 最后这n+1个桶中至少有一个空桶，说明桶内的数值差不是最大差值，我们去桶间找最大差值
  5. 对于每个桶，我们都保存了每个桶的最小值和最大值，从第2个桶开始，每次计算当前桶的最小值与前一个桶(要有元素)的最大值的差，过程中我们动态更新最大差值

堆排序基本知识

基本介绍

堆是一个完全二叉树，因此我们可以利用节点的特性去使用一个数组模拟一颗完全二叉树：

  1. 下标为i的节点的左子节点的下标为i*2+1, 右子节点的下标为i*2+2
  2. 下标为i的节点的父节点的下标为(i-1)/2

建立堆的时间复杂度：O(log1) + O(log2) + … + O(logN) 近似于 O(N)，因此建立堆的时间复杂度为O(N)

堆有大根堆以及小根堆，没有规定堆中左子树的根必须大于(或小于)右子树的根。

堆排序的两个基本步骤：(具体说明看代码注释)
  1. 建堆，循环将数组中的每个数加入堆中（每次都需要heapInsert）
  2. 不断从堆的最后一个元素交换到堆的头部，然后将堆的长度减小1，再调整堆，每次都需要heapify

思路整理：

冒泡排序

思路：从左向右每次两两比较相邻元素，如果前一个元素大于后一个元素，那么就交换这两个元素，一趟下来肯定有一个元素放到了最后的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func BubbleSort(nums []int) []int {
	bubbleSort(nums)
	return nums
}

func bubbleSort(nums []int) {
	//从前往后进行交换，每次都会固定好后面的元素
	for i := 0; i < len(nums)-1; i++ {
		for j := 0; j < len(nums)-1-i; j++ {
			//两两比较并交换
			if nums[j] > nums[j+1] {
				nums[j], nums[j+1] = nums[j+1], nums[j]
			}
		}
	}
}

直接插入排序

直接插入排序是简单排序中性能最好的

平均时间复杂度：O(n^n / 4)
最好时间复杂度：O(n)
最坏时间复杂度：O(n^n)

直接插入排序版本1

思路：将每次要插入的当前元素依次与左边元素比较，如果左边元素大于当前元素则交换，直到左边元素小于等于当前元素。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package main

import (
	"log"
	"math/rand"
	"time"
)

/**
 * @Author: yirufeng
 * @Email: yirufeng@foxmail.com
 * @Date: 2020/9/10 9:12 上午
 * @Desc: 直接插入排序
 */

func InsertSort(nums []int) []int {
	insertSort(nums)
	return nums
}

//思路：如果当前元素比前一个元素小就交换，一直到当前元素大于等于前一个元素
func insertSort(nums []int) {
	//默认下标为0的已经有序，因此从下标为1的开始插入
	for i := 1; i < len(nums); i++ {
		//插入条件：要排序的元素一定要小于前面的元素
		if nums[i] < nums[i-1] {
			//什么时候结束插入：当要插入的元素的值大于等于前面的那个元素就停止插入
			for j := i; j >= 1 && nums[j] < nums[j-1]; j-- {
				nums[j], nums[j-1] = nums[j-1], nums[j]
			}
		}
	}
}


//写一个随机数生成器
func RandArray(length int) []int {
	nums := []int{}
	for i := 0; i < length; i++ {
		r := rand.New(rand.NewSource(time.Now().UnixNano()))
		nums = append(nums, r.Intn(100))
	}
	return nums
}

func main() {
	rand.Seed(time.Now().UnixNano())
	nums := RandArray(30)
	log.Println(nums)
	log.Println(InsertSort(nums))
}