Hiyoung'blog

飞牛NAS备忘录
发表于|更新于|软件NAS

DNS拦截与Nginx设置

在本地网络中使用nas应用一般都是直接访问IP地址使用，使用DNS拦截可以在本地使用域名访问相应的应用
在 NAS 或家庭局域网 中，DNS 拦截非常有用。
比如:

  • emby.hiyoung.icu → 永远指向 NAS 局域网 IP
  • 让 Cloudflare DDNS 只影响公网，而内网访问时走本地 IP

下面是操作步骤：

  1. 飞牛Nginx操作
    飞牛OS自带Nginx，我们想要去使用nginx-UI去使用web管理反代，所以首先要对飞牛进行一些操作
    飞牛默认会监听80和443端口，要对他进行一些设置，有两个方法可以解决
    • 使用Docker安装的Nginx可以映射到其他的端口，例如：8080:80，但是这样设置后使用域名访问还是需要加上8080的端口才可以，因此不推荐。
    • 在系统设置→安全性→端口设置→高级设置里把重定向80与443端口的勾去掉，确认之后就释放了80，443端口，因为飞牛系统默认的nginx官方加了防篡改，因此在/usr/trim/nginx/conf/nginx.conf路径中直接修改配置文件是不生效的。
  2. 安装nginx-ui
    1. 确定80和443端口释放之后就可以安装nginx-ui了，下面使用docker compose安装
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      version: '3.1' 
      services: 
          nginx-ui:
              image: uozi/nginx-ui:latest
              container_name: nginx_UI
              volumes:
              - /vol1/1000/docker/nginx/nginx:/etc/nginx          #编辑为docker安装的路径
              - /vol1/1000/docker/nginx/nginx-ui:/etc/nginx-ui    #编辑为docker安装的路径
              - /vol1/1000/docker/nginx/www:/www                  #编辑为docker安装的路径
              environment:    
              - NGINX_UI_IGNORE_DOCKER_SOCKET=true
              ports:
              - 80:80
              - 443:443
              restart: always
      安装好后在80端口启动即可
    2. 操作过程
      1. 进入nginx ui，网站管理->添加站点，配置名称中填写这个服务的名字
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        其他不用修改，点击下一步即可
        2. 回到**网站管理->站点列表**，就可以看到你刚才创建的配置了
        点击**编辑->右边搜索配置模板->反向代理->查看**，到最下面找到Locations字段
        ```yaml
         proxy_http_version 1.1;
         proxy_set_header Upgrade $http_upgrade;
         proxy_set_header Connection $connection_upgrade;
         client_max_body_size 1000m;
         proxy_redirect off;
         proxy_set_header Host $host;
         proxy_set_header X-Real-IP $remote_addr;
         proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
         proxy_set_header X-Forwarded-Proto $scheme;
         proxy_set_header Forwarded $proxy_add_forwarded;
         proxy_pass http://127.0.0.1:9000/;  #edit
        需要将proxy_pass http://127.0.0.1:9000/; 修改为proxy_pass http://172.17.0.1:docker应用的端口号/;

        这里将要将IP设置为172.17.0.1，这是docker默认的网关
        点击添加即可。

  3. 路由器设置
    进入路由器后台，每个路由器可能不太一样，我这里是openwrt。
    在网络->DHCP/DNS->自定义挟持域名，这里要注意，连接网络的设备DNS服务器要是路由器才可以，一般默认都是路由器。

至此，在内网中使用DNS劫持进行内网重定向设置完成。

设置windows本地访问并挂载盘符

在飞牛中设置smb访问权限，注意这里飞牛的系统如果在我的文件下直接新建文件夹会导致在smb共享时无法访问所有文件夹，所以在建立文件时建议建立一个大的文件夹，将所有文件放在此文件夹下。

设置完成后，回到windouws。
使用win+R，进入cmd，输入以下命令：

1
2
3
4
net use  //查看当前所有映射
net use * /delete //删除所有映射，如果没有可以不执行
net use Z: \\192.168.1.10\samba /user:用户名 密码 /persistent:yes
explorer.exe Z:

命令解释
映射到盘符Z， \192.168.1.10\samba 这里是nas的smb路径自己设置即可
/user:用户名 密码 这里填写nas的管理员账号和登陆密码

完成以上步骤之后就可以在资源管理器中查看nas已经被映射为Z盘了，有一定概率资源管理器缓存没刷新，强制重启一下资源管理器即可

nas飞牛OS
安卓实用软件记录
发表于|更新于|软件安卓

强制旋转屏幕

针对一些软件不对平板进行优化，只能选择一些软件来强制旋转软件的方向:

强制旋转屏幕

Android安卓软件
github pages 使用自定义域名
发表于|更新于

暂定 未完成
https://www.daxiaju.net/2023/11/30/github-pages-custom-domain/

hexo引用站内文章
发表于|更新于|前端网站建设

语法

基本的语法结构如下：

1
{% post_link 文件夹名/文章名字 %}

如果没有放在文件夹中直接使用文章名字也是可以的
1
{% post_link 文章名字 %}

例如：
站内文章：使用Git实现hexo多端同步

除了直接使用之外，也可以自定义链接的标题

1
{% post_link 文件夹名/文章名字 自定义的链接标题%}

  • 如果自定义的链接标题留空，则自动使用文章标题

站内文章：点击这里学习新知识

hexo
MacOS上配置Hexo教程
发表于|更新于|前端网站建设

前言

最近买了台Macbook，之前一直使用的都是Win机子，换到mac后又是一个重新学习的过程。
当然拿到电脑后第一件事就是把我的博客同步到mac上来，然而由于mac和win的环境配置有一定区别，也是折腾了一段时间才搞好
今天终于是把环境配置好了，遂记录一篇如何在macos上配置hexo并多端同步。

环境配置

macos与win的一大区别就是环境配置工作，我前几次失败也都是倒在环境配置这一步，下面是操作步骤。
主要教程也是参考网上别人的方法：mac环境下使用hexo搭建个人博客
本文也记录一些本人安装时遇到的一些问题和解决方法。

准备工作

安装 Homebrew

一开始我是并不想使用Homebrew包管理器的，觉得能直接装就直接装了，多装个东西反而麻烦。但是在查找了多方教程后发现大多数人在mac上使用的都是Homebrew，所以最后还是选择了使用这个包管理器。

  1. 如果网络环境良好（不在中国大陆），可以略过设置环境变量的步骤并直接使用正常的安装脚本：

    1
    /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"

  2. 如果在大陆的话可以换成国内源来安装（即使是在大陆的玩家使用代理的话也有一定可能导致安装失败，毕竟网络问题是最玄学的了）
    在中国大陆，可以使用镜像源安装 Homebrew，下面以中科大镜像源为例。

设置环境变量：

1
2
3
4
export HOMEBREW_BREW_GIT_REMOTE="https://mirrors.ustc.edu.cn/brew.git"
export HOMEBREW_CORE_GIT_REMOTE="https://mirrors.ustc.edu.cn/homebrew-core.git"
export HOMEBREW_BOTTLE_DOMAIN="https://mirrors.ustc.edu.cn/homebrew-bottles"
export HOMEBREW_API_DOMAIN="https://mirrors.ustc.edu.cn/homebrew-bottles/api"

运行中科大 Homebrew 安装脚本：
1
/bin/bash -c "$(curl -fsSL https://mirrors.ustc.edu.cn/misc/brew-install.sh)"

安装node.js & Git

hexo 主要就是使用Node.js和Git工作的，所以使用Homebrew去安装这两个包即可
Homebrew安装完成后，安装 Git 和 Node.js：

1
2
brew install git   
brew install node   // npm随node安装

测试一下是否都安装完成

1
2
3
npm -v
node -v
git --version

出现npm、Node.js和git的版本号即代表安装成功。

MacOS上配置Hexo教程1

安装 Hexo

这里可以参考站内文章：使用Git实现hexo多端同步
从在新电脑上的操作 开始操作即可

注意：
在macos上执行生成 SSH Key之后生成的密钥和win的保存路径不同

如果已经创建过会出现 Overwrite (y/n)? n提示可以输入 n。
没有创建过的话三个回车就好（不设置密码），执行完成后会在~/.ssh/id_rsa.pub目录下生成 需要使用的 key，也就是公钥。（使用 Command+Shift+G 可以跳转）

到账户主文件夹下同时按 Command+Shift+. 显示隐藏文件，找到.ssh文件夹，打开id_rsa.pub，将里面的内容全部复制。

完成

按照以上步骤完成之后即可同步其他端的文章和设置了，十分的方便和便捷。
如果在配置中出现了网络问题可以尝试关闭或者开启代理重试一下，也可以在
搭建hexo错误记录中查找一下是否有相同的问题

配置个人域名

本步骤计划单独使用一篇文章来记录，因为之前在尝试换绑域名时也遇到了许多问题，值得单独开篇文章来记录

hexoMacOS
c++ string
发表于|更新于|学习笔记cpp

字符串和字符数组

cin.getline()与getline()的区别

Cpp的STL-string-1

cin.getline要使用字符数组做参数，getline要使用字符串做参数

  • cin.getline(字符数组,读取的长度);
  • getline(cin,字符串名)
1
2
3
4
5
6
7
8
   char name[20];
   string s;
cin.getline(name,20); //OK 
   getline(cin,name);    //ERROR

   cin.getline(s,20);    //ERROR
   getline(cin,s);       //OK

string 与 stringstream

参考资料：

1
2
3
string s1;
s1 = "hello";
s2 = 'K';

拼接

我们一般常用+和+=运算符对 string 对象执行字符串的连接操作。除此之外，也可以使用 append 成员函数进行拼接

1
2
3
4
5
6
7
8
string s1("123"), s2("abc");
s1 = s1 + "ABC"     //s1 = "123ABC"
s1 += s2;           //s1 = "123abc"
s1.append(s2);      // s1 = "123abc"
s1.append(s2, 1, 2); // s1 = "123bc"，从s2下标1开始，长度为2拼接到s1
s1.append(3, 'K');  // s1 = "123bcKKK"
s1.append("ABCDE", 2, 3); // s1 = "123CDE"，添加 "ABCDE" 的子串[2,5)
s1.push_back('A');      //s1 = "123A" 添加一个字符 'A' ，参数必须是字符形式

比较

字符串的比较默认是按照字典序来比较的，并且遵从两个规则：1. 逐个比较 2. 不同即停
string 类还有 compare 成员函数，也可用于比较字符串
常用的比较符：<、<=、==、!=、>=、>

ompare 成员函数有以下返回值：

  • 小于 0 表示当前的字符串小；
  • 等于 0 表示两个字符串相等；
  • 大于 0 表示当前的字符串大。
1
2
3
4
5
6
7
string s1("hello"), s2("hello, world");
int n = s1.compare(s2);
n = s1.compare(1, 2, s2, 0, 3); //比较s1的子串 (1,2) 和s2的子串 (0,3)
n = s1.compare(0, 2, s2); // 比较s1的子串 (0,2) 和 s2
n = s1.compare("Hello");
n = s1.compare(1, 2, "Hello"); //比较 s1 的子串(1,2)和"Hello”
n = s1.compare(1, 2, "Hello", 1, 2); //比较 s1 的子串(1,2)和 "Hello" 的子串(1,2)

string常用的成员函数

find()函数

使用方法： s.find(sub)，有返回值：无符号整数

示例代码：

1
2
3
4
5
6
7
8
9
10
//find函数返回类型size_type
string s = "1a2b3c4d5e6f7g8h9i1a2b3c4d5e6f7g8ha9i";
string sub;
string::size_type pos;

pos = s.find(sub);

if(s.find(sub) != string::npos){
    ...
}

  • Q1: find函数的返回类型
    string::size_type 是一个与实现相关的无符号整数类型，通常与 size_t 相同，用来表示字符串的长度和下标等
    它定义为与unsigned型（unsigned int获unsigned long）具有相同含义
    与实现相关的意思是它在不同的机器上，长度是可以不同的，并非固定的长度，只要你使用了这个类型，就使得你的程序适合这个机器

  • Q2: != string::npos
    npos表示size_type的最大值，用来表示不存在的位置

  • Q3: find函数的返回值
    如果找到了子串，则find函数的返回值是这个字串在字符串中第一次出现的位置。如果没有找到，那么会返回一个特别的标记string::npos

size() 函数

length 成员函数返回字符串的长度。size 成员函数可以实现同样的功能。
一般用size()多一些

1
2
3
string s1 = "12345";
int len = s1.size(); // 5
int len = s1.length(); // 5

substr() 函数

substr 成员函数可以用于求子串 (n, m)，调用时，如果省略 m 或 m 超过了字符串的长度，则求出来的子串就是从下标 n 开始一直到字符串结束的部分。例如：

1
2
3
string s1 = "hiyoung blog";
string s2 = s1.substr(2, 4); // s2 = "youn"
s2 = s1.substr(2); // s2 = "young blog"

replace() 函数

replace 成员函数可以对 string 对象中的子串进行替换，返回值为对象自身的引用。例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
string s1("Real Steel");
// 基础用法
s1.replace(1, 3, "123456"); //用 "123456" 替换 s1 的子串(1,3)
cout << s1 << endl; //输出 R123456 Steel

// 用法二
string s1("Real Steel");
s1.replace(1, 3, "123456", 2, 4); //用 "123456" 的子串(2,4) 替换 s1 的子串(1,3)

// 用法三
string s2("Harry Potter");
s2.replace(2, 3, 5, '0'); //用 5 个 '0' 替换子串(2,3)
cout << s2 << endl; //输出 HaOOOOO Potter

// 用法四
int n = s2.find("OOOOO"); //查找子串 "00000" 的位置，n=2
s2.replace(n, 5, "XXX"); //将子串(n,5)替换为"XXX"
cout << s2 < < endl; //输出 HaXXX Potter

erase() 函数

erase 成员函数可以删除 string 对象中的子串，返回值为对象自身的引用

s.erase(起始位置,长度);

1
2
3
string s1("Real Steel");
s1.erase(1, 3); //删除子串(1, 3)，此后 s1 = "R Steel"
s1.erase(5); //删除下标5及其后面的所有字符，此后 s1 = "R Ste"

insert() 函数

insert 成员函数可以在 string 对象中插入另一个字符串，返回值为对象自身的引用

1
2
3
string s1("Limitless"), s2("00");
s1.insert(2, "123"); //在下标 2 处插入字符串"123"，s1 = "Li123mitless"
s1.insert(3, s2); //在下标 2 处插入 s2 , s1 = "Lim00itless"
string字符串
二分查找
发表于|更新于|算法二分算法

二分查找算法概述

二分查找很简单吗？或许二分查找的思想是直观的，但是细节才是程序的核心。看看 Knuth 大佬（发明 KMP 算法的那位）怎么说的：

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…

二分代码的框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binarySearch(int[] nums,int target){
    int left = 0;
    int right = ...; // 一般是数组的长度
    while(...){
        int mid = (left + right) / 2;           //普通写法
        //int mid = left + (right - left) / 2;    // 防止溢出
        if(nums[mid] == target){
            ...
        }else if(nums[mid] < target){
            left = ...
        }else if(nums[mid] > target){
            right = ...
        }
    }
    return ...; // 没有找到  
}

这里虽然可以用else来简化代码，但是为了更好的理解二分查找的逻辑，这里还是用了if-else的写法。这样可以保留更多的二分比较的细节，作为初学者来说更易理解。

其中 … 标记的部分，就是可能出现细节问题的地方，当你见到一个二分查找的代码时，首先注意这几个地方。后文用实例分析这些地方能有什么样的变化。

另外声明一下，计算 mid 时需要技巧防止溢出，建议写成: mid = left + (right - left) / 2，可以暂时先不管这个问题，后文会详细解释。

二分查找一个数

二分查找的最基础应用，即给定一个有序数组，查找某个数是否存在，如果存在则返回其索引，否则返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//左闭右闭写法
int binarySearch(int nums[],int target){
    int left = 1;
    int right = n;              //这里数组下标从1开始
    while(left <= right){       // 注意
        int mid = (left+right) / 2;
        if(nums[mid] == target ){
            return mid;
        }else if(nums[mid] < target){
            left = mid + 1;     // 注意
        }else if(nums[mid] > target){
            right = mid - 1;    // 注意
        }
    }

    return -1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//左闭右开写法——推荐使用左闭右开写法
int binarySearch(int nums[],int target){
    int left = 1;
    int right = n+1;              //这里数组下标从1开始
    while(left < right){       // 注意
        int mid = (left+right) / 2;
        if(nums[mid] == target ){
            return mid;
        }else if(nums[mid] > target){
            right = mid;    // 注意
        }else if(nums[mid] < target){
            left = mid + 1;     // 注意
        }
    }

    return -1;
}

Q1:while 循环的条件中是 <= 还是 < ？

在初始化 right 的赋值是数组是最后一个元素的索引，这里使用的数组下标是从1开始的。
如果使用零下标数组，那应该这样写：

1
2
int left = 0;
int right = n-1;    //n-1是数组的最后一个元素索引

使用<=相当于二分查找的区间是左闭右闭的区间，[left,right]，而使用<则相当于左闭右开的区间[left,right)

在以0下标开始的数组来说索引大小为n是越界的。

下面没有特殊说明我们都按照左闭右开区间来说明。
这个算法中使用的是 [left, right) 左闭右开的区间。这个区间就是每次进行搜索的区间，我们不妨称为「搜索区间」(search space)。

什么时候应该停止搜索呢？当然，找到了目标值的时候可以终止：

1
2
if(nums[mid] == target)
    return mid;

但如果没找到，就需要 while 循环终止，然后返回 -1。那 while 循环什么时候应该终止？搜索区间为空的时候应该终止，意味着你没得找了，就等于没找到嘛。

对于左闭右闭的区间：
while(left <= right) 的终止条件是 left == right + 1，写成区间的形式就是 [right + 1, right]，或者带个具体的数字进去 [3, 2]，可见这时候搜索区间为空，因为没有数字既大于等于 3 又小于等于 2 。所以这时候 while 循环终止是正确的，直接返回 -1 即可。

对于左闭右开的区间：
while(left < right)的终止条件是 left == right，写成区间的形式就是 [right, right)

Q2：left和right如何迭代？

有的代码是 right = mid 或者 left = mid，没有这些加加减减，到底怎么回事，怎么判断？

答：这也是二分查找的一个难点，不过只要你能理解前面的内容，就能够很容易判断。

刚才明确了「搜索区间」这个概念，而且本算法的搜索区间是两端都闭的，即 [left, right]。那么当我们发现索引 mid 不是要找的 target 时，如何确定下一步的搜索区间呢？

当然是去搜索 [left, mid - 1] 或者 [mid + 1, right] 对不对？因为 mid 已经搜索过，应该从搜索区间中去除。

那为什么有些是right = mid 或者 left = mid呢？
很明显哪些代码用的是左闭右开的搜索区间

Q3：此算法有什么缺陷？

答：至此，应该已经掌握了该算法的所有细节，以及这样处理的原因。但是，这个算法存在局限性。

比如说给你有序数组 nums = [1,2,2,2,3]，target = 2，此算法返回的索引是2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理的。

这样的需求很常见。你也许会说，找到一个 target 索引，然后向左或向右线性搜索不行吗？可以，但是不好，因为这样难以保证二分查找对数级的时间复杂度了。

Q4：关于左闭右开写法的解释

在了解了左闭右闭写法之后，我们再来看左闭右开的写法

首先，我们先来分析一下右边界 right 的初始值：

  1. 当right=nums.size() 时，初始化的区间就变成了 $[0,right-1]$，也即 $[0,right)$，左闭右开写法
  2. 当right=nums.size()-1时，初始化的区间就变成了 $[0,right]$，左闭右闭写法

在第一种情况下（左闭右开），当 nums[mid] > target 时，需要将区间向左收缩，即 right = mid。
这个做法的逻辑是：既然 mid 位置处大于 target ，而查找区间又是 “ 左闭右开 ”，因此当 right=mid 时，新的查找区间变成了 $[0,mid)$，这样才不会漏掉值。
同理，当 nums[mid] < target 时，需要将区间向右收缩，即 left = mid+1 ，因为在 “ 左闭右开 “ 的区间下，新的查找区间变成 $[mid+1,right)$ 才不会漏掉值。
当目标值不在序列中时，需要将 while 的条件写成 while(left < right) 而不是写成 while(left<=right) ，这样会引起数组越界。

二分上下界

二分查找的上下界问题其实是为了解决有序数组中出现重复数据时会面临的问题
若序列中有重复的元素,那就不能简单的返回其中一个下标了,用户需要的是返回重复元素的起始下标和终止下标,用来表示范围

这里的二分上下界和上文提到的左右侧边界有所不同

定义

二分下界：第一个大于等于，目标元素target的元素
二分上届：第一个大于，目标元素target的元素

  • 举例：现有一个数组nums = [1,2,2,2,3]，数组采用1下标索引
    其中二分下界的下标就是nums[2]，二分上界就是nums[5]
  • 分析:
    数组中现在有重复的元素，二分下界就是这段重复元素的开始位置，上界就是这段重复元素的结束位置的右侧，正好围绕这段重复元素形成了一个左闭右开的区间，即[2,5)(数组下标)

二分查找的下界

上文提过，二分查找的左侧边界就是要查找的 target 元素的相邻相同元素的左侧下标，也就是重复元素的第一次出现下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int lower_bound(int[] nums, int target) {
    // vector数组写法
    // int left = 0;
    // int right = nums.size(); // 注意

    int left = 1;
    int right = n+1;        // 注意
    
    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;    //注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

Q1: 为什么 while(left < right) 而不是 <= ?

用相同的方法分析，因为初始化 right = nums.length 而不是 nums.length - 1 。因此每次循环的「搜索区间」是 [left, right)左闭右开。

二分查找的上界

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int upper_bound(int[] nums, int target) {
    // vector数组写法
    // int left = 0;
    // int right = nums.size(); // 注意

    int left = 1;
    int right = n+1;        // 注意

    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left; // 注意
}

Q1: 最后返回为什么还是left

因为我们要返回的是一个左闭右开的区间，我们这里nums[mid] == target时 left = mid + 1，最后我们返回的是[2,5)的5。如果我们返回的是left-1那就是4（即相同元素的右侧边界），那就不是第一个大于 target的元素了，而是最后一个等于 target的元素了

参考

详解二分查找算法
C++实现二分法详解

算法二分查找
前缀和与差分数组
发表于|更新于|算法前缀和与差分数组

前缀和算法

前缀和主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。

前缀和核心代码

1
2
3
4
5
6
7
int nums[110],prefix[110];
int n;
cin>>n;
for(int i=1;i<=100;i++){
    cin>>nums[i];
    prefix[i] = prefix[i-1] + nums[i];
}

前缀和数组prefix[i] 就代表着 nums[0..i] 所有元素的累加和，如果我们想求区间 nums[i..j] 的累加和，只要计算 prefix[j] - prefix[i-1] 即可，而不需要遍历整个区间求和。

后缀和

后缀和和前缀和类似，只是建立数组的过程不太一样

1
2
3
4
5
6
for(int i=1;i<=n;i++){
    cin>>nums[i];
}
for(int i=n;i>=1;i--){
    sum[i] = sum[i+1] + nums[i];
}

这里的sum数组sum[i]的含义就是 nums[i..n] 的所有元素的累加和

差分数组

差分数组和前缀和思想非常类似，差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。

比如说，我给你输入一个数组 nums，然后又要求给区间 nums[2..6] 全部加 1，再给 nums[3..9] 全部减 3，再给 nums[0..4] 全部加 2，再给…
然后问你，最后 nums 数组的值是什么？

常规的思路很容易，你让我给区间 nums[i..j] 加上 val，最简单的方法就是一个 for 循环给它们都加上。这种思路的时间复杂度是 O(N)，由于这个场景下对 nums 的修改非常频繁，所以效率会很低下。

这里就需要差分数组的技巧，类似前缀和技巧构造的 prefix 数组，我们先对 nums 数组构造一个 diff 差分数组，diff[i] 就是 nums[i] 和 nums[i-1] 之差

这样构造差分数组 diff，就可以快速进行区间增减的操作，如果你想对区间 nums[i..j] 的元素全部加 3，那么只需要让 diff[i] += 3，然后再让 diff[j+1] -= 3 即可

差分数组核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int nums[110],diff[110];
//构建差分数组
for (int i = 1; i <= 100; i++) {
    cin >> numsa[i];
    diff[i] = nums[i] - nums[i-1];//差分数组
}

//给定区间的修改，修改m次
while(m--){
    cin>>l>>r;
    cin>>x;
    diff[l] += x;
    if (r + 1 <= n) { //不越界
        diff[r+1] -= x;
    }
}

//利用差分数组还原数组
for(int i=1;i<=100;i++){
    nums[i] = nums[i-1] + diff[i];
    cout<<nums[i]<<" ";
}

越界判断：
当 r+1 >= diff.length 时，说明是对 nums[i] 及以后的整个数组都进行修改，那么就不需要再给 diff 数组减 val 了。

参考

算法前缀和差分数组
使用Git实现hexo多端同步
发表于|更新于|前端网站建设

前言

最近需要用两台电脑来更新博客，但是用U盘来回拷贝太麻烦而且有点捞，使用开始尝试使用git和github来实现hexo的多端同步
Hexo 本地和部署到Git page上的文件是不同的东西
在执行hexo g命令后，会在public目录下生成网页的静态文件，我们用hexo d上传的文件其实就是public目录下的这些静态文件。如果执行hexo clean，那么public文件夹就会消失。实现多端同步，只要让每台电脑上都有最新的资源文件就行了。

主要参考了以下文章：
利用Github实现hexo多端同步

Hexo在多台电脑上提交和更新

hexo同步原理

  1. hexo博客目录结构说明
    一般而言hexo的目录结构包含下面内容（shell脚本不属于hexo的目录结构）
    使用Git实现hexo多端同步-1
文件夹 说明 是否需要上传github
node_modules hexo需要的模块，就是一些基础的npm安装模块，比如一些美化插件，在执行npm install的时候会重新生成 不需要
themes 主题文件 需要
public hexo g命令执行后生成的静态页面文件 不需要
packages.json 记录了hexo需要的包的信息，之后换电脑了npm根据这个信息来安装hexo环境 需要
_config.yml 全局配置文件 需要
.gitignore hexo生成的默认的.gitignore模块，不需要上传的文件需要写入到.gitignore中 需要
scaffolds 文章的模板 需要
.deploy_git hexo g自动生成的 不需要
  1. 同步原理
    主要思路是利用git分支来实现hexo的同步。
    hexo生成的静态页面文件默认放在master分支上，这是由_config.yml配置文件所决定的
    你可以在全局配置文件_config.yml中找到这么一段
    1
    2
    3
    4
    5
    6
    # Deployment
    ## Docs: https://hexo.io/docs/one-command-deployment
    deploy:
      type: git
      repo: git@github.com:username/username.github.io.git
      branch: master

因此每当我们执行hexo d的时候，hexo都会帮我们把生成好的静态页面文件推到master分支上。

在我们第一次部署好博客的时候，github给我们创建的唯一一个分支就是master分支，同时也是默认分支。默认分支就意味着每次我们执行git clone 仓库地址或者git pull 仓库地址拉取的是默认分支的代码。

但是执行hexo d 对应的分支和默认分支是没有关系的，因为这是由配置文件决定的，配置文件写的哪个分支就是哪个分支。

因此，hexo生成的静态博客文件默认放在master分支上。hexo的源文件（部署环境文件，书写的MD源文件）可以都放在source分支上（可以新创建一个source分支或者hexo分支），分支的名字可以随意。然后把Hexo分支设置成默认分支。有小伙伴可能会担心默认分支的改变会不会影响到原来的网页的正常显示，其实如果是用GitHub Pages对博客进行托管的话也很简单，第一次搭建博客默认使用master分支作为页面。在下图所示的设置里可以找到。如果不小心搞错了只要把分支设置成静态页面对应的分支就好了。

  • 新建一个source分支用于存放hexo的源文件
    使用Git实现hexo多端同步-2

  • 把source分支设置成默认分支，用来存放源文件，master分支依然存放静态文件。
    使用Git实现hexo多端同步-3

在老电脑上，我们需要把必要的源文件push到source分支。换新电脑时，直接git clone 仓库地址此时会从source分支下载源文件，剩下的就是安装hexo环境，在新电脑上就可以重新生成静态页面了，并且因为配置文件clone下来，deploy配置依旧是master分支，所以在新电脑上执行hexo d还是会把更新过后的静态文件推送到master分支上。

由于master分支和source分支实际上是相互独立的两个普通的分支，所以我们源文件和静态页面的更新也是相互独立的，故而需要手动分别执行
下面git 代码来更新源文件,然后执行hexo d更新静态页面。

1
2
3
git add . 
git commit -m "Description"
git push

操作步骤

老电脑上的操作

  1. 按照上文操作建好新source分支并设为默认分支
  2. 打包将要推送到GitHub上的原始文件
    1. clone该仓库到本地（clone的是hexo默认分支）
    2. 下载的文件夹里仅留下 .git 文件夹，其他的文件都删除
    3. 找到hexo的原位置，将hexo文件夹内除.deploy_git 以外的文件都复制到clone下来的文件夹中（这里的文件名应该是你仓库的名字）
      tips:
    4. 现在clone下来的文件夹内应该有个.gitignore文件，用来忽略一些不需要的文件，表示这些类型文件不需要git。如果没有，右键新建，内容如下： 
      1
      2
      3
      4
      5
      6
      7
      .DS_Store
      Thumbs.db
      db.json
      *.log
      node_modules/
      public/
      .deploy*/
    5. 如果你是使用git clone下载的主题文件，那么需要把theme主题文件夹里的 .git 也删除。因为git不能嵌套上传，最好是显示隐藏文件，检查一下有没有，否则上传的时候会出错，导致你的主题文件无法上传，这样你的配置在别的电脑上就用不了了。
  3. 将clone并修改以后的文件夹推送到远程库
1
2
3
git add .
git commit –m add_branch
git push

此时已经成功将整个网站推送到了远程库的默认分支source

将hexo文件push到github仓库

至此，网站部署至master分支，整个网站备份至hexo分支。当网站的配置或文章修改后都要将远程仓库更新。首先，依次执行

1
2
3
4
5
6
7
git add .
git commit -m ChangeFiles（更新信息内容可改）
git push （或者git push origin source）

#保证hexo分支版本最新。然后正常执行部署hexo
hexo clean
hexo d -g

在新电脑上的操作

配置SSH密钥

  1. 首先在新设备上安装node.js和git并且生成SSH Key
1
2
git config --global user.name "你要设置的名字"
git config --global user.email "你要设置的邮箱"
  1. 之后生成SSH密钥：
    1
    ssh-keygen -t rsa -C "你刚刚设置的邮箱"

如果不需要设置密码的话，连续三个回车就好了。在这之后会得到两个文件： id_rsa 和 id_rsa.pub
找到id_rsa.pub文件(默认位置在C盘，一般也不建议改动位置)，用记事本打开，复制其内容。

Win路径： C:\Users\（你的用户名）.ssh
MacOS路径：/Users/（你的用户名）/.ssh/

在GitHub上添加SSH密钥

登录GitHub，在Settings里面选择 SSH and GPG keys ，然后点击 New SSH Key
这里应该包含你新老两个电脑的SHH密钥，如果你有多个电脑那就应该都要加入

完成之后测试一下，在git bash输入：

1
ssh -T git@github.com

image

安装hexo

在新设备上找到要存在博客文件的位置，然后clone仓库(仓库地址直接复制GitHub的SSH地址即可)：

1
git clone git@github.com:username/hexo

进入文件夹，执行如下命令配置Hexo：

1
2
npm install -g hexo-cli
npm install

这里在新设备上一定要先用git clone来获取文件，如果是先安装hexo的话可能会因为hexo的版本不一致导致无法同步

在完成上面操作之后就是正常的使用 hexo d -g来部署网页了

每次写完博客之后，需要顺便将修改push到github仓库中，操作和上面一样
每次转移到另一台设备的时候，先执行git pull命令就可以同步github仓库中的最新文件，然后就可以愉快地写博客了

写在最后

学计算机学到现在更能深刻的理解只有有需求才会去学习，早在一两年前刚开始折腾个人博客的时候就听说过git来同步很好用，但是当时觉得只会用一台设备没必要折腾，而且天然的会有一些畏惧心理。
最近因为有多台设备来写博客的原因才又把git捡回来了，之前觉得难以理解的操作现在尝试一遍后倒也觉得没那么难，但是回头想来如果没有之前的一点点尝试而是一开始就想一步到位也是很难的事情。
所以，在学习使用新工具的时候不要强求自己一步到位能彻底掌握，在使用的时候也不必强求一定要做到完美才去使用。发现痛点再去尝试解决不免也是一种好的方法，在学习中一定要及时的给自己一点正反馈。

githexo同步
高精度算法
发表于|更新于|算法高精度

高精度问题

高精度主要是解决处理大整数时的问题，这里的整数范围要超过longlong。
高精度问题的核心就是使用字符串去模拟加法、减法、乘法、除法运算

高精度加法

基本

使用三个数组a[],b[],c[]存储
模拟加法竖式：累加 进位 留位

  • 累加： c[i] += a[i] + b[i] ——>必须要累加之前的进位，使用 += //累加进位和对应位置的数字

  • 进位：c[i+1] = c[i] / 10;

  • 留位：c[i] %= 10;

Q1：假设正整数A的长度为n,正整数B的长度为m，那么A+B的长度最大为多少？最小为多少？

  • A1： 长度最大：max(n,m)+1 长度最小：max(n,m)

算法步骤

  1. 高精度数的读取与存储：使用字符串方式读取，然后将每一个字符转为整数，逆向存储到一个整型数组中
  2. 模拟加法操作：通过数组下标模拟两个加数中每一个为上数的加法（累加、进位、留位）
  3. 去除前导0，逆向重组（因为之前是逆向加，再反过来）

高精度加法函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// a,b数组用于存储A,B两个加数，c数组用于存储相加之和
int a[200+10],b[200+10],c[200+10];

string Add(string as,string bs){
    //清空a,b,c数组
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));

    //求出as bs字符串的长度
    int alen = as.size(),blen = bs.size();
    int clen = max(alen,blen) + 1;

    //将字符串转为整型数组，并且逆向存储
    for(int i=1; i<=alen; i++)
        a[i] = as[alen - i] - '0';
    for(int i=1; i<=blen; i++)
        b[i] = bs[blen - i] - '0';

    //模拟加法计算：累加 进位 留位
    for(int i=1; i<=clen; i++){
        c[i] += a[i] + b[i];    //一定要使用'+='累加进位
        c[i+1] = c[i]/10;   //进位
        c[i] = c[i]%10;     //留位
    }

    //去除前导0
    //clen>1：如果只有一位数字0要保留，所以只到第二位
    while(c[clen] == 0 && clen>1)
        clen--;

    //逆向重组
    string cs = "";
    for(int i=clen;i>=1;i--){
        cs += c[i] + '0';
    }

    return cs;
}

高精度减法

基本

  1. 如果a[i] < b[i]：说明a[i] 需要向a[i+1]借位：
    1
    2
    a[i+1]--;
    a[i]+=10;
  2. 模拟减法：c[i] = a[i] - b[i];
  3. 高精度减法的程序计算中都默认a 是大于 b来计算的，如果实际情况是a < b，那么只需要交换一下a，b即可
  4. 下面提到的a、as都是指减法运算中较大的那一个（被减数），b、bs同理都是值减数

Q1: 如果a[i+1] == 0，这样借位会不会有问题

  • A1： 不会，因为最多只会借一位。a[i+1]被借位后等于-1，因为a>b(在模拟计算的算法中都转化为a>b来计算，后文详解)，a[i+1]还可以向a[i+2]借位。借位后a[i+1] == 9，而b[i+1]最大也才为9。

算法步骤

  1. 高精度数的读取与存储：使用字符串方式读取，然后将每一个字符转为整数，逆向存储到一个整型数组中
  2. 模拟减法计算：相同位置进行相减，不够减时向高位借位
  3. 去除前导0，再逆序输出

Q1：两个长整数a,b，并且a>b，长度分别为n,m，那么c = a-b的长度最长为多少？

  • A1：n

Q2：两个正整数字符串as,bs，如何判断as和bs的大小（也即a和b的大小）？

  • A2 ：if( as.size() < bs.size() || (as.size() == bs.size() && as < bs)) 成立，那么说明 as < bs ---> 长整数a < b

Q3：如果a<b，如何计算a-b的值呢？

  • A3： 交换a和b的值，然后计算a-b，结果输出一个负号

计算高精度减法函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
int a[200+10],b[200+10],c[200+10];
string Sub(string as,string bs){
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));

    string cs = "";
    //预处理，比较as和bs的大小，来确定正负号和决定是否交换
    // 处理后要求as比bs大，计算都默认as比bs大
    if(as.size() < bs.size() || (as.size() == bs.size() && as < bs)){
        cs += '-';  //结果字符串加一个负号
        as.swap(bs);
    }

    int alen = as.size(),blen = bs.size();
    int clen = alen;    //因为as是较大的数，

    //字符串转整型数组，逆序存储
    for(int i=1;i<=alen;i++)
        a[i] = as[alen - i] - '0';
    for(int i=1;i<=blen;i++)
        b[i] = bs[blen - i] - '0';
    //模拟减法
    for(int i=1;i<=clen;i++){
        //模拟a[i]向a[i+1]借位
        if(a[i]<b[i]){
            a[i+1]--;
            a[i] += 10;
        }
        c[i] = a[i] - b[i];
    }

    //去除前导0
    while(c[clen]==0 && clen>1) clen--;

    //逆向重组
    for(int i=clen;i>=1;i--){
        cs+=c[i] + '0';
    }

    return cs;
}

int main(){
    string as,bs,cs;
    getline(cin,as);
    getline(cin,bs);
    cs = Sub(as,bs);
    cout<<cs;

    return 0;
}

高精度乘法

基本

  1. 本质上还是使用字符串来模拟整数的乘法计算过程

$\qquad\qquad\qquad b_3 \qquad\qquad\qquad b_2 \qquad\qquad\qquad b_1$
$\times\qquad\qquad\qquad\qquad\qquad\qquad a_2 \qquad\qquad\qquad a_1$
$—————————————————————————$
$\qquad\qquad\qquad b_3\ast a_1 \qquad\qquad b_2\ast a_1 \qquad\qquad b_1\ast a_1$
$\quad b_3\ast a_1 \qquad b_2\ast a_1 \qquad\qquad b_1\ast a_1$
$—————————————————————————$
$\qquad c_4 \quad\quad\qquad c_3 \qquad\qquad\qquad c_2 \qquad\qquad\qquad c_1$

  1. 观察式子的下标可以发现 c[i+j-1] += a[i]*b[j]

高精度乘法算式的模拟

  1. 下面的模拟是按照乘法结果的每一行来模拟的，即先把 $a_1$ 与b相乘的加到c中去，再把 $a_2$ 与b相乘的加到c中去
    1
    2
    3
    4
    5
    6
    7
    for(int i=1;i<=alen;i++){
        for(int j=1;j<=blen;j++){
            c[i+j-1] += a[i]*b[j];  //前一项的进位也加在c[i+j-1]中
            c[i+j] += c[i+j-1] / 10;    //因为是要处理多行，所以可能会有多次进位
            c[i+j-1] %= 10;     //留位
        }
    }

Q1：设整数A的长度为n，整数B的长度为m，那么A*B的长度最大为多少，最小为多少

  • A1： A*B的长度最长不会超过n+m，最短不会低于max(n,m)

算法步骤

时间复杂度O(n*m)

  1. 高精度数的读取与存储：使用字符串方式读取，然后将每一个字符转为整数，逆向存储到一个整型数组中
  2. 模拟乘法计算
  3. 去除前导0
  4. 逆序重组

高精度乘法函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const int N = 210;
int a[N],b[N],c[N+N];
string Mult(string as,string bs){
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));

    string cs = ""; //不能写成string cs = " ";
    int alen = as.size(),blen = bs.size();
    int clen = alen + blen;
    // 字符串逆序转为整型数组
    for(int i=1;i<=alen;i++)
        a[i] = as[alen - i] - '0';
    for(int i=1;i<=blen;i++)
        b[i] = bs[blen - i] - '0';

    //模拟乘法算式
    for(int i=1;i<=alen;i++){
        for(int j=1;j<=blen;j++){
            c[i+j-1] += a[i]*b[j];
            c[i+j] += c[i+j-1] / 10;
            c[i+j-1] %= 10;
        }
    }

    while(c[clen] == 0 && clen>1)
        clen--;
    for(int i=clen;i>=1;i--){
        cs += c[i] + '0';
    }

    return cs;
}

高精度除法（长数/短数）

这里的高精度除法指的是一个长数（被除数）和一个短数（除数）做高精度除法

基本

  1. 将长数做字符串处理转为整数存入数组，但与高精度加减法和乘法不同，除法的长数不需要做逆向存储
  2. 模拟的过程是从长数的高位开始与除法进行除法与取模 
    1
    2
    3
    4
    5
    6
    int r=0;
    for(int i=1;i<=clen;i++){
        r = r*10 + a[i];    //构造被除数,依次称10进位
        c[i] = r/x; //得到商
        r %= x;    //除剩的余数再进入到下一轮除法
    }
    Q1：设长整数A的长度为n，短整数B的长度为m，那么A/B的长度最大为多少，最小为多少
  • A1： A/B的长度最长不会超过n，最短为1

算法步骤

  1. 高精度数的读取与存储：使用字符串方式读取，然后将每一个字符转为整数，正向存储到一个整型数组中
  2. 从高位开始进行模拟除法计算
  3. 去除前导0
  4. 正序重组

高精度除法函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
const int N =10000+10;
int a[N],c[N];

string Div(string as,int x){
    memset(a,0,sizeof(a));
    memset(c,0,sizeof(c));

    int alen = as.size();
    int clen = alen;

    //正向存储
    for(int i=1;i<=alen;i++){
        a[i] = as[i-1] - '0';
    }

    int r=0;
    for(int i=1;i<=clen;i++){
        r = r*10 + a[i];
        c[i] = r/x;
        r %= x;
    }

    //去除前导0，但不到clen
    int k=1;
    while(c[k] == 0 && k<clen){
        k++;
    }

    string cs="";
    for(int i=k;i<=clen;i++){
        cs += c[i] + '0';
    }

    return cs;
}

求余数

同求商类似，最后只需要返回r即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int N =10000+10;
int a[N],c[N];

int Dremainder(string as,int x){
    memset(a,0,sizeof(a));
    memset(c,0,sizeof(c));

    int alen = as.size();
    int clen = alen;

    //正向存储
    for(int i=1;i<=alen;i++){
        a[i] = as[i-1] - '0';
    }

    int r=0;
    for(int i=1;i<=clen;i++){
        r = r*10 + a[i];
        c[i] = r/x;
        r %= x;
    }

    return r;
}

算法
avatar
Hiyoung
若无闲事挂心头，便是人间好时节
文章
51
标签
75
分类
31
Follow Me
公告
网站破后重生，变得更加花哨！
最新文章
飞牛NAS备忘录
安卓实用软件记录
github pages 使用自定义域名
hexo引用站内文章
MacOS上配置Hexo教程
分类
标签
nas飞牛OS路人女主的养成方法霞之丘诗羽完结读评加藤惠完结后有感丸户史明游戏制作,游戏叙事CppC++CcppSTLstring字符串HexohexoMacOSMarkdown
归档
网站资讯
文章数目 :
51
已运行时间 :
本站总字数 :
96.2k
最后更新时间 :