2020年3月

【每日打卡】[leetcode]面试题1.6-字符串压缩

作者: 编程我只用CPP
时间: 2020-03-16
分类: 数据结构和算法
评论

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/compress-string-lcci

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。

示例1：

输入："aabcccccaaa"
输出："a2b1c5a3"

示例2：

输入："abbccd"
输出："abbccd"
解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。

提示：字符串长度在[0, 50000]范围内。

二、题解

一道很简单的字符串处理题型，思路：

使用一个计数器保存每个重复字符的个数。
遇到相同字符，计数加一。
遇到不同字符，把前面的字符和计数加到输出字符串末尾，计数器归零。

三、代码

class Solution {
public:
    string compressString(string S) {
        char ch;
        int i, cnt;
        string output;
        stringstream ss;

        if (S.size() <= 1)
            return S;

        cnt = 1;
        ch = S[0];
        for (i = 1; i < S.size(); i++) {
            if (S[i] == ch) {
                cnt++;
            } else {
                // 压入到字符串流
                ss << ch << cnt;
                // 重新计数
                cnt = 1;
                ch = S[i];
            }
        }
        // 最后一个字符和计数也放到字符串流里面去
        ss << ch << cnt;
        // 打印到输出字符串
        ss >> output;

        return output.size() < S.size() ? output : S;
    }
};

【每日打卡】[leetcode]695-岛屿的最大面积

作者: 编程我只用CPP
时间: 2020-03-15
分类: 数据结构和算法
评论

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/max-area-of-island

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个岛屿是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)

示例 1：

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。

示例 2：

[[0,0,0,0,0,0,0,0]]

对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

二、题解

和地图相关的题目求最值，第一个想到的都应该是深度优先搜索，例如求两点间的最短路径、迷宫找最短出口等，都可以用深搜来解决问题。当然，出了深搜以外，还可以通过回溯来解决。深搜实际上是递归，而回溯则是迭代。

使用深搜的思路：遍历每个地图点，如果是陆地，就往四个方向上继续蔓延，一旦遍历到非陆地或者超出地图范围了就返回。

要注意的问题是，当一个点蔓延到另外一个点后，另外一个点也可能会蔓延回来。例如A是B的左节点，B作为陆地蔓延到A后又会作为A的右节点蔓延回来。这种情况下就导致重复计算，所以为了避免重复处理，需要特殊处理这个问题。可以采取的办法是每访问到一个节点，就把它变成海洋。

输入数据需要考虑的特殊场景：空地图，地图只有一列或一行。

三、代码

class Solution {
    /*
     * @grid 地图
     * @i/j 需要计算的地图坐标
     * @row/col 地图的行数和列数
     * @return 返回相连的面积
     */
    int dfs(vector<vector<int>> &grid, int i, int j, const int row, const int col) {
        int top, bottom, left, right;
        // dfs退出条件，到达了边界，或者当前值为0
        if (i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == 0)
            return 0;

        // 已经访问过的节点置为0，避免重复计算
        grid[i][j] = 0;

        // 分别计算上下左右四个方向上的面积
        top = dfs(grid, i + 1, j, row, col);
        bottom = dfs(grid, i - 1, j, row, col);
        right = dfs(grid, i, j + 1, row, col);
        left = dfs(grid, i, j - 1, row, col);

        // 返回总面积
        return top + bottom + left + right + 1;
    }

public:
    int maxAreaOfIsland(vector<vector<int>> &grid) {
        int i, j, row, col, res;

        if (grid.empty())
            return 0;

        row = grid.size();
        col = grid[0].size();

        res = 0;
        for (i = 0; i < row; i++) {
            for (j = 0; j < col; j++) {
                // 提前剪枝
                if (grid[i][j] == 0)
                    continue;

                // 遍历每一个节点
                res = max(res, dfs(grid, i, j, row, col));
            }
        }
        return res;
    }
};

测试案例：

TEST(leetcode, demo) {
    Solution s;
    vector<vector<int>> input1{
            {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
            {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
            {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}
    }, input2{{1}}, input3{{0,0,0,0,0,0}}, input4;

    EXPECT_EQ(s.maxAreaOfIsland(input1), 6);
    EXPECT_EQ(s.maxAreaOfIsland(input2), 1);
    EXPECT_EQ(s.maxAreaOfIsland(input3), 0);
    EXPECT_EQ(s.maxAreaOfIsland(input4), 0);
}

【深搜入门题】[leetcode]46-全排列

作者: 编程我只用CPP
时间: 2020-03-15
分类: 数据结构和算法
评论

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/permutations

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]

输出:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

二、题解

求全排列，简单的深搜题目，解法参考：深度优先搜索。

三、代码

class Solution {
private:
    set<int> m_set;
    vector<int> m_vec;
    vector<vector<int>> m_res;

    void dfs(vector<int> &nums, int l, int r) {
        int i;
        if (l == r) {
            m_res.push_back(m_vec);
            return;
        }

        for (i = 0; i < nums.size(); i++) {
            set<int>::iterator it;
            if (m_set.find(nums[i]) != m_set.end())
                continue;

            // 没有找到
            m_vec.push_back(nums[i]);
            m_set.insert(nums[i]);

            // 深搜
            dfs(nums, l + 1, r);

            // 删除当前值，遍历下一个节点
            m_vec.pop_back();
            it = m_set.find(nums[i]);
            if (it == m_set.end())
                throw logic_error("cannot find key");
            m_set.erase(it);
        }
    }

public:
    vector<vector<int>> permute(vector<int> &nums) {
        dfs(nums, 0, nums.size());
        return m_res;
    }
};

深度优先搜索算法

作者: 编程我只用CPP
时间: 2020-03-15
分类: 数据结构和算法
评论

今天leetcode打卡的题目是一道深搜题，好久没有写深搜，翻出了以前搞ACM时候的资料。

资料是2016年蓝桥杯程序设计大赛的解题报告，当时是10道题目，大半都是深搜解决。

redis字符串的用法和实现原理

作者: 编程我只用CPP
时间: 2020-03-14
分类: 数据库
评论

一、基本用法

字符串是redis中的基本数据类型之一，能存储任何形式的字符串，包括二进制数据。同时，它还可以进行字符串运算、数据运算和位运算等操作。一个字符串最大能有512M。

字符串主要的操作命令有两个：

GET KEY: 如果KEY存在就返回对应的值，如果不存在则返回空值nil。
SET KEY VALUE: 给KEY设置值为VALUE，如果KEY已经存在则更新值。

例如：

# 设置一个新值
127.0.0.1:6379> set test HelloWorld
OK
# 获取值
127.0.0.1:6379> get test
"HelloWorld"
# 获取不存在的值返回nil
127.0.0.1:6379> get aaaa
(nil)

字符串也支持同时给多个key同时赋值，方法为：

MGET key value [key value]: 同时设置多个键值。
MSET key value [key value]: 同时获取多个键值。

127.0.0.1:6379> mset keya aaa keyb bbb keyc ccc
OK
127.0.0.1:6379> mget keya keyb keyc
1) "aaa"
2) "bbb"
3) "ccc"

还有一个常用的操作就是在获取key的同时并设置key的值：

GETSET key value：给key赋值并返回先前的元素，如果元素不存在返回nil。

127.0.0.1:6379> keys *
(empty list or set)
127.0.0.1:6379> getset k 123
(nil)
127.0.0.1:6379> getset k 456
"123"

二、操作API

字符串主要有以下操作命令：

2.1. APPEND

在尾部增加字符串，命令格式：append key value，成功将会返回添加后的字符串长度。

127.0.0.1:6379> set test Hello
OK
127.0.0.1:6379> append test World
(integer) 10  # 添加成功返回总长度
127.0.0.1:6379> get test
"HelloWorld"

2.2. STRLEN

获取字符串长度，命令格式：strlen key，成功将会返回该值得长度。

127.0.0.1:6379> strlen test
(integer) 10
127.0.0.1:6379> strlen aaaa
(integer) 0  # 键不存在返回0

2.3. GETRANGE

获取指定偏移范围内的字符，命令格式：getrange key start end，键不存在返回空。

127.0.0.1:6379> getrange test 5 10
"World"
127.0.0.1:6379> getrange aaaa 1 2
""  # 键不存在返回空

和大多数程序语言一样，redis的字符串下标从0开始，到len(key) - 1结束。要注意的是redis中可以使用-1表示最后一位。

127.0.0.1:6379> getrange test 0 -1 # 获取第一个字符到最后一个字符
"HelloWorld"

三、数据运算

当我们存入一个十进制整数或者浮点数到redis当中去的时候，redis会自动察觉到这一点，并允许我们使用相关的命令来操作它们。

3.1 INCR和DECR

把整形数据加一或者减一，命令格式：incr key decr key，执行成功会返回增加过后的值，如果key不存在时会自动创建。

127.0.0.1:6379> set num 100
OK
127.0.0.1:6379> incr num
(integer) 101  
127.0.0.1:6379> incr num
(integer) 102
127.0.0.1:6379> decr num
(integer) 101
127.0.0.1:6379> get num
"101"
127.0.0.1:6379> incr aaaa
(integer) 1  # 自动创建aaaa并初始化值为0然后+1

3.2 INCRBY、DECRBY和INCRBYFLOAT

增加或者删除指定的大小，命令格式为：incrby key increment。INCRBY和DECRBY针对整数，INCRBYFLOAT针对浮点数，不可以使用INCRBY和DECRBY操作浮点数。

127.0.0.1:6379> set num 100
OK
127.0.0.1:6379> incrby num 10
(integer) 110
127.0.0.1:6379> decrby num 5
(integer) 105
127.0.0.1:6379> incrbyfloat num 1.1
"106.1"
127.0.0.1:6379> incrby num 10
(error) ERR value is not an integer or out of range  # 使用整形命令操作浮点数会报错

使用数据运算的同时还可以字符串命令：

127.0.0.1:6379> set num 100
OK
127.0.0.1:6379> append num 999  # 在尾部添加
(integer) 6
127.0.0.1:6379> get num
"100999"
127.0.0.1:6379> incr num  # 仍然可以执行数据运算
(integer) 101000

除了这些以外，redis还支持位运算，可参考：Redis中的位运算。

四、实现原理

字符串内部使用了三种编码方式，分别是int/raw/embstr。

4.1 int编码

当存储的字符串是一个整形数据的时候，redis会自动以整形数据来保存。

127.0.0.1:6379> set mobile 10086
OK
127.0.0.1:6379> OBJECT ENCODING mobile
"int"

当使用int类型编码的时候，字符串对象结构为：

4.2 raw和embstr编码

raw和embstr编码底层都是使用sdshdr来存储字符串，使用raw方式编码的字符串对象结构：

embstr和raw编码的不同在于使用embstr编码的时候，redis会把上面的redisObject和shshdr作为一个对象同时申请内存，它们在内存上是连续的，而raw编码的字符串在内存上并不连续。

当存储的字符串长度小于39时，redis会使用embstr来编码。这样做的目的主要有以下几个：

减少内存的分配和释放次数
内存连续适合小对象缓存

我给微信找BUG系列：微信代理引起的负载问题排查过程

作者: 编程我只用CPP
时间: 2020-03-14
分类: 编程语言
评论

本周处理了好几例负载高问题，原因竟然都是因为微信对代理场景的支持不好导致的。
回顾十分曲折的排查过程，记录下来！顺带吐槽一下微信。

一、问题描述

背景：我们的设备作为客户处的上网出口，代理内网用户上网。

问题：设备流量不高，但是负载特别高，经常性产生断网事件，流量突降为0。

二、排查过程

2.1 分析负载和CPU

先画出问题时间点的负载趋势图，可以看到负载确实是很高的：

这个设备只是2核的，负载超过4就可以认为负载高了，而记录下来的负载基本都在10以上，远超出设备负载。

然后分析CPU采样，找到对应时间点的mpstat记录，采样中显示较高的是iowait和soft：

Fri Mar 13 08:40:08 CST 2020
Linux 2.6.30-gentoo-r8 (localhost)     03/13/20     _x86_64_    (2 CPU)

Average:     CPU    %sys %iowait    %irq   %soft  %idle
Average:     all    2.50   82.00    3.00   10.50   0.00
Average:       0    1.01   81.82    5.05   10.10   0.00
Average:       1    3.00   83.00    1.00   11.00   0.00

soft高一般都是流量过高或者连接数过大导致的，而iowait高大部分时候都是内存不足导致的，因为内存不足会导致内存cache回收，大量的磁盘脏数据刷到磁盘，导致IO高。因此下一步应该先分析内存。

2.2 分析内存占用

分析问题时间点前后的内存状态，发现了内存cache回收的情况：

2020-3-13 08:37:57
             total       used       free     shared    buffers     cached
Mem:          1809       1675        133          0          6        130

2020-3-13 08:38:02
             total       used       free     shared    buffers     cached
Mem:          1809       1546        262          0          1         27

设备只有2G内存，属于低端平台了，内存不足应该属于常态，所以经常回收cache，导致了io高。

然后统计slab占用，发现占用最高的是TCP和TCPv6，总共占用了接近三百兆：

正常情况下，这两个东西不可能占用这么大比例。这只能说明，网络流量有异常！！

内核给TCPv6和TCP分配slab的场景

为了搞清楚内核在什么场景下会分配这两块内存好对症下药，所以在内核中定位了相关代码，最后发现是创建TCP套接字的时候分配的。

slab是内核中的的内存分配机制，所有的内存都通过kmem_cache_create创建，而每块被分配的内存块都是有名字的（如上面的TCPv6和TCP）。因此在内核代码中直接搜索：

kmem_cache_create("TCPv6")

不出意料，没有搜索到相关代码。因为根据linux代码的特性，这个字符串肯定是被宏定义代替或者结构体引用了。

于是先搜索"TCPv6"，在net/ipv6/tcpv6_prot中找到了定义：

struct proto tcpv6_prot = {
    .name = "TCPv6",
    // ...
}

整个内核代码中只有这一处出现了关键字段，除此之外没有其他地方有这个字符串，因此肯定一定是哪里引用这个字段。继续通过正则查找kmem_cache_create\(.*->namne，找到：

int proto_register(struct proto *prot, int alloc_slab)
{
    if (alloc_slab) {
        prot->slab = kmem_cache_create(prot->name, prot->obj_size, 0,
                    SLAB_HWCACHE_ALIGN | prot->slab_flags,
                    NULL);
    // ...
    }
}

proto_register是注册协议到内核的协议栈，产生对应协议请求的时候会调用这个方法来创建socket对象，TCPv6和TCP内存块占用内存高，说明肯定是这里走得多了，这就间接说明设备肯定产生了大量连接。

2.3 分析网络流量

分析出流量有异常之后，第一个想到的是不是网络环境有问题，因为上周刚好也查了一个类似的问题：一次孤儿socket过多导致系统异常的问题排查过程。但是抓包分析后发现，流量并没有出现类似的特征，而且设备总共的孤儿socket并不多，这说明两个问题不是同一个原因。

于是只能继续分析了，因为流量特征（各种数据包的占比）都比较正常，所以排查的重点放在的包的内容身上。终于在经过了大量的分析后发现了数据异常：

以上是内网发到我们设备的代理请求，设备地址是10.115.5.2，因为是代理场景，所以目的地址是它，这没有问题。但问题出在了数据包身上，也就是最后一列，可以看到他们都是：

POST http://10.115.5.2/download HTTP/1.1

这个HTTP代理请求是请求代理本机，这是明显有问题的，也是不符合RFC规定的，正常的代理数据包应该是被代理的地址如www.biadu.com，绝不会是10.115.5.2，如：

POST http://www.baidu.com/download HTTP/1.1

以下是一些正常的代理请求：

如果代理的请求是本机，就会导致本机自己再去连接自己的80端口，造成的结果就是设备会多产生一个发往本机nginx的连接。nginx收到请求后因为不存在这个uri资源会返回404到代理进程，代理进程再返回给客户端。流程为：

本来到这里也没有很大的问题，只是会导致本机多一个连接而已。但关键的问题是，返回错误给PC客户端后，客户端会频繁发起重连，产生大量的重试请求。频率有多高呢？从下面的这个抓包截图来看，不到0.5ms的时间内内网就产生了10+个请求：

代理场景并不像路一样由，只要做NAT把地址转换一下发出去就可以了，路由对设备的资源占用并不大。代理场景除了要和内网PC执行三次握手以外，还要主动发起连接请求WAN端，要产生双倍的资源消耗。如此大规模的重连请求，占用了大量的连接资源，足以算得上dos攻击了。因此，可以认为本次问题就是内网的异常连接导致的。

这些异常的请求具体是什么呢，通过分析数据包内容和特征，很容易就能看出是微信的请求，是在请求下载小视频：

三、和微信的交涉

为了确认微信的问题，找微信客服反馈。他们承认确实是有问题，但是并不想改：

四、微信代理存在的问题

微信代理场景目前存在以下问题：

代理数据包构造不正确，也就是上面描述的场景。
微信视频不支持代理，使用代理后无法发起微信视频。
微信传输大文件时，不会经过代理，直接发到了服务端了。
不支持代理长连接。

第三个问题是出在另外一个客户身上，现象上是无法传输超出20M以上的文件。实际上通过抓包分析发现是微信直接绕过了代理，目的地址不是代理设备地址：

而不支持长连接问题就更有意思了，问题现象是微信代理后无法正常收到图片等相关资源，微信给出的反馈竟然是不支持嵌套，嵌套这个词说出来就很有意思了，刚说出来我还琢磨是什么嵌套。最后抓包发现竟然指的是HTTP长连接。

五、吐槽

从技术角度而言，这几个问题实际上并不能算成是问题，调整起来的技术难度并不高。不知道为什么就是不调整，反馈了很多次了。突然想起前两天微信的热搜，面对用户，好像并不“怂”：

【每日打卡】[leetcode+剑指offer] 169-多数元素

作者: 编程我只用CPP
时间: 2020-03-13
分类: 数据结构和算法
评论

【每日打卡】[leetcode+剑指offer] 169-多数元素

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/majority-element

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题也是《剑指offer》原题——面试题39数组中出现次数超过一半的数字。
https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/

一、题目描述

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入: [3,2,3]
输出: 3

示例 2：

输入: [2,2,1,1,1,2,2]
输出: 2

二、题解

2.1 哈希表

使用哈希表的思路：用数字作为key，每遇到一次，值加一。遍历完数字后，找出次数最大的。

思路很简单，时间复杂度O(N)，空间复杂度O(N)，N表示哈希表槽大小。

2.2 排序

因为元素在数组出现一半以上，所以排序后的中位数一定就是目标元素。

使用快速排序时间复杂度O(Nlog(N))，空间复杂度O(1)。

2.3 摩尔投票法

摩尔投票法的核心思想：因为元素出现次数超过一半，所以它出现的次数减去剩余元素出现次数一定是大于0的。基于这个思想，可以使用抵消的办法来消除掉所有非目标元素，然后剩下的就是目标元素了。

可以先随机找一个元素作为标杆，然后往后遍历，这个标杆元素每出现一次，次数加一。只要出现非标杆元素，次数减一。当次数变成0后，重新设置标杆元素，重复上面的过程。直到最后剩下来的元素就是目标元素。

以target表示目标元素，count表示出现的次数。过程描述：

array |[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
target| 7                | 5    | 5          | 7
count | 1, 2, 1, 2, 1, 0 | 1, 0 | 1, 2, 0, 0 | 1, 2, 3, 4

最后剩下来的目标元素是7，也就是我们需要的值。

时间复杂度O(N)，空间复杂度0(1)。

三、代码

using namespace std;

class Solution {
public:
    int majorityElement(vector<int> &nums) {
        int count = 0, x;
        if (nums.empty()) {
            throw length_error("empty array");
        }

        x = nums[0];
        for (auto i : nums) {
            if (count == 0) {
                x = i;
            }
            if (x == i) {
                count++;
            } else {
                count--;
            }
        }

        return x;
    }
};

【每日打卡】[leetcode]1071-字符串的最大公因子

作者: 编程我只用CPP
时间: 2020-03-12
分类: 数据结构和算法
评论

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/greatest-common-divisor-of-strings

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。

返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。

示例 1：

输入：str1 = "ABCABC", str2 = "ABC"
输出："ABC"

示例 2：

输入：str1 = "ABABAB", str2 = "ABAB"
输出："AB"

示例 3：

输入：str1 = "LEET", str2 = "CODE"
输出：""

提示：

1 <= str1.length <= 1000
1 <= str2.length <= 1000
str1[i] 和 str2[i] 为大写英文字母

二、题解

2.1 欧几里得算法

欧几里得算法（GCD）又称为辗转相除法，是用来计算两个整数的最大公因子的算法。

算法描述：

$$\begin{equation} gcd(a, b) = \begin{cases} a & b = 0\\ gcd(b, a \bmod b) & b \ne 0 \end{cases} \end{equation}$$

通过表达式能看出，算法是通过对两个数互相取模来计算得到最大公因子，也因此叫做辗转相除法。

算法依赖定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。

证明：

假设a=kb+r，四者皆为整树，r表示a%b的余数。假设m是a和b的最大公约数，那么可以推算得到：

a=kb+r  ==>  r=a-kb  ==>  r/m=a/m-kb/m;

最后一个表达式表示等式两边同时除以公约数，因为m是a和b的约数，所以a/m和kb/m都是整数，两者的差值也是整数。间接就说明r/m也是整数，一旦r/m是整数，那么m也是r的约数，即m也是a%b的余数的约数。证明了定理。

2.2 本题解析

在知晓了上面的定理后，就可以使用GCD算法来计算这个问题。只要对两个字符出的长度求出最大公约数即可。

问题的关键点在于两者是否存在最大公约数，假设用{}表示公约数，存在公约数的两个字符串格式一定是：

{}{}{}   {}{}

如果不存在公约数，两个字符串格式就是：

{}{}{}   }{ 或 }{}

能看出的规律：如果存在公约数，str1+str2=str2+str1，因为两个字符串都是由公因子组成，相加起来只是多个公因子的组合而已。而如果不存在公约数，两者相加后一定不相等，因此基于这一点就能判断字符串是否有公因子了。

三、代码

class Solution {
public:
private:
    int gcd(int a, int b) {
        if (b == 0)
            return a;
        else
            return gcd(b, a % b);
    }
public:
    string gcdOfStrings(string str1, string str2) {
        if (str1 + str2 != str2 + str1)
            return "";

        return str1.substr(0, gcd(str1.size(), str2.size()));
    }
}

测试案例：

#include <gtest/gtest.h>
TEST(leetcode, demo) {
    Solution s;
    EXPECT_EQ("ABC", s.gcdOfStrings("ABCABC", "ABC"));
    EXPECT_EQ("AB", s.gcdOfStrings("ABABAB", "ABAB"));
    EXPECT_EQ("", s.gcdOfStrings("LEET", "CODE"));
}

[leetcode]1013-将数组分成和相等的三个部分

作者: 编程我只用CPP
时间: 2020-03-11
分类: 数据结构和算法
评论

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/partition-array-into-three-parts-with-equal-sum

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。

形式上，如果可以找出索引i+1 < j且满足(A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1])就可以将数组三等分。

示例1：

输入：[0,2,1,-6,6,-7,9,1,2,0,1]
输出：true
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

示例2：

输入：[0,2,1,-6,6,7,9,-1,2,0,1]
输出：false

示例3：

输入：[3,3,6,5,-2,2,5,1,-9,4]
输出：true
解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

二、题目解析

要求三个相等的和，首先要知道的是每一段的和是多少，这就要先计算整个数组的总和。

如果总和不能整除3，可以直接返回false，因为输入的都是整数，每一段的和也都是整数。
如果总和能整除3，从头开始遍历数组，每找到一个满足条件的计数加1，直到最后如果计数为3的话就说明是存在符合条件的区间。

一个需要额外注意的地方是：

上面的数组中，总和是0，三个分区间的和也应该是0。但是实际上，按照上面的算法，计数为4，这个场景怎么处理？实际上，只要把最后一个区间归类到第三个区间就可以了，只要他们两者的和满足条件就行了。

而第三个区间是满足条件的，这种情况下，只要从第四个满足条件的区间开始，后面所有元素的总和不会对第三个区间的和造成影响的时候（即后面所有元素和为0），数组是满足条件的。

三、代码

class Solution {
public:
    bool canThreePartsEqualSum(vector<int> &A) {
        int i, cnt = 0, sum, tmp_sum, n;
        // 计算所有的总和
        for (auto x: A) {
            cnt += x;
        }

        // 如果总和不能整除3，直接返回false
        if (cnt % 3 != 0)
            return false;
        // 计算每一段的和
        sum = cnt / 3;

        // 找到三段符合条件的和
        tmp_sum = 0, n = 0;
        for (i = 0; i < A.size() && n < 3; i++) {
            tmp_sum += A[i];
            if (tmp_sum == sum) {
                // 每找到一段，tmp_sum置零，重新开始找
                n++;
                tmp_sum = 0;
            }
        }

        // 已经得到了三段满足条件的和，但是数组可能并没有遍历完
        // 只有在剩余元素的总和是0的条件下才认为满足条件
        tmp_sum = 0;
        for (; i < A.size(); i++) {
            tmp_sum += A[i];
        }

        return n == 3 && tmp_sum == 0;
    }
};

复杂度分析

时间复杂度：O(N)
空间复杂度：O(1)

单元测试案例：

TEST(Solution, leetcode_1) {
    Solution s;
    vector<int> v{0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1};
    EXPECT_TRUE(s.canThreePartsEqualSum(v));
}

TEST(Solution, leetcode_2) {
    Solution s;
    vector<int> v{0, 2, 1, -6, 6, 7, 9, -1, 2, 0, 1};
    EXPECT_FALSE(s.canThreePartsEqualSum(v));
}

TEST(Solution, leetcode_3) {
    Solution s;
    vector<int> v{3, 3, 6, 5, -2, 2, 5, 1, -9, 4};
    EXPECT_TRUE(s.canThreePartsEqualSum(v));
}

TEST(Solution, leetcode_4) {
    Solution s;
    vector<int> v{10, -10, 10, -10, 10, -10, 10, -10};
    EXPECT_TRUE(s.canThreePartsEqualSum(v));
}

HTTP代理

作者: 编程我只用CPP
时间: 2020-03-08
分类: 计算机网络
评论

一、HTTP代理

HTTP代理的实现很简单，和普通的HTTP请求差别不大，只要在请求行的uri路径中加上实际请求的host就可以了：

代理服务器收到这个请求后，会主动请求uri中的host地址（不是请求头部的Host字段中的值），然后去掉这部分构造成一个普通的HTTP请求发送到服务端。服务端响应后的数据也直接发回到客户端。

过程图解：

长连接的场景

当连接是长连接的时候，后面的请求可以不用加上http://ifeng.com，直接和普通的GET请求一样就可以了。

二、HTTPS代理

HTTPS相较于HTTP代理不同的是：HTTPS代理是加密的，代理无法从HTTP请求行中获取到host。因此，执行HTTPS代理前，客户端要先主动发起一个CONNECT请求，表示要连接到的服务端。然后代理程序和服务端建立连接，把后续所有的客户端数据包都发往服务器。

以下是一个HTTPS代理请求的数据包：

过程分解：

客户端发起CONNECT连接，明确告诉代理程序，帮我连接www.ifeng.com的443端口。
服务端发起对www.ifeng.com:443的连接，成功后给客户端返回HTTP 200。
客户端开始建立HTTPS连接，执行Clinet-Hello过程。

图解：

整个代理过程中，除了多了个CONNECT流程以外，后面所有的请求交互过程和普通HTTPS连接是一样的。

2020年3月

一、题目描述

二、题解

三、代码

一、题目描述

二、题解

三、代码

一、题目描述

二、题解

三、代码

一、基本用法

二、操作API

2.1. APPEND

2.2. STRLEN

2.3. GETRANGE

三、数据运算

3.1 INCR和DECR

3.2 INCRBY、DECRBY和INCRBYFLOAT

四、实现原理

4.1 int编码

4.2 raw和embstr编码

一、问题描述

二、排查过程

2.1 分析负载和CPU

2.2 分析内存占用

2.3 分析网络流量

三、和微信的交涉

四、微信代理存在的问题

五、吐槽

【每日打卡】[leetcode+剑指offer] 169-多数元素

一、题目描述

二、题解

2.1 哈希表

2.2 排序

2.3 摩尔投票法

三、代码

一、题目描述

二、题解

2.1 欧几里得算法

2.2 本题解析

三、代码

一、题目描述

二、题目解析

三、代码

一、HTTP代理

二、HTTPS代理

最新文章

最近回复

分类

归档

其它