微观天下

Problem

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

“123”

“132”

“213”

“231”

“312”

“321”

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Solution

解题思路

寻找排列顺序规律，可以得出如下排序规律：

1. 整个排序可以划分成n个小排序。以1为首，[2, 3]的子序列排序。以2为首，[1, 3]的子序列排序， 以3为首，[1, 2]的子序列排序。

2. 再次划分，则可以将以1为首的排序中，分成以2为第二位， [3]的全排列，和以3为第二位，[2]的全排列。

3. 逐次划分，分别能将长度为n的序列分解成n个(n-1)全排列，n*(n-1)个(n-2)的全排列，…n!个(1)的全排列。

程序设计

在知晓序列排序规律后，可以着手考虑将第k个元素找到。搜索定位的思想类似于一棵树的节点查找，这棵树的结构已经找到：第一层儿子有n个，第二层的孙子节点共有n*(n-1)个，且每个儿子拥有(n-1)个儿子，以此类推。

而第k个元素对应的元素如何计算出呢？根据这棵树的特点，我们可以做出如下设计，使得从树根到第k个节点的路径就是我们所需要的元素。

1. 假设树根节点是个空节点，其的n个儿子分别为1, 2, 3, 4, 5,…, n。

2. 第一层的节点1拥有(n-1)个儿子，分别为2, 3, 4, 5,…n。

3. 第二层节点2拥有(n-2)个儿子，分别为3, 4, 5,…n。 而第二层节点3拥有N(n-2)个儿子，分别为2, 4, 5,…n。尤其需要注意，儿子的顺序是除开父亲节点后的顺序结构。

时间复杂度树的高度，为O(n)。

实现技巧

从1到n的全排列值计算具有较高的代码重复性， 可以用如下算法进行缓存，从而减少反复计算产生的时间消耗。

1
2
3
4
5
6
7
8
9

// dynamic length int array declaration!!!
int[] factorial = new int[n+1];
// create an array of factorial lookup
    int sum = 1;
    factorial[0] = 1;
    for(int i=1; i<=n; i++){
        sum *= i;
        factorial[i] = sum;
    }

对于元素生成，可以运用List类型的灵活性而避免在元素中挪动数字造成的时间开销。即使int array也可以作为一种高效的数据结构。

在程序实现中，递归算法会产生较高的空间开销，在for循环可以完成计算的情况下，优先采用后者。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

List<Integer> numbers = new ArrayList<>();
StringBuilder sb = new StringBuilder();

// create a list of numbers to get indices
for(int i=1; i<=n; i++){
    numbers.add(i);
}
// numbers = {1, 2, 3, 4}

k--;

for(int i = 1; i <= n; i++){
        int index = k/factorial[n-i];
        sb.append(String.valueOf(numbers.get(index)));
        numbers.remove(index);
        k-=index*factorial[n-i];
    }
    
    return String.valueOf(sb);

Welcome to Sunny’s hexo post

本文主要介绍一种常见的个人博客管理方式，利用现有的Hexo静态博客模板管理和生成静态博客文档，和github pages对git repo页面的原生发布功能进行博客展示。同时，博客文档也能在本地生成，部署，存档，较于现有的博客工具具有更好的功能扩展。

Prepare Node.js

Hexo is Node.js based npm plugin, which provides many extensions and powerful blog management functionality.

Use Hexo to manage blogs

1
2
3
4

$ npm install hexo --save
$ hexo init
$ hexo new "My New Post" # hexo new draft "My New Draft"
$ hexo server

Use SSH git management

1
2

$ ssh-keygen -t rsa -C "{yourgithubaddress}"
$ ssh -T git@github.com

Create {username}.github.io repo for statics hexo pages

Configure _config.yml file for hexo blogs and deployments

1
2
3
4
5
6
7
8
9
10
11
12

# URL
## If your site is put in a subdirectory, set url as 'http://yoursite.com/child' and root as '/child/'
url: https://{username}.github.io/

# Deployment
## Docs: https://hexo.io/docs/deployment.html
deploy:
  type: git
  repo: git@github.com:{username}/{username}.githubm.io.git
  branch: master
  message: "Site updated: {{ now('YYYY-MM-DD HH:mm:ss') }}"

Deploy hexo static files to target repo

1
2
3

$ hexo clean
$ hexo generate
$ hexo deploy

Useful links:
Hexo with pictures,
Hexo Deployment,
Jekyll vs Hexo,
Markdown,
Markdown brief,
Markdown highlights

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment

Nodejs and NPM requirement

Nodejs higher than 6.0.0 and NPM higher than 5. Otherwise, Hexo might not work with some strange error!!

Hexo Mermaid for graph

More info: Here

• Flow chart

  graph TD;
    A-->B;
    A-->C;
    B-->D;
    C-->D;

graph TD;
    交易合同TradeContract--contains-->仓位Position;
    仓位Position--scales-->资产Asset;
    资产Asset--references-->价值的票据InstrumentOfValue;

• Gannt diagram

gantt
    dateFormat  YYYY-MM-DD
    title       Adding GANTT diagram functionality to mermaid
    excludes    weekends
    %% (`excludes` accepts specific dates in YYYY-MM-DD format, days of the week ("sunday") or "weekends", but not the word "weekdays".)

    section A section
    Completed task            :done,    des1, 2014-01-06,2014-01-08
    Active task               :active,  des2, 2014-01-09, 3d
    Future task               :         des3, after des2, 5d
    Future task2              :         des4, after des3, 5d

    section Critical tasks
    Completed task in the critical line :crit, done, 2014-01-06,24h
    Implement parser and jison          :crit, done, after des1, 2d
    Create tests for parser             :crit, active, 3d
    Future task in critical line        :crit, 5d
    Create tests for renderer           :2d
    Add to mermaid                      :1d

    section Documentation
    Describe gantt syntax               :active, a1, after des1, 3d
    Add gantt diagram to demo page      :after a1  , 20h
    Add another diagram to demo page    :doc1, after a1  , 48h

    section Last section
    Describe gantt syntax               :after doc1, 3d
    Add gantt diagram to demo page      :20h
    Add another diagram to demo page    :48h

Hexo simple mindmap

Hexo simple mindmap插件提供了对脑图的可视化支持，相较于mermaid插件的流程图，能够提供更加原生的脑图体验。

More info：here

• Example

• 软件架构师思维导图
  • 代码规范
    • 设计模式
    • 重构
    • 源码学习与分析
    • 复杂系统面向对象模型设计

Hexo search功能

随着文章数量增加，每一页寻找文档变得耗时间，所以增加了search功能来支持快速文章定位功能。

More info: here

1. 下载插件

1

npm install hexo-generator-searchdb --save

2. 配置_config.yaml文件( “hexo-generator-searchdb”: “^1.4.1”后需要更新配置)

1
2
3
4
5
6

search:
  path: search.xml
  field: post
  content: true
  format: html

3. 配置next主题的_config.yaml文件

1
2
3
4
5
6
7
8
9

# Local search
# Dependencies: https://github.com/flashlab/hexo-generator-search
local_search:
  enable: true
  # if auto, trigger search by changing input
  # if manual, trigger search by pressing enter key or search button
  trigger: auto
  # show top n results per article, show all results by setting to -1
  top_n_per_article: 1

hexo UML图绘制

顺序图(Sequence Diagram)

类图（Class Diagram）

1. 强耦合关系

2. 弱耦合关系

Hexo post asset image 管理

1. 自带的hexo-renderer-marked的postAsset无法正常工作
2. 使用hexo-asset-link可以动态生成基于post_dir的图片link，同时在local/remote正常工作
3. 不要在code中写入encoded path或者linux slash /，虽然预览没有问题，但是生成的Link会出问题

Hexo blog encrypt 支持TOC

1. 完美修复
   https://www.itfanr.cc/2021/04/16/hexo-blog-article-encryption/

2. UX修复

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

# node_modules\hexo-theme-next\layout\_macro\sidebar.njk

{%- if display_toc %}
       {%- if (page.encrypt) %}
        {%- set toc = toc(page.origin, { class: "nav", list_number: page.toc.number, max_depth: page.toc.max_depth }) %}
      {%- else %}
        {%- set toc = toc(page.content, { class: "nav", list_number: page.toc.number, max_depth: page.toc.max_depth }) %}
      {%- endif %}
      {%- set display_toc = toc.length > 1 and display_toc %}
    {%- endif %}

<!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
          {%- if display_toc %}
            <!--- For hide TOC in encryption -->
            {%- if (page.encrypt) %}
              <div id="toc-div" style="display:none">
            {%- else %}
              <div id="toc-div">
            {%- endif %}
            <div class="post-toc animated">{{ toc }}</div>
            </div><!-- end of hide -->
          {%- endif %}
        </div>
<!--/noindex-->

hexo 将category作为目录归类博客

当文件数量已经比较多，单层级目录很难去管理文章分类。用hexo-directory-category 可以较好的管理post文档，便于源文件查找和更新。

hexo-next-pwa，支持页面离线访问

PWA应用的创建包含两部分，一个是manifest.json文件放在source目录下，用于提示浏览器安装PWA应用。一个是sw.js文件，用hexo workbox命令生成并注册到index.html文件，使应用支持离线访问，在线更新功能。

PWA应用的好处是运用sw.js文件，在浏览器启动一个类似原生应用的app，加载初始页面，在没有网的情况下访问离线页面，有网的情况下可以选择优先加载。对于静态页面的应用具有提升加载速度的好处。

hexo-highcharts, 支持绘制highchart原生图

这是一个轻量级的plugin，主要支持在markdown内嵌一段highcharts的配置文件，绘制出相应的图。

在加密文档里chart加载会出现竞争问题，需要用如下代码解决

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

let template = `
    <script defer src="https://code.highcharts.com/12.1.2/highcharts.js"></script>
    <script defer src="https://code.highcharts.com/12.1.2/modules/sankey.js"></script>
    <script defer src="https://code.highcharts.com/12.1.2/modules/treemap.js"></script>
    <script defer src="https://code.highcharts.com/12.1.2/modules/treegraph.js"></script>
    <script defer src="https://code.highcharts.com/12.1.2/modules/exporting.js"></script>
    <script defer src="https://code.highcharts.com/12.1.2/modules/export-data.js"></script>
    <script defer src="https://code.highcharts.com/12.1.2/modules/accessibility.js"></script>
    <button onclick="(function() {
        console.log('show highcharts')
        var event = new Event('hexo-blog-decrypt');
        window.dispatchEvent(event);
    })()">HighCharts</button>
    <div id="highcharts${id}" style="width:${args[0] || "85%"}" height:"${args[1] || 400} overflow: auto"></div>
    <script>
        var op = Object.assign(${defaultOpt},${options})
        var chart = !!window.Highcharts ? Highcharts.chart(highcharts${id},op) : console.log("Highcharts undefined");
        window.addEventListener('hexo-blog-decrypt', function() {
            console.log('decrypted')
            //if (sessionStorage.getItem("encryptState") != "1") {
            var op = Object.assign(${defaultOpt},${options})
              if(op.url){
                  $.ajax({
                      url: op.url,
                      type: "JSON",
                      method: op.method || "GET",
                      success: function(res){
                          if(op.seriesFormat){
                              op.series = op.seriesFormat(res)
                          } else {
                              op.series = res;
                          }
                          var chart = Highcharts.chart(highcharts${id},op);
                      }
                  })
              }else{
            var chart = !!window.Highcharts ? Highcharts.chart(highcharts${id},op) : console.log("Highcharts undefined");
            }
            //  sessionStorage.setItem("encryptState", "1");
            //}
        });
    </script>
    `;
    return template;