算法（十一）刷题常用语法python/go

2019-07-19

本文简单介绍一些在刷题过程中常用的库或者语法，设计python和go

1. python常用数据结构

1.1 heapq库

heapq实现小顶堆。实现涉及堆排序的问题

import heapq

heap = []

# 构造小顶堆
for i in [3,4,5]:
    heapq.heappush(heap, i)

# 获取堆顶元素,heap[0]永远维护最小元素
heap[0]

# 删除堆顶元素
heapq.heappop(a)

# 讲一个普通数组转换成一个小顶堆,原地转换，时间复杂度O(len(x))
heapq.heapify(x)

1.2 collections库

collections.defaultdict()函数

举例分析

初始化a为dict，如过某个key在a中不存在，那么在调用a[key]的时候，返回0。

如过初始化为collections.defaultdict(str)，那么默认返回空字符串""
import collections
a = collections.defaultdict(int)

collections.deque提供一个双端队列

dq = collections.deque()
dq.append(10)
dq.append(11)
dq.popleft() #删除左边元素
dp.pop() #删除右边元素

1.3 python无穷大

# 正无穷大
float("inf")
# 负无穷大
float("-inf")

1.4 python lru_cache

python在做bfs或者dfs的时候，利用lru_cache来缓存中间结果，从而降低时间复杂度

# None是不限制cache大小。@lru_cache(None)的作用是如果调用bfs这个函数，当输入aaa相同时，直接返回结果

@lru_cache(None)
def bfs(aaa)
    # pass
    return bbb

1.5 python字典遍历

1
2
3

a = {"a":1, "b":2}
for k, v in a.items():
    print k, v

1.6 python集合操作

a = set([1,2,2,3])
# 添加元素
a.add(4)
# 删除元素
s.remove(2) # 如果不存在会报错
s.discard(5) #如果不存在，也不报错
#求交集
a=set([1,2,3])
b=set([3,2,2])
a & b # set([2,3])
#求并集
a|b # set([1,2,3])
# 求差集
a-b #set([1])
# 对称差集
a^b #对称差集（项在a或b中，但不会同时出现在二者中）

1.7 python数据排序

a=[4,9,100,203]
a.sort()

b = [[0,30],[5,10],[15,20]]
b.sort(key = lambda x: x[0])

2. Golang常用数据结构

2.1 Golang循环

Golang没有while函数，只有for循环

无限循环

for {
    // pass
}
或者
for true {
    // pass
}

根据某变量循环

sum := 100
for sum < 10 {
    // pass
}

固定循环数量

1
2
3

for i:=0; i <= 10 ; i ++ {
    // pass
}

字典/数组遍历

a_list := []int{1,2,3}
for _, v := range a_list{
    //pass
}

b_dict := map[string]string{
    "a": "a_v",
}
for k, v := range b_dict {
    //pass
}

2.2 Golang数组操作

初始化数组/切片

//数组
var a_list [10] int

//切片
var b_slice [] int
var b_slice = make([]int, 10)
var b_slice = make([]int)

//初始化
c := []int{1,2,3}

//多维数组

d := [][]int{}

d := [][]int{
    {1,2,3},
    {4,5,6},
}

// 初始化m*n二维矩阵
visited := make([][]int, m)
for i := 0; i < m; i++ {
    visited[i] = make([]int, n)
}

切片元素操作(插入，删除，截取，拷贝)

//插入元素
a := []int{}
append(a, 10)

//删除第2个元素
new_arr := append(a[:3], a[3:]...)

// 截取startIndex到endIndex-1之间的元素
arr[startIndex:endIndex]

//拷贝,将arr1拷贝给arr2
copy(arr1, arr2)

获取数组长度
1
len(a_list)
数组作为函数参数
1
2
3
func test(arr []int){
// pass
}
2.3 Golang dict操作

初始化字典

var a map[string]string

b := map[string]string{}

c := map[string]string{
    "a":"b",
}

删除字典元素
1
delete(a_map, a_key)

字典作为函数参数

1
2
3

func test(aDict map[string]string) {
    //pass
}

2.4 Golang字符串操作

字符串相关操作使用strings包

获取字符串长度
1
import "strings"
字符串截取
1
2
从start到end-1
s[start:end]

字符串遍历

s := "nihao"
sChar := []byte(s)
for i:=0; i < len(sChar); i++ {
    fmt.Println(string(sChar[i]))
}

字符串比较
1
strings.Compare(a, b)
字符串包含
1
strings.Contains(a, sub_a)
字符串分割
1
strings.Split(a, " ")

字符串是否含有前缀后缀

1 2	strings.HasPrefix(s, s_pre) strings.HasSuffix(s, s_suf)

字符数组合并

1 2	strings.Join([]string{"a", "b"}) 输出"ab"

字符串第一次出现的位置
1
strings.Index(s, sub_s)

字符串替换

n是替换的次数，负数表示全部替换
func Replace(s, old, new string, n int) string

strings.Replace("nihao", "ni", "li", -1)

字符串大小写转换

func ToLower(s string) string
func ToUpper(s string) string

strings.Tolower("NIHao")
strings.ToUpper("nihao")

字符操作

golang的字符（char）的类型为rune
相比于byte类型。byte是1个字节，rune是4个字节。
// byte is an alias for uint8 and is equivalent to uint8 in all ways. It is
// used, by convention, to distinguish byte values from 8-bit unsigned
// integer values.
type byte = uint8
// rune is an alias for int32 and is equivalent to int32 in all ways. It is
// used, by convention, to distinguish character values from integer values.
type rune = int32

s := "中国"
sToRune := []rune{s}
string(sTorune[:1])//输出”中“

a := []rune{} //字符数组
// 字符串遍历 s= "abc"
for _, c := range s {
    // c为rune类型
}

//字符转int
c := '1'
cToInt := int(c)
cToString := string(c)

2.5 string与int转换

// package strconv来实现互转
import strconv
//string to int
i, err := strconv.Atoi("-42")
s := strconv.Itoa(12)