dp动态规划

解决问题

通常用于解决最优化问题,通常做出一组选择来达到最优解.

特点

• 做出每个选择时,通常会生成与原问题形式相同的子问题
• 多于一个选择子集都会生成相同的子问题(子问题重叠)

关键技术

• 对每个相同的子问题保存其解,当其重复出现时避免重复求解
• 通常可将指数时间的算法转换为多项式级别的算法

步骤

1. 刻画一个最优解的结构特征
2. 递归地定义最优解的值
3. 计算最优解的值,通常采用自底向上的方法
4. 利用计算出的信息构造一个最优解

典型问题

算法导论

钢条切割
求两个序列的最长公共子序列
构造最优二叉搜索树

使用antlr4实现一个计算器

antlr4简介

antlr4是一款强大的语法分析器生成工具,我们可以使用antlr4分析处理各种可以用语法描述的文本(代码,配置文件,报表,json文本),还可以用来实现DSL.

antlr4能够为我们定义的语法生成AST(一种描述语法与输入文本匹配关系的数据结构),还能够自动生成遍历AST的代码,使我们可以专注于业务逻辑实现.antlr4支持生成各种语言的代码,因此我们可以根据熟悉的语言实现业务功能.

本文章通过实现一个计算器来直观的感受一下antlr4如何使用.

定义语法规则

antlr4语法文件以g4为后缀,可以在一个文件中同时定义词法和语法.

• 词法以全大写表示
• 语法以全小写表示.
• 首行使用grammar声明语法名称,需要和文件名完全一致.

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

grammar LabeledExpr;

prog: stat+;

stat: expr NEWLINE  # printExpr
    | ID '=' expr NEWLINE # assign
    | NEWLINE   #blank
    ;

expr: expr op=('*' | '/') expr # MulDiv
    | expr op=('+' | '-') expr # AddSub
    | INT   #int
    | ID    #id
    | '(' expr ')'  #parens
    ;

MUL : '*';
DIV : '/';
ADD : '+';
SUB : '-';

ID : [a-zA-Z]+ ;
INT : [0-9]+ ;
NEWLINE : '\r'? '\n';
WS : [ \t]+ -> skip;

解释一下:

• prog: stat+; 定义了一个prog语法,程序是由1个或多个语句构建,antlr4支持类似正则的语法,(+表示一个或多个). ‘|’表示或的关系.
• stat: 定义语句的语法,语句可以是表达式,赋值或者换行.
• expr: 定义表达式的语法,表达式可以是两个表达式的乘除,加减,或者是一个整数,一个变量,或者带括号的表达式. antlr4支持上下文无关方法,可以处理左递归,因此我们可以递归定义语法.
• “#”: #号开关的属于antlr4标签,通过定义标签可以让antlr4为每个备选分支都生成一个遍历方法,否则antlr4只为expr这种语法生成一个遍历方法.
• MUL,DIV,ADD,SUB: 定义词法的名字,通过定义名字使我们可以在代码中通过这些名字来引用具体的单词.
• ID,INT,NEWLINE: 定义变量和整型的词法.
• WS: 定义空白符词法, ->skip为antlr4的指令,表示丢弃当前的单词(每个输入的字符都至少被一条词法规则匹配)

生成代码

本文以Python代码举例,antlr4本身使用java语言编写,可以生成不同的目标语言

1

antlr4 -no-listener -visitor -Dlanguage=Python3 -o python3 LabeledExpr.g4

• -Dlanguage: 定义输出的目标语言,这里是Python3
• -o:指定代码输出路径
• -no-listener -visitor: antlr4默认为处理AST生成监听器代码,这里我们不使用监听器方式而是使用visitor(访问者模式)方式来遍历AST.

通过上述命令antlr4为我们生成以下代码:

1. LabeledExprParser.py: 语法分析器代码,每条语法规则都有对应的处理方法.
2. LabeledExprLexer.py: 词法分析器代码
3. LabeledExpr.tokens: 词法符号对应的数字类型
4. LabeledExprVisitor.py: 语法分析树的访问器,每条语法和标签都有对应的访问方法,通过实现里面的方法实现业务功能.

编写处理逻辑

1.首先编写visitor实现处理逻辑

代码比较容易理解,就不再详细展开.定义了一个vars字典用来存储定义的变量,然后在对应的语法里获取相应的数据并计算.

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

class LabeledExprVisitor(ParseTreeVisitor):
    def __init__(self):
        self.vars = {}

    # Visit a parse tree produced by LabeledExprParser#prog.
    def visitProg(self, ctx:LabeledExprParser.ProgContext):
        return self.visitChildren(ctx)


    # Visit a parse tree produced by LabeledExprParser#printExpr.
    def visitPrintExpr(self, ctx:LabeledExprParser.PrintExprContext):
        value = self.visit(ctx.expr())
        print(value)
        return 0


    # Visit a parse tree produced by LabeledExprParser#assign.
    def visitAssign(self, ctx:LabeledExprParser.AssignContext):
        var = ctx.ID().getText()
        value = self.visit(ctx.expr())
        self.vars[var] = value
        return value


    # Visit a parse tree produced by LabeledExprParser#blank.
    def visitBlank(self, ctx:LabeledExprParser.BlankContext):
        return self.visitChildren(ctx)


    # Visit a parse tree produced by LabeledExprParser#parens.
    def visitParens(self, ctx:LabeledExprParser.ParensContext):
        return self.visit(ctx.expr())


    # Visit a parse tree produced by LabeledExprParser#MulDiv.
    def visitMulDiv(self, ctx:LabeledExprParser.MulDivContext):
        left = self.visit(ctx.expr(0))
        right = self.visit(ctx.expr(0))
        if ctx.op.getType() == LabeledExprParser.MUL:
            return left * right
        return left / right


    # Visit a parse tree produced by LabeledExprParser#AddSub.
    def visitAddSub(self, ctx:LabeledExprParser.AddSubContext):
        left = self.visit(ctx.expr(0))
        right = self.visit(ctx.expr(1))
        if ctx.op.type == LabeledExprParser.ADD:
            return left + right
        return left - right


    # Visit a parse tree produced by LabeledExprParser#id.
    def visitId(self, ctx:LabeledExprParser.IdContext):
        var = ctx.ID().getText()
        if var in self.vars: # use before assignment?
            return self.vars[var]
        return 0


    # Visit a parse tree produced by LabeledExprParser#int.
    def visitInt(self, ctx:LabeledExprParser.IntContext):
        return int(ctx.INT().getText())

2.编写主程序,将输入与语法分析结合

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

caculator.py:

import sys
from antlr4 import *
from LabeledExprLexer import LabeledExprLexer
from LabeledExprParser import LabeledExprParser
from LabeledExprVisitor import LabeledExprVisitor

def main(argv):
    input_stream = FileStream(argv[1])
    lexer = LabeledExprLexer(input_stream) # 将输入文件交给记法分析器
    tokens = CommonTokenStream(lexer)  # 将记法分析器传递给token生成一个个单词
    parser = LabeledExprParser(tokens) # 将单词传递给语法分析器
    tree = parser.prog() # 调用prog语法生成AST

    eval = LabeledExprVisitor() # 调用visitor遍历生成的AST
    eval.visit(tree)

if __name__ == '__main__':
    main(sys.argv)

3.验证程序

输入文本:

1
2
3
4
5

1.text

a=5
b=4
a+b

1
2
3

python3 caculator.py 1.text

输出:9

Linux 系统实际上没有实现相关的虚拟路由器设备，自然也没有工具可以操作路由器，因为 Linux 本身就是一台路由器。（这也是我文章的标题对 vRouter 打双引号的原因）

Linux 提供一个开关来操作路由功能，就是 /proc/sys/net/ipv4/ip_forward，默认这个开关是关的，打开只需：

echo 1 > /proc/sys/net/ipv4/ip_forward

但这种打开方式只是临时的，如果要一劳永逸，可以修改配置文件 /etc/sysctl.conf，添加或修改项 net.ipv4.ip_forward 为：

net.ipv4.ip_forward = 1

即可。

实践

为了降低大家实践的难度，我们就不创建虚拟机了，直接使用 namespace，一条 ip 命令就可以搞定所有的操作。

我们按照下面的图示进行操作（NS1 和 NS2 分布在不同网段）：

创建两个 namespace：

ip netns add ns1
ip netns add ns2

创建两对 veth-pair，一端分别挂在两个 namespace 中：

ip link add v1 type veth peer name v1_r
ip link add v2 type veth peer name v2_r

ip link set v1 netns ns1
ip link set v2 netns ns2

分别给两对 veth-pair 端点配上 IP 并启用：

ip a a 10.10.10.1/24 dev v1_r
ip l s v1_r up
ip a a 10.10.20.1/24 dev v2_r
ip l s v2_r up

ip netns exec ns1 ip a a 10.10.10.2/24 dev v1
ip netns exec ns1 ip l s v1 up
ip netns exec ns2 ip a a 10.10.20.2/24 dev v2
ip netns exec ns2 ip l s v2 up

验证一下： v1 ping v2，结果不通。

看下 ip_forward 的值：

[root@by ~]# cat /proc/sys/net/ipv4/ip_forward
0

没开路由怎么通，改为 1 再试，还是不通。

看下 ns1 的路由表：

[root@by ~]# ip netns exec ns1 route -n
Kernel IP routing table
Destination Gateway Genmask Flags Metric Ref Use Iface
10.10.10.0 0.0.0.0 255.255.255.0 U 0 0 0 v1

只有一条直连路由，没有去往 10.10.20.0/24 网段的路由，怎么通？那就给它配一条：

[root@by ~]# ip netns exec ns1 route add -net 10.10.20.0 netmask 255.255.255.0 gw 10.10.10.1

ip netns exec ns1 route -n Kernel IP routing table Destination Gateway Genmask Flags Metric Ref Use Iface 10.10.10.0 0.0.0.0 255.255.255.0 U 0 0 0 v1 10.10.20.0 10.10.10.1 255.255.255.0 UG 0 0 0 v1

同理也给 ns2 配上去往 10.10.10.0/24 网段的路由。

最后再 ping，成功了！

[root@by ~]# ip netns exec ns1 ping 10.10.20.2
PING 10.10.20.2 (10.10.20.2) 56(84) bytes of data.
64 bytes from 10.10.20.2: icmp_seq=1 ttl=63 time=0.071 ms
64 bytes from 10.10.20.2: icmp_seq=2 ttl=63 time=0.070 ms
^C
— 10.10.20.2 ping statistics —
2 packets transmitted, 2 received, 0% packet loss, time 1000ms
rtt min/avg/max/mdev = 0.070/0.070/0.071/0.008 ms

总结

Linux 本身是一台路由器。

上面的实验使用 namespace 效果和使用虚拟机是一样的，关键是知道有这个功能，知道怎么用就差不多了。

转自: https://www.ucloud.cn/yun/11656.html

最近在做一个移植Puppet到公司的网络操作系统上的项目，需要在puppet上进行二次开发，开发type,provider.

但是发现网上和书上都是讲Puppet布署和使用的居多，讲二次开发的很少。所以自己一边在项目里开发，一边研究源码，现将研究的成果分享出来。

因为是讲puppet的源码，所以要对puppet的使用和ruby语言有一定的基础。因为Puppet里运用了大量ruby的元编程特性，所以建议看一下<ruby元编程>这本书。

使用的puppet版本是2.7.3,ruby是1.9.3.

我们在puppet/lib/type目录下可以看到很多puppet自带的type,如常用的file,exec等。定义它们都是形如下面的代码：

Puppet::Type.newtype(:file) do{}

Puppet::Type.newtype(:exec) do{}

我们就从这里出发，看看在puppet里如何自定义type,以及它是如何实现的。为了简化起见，我将puppet的代码抽取出来，用一个最简化的代码来讲解。这些代码都是从puppet的源码中抽取出来的，在不影响理解实现的基础上，删除了一些代码，以求理解起来方便。废话少说，先上代码：

├─lib
│  └─puppet
│      │  testType.rb
│      │  type.rb
│      │  util.rb
│      │
│      ├─metatype
│      │      manager.rb
│      │
│      └─util
│              classgen.rb
│              methodhelper.rb
│

为了方便理解，有几点先说明一下:

1.目录结构和puppet的源码保持一致，puppet在定义module时，module名都用了目录名作为一个命名空间，这样避免了冲突。如manger.rb定义如下:

module Puppet::MetaType //目录结构
  module Manager

 ……

 end

end

2.类也是一个对象，puppet/type.rb里定义的type类是管理所有type的一个类，newtype方法自定义的类都会保存在这里。

具体的代码如下：

type.rb:

require_relative ‘../puppet/metatype/manager’

module Puppet
  class Type
    class << self
      include Puppet::MetaType::Manager  #Manger模块里的方法都成为Type类的类方法，主要是newtype方法，用于定义新的类

      attr_accessor :types           #所有定义的类都保存在@types={}这个hash表里，定义存取器，便于访问验证。
    end

    def self.initvars                 #初始化一些类实例变量，自定义的类会继承这个方法。
      @objects = Hash.new
      @aliases = Hash.new

      @is_init = true
    end

  end
end

metatype/manager.rb:   #此模块主要体现元编程的能力，所以放在metatype目录下，用于产生新的type.

require_relative ‘../util’
require_relative ‘../type’
require_relative ‘../util/methodhelper’
require_relative ‘../util/classgen’

module Puppet::MetaType
  module Manager
     include  Puppet::Util::ClassGen  #包含ClassGen模块，这个模块主要是动态生成类的一些方法。如genclass.

    def newtype(name,options={},&block)
        unless options.is_a?(Hash)            #自定义类时的options必须为hash
          warn “Puppet::Type.newtype#{name} expects a hash as the second argument,not #{options.inspect}”
          options = {:parent => options}
        end

        name = symbolize(name)         #将自定义的类名转化为symbol
        newmethod = “new#{name.to_s}” #定义产生新类对象的方法名，如自定义类:file,则产生这个类对象的方法名newfile

        selfobj = singleton_class  #获得当前对象的单例类，注意这里其实是Type类的单例类，取得它的单例类，是为了向Type添加或删除类方法。

        @types = {} #如果还没有定义@types，则定义它为hash.这个变量成为Type类的实例变量，用于存储所有自定义的Type类。

        #如果已经定义了同名的类，且定义了newmethod方法，则删除它。
        if @types.include?(name)
          if self.respond_to?(newmethod)
            #caution: remove method from self.singleton_class not self
            selfobj.send(:remove_method,newmethod)
          end
        end

       #将options中的key都转换为符号
        options = symbolize_options(options)

      #获取自定义的类的父类，并将其从options里删除
        if parent = options[:parent]
          options.delete(:parent)
        end

      #产生新的类
        kclass = genclass(
            name,
            :parent => (parent Puppet::Type),
            :overwrite => true,
            :hash => @types,
            :attribute => options,
            &block
        )

      #如果Type类里还没定义产生新类的对象的方法，则定义它。
        if self.respond_to?(newmethod)
            puts “new#{name.to_s} is already exists skipping”
        else
            selfobj.send(:define_method,newmethod) do *args #注意selfobj是Type类的单例类，所以定义的方法便成为Type类的方法。
              kclass.new(*args)
            end
        end

       #返回新产生的类对象(类也是对象）
        kclass

    end
  end
end

util/classgen.rb:   #产生新类的模块，用于产生新的类，在这一节主要是产生新的Type类，后面还可以看到用它产生新的provider类。

require_relative ‘../util’
require_relative ‘../util/methodhelper’

module Puppet::Util::ClassGen
  include Puppet::Util::MethodHelper
  include Puppet::Util

 #产生新的类
  def genclass(name,options={},&block)
      genthing(name,Class,options,block)
  end

#获取常量的名称
  def getconst_string(name,options)
    unless const = options[:constant]
      prefix = options[:prefix] “”
      const = prefix + name2const(name)
    end

    const
  end

#是否定义了这个常量
  def is_const_defined?(const)
    if ::RUBY_VERSION =~ /1.9/
      const_defined?(const,false)
    else
      const_defined?(const)
    end
  end

#给类定义新的常量
  def handleclassconst(kclass,name,options)
     const = getconst_string(name,options)

     if is_const_defined?(const)
       if options[:overwrite]
         remove_const(const)
       else
          puts “Class #{const} is already defined in #{self}”
       end
     end

     const_set(const,kclass)
  end

#初始化一个类,通过这个方法，我们可以看到，自定义类可以给它定义常量，也可以通过模块扩展自定义类的功能。
  def initclass(kclass,options)
    kclass.initvars if kclass.respond_to?(:initvars) #如果类有initvars方法，则调用它。因为新定义type类的父类是Puppet::Type类，这个类里有initvars方法，所以会调用它。

    if attrs = options[:attributes]  #如果定义新类时指定了attributes则为它定义这类属性的存储器
      if attrs.is_a?(Hash)
        attrs.each do param,value
          method = param.to_s+”=”
          kclass.send(method,value) if kclass.respond_to?(method)
        end
      end
    end

    [:include,:extend].each do method #如果定义新类时指定了include,extend在模块，它在新类里加载这些模块。可以通过模块扩展自定义的类
      if mods = options[method]
        mods = [mods] unless mods.is_a?(Array)
        mods.each do mod
          kclass.send(method,mod)
        end
      end
    end

    kclass.preinit if kclass.respond_to?(:preinit)  #最后设置一个钩子，如果新定义的类有preinit方法，则调用它一下下
  end

#将自定义类存储在@types
  def stroeclass(kclass,name,options)
    if hash = options[:hash]
      if hash.include?(name) and !options[:overwrite]
        raise “Already a generated class named #{name}”
      end

      hash[name] = kclass
    end

  end

 #这个方法是产生自定义类的方法
  def genthing(name,type,options,block)
     options = symbolize_options(options)

     name = symbolize(name)

      options[:parent] = self
      eval_method = :class_eval
      kclass = Class.new(options[:parent]) do    #产生一个新的自定义类，并给它定义一个实例变量@name
        @name = name
      end

      handleclassconst(kclass,name,options)  #定义自定义类的常量,具体功能见上面对方法的注释

      initclass(kclass,options) #初始化自定义类

      block = options[:block]
      kclass.send(eval_method,&block) if block #将定义类时的block传给产生的类去执行，这样这个block里就可以执行所有Type的类方法。这也是为什么我们可以在自定义类的块里调用newproperty这些方法的原因。

      kclass.postinit if kclass.respond_to?(:postinit)  #又一个钩子函数，用于初始化完成后进行一些处理工作。

      stroeclass(kclass,name,options)  #将新定义的类存储起来

  end

  # :abc => “Abc”
  # “abc” => “Abc”
  # “123abc” => “123abc”
  def name2const(name)
    name.to_s.capitalize
  end

end

util/methodhelper.rb      #util目录主要是一些功能函数，如这个模块定义了符号化options的方法

module Puppet::Util::MethodHelper

  def symbolize_options(options)
    options.inject({}) do hash,opts
      if opts[0].respond_to? :intern
        hash[opts[0].intern] = opts[1]
      else
        hash[opts[0]] = opts[1]
      end
      hash
    end
  end

end

util.rb: #同理，这里定义了符号化一个变量的操作

module Puppet
  module Util
    def symbolize(value)
      if value.respond_to? :intern then
        value.intern
      else
        value
      end
    end

  end
end

testType.rb

require_relative ‘./type’

Puppet::Type.newtype(:atest) do

end

Puppet::Type.types.each do name,kclass
  p kclass.methods
  p kclass.instance_variables
end

最后我们用testType.rb测试我们的代码，我们定义了一个新类atest。然后遍历Type类的@types变量，查看所有新定义的类的方法和实例变量。运行结果如下:

[:types, :types=, :initvars, :newatest, :newtype, :genclass, :getconst_string, :is_const_defined?, :handleclassconst, :initclass, :stroeclass, :genthing, :name2const, :symbolize, :symbolize_options_,……….]
[:@name, :@objects, :@aliases, :@is_init]

可以看到新定义的类从父类Type里继承了许多类方法，并在initvars后产生了自己的实例变量。

注释较为详细，如果还有不理解或讲的不对的地方，欢迎讨论。

一位程序员工作10年总结的13个忠告

展望未来，总结过去10年的程序员生涯，给程序员小弟弟小妹妹们的一些总结性忠告。

走过的路，回忆起来是那么曲折，把自己的一些心得体会分享给程序员兄弟姐妹们，虽然时代在变化，但是很可能你也会走我已经做过的10年的路程，有些心得体会你可以借鉴一下，觉得说得有道理的你就接纳，觉得说得没道理的，你就抛弃，以下是我发自内心的，给大家的忠告，特别是针对那些小弟弟妹妹们。

1.自己的户口档案、养老保险、医疗保险、住房公积金一定要保管好。

由于程序员行业每年跳槽一次，我不隐瞒大家，我至少换过5个以上的单位，这期间跳来跳去，甚至是城市都换过3个。还好户口没丢掉，其他都已经是乱了，好几个城市里，都有交过三金，甚至是一个程序的2个区里交的都有，那些东西，10年后，会变得很重要。你买房子若有公积金，可以取出来，贷款利率也会比较低一些，有孩子了，还需要上学，生病了还需要医疗保险。

特别是买房子时，你要商业贷款与公积金贷款的利率差别还是很大，有可能会有10万的差距。你平时都注意这些，会给你带来的损失会最小，例如每个月缴纳300元的公积金，公司也缴纳300元，你一个月能存下来600元，一年就是7200元，10年就是72000元。

我以前都忽视了这些，到我需要买房子时，公积金里可能只有几千元，10年很快就过去了，结果我没能存下来多少公积金，医疗保险，养老金等更别提了，都已经稀里糊涂了，这些损失10年累加起来，是很庞大的数字，大家要注意，跳槽换工作时也要保护好自身的利益，现在房价很贵，你可能是跟我一样，大山里出来打拼的娃子，家里也没有丰厚的积蓄，只有靠自己拼搏，买房子是人生的一件大事，等你到了10年，才想到这个事情，已经晚了，特别是孩子要上学，上幼儿园等，需要户口啥的都要齐全。

2.不要轻易换笔记本电脑，不要跟潮流，不要买过多的电子产品，不要过于频繁的更换手机。

这方面我的经验教训也是惨痛的。我大概前后购买过5-6个笔记本，以前的都是1万多元一台，最近买的是一台是1万多给女朋友的，自己买了一台是7500元左右，手机大概换过接近10个了，这些钱加起来也足够有10万以上了，你可能一不小心就购买了这些电子产品，但是时间长了，你一回过头来想想，你为什么赚得也不少，但是为什么还是那么穷？

是因为你购买这些电子产品花费了过多的金钱了，平时笔记本啥的贵重物品要保护好，我一个同事不小心丢了2台笔记本电脑，接近2万的损失啊，你净赚2万，不是那么容易的，这个窟窿不是开玩笑的，我曾经也被人偷了一个崭新的笔记本，损失1.5万左右，更糟糕的是最新的代码也丢被偷了。

3.这年代外语、学历、职称、驾驶证还是蛮重要的。

想找高薪，外资企业是正确的选择，在同样的打工里，外资企业的收入普遍是高的，我就想不明白，我们的赚钱能力怎么就比不过人家了，社会不断发展，将来可能去外国就像串门一样了，也说不定的，外语好将来的就业机会也会更多更广一些。

学历并不代表啥，但是学历也是敲门砖，例如有300个应聘者，那至少重点本科以下的，统统不看了，因为实在是来不及看了，你再厉害也被挡在机会的门外了，同样有时候你想改行什么的，职称也很重要，最起码评个中级职称，说不定还有机会能进入大学或者政府部门还是有可能性。

若有充裕的时间，应该把驾驶证考了，因为你越到后面越忙与工作家庭，没机会学车了也说不定的，平时也别光顾拼命工作，工作10年后你才发现，原来身边的人都至少硕士学历了，你被社会自动淘汰了，我现在就有这个感觉，虽然我带过很多硕士，他们的就业机会比我还好，经常能进入名牌企业，我也一直进不去。

4.不要谈过多的女朋友，谈女朋友要看准，下手要稳准狠。

我谈过2个女朋友，平均每个女朋友身上的开支前后大概会有10万左右，还好我不用谈第3个女朋友了，若投资失误，那也是很残忍的，谈女朋友也会消耗很多时间精力、还会消耗很多金钱，实话的讲的确是这样的，人家女孩子也值钱啊，凭什么就那么轻易的跟你啊。

我跟第一个朋友分手时，我的生活至少是倒退了3-4年，一切从零开始，一切从头开始，我劝大家谈女朋友是人生最大的一笔买卖，投资失误会有惨痛的后果，不仅仅是金钱上的损失，更会有精神、心灵上的沉重打击，大家要学会珍惜女朋友，要学会哄好女朋友，让老婆开心每一天，虽然鱼儿上钩了，不用再下鱼饵了，偶尔也别忘记放点米，这个鱼要是脱钩了，那不是开玩笑的。

5.工作不要更换得太过于频繁，选好了行业方向最好别更换太频繁。

换工作，换行业方向，就像熊掰苞米一样的道理，有时候是丢了芝麻捡西瓜，有时候是丢了西瓜捡芝麻，这个道理我就不多讲了，大家都应该能明白的。

6.要对身边的人好，要得到老板的信任、同事的认可及支持、珍惜良好的工作环境。

有个朋友的QQ名字很有意思，“只爱陌生人”，陌生人是很有意思，但是最关键时刻，还是需要靠非陌生人，你每天跟同事一起生活，要维系好身边的人。你的成功与失败，往往是你身边的30-40个人决定的。

你就是世界首富，他身边也是那么不超过100个人的在左右着他的生活，当你工作10年了，没一个老板信任你，没几个要好的同事朋友，那你惨了，你在这个世界上已经是很孤单了，你的收入，其实大多是来自这些身边的朋友给你介绍的生意，不大会网上掉几个馅饼的。现在你身边的人有可能在不久的将来，给你提供很多好机会。

7.钱很重要，但是生活质量比钱还重要，工作是很重要，但是家人比工作还重要。

钱不是万能的，但是没钱是万万不能的。钱赚了，身体夸了，全送给医院了，钱赚了，身心疲惫了，人活着为了啥？不就为了开开心心生活嘛？工作重要，但是失去了家人的爱，失去了女朋友，失去了老婆孩子，那这个工作有啥用了？工作很容易就换了，家人是换不了的，老婆不是想换就换的，孩子不是想换就换的，连自己的家庭都不负责的人，怎么可能对公司负责呢？我一直是这个观念，来面试时觉得工作更重要的，我们一般不录取的，那太假了，或者太不懂事了。

8.工作累了，也别太贪玩，有时候还是需要多想想如何才能赚钱。

时间一晃就过去了，工作累了是可以适当放松，但是别太贪玩，10年很容易就过去了，10年后你要买房子，要娶老婆，要买车子，要生娃娃，身体也会变得脆弱一些，需要良好的生活习惯，也经不起通宵了，通宵一次，你要低迷好几天才能缓过劲儿来，跟20刚出头完全不一样了，用钱的地方多了去了。

父母也会变得更老一些，可能也需要你的照顾，整个家子都指望你赚钱，别到了这个时候，你才意识到赚钱是那么的重要，更何况现在城市的房价，动不动就是100万，加上按揭的利息，你很可能需要支付150万。还可能需要装修，买车子。可能你身上的压力是200万。别觉得谈钱就俗，你要学会赚钱，要有个需要赚钱的良好意识，当然你出身富裕家庭，就不用考虑这些因素了。

9.每天一点点进步，每月一点点积累，要敬业要爱业，我们给别人提供的也是服务。

总有一天，你也会有累的时候，你也会有老的时候，这时候，你要靠啥呢？就要靠你平时的积累，你10年的积累，可以打倒很多竞争对手，他们再厉害，再怎么样，也很难抵得过你10年的积累，特别是后面5-10年的积累，成果会很明显，前面的1-5年，算是做软件的入门吧，除非你有高人指点，那可能2-3年就可以修成正果，软件在将来还是会值钱的，以为生活会越来越智能化，越来越数字化，软件的需求还是很有前途，最起码未来的10-20年里不用太担心失业问题了。

10.对程序员来讲，开发思想、架构、代码就是财富，别老丢弃你的劳动成果，要学会保护你的劳动成果。

我大概7-8年前的代码都在手上，经常改进来改进去，维护来维护去，在一定的程度上，让我生活轻松了不少，因为我不用什么都从头来过，我只要痛苦一次，以后就要反复重复利用，软件的价值在于重复利用，而不是每个东西，都从头开发，那永远也是辛苦的程序员，这个生活质量就别提了，不管自己的代码丑还是拿不出手，要学会精心维护，每天改进一点点，每个月一个小进步，每年一个大进步，多年的积累是宝贵的，这个早晚也会给你带来丰厚的收益。

11.当程序员要防止原地踏步，不是工作年限长了，经验就丰富了，能力就强了，年纪越大工作越难找。

我有一个朋友跟我开玩笑，工作5年的人，可能能力差距会很大，为什么呢？因为第一年他们干的事情都是一样的，都写程序了，2个人可能由于价值观不一样，5年后差距会很大，甚至是大到无法追赶的程度，为啥？因为还有机会的因素在里面，有的人干了5年，还是在原地踏步，天天只会写那些添加、删除、修改的代码。

那你得注意了，需要不断的提高自己，才是硬道理。例如你会SQLServer，那要试着学习Oracle，你是做C/S的，那得需要提高到B/S的，你是做单机软件的，那得需要提高到网络软件，你只关注自己的工作的，需要学会管理，关心他人的工作。你是当程序员的，要试着提高当项目经理、部门经理，公司的总监等等，人有野心有目标才会不断进步，最俗的为了多赚钱，提高工作职位工作岗位，工作单位，也是可以理解的。

年纪越大工作越难找，例如3-4千的工作是随便找找，玩一样，但是你30过后，最起码要找月薪上1万的工作，这样的工作是机会也少，一般小公司也给不起，还得找个好公司才可以，好公司又不是天天招聘人，天天缺好的工作岗位，说不好听点儿，小公司的老板才赚多少啊？他来钱也很不容易的，小池塘就不好容得下大鲨鱼了。

12.当创业的收入比打工还少时，那就别创业，要找比自己能力强的人创业，你不会吃亏。

创业的收入，比打工还少，那就是瞎扯蛋，恶搞。创业的真正意思并不是要你去吃苦没钱赚，那是忽悠无知的人的。当你创业时的收入，比打工还多，那你可以考虑创业，没有工资什么的，股份啥的，都是瞎扯蛋。

不要跟自己能力还弱的人一起创业，那损失最大的，很可能就是你，要创业，也要找比自己强的人一起创业，最起码赚不到钱，还能学到不少。不会有过多的损失。别热血一沸腾就创业了，创业了，也别烧自己的钱，家人的钱，那是很不抗烧的，没几下几十万就烧干了。

其实打工，也是创业的开始，每个月都能拿到钱，还可以学到知识，什么公司的股份都是空话，没几个小公司能成功，开起来了也走不了3年就分家了，都忽悠小孩子玩的，除非真的有科技含量或者是客户资源的，否则股份是一文钱不值的，就算创业每个月也按时拿工资才是硬道理。

13.未来的生活节奏会更快，生活压力会更大，竞争会更激烈，社会服务体系会更完善。

在未来，我们享受良好的服务的同时，也会为别人提供更良好的服务，需要在技能上还是服务质量上的要求会更高更严格。平时要注意提高自己，不要被时代淘汰掉，我从小的朋友，一波又一波被社会无情的淘汰了，很小的时候，我出生在大草原与大山的交界处，我小时候的玩伴，还在大山里，我跟着家人杀出来了，我小学、中学、大学、工作上的、这10年，我一直很坚强的拼搏下来，很不容易的在杭州立住脚了，说实话，参加工作后的十年，也是不断拼搏，不断提高的十年。

https://www.cnblogs.com/ccccch/p/8046432.html

原理：

１.指定密码包括的字符种类，如：数字，小写字母，大写字母，特殊字符

２.指定密码的长度

３.遍历所有可能的组合暴力破解

在密码比较简单的时候比较有用。

使用指导:

optional arguments:
  -h, –help           show this help message and exit
  -a                   指定密码中包含小写字母.
  -A                  指定密码中包含大写字母..
  -n                  指定密码中包含数字.
  -N N              指定密码的长度.
  –spec SPEC         单独指定密码中包含的字符，字符串形式,指定密码中包含’.’和’‘,则指定”.“.
  –filepath FILEPATH  待破解的zip加密文件路径.

使用举例：

• 指定密码由数字构成，密码长度为３位

python main.py -n -N 3 D:/xxx.zip

• 指定密码由大小写字母构成，密码长度为１０位

python main.py -a -A -N 10 D:/xxx.zip

• 指定密码由[‘!’, ‘@’,  ‘$’, ‘&’]４个特殊字符构成，密码长度为６位

python main.py -N 10 –spec “!@$&” D:/xxx.zip

代码

github地址:

https://github.com/happyAnger6/angerZipDecode

python代码:

angerZipDecodeargs.py:

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

import argparse

def setup_args():
    parser = argparse.ArgumentParser(description='anger zip brute force decode.')

    parser.add_argument('-a', action='store_true', help='add lower case(a-z) letter to password.')
    parser.add_argument('-A', action='store_true', help='add upper case(A-Z) letter to password..')
    parser.add_argument('-n', action='store_true', help='add numeric(0-9) to password..')
    parser.add_argument('-N', action='store', required=True, help='total word nums of the password. ')
    parser.add_argument('--spec', action='store', help='add special words to password..')
    parser.add_argument('--filepath', action='store', required=True, help='zip file path. ')

    return parser.parse_args()

angerZipDecodemain.py:

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

import os
import sys
from zipfile import ZipFile

def gen_passwd_elems(args):
    total_elems = []
    if args.a: #use lower letter
        lower_word  = [chr(ord('a') + i) for i in range(26)]
        total_elems.extend(lower_word)

    if args.A: #use upper letter
        upper_word = [chr(ord('A') + i) for i in range(26)]
        total_elems.extend(upper_word)

    if args.spec: #use user spec letter
        total_elems.extend(list(set(args.spec)))

    if args.n: #user numeric
        digits = [i for i in range(10)]
        total_elems.extend(digits)

    return total_elems

def gen_passwd_iter(elements, pwnums=6, curnum=1):
    for i in elements:
        if pwnums == curnum:
            yield str(i)
        else:
            for j in gen_passwd_iter(elements, pwnums, curnum+1):
                yield str(i) + str(j)

if __name__ == "__main__":
    from args import setup_args

    args = setup_args()
    filename = args.filepath
    passwd_len = int(args.N)
    passwd_words = gen_passwd_elems(args)

    zfile = ZipFile(os.path.abspath(filename))
    for l in range(1, passwd_len+1):
        for pwd in gen_passwd_iter(passwd_words, l, 1):
            try:
                zfile.extractall(pwd=pwd.encode('utf-8'))
                print('Try password:{0} successed.'.format(pwd))
                sys.exit(0)
            except Exception as e:
                print('Try password:{1} failed! Error:{0}'.format(e, pwd))

通常我们在linux下用源码安装库或程序，都是使用的autoools工具(虽然可能有些过时，bazel,CMake等等）。但是目前来看，还是一种不错的选择。

典型安装过程:

./configure

make

sudo make install

如果你自己创建了一个开源项目，自己手工编写Makefile的痛苦可想而知，因此还是用autools吧，如果正好你不太好用。就用下面的脚本生成吧。

https://github.com/happyAnger6/anger6_autotools.git
————————————————

overlayfs
overlayfs试图在其它文件系统之上提供一个联合的文件系统视图

Upper and Lower
overlayfs组合了2个文件系统—Upper文件系统和Lower文件系统。

当同名文件在Upper和Lower中都存在时，Lower中的文件会隐藏，如果是目录，则会合并显示.

Lower文件系统更准确的说法应该是目录树，因为这些目录树可以属于不同的文件系统。

Lower文件系统可以是linux支持的任何文件系统类型,其甚至可以是overlayfs.

目录合并
对于非目录文件，如果upper和lower中都存在，那么lower中的对象会被隐藏.

如果是目录，upper和lower中的目录会合并.

我们通过下面的命令来指定upperdir, lowerdir,它们将会合并成merged目录.

mount -t overlay overlay -o lowerdir=/root/lowerdir/,upperdir=/root/overlayt/upper,workdir=/root/overlayt/work /root/overlayt/merged

其中lowerdir目录中的内容如下:

[root@localhost overlayt]

ls -l /root/lowerdir/

总用量 4

-rw-r–r– 1 root root 4 3月  15 18:35 1

-rw-r–r– 1 root root 0 3月  15 18:35 2

-rw-r–r– 1 root root 0 3月  15 18:35 3

drwxr-xr-x 2 root root 6 3月  15 18:35 4

[root@localhost overlayt]

upper:我们的可写层

lower:底层目录树

merged:联合视图

workdir:需要是一个空目录，且和upper在同一个文件系统中

当在merged目录进行lookup操作时，lookup会在各个目录中搜寻并将结果联合起来缓存到overlayfs文件系统的dentry中。

如果upper,lower中存在相同的目录，则会合并在merged中显示

我们在lower中的dir1目录下创建low1文件

在upper的dir1目录下创建up1文件

在merged中的dir1目录下会同时出现up1,low1.

再来看看删除文件的处理
whiteouts和opaque目录
为了支持rm,rmdir操作，且不影响lowdir的内容，overlayfs需要在upper中记录被删除文件的信息。

whiteout是一个主从设备号为0/0的字符设备文件,当在merged目录下有whiteout文件时，lower目录中的同名文件会被忽略.whiteout文件本身也会隐藏，我们在upper目录中能够找到它.

readdir
当在merged目录调用readdir时，upper和lower目录的文件都会被读取(先读取upper目录,再读取lower目录).这个合并列表会被缓存在file结构中并保持到file关闭。如果目录被两个不同的进程打开并读取，那么它们有不同的缓存。seekdir设置偏移为0后再调用readdir会使缓存无效并进行重建。

这意味着，merged的变化在dir打开期间不会体现，对于很多程序容易忽略这一点。

非目录
对于非目录对象（文件，符号链接，特殊设备文件）。当对lowdir的对象进行写操作时，会先进行copy_up操作。创建硬链接也需要copy_up,软链接则不需要。

copy_up有时可能不需要，比如以read-write方式打开而实际上并没有进行修改.

copy_up处理的过程大致如下:

按需创建目录结构
用相同的元数据创建文件对象
拷贝文件数据
拷贝扩展属性  

copy_up完成之后,overlayfs就可以简单的在upper文件系统上提供对对象的访问。

多个lower layers
我们可以通过”:”来指定多个lower layers.

 mount -t overlay overlay -olowerdir=/lower1:/lower2:/lower3 /merged

在上面的例子中，我们没有指定upper,workdir.这意味着overlayfs是只读的。

多个lower layers从右边依次入栈，按照在栈中的顺序在merge中体现。lower3在最底层，lower1在是顶层.

非标准行为
copy_up操作创建了一个新的文件。新文件可能处于和老文件不同的文件系统中,因此st_dev,st_ino都是新的。

在copy_up之前老文件上的文件锁不会copy_up

如果一个有多个硬链接的文件被copy_up,那么会打断这种链接。改变不会传播给相同硬链接文件。

修改底层underlay文件系统
线下修改，当overlay没有mount时，允许修改upper,lower目录

不允许在mount overlay时对underlay进行修改。如果对underlay进行了修改，那么overlay的行为是不确定的。尽管不会crash或者deadlock.
————————————————
版权声明：本文为CSDN博主「self-motivation」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/happyAnger6/article/details/104885037

使用两种方法实现。

方法一：中序遍历二叉树，记录指定节点，当遍历到下一个节点时返回

时间复杂度o(n)

方法二:

1）当指定节点有右子树时，返回其右子树的第一个中序遍历节点

2）当指定节点无右子树时，如果其是父节点的左节点，则返回其父节点

3）当指定节点无右子树，且是其父节点的右节点，则一直向上找父节点，当找到某个父节点是其父节点的左节点时返回

时间复杂度o(logn)

代码实现:

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

class BinNode:
    def __init__(self, val, left=None, right=None, father=None):
        self.val = val
        self.left = left
        self.right = right

        if self.left:
            self.left.father = self
        if self.right:
            self.right.father = self

        self.father = father

    def __str__(self):
        return self.val

def no_traverse_next(target):
    if target.right:
        r = target.right
        while r.left:
            r = r.left
        return r

    f = target
    ff = f.father
    while f and ff:
        if ff.left == f:
            return ff
        else:
            f = ff
            ff = ff.father
    return None


def inorder_traverse_next(root, target):
    prev, node, stack = None, root, []
    while node or stack:
        if node:
            stack.append(node)
            node = node.left
        else:
            n = stack.pop()
            if n == target:
                prev = n
            if prev and n != target:
                return n
            node = n.right
    return None

if __name__ == "__main__":
    i = BinNode('i')
    h = BinNode('h')
    g = BinNode('g')
    f = BinNode('f')
    e = BinNode('e', h, i)
    d = BinNode('d')
    c = BinNode('c', f, g)
    b = BinNode('b', d, e)
    a = BinNode('a', b, c)

    print(inorder_traverse_next(a, i))
    print(inorder_traverse_next(a, b))
    print(inorder_traverse_next(a, g))

    print(no_traverse_next(i))
    print(no_traverse_next(b))
    print(no_traverse_next(g)

有志同道合的朋友，可以大家一起交流监督学习。哈哈哈 ！！！

5352. 生成每种字符都是奇数个的字符串
给你一个整数 n，请你返回一个含 n 个字符的字符串，其中每种字符在该字符串中都恰好出现 奇数次 。

返回的字符串必须只含小写英文字母。如果存在多个满足题目要求的字符串，则返回其中任意一个即可。

示例 1：

输入：n = 4
输出：”pppz”
解释：”pppz” 是一个满足题目要求的字符串，因为 ‘p’ 出现 3 次，且 ‘z’ 出现 1 次。当然，还有很多其他字符串也满足题目要求，比如：”ohhh” 和 “love”。
示例 2：

输入：n = 2
输出：”xy”
解释：”xy” 是一个满足题目要求的字符串，因为 ‘x’ 和 ‘y’ 各出现 1 次。当然，还有很多其他字符串也满足题目要求，比如：”ag” 和 “ur”。
示例 3：

输入：n = 7
输出：”holasss”  

提示：

1 <= n <= 500
我的解答：

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

class Solution:
    def generateTheString(self, n: int) -> str:
        cur_len = 0
        states = [0 for _ in range(26)]
        i, bFind = 0, False
        while i <= 26 and i >= 0:
            if bFind:
                break
 
            if i == 26:
                i-= 1
                continue
 
            while True:
                if states[i] == 0:
                    j = 1
                else:
                    j = states[i] + 2
 
                cur_len-=states[i]
                if cur_len + j == n:
                    states[i] = j
                    bFind = True
                    break
                elif cur_len + j > n:
                    states[i] = 0
                    i-=1
                    break
                else:
                    states[i] = j
                    cur_len += j
                    i+=1
                    break
 
        s = ""
        cnt = 0
        for i, j in enumerate(states):
            if j > 0:
                c = chr(ord('a')+i)*j
                s += c
                cnt+=j

         return s