Problem

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:

Input: [23, 2, 4, 6, 7], k=6

Output: True

Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7], k=6

Output: True

Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42. 42 is a mutiple of 6 and 7 and n=7.

Note:

1. The length of the array won’t exceed 10,000.
2. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

Solution

基本思想

本题是一个经典的动态规划问题，此类问题的特征是，需要在穷举的可能性中找到一个最优化的解，从而求出所需问题的答案。本题的目标是找到所有和为K的连续子数组的个数。虽然本题没有直接提问一个最优解的概念，但是其实和为K的连续子数组的个数就是在穷举所有可能性后得出的并且是唯一的结果。

本题的解题思路是采用是动态规划思想，一般来讲，动态规划题目的解题思路如下：

1. 找出最优解性质，并刻画其结构特征;
2. 递归的定义最优值;
3. 自底向上的方式算出最优值；
4. 根据计算最优值时得到的信息构造最优解。

动态规划解题的前提假设是：问题的最优解包含着其自问题的最优解。此种性质称为最优子结构性质。最优子结构性质不难通过反证法证明。

递归关系的建立，是基于已有的前提最优解，所以不难在此基础上推导出递增关系。

解题思路

本题中，连续子数组的和是可以通过数组前缀和算出来的。两个长度不同的数组S[i], S[j]的前缀和相减就能计算出子数组S[(i+1)~j]的和。

数组前缀和定义：一个数组从0号元素相加到k号元素则是该数组的第k个前缀和。下文用Sum(k)表示。

假设已知长度为k的所有长度大于2的子数组后缀和中，是K的整数倍的有a(k)个，则当在k+1的情况下，a(k+1)则是a(k)+所有k的子数组后缀和中值为K的整数倍-a[k+1]的个数。

数组后缀和定义：一个数组从最后一个元素加到倒数第k的元素，是该数组的第k个后缀和。

长度为k的数组的所有子数组的后缀和计算，可以利用数组的前缀和计算出。a(k)情况下，其后缀和的集合为第k个前缀和减去第i个前缀和(0<=i<k)的数集。

为求得所有k的子数组后缀和中值为K的整数倍-a[k+1]的个数，需要求出所有k的整倍数-a[k+1]的个数。循环终止于当k的倍数大于整个序列和。

程序设计

本程序需要维护一个HashMap，每个key都是一个前缀和，value则是前缀和的子数组个数。从而在每步的计算中能够利用这个数据结构最优查找速度。

每步的运算设计思想是找到重复的子问题，从而能在一步一步地推中找到第n步的答案。每步的计算中需要找到第k后缀和中符合条件的解，也就是HashMap中key值为sum-K_multiple的value。计算公式推导如下：

1
2
3
4
5

第k后缀和中符合条件的解
    =[所有K的整倍数a[k+1]-为a[k]后缀和的]value
    =[所有K的整倍数-a[k+1]为(Sum(k)-Sum(i))]的value, i=0,1,...,k-2中某值
    =[所有K的整倍数为(Sum(k+1)-Sum(i))]的value
    =[Sum(i)中值为(Sum(k+1)-所有K的整数倍)]的value

本算法需要计算从0到n的所有子数组前缀和并进行O(1)的HashMap查找，所以最终的复杂度为O(n)。

实现技巧

边界条件考虑：

1. 长度至少为2的子数组；

   对于存在单个数为K的整数倍的数组，单数的情况是不能统计进最终结果的，所以需要在查找匹配的情况下去检查Sum(i)是否为previous_sum。如果是且value=1就需要剔除该种情况。

2. 非负序列

   注意，value是可以不为1的，因为非负序列是可以存在连续的0元素。

3. K的整数倍

   K的整数倍包括负数倍，也包括0倍，所以需要考虑K<0是将K转化为正数，因为同解。

4. K为零的情况

   K为零的情况需要特殊考虑，主要是因为算法可以大大简化为查找连续两个0的算法。也因为K为零会使求余数运算符无法使用。

5. 循环次数过多超时问题

   此属于算法优化问题，当Sum(k+1)本身就是K的整数倍的时候，可以直接跳过K的整数倍递增的查找运算，从而避免K过小，序列元素值过大而造成的超时问题。

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

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        //special consideration for k=0 case
        if(k == 0){
            for(int i = 0; i< nums.length; ++i){
                if(i> 0 && nums[i] == 0 && nums[i-1]==0)
                    return true;
            }
            return false;
        }
        // revert to positive value to get same solution
        if(k < 0)
            k = -k;
        
        int previous_sum = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer> ();
        int sum = 0;
        for(int i = 0; i< nums.length; ++i){
            sum += nums[i];            
            //check sum(k+1) first
            if(sum%k == 0 && i > 0)
                return true;
            //iterate to search
            int k_multiple = 0;
            while(k_multiple<sum ){
                if(map.containsKey(sum-k_multiple)){
                    if(sum-k_multiple == previous_sum && map.get(previous_sum) == 1){
                        k_multiple += k;
                        continue;
                    }                        
                    return true;
                }                    
                k_multiple += k;
            }
            

            //memroize sum(k)
            if(map.containsKey(sum))
                map.put(sum, map.get(sum)+1);
            else
                map.put(sum, 1);

            // store previoius sum(k) to avoid length=1 subarraies
            previous_sum = sum;
        }
        return false;
    }
}

读书是一个很好的习惯

Books that I have read

Books that I am reading

Books that I want to read

Books of reference

Books that I am not reading for months

Angular 5 Overview

Angular 5的快速开发，测试和部署可以使用Angular CLI工具完成。Angular 5是基于Typescript语言开发的Web前端框架。

Angular 5 quick start

• Environment Setup
• ng command
• Project structure definition

  More at: https://angular.io/guide/quickstart

Angular 5 basic prject development tutorial

Application shell

Angular 5应用的基本框架，可以用ng new {projectname}命令生成，一个简单的Angular项目需要包含一个app module和app component。在app component中，会定义一个控件，作为整个Angular app的入口，一般写在index.html中。

Angular Component

在已经有的app component基础上，可以用ng generate component {dir/componetname}命令生成更多的组件，新的组件组成元素和app component一样，也是html模板，ts组件功能定义，和css组件风格。一般意义上，在ts中定义控件directive的名称，在html模板中，可以直接调用该directive。

每个已经创建好的component会被自动import进入app.module.ts文件，从而在Angular应用启动时，能自动寻找到对应的component并加载。如果developer需要在自己定义的component中引用其他component/service组件，也需要定义相似的import语句，否则Angualr引擎并不能成功识别调用组件。

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

//Angular components
import { BrowserModule } from '@angular/platform-browser';
import { NgModule } from '@angular/core';
import { FormsModule } from '@angular/forms';

//Angular application shell
import { AppComponent } from './app.component';
//Additional costomized components
import { HeroesComponent } from './heroes/heroes.component';
import { HeroDetailComponent } from './hero-detail/hero-detail.component';
//Additional service modules
import { HeroService } from './hero.service';

@NgModule({
  declarations: [
    AppComponent,
    HeroesComponent,
    HeroDetailComponent,
  ],
  imports: [
    BrowserModule,
    FormsModule
  ],
  providers: [
    HeroService
  ],
  bootstrap: [ AppComponent ]
})

Angular Service

Angular提供了service module来支持现在Web前端数据获取和更新功能。可以用ng generate service {dir/servicename} –module=app命令来生成。

Angular Routing

Angular提供了routing来允许Web前端以single page application(SPA)方式渲染多个url的页面。可以用ng generate module app-routing –flat –module=app生成app.routing.ts模块。app routing模块隐式定义了控件，这是一个可以根据输入url进行跳转的控件。一般放在app componet html模板中，作为Angular应用的跳转渲染单元。这个控件本身，并不能提供跳转入口，一般需要写锚，在html模板显式来定义url。

1
2
3
4
5

<nav>
  <a routerLink="/heroes">Heroes</a>
  <a routerLink="/heroes">Heroes</a>
</nav>
<router-outlet></router-outlet>

此外，app routing模块本身，定义了url跳转的逻辑。由于Angualar的html模块本身具有嵌套性，因而在routing逻辑中，只要引入自定义的directive控件，就能自动渲染出控件中所嵌套的所有元素。可以说，Angular的程序设计思想，就是基于模板设计的，每个模板都是一个自定义的DOM元素，允许在Angular的控制域中任意的复用。

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

import { NgModule }             from '@angular/core';
// Angular routing module
import { RouterModule, Routes } from '@angular/router';
 
import { DashboardComponent }   from './dashboard/dashboard.component';
import { HeroesComponent }      from './heroes/heroes.component';
import { HeroDetailComponent }  from './hero-detail/hero-detail.component';
 
const routes: Routes = [
  { path: '', redirectTo: '/dashboard', pathMatch: 'full' },
  { path: 'dashboard', component: DashboardComponent },
  { path: 'detail/:id', component: HeroDetailComponent },
  { path: 'heroes', component: HeroesComponent }
];
 
@NgModule({
  imports: [ RouterModule.forRoot(routes) ],
  exports: [ RouterModule ]
})
export class AppRoutingModule {}      

Angular HTTP

Angular提供了HttpClient库作为Restful API的utility来完成Web前端的服务器数据交互。在程序中，HttpClient库一般本身不会单独存在于componnet中，而是作为Angular Service模块的底层调用库。

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

// Service module
import { Injectable } from '@angular/core';
// import httpclient Angular module
import { HttpClient, HttpHeaders } from '@angular/common/http';
 
import { Observable } from 'rxjs/Observable';
import { of } from 'rxjs/observable/of';
import { catchError, map, tap } from 'rxjs/operators';
 
import { Hero } from './hero';
import { MessageService } from './message.service';
 
const httpOptions = {
  headers: new HttpHeaders({ 'Content-Type': 'application/json' })
};
 
@Injectable()
export class HeroService {
 
  private heroesUrl = 'api/heroes';  // URL to web api
 
  constructor(
    private http: HttpClient,
    private messageService: MessageService) { }
 
  /** GET heroes from the server */
  getHeroes (): Observable<Hero[]> {
    return this.http.get<Hero[]>(this.heroesUrl)
      .pipe(
        tap(heroes => this.log(`fetched heroes`)),
        catchError(this.handleError('getHeroes', []))
      );
  }
 
  /** GET hero by id. Return `undefined` when id not found */
  getHeroNo404<Data>(id: number): Observable<Hero> {
    const url = `${this.heroesUrl}/?id=${id}`;
    return this.http.get<Hero[]>(url)
      .pipe(
        map(heroes => heroes[0]), // returns a {0|1} element array
        tap(h => {
          const outcome = h ? `fetched` : `did not find`;
          this.log(`${outcome} hero id=${id}`);
        }),
        catchError(this.handleError<Hero>(`getHero id=${id}`))
      );
  }
 
  /** GET hero by id. Will 404 if id not found */
  getHero(id: number): Observable<Hero> {
    const url = `${this.heroesUrl}/${id}`;
    return this.http.get<Hero>(url).pipe(
      tap(_ => this.log(`fetched hero id=${id}`)),
      catchError(this.handleError<Hero>(`getHero id=${id}`))
    );
  }
 
  /* GET heroes whose name contains search term */
  searchHeroes(term: string): Observable<Hero[]> {
    if (!term.trim()) {
      // if not search term, return empty hero array.
      return of([]);
    }
    return this.http.get<Hero[]>(`api/heroes/?name=${term}`).pipe(
      tap(_ => this.log(`found heroes matching "${term}"`)),
      catchError(this.handleError<Hero[]>('searchHeroes', []))
    );
  }
 
  //////// Save methods //////////
 
  /** POST: add a new hero to the server */
  addHero (hero: Hero): Observable<Hero> {
    return this.http.post<Hero>(this.heroesUrl, hero, httpOptions).pipe(
      tap((hero: Hero) => this.log(`added hero w/ id=${hero.id}`)),
      catchError(this.handleError<Hero>('addHero'))
    );
  }
 
  /** DELETE: delete the hero from the server */
  deleteHero (hero: Hero | number): Observable<Hero> {
    const id = typeof hero === 'number' ? hero : hero.id;
    const url = `${this.heroesUrl}/${id}`;
 
    return this.http.delete<Hero>(url, httpOptions).pipe(
      tap(_ => this.log(`deleted hero id=${id}`)),
      catchError(this.handleError<Hero>('deleteHero'))
    );
  }
 
  /** PUT: update the hero on the server */
  updateHero (hero: Hero): Observable<any> {
    return this.http.put(this.heroesUrl, hero, httpOptions).pipe(
      tap(_ => this.log(`updated hero id=${hero.id}`)),
      catchError(this.handleError<any>('updateHero'))
    );
  }
 
  /**
   * Handle Http operation that failed.
   * Let the app continue.
   * @param operation - name of the operation that failed
   * @param result - optional value to return as the observable result
   */
  private handleError<T> (operation = 'operation', result?: T) {
    return (error: any): Observable<T> => {
 
      // TODO: send the error to remote logging infrastructure
      console.error(error); // log to console instead
 
      // TODO: better job of transforming error for user consumption
      this.log(`${operation} failed: ${error.message}`);
 
      // Let the app keep running by returning an empty result.
      return of(result as T);
    };
  }
 
  /** Log a HeroService message with the MessageService */
  private log(message: string) {
    this.messageService.add('HeroService: ' + message);
  }
}

HttpClient除了和真正的服务器交互外，还可以和in-memory的数据服务器进行虚拟交互，也就是说，在不修改(略微)原有程序代码的情况下，可以自己运用一个npm package设立一个in-memory的数据服务器，HttpClient并不知道request已经被这个in-memory服务器拦截并返回内存中的数据。

在前后端分离的开发过程中，如果要引用此功能，需要预先安装angular-in-memory-web-api的npm包。

1

$ npm install angular-in-memory-web-api@0.5 --save

然后，创建in-memory-data.service模块，存储内存中的数据，作为HttpClient访问交互的相关数据。

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

import { InMemoryDbService } from 'angular-in-memory-web-api';

export class InMemoryDataService implements InMemoryDbService {
  createDb() {
    const heroes = [
      { id: 11, name: 'Mr. Nice' },
      { id: 12, name: 'Narco' },
      { id: 13, name: 'Bombasto' },
      { id: 14, name: 'Celeritas' },
      { id: 15, name: 'Magneta' },
      { id: 16, name: 'RubberMan' },
      { id: 17, name: 'Dynama' },
      { id: 18, name: 'Dr IQ' },
      { id: 19, name: 'Magma' },
      { id: 20, name: 'Tornado' }
    ];
    return {heroes};
  }
}

最后，在app module模块中引入对in-memory-web-api的引用，和in-memory-data service模块的使用，并配置好in-memeory-server对应的data/service来源。

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

import { NgModule }       from '@angular/core';
import { BrowserModule }  from '@angular/platform-browser';
import { FormsModule }    from '@angular/forms';
import { HttpClientModule }    from '@angular/common/http';

// import in-memroy-data servier related module 
import { HttpClientInMemoryWebApiModule } from 'angular-in-memory-web-api';
import { InMemoryDataService }  from './in-memory-data.service';
 
import { AppRoutingModule }     from './app-routing.module';
 
import { AppComponent }         from './app.component';
import { DashboardComponent }   from './dashboard/dashboard.component';
import { HeroDetailComponent }  from './hero-detail/hero-detail.component';
import { HeroesComponent }      from './heroes/heroes.component';
import { HeroSearchComponent }  from './hero-search/hero-search.component';
import { HeroService }          from './hero.service';
import { MessageService }       from './message.service';
import { MessagesComponent }    from './messages/messages.component';
 
@NgModule({
  imports: [
    BrowserModule,
    FormsModule,
    AppRoutingModule,
    HttpClientModule,
 
    // The HttpClientInMemoryWebApiModule module intercepts HTTP requests
    // and returns simulated server responses.
    // Remove it when a real server is ready to receive requests.
    HttpClientInMemoryWebApiModule.forRoot(
      InMemoryDataService, { dataEncapsulation: false }
    )
  ],
  declarations: [
    AppComponent,
    DashboardComponent,
    HeroesComponent,
    HeroDetailComponent,
    MessagesComponent,
    HeroSearchComponent
  ],
  providers: [ HeroService, MessageService ],
  bootstrap: [ AppComponent ]
})
export class AppModule { }

Angular Data Model – Class

In Angular 5, data model is encapsulated through classes, mainly for rendering templates in components. Creating a new class by Angular Cli:

1

$ ng generate class {classname}

Problem

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2

Output: 2

Note:
The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Solution

解题思路

本题不属于某类经典类型的算法题。本题的解题关键在于深刻理解子数组和的计算方法，以及和为K的子数组和个数的求解技巧。

首先，需要求得长度为n的数组的和为K的连续子数组的个数，设为A(n)。统计连续子数组的和，以及和的分布则成为解题的前提条件。在统计连续子数组的和的过程中，我们可以采用穷举法，将所有子数组的和都进行一次统计，也能运用一些巧妙的方法，只统计部分子数组的和的个数，计算出和为K的子数组和的个数。

为了达到优化子数组和统计的方法，可以仔细思考子数组和的计算方法。不难得出，子数组和的计算方法其实源于两个从零开始的数组和之差。也就是说，假设从A[m]到A[n]之间的子数组和S[mn] = S[0n] - S[0-m]。如果在已知S[0~i] (i=0,…,n-1)的值，就能轻松求解出所有子数组的和。

然而，这样的方法用于求所有的子数组的和，并不能简化计算复杂度。要找到和为K的子数组的个数，就等于需要便利S[0i] (i=0,…,n)，并且找出末尾为第i个元素的子数组序列和为K的个数。由此不难推出，末尾为第i个元素的子数组序列和为K的个数，等价于S[mi] (m=1,…,i-1)中和为K的个数，也等价于S[0m] (m=1,…,i-1)中和为S[0i]-K的子数组个数。

1
2
3

Number(末尾为第i个元素的子数组序列和为K的个数)=Number(S[0~m] (m=1,...,i-1)中和为S[0~i]-K的子数组个数);

Number(n长数组子数组序列和为K的个数)=sigma(Number(末尾为第i个元素的子数组序列和为K的个数)) (i=0,...n-1)

程序设计

本题解的优劣则取决于统计子数组和的计算量。

1. 运用hashmap数据结构存取所有的子数组和，经过两次for循环遍历得出所有子数组可能性下的和的值，并统计入hashmap中。本解法的时间复杂度是O(n^2)。
2. 优化后的算法采用hashmap数据结构存取S[0~i] (i=0,…n-1)，并且在每次计算后计算以i结尾的连续子数组和为K的个数。将所有数字相加则为综合。本解法的时间复杂度是O(n)。

实现技巧

边界条件考虑：

• K=0的情况。
• K=S[0~i] (i=0,…,n-1)中的任意一个情况

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

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer> ();
        int sum = 0;
        int total =0;
        for(int i = 0; i< nums.length; ++i){
            sum += nums[i];  
            // don't forget margin k = 0, check previous count before adding this count to avoid confustion.
            if( map.containsKey(sum-k))
                total += map.get(sum-k);
            if(k == sum)
                total += 1;
               
            if(map.containsKey(sum))
                map.put(sum, map.get(sum)+1);
            else
                map.put(sum, 1);                
        }
        return total;
    }
}

Ubuntu on Windows 10

1. Enable Developer mode for Win 10
   
2. Add Windows Linux subsystem
   
3. Install Ubuntu/SUSE/*** from App Store
   

Update package sources

1. Edit /etc/apt/source.list

   #中国数学物理大学源

   deb http://debian.ustc.edu.cn/ubuntu/ vivid main multiverse restricted universe

   deb http://debian.ustc.edu.cn/ubuntu/ vivid-backports main multiverse restricted universe

   deb http://debian.ustc.edu.cn/ubuntu/ vivid-proposed main multiverse restricted universe

   deb http://debian.ustc.edu.cn/ubuntu/ vivid-security main multiverse restricted universe

   deb http://debian.ustc.edu.cn/ubuntu/ vivid-updates main multiverse restricted universe

   deb-src http://debian.ustc.edu.cn/ubuntu/ vivid main multiverse restricted universe

   deb-src http://debian.ustc.edu.cn/ubuntu/ vivid-backports main multiverse restricted universe

   deb-src http://debian.ustc.edu.cn/ubuntu/ vivid-proposed main multiverse restricted universe

   deb-src http://debian.ustc.edu.cn/ubuntu/ vivid-security main multiverse restricted universe

   deb-src http://debian.ustc.edu.cn/ubuntu/ vivid-updates main multiverse restricted universe

   #阿里云的源：

   deb http://mirrors.aliyun.com/ubuntu/ vivid main restricted universe multiverse

   deb http://mirrors.aliyun.com/ubuntu/ vivid-security main restricted universe multiverse

   deb http://mirrors.aliyun.com/ubuntu/ vivid-updates main restricted universe multiverse

   deb http://mirrors.aliyun.com/ubuntu/ vivid-proposed main restricted universe multiverse

   deb http://mirrors.aliyun.com/ubuntu/ vivid-backports main restricted universe multiverse

   deb-src http://mirrors.aliyun.com/ubuntu/ vivid main restricted universe multiverse

   deb-src http://mirrors.aliyun.com/ubuntu/ vivid-security main restricted universe multiverse

   deb-src http://mirrors.aliyun.com/ubuntu/ vivid-updates main restricted universe multiverse

   deb-src http://mirrors.aliyun.com/ubuntu/ vivid-proposed main restricted universe multiverse

   deb-src http://mirrors.aliyun.com/ubuntu/ vivid-backports main restricted universe multiverse

作者：sarleon
链接：https://www.zhihu.com/question/41311332/answer/90517838

2. Run apt to udpate

   1	$ sudo apt-get update

Intall Nodejs and npm

• Install from Ubuntu apt tool

  1	$ sudo apt install nodejs nodejs-legacy npm

• npm self update for npm

  1	$ sudo npm install -g npm@latest

• npm update nodejs using package n

  1 2 3

  $ sudo npm install -g n $ sudo n stable #get latest stable $ sudo n latest #get latest version

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，加载初始页面，在没有网的情况下访问离线页面，有网的情况下可以选择优先加载。对于静态页面的应用具有提升加载速度的好处。