2020-11-08

Go-make和new关键字的区别和实现原理

一、简介

make 和 new都用来初始化一个结构，make 关键字的主要作用是初始化内置的数据结构，也就是我们在前面提到的数组、切片和 Channel，而当我们想要获取指向某个类型的指针时可以使用 new 关键字

二、区别

make在Go语言中用来初始化语言的基本类型

func main() {
	slice := make([]int, 0, 100)
	myMap := make(map[string]int, 10)
	ch := make(chan int, 5)
}

new 的作用其实只是接收一个类型作为参数然后返回一个指向这个类型的指针

1
2
3

i := new(int)
var v int
i := &v

所以：make 用于创建切片、哈希表和管道等内置数据结构，new 用于分配并创建一个指向对应类型的指针。

三、原理

make

在编译期间的类型检查阶段，Go语言其实就将代表 make 关键字的 OMAKE 节点根据参数类型的不同转换成了 OMAKESLICE、OMAKEMAP 和 OMAKECHAN 三种不同类型的节点，这些节点最终也会调用不同的运行时函数来初始化数据结构。

new

内置函数 new 会在编译期间的 SSA 代码生成阶段经过 callnew 函数的处理，如果请求创建的类型大小是 0，那么就会返回一个表示空指针的 zerobase 变量，在遇到其他情况时会将关键字转换成 newobject：

func callnew(t *types.Type) *Node {
    if t.NotInHeap() {
        yyerror("%v is go:notinheap; heap allocation disallowed", t)
    }
    dowidth(t)
 
    if t.Size() == 0 {
        z := newname(Runtimepkg.Lookup("zerobase"))
        z.SetClass(PEXTERN)
        z.Type = t
        return typecheck(nod(OADDR, z, nil), ctxExpr)
    }
 
    fn := syslook("newobject")
    fn = substArgTypes(fn, t)
    v := mkcall1(fn, types.NewPtr(t), nil, typename(t))
    v.SetNonNil(true)
    return v
}

需要提到的是，哪怕当前变量是使用 var 进行初始化，在这一阶段也可能会被转换成 newobject 的函数调用并在堆上申请内存：

func walkstmt(n *Node) *Node {
    switch n.Op {
    case ODCL:
        v := n.Left
        if v.Class() == PAUTOHEAP {
            if prealloc[v] == nil {
                prealloc[v] = callnew(v.Type)
            }
            nn := nod(OAS, v.Name.Param.Heapaddr, prealloc[v])
            nn.SetColas(true)
            nn = typecheck(nn, ctxStmt)
            return walkstmt(nn)
        }
    case ONEW:
        if n.Esc == EscNone {
            r := temp(n.Type.Elem())
            r = nod(OAS, r, nil)
            r = typecheck(r, ctxStmt)
            init.Append(r)
            r = nod(OADDR, r.Left, nil)
            r = typecheck(r, ctxExpr)
            n = r
        } else {
            n = callnew(n.Type.Elem())
        }
    }
}

当然这也不是绝对的，如果当前声明的变量或者参数不需要在当前作用域外生存，那么其实就不会被初始化在堆上，而是会初始化在当前函数的栈中并随着函数调用的结束而被销毁。

newobject 函数的工作就是获取传入类型的大小并调用 mallocgc 在堆上申请一片大小合适的内存空间并返回指向这片内存空间的指针：

1
2
3

func newobject(typ *_type) unsafe.Pointer {
    return mallocgc(typ.size, typ, true)
}

四、总结

简单总结一下Go语言中 make 和 new 关键字的实现原理，make 关键字的主要作用是创建切片、哈希表和 Channel 等内置的数据结构，而 new 的主要作用是为类型申请一片内存空间，并返回指向这片内存的指针

参考：https://blog.csdn.net/qq_32252917/article/details/102953438

2020-11-06

并发编程（go）

Sync(Go语言中的同步手段)

1.sync.WaitGroup

Go语言中可以使用sync.WaitGroup来实现并发任务的同步。

sync.WaitGroup内部维护着一个计数器，计数器的值可以增加和减少。例如当我们启动了N 个并发任务时，就将计数器值增加N。每个任务完成时通过调用Done()方法将计数器减1。通过调用Wait()来等待并发任务执行完，当计数器值为0时，表示所有并发任务已经完成

 sync.WaitGroup有以下几个方法：

方法名	功能
(wg * WaitGroup) Add(delta int)	计数器+delta
(wg *WaitGroup) Done()	计数器-1
(wg *WaitGroup) Wait()	阻塞直到计数器变为0

package main

import (
	"fmt"
	"sync"
)

var wg sync.WaitGroup

func hello()  {
	defer wg.Done()
	fmt.Println("hello Goroutine!")
}

func main() {
	wg.Add(1)
	go hello()
	fmt.Println("main gorountine done")
	wg.Wait()
}

2.sync.Once

确保某些操作在高并发的场景下只执行一次,sunc.Once是一个针对值执行一次场景的解决方案

整个程序，只会执行printNum()方法一次,print()方法是不会被执行的。

package main

import (
	"fmt"
	"sync"
	"time"
)

var once sync.Once

func main() {
	for i, v :=range make([]string, 10) {
		once.Do(printNum)
		fmt.Println("count:",v,"---",i)
	}

	for i := 0; i < 10; i++ {
		go func() {
			once.Do(print)
			fmt.Println("hello")
		}()
	}

	time.Sleep(4000)
}

func printNum()  {
	fmt.Println("123456")
}

func print()  {
	fmt.Println("abcdefg")
}

3.sync.Map

Go语言中内置的map不是并发安全的,有些场景下就需要为map加锁来保证并发的安全性了，Go语言的sync包中提供了一个开箱即用的并发安全版map–sync.Map。开箱即用表示不用像内置的map一样使用make函数初始化就能直接使用。同时sync.Map内置了诸如Store、Load、LoadOrStore、Delete、Range等操作方法

2020-11-04

并发编程（go）

Goroutine

一、Goroutine简介

在java/c++中我们要实现并发编程的时候，我们通常需要自己维护一个线程池，并且需要自己去包装一个又一个的任务，同时需要自己去调度线程执行任务并维护上下文切换，这一切通常会耗费程序员大量的心智。那么能不能有一种机制，程序员只需要定义很多个任务，让系统去帮助我们把这些任务分配到CPU上实现并发执行呢？

Go语言中的goroutine就是这样一种机制，goroutine的概念类似于线程，但 goroutine是由Go的运行时（runtime）调度和管理的。Go程序会智能地将 goroutine 中的任务合理地分配给每个CPU。Go语言之所以被称为现代化的编程语言，就是因为它在语言层面已经内置了调度和上下文切换的机制。

在Go语言编程中你不需要去自己写进程、线程、协程，你的技能包里只有一个技能–goroutine，当你需要让某个任务并发执行的时候，你只需要把这个任务包装成一个函数，开启一个goroutine去执行这个函数就可以了，就是这么简单粗暴。

二、Goroutine使用

Go语言中使用goroutine非常简单，只需要在调用函数的时候在前面加上go关键字，就可以为一个函数创建一个goroutine。

一个goroutine必定对应一个函数，可以创建多个goroutine去执行相同的函数。

package main

import (
	"fmt"
	"time"
)

func hello(s string)  {
	fmt.Println("hello", s)
}

func main() {
	go hello("a")
	go hello("b")
	go hello("c")
	time.Sleep(time.Second)
}

三、goroutine与线程

OS线程（操作系统线程）一般都有固定的栈内存（通常为2MB）,一个goroutine的栈在其生命周期开始时只有很小的栈（典型情况下2KB），goroutine的栈不是固定的，他可以按需增大和缩小，goroutine的栈大小限制可以达到1GB，虽然极少会用到这个大。所以在Go语言中一次创建十万左右的goroutine也是可以的。

goroutine调度细节——GPM模型

GPM是Go语言运行时（runtime）层面的实现，是go语言自己实现的一套调度系统。区别于操作系统调度OS线程。

1.G很好理解，就是个goroutine的，里面除了存放本goroutine信息外还有与所在P的绑定等信息。
2.P管理着一组goroutine队列，P里面会存储当前goroutine运行的上下文环境（函数指针，堆栈地址及地址边界），P会对自己管理的goroutine队列做一些调度（比如把占用CPU时间较长的goroutine暂停、运行后续的goroutine等等）当自己的队列消费完了就去全局队列里取，如果全局队列里也消费完了会去其他P的队列里抢任务。
3.M（machine）是Go运行时（runtime）对操作系统内核线程的虚拟， M与内核线程一般是一一映射的关系，一个groutine最终是要放到M上执行的；

P与M一般也是一一对应的。他们关系是： P管理着一组G挂载在M上运行。当一个G长久阻塞在一个M上时，runtime会新建一个M，阻塞G所在的P会把其他的G 挂载在新建的M上。当旧的G阻塞完成或者认为其已经死掉时回收旧的M。

P的个数是通过runtime.GOMAXPROCS设定（最大256），Go1.5版本之后默认为物理线程数。在并发量大的时候会增加一些P和M，但不会太多，切换太频繁的话得不偿失。

单从线程调度讲，Go语言相比起其他语言的优势在于OS线程是由OS内核来调度的，goroutine则是由Go运行时（runtime）自己的调度器调度的，这个调度器使用一个称为m:n调度的技术（复用/调度m个goroutine到n个OS线程）。其一大特点是goroutine的调度是在用户态下完成的，不涉及内核态与用户态之间的频繁切换，包括内存的分配与释放，都是在用户态维护着一块大的内存池，不直接调用系统的malloc函数（除非内存池需要改变），成本比调度OS线程低很多。另一方面充分利用了多核的硬件资源，近似的把若干goroutine均分在物理线程上，再加上本身goroutine的超轻量，以上种种保证了go调度方面的性能。

四、Goroutine(协程)的理解

先了解一下进程线程协程的定义：

进程：拥有自己独立的堆和栈，既不共享堆，亦不共享栈，进程由操作系统调度。
线程：拥有自己独立的栈和共享的堆，共享堆，不共享栈，线程亦由操作系统调度。
协程 :和线程一样共享堆，不共享栈，协程由程序员在协程的代码里显示调度。

在操作系统的OS Thread和编程语言的User Thread之间，实际上存在3种线程对应模型，也就是：1:1，1:N，M:N。

1:1：一个用户线程就只在一个内核线程上跑，这时可以利用多核，但是上下文切换很慢，切换效率很低。
N:1：多个（N）用户线程始终在一个内核线程上跑，context上下文切换很快，但是无法真正的利用多核。
M:N：多个goroutine在多个内核线程上跑，这个可以集齐上面两者的优势,既能快速切换上下文，也能利用多核的优势，而Go正是选择这种实现方式。

Java中的线程属于1：1，Goroutine属于M:N

简单将 goroutine归纳为协程并不合适。运行时会创建多个线程来执行并发任务,且任务单元可被调度到其他线程并行执行。这更像是多线程和协程的综合体,能最大限度提升执行效率,发挥多核处理能力。

五、总结

相比于线程，goroutine并不会更快，它只是增加了更多的并发性。当一goroutine被阻塞（比如等待IO）,golang的调度器会调度其它可以执行的goroutine运行。与线程相比，它有以下几个优点：

优点：

内存消耗更少：Goroutine所需要的内存通常只有2kb，而线程则需要1Mb
创建与销毁的开销更小:由于线程创建时需要向操作系统申请资源，并且在销毁时将资源归还，因此它的创建和销毁的开销比较大。相比之下，goroutine的创建和销毁是由go语言在运行时自己管理的，因此开销更低。
切换开销更小线程的调度方式是抢占式的，如果一个线程的执行时间超过了分配给它的时间片，就会被其它可执行的线程抢占;而goroutine的调度是协同式的，它不会直接地与操作系统内核打交道。

缺点：

协程调度机制无法实现公平调度：因为协程的调度是非入侵式的，系统不会为他分配资源。

2020-11-01

Gin框架

Gin数据库操作

一、连接数据库

准备好数据库，表，同时与Gin建立连接

//初始化数据库连接
func InitDatabase() (*sql.DB, error) {
	//将数据转换成数据库url作为返回值
	url := strings.Join([]string{"root", ":", "123456", "@tcp(", "127.0.0.1", ":", "3306", ")/", "gomysql"}, "")
	db, err := sql.Open("mysql", url)
	if err != nil {
		log.Printf("open database error:%v", err)
		return nil, err
		}
	return db, nil
}

新建一个全局变量sql.DB方便我们后期调用，然后通过 sql.Open对数据进行连接

二、增删改

往数据库中增删改

//用于增删改
 //执行增、改、删任务
 func Execute(db *sql.DB, sql string, params ...interface{}) error {
	stmt, _ := db.Prepare(sql) //预编译
	defer stmt.Close()
	_, err := stmt.Exec(params...)
	if err != nil {
		log.Printf("execute sql error:%v\n", err)
		return err
		}
	log.Println("execute sql success")
	return nil
 }

三、查询

//查询数据库数据
func QueryData(db *sql.DB, sql string, params ...interface{}) (*sql.Rows, error) {
	stmt, _ := db.Prepare(sql)
	defer stmt.Close()
	rows, err := stmt.Query(params...)
	if err != nil {
		log.Printf("query data error:%v", err)
		return nil, err
		}
	log.Println("query data success")
	return rows, nil
}

四、总结

package main

import (
	"database/sql"
	_ "github.com/go-sql-driver/mysql"
	"log"
	"strings"
)

type Student struct {
	id int
	name string
	age int
}

func main() {
	db, err := InitDatabase()
	defer db.Close()
	if err != nil {
		log.Println(err)
		return
	}

	//增加
	insert := "insert into person (name, age) values (?,?)"
	err = Execute(db, insert, "xiaoming", 23)
	if err != nil {
		log.Println("insert data error : %v\n", err)
		return
	}

	querySql := "select * from person"
	data, err := QueryData(db,querySql)
	defer data.Close()
	if err != nil {
		log.Printf("query data error:%v\n", err)
		return
	}
	s := new(Student)
	for data.Next() {
		data.Scan(&s.id, &s.name, &s.age)
		log.Println(*s)
	}
}


//初始化数据库连接
func InitDatabase() (*sql.DB, error) {
	//将数据转换成数据库url作为返回值
	url := strings.Join([]string{"root", ":", "123456", "@tcp(", "127.0.0.1", ":", "3306", ")/", "gomysql"}, "")
	db, err := sql.Open("mysql", url)
	if err != nil {
		log.Printf("open database error:%v", err)
		return nil, err
		}
	return db, nil
}

//用于增删改
 //执行增、改、删任务
 func Execute(db *sql.DB, sql string, params ...interface{}) error {
	stmt, _ := db.Prepare(sql) //预编译
	defer stmt.Close()
	_, err := stmt.Exec(params...)
	if err != nil {
		log.Printf("execute sql error:%v\n", err)
		return err
		}
	log.Println("execute sql success")
	return nil
 }

//查询数据库数据
func QueryData(db *sql.DB, sql string, params ...interface{}) (*sql.Rows, error) {
	stmt, _ := db.Prepare(sql)
	defer stmt.Close()
	rows, err := stmt.Query(params...)
	if err != nil {
		log.Printf("query data error:%v", err)
		return nil, err
		}
	log.Println("query data success")
	return rows, nil
}

2020-11-01

Gin框架

Gin框架入门

一、Gin简介

Gin 是使用 Go/golang 语言实现的 HTTP Web 框架。接口简洁，性能极高，框架源码仅5K

二、Gin 特性

快速：路由不使用反射，基于Radix树，内存占用少。
中间件：HTTP请求，可先经过一系列中间件处理，例如：Logger，Authorization，GZIP等。这个特性和 NodeJs 的 Koa 框架很像。中间件机制也极大地提高了框架的可扩展性。
异常处理：服务始终可用，不会宕机。Gin 可以捕获 panic，并恢复。而且有极为便利的机制处理HTTP请求过程中发生的错误。
JSON：Gin可以解析并验证请求的JSON。这个特性对Restful API的开发尤其有用。
路由分组：例如将需要授权和不需要授权的API分组，不同版本的API分组。而且分组可嵌套，且性能不受影响。
渲染内置：原生支持JSON，XML和HTML的渲染。

package main

import (
	"github.com/gin-gonic/gin"
	"net/http"
)

func main() {
	r := gin.Default()
	r.GET("/", func(c *gin.Context) {
		c.String(http.StatusOK, "hello, world")
	})
    r.Run(":8000")
}

首先，我们使用了gin.Default()生成了一个实例，这个实例即 WSGI 应用程序。
接下来，我们使用r.Get("/", ...)声明了一个路由，告诉 Gin 什么样的URL 能触发传入的函数，这个函数返回我们想要显示在用户浏览器中的信息。
最后用 r.Run()函数来让应用运行在本地服务器上，默认监听端口是 _8080_，可以传入参数设置端口，例如r.Run(":8000")即运行在8000端口。

三、路由（Route）

1. 路由方法有 GET, POST, PUT, PATCH, DELETE 和 OPTIONS，还有Any，可匹配以上任意类型的请求。

2.解析路径参数；动态的路由，如 /user/:name，通过调用不同的 url 来传入不同的 name。/user/:name/*role，* 代表可选

package main

import (
	"github.com/gin-gonic/gin"
	"net/http"
)

func main() {
	r := gin.Default()
	r.GET("/user/:name", func(c *gin.Context) {
		name := c.Param("name")
		c.String(http.StatusOK, "hello,%s", name)
	})
	r.Run(":8000")
}

3.获取Query参数

package main

import (
	"github.com/gin-gonic/gin"
	"net/http"
)

// 匹配users?name=xxx
func main() {
	r := gin.Default()
	r.GET("/user", func(c *gin.Context) {
		name := c.Query("name")
		c.String(http.StatusOK, "hello, %s", name)
	})
	r.Run(":8000")
}

4.获取POST参数

package main

import (
	"github.com/gin-gonic/gin"
	"net/http"
)

func main() {
	r := gin.Default()
	r.POST("/form", func(c *gin.Context) {
		username := c.PostForm("username")
		password := c.DefaultPostForm("password", "000000") // 可设置默认值

		c.JSON(http.StatusOK, gin.H{
			"username": username,
			"password": password,
		})
	})
	r.Run(":8000")
}

四、HTML模板

package main

import (
    "github.com/gin-gonic/gin"
    "net/http"
)

func main()  {
    r := gin.Default()
    // 指明html加载文件目录
    r.LoadHTMLGlob("./html/*")
    r.Handle("GET", "/", func(c *gin.Context) {
        // 返回HTML文件，响应状态码200，html文件名为index.html，模板参数为nil
        c.HTML(http.StatusOK, "index.html", nil)
    })
    r.Run()
}

2020-11-01

算法

剑指offer 56-67

56.删除链表中重复的结点

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

public class Solution {
    public ListNode deleteDuplication(ListNode head)
    {
        ListNode res=new ListNode(0);
        res.next=head;
        ListNode pre=res;
        ListNode cur=head;
        while(cur!=null){
            if(cur.next!=null&&cur.val==cur.next.val){
                while(cur.next!=null&&cur.val==cur.next.val){
                    cur=cur.next;
                }
                cur=cur.next;
                pre.next=cur;
            }else{
                pre=pre.next;
                cur=cur.next;
            }
        }
        return res.next;
    }
}

57.二叉树的下一个结点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode root)
    {
        if(root==null){
            return root;
        }
        if(root.right!=null){
            root=root.right;
            while(root.left!=null){
                root=root.left;
            }
            return root;
        }
        if(root.next!=null&&root.next.left==root){
            return root.next;
        }
        while(root.next!=null&&root.next.right==root){
            root=root.next;
        }
        return root.next;
    }
}

58.对称的二叉树

public class Solution {
    boolean isSymmetrical(TreeNode root)
    {
        if(root==null){
            return true;
        }
        return help(root.left,root.right);
    }
     
    private boolean help(TreeNode p,TreeNode q){
        if(p==null&&q==null){
            return true;
        }
        if(p==null||q==null){
            return false;
        }
        if(p.val!=q.val){
            return false;
        }
        return help(p.left,q.right)&&help(p.right,q.left);
    }
}

59.按之字形顺序打印二叉树

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode root) {
         ArrayList<ArrayList<Integer> > res=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if(root==null){
            return res;
        }
        int index=0;
        queue.add(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            ArrayList<Integer> list=new ArrayList<>();
            for(int i=0;i<size;i++){
                TreeNode node=queue.poll();
                if(index%2==0){
                    list.add(node.val);
                }else{
                    list.add(0,node.val);
                }
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
            index++;
            res.add(new ArrayList<>(list));
        }
        return res;
    }
 
}

60.把二叉树打印成多行

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode root) {
        ArrayList<ArrayList<Integer> > res=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if(root==null){
            return res;
        }
        queue.add(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            ArrayList<Integer> list=new ArrayList<>();
            for(int i=0;i<size;i++){
                TreeNode node=queue.poll();
                list.add(node.val);
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
            res.add(new ArrayList<>(list));
        }
        return res;
    }
     
}

61.序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#），以！表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，我们可以把一个只有根节点为1的二叉树序列化为”1,”，然后通过自己的函数来解析回这个二叉树

public class Solution {
    String Serialize(TreeNode root) {
        String res = "";
        if(root==null){
            return "#!";
        }
        res+=root.val+"!";
        res+=Serialize(root.left);
        res+=Serialize(root.right);
        return res;
  }
    TreeNode Deserialize(String str) {
       if(str == null || str.length()==0){
           return null;
       }
        Queue<String> queue = new LinkedList<>();
        String[] s= str.split("!");
        for(int i=0;i<s.length;i++){
            queue.add(s[i]);
        }
        return Deserialize(queue);
  }
     
    private TreeNode Deserialize(Queue<String> queue){
        if(queue.isEmpty()){
            return null;
        }
        String s=queue.poll();
        if(s.equals("#")){
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(s));
        root.left=Deserialize(queue);
        root.right=Deserialize(queue);
        return root;
    }
}

62.二叉搜索树的第k个结点

给定一棵二叉搜索树，请找出其中的第k小的结点。

public class Solution {
    TreeNode KthNode(TreeNode root, int k)
    {
        //中序遍历
        if(root==null) {
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        while(!stack.isEmpty()||root!=null) {
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            if(--k==0){
                return root;
            }
            root=root.right;
        }
        return null;
    }
}

63.数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

public class Solution {
 
    PriorityQueue<Integer> minqueue = new PriorityQueue<>();
    PriorityQueue<Integer> maxqueue = new PriorityQueue<>(new Comparator<Integer>(){
        public int compare(Integer a,Integer b) {
            return b-a;
        }
    });
    int index=0;
    public void Insert(Integer num) {
        if(index%2==0){
            minqueue.add(num);
            maxqueue.add(minqueue.poll());
        }else{
            maxqueue.add(num);
            minqueue.add(maxqueue.poll());
        }
        index++;
    }
 
    public Double GetMedian() {
        if(index%2==1){
            return maxqueue.peek()/1.0;
        }else{
            return (maxqueue.peek()+minqueue.peek())/2.0;
        }
    }
}

64.滑动窗口的最大值

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

窗口大于数组长度的时候，返回空

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        ArrayList<Integer> res = new ArrayList<>();
        int len=num.length;
        if(num.length<size||size<1){
            return res;
        }
        LinkedList<Integer> queue = new LinkedList<>();
        for(int i=0;i<len;i++){
            while(!queue.isEmpty()&&num[queue.peekLast()]<=num[i]){
                queue.pollLast();
            }
            queue.addLast(i);
            if(queue.peekFirst()==i-size){
                queue.pollFirst();
            }
            if(i>=size-1){
                res.add(num[queue.peekFirst()]);
            }
        }
        return res;
    }
}

65.单词搜索

public class Solution {
    char[][] board;
    boolean[][] used;
    int rows;
    int cols;
    char[] str;
    int[][] dep={{1,0},{0,1},{-1,0},{0,-1}};
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        this.rows=rows;
        this.cols=cols;
        this.board = new char[rows][cols];
        this.used = new boolean[rows][cols];
        this.str=str;
        int p=0;
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                board[i][j]=matrix[p++];
            }
        }
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(dfs(i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }
     
    private boolean dfs(int i,int j,int index){
       if(index==str.length-1){
           return board[i][j]==str[index];
       }
        //if(used[i][j]){
        //    return false;
      //  }
       if(board[i][j]==str[index]){
           used[i][j]=true;
           for(int a=0;a<4;a++){
               int x=i+dep[a][0];
               int y=j+dep[a][1];
               if(x>=0&&x<rows&&y>=0&&y<cols&&!used[x][y]){
                   if(dfs(x,y,index+1)){
                       return true;
                   }
               }
           }
           used[i][j]=false;
       }
        return false;
    }

66.机器人的运动范围

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

public class Solution {
    int threshold;
    int rows;
    int cols;
    boolean[][] used;
    public int movingCount(int threshold, int rows, int cols)
    {
        this.threshold = threshold;
        this.rows = rows;
        this.cols = cols;
        used = new boolean[rows][cols];
        return help(0,0);
    }
     
    private int help(int i,int j) {
        if(i<0||i>=rows||j<0||j>=cols||((isSum(i)+isSum(j))>threshold)||used[i][j]) {
            return 0;
        }
        used[i][j]=true;
        return help(i-1,j)+help(i,j-1)+help(i+1,j)+help(i,j+1)+1;
    }
     
    private int isSum(int i) {
        int sum = 0;
        while(i!=0){
            sum+=(i%10);
            i/=10;
        }
        return sum;
    }
}

67.剪绳子

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],…,k[m]。请问k[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

public class Solution {
    public int cutRope(int target) {
        if (target <= 3) {
            return target - 1;
        }
        int [] dp = new int[target + 1];
      //  dp[0] = 0;
        //dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for(int i = 4; i <= target; i++) {
     //       for(int j = 1; j <= i / 2; j++) {
                dp[i] = Math.max(dp[i-2]*2, dp[i-3]*3);
       //     }
        }
        return dp[target];
    }
}

2020-10-31

操作系统

操作系统-进程管理-用户级线程和内核级线程的区别

一、线程的分类

线程的实现可以分为两大类：用户级线程和内核级线程。

1.用户级线程

在一个纯粹的用户级线程软件中，有关线程管理的所有工作都由应用程序完成，内核意识不到线程的存在。任何应用程序都可以通过使用线程库被设计成多线程程序。线程库是用于用户级线程管理的一个例程包，它包含用于创建和销毁线程的代码、在线程间传递消息和数据的代码、调度线程执行的代码、以及保存和恢复线程上下文的代码。在默认情况下，应用程序从单线程开始，并在该线程中开始运行。该应用程序及其线程被分配给一个由内核管理的进程。在应用程序正在运行（进程处于运行态）的任何时刻，应用程序都可以派生一个在相同进程中运行的新线程（派生线程是通过调用线程库中的派生例程完成的，通过过程调用，控制权被传递给派生例程）。线程库为新线程创建一个数据结构，然后使用某种调度算法，把控制权传递给该进程中处于就绪态的一个线程。当控制权被传递给线程库时，需要保存当前线程的上下文，然后当控制权从线程库中传递给一个线程时，将恢复哪个线程的上下文。上下文实际上包括用户寄存器的内容、程序计数器和栈指针

在前一段描述的所有活动都发生在用户空间中，并且发生在一个进程内，而内核并不知道这些活动。内核继续以进程为单位进行调度，并且给该进程指定一个执行状态。

使用用户级线程而不是内核线程有很多优点：

1、由于所有线程管理数据结构都在一个进程的用户地址空间中，线程切换不需要内核态特权；

2、调度可以是应用程序相关的，可以做到为应用程序量身定做调度算法而不扰乱底层的操作系统调度程序；

3、用户级线程可以在任何操作系统中运行，线程库是一组供所有应用程序共享的应用程序级别的函数。

使用用户级线程而不是内核线程有两个明显的缺点：

1、当用户级线程执行一个会引起阻塞的系统调用时，不仅这个线程会被阻塞，进程中的所有线程都会被阻塞；

2、在纯粹的用户级线程策略中，多线程应用程序不能利用多处理技术，内核一次只把一个进程分配给一个处理器，因此一次进程中只有一个线程可以执行。

2.内核级线程

在一个纯粹的内核级线程软件中，有关线程管理的所有工作都是由内核完成的，应用程序部分没有进行线程管理的代码，只有一个到内核线程设施的应用程序编程接口（API）。Windows 是这种方法的一个例子。

内核为进程及其内部的每个线程维护上下文信息。调度是由内核基于线程完成的。该方法克服了用户级线程方法的两个基本缺陷（优点：）：

首先：内核可以同时把同一个进程中的多个线程调度到多个处理器中；

再者：如果进程中的一个线程被阻塞，内核可以调度同一个进程中的另一个线程；

另外：内核例程自身也是可以使用多线程的。

缺点：把控制从一个线程传送到同一个进程内的另一个线程时，需要到内核的状态转换

二、Windows线程

Windows 使用两类与进程相关的对象：进程和线程。

进程是对应一个拥有内存、打开的文件等资源的用户作业或应用程序的实体。线程是顺序执行的一个科分派的工作单元，并且它是可中断的，因此，处理器可以切换到另一个线程。一个 Windows 进程必须至少包含一个执行线程，该线程可能会创建别的线程。在多处理器系统中，同一个进程的多个线程可以并行的执行。

由于不同进程中的线程可能并非执行，因而 Windows 支持进程间的并发性。此外，同一个进程中的多个线程可以分配给不同的处理器并且同时执行。一个含有多线程的进程在实现并发时，不需要使用多进程的开销。同一个进程中的线程可以通过他们的公共地址空间交换信息，并访问进程中的共享资源，不同进程中的线程可以通过在两个进程间建立的共享内存交换信息

三、Linux的进程和线程管理

Linux 中的进程或任务由一个 task_struct 数据结构表示。

传统的 UNIX 系统支持每个执行的进程中只有一个单独的一个线程，但现代典型的 UNIX 系统支持一个进程中含有多个内核级线程。

** Linux 提供一种不区分进程和线程的解决方案**。用户级线程被映射到内核级进程上，组成一个用户级进程的多个用户级线程被映射到共享同一个组 ID 的多个 Linux 内核级进程上。这使得这些进程可以共享文件和内存等资源，使得同一组中的进程调度切换时不需要切换上下文。

当两个进程共享相同的虚存时，它们可以被当做是一个进程中的线程。

当 Linux 内核执行从一个进程到另一个进程的切换时，它将坚持当前进程的页目录地址是否和将被调度的进程相同。如果相同，那么它们共享同一个地址空间，所以此时上下文切换仅仅是从代码的一处跳转到代码的另一处。

虽然属于同一进程组的被克隆的进程共享同一内存空间，但它们不能共享同一个用户栈。

四、总结

用户级线程对操作系统是未知的，它们由一个在进程的用户空间中运行的线程库创建并管理。用户线程是非常高效的，因为从一个线程切换到另一个线程不需要进行状态切换，但是，一个进程中一次只有一个用户级线程可以执行，如果一个线程发生阻塞，整个进程都会被阻塞。

进程内包含的内核级线程是由内核维护的。由于内核认识它们，因而同一个进程中的多个线程可以再多个处理器上并行执行，一个线程的阻塞不会阻塞整个进程，但当从一个线程切换到另一个线程时就会需要进行模式切换。

2020-10-31

算法

剑指offer 46-55

46.孩子们的游戏(圆圈中最后剩下的数)

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

public class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if(m==0||n==0){
            return -1;
        }
        List<Integer> res=new ArrayList<>();
        for(int i=0;i<n;i++){
            res.add(i);
        }
        int index=-1;
        while(res.size()>1){
            index=(index+m)%res.size();
            res.remove(index);
            index--;
        }
        return res.get(0);
    }
}

47.求1+2+3+…+n

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

public class Solution {
    public int Sum_Solution(int n) {
        int sum=n;
        boolean flag=n>0&&(sum+=Sum_Solution(n-1))>0;
        return sum;
    }
}

48.不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

public class Solution {
    public int Add(int num1,int num2) {
        int tmp=0;
        while(num1!=0){
            tmp=(num1^num2);
            num1=((num1&num2)<<1);
            num2=tmp;
        }
        return num2;
    }
}

49.把字符串转换成整数

将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。数值为0或者字符串不是一个合法的数值则返回0

public class Solution {
    public int StrToInt(String str) {
        if(str==null||str.length()==0){
            return 0;
        }
        boolean flag=true;
        int index=0;
        if(str.charAt(index)=='+'){
            index++;
        }else if(str.charAt(index)=='-'){
            index++;
            flag=false;
        }
        int sum=0;
        for(int i=index;i<str.length();i++){
            if(str.charAt(i)<'0'||str.charAt(i)>'9'){
                return 0;
            }
            int p = str.charAt(i)-'0';
            if(flag&&((sum==Integer.MAX_VALUE/10&&p>7)||sum>Integer.MAX_VALUE/10)){
                return Integer.MAX_VALUE;
            }
            if(!flag&&((-sum==Integer.MIN_VALUE/10&&p>8)||-sum<Integer.MIN_VALUE/10)){
                return Integer.MIN_VALUE;
            }
            sum=sum*10+p;
        }
        return flag?sum:-sum;
    }
}

50.数组中重复的数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中第一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

public class Solution {
    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if(length==0){
            return false;
        }
        for(int i=0;i<length;i++){
            while(numbers[i]!=i){
                if(numbers[i]==numbers[numbers[i]]){
                    duplication[0]=numbers[i];
                    return true;
                }else {
                    int tmp=numbers[i];
                    numbers[i]=numbers[tmp];
                    numbers[tmp]=tmp;
                }
            }
             
        }
        return false;
    }
}

51.构建乘积数组

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…*A[i-1]A[i+1]…*A[n-1]。不能使用除法。（注意：规定B[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2];）

对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。

public class Solution {
    public int[] multiply(int[] A) {
        int len=A.length;
        if(len==0){
            return A;
        }
        int[] B=new int[len];
        int tmp=1;
        for(int i=0;i<len;i++){
            B[i]=tmp;
            tmp*=A[i];
        }
        tmp=1;
        for(int i=len-1;i>=0;i--){
            B[i]*=tmp;
            tmp*=A[i];
        }
        return B;
    }
}

52.正则表达式匹配

请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配

public class Solution {
    Integer[][] memo;
    public boolean match(char[] str, char[] p)
    {
        int m=str.length;
        int n=p.length;
        memo = new Integer[m+1][n+1];
        return help(str,p,0,0);
    }
     
    private boolean help(char[] c,char[] p,int i,int j){
        if(j==p.length){
            return i==c.length;
        }
        if(memo[i][j]!=null){
            return memo[i][j]!=-1;
        }
        boolean firstMatch = i<c.length&&j<p.length&&(c[i]==p[j]||p[j]=='.');
        boolean ans;
        if(j+1<p.length&&p[j+1]=='*'){
            ans=help(c,p,i,j+2)||(firstMatch&&help(c,p,i+1,j));
        }else{
            ans=help(c,p,i+1,j+1)&&firstMatch;
        }
        memo[i][j]=ans?1:-1;
        return ans;
    }
}

53.表示数值的字符串

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

public class Solution {
    int index=0;
    public boolean isNumeric(char[] str) {
        boolean flag = isPoNum(str);
        if(index<str.length&&str[index]=='.'){
            index++;
            flag = isNum(str)||flag;
        }
        if(index<str.length&&(str[index]=='e'||str[index]=='E')){
            index++;
            flag = isPoNum(str)&&flag;
        }
        return flag&&index==str.length;
    }
     
    private boolean isPoNum(char[] str){
        if(index<str.length&&(str[index]=='+'||str[index]=='-'))
            index++;
        return isNum(str);
    }
     
    private boolean isNum(char[] str){
        int start=index;
        while(index<str.length&&(str[index]>='0'&&str[index]<='9')){
            index++;
        }
        return index>start;
    }
}

54.字符流中第一个不重复的字符

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。

public class Solution {
    //Insert one char from stringstream
    Queue<Character> queue=new LinkedList<>();
    int[] map = new int[256];
    public void Insert(char ch)
    {
        map[ch]++;
        if(map[ch]==1){
            queue.add(ch);
        }
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        char c = '#';
        while(!queue.isEmpty()){
            c=queue.peek();
            if(map[c]==1){
                return c;
            }else{
                queue.poll();
            }
        }
        return '#';
    }
}

55.链表中环的入口结点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

public class Solution {
 
    public ListNode EntryNodeOfLoop(ListNode head)
    {
        ListNode p=head;
        ListNode q=head;
        while(q!=null&&q.next!=null){
            p=p.next;
            q=q.next.next;
            if(p==q){
                break;
            }
        }
         
        if(q==null||q.next==null){
            return null;
        }
        p=head;
        while(p!=q){
            p=p.next;
            q=q.next;
        }
        return p;
    }
}

2020-10-30

算法

剑指offer 36-45

36.两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

public class Solution {
    public ListNode FindFirstCommonNode(ListNode head1, ListNode head2) {
        ListNode p=head1;
        ListNode q=head2;
        while(p!=q){
            p=p==null?head2:p.next;
            q=q==null?head1:q.next;
        }
        return p;
    }
}

37.数字在排序数组中出现的次数

统计一个数字在升序数组中出现的次数。

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
       int len=array.length;
        if(len==0){
            return 0;
        }
        int l=help(array,k);
        int r=help(array,k+1);
        return r>l?r-l:0;
    }
     
    private int help(int[] arr,int k){
        int l=0;
        int r=arr.length-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(arr[mid]<k){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        return l;
    }
}

38.二叉树的深度

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        return Math.max(TreeDepth(root.left),TreeDepth(root.right))+1;
    }
}

39.平衡二叉树

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null){
            return true;
        }
        return help(root)!=-1;
    }
    private int help(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=help(root.left);
        if(left==-1){
            return -1;
        }
        int right=help(root.right);
        if(right==-1){
            return -1;
        }
        return Math.abs(left-right)<=1?Math.max(left,right)+1:-1;
    }
}

40.数组中只出现一次的数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        int val=0;
        for(int num:array){
            val^=num;
        }
        int index=1;
        while((index&val)==0){
            index<<=1;
        }
        num1[0]=0;
        num2[0]=0;
        for(int num:array){
            if((num&index)==0){
                num1[0]^=num;
            }else{
                num2[0]^=num;
            }
        }
    }
}

41.和为S的连续正数序列

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
       ArrayList<ArrayList<Integer> >res=new ArrayList<>();
        int l=1;
        int r=2;
        while(r<sum){
            int tmp=(l+r)*(r-l+1)/2;
            if(tmp==sum){
                ArrayList<Integer> list=new ArrayList<Integer>();
                for(int i=l;i<=r;i++){
                    list.add(i);
                }
                res.add(new ArrayList<>(list));
                l++;
            }else if(tmp<sum){
                r++;
            }else{
                l++;
            }
        }
        return res;
    }
}

42.和为S的两个数字

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> res=new ArrayList<>();
        int len=array.length;
        if(len==0){
            return res;
        }
        int l=0;
        int r=len-1;
        while(l<r){
            int tmp=array[l]+array[r];
            if(tmp==sum){
                res.add(array[l]);
                res.add(array[r]);
                return res;
            }else if(tmp>sum){
                r--;
            }else{
                l++;
            }
        }
        return res;
    }
}

43.左旋转字符串

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

public class Solution {
    public String LeftRotateString(String str,int n) {
        if(n>str.length()){
            return "";
        }
        return str.substring(n,str.length())+str.substring(0,n);
    }
}

44.翻转单词顺序列

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

public class Solution {
    public String ReverseSentence(String str) {
        if(str.trim().length()==0){
            return str;
        }
        String[] c=str.split("\\s+");
        for(int i=0;i<c.length/2;i++){
            String tmp=c[i];
            c[i]=c[c.length-1-i];
            c[c.length-1-i]=tmp;
        }
        StringBuffer sb=new StringBuffer();
        for(int i=0;i<c.length;i++){
            sb.append(c[i]);
            if(i!=c.length-1){
                sb.append(" ");
            }
        }
        return sb.toString();
    }
}

45.扑克牌顺子

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何，如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

public class Solution {
    public boolean isContinuous(int [] numbers) {
        int len=numbers.length;
        if(len<5){
            return false;
        }
        int count=0;
        int p=0;
        Arrays.sort(numbers);
        for(int i=0;i<len;i++){
            if(numbers[i]==0){
                count++;
            }else{
                if(i<len-1&&numbers[i]==numbers[i+1]){
                    return false;
                }
                if(i<len-1){
                    p+=(numbers[i+1]-numbers[i]-1);
                }
            }
             
        }
        return count>=p;
    }
}

2020-10-29

操作系统

进程管理

一、进程的引入和概念

程序的顺序执行
最简单的程序设计方法是顺序的方法，这种方法有以下特点：

①. 程序在运行时独占资源，叫做封闭性；②. 程序执行时，只要初始条件相同，无论程序是连续执行还是断续执行，结果不变，叫做可再现性
程序的并行执行

进程的概念
①. 进程定义

进程又叫做任务，是程序的一次执行过程，是程序在一个数据集合上顺序执行发生的活动，是系统资源分配的单位

②. 进程和程序的联系和区别

进程是程序的一次执行过程，具有动态性，而程序是一种可以长期保存的软件资源；进程是系统进行资源分配和资源调度的一个独立单位，句有独立性，程序不是；进程可以与其他进程并行；

二、进程的描述

进程控制块
为了描述进程的运行变化情况，操作系统为每个进程定义了一个数据结构叫做进程控制块（PCB），也叫进程描述符，是进程的唯一标志，包含了进程的描述信息和管理控制信息。

PCB包含的信息：

①. 进程标志数

②. 进程的状态以及调度和存储器管理信息

③. 进程使用的资源信息，包括分配给进程的IO设备、正在执行的IO请求信息

④、CPU现场保护区

⑤、记账信息，包括CPU时间量等

⑥、进程之间的家族关系

⑦、进程的链接指针
进程的状态
创建态、终止态、就绪态、运行态、阻塞等待态

①. 创建态，进程刚刚被创建

②. 终止态，进程不再受处理及调度管理，可能是正常完成或者已经中断

③. 就绪态，已经获得了除cpu之外的所有资源，等待系统分配CPU

④. 运行态，正在CPU执行的进程

⑤. 阻塞等待态，等待某些资源
进程的组织
进程控制块是系统对进程统一管理的依据，为了便于系统管理，通常对系统中的进程采用两种组织方式

①. 线性表

把所有进程的PCB组成一个数组，系统通过数组下标访问每一个PCB。系统通过数组下标访问每一个PCB，优点是简单，节省存储空间，缺点是系统开销大

②. 链接表

将同一状态下的进程链接成一个队列，系统会设置一个指针指向当前运行进程的PCB。

三、进程的控制

所谓进程控制是指系统使用一些具有特定功能的程序段来创建、撤销进程以及完成进程各状态间转换的一系列有效管理。

用于控制进程的原语如下：

创建原语
创建原语的功能：创建一个进程主要是为进程创建一个PCB，扫描系统的PCB的集合表，找到一个空闲的PCB，并获得PCB的内部名称，作为进程的标识。若程序和数据不在主存，也应为其分配主存，并调入主存，把调用者的参数填入PCB中，将状态置为就绪，插入队列中。
撤销原语
撤销，归还资源
阻塞原语
处于运行态的进程中断CPU，将其运行现场保存在其PCB的CPU现场保护区；状态置为阻塞态，插入相应等待队列
唤醒原语
挂前期原语
激活原语

四、处理机的调度

处理机调度的级别
作业调度、进程调度、交换调度

作业调度是让作业有资格获得CPU，作业的运行需要通过进程调度实现，处理机的交换调度是为了使得资源分配更加合理
进程调度的方式
非抢先方式

抢先方式
处理机调度算法
先来先到服务、最短作业优先、最短剩余时间优先、优先级调度，时间片轮转算法、多级反馈队列算法

五、线程

进程和线程的区别
线程分类
用户级线程、核心线程、两级结合

一、简介

二、区别

三、原理

四、总结

1.sync.WaitGroup

2.sync.Once

3.sync.Map

一、Goroutine简介

二、Goroutine使用

三、goroutine与线程

四、Goroutine(协程)的理解

五、总结

一、连接数据库

二、增删改

三、查询

四、总结

一、Gin简介

二、Gin 特性

三、路由（Route）

四、HTML模板

56.删除链表中重复的结点

57.二叉树的下一个结点

58.对称的二叉树

59.按之字形顺序打印二叉树

60.把二叉树打印成多行

61.序列化二叉树

62.二叉搜索树的第k个结点

63.数据流中的中位数

64.滑动窗口的最大值

65.单词搜索

66.机器人的运动范围

67.剪绳子

一、线程的分类

1.用户级线程

2.内核级线程

二、Windows线程

三、Linux的进程和线程管理

四、总结

46.孩子们的游戏(圆圈中最后剩下的数)

47.求1+2+3+…+n

48.不用加减乘除做加法

49.把字符串转换成整数

50.数组中重复的数字

51.构建乘积数组

52.正则表达式匹配

53.表示数值的字符串

54.字符流中第一个不重复的字符

55.链表中环的入口结点

36.两个链表的第一个公共节点

37.数字在排序数组中出现的次数

38.二叉树的深度

39.平衡二叉树

40.数组中只出现一次的数字

41.和为S的连续正数序列

42.和为S的两个数字

43.左旋转字符串

44.翻转单词顺序列

45.扑克牌顺子

一、进程的引入和概念

程序的顺序执行

程序的并行执行

进程的概念

二、进程的描述

进程控制块

进程的状态

进程的组织

三、进程的控制

创建原语

撤销原语

阻塞原语

唤醒原语

挂前期原语

激活原语

四、处理机的调度

处理机调度的级别

进程调度的方式

处理机调度算法

五、 线程

进程和线程的区别

线程分类

五、线程