PHP
6 minutes read (About 878 words)

依赖注入和IOC

依赖注入

依赖注入 (Dependency Injection，简称DI）
Class A中用到了Class B的对象b，一般情况下，需要在A的代码中显式的new一个B的对象。
采用依赖注入技术之后，A的代码只需要定义一个私有的B对象，不需要直接new来获得这个对象，而是通过相关的容器控制程序来将B对象在外部new出来并注入到A类里的引用中。

而我们通常注入依赖的方式有两种：

  • 通过构造函数传入依赖，实现特定参数的构造函数，在新建对象时传入所依赖类型的对象。

  • 通过setter方法注入依赖，实现特定属性的public set方法，来让外部容器调用传入所依赖类型的对象。

    控制反转

控制反转（Inversion of Control，缩写为IoC），是面向对象编程中的一种设计原则，可以用来减低计算机代码之间的耦合度。其中最常见的方式叫做依赖注入（Dependency
Injection，简称DI），还有一种方式叫“依赖查找”（Dependency
Lookup）。通过控制反转，对象在被创建的时候，由一个调控系统内所有对象的外界实体，将其所依赖的对象的引用传递给它。也可以说，依赖被注入到对象中。

控制反转是一种思想，而依赖注入是这种思想的一种实现。

下面是一段IOC容器的实现代码。

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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
<?php
    class Bim
    {
        public function doSomething()
        {
            echo __METHOD__, '|';
        }
    }
    
    class Bar
    {
        private $bim;
    
        public function __construct(Bim $bim)
        {
            $this->bim = $bim;
        }
    
        public function doSomething()
        {
            $this->bim->doSomething();
            echo __METHOD__, '|';
        }
    }
    
    class Foo
    {
        private $bar;
    
        public function __construct(Bar $bar)
        {
            $this->bar = $bar;
        }
    
        public function doSomething()
        {
            $this->bar->doSomething();
            echo __METHOD__;
        }
    }
    
    class Container
    {
        private $s = array();
    
        public function __set($k, $c)
        {
            $this->s[$k] = $c;
        }
    
        public function __get($k)
        {
            // return $this->s[$k]($this);
            return $this->build($this->s[$k]);
        }
    
        /**
         * 自动绑定（Autowiring）自动解析（Automatic Resolution）
         *
         * @param string $className
         * @return object
         * @throws Exception
         */
        public function build($className)
        {
            // 如果是匿名函数（Anonymous functions），也叫闭包函数（closures）
            if ($className instanceof Closure) {
                // 执行闭包函数，并将结果
                return $className($this);
            }
    
            /** @var ReflectionClass $reflector */
            $reflector = new ReflectionClass($className);
    
            // 检查类是否可实例化, 排除抽象类abstract和对象接口interface
            if (!$reflector->isInstantiable()) {
                throw new Exception("Can't instantiate this.");
            }
    
            /** @var ReflectionMethod $constructor 获取类的构造函数 */
            $constructor = $reflector->getConstructor();
    
            // 若无构造函数，直接实例化并返回
            if (is_null($constructor)) {
                return new $className;
            }
    
            // 取构造函数参数,通过 ReflectionParameter 数组返回参数列表
            $parameters = $constructor->getParameters();
    
            // 递归解析构造函数的参数
            $dependencies = $this->getDependencies($parameters);
    
            // 创建一个类的新实例，给出的参数将传递到类的构造函数。
            return $reflector->newInstanceArgs($dependencies);
        }
    
        /**
         * @param array $parameters
         * @return array
         * @throws Exception
         */
        public function getDependencies($parameters)
        {
            $dependencies = [];
    
            /** @var ReflectionParameter $parameter */
            foreach ($parameters as $parameter) {
                /** @var ReflectionClass $dependency */
                $dependency = $parameter->getClass();
    
                if (is_null($dependency)) {
                    // 是变量,有默认值则设置默认值
                    $dependencies[] = $this->resolveNonClass($parameter);
                } else {
                    // 是一个类，递归解析
                    $dependencies[] = $this->build($dependency->name);
                }
            }
    
            return $dependencies;
        }
    
        /**
         * @param ReflectionParameter $parameter
         * @return mixed
         * @throws Exception
         */
        public function resolveNonClass($parameter)
        {
            // 有默认值则返回默认值
            if ($parameter->isDefaultValueAvailable()) {
                return $parameter->getDefaultValue();
            }
    
            throw new Exception('I have no idea what to do here.');
        }
    }
    
    // ----
    $c = new Container();
    $c->bar = 'Bar';
    $c->foo = function ($c) {
        return new Foo($c->bar);
    };
    // 从容器中取得Foo
    $foo = $c->foo;
    $foo->doSomething(); // Bim::doSomething|Bar::doSomething|Foo::doSomething
    
    // ----
    $di = new Container();
    
    $di->foo = 'Foo';
    
    /** @var Foo $foo */
    $foo = $di->foo;
    
    var_dump($foo);
    /*
    Foo#10 (1) {
      private $bar =>
      class Bar#14 (1) {
        private $bim =>
        class Bim#16 (0) {
        }
      }
    }
    */
    
    $foo->doSomething(); // Bim::doSomething|Bar::doSomething|Foo::doSomething
?>
设计模式
5 minutes read (About 728 words)

三种工厂模式

阅读《设计模式之禅》后的总结。

前言

之前的工厂模式有看过，但是没过多久就会忘，主要还是自己平常写代码业务逻辑的时候缺少思考，可能也就会用个单例模式。然后网上很多有关设计模式的介绍，感觉有些还是介绍的不够具体，或者说只介绍到了工厂模式的一部分吧。

工厂方法模式

工厂方法模式的定义：Define an interface for ceating an object ,but let subclasses decide which class to instantiate.Factory Method lets a class defer instantiation to subclasses(定义一个用于创建对象的接口，让子类决定实例化哪一个类。工厂方法使一个类的实例化延迟到器子类。)

1
2
3
4
5
6
7
8
  /**
   * 产品类接口
   */
interface Product{
    public function method1();
    public  function method2();
    
}
1
2
3
4
5
6
7
8
9
10
11
12
  /**
   * 具体产品类
   */
public  class ConcreteProduct1 implements Product{
    public function method1(){
    //业务逻辑
    }
    public function method2(){
    //业务逻辑
    };
    
}
1
2
3
4
5
6
  /**
   * 工厂类
   */
 interface Creator{
    public  creatorProduct();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
  /**
   * 具体工厂类
   */
public class ConcreteCreator implements Creator{

    public function creatorProduct($product){
        try{
            $productObj = new $product;
        }catch(Exception $e){
            //异常处理
        }
        return $productObj;
    }
}
1
2
3
4
5
6
7
8
public class Client{
    public function main(){
        //用工厂类制造product1
        $fc = new ConcreteCreator();
        $cp1 = $fc->creatorProduct("ConcreteProduct1");
        $cp1->method1();
    }
}

简单工厂模式

简单工厂模式又称静态工厂模式

就是把上面的方法ConcreteCreator()改为静态就可以了。
优点很明显，就是不用实例化工厂类直接调用工厂方法就可以了。

抽象工厂模式

抽象工厂模式

优点

  • 封装性

  • 产品族内的约束为非公开状态

缺点

  • 产品族的扩展非常困难
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
<?php
/**
 * 抽象工厂模式 2010-05-28 sz
 * @author phppan.p#gmail.com  
 * http://www.phppan.com 哥学社成员（http://www.blog-brother.com/）
 * @package design pattern
 */
 
/**
 * 抽象工厂
 */
interface AbstractFactory {
    /**
     * 创建等级结构为A的产品的工厂方法
     */
    public function createProductA();
 
     /**
     * 创建等级结构为B的产品的工厂方法
     */
    public function createProductB();
 
}
 
/**
 * 具体工厂1
 */
class ConcreteFactory1 implements AbstractFactory{
 
    public function createProductA() {
        return new ProductA1();
    }
 
    public function createProductB() {
        return new ProductB1();
    }
}
 
 
/**
 * 具体工厂2
 */
class ConcreteFactory2 implements AbstractFactory{
 
    public function createProductA() {
        return new ProductA2();
    }
 
    public function createProductB() {
        return new ProductB2();
    }
}
 
/**
 * 抽象产品A
 */
interface AbstractProductA {
 
    /**
     * 取得产品名
     */
    public function getName();
}
 
/**
 * 抽象产品B
 */
interface AbstractProductB {
 
    /**
     * 取得产品名
     */
    public function getName();
}
 
/**
 * 具体产品Ａ1
 */
class ProductA1 implements AbstractProductA {
    private $_name;
 
    public function __construct() {
        $this->_name = 'product A1';
    }
 
    public function getName() {
        return $this->_name;
    }
}
 
 
/**
 * 具体产品Ａ2
 */
class ProductA2 implements AbstractProductA {
    private $_name;
 
    public function __construct() {
        $this->_name = 'product A2';
    }
 
    public function getName() {
        return $this->_name;
    }
}
 
 
/**
 * 具体产品B1
 */
class ProductB1 implements AbstractProductB {
    private $_name;
 
    public function __construct() {
        $this->_name = 'product B1';
    }
 
    public function getName() {
        return $this->_name;
    }
}
 
/**
 * 具体产品B2
 */
class ProductB2 implements AbstractProductB {
    private $_name;
 
    public function __construct() {
        $this->_name = 'product B2';
    }
 
    public function getName() {
        return $this->_name;
    }
}
 
 
/**
 * 客户端
 */
class Client {
 
     /**
     * Main program.
     */
    public static function main() {
        self::run(new ConcreteFactory1());
        self::run(new ConcreteFactory2());
    }
 
    /**
     * 调用工厂实例生成产品，输出产品名
     * @param   $factory    AbstractFactory     工厂实例
     */
    public static function run(AbstractFactory $factory) {
        $productA = $factory->createProductA();
        $productB = $factory->createProductB();
        echo $productA->getName(), '<br />';
        echo $productB->getName(), '<br />';
    }
 
}
 
Client::main();
?>
设计模式
3 minutes read (About 436 words)

单例模式

单模式的定义：确保某一个类只有一个实例，而且自行实例化并向整个系统提供这个实例。

优点

  • 由于单励模式在内存中只有一个实例，减少了内存的开支，特别是一个对象需要频繁地创建和销毁，而且创建或销毁时性能又无法优化，单例模式的优势就非常明显。

  • 由于单例模式只生成一个实例，所以减少了系统的性能开销，当一个对象的产生需要比较多的资源时，如读取配置，产生其他依赖对象时，则可以通过在应用启动时产生一个单对象。

使用场景

  • 创建一个对象需要消耗很多资源的，如要访问IO和数据库等资源。

  • 在整个项目中需要一个共享的访问点或共享数据，例如一个Web页面上的计数器，可以不用每次刷新都记录到数据库中，使用单例模式保持计数器的值。

单模式的如下面代码所示。

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
<?php

/**
 * 懒汉式单例类
 */
class Singleton {
 
    /**
     * 静态成品变量 保存全局实例
     */
    private static  $_instance = NULL;
 
    /**
     * 私有化默认构造方法，保证外界无法直接实例化
     */
    private function __construct() {
    }
 
    /**
     * 静态工厂方法，返还此类的唯一实例
     */
    public static function getInstance() {
        if (is_null(self::$_instance)) {
            self::$_instance = new Singleton();
        }
 
        return self::$_instance;
    }
 
    /**
     * 防止用户克隆实例
     */
    public function __clone(){
        die('Clone is not allowed.' . E_USER_ERROR);
    }
 
    /**
     * 测试用方法
     */
    public function test() {
        echo 'Singleton Test!';
    }
 
}
 
/**
 * 客户端
 */
class Client {
 
     /**
     * Main program.
     */
    public static function main() {
        $instance = Singleton::getInstance();
        $instance->test();
    }
}
 
Client::main();
?>
MySQL
7 minutes read (About 1082 words)

高性能MySQL之索引（一）

这篇文章来自于对《高性能MySQL》的总结

索引（在mysql中叫做“key”）是存储引擎用于快速找到记录的一种数据结构。

索引基础

就像看书一样，我们想要找我们想看的内容都会翻到书的目录，找到对应的章节。这里的目录就是现实生活中的索引。
在mysql中，在存储引擎用类似的方式使用索引，其先在索引中找到对应值，然后根据匹配的索引记录找到对应的数据行。

索引的类型

Mysql索引的类型有B-Tree索引，哈希索引，空间数据索引（R-Tree），全文索引。

Btree索引

当人们谈论索引的时候，如果没有特别指明类型，多半说的就是B-Tree数据结构来存储数据。大多数Mysql引擎都支持这种索引.Archive引擎是一个例外：5.1之前Archive不支持任何索引，直到5.1才开始支持单个自增列（AUTO_INCREMENT）的索引。
我们使用的术语“B-Tree”,是因为在MySQL在Create Table和其他语句中也使用该关键字。不过底层的存储引擎也可能使用不同的存储结构，例如NDB集群存储引擎内部实际上使用了T-Tree结构存储这种引擎，即使其名字是BTREE；Innodb则使用B+Tree，各种数据结构和算法的变种不在本讨论范围之内。

![B-Tree结构][1]
建立在B-Tree树上的索引（技术上是B+Tree）
B-Tree索引能够加快访问数据的速度，因为存储引擎不再需要进行全表扫描来获取需要的数据，取而代之的是从索引的根节点（图示并未画出）开始进行搜索。根节点槽中存放了指向子节点的指针，存储引擎根据这些指向下层查找。通过比较节点页的值和要查找的值可以找到合适的指针进入下层子节点，这些指针实际上定义了子节点页中值的上限和下限。最终存储引擎要么是找到对应的值，要么该记录不存在。
叶子节点页比较特别，它们的指针指向的是被索引的数据，而不是其他的节点页。
[1]: http://wx2.sinaimg.cn/mw690/7503dc51gy1fcoo7uy3rnj20rh0c7ab2.jpg

索引有效查询方式

全值匹配

全值匹配指的是和索引中的所有列进行匹配，例如前面提到的索引可用于查找姓名为Cuba Allen，出生于1960-01-01的人。

匹配最左前缀

前面提到的索引可用于查找所有姓为Allen的人，即只使用索引的第一列。

匹配范围值

例如前面提到的索引可以用于查找姓在Allen和Barrymore之间的人。这里只使用了索引的第一列。

精确匹配某一列并范围匹配另外一列

前面提到的索引也可用于查找所有姓为Allen，并且名字是字母K开头（比如Kim,Karl等）的人。即第一列last_name全匹配，第二列first_name范围匹配。

只访问索引的查询

B-Tree通常可以支持“只访问索引的查询”，即查询只需要访问索引，而无需访问数据行。这种方式叫做“覆盖索引”。

索引的限制

  • 如果不是按照索引的最左列开始查询，则无法使用索引。
  • 不能跳过索引中的列。
  • 如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查找。

总结：索引列的顺序是很重要的，这些限制都和索引列的顺序有关。在优化性能的时候，可能需要使用相同的列但顺序不同的索引来满足不同类型的查询需求。

leetcode
a minute read (About 185 words)

Sum_to_leaf_numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,

  1
 / \
2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.

解析

这道题目不难，用递归很好解决，只要有儿子就要加数字，这里的数字组成方式是旧的树*10+新的数。

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int sumNumbers(TreeNode* root) {
        if(!root) return 0;
        int sum=0;
        getSum(root,root->val,sum);
        return sum;
            
    }
    void getSum(TreeNode * root,int number,int &sum){
        if(root->left)
            getSum(root->left,number*10+root->left->val,sum);
        if(root->right)
            getSum(root->right,number*10+root->right->val,sum);
        if(!root->left&&!root->right){
            sum += number;
        }
    }
};
leetcode
3 minutes read (About 416 words)

Delete_node_in_bst

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
Search for a node to remove.
If the node is found, delete the node.
Note: Time complexity should be O(height of tree).

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

    5
   / \
  4   6
 /     \
2       7

Another valid answer is [5,2,6,null,4,null,7].

    5
   / \
  2   6
   \   \
    4   7

解析

这道题目重点分以下几种情况去分析

  1. 如果要删除的那个节点存在，且他的左右子树不都存在。那就直接用子树去替代被删除的节点。
  2. 如果要删除的节点左右子树都存在的话，正如上面所示的其实有两种解决方案，一种就是拿右子树的最小值去替代，另外一种就是拿左子树的最大值去替代。替代完之后又要删除替代的那个节点（这里逻辑就可以套用1去解决）。
    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
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        TreeNode* deleteNode(TreeNode* root, int key) {
            if(!root) return NULL;
            //搜索那个要删除的节点
            if(key < root->val){
                //在左子树搜
                root->left = deleteNode(root->left,key);
            } else if(key > root->val){
                //在右子树搜
                root->right = deleteNode(root->right,key);
                
            } else {
                //找到删除节点，而且左右子树只存在一个以下。
                if(!root->left||!root->right){
                    root = (root->left) ? root->left : root->right;
                }else{
                //左右子树都存在
                    TreeNode* cur;
                    cur = root->right;
                    while(cur->left){
                        cur = cur->left ;
                    }
                    root->val = cur->val;
                //删除右子树下用来替换的节点。
                    root->right = deleteNode(root->right,cur->val);
                }
            }
            return root;    
        }
    };
leetcode
2 minutes read (About 266 words)

重新构建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

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
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    //判断两个向量大小是否相等
        if(preorder.size() != inorder.size())
            return NULL;
        int length = preorder.size();
        //传入首尾的索引
        return constructTree(preorder,0,length-1,inorder,0,length-1);
        
    }
    TreeNode* constructTree(vector<int>& preorder,int ps, int pend,vector<int>& inorder ,int is,int iend){
    //边界值判断 超出就表示没有左右树了。
        if(ps>pend || is>iend)
            return NULL;
        TreeNode *root = new TreeNode(preorder[ps]);
        int irootpos;
            for(int i=is;i<=iend;i++){
                if(inorder[i] == root->val){
                    irootpos = i;
                    break;
                }
            }
        //获取中序的左边的长度 表示左子树的大小
        int leftlength = irootpos - is;
        //获取中序的右边的长度 表示右子树的大小
        int rightlength = iend - irootpos;
        //进入递归
        root->left = constructTree(preorder,ps+1,ps+leftlength,inorder,is,irootpos-1);
        root->right = constructTree(preorder,pend-rightlength+1,pend,inorder,irootpos+1,iend);
        //返回根节点
        return root;
               
    }
    
};
C&数据结构
4 minutes read (About 530 words)

二叉树的前中后非递归实现

{}

设计模式
4 minutes read (About 639 words)

适配器模式

读了《设计模式之蝉》之适配器模式后的总结。

C适配器模式的定义：
onvert the interface of a class into another interface clients expect.Adapter lets classes work togeher that couldn’t otherwise because of incompatible interfaces.(将一个类的接口变换成客户端所期待的另一种接口，从而使原本因接口不匹配而无发在一起工作的两个类能够在一起工作)

类适配器

原有公司的内部员工形象有这么一个接口（target）

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
<?php 
interface IuserInfo{
    public function getUserName();
    public function getHomeAdress();
    public function getMobileNumber();
    public function getOfficeTelNumber();
    public function getJobPosition();
    public function getHomeNumber();
    }

public class UserInfo implements IuserInfo{
    public function getUserName(){
        echo "名字是...."
    };
    public function getHomeAdress(){
        echo "家庭住址是...."
    };
    public function getMobileNumber(){
        echo "手机号码是...."
    };
    public function getOfficeTelNumber(){
        echo "办公室号码是..."
    };
    public function getHomeNumber(){
        echo "家里的号码是..."
    };
    
    public function getJobPosition(){
        echo "办公室位置式..."
    };

}
public class clients{
    public main function(){
        $user = new UserInfo();
        $user->getUserName();
    }
}

一切看上去都没有什么问题，但是可能处于某种原因，公司需要从其他公司租用的员工的信息。而其他公司租用的员工信息的接口是这个样子的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<?php
    interface IouterUserInfo(){
        public function userNumber();
        public function userAddress();
    }
    public class OuterUser implements IouterUserInfo{
        public function userNumber(){
            $telnumber = ['moblie_number' => '135...',
                'office_mobile_number' =>'001-12..',
                'home_tel_number' => '002-22'
            ];
            return $telnumber;
        }
        public function baseInfo(){
            $info = ['name' => 'steve',
                'office_address' => '办公室位置...',
                'home_address' => '家的位置是...'
            ];
            return $info;
        }
    }

这和我们原先的接口完全不同，我们希望还是希望以自己接口设计去获取信息，因为这样就不需要大修改原先已经写好的客户端类。
我们这里就可以用到适配器模式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
<?php
    //类适配器 OuterUserInfo
    public class OuterUserInfo extends OuterUser implements UserInfo{
        public function getUserName(){
            echo $this->baseInfo()['name'];
        };
        public function getHomeAdress(){
        };
        public function getMobileNumber(){
        };
        public function getOfficeTelNumber(){
        };
        public function getHomeNumber(){
        };
        public function getJobPosition(){
        };
    }
    //客户端相对于之前只是改了实例其他不变。
    public class clients{
        public main function(){
            $user = new OuterUserInfo();
            $user->getUserName();
        }
}

对象适配器

如果是多个不同的接口则可以用对象适配器
对象适配器和类适配器的不同就是，对象适配器是把对象注入到适配器内部而不是通过继承直接使用。假如我们把IouterUserInfo一分为二，mobile归IouterUserMobile（通讯录），IouterUserInfo接口则是基本信息（姓名和地址）。那么类适配器是不能继承两个类的，所以采用对象适配器来解决。

1
2
3
4
5
6
7
8
9
<?php 
    public class OuterUserInfo implements UserInfo{
        private $outerUserMobile;
        private $outerUserInfo;
        public function __construct(OuterUserInfo $outrUserInfo,OuterUserMoblie $outerUserMobile) {
        $this->outerUserMobile =  $outerUserMobile;
        $this->outerUserInfo =  $outerUserInfo;
    }
    }
leetcode
3 minutes read (About 405 words)

lca_of_bst

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

     _______6______
    /              \
 ___2__          ___8__
/      \        /      \
0      _4       7       9
      /  \
      3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

意思就是找俩个节点的共同祖先。
这是一颗二叉搜索树，解决思路就比较简答。输入参数是根节点和找共同祖先的两个节点。我们就可以让两个节点和root节点做比较。有以下几种情况：

  1. 两个节点中一个比根节点大，另一个比根节点小。那么他们的祖先就是root。
  2. 两个节点有一个节点等于根节点，那么很显然他们的祖先就是root。
  3. 两个节点都比root节点大，那么缩小两个几点的搜索范围，到root的右子树中，然后再和root->right 做比较。
  4. 同理，两个节点都比root的节点小，到root的左子树做比较。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if((root->val > p->val && root->val< q->val) ||(root->val < p->val && root->val> q->val))
            return root;
        if(root->val == p->val ||root->val== q->val)
            return root;
        if(root->val>p->val&&root->val>q->val)
            return lowestCommonAncestor(root->left,p,q);
        if(root->val<p->val&&root->val<q->val)
            return lowestCommonAncestor(root->right,p,q);
      
        
    }
};
Follow

Categories

Tag Cloud

C&数据结构 leetcode 协议 总结 数据结构 设计模式

Recent

Recent

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×