头像

wangzitiansky

知乎




离线:2小时前



Go 哈希表

文章汇总

由于公司工作需要,最近在学习 Go 语言,开个坑记录一下学习笔记

Go 学习资料推荐 (也是本文的参考书目)

Go 设计与实现

Go 高级编程

本文简要讲解了 Go 语言 map 的用法

概述

Gomap 就是哈希表,使用拉链法解决哈希冲突

初始化

有两种初始化方式

  • 通过字面量初始化

code2.png

  • 使用 make 关键字创建 Map

code1.png

添加删除元素

注意删除元素要使用 delete 关键字

code3.png

迭代

  • 支持 range 迭代

code4.png

  • 判断某个键是否在哈希表中的方法

通过 _, ok := map[key] 操作

code6.png

例子

code5.png




Go 切片

文章汇总

由于公司工作需要,最近在学习 Go 语言,开个坑记录一下学习笔记

Go 学习资料推荐 (也是本文的参考书目)

Go 设计与实现

Go 高级编程

本文简要讲解了 Go 语言 切片的用法

概述

Goslice 是可自动扩容的数组。类似Java 里面的 ArrayList / LinkedListC++ 里面的 vector

初始化

切片初始化有三种方式

  • 通过字面量初始化新切片

code.png

  • 通过下标获得数组或者切片的一部分

code2.png

  • 使用 make 关键字创建切片

code3.png

添加元素

  • 在尾部添加元素

注意添加一个切片的时候需要解包操作

code4.png

  • 在头部添加元素

注意头部添加性能很差

code5.png

  • 在中间位置添加元素

需要注意提前分配出空间并且和 copy 配合

code6.png

删除元素

删除元素通过切片操作来实现

  • 删除头部或者尾部元素

code8.png



活动打卡代码 AcWing 1018. 最低通行费

#include <iostream>
#include <cstring>

using namespace std;
const int N = 110, INF = 1e9;
int g[N][N];
int f[N][N];

int main(){

    int n;
    scanf("%d", &n);

    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            scanf("%d", &g[i][j]);
        }
    }

    // memset(f, INF, sizeof f);

    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= n; j ++){
            if(i == 1 && j == 1) {
                f[i][j] = g[i][j];
            } else {
                f[i][j] = INF;
                if(i > 1){
                    f[i][j] = min(f[i][j], f[i - 1][j] + g[i][j]);
                } 
                if(j > 1){
                    f[i][j] = min(f[i][j], f[i][j - 1] + g[i][j]);
                }   
            }
        }
    }

    printf("%d\n", f[n][n]);

    return 0;
}


活动打卡代码 AcWing 1015. 摘花生

#include <iostream>
#include <cstring>

using namespace std;
const int N = 110;
int g[N][N];
int r, c;
int T;
int f[N][N];


int main(){

    scanf("%d", &T);

    while(T --){
        memset(f, 0, sizeof f);
        scanf("%d %d", &r, &c);
        for(int i = 1; i <= r; i ++){
            for(int j = 1; j <= c; j ++){
                scanf("%d", &g[i][j]);
            }
        }

        for(int i = 1; i <= r; i ++){
            for(int j = 1; j <= c; j ++){
                f[i][j] = max(f[i - 1][j] + g[i][j], f[i][j - 1] + g[i][j]);
            }
        }

        printf("%d\n", f[r][c]);
    }

    return 0;
}



工厂模式

文章汇总

原文地址 Github

动机

  • 在软件系统中,经常面临着创建对象的工作,由于需求变化,需要创建的对象的具体类型经常变化
  • 如何绕过常规的 new 方法,提供一种封装机制来避免客户程序和具体对象创建工作的紧耦合

代码示例

有一个文件分割器类和一个 Form 类,Form 类中需要新建一个文件分割器的对象

// 文件分割器基类
class ISplitter{
public:
    virtual void split()=0;
    virtual ~ISplitter(){}
};

// 具体的文件分割器类
class BinarySplitter : public ISplitter{

};

// Form 类
class MainForm : public Form
{
    TextBox* txtFilePath;
    TextBox* txtFileNumber;
    ProgressBar* progressBar;

public:
    void Button1_Click(){
        // 紧密耦合
        // 面向接口编程 变量声明为抽象基类
        ISplitter * splitter=
            new BinarySplitter();//依赖具体类 不好

        splitter->split();

    }
};

采用工厂模式的代码

//抽象类
class ISplitter{
public:
    virtual void split()=0;
    virtual ~ISplitter(){}
};


//工厂基类
class SplitterFactory{
public:
    virtual ISplitter* CreateSplitter()=0;
    virtual ~SplitterFactory(){}
};

//具体类
class BinarySplitter : public ISplitter{

};

//具体工厂
class BinarySplitterFactory: public SplitterFactory{
public:
    virtual ISplitter* CreateSplitter(){
        return new BinarySplitter();
    }
};


class MainForm : public Form
{
    // 工厂类的抽象类的引用
    SplitterFactory*  factory;//工厂

public:

    MainForm(SplitterFactory*  factory){
        this->factory=factory;
    }

    void Button1_Click(){


        ISplitter * splitter=
            factory->CreateSplitter(); //多态new

        splitter->split();

    }
};

这里新建对象的时候,运行时究竟调用了哪个工厂方法新建了哪个对象,是由 MainFormSplitterFactory 的类型决定的,是一种多态的思想。而且对于 MainForm 来说,并不知道具体的工厂类,是面向接口编程,是一种抽象的思想。

参考

https://www.bilibili.com/video/BV1kW411P7KS?from=search&seid=13066287095511349570



活动打卡代码 AcWing 173. 矩阵距离

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1010, M = N * N;
typedef pair<int, int> PII;
PII q[M];
int hh = 0, tt = -1;
int n, m;
int dist[N][N];
char g[N][N];

void bfs(){
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
    memset(dist, -1, sizeof dist);
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            if(g[i][j] == '1'){
                q[++ tt] = {i, j};
                dist[i][j] = 0;
            }
        }
    }

    while(hh <= tt){
        auto t = q[hh ++];
        for(int i = 0; i < 4; i ++){
            int nx = t.first + dx[i];
            int ny = t.second + dy[i];
            if(nx <= 0 || nx > n || ny <= 0 || ny > m) continue;
            if(dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[t.first][t.second] + 1;
            q[++ tt] = {nx, ny};
        }
    }
}

int main(){

    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i ++) scanf("%s", g[i] + 1);

    bfs();

    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            printf("%d ", dist[i][j]);
        }
        puts("");
    }

    return 0;
}


活动打卡代码 LeetCode 435. 无重叠区间

此题可以参考 算法基础课 贪心部分

https://www.acwing.com/problem/content/910/

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),[](const vector<int>&a,const vector<int>&b)
             {
                 return a[1] == b[1] ? a[0] > b[0]:a[1] < b[1];
             });
        int res = 0, ed = -2e9;
        int left = 0, right = 1;
        for(int i = 0; i < intervals.size(); i ++){
            if(intervals[i][left] >= ed){
                res ++;
                ed = intervals[i][right];
            }
        }
        return intervals.size() - res;
    }
};



class Solution {
public:
    int countSegments(string s) {
        int res = 0;
        s += ' ';
        for(int i = 0; i < s.size() - 1; i ++){
            if(s[i] != ' ' && s[i + 1] == ' ') res ++;
        }
        return res;
    }
};



/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> res;
        if(!root) return res;
        queue<Node*> q;
        q.push(root);
        while(q.size()){
            int size = q.size();
            vector<int> temp;
            while(size --){
                auto t = q.front();
                q.pop();
                temp.push_back(t->val);
                for(auto child : t->children){
                    if(child){
                        q.push(child);
                    }
                }
            }
            res.push_back(temp);
        }
        return res;
    }
};



MySQL 的 redo 日志

原文地址 GitHub

分享文章汇总

为什么要有 redo 日志

其实 redo 日志主要是为 MySQL 提供了异常情况下恢复数据的功能。MySQL 为了性能考虑,所以在更新一条数据时,只会将内存中的数据更新,并不会更新磁盘中的数据。但是如果此时 MySQL 出现了崩溃,那内存中的数据就丢了,这是不可接受的。但是每次都把更新刷新到磁盘又实在是太慢了,所以就出现了 redo 日志。redo 日志记录的是对数据库的修改,如果遇到系统崩溃,那直接按照 redo 日志,重新更新一下数据库就好了。

redo 日志的好处

  • redo 日志占据空间较小

一条 redo 日志占用空间不是很大

  • redo 日志是顺序写入磁盘的

顺序 IO 的性能是好于随机 IO 的(如果直接更新磁盘中的数据页,则是随机 IO)

  • 保证数据库发生异常重启之后,之前的更新不会丢失

这就是 crash-safe 能力

一条更新语句写入数据库的过程

当一条更新数据库的语句执行之后,首先会写入 redo 日志,更新内存,之后在适当的时间才会将此次更新刷新到磁盘

参考

https://time.geekbang.org/column/article/68633

https://juejin.im/book/6844733769996304392/section/6844733770063626253