Java memory allocation

Java虚拟机管理内存会包括以下几个运行时数据区域，如下图所示。

JVM运行时数据区域简介

程序计数器(Program Counter Register)

程序计数器时当前线程执行字节码的行号指示器。每条线程有独立的程序计数器。

• 如果线程执行Java方法，这个技术及记录的时真该执行的虚拟机字节码指令的地址。
• 如果线程执行的时Native方法，这个计数器值则为Undefined。

Java虚拟机栈(JVM stacks)

JVM栈也是线程私有的。虚拟机栈描述的时Java方法执行的内存模型：

1. 每个方法会先创建一个栈帧Stack Frame，用于存储局部变量表，操作数栈，动态链接，方法出口等信息。
2. 在方法执行完后，该栈帧会出栈。

栈内存说的就是虚拟机中局部变量表部分。

Native方法栈

本地方法栈为虚拟机使用到的Native方法服务。

Java堆

Java堆是虚拟机所管理的内存，被所有线程共享的，目的是存放对象实例。Java堆是垃圾收集器(GC)主要管理的区域。

方法区

方法区是用于存储虚拟机的类信息，常量，静态变量，即时编译器编译后的代码等数据，被所有线程共享。在HotSpot虚拟机中，方法区又叫做“永久代”，是因为GC分代收集扩展至方法区，使得方法区由GC中的永久代区域实现。

运行时常量池

运行时常量池是方法区的一部分。本来在方法区中的类信息就包含了除类的版本、字段、方法、接口等描述信息之外，还有一项信息便是常量池，用于存放编译生成的各种字面量和符号引用。常量池信息将在类加载后进入方法区的运行时常量池中存放。同时，一些方法如String类的intern()方法也能将字符串加入运行时常量池。所以在类信息加载完成后，常量池也不是大小就不变的。

直接内存

直接内存并不是与JVM运行时数据区的一部分。JDK1.4后引入的NIO(New I/O)类，引入了一种基于通道(Channel)与缓冲区(Buffer)的I/O方式。它可以使用Native函数库直接分配对外内存，然后通过Java堆中的DirectByteBuffer对象作为这块内存的引用进行操作。直接内存不属于JVM GC的管理范畴，可以用-Xmx进行设定。

JVM对象的创建

当JVM遇到一条new指令时，会做出什么样的处理呢?

1. 检查指令参数是否能在常量池中定位到一个类的符号引用，并确保其被正确的加载、解析和初始化；

2. 在Java堆上分配内存，有两种空闲内存分配方式：

   • 空闲列表： 基于Mark-Sweep算法的收集器的GC，如CMS；
   • 指针碰撞： 具有compact过程的收集器的GC，如Serial, ParNew等。

3. 为了避免竞争效应即操作的原子性，系统采用如下两种其一的方法：

   • 分配内存动作进行同步处理，CAS(Compare and swap)+失败重试机制，
   • 分配内存按照线程划分不同的空间之中进行，即本地线程缓冲机制(TLAB, Thread local allocation buffer)。

4. 为新创建对象设置好初始值；

5. 对对象的对象头信息(Object header)进行相关必要设置，如：

   • 类型指向
   • 类的元数据
   • 对象哈希值
   • 对象的GC年代信息

6. 类文件bytecode中的< init>方法执行；

init方法是Java的class文件中的各种构造方法经过JIT解释后生成的bytecode代码，一般由invokespecial操作码所调用。

自此，一个完整的对象就被创建好了。

JVM对象的内存布局

当JVM对象被创建好了，会被分配在Java堆上，存储布局可以分为三个区域：对象头(header)、实例数据(instance data)和对齐填充(padding)。

对象头

对象头包括两部分，一部分是”Mark Word”,另一部分是类型指针。

• Mark word: 长度为32bit或64bit。HotSpot 32位虚拟机中具体的对象头存储内容取决于对象的锁状态值，如下：
  
• 类型指针: 长度为32bit或64bit，用于存储指向类元数据的指针，并不是所有的虚拟机实现都必须在对象数据上保留类型指针。
• 数组长度：长度为32bit，当对象为数组时，用于存储数组的长度。注：此数组并非ArrayList泛型，后者属于引用类型。

实例数据

实例数据部分存储了类对象的所有类型的字段内容。每种虚拟机有自己定义好的参数和字段的分配策略。

对齐填充

对齐填充的存在是为了满足HotSpot VM自动内存管理系统要求，保证所有对象的地址都是8字节的整数倍。

Java基础类型内存布局

java的基本数据类型共有8种，即int,short,long,byte,float,double,boolean,char(注意，并没有String的基本类型)。Java基础类型变量是在(Java虚拟机)栈上分配的，当变量的作用域运行结束后，通过出栈的方式回收分配在栈上的变量内存。

当声明分配一个int类型变量a = 3时，JVM会先为该变量创建一个变量为a的引用，再在栈上搜索是否存在字面值为3的引用。

• 如果找到，就直接将a指向3的地址。
• 如果没有找到，就分配一个内存存放字面值3，并将a指向这个地址。
  因此说，基础类型字面值在同一个栈上是共享的。

问题：已知int类型变量需要32bit内存，具体stack frame上内存分配是什么样子的呢? 变量a是怎么存放的? int类型信息又是放在那里的呢?

JVM对象的访问定位

对象的访问定位如下图，HOTSOPT用的是第2种算法：

1. 使用句柄（先指向堆里的句柄池，再从句柄池找到指针，优点是只需要修改句柄, 缺点就是句柄池也是开销）；
2. 直接指针（减少性能开销）: 需要存2个数据， 到对象实例数据的指针，到对象类数据的指针。
   

Garbage Collection of JVM

GC定义

Garbage Collection（垃圾回收/GC）是JVM对于Java堆上内存在运行时进行的动态管理，主要是对Java堆上不再被引用的对象进行回收。Minor GC是主要快速回收Eden区和Survivor区对象内存，Full GC则会对老年代也进行回收，后者可能会影响性能。

如何确定对象是否需要回收？

引用计数算法（Reference Counting）

给对象中添加一个引用计数器，每当有一个地方引用它时，计数器值就加1；当引用失效时，计数器值就减1；任何时刻计数器为0的对象就是不可能再被使用的。

缺点：存在循环引用的问题。

可达性分析算法（Reachability Analysis）

通过一系列的称为“GC Roots”的对象作为起始点，从这些节点开始向下搜索，搜索所走过的路径称为引用链（Reference Chain），当一个对象到GC Roots没有任何引用链相连（用图论的话来说，就是从GC Roots到这个对象不可达）时，则证明此对象是不可用的。

GC Roots:

• 虚拟机栈中引用的对象
• 方法去中类静态属性引用的对象
• 方法去中常量引用的对象
• 本地方法栈中JNI（Native方法）引用的对象。

如何对对象进行回收？

标记——清除算法

复制算法

标记——整理算法

分代收集算法

对于新生代和老年代的对象进行不同的清理算法，一般来说，复制算法适合新生代，标记-清除算法和标记整理算法更适合老年代内存。

JVM对象内存管理策略

GC管理的内存分为三类区域，分别是Eden+Survivor（新生代），Tenured（老年代）和Permanent（永久代）。

1. 对象优先在Eden分配

2. 大对象直接进入老年代

3. 长期存活的对象将进入老年代

4. 动态对象年龄判定：当Survivor空间中相同年龄所有对象大小的总和大于Survivor空间的一半，年龄大于或者等于该年龄的对象可以直接进入老年代，无须等到MaxTenuringThreshold中要求的年龄。这是为了防止Survivor区溢出。

JVM常用的垃圾收集器

Serial收集器

单线程处理新生代GC。复制算法。STW

ParNew收集器

采用多线程处理新生代GC。复制算法。STW

Parallel Scavenge收集器

处理算法和ParNewGC完全一样。
但是，Parallel Scavenge收集器的特点是它的关注点与其他收集器不同，CMS等收集器的关注点是尽可能地缩短垃圾收集时用户线程的停顿时间，而Parallel Scavenge收集器的目标则是达到一个可控制的吞吐量（Throughput）。所谓吞吐量就是CPU用于运行用户代码的时间与CPU总消耗时间的比值，即吞吐量 = 运行用户代码时间 /（运行用户代码时间 +垃圾收集时间），虚拟机总共运行了100分钟，其中垃圾收集花掉1分钟，那吞吐量就是99%。

Serial Old收集器

单线程处理老年代GC。采用标记-整理算法。STW

Parallel Old收集器

多线程处理老年代GC。采用标记整理算法。STW

CMS(Concurrent Mark Sweep)收集器

四个阶段（基于标记-清理算法）：

• 初始标记 STW
• 并发标记
• 再次标记 STW
• 并发清理

问题：

1. 并发清理时预留空间不够造成并发清理(Concurrent Mode Failure)失败=>浮动垃圾(Floating Gabage)过多。
2. 内存碎片化问题。一旦发生大对象触发的FullGC，Serial Old回收则会出现长时间STW。

• CMS并发三色标记法

  1. 黑色：已经标记完引用对象的颜色
  2. 灰色：没有标记完引用对象的颜色
  3. 白色：默认垃圾（没有被标记颜色）

  • 标记问题：

    1. 本来A->B, B->D;
    2. 在A标记完，B部分标记后，B->D引用消失，D没有被标记，A->D引用建立
    3. 由于D从始至终都没有被标记

  • 标记问题一Incremental Update更正：

    1. 对于A->D（白)的引用建立，把A修正成灰色。

  • Incremental Update更正存在的ABA问题：

    1. 回收线程一：标记A属性1，正在标记属性2
    2. 业务逻辑线程二：把属性1指向白色D， A保持灰色
    3. 回收线程三: 更新属性2的标记，将A标记为黑色

  • CMS最终解决方案：必须STW从头扫描一次

G1(Garbage First)收集器

启动G1需要参数-XX:+UseG1GC，G1不是与其他GC分代处理垃圾的，而是对新生代和老年代均进行不同的GC。

Young GC:

• 标记-清除-复制算法整理 STW
  只对新生代区块进行清理，但是也会需要扫描所有region的Rset，否则不知道有哪些Old->Young的引用。

Mixed GC:
处理Mixed GC时只将将部分old区块进行回收。Rset记录了其他区块对本区块的引用。最终的扫描区域为Young+对Rset进行扫描，缩短了原来需要扫描整个Old时间。而且Young<->Old的引用都能快速找到。

并发标记分为四个阶段(基于标记-整理算法)：

• 初始标记 STW
• 并发标记
• 最终标记 STW
• 筛选回收 STW 根据停顿时间要求筛选出Old中的Cset集合，作为回收目标。

回收evacuation阶段（小区块进行复制整理避免碎片）：
需要STW，将选出的Cset中的对象进行复制到新的区块，清除掉原来的区块，达到收集的效果。

ZGC(Z Garbage Collector)收集器

ZGC（Z Garbage Collector）是一款由Oracle公司研发的，以低延迟为首要目标的一款垃圾收集器。它是基于动态Region内存布局，（暂时）不设年龄分代，使用了读屏障、染色指针和内存多重映射等技术来实现可并发的标记-整理算法的收集器。在JDK 11新加入，还在实验阶段，主要特点是：回收TB级内存（最大4T），停顿时间不超过10ms。m目前ZGC是实验性功能，可以通过-XX:+UnlockExperimentalVMOptions -XX:+UseZGC参数启动ZGC。

垃圾收集器参数

Problem

Write a class StockSpanner which collects daily price quotes for some stock, and returns the span of that stock’s price for the current day.

The span of the stock’s price today is defined as the maximum number of consecutive days (starting from today and going backwards) for which the price of the stock was less than or equal to today’s price.

For example, if the price of a stock over the next 7 days were [100, 80, 60, 70, 60, 75, 85], then the stock spans would be [1, 1, 1, 2, 1, 4, 6].

Example 1:

1
2
3
4
5
6
7
8
9
10
11

Input: ["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
Output: [null,1,1,1,2,1,4,6]
Explanation: 
First, S = StockSpanner() is initialized.  Then:
S.next(100) is called and returns 1,
S.next(80) is called and returns 1,
S.next(60) is called and returns 1,
S.next(70) is called and returns 2,
S.next(60) is called and returns 1,
S.next(75) is called and returns 4,
S.next(85) is called and returns 6.

Note that (for example) S.next(75) returned 4, because the last 4 prices
(including today’s price of 75) were less than or equal to today’s price.

Note:

1. Calls to StockSpanner.next(int price) will have 1 <= price <= 10^5.
2. There will be at most 10000 calls to StockSpanner.next per test case.
3. There will be at most 150000 calls to StockSpanner.next across all test cases.
4. The total time limit for this problem has been reduced by 75% for C++, and 50% for all other languages.

Solution

解题思路

本题考验的是对Java Stack类的熟练使用。

O(n)复杂度思路

不难发现，运用两个Stack可以灵活的将数组中的数字进行遍历比较，从而得出结果。但是由于Leetcode对于时间复杂度要求较高，因此同为O(n)算法，需要最大化的优化其系数，从而通过时间限制测试。

Leetcode solution中提出的一种简化计算的方法

在仔细分析对比数组的计算结果后，不难得出以下几个结论：

• 当数组元素值减少时,权重结果为1；
• 当数组元素值增加时，倒推前面小于该值的连续区间可以替换成局部最大值和其局部权重weight。局部最大值即当前元素值；而最末元素的权重，正好是其前面小于该值的连续区间的权重和+1。权重值则为我们需要的返回值。

以Example中的数组为例，用Stack<int[]>表示分步计算结果为：

1. [100, 1]
2. [100, 1], [80, 1]
3. [100, 1], [80, 1], [60, 1]
4. [100, 1], [80, 1], [70, 2]
5. [100, 1], [80, 1], [70, 2], [60, 1]
6. [100, 1], [80, 1], [75, 4]
7. [100, 1], [85, 6]
   …

实现技巧

需要注意的本解法并没有简化时间复杂度，因为在最差情况下（数列递减），计算的复杂度为O(n)。代码如下：

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

class StockSpanner {
    Stack<Integer> prices, weights;

    public StockSpanner() {
        prices = new Stack();
        weights = new Stack();
    }

    public int next(int price) {
        int w = 1;
        while (!prices.isEmpty() && prices.peek() <= price) {
            prices.pop();
            w += weights.pop();
        }

        prices.push(price);
        weights.push(w);
        return w;
    }
}

Angular binding brief introduction

This blog is talking about the template syntax of Angular 5. The reference topic is at https://angular.io/guide/template-syntax.

Angular one-way binding with DOM elements

For DOM elmenets that does simple display, Angular one-way binding is very useful. For example, pure text, or un-editable tables, one-way binding can quick get rendered by directly binding the Angular variable or using *ngFor iteration. There are three examples of one-way binding in the html template. THe binding objective can be expression, which does not change variables.

1
2
3

<p>Hello {{username}}.</p> <!-- pure one-way interpolation with {{}} syntax-->
<input [value]="username"> <!-- DOM property with [] binding -->
bind-target="expression" <!-- bind- prefix target binding-->

** Remember to user [] brackets to make the DOM property actively linked with Angular variables, otherwise the binding is worked as string type initialization only.

Angular two-way binding with DOM elements

For DOM elements that also can have user interactions like input elements, select elments, two-way binding or event binding is required to allow Angular know about the user action. The grammar to bind a two-way variable is to use [(target)].

There are some examples of Angular two-way binding:

1
2

<input [(ngModel)]="username"> <!-- property, like ngModel for form elements, with [()] syntax-->
bindon-target="expression" <!-- bindon- prefix target two-way binding-->

Angular event binding with DOM elements

Some DOM elements are not interact with text but events link click or text change, Angular also provides sytax for event binding so it can track user’s behavior based on DOM events. Vairables, like #event template input variable (let here), and template reference variable (#heroForm), which can be passed to the event handlers. The grammar to bind a event of a DOM is to use parenthesis with Angular event like (click). Event handlers can only be statements like methods of the component instance.

There are some examples of Angular event bindings:

1
2

(click)="click($event)" <!-- use DOM property binding with () syntax-->
on-target="statement"  <!-- use on- prefix target binding -->

Angular template binding targets

It’s not hard to see, binding targets in Angular includes HTML properties and events as below table.

Besides, Angular also supports built-in directives as below table.

Template reference variables

A template reference variable is often a reference to a DOM element within a template. It can also be a reference to an Angular component or directive or a web component.
Use the hash symbol (#) to declare a reference variable. The #phone declares a phone variable on an <input> element.

Example:

1
2
3
4

<input #phone placeholder="phone number">
<!-- lots of other elements -->
<!-- phone refers to the input element; pass its `value` to an event handler -->
<button (click)="callPhone(phone.value)">Call</button>

Template expression operators

The template expression language employs a subset of JavaScript syntax supplemented with a few special operators for specific scenarios. The next sections cover two of these operators: pipe and safe navigation operator.

The pipe operator ( | )

Angular pipes are a good choice for small transformations such as these. Pipes are simple functions that accept an input value and return a transformed value. They’re easy to apply within template expressions, using the pipe operator (|):

Example:

1

<div>Title through uppercase pipe: {{title | uppercase}}</div>

The safe navigation operator ( ?. ) and null property paths

The Angular safe navigation operator (?.) is a fluent and convenient way to guard against null and undefined values in property paths. Here it is, protecting against a view render failure if the currentHero is null.

Example:

1

The current hero's name is {{currentHero?.name}}

The Angular non-null assertion operator (!) serves the same purpose in an Angular template.

Example:

1
2
3
4
5

<!--No hero, no text -->
<div *ngIf="hero">
  The hero's name is {{hero!.name}}
</div>

The $any type cast function ($any( ))

Sometimes a binding expression will be reported as a type error and it is not possible or difficult to fully specify the type. To silence the error, you can use the $any cast function to cast the expression to the any type.

1
2
3
4

<!-- Accessing an undeclared member -->
<div>
  The hero's marker is {{$any(hero).marker}}
</div>

Angular binding different component properties

We usually binding a template to its own component class. In such binding expressions, the component’s property or method is to the right of the (=).

The Angular compiler won’t bind to properties of a different component unless they are Input or Output properties. You can’t use the TypeScript public and private access modifiers to shape the component’s public binding API.

Declaring Input and Output properties

An Input property is a settable property annotated with an @Input decorator. Values flow into the property when it is data bound with a property binding
An Output property is an observable property annotated with an @Output decorator. The property almost always returns an Angular EventEmitter. Values flow out of the component as events bound with an event binding.

Example:

In the sample for this guide, the bindings to HeroDetailComponent do not fail because the data bound properties are annotated with @Input() and @Output() decorators.

In src/app/app.component.html file, below code will through compile error as template of app component does not recognize the property of hero-detail component:

1
2

<app-hero-detail [hero]="currentHero" (deleteRequest)="deleteHero($event)">
</app-hero-detail>

In src/app/hero-detail.component.ts file, set @Input and @Output decorator with corresponding properties. Then the error is resolved.

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

...

@Component({
  inputs: ['hero'],
  outputs: ['deleteRequest'],
})

...

@Input()  hero: Hero;
@Output() deleteRequest = new EventEmitter<Hero>();

...

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