Java集合框架

Reference Link: http://www.runoob.com/java/java-collections.html

集合框架被设计成要满足以下几个目标。

• 该框架必须是高性能的。基本集合（动态数组，链表，树，哈希表）的实现也必须是高效的。
• 该框架允许不同类型的集合，以类似的方式工作，具有高度的互操作性。
• 对一个集合的扩展和适应必须是简单的。
  为此，整个集合框架就围绕一组标准接口而设计。你可以直接使用这些接口的标准实现，如下图所示，诸如： LinkedList, HashSet, 和 TreeSet 等,除此之外你也可以通过这些接口实现自己的集合。

从上面的集合框架图可以看到，Java 集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值对映射。Collection 接口又有 3 种子类型，List、Set 和 Queue，再下面是一些抽象类，最后是具体实现类，常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。

集合框架是一个用来代表和操纵集合的统一架构。所有的集合框架都包含如下内容：

• 接口：是代表集合的抽象数据类型。例如 Collection、List、Set、Map 等。之所以定义多个接口，是为了以不同的方式操作集合对象
• 实现（类）：是集合接口的具体实现。从本质上讲，它们是可重复使用的数据结构，例如：ArrayList、LinkedList、HashSet、HashMap。
• 算法：是实现集合接口的对象里的方法执行的一些有用的计算，例如：搜索和排序。这些算法被称为多态，那是因为相同的方法可以在相似的接口上有着不同的实现。
  除了集合，该框架也定义了几个 Map 接口和类。Map 里存储的是键/值对。尽管 Map 不是集合，但是它们完全整合在集合中。

集合框架体系如图所示:

集合接口

1. Collection 接口

Collection 是最基本的集合接口，一个 Collection 代表一组 Object，即 Collection 的元素, Java不提供直接继承自Collection的类，只提供继承于的子接口(如List和set)。
Collection 接口存储一组不唯一，无序的对象。

2. List 接口

List接口是一个有序的 Collection，使用此接口能够精确的控制每个元素插入的位置，能够通过索引(元素在List中位置，类似于数组的下标)来访问List中的元素，第一个元素的索引为 0，而且允许有相同的元素。
List 接口存储一组不唯一，有序（插入顺序）的对象。

3. Set 接口

Set 具有与 Collection 完全一样的接口，只是行为上不同，Set 不保存重复的元素。
Set 接口存储一组唯一，无序的对象。

4. SortedSet 接口

继承于Set保存有序的集合。

5. Map 接口

Map 接口存储一组键值对象，提供key（键）到value（值）的映射。

6. Map.Entry 接口

描述在一个Map中的一个元素（键/值对）。是一个Map的内部类。

7. SortedMap 接口

继承于 Map，使 Key 保持在升序排列。

8. Enumeration 接口

这是一个传统的接口和定义的方法，通过它可以枚举（一次获得一个）对象集合中的元素。这个传统接口已被迭代器取代。

9. Queue 接口

Queue是队列实现，实现了先进先出功能。

集合实现类（集合类）

抽象类

集合类

其他：数据结构类

遍历示例代码

遍历ArrayList

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

import java.util.*;
 
public class Test{
 public static void main(String[] args) {
     List<String> list=new ArrayList<String>();
     list.add("Hello");
     list.add("World");
     list.add("HAHAHAHA");
     //第一种遍历方法使用foreach遍历List
     for (String str : list) {            //也可以改写for(int i=0;i<list.size();i++)这种形式
        System.out.println(str);
     }
 
     //第二种遍历，把链表变为数组相关的内容进行遍历
     String[] strArray=new String[list.size()];
     list.toArray(strArray);
     for(int i=0;i<strArray.length;i++) //这里也可以改写为  foreach(String str:strArray)这种形式
     {
        System.out.println(strArray[i]);
     }
     
    //第三种遍历 使用迭代器进行相关遍历
     
     Iterator<String> ite=list.iterator();
     while(ite.hasNext())//判断下一个元素之后有值
     {
         System.out.println(ite.next());
     }
 }
}

遍历Map

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

import java.util.*;
 
public class Test{
     public static void main(String[] args) {
      Map<String, String> map = new HashMap<String, String>();
      map.put("1", "value1");
      map.put("2", "value2");
      map.put("3", "value3");
      
      //第一种：普遍使用，二次取值
      System.out.println("通过Map.keySet遍历key和value：");
      for (String key : map.keySet()) {
       System.out.println("key= "+ key + " and value= " + map.get(key));
      }
      
      //第二种
      System.out.println("通过Map.entrySet使用iterator遍历key和value：");
      Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
      while (it.hasNext()) {
       Map.Entry<String, String> entry = it.next();
       System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
      }
      
      //第三种：推荐，尤其是容量大时
      System.out.println("通过Map.entrySet遍历key和value");
      for (Map.Entry<String, String> entry : map.entrySet()) {
       System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
      }
    
      //第四种
      System.out.println("通过Map.values()遍历所有的value，但不能遍历key");
      for (String v : map.values()) {
       System.out.println("value= " + v);
      }
     }
}

题外话： Java 数组

Java 数组是很容易和Java动态数组(ArrayList)进行混淆的数据结构。其实Java数组本身并不具有方法，唯一的属性是length。对于数组的大小也不能改变，很多功能需要借助Utility类Arrays提供的静态方法。

Java中的所有数组都是通过Array类实例化。Array类没有public的构造方法，数组是通过Array的newInstance()方法进行实例化。Java数组是支持所有类型的，也就是说对于自定义引用类型，也能创建数组类型，但是与动态数组的方式不同，内存分配机制上也有所不同。

Array类源码

数组类的实现主要基于本地方法创建，申请分配一段连续内存，每一个数组元素支持强类型检查。长度不支持扩展。

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

package com.lang;

public final class System {
    //System 类不能被实例化。 
    private System() {}
    //在 System 类提供的设施中，有标准输入、标准输出和错误输出流；对外部定义的属性
    //和环境变量的访问；加载文件和库的方法；还有快速复制数组的一部分的实用方法。
    /**
    * src and dest都必须是同类型或者可以进行转换类型的数组．
    * @param      src      the source array.
    * @param      srcPos   starting position in the source array.
    * @param      dest     the destination array.
    * @param      destPos  starting position in the destination data.
    * @param      length   the number of array elements to be copied.
     */
    public static native void arraycopy(Object src, int srcPos, Object dest,
            int destPos, int length);
}
package com.lang.reflect;

public final class Array {
    private Array() {}
    
    //创建一个具有指定的组件类型和维度的新数组。
    public static Object newInstance(Class<?> componentType, int length)
            throws NegativeArraySizeException {
        return newArray(componentType, length);
   }

    private static native Object newArray(Class componentType, int length)
            throws NegativeArraySizeException;
}

数组声明与初始化

1
2
3
4
5
6

//直接声明空数组
dataType[] arrayRefVar = new dataType[arraySize];
//直接引入数组元素，用花括弧创建
int [] arrayRefVar2 = {1, 2, 3};
//访问时通过下标访问
System.out.println(arrayRefVar2[0]);

多维数组声明与初始化

多维数组其实就是一维数组的嵌套扩展，维度取决于数组各个元素的类型，如果是一个数组则能增加一个维度。因此多维数组的创建与访问也是基于一维数组的方法。Array类属性只有length一个，访问是基于下标的。

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

//直接声明矩阵二维数组
dataType[][] arrayRefVar = new dataType[colsize][rowsize];
//分段申明非矩阵二维数组
dataType[][] arrayRefVar2 = new dataType[colsize][];
arrayRefVar2[0] = new dataType[row1size];
arrayRefVar2[1] = new dataType[row2size];
//直接引入数组元素，用嵌套花括弧创建，按照维度分配，第一个是第一列
int[][] arrayint = {
  {1, 2, 3},
  {2, 3, 4}
}
//直接引入数组元素，用下标顺序填入
int[][] array2 = {new int[2], new int[3]};

//数组的访问是基于下标 array2[col][row]

题外话: Arrays 类

java.util.Arrays 类能方便地操作数组，它提供的所有方法都是静态的。
具有以下功能：

• 给数组赋值：通过 fill 方法。
• 对数组排序：通过 sort 方法,按升序。
• 比较数组：通过 equals 方法比较数组中元素值是否相等。
• 查找数组元素：通过 binarySearch 方法能对排序好的数组进行二分查找法操作。

题外话： Collections 类

读书笔记 —— 《凤凰项目：一个IT运维的传奇故事》

本书从IT运维管理者的第一视角，讲述了IT部门每天都会发生的事情，并通过从工厂管理经验中借鉴到的方法，改善了IT部分的产能的故事。

IT工作者的每日工作项目

IT人员的工作往往分为如下几个项目。所以每一个程序员需要重视这四类工作。

业务项目

这是多数开发项目所包含的业务举措，通常隶属于项目管理办公室。虽然是IT项目，但大多数是跟业务的利润有直接相关联。

IT内部项目

IT内部项目包括可能由业务项目衍生出的基础架构或IT运维项目，亿级内部生成的改进项目（例如创建新环境和部署自动化等）。这类项目业务部门并不是直接集中跟踪管理的，而属于预算所有者（例如数据库经理、存储管理经理和分布式系统经理）。

变更

经常由前两种类型的工作引起，往往在保修系统中被跟踪（例如IT运维补救、JIRA或者用于开发的敏捷计划工具）。事实上，在价值流的两个不同部分中存在两个工作跟踪系统，这会引起问题，尤其在交接工作的时候。

某些情况下，在一些兼具功能开发和服务交付指责的专门团队中，所有工作都会处在同一个系统中。这样做的好处是，操作层面的故障会和功能缺陷以及新的特性功能一起，在存量工作和现行工作中显现。

在生产环境的变更是需要严格关注的，有的公司会专门对生产环境的变更进行记录。尤其会对变更本身的原因，步骤，以及风险评估和处理细节都进行记录。变更记录会交由管理者进行审批从而在计划时间窗口生效。

计划外项目/救火

包括操作事故和操作问题，通常由上述三类型的工作导致，而且往往以牺牲其他计划内工作为代价。

布伦特——约束点问题

文中的工程师布伦特是IT运维部的约束点，原因是：

• IT运维工作中最优秀的救火队员
• IT运维视角唯一的项目系统架构师
• IT变更项目中时常存在的执行者
• 项目半成品堆积：由于救火项目或者忙等待问题造成。

每个工作中心中都存在他的身影，个人能力的有限决定了IT部门的产出有限。

约束点问题解决了，工作产能问题便能解决。所有在非约束点做的改进都是假象。

对应的改善约束点问题的方案：

• 建立L3支持工程师代替执行并学习布伦特的救火技术，建立其他人可以借鉴的trouble shooting检查清单。
• 专一做到资深架构应该做的工作：关键项目的系统架构
• 将需要布伦特参与的项目进行工作和流程标准化管理
• IT工作可视化并控制半成品

等待时间是工作中心中某个资源忙碌成都的函数。下图横轴坐标上是工作重心中给定资源的忙碌百分比，纵坐标轴上是大致的等待时间（更确切的说是队列长度）。等待时间=忙碌时间百分比/空闲时间百分比。曲线的形状表明，当资源使用率超过80%时，等待时间就会直线上升。这会对项目交付产生灾难性后果。

看板对于IT中的半成品问题是最有效、最简单的一种对策。两本书推荐阅读：

1. 《个人看板:了解工作/驾驭生活》by吉姆·本森和托尼安妮·德马里亚·巴里
2. 《看板方法：科技企业渐进变革成功之道》by戴维·J·安德森

工作流程改进————形

为了将IT的工作项目完善的进行预先评估和量化分析，每一项工作类型都可以进行执行周期的管理与规划，尽量减少工作半成品的积压，并且最大化工作成品的“吞吐量”。本文提出需要进行“改进形”计划：

以两周为周期，进行两个“计划-执行-审核-落实”改进周期，确立项目需要的四大要素：机器、方法、人员与测评。每两周必须做出一些改进，无论任何形式的改进。

积压的项目分为三类：需要布伦特参与的项目，可以提高布伦特生产力的项目，其他项目。优先开展后两类项目；对于需要布伦特参与的项目遵循约束点问题解决方案进行优化。

“改进形”带来的好处：

• 提供一种适用于各种问题或挑战的系统化科学规程；
• 组织成员普遍养成解决问题的习惯；
• 通过让经理开展周期性指导，让其向教练和导师的角色转变；
• 通过让人们每天慢慢进步的方法，形成PDCA（Plan-Do-Check-Action）。

微软IT案例研究《在9个月内实现逆袭：在微软IT部门应用鼓点-缓冲-绳子解决法（译注：即限制驱导式排程法）》，作者是戴维·J．安德森和德拉戈什·杜密特里乌。

当时安德森和杜密特里乌两人都在微软，他们描述了以前那种糟透了的状态。大多数IT从业人员>对那种状态都再熟悉不过了。

❑ 完成业务部门要求的工作耗时过长：平均交付周期是155天。

❑ 对于延误和长交付周期的不满迫使IT管理作出“更多的工作预估”，这让经理们不得不把全部时
间都用来做PPT，而不是干实事（因为业务部门的结论是他们没有作出正确的工作预估）。

❑ 不管业务部门提出什么要求，回答永远是“做这件事需要5个月”。

❑ 每项任务都预计在20天内完成，但是没人知道多出的那135天都去哪儿了。

杜密特里乌在报修系统中创建了一个名叫“等待德拉戈什”的新字段（实际上，这个报修系统是微>软缺陷跟踪系统），以及时发现工作阻碍。他很快得出结论，项目团队70%的时间都卡在了别人>那里——也就是说，在70%的时间里，工作都在排队。
杜密特里乌认为，他的团队一个月只能完成3项工作，按照这个速度，需要三年才能完成所有的>工作。以下是他提出的对策及其惊人结果。

❑ 他们不再预估工作，而采用根据历史数据得出的实际时间——他们有80个人——报修系统里有多>年的工作记录供他们使用。这样做的结果是开发和测试效率立刻提高了30%。

❑ 他们不再采用成本核算，而采用简单的“基于预算贡献的ROI（Return on Investment，投资>回报率）”。所节省的时间让PM能力立刻提高了20%。

❑ 发现约束点是开发部之后，PM接管了许多开发任务，把开发能力提高了20%。这样做也让开发>人员更加高兴，因为他们可以专心写代码，不用再作任务预估了。

❑ 他们引进了一名可用性专家来调整变更申请表。（他打趣说：“我们得填完4页表格，才能得到>一杯水；我们把4页表格换成2页的，上面还有很多自由格式字段，目的是保证从事这项工作的人>了解其所需的全部信息。”）

❑ 接着他们减少了系统中允许的半成品数量：一开始平均有40到60个未结项目，他们把未结项目>数减少到了5个。

❑ 然后他们创建了工作缓冲区，任何遇到阻碍的开发或测试人员都能在缓冲区里做一些工作。

❑ 交付周期从155天下降到22天。这么短的交付周期让他们创造了一个新的SLA认证（SLA >guarantee）,25天（哇哦！）。

❑ 他们的下一轮生产能力大幅提高来自于增加开发人员数量，因为每两天的开发工作就需要一天>的测试工作。他们提拔了愿意参与开发工作的测试人员，把开发人员和测试人员的比例从1∶1提>高到2∶1。

❑ 上述种种的结果是什么？他们在9个月里完成了整整3年积压下来的工作；对他们服务的需求量>也增加了，然后他们继续在其后的每个月都顺利完成并交付了所有业务部门要求的工作；不仅没>人被解雇，而且很多人还升了职。
杜密特里乌说：“我们始终致力于降低交付周期，而不是开发和测试自身的优化，因此我们成功>了。”

这只是详细描述的众多惊人转变之一。难以置信的是，转变主要不是基于自动化，相反，这种不>可思议的改进来自于调整关于工作系统的策略和控制半成品的策略，确保有一个高效的跨职能团>队，让所有事情都为约束点服务，以及管理好工作交接。

IT工作管理核心思想

三步工作法

第一工作法是关于从开发到IT运维再到客户的整个自左向右的工作流。为了使流量最大化，我们需要小的批量规模和工作间隔，决不让缺陷刘翔下游工作中心，并且不断为了整体目标(相对于开发功能完成率、测试发现/修复比率或运维有效性指标等局部目标）进行优化。

必要的做法包括持续构建、集成以及部署，按需创建环境，严控半成品，以及构建起能够顺利变更的安全系统和组织。

第二工作法是关于价值流各阶段自右向左的快速持续反馈流，放大其效益以确保防止问题再次发生，或者更快地发现和修复问题。这样，我们就能在所需之处获取或嵌入知识，从源头上保证质量。

必要的做法包括：在部署管道中的构建和测试失败时“停止生产线”；日复一日地持续改进日常工作；创建快速的自动化测试套装软件，以确保代码总是处于可部署的状态；在开发和IT运维之间建立共同的目标和共同解决问题的机制；建立普遍的产品遥测技术，让每个人都能知道，代码和环境是否在按照设定的运行，以及是否达到了客户的目标。

第三工作法是关于创造公司文化，该文化可带动两种风气的形成：不断尝试，这需要承担风险并从成功和失败中吸取经验教训；理解重复和练习是熟练掌握的前提。

尝试和承担风险让我们能够不懈地改进工作系统，这经常要求我们去做一些与几十年来的做法大不相同的事。一旦出了问题，不断重复的日常操练赋予我们的技能和经验，令我们可以撤回至安全区域并恢复正常运作。

必要的做法包括营造一种勇于创新、敢于冒险（相对于畏惧或盲目服从命令）以及高信任度（相对于低信任度和命令控制）的文化，把至少20%的开发和IT运维周期划拨给非功能性需求，并且不断鼓励进行改进。

团队领导力的寓言

这是帕特里克·兰西奥尼在《团队领导的五大障碍：关于领导力的寓言》（The Five Dysfunctions of a Team: A Leadership Fable）一书中描述的方法。
他认为，团队无法达成目标的一个核心诱因是信任缺失。在他的模型中，五大障碍被描述为：

• 信任缺失——不愿在团队中显示弱点；
• 惧怕冲突——在充满激情的建设性辩论中寻求和谐的假象；
• 缺乏诚意——假意与团队的决策达成一致，形成模棱两可的公司氛围；
• 回避问责——面对员工的失职行为，逃避追责，降低了工作标准；
• 忽视结果——对个人成就、地位和自我价值的关注超过了对团队成功的关注。

考虑到开发部和IT运维部之间，以及IT和“业务部门”之间存在着长期、剧烈的部门斗争，我想我们非常需要兰西奥尼先生的教诲以实现开发运维的理想。
通常来说，运用兰西奥尼先生方法论的第一步，是领导人要展示自己的弱点（或者起码要从塑造示弱的行为着手）。在《凤凰计划》中，史蒂夫多年来已将这一实践内化于心，并主导了一场关于个人经历的分享活动。

信息安全问题解决思想

以不对IT系统做过多无用功就保护公司不受审计困扰，才是最终的胜利。而不是一昧的强制加入新的安全补丁，限制IT系统的功能与产出更多的维护问题。正如QA不需要测试不再需要的功能和不可能发生的性能压力，不要犯“眼界的错误”。

优先项目永远优先

关乎公司存亡的项目永远放在第一位。必要时可以冻结其他项目进度以提供充足的资源，人力和时间。

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