Kenway's Blog

发表于 更新于 分类于
  1. Blog性质
  • 本BLOG由个人维护，文章内容来自于个人原创，主要目的为记录、整理学习过程中遇到的问题和笔记，不涉及商业用途
  1. 关于转载、版权
  • 欢迎非商业性用途转载，转载请注明出处
  • 本BLOG文章除特别声明以外，均为作者原创，未经作者本人允许不得擅自用于商业用途及传统媒体

本站文章采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

发表于 更新于 分类于

目录

基础题

典型题

常用算法

进阶算法

数据结构设计

SQL典型题

解题通用思路

基础题

1.传递信息

给定总玩家数n，以及按[玩家编号,对应可传递玩家编号]关系组成的二维数组 relation。返回信息从编号0玩家经过k轮传递到编号为n-1玩家处的方案数；若不能到达，返回0

示例：输入：n = 5, relation = [[0,2],[2,1],[3,4],[2,3],[1,4],[2,0],[0,4]], k = 3
输出：3
解释：信息从小 A 编号 0 处开始，经 3 轮传递，到达编号 4。共有 3 种方案，分别是 0->2->0->4， 0->2->1->4， 0->2->3->4。

解法:模拟法

  • 从第一轮开始模拟
  • 每一轮中遍历relation数组根据发送者-接受者的关系，用上一轮能到达发送者的方案数去更新该轮能到达接受者的方案数
  • 模拟到最后一轮后返回满足题目要求的方案数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # k是轮数，n是总人数
    vector<vector<int>> dp(k+1, vector<int> (n));
    dp[0][0] = 1;
    for(int i = 1; i < k+1; i++){
        for(auto& t:relation){
            int send_id = t[0];
            int accept_id = t[1];
            dp[i][accept_id] += dp[i-1][send_id];
        }
    }
    return dp[k][n-1];
        
    # dp[i][j]表示在第i轮能到达编号j的方案数
阅读全文 »

发表于 分类于

目录

一、MyRedis开发

二、秒杀系统

一、MyRedis开发

1.Redis的数据序列化协议是RESP，即client和server之间的通信协议，5种数据格式如下：

  • 正常回复：以”+”开头，以”\r\n”结尾，例如+OK\r\n
  • 错误回复：以”-“开头，以”\r\n”结尾，例如-Error message\r\n
  • 整数：以”:”开头，以”\r\n”结尾，例如:123456\r\n
  • 多行字符串：以”$”开头后跟字符数量，数据由”\r\n”隔断，例如:$6\r\n123456\r\n
  • 数组：以”*“开头后跟成员数量，每个成员由”\r\n”隔断，例如:*2\r\n$4\r\nstr1\r\n$4\r\nstr2\r\n

2.myRedis的解析异步化

  • 对外公布的Parser()方法会返回一个<-ch *PayLoad，因为方法里面用协程去调用了执行解析的实际方法，当解析完成时，会吐到这个channel里面
    1
    2
    3
    4
    5
    func ParseStream(reader io.Reader) <-chan *Payload{
    	ch := make(chan *Payload, 0)
    	go parse0(reader, ch)
    	return ch
    }

3.k-v和dict的实现

  • k-v的val用interface{}，是因为可以适应各种数据类型的值
  • dict里面的方法:get、put、len等等的实现，其实就是底层对sync.map的业务调用，而因为这样封装了一层，以后改用不是sync.map的数据结构实现也方便

4.数据命令解析过程

  • 主线程监听端口，用handle去处理
  • parse0里面根据传的命令第一个字符是’*’还是’$’分别调不用的函数进行处理，当前读取的状态用state结构体记录
  • 解析得到args数组后吐到channel里
  • handle接受了这个channel里面的数据args数组后，去调数据库内核的Exce方法
    • echo_database这个数据库内核的Exce()实现的是，传什么进来就返回什么回去，所以会把解析好的数据再重新包装

5.核心链路

  • tcp包里监听接口的数据，然后拿去给resp协议层handle()处理
  • handle()去调parseStream解析命令
  • parseStream将翻译后的命令转给内核database去处理
    • 这里是异步执行，通过go parse0异步往channel里写数据，然后主程序去获取这个channel的产出往下执行
  • 每个内核database里面有一个*DB列表
  • 每个db里面有一个它的序号和一个dict
  • 每个dict底层用sync.map实现了Get()、PUT()等一系列方法

6.aof落盘逻辑

  • database内核在初始化时，也会初始化aof，先根据aof文件恢复之前状态
    • 恢复依然是走的parseStram()方法
  • 初始化有buffer的管道，然后起一个协程去异步从管道里拿操作命令写aof文件(落盘)
    • 每次出现set、rename这种写命令时，就调一次addAof()把命令塞入管道

7.碰到的问题

  • aof落盘的时候，明明应该是db0，但是落盘成db15
    • 原因：
      • 初始化database内核时，用匿名函数赋予里面的成员db的addAof()方法出现闭包问题
      • 因为闭包去调addAof()的方法会使用到局部变量db.index，所以这个局部变量db会逃逸到堆上，然后每次for遍历的时候都会去更新这个堆上的db值
      • 最后实际堆上是遍历的最后一个db成员
    • 解决办法：
      • for循环里新定义一个临时变量来放db
    • 原理：
      • for循环头部的变量每次循环中在内存上的地址其实是一样的，只是每次的值不一样(所以有时候这个地址逃逸到堆上就会产生闭包问题)
      • 而for循环内部定义的变量每次循环都会是一个新的内存地址，单次循环结束后就销毁

8.集群化

  • 采用一致性哈希，好处是：增加一个新节点只用迁移部分数据
  • 每个节点运行有一个database内核和一个连接池
      - 连接池是自己作为客户端与其他节点的连接(客户端用的是github上的开源库)
  • 对于数据不存在自己本地上的命令，会把本机当做一个redis客户端去访问别的节点
阅读全文 »

发表于 更新于 分类于

目录

云服务器配置

本地设置

域名相关

云服务器

1.采用阿里云单核CPU云服务器ECS

2.云服务器安全组规则

1
2
3
4
5
6
7
8
网卡类型:内网
规则方向:入方向
授权策略:允许
协议类型:HTTP(80)
端口范围:80/80
优先级:100
授权类型:IPv4地址段访问
授权对象:0.0.0.0/0

3.在云服务器上配置Nginx和Git

  • 安装
    1
    2
    apt install nginx
    apt install git

4.配置blog文件路径

  • 建立文件夹
    1
    mkdir /var/blog/
  • 修改权限
    1
    2
    chown -R $USER:$USER /var/repo/
    chmod -R 755 /var/repo/
  • Git初始化
    1
    2
    cd /var/blog
    git init --bare {自定义仓库名name}.git

5.配置Nginx托管文件路径

  • 建立文件夹
    1
    2
    3
    mkdir -p /var/www/hexo
    chown -R $USER:$USER /var/www/hexo
    chmod -R 755 /var/www/hexo
  • 修改Nginx配置文件的server使root指向文件路径
    1
    root /var/www/hexo
    server_name后写入自己的域名或公网ip(写一个就行)
    1
    server_name 39.105.120.230 kenway-20.com www.kenway-20.com;

6.Git钩子(hook)

  • 新建一个钩子文件
    1
    vim /var/blog/kenwayBlog.git/hooks/post-receive
  • 在该钩子文件中添加以下代码
    1
    2
    3
    #!/bin/bash

    git --work-tree=/var/www/hexo --git-dir=/var/blog/kenwayBlog.git checkout -f
  • 将钩子文件保存后再赋予其权限
    1
    chmod +x /var/blog/kenwayBlog.git/hooks/post-receive
阅读全文 »