0%

韩信点兵原理

描述

相传韩信才智过人,从不直接清点自己军队的人数,只要让士兵先后以三人一排、五人一排、七人一排地变换队形,而他每次只掠一眼队伍的排尾就知道总人数了。输入3个非负整数a,b,c ,表示每种队形排尾的人数(a<3,b<5,c<7),输出总人数的最小值(或报告无解)。已知总人数不小于10,不超过100 。

输入

输入3个非负整数a,b,c ,表示每种队形排尾的人数(a<3,b<5,c<7)。例如,输入:2 4 5

输出

输出总人数的最小值(或报告无解,即输出Noanswer)。实例,输出:89

样例输入

2 1 6

样例输出

41

定理1 如a被n除所得的余数等于b被n除所得的余数,c被n除所得的余数等于d被n除所得的余数, 则ac被n除所得的余数等于b d被n除所得的余数。

用同余式叙述就是:

如a≡b(mod n ),c≡d(mod n )

则ac≡b d(mod n )

定理2 被除数a加上或减去除数b的倍数,再除以b,余数r不变。即

如a ≡ r(mod b ),则a ± b n≡r(mod b )

例如70≡1(mod 3 )可得70±10×3≡1(mod 3 )

韩信点兵法口诀的原理

①能被5,7除尽数是35k,其中k=2,即70除3正好余1,70a 除3正好余a。

②能被3,7除尽数是21k,其中k=1,即21除5正好余1,21b 除5正好余b。

③能被3,5除尽数是15k,其中k=1,即15除7正好余1,15c 除7正好余c。

这样——

根据①可知 70a+21b+15c 除3正好余a。

根据②可知 70a+21b+15c 除5正好余b。

根据③可知 70a+21b+15c 除7正好余c。

这样我们就得到了一个答案

除 3 余 a 除 5 余 b 除 7 余 c 的一个答案是 70a+21b+15c

而这个数(70a+21b+15c)对(357)取余就得到了最小答案

(70a+21b+15c)%(357)为最小值,然后再判断最小值是否满足条件。

转载自:https://www.cnblogs.com/zqxLonely/p/4054526.html

前置知识

Character encodings: Essential concepts

UTF-8 uses 1 byte to represent characters in the ASCII set, two bytes for characters in several more alphabetic blocks, and three bytes for the rest of the BMP. Supplementary characters use 4 bytes.

UTF-16 uses 2 bytes for any character in the BMP, and 4 bytes for supplementary characters.

UTF-32 uses 4 bytes for all characters.

In the following chart, the first line of numbers represents the position of a character in the Unicode coded character set. The other lines show the byte values used to represent that character in a particular character encoding.

A(Latin A.) א(Hebrew alef.) 好(Han ideograph AN.) 𣎴(Chinese ideograph meaning ‘stump of tree’.)
Code point U+0041 U+05D0 U+597D U+233B4
UTF-8 41 D7 90 E5 A5 BD F0 A3 8E B4
UTF-16 00 41 05 D0 59 7D D8 4C DF B4
UTF-32 00 00 00 41 00 00 05 D0 00 00 59 7D 00 02 33 B4

乱码原因

以下 css 进行 sass 压缩

1
2
3
4
5
6
a::before {
content: '\4e2d' // codepoint
}
b::after {
content: "\e6df"; // codepoint
}

压缩后(为了方便查看,对压缩后的代码进行了格式化)

1
2
3
4
5
6
a::before {
content '中'
}
b::after {
content: "";
}

源代码 \4e2d 占用 5 个字节,压缩后代码 占用 3 个字节 E4 B8 AD

浏览器对压缩后的代码解析可能会出错,把 按 3 个 codepoint 解析,然后页面中就出现了三个 ascii 码

解决方案

css-unicode-loader

备注

1
2
3
4
encodeURI('中') // '%E4%B8%AD' 三位 16 进制
const encoder = new TextEncoder();
const view = encoder.encode("中"); // [228, 184, 173] 三位十进制
'中'.charCodeAt(0).toString(16) // 4e2d codepoint

sass 开发者一直强调他们把 css 压缩后,会在文件头声明 charset 或者 以 utf-8 with bom 格式保存文件,浏览器会正确处理,之所以导致这个问题,是因为后续的 css 处理(postcss) 把 charset 或 utf-8 with bom 格式丢掉了。
实际上 sass 的确是按 utf-8 with bom 保存的文件,后续的 css 处理也的确把 utf-8 with bom 格式丢掉了。但这问题和 bom 没关系。
The byte-order mark (BOM) in HTML

此文章发表时,官方文档关于搜索部分还未更新。

algolia 工作原理

你把你的网站数据上传到 algolia, 当你在你的网站上进行搜索时,会向 algolia 发送一个请求,algolia 在你上传的数据中进行搜索,然后把结果返回给你,你在你的网站上进行展示。

那么最关键的就是申请一个 algolia 账号,然后把你的数据上传上去。

上传数据有这么几种方法

  1. 手动上传,algolia 支持 json 数据上传。
  2. 使用官方提供的工具上传。(本文主要介绍)
  3. 使用官方提供的 crawler 爬虫自动爬取。(需要拥有 crawler 权限)

DocSearch

DocSearch 是 algolia 旗下的一款产品,主要做技术文档和技术博客的搜索,免费,但是申请条件比较严苛,需要人工审核。
申请通过后可以使用官方提供的 crawler。官方也提供了 vitepress config template,操作比较简单。具体可参考这篇文章或官方文档。

DocSearch 申请条件

  1. 你的网站可以公开访问
  2. 你的网站是开源项目的技术文档或技术博客
  3. 你是此网站的所有者

注册 algolia 账号

algolia 官网

在 algolia 创建 index

下一步要用到

配置中开启 algolia

1
2
3
4
5
6
7
8
9
10
11
12
13
// docs/.vitepress/config.js

export default defineConfig({
title: "xxx",
description: "Just playing around.",
themeConfig: {
algolia: {
appId: 'xxx',
apiKey: 'xxxx',
indexName: 'xxx'
},
},
});

appId

setting -> Team and Access -> API keys -> Application ID

apiKey

请勿使用 Admin API Key

setting -> Team and Access -> API keys -> Search-Only API Key

indexName

上一步创建的 index 的名称

到这一步你的 vitepress 页面中应该能看到搜索框了,但是还无法搜索到结果,因为你还没上传数据到 algolia。

上传数据到 algolia

algolia 官方提供了 crawler(爬虫) 来爬取你网站的数据,直接在网站上操作,简单方便,但是需要 crawler 权限。

algolia 也提供了免费的方法,运行官方提供的 docker image 上传数据到 algolia。

此方法已进入 legacy 阶段,后期可能会失效。

Run the crawl from the Docker image

docker 安装使用请自行查询
install jq, a lightweight command-line JSON processor

1
docker run -it --env-file=.env -e "CONFIG=$(cat /path/to/your/config.json | jq -r tostring)" algolia/docsearch-scraper

config.json 模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
{
"index_name": "test",
"start_urls": ["https://test.com/docs/"], // 此链接是你最终部署文档的地址
"selectors": {
"lvl0": "",
"lvl1": ".content h1",
"lvl2": ".content h2",
"lvl3": ".content h3",
"lvl4": ".content h4",
"lvl5": ".content h5",
"content": ".content p, .content li"
}
}

本文主要记录 require 升级为 import 遇到的问题

__dirname is not defined in ES module scope

1
2
3
4
5
6
7
8
9
10
11
12
import path from 'path';
import {fileURLToPath} from 'url';

const __filename = fileURLToPath(import.meta.url);

// 👇️ "/home/john/Desktop/javascript"
const __dirname = path.dirname(__filename);
console.log('directory-name 👉️', __dirname);

// 👇️ "/home/borislav/Desktop/javascript/dist/index.html"
console.log(path.join(__dirname, '/dist', 'index.html'));

import json file

1
2
import json from "./foo.json" assert { type: "json" };
import("foo.json", { assert: { type: "json" } });

import 条件导入

1
2
3
4
if (condition) { // 报错
import moduleA from './moduleA';
}

import 函数

1
2
3
4
5
import('./moduleA .js')
.then(moduleA => {
console.log(moduleA);
});

1
2
3
4
if(condition){
import('moduleA').then(...);
}

代码如何执行

使用高级语言编写的代码需要先编译为机器码(二进制代码)再执行

执行方式有如下两种

编译执行

代码 =》 解析器 =》 中间代码 =》 编译器 =》 机器码 =》 执行结果

把代码一次性编译为机器码,然后执行

解释执行

代码 =》 解析器 =》 中间代码 =》 解释器 =》 执行结果

编译一行代码,执行一行代码,一边编译一边执行

为何需要虚拟机

java 和 javascript 等语言需要虚拟机,是为了跨平台,抹平平台差异。

为何需要中间代码

中间代码一般为字节码

因为把源码编译为机器码占用太多空间,热代码需要缓存下来,避免重复编译。而使用字节码可以节省空间。

当然字节码还能提升代码启动速度、降低代码负责度

V8是如何执行一段JavaScript代码的?

字节码(一):V8为什么又重新引入字节码?

重写 fetch 和 XHR

原理

重写 fetch 和 XHR,返回自定义数据。
把重写 fetch 和 XHR 的代码通过 <script></script> 标签 插入到 html 里

问题

当你插入 <script></script> 标签的时候,请求可能已经发出了,所以此种方法不能保障拦截所有请求

tweak