作者归档：Young

使用Grafana+InfluxDB展示Nagios监控数据

发表回复

概述

Nagios作为监控软件来说已经让人基本满意了，但是个人在使用中感觉还存在部分问题：

不能绘图

可能有同学会说不是有PNP4Nagios这样的软件吗？这个软件Nagios并没有默认携带，需要自己手动安装配置。

另外PHP4Nagios虽然已经能满足显示上的需求，但是绘图效果比较古老（图片来自网络，侵删）：

PNP4Nagios sample

并且不能对某些数据进行对比（比如多台机器的负载情况在同一个图表中显示）。

无法查看历史数据

Nagios只能看到“现在”的数据，无法回顾历史以及查看趋势。

譬如，如果使用现有的Nagios，想要回顾周日半夜任务对系统的消耗时，就会比较抓瞎了。

方案

绘图

先说绘图。

绘图作为一个附加的功能，可以考虑现有的一些优秀的数据展现软件，譬如Kibana和Grafana。

个人认为，Kibana更适合展现日志计数类型的数据，并且本身没有权限控制等功能，这一点比较麻烦，虽然可以通过第三方插件或者HTTP Basic Auth来解决，但是总是增加了维护成本。

相比之下，Grafana带有权限控制，能支持相当多的时序数据库，从graphite、opentsdb、influxdb，当然也有ES。多条曲线同时展示时还可以看到具体数值，显示效果也相当不错。

Grafana sample from it's website

并且，Grafana在4.0后将会具有告警功能，玩法会变得更多。

最终选择Grafana作为展示端。

数据内容

提一下数据内容。

在这个方案中，我们展现的数据，实际上是Nagios插件产生的Performance Data（或者叫PERFDATA），如果自行编写的插件没有按照 PERFDATA 的格式输出信息，是不会被收集到InfluxDB中的。如果有自行编写业务监控插件，除了基本的返回码和错误信息之外，要考虑按照标准输出相关的信息，以便收集到InfluxDB中。

Nagios 3的插件多行输出格式为：

TEXT OUTPUT | OPTIONAL PERFDATA

LONG TEXT LINE 1

LONG TEXT LINE 2

…

LONG TEXT LINE N | PERFDATA LINE 2

PERFDATA LINE 3

…

PERFDATA LINE N

如磁盘信息的收集，单行模式很好理解，通过 | 分隔输出信息以及 PERFDATA；多行模式的话，引用官网的例子：

DISK OK – free space: / 3326 MB (56%); | /=2643MB;5948;5958;0;5968

/ 15272 MB (77%);

/boot 68 MB (69%);

/home 69357 MB (27%);

/var/log 819 MB (84%); | /boot=68MB;88;93;0;98

/home=69357MB;253404;253409;0;253414

/var/log=818MB;970;975;0;980

第一行仍然可以按照单行模式进行理解（红色部分是输出信息，橙色部分是 PERFDATA），从第二行开始，每行一个输出信息，最后将剩余的 PERFDATA 紧接着输出信息的最后一行，通过 | 分隔，逐行输出。

每项 PERFDATA 格式为：

'label'=value[UOM];[warn];[crit];[min];[max]

1 2	'label'=value[UOM];[warn];[crit];[min];[max]

引用上述例子的数据 /=2643MB;5948;5958;0;5968，可以看到对应关系为：

label	/
value	263MB
warn	5498
crit	5958
min	0
max	5968

UOM 表示 unit of measurement，即单位，可以是：

不设定（即数字）
秒s（或者ms或us）
百分数%
字节B（或者KB, MB, TB）

详情可以参阅 Nagios Plugin Development Guidelines 以及 Nagios Plugin API。

数据落地

只有Grafana是不能完成期望的工作的，Grafana只是展现工具，需要有数据源才能展现。

目前主力使用的时序数据库是ES，但是可以看到Nagios官方网站上关于绘图这一主题推荐的插件中没有看到写入到ES中的插件（ES倒是可以把输出作为监控信息交给Nagios，参见）。

查阅资料，graphite性能可能存在问题，opentsdb需要有专业的运维同学维护（毕竟是Hadoop衍生产品），InfluxDB兼顾了性能和运维成本，考虑使用。

值得一提的是，InfluxDB提供了Web管理端，查询语句上类似SQL，便捷程度让人满意。

数据收集

落地方式确定之后，需要考虑如何将Nagios收集的诸如load、CPU、内存使用等信息存入InfluxDB了。

graphios可以相当便捷的完成这一工作。这是一个将Nagios perf data写入到InfluxDB中的工具。配置也相当便捷，基本上按照README即可完成。

Nagflux看起来也是不错，然而问题在于这个适用于4.x版本的Nagios，在不打算升级Nagios的情况下，只能放弃。

但是，凡事总有例外，使用软件的特定组合的情况下，会出现一些问题。

数据解析异常

graphios在Nagios官网上声称匹配3.x版本的Nagios，但是在与实际使用的Nagios 3.5结合时，会出现部分perf data无法成功解析的情况，检查后发现Nagios 3.5的部分数据在graphios读取时，并没有按数据协议组织，导致解析错误。

对此，针对输出数据，修改了解析所在部分源码进行了匹配，筛选出了所需数据。

InfluxDB版本

提示的InfluxDB版本较新，为0.13，然而，在graphios的配置文件中，backend部分，只有enable_influxdb09以及enable_influxdb选项，默认使用的json数据写入协议已经在0.13中废弃。

上述问题，考虑到版本后续兼容性，将0.13视作0.9版本配置，并且配置数据写入协议为line即可（即配置influxdb_line_protocol = True）。

为了让graphios永驻后台，可以考虑使用supervisord等工具。

展现样例

load

CPU

小结

使用Nagios+graphios+InfluxDB+Grafana可以将监控数据以更好的方式进行展现，并能够回顾历史，查看趋势，随着Grafana的升级，还可以有更多的玩法。

《格鲁夫给经理人的第一课》

发表回复

概述

《创业维艰》中多次提到格鲁夫的这本著作，作为作者霍洛维茨称赞的书籍，自然是需要阅读一番。

安迪·格鲁夫作为一名匈牙利移民，经过自己积极努力的学习，成为了一名工程师，作为Intel的第三名员工，参与了Intel的创建，历经工程师、工程经理，最终作为Intel的总裁/CEO，成就了Intel的故事。格鲁夫已于2016年3月21日逝世，然而这本1995年出版的书籍再版多次，影响可谓众多。

格鲁夫最为我熟悉的一点，应该是Andy and Bill’s Law，即Andy gives, Bill takes away，直到现在，制程的进步和技术的突破终于让CPU的性能似乎超过了操作系统和应用软件带来的消耗。

书名直接指向“经理人”，但是格鲁夫所指的经理人，并不单指是管理工作者，格鲁夫认定的中层经理人，也包括了解工作所需技能，运用经验、学识以及技术影响他人工作的人，也就是技术支持经理人。个人认为作为有一定的工作年限的工程师来说，一定程度上与这个概念有所契合。

书名虽然是指向管理，但是书中观点也许能让自己从另一个角度观察自己的工作。

笔记

新环境的规则是：第一，事情发生的速度越来越快；第二，事情总有人能做，如果你不做，我们就另请高明。

越来越充满危机感的工作环境。

让混沌丛生，然后掌握混沌

产出导向管理；团队意识；管理杠杆率；

本书提出的三个基本概念

一个经理人的产出，便是他所管理或影响所及的部署工作的成效和综合。

必须按预定的时间、可接受的品质以及可能的最低成本，按照顾客的需求制造及运输产品。

格鲁夫对生产的一个定义，程序员的工作中，指向的应是里程碑，代码质量，开发工时，实现产品需求。

可选的指标也许不计其数，但除非“每一项指标个针对不同作业目标评估”，这整套指标才会发挥功效。

通过“指标配对”的方法避免反应过度。

指标运用的第一条原则是，“有总比没有好”。

指标运用的第二条原则是，一个好的指标应该是用来衡量具体且可计算的事情的。

上述观点与SMART部分重合

员工永远会将交差的时间拖到最后一秒。

个人认为这是和人的惰性做斗争，同时发生了这类事情，也可能会发现糟糕的时间规划。

“监视器”的执行成本比“海关”低。广设关卡可以提升产品的品质，但是应该设多少则很难有定论。

提到的“监视器”指的是抽查的方法，“海关”则是普查。毋庸置疑，普查带来的成本必定是巨大的，追求质量也不能忽视效率。事必躬亲的产出效果不一定理想，正常情况下，事情越大，个人能力会显得不足，当然也会有例外。

必须了解哪些活动有最高的杠杆率。

时间成本会越来越大，追求事半功倍是必然。

对于大多数的经理人而言，最重要的信息往往来自于简短而非正式的谈话。

书面报告的作用在于建立数据文件、过滤并确认纷至沓来的各种信息，且要避免漏网之鱼。

报告用来表示一个人的自律，远胜于它咋传递信息上的作用。

考虑口头尽快同步信息，书面文字落实，定期重复检查。

对于报告的观点，认同。

如果你的授权人猜不透自己已被授权或不明白被授权的范围，将会有极高的负杠杆率。

不信任感与不明确的负面影响。

没有完备的监督计划的授权等于渎职。你绝对不能完全的抽身，即使你已经授权，你还是的负成败责任。全程监督整个被授权的案子是确保结果进入任意的唯一方法。监督不是干涉，而是通过不是的检查，来确定活动的进行移入预期。因为监督你熟悉的工作比较容易，所以如果有机会，你应该把自己熟悉的工作授权给他人。

理智让你松手，但情感上你可以能老大不愿意。

手到擒来的熟练工作，复杂度不高的就应当交出，获取更多的时间完成更重要的工作。不需要通过这些来找存在感。

找出限制步骤

类似的工作集中一起做

安排好你的日程表

以上是格鲁夫提到的时间管理的几个方向。限制步骤即必须完成的工作，了解清楚可以重新安排整个工作过程。类似的工作集中一起做解决中断带来的成本问题。

安排日程表上来说，个人觉得，对于超过工作负荷的事说不相当重要，这是对整个工作负责，可以有重新安排的空间。承担更多的责任当然是必须的，但是把事情搞砸是更不能接受的，对个人来说，也是灾难性的。

会议是从事管理工作必经的媒介。

格鲁夫认为会议分为两种，一种是信息交流的的“过程导向”型会议，如例会；一种则是解决特定问题的“任务导向”会议，是随着工作的变化而随时发生的。

会议强度和熟悉度负相关。

对于一对一会议，格鲁夫认为应当让会议对象承担更重要的角色，由会议对象掌握会议议程，鼓励提出隐藏问题（帮助提早发现解决），让会议对象知无不言。同时也需要有会议纪要（会议纪要可以一定程度上表示已关注，同时也方便回顾）。

决策权不再完全由职位决定，另一种掌握知识和技能到那时职位不高的决策新秀将脱颖而出。

决策权的指定和执行应交给最低层级。

我们这个产业，必须要结合具有“知识力”及“权利”的两种人一起决策，如果我们没有办法让两种人合作以提升决策品质，那企业的衰亡就是迟早的事。

工具和外部环境的变化会带来技术技能上的盲区，很难永远跟上这类变化，拥有专业知识的人员的作用正是跟上变化。

后两句如字面意思。

当一群职位相当的人要开会时，总需要一个职位较高的人与会。不见得最能干或者最具有专业知识，但是他能控制会议的进行。

同级、同类害怕成为异类。

在指定政策之前，经理人应对一下6个问题的答案了然于胸：1.决策的内容。2.决策的问题。3.决策人。在制定决策前应先向谁咨询。5.谁对此决策一言九鼎，或是能全盘否定。6，谁应该在决策指定行后被告知。

如字面意思。

我见过太多人，他们了解现状与理想之间的差距，并且努力想要缩小此察觉，但他们不明白今日他们所面临的问题，经常是源于过去规划的失误。

Nagios检查域名是否可连通

发表回复

概述

日常服务器使用中，可能存在某些服务器被意外的更改路由表等问题，在多张网卡的情况下，可能会出现Nagios可以发现服务器，但是实际上服务器对外连接不可用的情况。

这必然是对服务有着致命打击的，将其纳入监控势在必行。

分析

大多数时候，我们只需要要关心这个服务需要访问的域名的连通性，即主机的连通性，可以考虑通过nagios定时ping。如果是web服务，还可以通过curl判断访问情况。

思路确定的话，那么编写插件即变得很容易。针对Nagios的使用上，可以考虑定义自定义命令，通过nrpe调用客户端上的插件，通过主动检查的方式进行。

通过nrpe调用命令的设置上有一个很有趣的地方，客户端定义的指令和服务端定义的指令有一个位置的偏移，因为服务端的调用check_nrpe插件第一个参数$ARG1必定是客户端上的命令名称。所以服务端的定义的$ARG2将会被作为到客户端的$ARG1使用。

例如，服务端指定命令为：

define command {
    command_name                    check_domain_accessibility
    command_line                    $USER1$/check_nrpe -c $ARG1$ -a $ARG2$ $ARG3$ $ARG4$
    register                        1
}

define command {

command_name check_domain_accessibility

command_line $USER1$/check_nrpe -c $ARG1$ -a $ARG2$ $ARG3$ $ARG4$

}

客户端的命令为：

command[check_domain_accessibilty]=/path/to/plugins/check_domain_accessibility.sh -d $ARG1$ -t $ARG2$ -p $ARG3$

1 2	command[check_domain_accessibilty]=/path/to/plugins/check_domain_accessibility.sh -d $ARG1$ -t $ARG2$ -p $ARG3$

服务端	客户端
$ARG1$	check_domain_accessibilty
$ARG2$	$ARG1$
$ARG3$	$ARG2$
$ARG4$	$ARG3$

可以看到的对应关系为：

插件代码

插件代码通过shell编写，按照Nagios插件的特定，只出现OK/CRITICAL/UNKNOWN三种情况。

考虑到内网请求是主要关注的点，连通性不佳（如ping丢包）也会被归类到CRITICAL之中，用于提醒SA关注。

#!/bin/sh

usage()
{
    echo "Usage: `basename $0` -d DOMAIN [-t TIMEOUT_S -p y|n]"
    exit 3
}

do_curl()
{
    domain=$1
    timeout=$2

    result=`curl -I -s --connect-timeout $timeout $domain -w %{http_code} | tail -n1`

    if [ "$result""x" = "200x" ];then  
        return 0
    else
        return 1
    fi
}

do_ping()
{
    domain=$1
    timeout=$2
    package=4

    if [ ! -z $3 ];then
        if [ $3 -gt 0 ];then
            package=$3
        fi
    fi

    timeout=$(($timeout*$package))

    result=`ping -t $timeout -c $package $domain | egrep '\s0*\.?0%\spacket\sloss' | wc -l`

    if [ $result -eq 1 ]; then
        return 0
    else
        return 1
    fi
}


[ $# -eq 0 ] && usage

DOMAIN=""
TIMEOUT_S=1
PING_FIRST=""

while getopts ":d:t::p::" OPTION
do
    case $OPTION in
        d)
            DOMAIN=$OPTARG
            ;;
        t)
            TIMEOUT_S=$OPTARG
            ;;
        p)
            PING_FIRST=$OPTARG
            ;;
        \?)                       
            usage
            ;;
    esac
done

if [ -z $TIMEOUT_S ];then
    TIMEOUT_S=1
fi

if [ $PING_FIRST"x" = "nx" ];then
    PING_FIRST="n"
else
    PING_FIRST="y"
fi

if [ -z "$DOMAIN" ];then 
    echo "You must specify DOMAIN with -d option"
    exit 3
fi

if [ $PING_FIRST = "y" ];then
    $(do_ping $DOMAIN $TIMEOUT_S)
else
    $(do_curl $DOMAIN $TIMEOUT_S)
fi

check_result=$?

if [ $check_result -ne 0 ];then
    if [ $PING_FIRST = "n" ];then
        $(do_ping $DOMAIN $TIMEOUT_S)
    else
        $(do_curl $DOMAIN $TIMEOUT_S)
    fi
    check_result=$?
fi
  
if [ $check_result -eq 0 ];then  
    echo "$DOMAIN is reachable"
    exit 0
else  
    echo "$DOMAIN not reachable"
    exit 2
fi

100

101

102

103

104

105

106

107

108

109

110

#!/bin/sh

usage()

{

echo "Usage: `basename $0` -d DOMAIN [-t TIMEOUT_S -p y|n]"

exit 3

}

do_curl()

{

domain=$1

timeout=$2

result=`curl -I -s --connect-timeout $timeout $domain -w %{http_code} | tail -n1`

if [ "$result""x" = "200x" ];then

return 0

else

return 1

}

do_ping()

{

domain=$1

timeout=$2

package=4

if [ ! -z $3 ];then

if [ $3 -gt 0 ];then

package=$3

timeout=$(($timeout*$package))

result=`ping -t $timeout -c $package $domain | egrep '\s0*\.?0%\spacket\sloss' | wc -l`

if [ $result -eq 1 ]; then

return 0

else

return 1

}

[ $# -eq 0 ] && usage

DOMAIN=""

TIMEOUT_S=1

PING_FIRST=""

while getopts ":d:t::p::" OPTION

case $OPTION in

DOMAIN=$OPTARG

;;

TIMEOUT_S=$OPTARG

;;

PING_FIRST=$OPTARG

;;

\?)

usage

;;

esac

done

if [ -z $TIMEOUT_S ];then

TIMEOUT_S=1

if [ $PING_FIRST"x" = "nx" ];then

PING_FIRST="n"

else

PING_FIRST="y"

if [ -z "$DOMAIN" ];then

echo "You must specify DOMAIN with -d option"

exit 3

if [ $PING_FIRST = "y" ];then

$(do_ping $DOMAIN $TIMEOUT_S)

else

$(do_curl $DOMAIN $TIMEOUT_S)

check_result=$?

if [ $check_result -ne 0 ];then

if [ $PING_FIRST = "n" ];then

$(do_ping $DOMAIN $TIMEOUT_S)

else

$(do_curl $DOMAIN $TIMEOUT_S)

check_result=$?

if [ $check_result -eq 0 ];then

echo "$DOMAIN is reachable"

exit 0

else

echo "$DOMAIN not reachable"

exit 2

《创业维艰》

发表回复

概述

《创业维艰》是今年来读过的印象较为深刻的书籍。

作者本·霍洛维茨作为硅谷投资教父级的任务，本身是一个成功的创业者，带领自己创业的LoudCloud公司活过了互联网泡沫破碎的时代，本人也是个成功的投资家，Facebook, Instagram, Twitter, Airbnb这些赫赫有名的公司都有他的手笔。

书中提到的一些观点个人读到之后觉得较为有趣，虽然并不身处于创业公司，但是读到之后个人还是引发了自己的思考，了解了创业这个方向的另一面。书中作者的措辞和举例的诚恳态度相当让人印象相当深刻。

成功者的经历几乎无法复制，但是成功者的经验却是可能会后来者规避更多陷阱的有效参考。

在Kindle上入了中信的译本，对自己觉得有意思的一些观点做简要的记录。

书摘

寻找一个统一市场，其中只要有一个投资者点头，即可成功。即便30位投资者即便全都摇头拒绝也无关紧要。

笔记：毕竟拥有十足信心的人在少数，即便是到了投资者这个级别，依然也有跟风的现象存在。

每当大公司打算事实一个计划时，该计划总会落到某个人身上，而此人却极有可能延误整个计划。如果此人是工程师，他也许会因为等待上层觉得而踌躇不前；如果此人是管理者，他也许会因为自己无权做出关键性购买决定而犹犹豫豫。这些看似微不足道的踌躇和犹豫很有可能会造成致命的延误

笔记：指令要明确，分工也需要具体，不能存在灰色地带。

大多数管理书籍的重点都是如何正确做事，不要把事情搞砸。但我的经验却是，把事情搞砸之后，如何深刻的理解你必须要做的那些事情。

笔记：然而很多时候个人代替从搞砸了事情中的吸取教训所做的事情却是悔恨与烦恼，并无用处。多人已经提过类似观点，戴尔也说过试错并学习（然而戴尔现在……）。

自己的员工要自己亲自辞退，不能将这项工作推给人力资源部门或某个更严厉的同事，不能像电影《在云端》中雇佣一家外包公司完成。

笔记：last day会被记住。

正确解雇高管的第一步是，搞清楚自己为什么为公司招错了人

如果这名高管是由董事会成员举荐而来的，打电话个人通知就显得尤为重要

说话要果断，不要给讨论留下悬念

向董事会宣布最新的人事变动信息时，一定要用积极正面的方式，不要给人一种“一脚将高管踢出公司的感觉”

此时，你也许会担心员工们曲解消息，以为公司陷入了困境。不要在意这些反应

笔记：不做评论，基本不会用到这些内容，但是最后一条让人对这类事件可以用一个新的角度去看待管理者们的表现。

人，尤其是那些创造事物的人，只愿意听好消息。

笔记：码农的天然乐观是个毒药，要学会接受坏消息。

不要花时间懊悔过去，要将所有时间花在自己可以做的事情上，因为说到底，没人会在意。

笔记：一针见血，懊悔过去当真是对当前的不负责，累计了更多的债务。再次强调，没人会在意自己做错的事情。

和平时期的世界与你每天必须为生活苦苦挣扎的世界完全不同。和平时期，人们有时间关注言行是否得体、长远的文化影响以及人们的情感这类问题。而在你为生活苦苦挣扎的时期，最重要的是奋勇杀敌，带领自己的队伍安全抵达目的地。

笔记：想起《鸿门宴》，沛公曰：“今者出，未辞也，为之奈何？”樊哙曰：“大行不顾细谨，大礼不辞小让。如今人方为刀俎，我为鱼肉，何辞为！”。活下去是第一要素。理解了某些情况下领导的做法。

我们要依次管理好人、产品和利润。

笔记：人生产产品，产品带来利润？

在科技公司里，一旦员工流失，就会出现螺旋式的循环：公司价值下跌，最优秀的员工流失，公司价值继续下跌，最优秀的员工继续流失。这种恶性循环很难逆转。

笔记：论公司的倒掉。

未完待续。

LeetCode-118-119-121-141-155

发表回复

118 Pascal’s Triangle，119 Pascal’s Triangle II，121 Best Time to Buy and Sell Stock，141 Linked List Cycle，155 Min Stack 均较为简单，合并完成解题报告。

118 Pascal’s Triangle

概述

帕斯卡三角绘制。

分析

所谓帕斯卡三角，也叫做杨辉三角（也是贾宪三角……），解释可以在维基百科上得知。

那么只需按照定义，逐层生成即可。

解法

public class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        if (numRows <= 0) {
            return result;
        }

        List<Integer> prev = null;

        for (int i = 1; i <= numRows; ++i) {
            List<Integer> now = new ArrayList<Integer>();
            now.add(1);

            if (prev == null) {
                result.add(now);
                prev = now;
                continue;
            }

            for (int j = 0 ; j < prev.size() - 1; ++j) {
                now.add(prev.get(j) + prev.get(j + 1));
            }

            now.add(1);
            result.add(now);
            prev = now;
        }

        return result;
    }
}

public class Solution {

public List<List<Integer>> generate(int numRows) {

List<List<Integer>> result = new ArrayList<List<Integer>>();

if (numRows <= 0) {

return result;

}

List<Integer> prev = null;

for (int i = 1; i <= numRows; ++i) {

List<Integer> now = new ArrayList<Integer>();

now.add(1);

if (prev == null) {

result.add(now);

prev = now;

continue;

}

for (int j = 0 ; j < prev.size() - 1; ++j) {

now.add(prev.get(j) + prev.get(j + 1));

}

now.add(1);

result.add(now);

prev = now;

}

return result;

}

119 Pascal’s Triangle II

概述

只绘制杨辉三角的某行。

分析

属于118 Pascal’s Triangle的扩展题目，可以考虑直接复用118的代码，生成后返回。

问题在于时间复杂度过高。后续可以优化。

解法

public class Solution {
    public List<Integer> getRow(int rowIndex) {
        return this.generate(rowIndex + 1).get(rowIndex);
    }

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();

        if (numRows <= 0) {
            return result;
        }

        List<Integer> prev = null;

        for (int i = 1; i <= numRows; ++i) {
            List<Integer> now = new ArrayList<Integer>();
            now.add(1);

            if (prev == null) {
                result.add(now);
                prev = now;
                continue;
            }

            for (int j = 0 ; j < prev.size() - 1; ++j) {
                now.add(prev.get(j) + prev.get(j + 1));
            }

            now.add(1);
            result.add(now);
            prev = now;
        }

        return result;
    }
}

public class Solution {

public List<Integer> getRow(int rowIndex) {

return this.generate(rowIndex + 1).get(rowIndex);

}

public List<List<Integer>> generate(int numRows) {

List<List<Integer>> result = new ArrayList<List<Integer>>();

if (numRows <= 0) {

return result;

}

List<Integer> prev = null;

for (int i = 1; i <= numRows; ++i) {

List<Integer> now = new ArrayList<Integer>();

now.add(1);

if (prev == null) {

result.add(now);

prev = now;

continue;

}

for (int j = 0 ; j < prev.size() - 1; ++j) {

now.add(prev.get(j) + prev.get(j + 1));

}

now.add(1);

result.add(now);

prev = now;

}

return result;

}

121 Best Time to Buy and Sell Stock

概述

给出股价列表，找出最大的获利。

分析

可以想到，获利最大，即买入价最低，卖出价最高。

每个时间段都会有最高的卖出价，在数组中，一个区间的最大值是一定的。从后向前遍历，如果当前值不大于当前位置之后的最大值，那么当前值开始的最大值，仍然是当前值之后的最大值。反之则是当前值。

只需要针对价格，再次遍历数组，获得每个位置的数字的差值，即可知道在哪一位置时获利最大，即差值最大。

解法

public class Solution {
    public int maxProfit(int[] prices) {
        int[] maxNumbers = new int[prices.length];

        for (int i = prices.length - 1; i >= 0; --i) {
            if (i == prices.length - 1) {
                maxNumbers[i] = prices[i];
                continue;
            }

            if (prices[i] > maxNumbers[i + 1]) {
                maxNumbers[i] = prices[i];
                continue;
            }

            maxNumbers[i] = maxNumbers[i + 1];
        }

        int maxProfit = 0;

        for (int i = prices.length - 1; i >= 0; --i) {
            if (maxProfit < (maxNumbers[i] - prices[i])) {
                maxProfit = maxNumbers[i] - prices[i];
            }
        }

        return maxProfit;
    }
}

public class Solution {

public int maxProfit(int[] prices) {

int[] maxNumbers = new int[prices.length];

for (int i = prices.length - 1; i >= 0; --i) {

if (i == prices.length - 1) {

maxNumbers[i] = prices[i];

continue;

}

if (prices[i] > maxNumbers[i + 1]) {

maxNumbers[i] = prices[i];

continue;

}

maxNumbers[i] = maxNumbers[i + 1];

}

int maxProfit = 0;

for (int i = prices.length - 1; i >= 0; --i) {

if (maxProfit < (maxNumbers[i] - prices[i])) {

maxProfit = maxNumbers[i] - prices[i];

}

return maxProfit;

}

141 Linked List Cycle

概述

判断单向链表中是否存在环。

分析

简单的做法，用hash存储当前的节点指针值，如果再次遇到这一指针，说明有环。

但是目前还没有做出不需要额外空间的做法。

解法

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (null == head) {
            return false;
        }

        HashMap<Object, Integer> m = new HashMap<Object, Integer>();

        ListNode h = head;

        while (h != null) {
            if (m.containsKey(h)) {
                return true;
            }

            m.put(h, 1);
            h = h.next;
        }

        return false;
    }
}

public class Solution {

public boolean hasCycle(ListNode head) {

if (null == head) {

return false;

}

HashMap<Object, Integer> m = new HashMap<Object, Integer>();

ListNode h = head;

while (h != null) {

if (m.containsKey(h)) {

return true;

}

m.put(h, 1);

h = h.next;

}

return false;

}

155 Min Stack

概述

用单向链表实现一个可以直接获得最小值的栈。

分析

栈的特点是先进后出。

push 操作，可以看做是更换首节点的操作。同时，由于要直接获得最小值，可以入栈时判断是否比当前的最小值更小，由此可以完成更新操作。

pop 操作，可以看做是删除首节点的操作。同样的，如果pop的数值比小于等于最小值，需要遍历链表找到最小值。

如是，随时获得栈最小值的时间复杂度是O(1)。

解法

public class MinStack {

    /** initialize your data structure here. */
    public class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int x) { val = x; }
    }

    private boolean gotMin = false;
    private int minVal = Integer.MAX_VALUE;
    private ListNode stack = null;

    public MinStack() {

    }

    public void push(int x) {
        minVal = getMin();

        if (x <= minVal) {
            minVal = x;
        }

        ListNode n = new ListNode(x);
        n.next = stack;
        stack = n;
    }

    public void pop() {
        if (stack == null) {
            gotMin = false;
            minVal = Integer.MAX_VALUE;
            return;
        }

        if (gotMin && stack.val == minVal) {
            gotMin = false;
            minVal = Integer.MAX_VALUE;
        }

        if (stack.next == null) {
            stack = null;
            gotMin = false;
            minVal = Integer.MAX_VALUE;
            return;
        }

        stack = stack.next;
    }

    public int top() {
        if (stack == null) {
            return 0;
        }

        return stack.val;
    }

    public int getMin() {
        if (gotMin) {
            return minVal;
        }

        ListNode h = stack;

        while (h != null) {
            if (h.val <= minVal) {
                gotMin = true;
                minVal = h.val;
            }

            h = h.next;
        }

        return minVal;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */
 ```

public class MinStack {

/** initialize your data structure here. */

public class ListNode {

public int val;

public ListNode next;

public ListNode(int x) { val = x; }

}

private boolean gotMin = false;

private int minVal = Integer.MAX_VALUE;

private ListNode stack = null;

public MinStack() {

}

public void push(int x) {

minVal = getMin();

if (x <= minVal) {

minVal = x;

}

ListNode n = new ListNode(x);

n.next = stack;

stack = n;

}

public void pop() {

if (stack == null) {

gotMin = false;

minVal = Integer.MAX_VALUE;

return;

}

if (gotMin && stack.val == minVal) {

gotMin = false;

minVal = Integer.MAX_VALUE;

}

if (stack.next == null) {

stack = null;

gotMin = false;

minVal = Integer.MAX_VALUE;

return;

}

stack = stack.next;

}

public int top() {

if (stack == null) {

return 0;

}

return stack.val;

}

public int getMin() {

if (gotMin) {

return minVal;

}

ListNode h = stack;

while (h != null) {

if (h.val <= minVal) {

gotMin = true;

minVal = h.val;

}

h = h.next;

}

return minVal;

}

/**

* Your MinStack object will be instantiated and called as such:

* MinStack obj = new MinStack();

* obj.push(x);

* obj.pop();

* int param_3 = obj.top();

* int param_4 = obj.getMin();

```

服务端	客户端
\(ARG1\)	check_domain_accessibilty
\(ARG2\)	\(ARG1\)
\(ARG3\)	\(ARG2\)
\(ARG4\)	\(ARG3\)