LeetCode刷题
263.丑数
链接
总体思路：通过模运算和除运算判断n的因子
264.丑数II
方法一：最小堆排序
基本数据结构 —— 堆以及堆排序（C++实现）
堆的构建， 以及堆排序的c++实现
C++解法
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> factors = {2,3,5};
unordered_set<long> seen;
priority_queue<long,vector<long>,greater<long>> heap;
seen.insert(1L);
heap.push(1L);
int ugly = 0;
for(int i=0;i<n;i++){
long cur = heap.top();
heap.pop();
ugly = (int)cur;
for(int factor:factors){
long next = cur*factor;
if(!seen.count(next)){
seen.insert(next);
heap.push(next);
}
}
}
return ugly;
}
};
知识点：
Go解法
var factors =[]int{2,3,5}
type hp struct{sort.IntSlice}
func (h *hp)Push(v interface{}) {h.IntSlice = append(h.IntSlice,v.(int))}
func (h *hp)Pop()interface{}{a:=h.IntSlice;v:=a[len(a)-1];h.IntSlice = a[:len(a)-1];return v}
func nthUglyNumber(n int) int {
h := &hp{sort.IntSlice{1}}
seen := map[int]struct{}{1:{}}
for i := 1;;i++{
x := heap.Pop(h).(int)
if i==n{
return x
}
for _,f := range factors{
next := x*f
if _,has := seen[next];!has{
heap.Push(h,next)
seen[next]=struct{}{}
}
}
}
}
知识点
方法二：动态规划
C++版
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> dp(n+1);
dp[1]=1;
int p2=1,p3=1,p5=1;
for(int i = 2;i<=n;i++){
int num2=dp[p2]*2,num3=dp[p3]*3,num5=dp[p5]*5;
dp[i] = min(min(num2,num3),num5);
if(dp[i] == num2){
p2++;
}
if(dp[i] == num3){
p3++;
}
if(dp[i] == num5){
p5++;
}
}
return dp[n];
}
};
其实就是个排序的问题
Go版本
func nthUglyNumber(n int) int {
dp := make([]int, n+1)
dp[1] = 1
p2, p3, p5 := 1, 1, 1
for i := 2; i <= n; i++ {
x2, x3, x5 := dp[p2]*2, dp[p3]*3, dp[p5]*5
dp[i] = min(min(x2, x3), x5)
if dp[i] == x2 {
p2++
}
if dp[i] == x3 {
p3++
}
if dp[i] == x5 {
p5++
}
}
return dp[n]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
313.超级丑数
C++版本
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
unordered_set<long> seen;
priority_queue<long,vector<long>,greater<long>> heap;
seen.insert(1);
heap.push(1);
int ugly=0;
for(int i=0;i<n;i++){
long curr = heap.top();
heap.pop();
ugly = (int)curr;
for(int prime:primes){
long next = curr*prime;
if(seen.insert(next).second){
heap.push(next);
}
}
}
return ugly;
}
};
Go版本
func nthSuperUglyNumber(n int, primes []int) (ugly int) {
seen := map[int]bool{1: true}
h := &hp{[]int{1}}
for i := 0; i < n; i++ {
ugly = heap.Pop(h).(int)
for _, prime := range primes {
if next := ugly * prime; !seen[next] {
seen[next] = true
heap.Push(h, next)
}
}
}
return
}
type hp struct{ sort.IntSlice }
func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() interface{} { a := h.IntSlice; v := a[len(a)-1]; h.IntSlice = a[:len(a)-1]; return v }
牛客网理论题
运维相关
Go相关
- map是Go的内置类型不需要引入其他的库即可使用。
- Go的channel常见使用方式
- Go函数返回参数中，要么都没有变量名，要么都有变量名，必须统一、
- 函数执行时，如果由于panic导致了异常，延迟函数会执行。由panic引发异常以后，程序停止执行，然后调用延迟函数（defer），就像程序正常退出一样。另外recover也是要写在延迟函数中的，如果发生异常延迟函数就不执行了，那就永远无法recover了。
Go基础系列：defer、panic和recover
go语言defer panic recover用法总结 - Golang支持反射，反射最常见的使用场景是做对象的序列化，反射最常见的使用场景是做对象的序列化（serialization，有时候也叫Marshal & Unmarshal）。例如，Go语言标准库的encoding/json、encoding/xml、encoding/gob、encoding/binary等包就大量依赖于反射功能来实现。
- import
- 只有自定义的类型才能添加相应的方法，如果想给int添加方法需要
type Interger int定义别名 - Go delete
内置函数delete只能删除map类型的键值 - channal
- 序列化通常将类型结构传入标准库或第三方包，类型结构中没有大写的变量未导出，对第三方包不可见，无法进行任何操作，依旧是默认的零值。
- Go 类型断言
- CGO是C语言和Go语言之间的桥梁，原则上无法直接支持C++的类。CGO不支持C++语法的根本原因是C++至今为止还没有一个二进制接口规范(ABI)。CGO只支持C语言中值类型的数据类型，所以我们是无法直接使用C++的引用参数等特性的。
[Go语言]cgo用法演示 - 局部变量初始化
- [go 语言系列 Beego 框架](go 语言系列 Beego 框架)
- Main函数和init函数都没有参数和返回值的定义
- 内存泄漏
- Golang包管理工具之govendor的使用
- go语言编译器会自动在以标识符、数字字面量、字母字面量、字符串字面量、特定的关键字（break、continue、fallthrough和return）、增减操作符（++和–）、或者一个右括号、右方括号和右大括号（即)、]、}）结束的非空行的末尾自动加上分号。
定义切片时，新起一行时，上一行必须是逗号或者右括号 - golang中没有隐藏的this指针
- Go语言基础：make，new, len, cap, append, delete方法
- go互斥锁Mutex
Go语言之mutex
- GoStub
