title: Go全栈面试题（6） -数据结构与算法面试题
tags: go
author: Clown95
数据结构与算法面试题
基本排序，哪些是稳定的.
- 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，
- 冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法.
简述算法的概念以及特征
算法是求解一个问题所需要的步骤所形成的解决方法，每一步包括一个或者多个操作。无论是现实生活中还是计算机中，解决同一个问题的方法可能有很多种，在这N多种算法中，肯定存在一个执行效率最快的方法，那么这个方法就是最优算法。
算法具有五个基本特征：输入、输出、有穷性、确定性和可行性。
算法的设计要求是什么？
- 正确性
对于合法输入能够得到满足的结果,算法能够处理非法处理，并得到合理结果.算法对于边界数据和压力数据都能得到满足的结果。
- 可读性
算法要方便阅读，理解和交流，只有自己能看得懂，其它人都看不懂，谈和好算法。
- 健壮性
通俗的讲,一个好的算法应该具有捕获异常/处理异常的能力。另外，对于测试人员的压力测试、边界值测试等刁难的测试手段，算法应该能够轻松的扛过去。
- 高性价比
利用最少的时间和资源得到满足要求的结果，可以通过(时间复杂度和空间复杂度来判定)。
快速排序
快速排序:
func main() {
var arr = []int{19,8,16,15,23,34,6,3,1,0,2,9,7}
quickAscendingSort(arr, 0, len(arr)-1)
fmt.Println("quickAscendingSort:",arr)
quickDescendingSort(arr, 0, len(arr)-1)
fmt.Println("quickDescendingSort:",arr)
}
//升序
func quickAscendingSort(arr []int, start, end int) {
if (start < end) {
i, j := start, end
key := arr[(start + end)/2]
for i <= j {
for arr[i] < key {
i++
}
for arr[j] > key {
j--
}
if i <= j {
arr[i], arr[j] = arr[j], arr[i]
i++
j--
}
}
if start < j {
quickAscendingSort(arr, start, j)
}
if end > i {
quickAscendingSort(arr, i, end)
}
}
}
//降序
func quickDescendingSort(arr []int, start, end int) {
if (start < end) {
i, j := start, end
key := arr[(start + end)/2]
for i <= j {
for arr[i] > key {
i++
}
for arr[j] < key {
j--
}
if i <= j {
arr[i], arr[j] = arr[j], arr[i]
i++
j--
}
}
if start < j {
quickDescendingSort(arr, start, j)
}
if end > i {
quickDescendingSort(arr, i, end)
}
}
}
冒泡排序
// BubbleSort n^2
// 冒泡排序的大错觉： 是j 和 j+1 的对比，而不是i和j的比较
func BubbleSort(nums []int) []int {
for i := 0; i < len(nums); i++ {
for j := 0; j < len(nums)-1; j++ {
if nums[j] > nums[j+1] {
nums[j+1], nums[j] = nums[j], nums[j+1]
}
}
}
return nums
}
选择排序
// SelectSort 选择排序 n^2
// SelectSort 是 min 和 j 比， min 和 i 换
// 假设i是最小的那个数，然后向后比较，一旦发现比i小的数字，则用min记录，最终将min和i交换
// j 只是用于记录sorted 和 unsorted 的界限
func SelectSort(nums []int) []int {
for i := 0; i < len(nums); i++ {
var min int = i
for j := i; j < len(nums); j++ {
if nums[min] > nums[j] {
min = j
}
}
nums[i], nums[min] = nums[min], nums[i]
}
return nums
}
归并排序
// Merge Sort n*log(n)
// MergeSort = Merge将两个array合并 + MergeSort
func MergeSort(nums []int) []int {
if len(nums) == 1 {
return nums
}
left := nums[:len(nums)/2]
right := nums[len(nums)/2:]
return merge(MergeSort(left), MergeSort(right))
}
func merge(left, right []int) []int {
var result []int
var l, r = 0, 0
for {
if left[l] < right[r] {
result = append(result, left[l])
l++
} else {
result = append(result, right[r])
r++
}
if l == len(left) {
result = append(result, right[r:]...)
return result
}
if r == len(right) {
result = append(result, left[l:]...)
return result
}
}
}
实现队列
main.go
package main
import (
"errors"
"fmt"
)
// 队列
// 面试中有可能会问到，如何用golang实现一个队列
// 要实现队列，首先要指导队列是什么？
// 表现特征：FIFO
// 含有的方法： Enqueue , Dequeue
// 下面实现一个 int 的 queue
type Queue interface {
// 将 i 添加到 队尾
Enqueue(i int)
// 返回队首的i, 如果队空，则返回error
Dequeue() (i int, err error)
}
type queue struct {
slice []int
}
func (q *queue) Enqueue(i int) {
q.slice = append(q.slice, i)
}
func (q *queue) Dequeue() (i int, err error) {
if len(q.slice) == 0 {
return 0, errors.New("no int in queue")
}
// 获取队首
i = q.slice[0]
// 删除队首
q.slice = q.slice[1:]
return
}
func (q *queue) String() string {
return fmt.Sprintf("%#v", q.slice)
}
test_main.go
package main
import (
"fmt"
"testing"
)
func Test(t *testing.T) {
q := new(queue)
q.Enqueue(1)
q.Enqueue(12)
q.Enqueue(123)
fmt.Println(q)
fmt.Println(q.Dequeue())
fmt.Println(q)
fmt.Println(q.Dequeue())
fmt.Println(q)
fmt.Println(q.Dequeue())
}
实现栈
main.go
package main
import "errors"
type Stack interface {
Push(i int)
Pop() (i int, err error)
}
type stack struct {
slice []int
}
func (s *stack) Push(i int) {
s.slice = append(s.slice, i)
}
func (s *stack) Pop() (i int, err error) {
if len(s.slice) == 0 {
return i, errors.New("no int in stack")
}
i = s.slice[len(s.slice)-1]
s.slice = s.slice[:len(s.slice)-1]
return
}
test_main.go
package main
import (
"fmt"
"testing"
)
func Test(t *testing.T) {
s := new(stack)
s.Push(1)
s.Push(12)
s.Push(123)
fmt.Println(s)
fmt.Println(s.Pop())
fmt.Println(s)
fmt.Println(s.Pop())
fmt.Println(s)
fmt.Println(s.Pop())
}
实现链表
mian.go
package linked_list
import (
"fmt"
"strings"
)
// 最常在面试中出现的数据结构
// 如何实现一个linked list
type Node struct {
Data interface{}
Next *Node
}
func NewNode(data interface{}, nextNode *Node) *Node {
return &Node{
Data: data,
Next: nextNode,
}
}
// 整理一下实现一个LinkedList，要考虑的各种特殊情况：
// 1. 新增即换头
// 2. 头很重要： 对head是否等于nil的判断，对于 删除，新增操作等
// 3. 头尾一体的特殊情况： 在删除尾巴的时候，如果头尾一体，即只有一个节点，也要当作特殊情况处理
// 3. size 方法，如果不是用遍历的方式，则对应所有的新增和删除都要添加对size的操作
// 4. 带有index都要考虑到3种情况，头，尾，中间，并且遍历的时候，要找index-1的位置，这个位置是操作位置
type LinkedList struct {
head *Node
size int
}
func NewLinkedList() *LinkedList {
return &LinkedList{}
}
func (l *LinkedList) InsertFirst(data interface{}) {
newNode := NewNode(data, nil)
if l.head != nil {
newNode.Next = l.head
}
l.head = newNode
l.size += 1
}
// InsertLast 和size一样，有两种实现方式：
// O(n) 的方式是，每次遍历到最后一个节点，然后进行新增
// O(1) 的方法是，保存一个tail的标记，但是则需要在 Insert,Remove 等多个方法中维护这个标记,就会很复杂
func (l *LinkedList) InsertLast(data interface{}) {
newNode := NewNode(data, nil)
if l.head == nil {
l.head = newNode
return
}
node := l.head
for node.Next != nil {
node = node.Next
}
node.Next = newNode
l.size += 1
}
func (l *LinkedList) GetFirst() interface{} {
// 记住要判断head是否为nil
if l.head == nil {
return nil
}
return l.head.Data
}
func (l *LinkedList) GetLast() interface{} {
node := l.head
if node == nil {
return nil
}
for node.Next != nil {
node = node.Next
}
return node.Data
}
func (l *LinkedList) Head() *Node {
return l.head
}
func (l *LinkedList) Size() int {
// 用遍历的一边的方式获取linked的大小
//size := 0
//var node *Node
//node = l.head
//for node != nil {
// size += 1
// node = node.Next
//}
return l.size
}
func (l *LinkedList) Clear() {
node := l.head
if node == nil {
return
}
for node != nil {
nextnode := node.Next
node.Next = nil
node = nextnode
}
// 将 head 设置为空（重要）,同时要将 size 设置为 0
l.head = nil
l.size = 0
}
func (l *LinkedList) RemoveFirst() {
if l.head == nil {
return
}
oldhead := l.head
l.head = oldhead.Next
oldhead.Next = nil
l.size -= 1
}
func (l *LinkedList) RemoveLast() {
defer func() {
l.size -= 1
}()
if l.head == nil {
return
}
// 只有一个节点的情况
if l.head.Next == nil {
l.head = nil
return
}
node := l.head
// 重要，不能这么写，应为当只有一个node的时候，不存在倒数第二个node
// 永远只找倒数第一，不找倒数第二
for node.Next.Next != nil {
node = node.Next
}
node.Next = nil
}
func (l *LinkedList) GetAt(index int) (data interface{}) {
if l.size == 0 || index > l.size-1 || index < 0 {
return nil
}
node := l.head
count := 0
for node.Next != nil {
if count == index {
break
}
node = node.Next
count += 1
}
return node.Data
}
func (l *LinkedList) RemoveAt(index int) {
if l.size == 0 || index > l.size-1 || index < 0 {
return
}
// 2种情况
// 1. 有一个节点
// 2. 有多个节点
defer func() {
l.size -= 1
}()
// 只有一个节点
if index == 0 && l.size == 1 {
l.RemoveFirst()
return
}
// 有多个节点
// 1. 删除头
if index == 0 {
l.RemoveFirst()
return
}
// 2. 删除尾
if index == l.size-1 {
l.RemoveLast()
return
}
// 3. 删除其他,找到index之前的那个节点
node := l.head
count := 0
for node.Next != nil {
if count == index-1 {
break
}
node = node.Next
count += 1
}
removeedNode := node.Next
node.Next = node.Next.Next
removeedNode.Next = nil
return
}
func (l *LinkedList) String() string {
var result []string
var node *Node
node = l.head
for node != nil {
result = append(result, fmt.Sprintf("%#v", node.Data))
node = node.Next
}
return strings.Join(result, " -> ")
}
mian_test.go
package linked_list
import (
"fmt"
"testing"
)
// 插入测试
func TestLinkedList_InsertFirst(t *testing.T) {
list := NewLinkedList()
list.InsertFirst(1)
fmt.Println(list, list.Size())
list.InsertFirst(2)
fmt.Println(list, list.Size())
list.InsertFirst(3)
fmt.Println(list, list.Size())
fmt.Println(list.GetFirst())
fmt.Println(list.GetLast())
list.Clear()
fmt.Println(list)
}
// 插入尾测试
func TestLinkedList_InsertLast(t *testing.T) {
list := NewLinkedList()
list.InsertLast(1)
fmt.Println(list, list.Size())
list.InsertLast(2)
fmt.Println(list, list.Size())
list.InsertLast(3)
fmt.Println(list, list.Size())
fmt.Println(list.GetFirst())
fmt.Println(list.GetLast())
list.Clear()
fmt.Println(list)
}
// 删除头测试
func TestLinkedList_RemoveFirst(t *testing.T) {
list := NewLinkedList()
list.InsertFirst(1)
fmt.Println(list, list.Size())
list.InsertFirst(2)
fmt.Println(list, list.Size())
list.InsertFirst(3)
fmt.Println(list, list.Size())
list.RemoveFirst()
fmt.Println(list, list.Size())
list.RemoveFirst()
fmt.Println(list, list.Size())
list.RemoveFirst()
}
// 删除尾测试
func TestLinkedList_RemoveLast(t *testing.T) {
list := NewLinkedList()
fmt.Println(list, list.Size())
list.InsertFirst(1)
fmt.Println(list, list.Size())
list.InsertFirst(2)
fmt.Println(list, list.Size())
list.InsertFirst(3)
fmt.Println(list, list.Size())
list.RemoveLast()
fmt.Println(list, list.Size())
list.RemoveLast()
fmt.Println(list, list.Size())
list.RemoveLast()
fmt.Println(list, list.Size())
}
// 获取第X个的测试
func TestLinkedList_GetAt(t *testing.T) {
list := NewLinkedList()
list.InsertFirst(1)
list.InsertFirst(2)
list.InsertFirst(3)
fmt.Println(list.GetAt(0))
fmt.Println(list.GetAt(1))
fmt.Println(list.GetAt(2))
fmt.Println(list, list.Size())
}
// 删除第X个的测试
func TestLinkedList_RemoveAt(t *testing.T) {
list := NewLinkedList()
list.InsertFirst(1)
list.InsertFirst(2)
list.InsertFirst(3)
fmt.Println(list, list.Size())
list.RemoveAt(1)
fmt.Println(list, list.Size())
}
字符串反转
mian.go
package main
// 遍历字符串
// golang 中没有build-in的例如js中的 reverse()的方法对数组进行反转，所以得手写一个反转数组的方法
// 为什么这里使用了 rune ,而不是 byte ?
// byte 是 8bit
// rune 是 32bit
// 在utf-8编码中，对于 中文字符 而言，一个字符占 3个字节, 使用 byte 是放不下的
// 常见的 range 也是对str进行了隐式的 unicode 解码, 而 str[i] 并不一定和我们看到的字符串对应
// 同理，如果只是序列化和反序列化，可以通过byte进行操作，但是如果涉及字符串中的反转，截断等操作，则使用rune
func reverse02(str string) string {
runes := []rune(str)
for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
runes[i], runes[j] = runes[j], runes[i]
}
return string(runes)
}
// 使用byte进行反转字符串的话，仅会对字母和数字有效，一旦加入中文字符串，结果就无法满足预期了
func reverseByByte(str string) string {
bs := []byte(str)
for i, j := 0, len(str)-1; i < j; i, j = i+1, j-1 {
bs[i], bs[j] = bs[j], bs[i]
}
return string(bs)
}
mian_test.go
package main
import "testing"
func Test(t *testing.T) {
testcases := []struct {
str1 string
str2 string
}{
{"cda54321", "12345adc"},
{"hello 世界", "界世 olleh"},
}
getResult := func(do func(str1 string) string) {
for _, testcase := range testcases {
if testcase.str2 != do(testcase.str1) {
t.Error("except", testcase.str2, "get", do(testcase.str1))
}
}
}
getResult(reverse02)
getResult(reverseByByte)
}
如何通过递归反转单链表?
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。
package main
import "fmt"
// 通过递归反转单链表
type Node struct {
Value int
NextNode *Node
}
func Param(node *Node){
for node !=nil{
fmt.Print(node.Value,"--->")
node = node.NextNode
}
fmt.Println()
}
func reverse(headNode *Node) *Node{
if headNode ==nil {
return headNode
}
if headNode.NextNode == nil{
return headNode
}
var newNode = reverse(headNode.NextNode)
headNode.NextNode.NextNode = headNode
headNode.NextNode = nil
return newNode
}
func main() {
var node1 = &Node{}
node1.Value = 1
node2 := new(Node)
node2.Value = 2
node3 := new(Node)
node3.Value = 3
node4 := new(Node)
node4.Value = 4
node1.NextNode = node2
node2.NextNode = node3
node3.NextNode = node4
Param(node1)
reverseNode := reverse(node1)
Param(reverseNode)
运行:
1--->2--->3--->4--->
4--->3--->2--->1--->
输出金字塔
main.go
package _0_pyramid
import "fmt"
// 和上一个阶梯类似，输出金字塔型的#
// 例如输出3
// " # "
// " ### "
// "#####"
// 首当其冲就是递归
// 用递归，每一层和每一层之间的关系非常清晰
// 比迭代要简单的多
func pyamid(n int) {
// 最底层的#数
printPy(n*2-1, 0)
}
// i = # 数量
// j = 每边的<space>数量
func printPy(i, j int) {
if i <= 0 {
return
}
printPy(i-2, j+1) // 每天上一层，#数量减少2，空格数量每边加1
for index := 0; index < j; index++ {
fmt.Print(" ")
}
for index := 0; index < i; index++ {
fmt.Print("#")
}
for index := 0; index < j; index++ {
fmt.Print(" ")
}
fmt.Println("")
}
main_test.go
package _0_pyramid
import "testing"
func Test(t *testing.T) {
testcases := []struct {
num int
}{
{2},
{3},
{5},
}
getResult := func(do func(int)) {
for _, testcase := range testcases {
do(testcase.num)
}
}
getResult(pyamid)
}
两个数组求交集
思路：把两个数组合并成一个数组，然后通过 hash 表找出数组中重复的元素
package main
import "fmt"
func ArrayIntersection(arr []int, arr1 []int) []int {
var intersection []int
arr = append(arr, arr1...)
sameElem := make(map[int]int)
for _, v := range arr {
if _, ok := sameElem[v]; ok {
intersection = append(intersection, v)
} else {
sameElem[v] = 1
}
}
return intersection
}
func main() {
arr1 := []int{1, 2, 3, 4, 5, 6}
arr2 := []int{5, 6, 7, 8, 9, 0}
fmt.Println(ArrayIntersection(arr1, arr2))
}
寻找最长含有不重复字符的字串长度大小
package main
import "fmt"
func lengthOfNonRepeatingSubStr(s string) int {
lastOccurred := make(map[rune]int)
start := 0
maxLength := 0
for i, ch := range []rune(s) {
if lastI, ok := lastOccurred[ch]; ok && lastI >= start {
start = lastOccurred[ch] + 1
}
if i-start+1 > maxLength {
maxLength = i - start + 1
}
lastOccurred[ch] = i
}
return maxLength
}
func main() {
fmt.Println(lengthOfNonRepeatingSubStr("hello 世界!"))
}
链表反转
type Node struct {
value int
next *Node
}
func reverse(head *Node) *Node {
var pre *Node = nil
for head != nil {
temp := head.next
head.next = pre
pre = head
head = temp
}
return pre
}
func printNode(head *Node) {
for head != nil {
fmt.Println(head.value)
head = head.next
}
}
大整数加法
func stringReverse(str string) string {
reverse := []rune(str)
strLen := len(str)
for i, j := 0, strLen-1; i < j; i, j = i+1, j-1 {
reverse[i], reverse[j] = reverse[j], reverse[i]
}
return string(reverse)
}
func add(str1 string, str2 string) string {
if len(str1) < len(str2) {
str1 = strings.Repeat("0", len(str2)-len(str1)) + str1
} else if len(str1) > len(str2) {
str2 = strings.Repeat("0", len(str1)-len(str2)) + str2
}
str1 = stringReverse(str1)
str2 = stringReverse(str2)
count := len(str1)
nums := make([]byte, count)
carry := false
for i := 0; i < count; i++ {
sum := str1[i] - '0' + str2[i] - '0'
if carry {
sum++
}
if sum > 9 {
sum = sum - 10
carry = true
} else {
carry = false
}
nums[i] = sum + '0'
}
result := stringReverse(string(nums))
if carry {
result = "1" + result
}
return result
}
查找不重复最长字串
package main
import "fmt"
func lengthOfNonRepeatingSubStr(s string) int {
lastOccurred := make(map[rune]int)
start := 0
maxLength := 0
for i, ch := range []rune(s) {
if lastI, ok := lastOccurred[ch]; ok && lastI >= start {
start = lastOccurred[ch] + 1
}
if i-start+1 > maxLength {
maxLength = i - start + 1
}
lastOccurred[ch] = i
}
return maxLength
}
func main() {
fmt.Println(lengthOfNonRepeatingSubStr("abcabcbb"))
fmt.Println(lengthOfNonRepeatingSubStr("bbbbb"))
fmt.Println(lengthOfNonRepeatingSubStr("黑化肥发黑会挥发"))
}