画图、举例子和分解这三种办法能够帮助我们解决复杂的编程问题。
图形能使抽象的问题形象化，如涉及链表、 二叉树等数据结构时， 如果在纸上画几张草图， 数形结合，抽象问题中中隐藏的规律就有可能变得很直观。
一个或两个简单而有代表性的例子能使抽象的问题具体化。很多与算法相关的问题都很抽象，未必一眼就能看出它们的规律。 这个时候我们不妨举几个例子， —步一步模拟运行的过程， 说不定就能发现其中的规律， 从而找到解决问题的窍门。
把复杂问题分解成若干个小问题， 是解决很多复杂问题的有效方法。如果我们遇到的问题很大， 可以尝试先把大问题分解成小问题， 然后再递归地解决这些小问题。 分治法、 动态规划等方法都是应用分解复杂问题的思路。从整体上来说，面向过程和面向对象的设计哲学都有这种分解思维的体现，面向对象：函数分解。面向过程：类与对象分解，在类的内部再分解出成员函数。
1 字符串替换(从简单实例和画图入手)
题目：请实现一个函数，把字符串中的每个空格替换成"%20"。例如输入“We are happy.”，则输出“We%20are%20happy.”。
在网络编程中，如果URL参数中含有特殊字符，如空格、'#'等，可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在'%'后面跟上ASCII码的两位十六进制的表示。比如空格的ASCII码是32，即十六进制的0x20，因此空格被替换成"%20"。再比如'#'的ASCII码为35，即十六进制的0x23，它在URL中被替换为"%23"。
看到这个题目，我们首先应该想到的是原来一个空格字符，替换之后变成'%'、'2'和'0'这3个字符，因此字符串会变长。如果是在原来的字符串上做替换，那么就有可能覆盖修改在该字符串后面的内存。如果是创建新的字符串并在新的字符串上做替换，那么我们可以自己分配足够多的内存。
现在我们考虑怎么做替换操作。最直观的做法是从头到尾扫描字符串，每一次碰到空格字符的时候做替换。由于是把1个字符替换成3个字符，我们必须要把空格后面所有的字符都后移两个字节，否则就有两个字符被覆盖了。
举个例子，我们从头到尾把"We are happy."中的每一个空格替换成"%20"。为了形象起见，我们可以用一个表格来表示字符串，表格中的每个格子表示一个字符。
我们替换第一个空格，这个字符串变成下图中的内容：
表格中灰色背景的格子表示需要做移动的区域。接着我们替换第二个空格，替换之后的内容如下图所示：
同时，我们注意到用深灰色背景标注的"happy"部分被移动了两次。
假设字符串的长度是n。对每个空格字符，需要移动后面O(n)个字符，因此对含有O(n)个空格字符的字符串而言总的时间效率是O(n2)。
在前面的分析中，我们发现数组中很多字符都移动了很多次，能不能减少移动次数呢？答案是肯定的。我们换一种思路，把从前向后替换改成从后向前替换。
我们可以先遍历一次字符串，这样就能统计出字符串中空格的总数，并可以由此计算出替换之后的字符串的总长度。每替换一个空格，长度增加2，因此替换以后字符串的长度等于原来的长度加上2乘以空格数目。我们还是以前面的字符串"We are happy."为例，"We are happy."这个字符串的长度是14(包括结尾符号'0')，里面有两个空格，因此替换之后字符串的长度是18。
我们从字符串的后面开始复制和替换。首先准备两个指针，P1和P2。P1指向原始字符串的末尾，而P2指向替换之后的字符串的末尾，如下图所示：
接下来我们向前移动指针P1，逐个把它指向的字符复制到P2指向的位置，直到碰到第一个空格为止。此时字符串包含如下图所示：
灰色背景的区域是做了字符拷贝(移动)的区域。碰到第一个空格之后，把P1向前移动1格，在P2之前插入字符串"%20"。由于"%20"的长度为3，同时也要把P2向前移动3格如下图所示：
我们接着向前复制，直到碰到第二个空格，如下图所示：
和上一次一样，我们再把P1向前移动1格，并把P2向前移动3格插入"%20"，如下图所示：
此时P1和P2指向同一位置，表明所有空格都已经替换完毕。
从上面的分析我们可以看出，所有的字符都只复制(移动)一次，因此这个算法的时间效率是O(n)，比第一个思路要快。
代码：
#include #include /*length 为字符数组string的总容量*/void ReplaceBlank(char string[], int length){    if(string == NULL && length <= 0)        return;    /*originalLength 为字符串string的实际长度*/    int originalLength = 0;    int numberOfBlank = 0;    int i = 0;    while(string[i] != '0')    {        ++ originalLength;        if(string[i] == ' ')            ++ numberOfBlank;        ++ i;    }    /*newLength 为把空格替换成'%20'之后的长度*/    int newLength = originalLength + numberOfBlank * 2;    if(newLength > length)        return;    int indexOfOriginal = originalLength;    int indexOfNew = newLength;    while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)    {        if(string[indexOfOriginal] == ' ')        {            string[indexOfNew --] = '0';            string[indexOfNew --] = '2';            string[indexOfNew --] = '%';        }        else        {            string[indexOfNew --] = string[indexOfOriginal];        }        -- indexOfOriginal;    }}void Test(char* testName, char string[], int length, char expected[]){    if(testName != NULL)        printf("%s begins: ", testName);    ReplaceBlank(string, length);    if(expected == NULL && string == NULL)        printf("passed.");    else if(expected == NULL && string != NULL)        printf("failed.");    else if(strcmp(string, expected) == 0)        printf("passed.");    else        printf("failed.");}// 空格在句子中间void Test1(){    const int length = 100;    char string[length] = "hello world";    Test("Test1", string, length, "hello%20world");}// 空格在句子开头void Test2(){    const int length = 100;    char string[length] = " helloworld";    Test("Test2", string, length, "%20helloworld");}// 空格在句子末尾void Test3(){    const int length = 100;    char string[length] = "helloworld ";    Test("Test3", string, length, "helloworld%20");}// 连续有两个空格void Test4(){    const int length = 100;    char string[length] = "hello  world";    Test("Test4", string, length, "hello%20%20world");}// 传入NULLvoid Test5(){    Test("Test5", NULL, 0, NULL);}// 传入内容为空的字符串void Test6(){    const int length = 100;    char string[length] = "";    Test("Test6", string, length, "");}//传入内容为一个空格的字符串void Test7(){    const int length = 100;    char string[length] = " ";    Test("Test7", string, length, "%20");}// 传入的字符串没有空格void Test8(){    const int length = 100;    char string[length] = "helloworld";    Test("Test8", string, length, "helloworld");}// 传入的字符串全是空格void Test9(){    const int length = 100;    char string[length] = "   ";    Test("Test9", string, length, "%20%20%20");}int main(){    Test1();    Test2();    Test3();    Test4();    Test5();    Test6();    Test7();    Test8();    Test9();    while(1);    return 0;}
2 某年日历输出(复杂问题的分解)
这个问题看似稍微有点复杂，但分解后，再组合成相互调用关系，就简单了。
某年日历输出可以分解为以下函数功能：
void PrintHead(int m);// 打印每月日历的头部bool IsLeapYear(int y);// 是否闰年int FirstDayOfYear(int y);// 元旦是周几int DaysOfMonth(int m);// 某月天数void PrintMonth(int m);// 打印某月日历
代码：
#includeusing namespace std;#includevoid PrintHead(int m);// 打印每月日历的头部bool IsLeapYear(int y);// 是否闰年int FirstDayOfYear(int y);// 元旦是周几int DaysOfMonth(int m);// 某月天数void PrintMonth(int m);// 打印某月日历int weekDay;// 每月1号是周几int year;void main(){cerr<>year;if(year<1900){//cerr<
3 其它的一些例子
3.1 删除链表中指定的元素
代码：
class Solution {public:    ListNode* removeElements(ListNode* head, int val) {        // 创建虚拟头结点        ListNode* dummyHead = new ListNode(0);        dummyHead->next = head;        ListNode* cur = dummyHead;        while(cur->next != NULL){            if(cur->next->val == val){                ListNode* delNode = cur->next;                cur->next = delNode->next;                delete delNode;            }            else                cur = cur->next;        }        ListNode* retNode = dummyHead->next;        delete dummyHead;        return retNode;    }};
3.2 反转链表
class Solution {public:    ListNode* reverseList(ListNode* head) {        ListNode* pre = NULL;        ListNode* cur = head;        while(cur != NULL){            ListNode* next = cur->next;            cur->next = pre;            pre = cur;            cur = next;        }        return pre;    }};
3.3 层次遍历二叉树
3.4 移除倒数第n个节点
class Solution {public:    ListNode* removeNthFromEnd(ListNode* head, int n) {     ListNode* dummyHead = new ListNode(0);        dummyHead->next = head;        ListNode* p = dummyHead;        ListNode* q = dummyHead;        for( int i = 0 ; i < n + 1 ; i ++ ){            q = q->next;        }        while(q){            p = p->next;            q = q->next;        }        ListNode* delNode = p->next;        p->next = delNode->next;        delete delNode;        ListNode* retNode = dummyHead->next;        delete dummyHead;        return retNode;    }};
3.5 二分查找
#include   // 二分查找的递归与非递归实现using namespace std; // 分治法，可分，可合，子问题有独立性int bisoLoop(int arr[], int len, int findData){    if(arr==NULL || len <=0)        return -1;    int start = 0;    int end = len-1;    while(start<=end)    {        int mid = start+(end-start)/2;        if(arr[mid] == findData)            return mid;        else if(findData < arr[mid])            end = mid-1;        else            start = mid+1;    }    return -1;}// 递归有自调用的问题，需要将start和end写在参数列表中// 来标记和动态变更搜索范围的开始和结束int bisoRecurs(int arr[], int findData, int start, int end){    if(arr==NULL || start>end)        return -1;        int mid = start+(end-start)/2;        if(arr[mid] == findData)            return mid;        else if(findData < arr[mid])            bisoRecurs(arr, findData, start, mid-1);        else            bisoRecurs(arr, findData, mid+1, end);}void main(){    int arr[] = {1,2,3,4,5,6,7,8,9};    int len = sizeof(arr)/sizeof(arr[0]);    int index = bisoLoop(arr,len,6);    int index2 = bisoRecurs(arr,6,0,len-1);    cout<
ref：《剑指Offer：名企面试官精讲典型编程题》
－End－

1、问题描述
请实现一个函数复制复杂链表。在复杂链表中，每个节点除了有一个m_next指针指向下一个节点处，还有一个m_pSibling指针指向链表中的任意节点或者NULL。
2、解题思路

边界条件：复杂链表头节点为空指针。
思路1：最简单的方法是把复制过程分成两步：第一步是复制原始链表中的每一个节点，并用m_next将这些节点连接起来；第二步是设置每一个节点的m_pSbling。这种方法的时间复杂度为$O(n^{2})$。
思路2：第二种方法分为3步：
（1）第一步是根据原始链表中的每一个节点N创建N’，然后把N’连接在N的后面。链表经过第一步后新的的结构如下图所示：


（2）第二步是设置复制出来节点的m_pSbling。假设原始链表中的节点N的m_pSbling指向节点S，其复制出来的对应节点N’是N的m_next指向的节点，那么N’的m_pSibliing指向的节点S’是S的m_pSibling所指向的节点。例如上图，A的m_next是A’，C的m_next是C’，A的m_pSbling是C，那么A’的m_pSbling就是C。设置m_pSbling之后的链表如下所示：



（3）第三步是把这个长链表拆成两个短链表。将奇数位置的节点连接起来就是原始链表；将偶数位置的节点连接起来就是复制后的链表。



3、代码实现
# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        self.CloneNode(pHead)
        self.ConnectSiblingNode(pHead)
        pCloneNode = self.ReconnectNode(pHead)
        return pCloneNode

    # 复制原链表的每一节点N,创建N',并将N'连接到N节点的后面
    def CloneNode(self,pHead):
        pNode = pHead
        while pNode != None:
            pCloneNode = RandomListNode(pNode.label)
            pCloneNode.next = pNode.next
            pNode.next = pCloneNode
            pNode = pCloneNode.next


    #设置复制出来的节点的sibling
    def ConnectSiblingNode(self, pHead):
        pNode = pHead
        while pNode != None:
            pCloneNode = pNode.next
            if pCloneNode != None:
                if pNode.random != None:
                    pCloneNode.random = pNode.random.next
            pNode = pCloneNode.next

    #将长链表拆成两个链表
    def ReconnectNode(self,pHead):
        pNode = pHead
        pCloneHead = None
        pCloneNode = None
        if pNode != None:
            pCloneHead = pNode.next
            pCloneNode = pCloneHead
            pNode.next = pCloneNode.next
            pNode = pNode.next

        while pNode != None:
            pCloneNode.next = pNode.next
            pCloneNode = pCloneNode.next
            pNode.next = pCloneNode.next
            pNode = pNode.next

        return pCloneHead

层次分析法：Analytic Hierarchy Process(AHP)

文章目录
一、致谢
二、运用层次分析法的一般步骤
三、简单举例进行应用
四、部分步骤的matlab实现

一、致谢
本文得益于王莲芬老师、许树柏老师著作《层次分析法引论》（中国人民大学出版社1990年6月第1版）良多，在此致谢。




二、运用层次分析法的一般步骤
1.分析系统中各因素之间的关系，建立系统更多解题层次结构

首先把问题条理化、层次化，构造出一个层次分析的结构模型。在这个结果模型下，复杂问题被分解为可以被称之为元素的组成部分。这些元素又按照其属性分为若干组，形成不同层次。同一层次的元素作为准则对下一层次的某些元素起支配作用，同时又受上一层次元素的支配。这些层次大体上可以分为3类：

（1）最高层：这一层次中只有一个元素，一般它是分析问题的预定目标或理想结果，因此也称为结果层。

（2）中间层：这一层次包括了为实现目标所涉及的中间节，它可以由若干个层次组成，包括所需考虑的准则、子准则，因此也称为准则层。

（3）最底层：表示为实现目标可供选择的各种措施、决策方案等因此也称为措施层或方案层。

2.对同一层次的各元素关于上一层次中某一准则的重要性进行两两比较，构造两两比较判断矩阵

假定以上一层元素$C$为准则，所支配的下一层次的元素为$u_1,u_2,...,u_n$，我们的目的是要按照它们对于准则$C$的相对重要性赋于$u_1,...,u_n$相应的权重。

在赋于权重的这一步中，决策者需要反复回答问题：针对准则$C$，两个元素$u_i$和$u_j$哪一个更重要，重要多少，并按照表一比例标度对重要性程度赋值。

例如选择旅行目的地下支配的元素为景色与居住。如果认为景色比居住强烈重要，那么它们的重要性之比的标度应取为$7$，而居住与景色重要性的比例标度应取为$\frac{1}{7}$。这样对于准则$C$，$n$个被比较元素构成了一个两两比较判断矩阵：

$A=(a_{ij})_{n×n}$、

其中，$a_{ij}$就是元素$u_i$与$u_j$相对于$C$的重要性的比例标度。

显然判断矩阵具有下列性质：

$a_{ij}>0，a_{ij}a_{ji}=1，a_{ii}=1$

我们称这样的矩阵$A$为正互反矩阵。

特殊地，如果矩阵$A$中的所有元素具有传递性，即满足等式时：

$a_{ij}·a_{jk}=a_{ik}$

我们称矩阵$A$为一致性矩阵




标度
含义




1
表示两个元素相比，具有同样重要性


3
表示两个元素相比，前者比后者稍重要


5
表示两个元素相比，前者比后者明显重要


7
表示两个元素相比，前者比后者强烈重要


9
表示两个元素相比，前者比后者极端重要


2,4,6,8
表示上述相邻判断的中间值


倒数
若元素$i$和元素$j$的重要性之比为$a_{ij}$，那么元素$j$和元素$i$的重要性之比为$\frac{1}{a_{ij}}$


表一

3.由判断矩阵计算被比较元素对于该准则的相对权重并进行一致性检验

此部分分为两个部分：

（1）计算相对权重

事实上，计算相对权重有和法、根法、特征根方法、对数最小二乘法等方法，但考虑到特征根方法在层次分析法中具有特别重要的理论意义及使用价值，此处我们只介绍使用特征根方法计算相对权重。

记在准则$C$下得到的两两比较判断矩阵为$A$。而矩阵$A$的最大特征根为$\lambda_{max}$，对应的特征项为$\omega$，将$\omega$归一化[1]后即可作为相对权重向量。

补充知识：向量的归一化

记向量$\vec{\alpha}=(a_1,a_2,...,a_n)$，且$s=\sum_{i=1}^na_i$

则向量$\vec{\alpha'}=\frac{1}{s}\vec{\alpha}=(\frac{a_1}{s},...,\frac{a_n}{s})$即为向量$\vec{\alpha}$的归一化向量

（2）一致性检验

前面我们介绍了一致性矩阵的定义，但是在实际判断矩阵的构造中，我们并不要求判断矩阵一定要具有传递性（即一致性），这是由客观事物的复杂性与人的认识的多样性所决定的。但判断矩阵既然是我们计算相对权重向量的依据，那么我们要求判断矩阵具有大体上的一致性是应该的。

事实上，上面提到的权重向量的计算方法只是一种近似算法。当判断矩阵偏离一致性过大时，这种近似算法的可靠程度就值得怀疑了。从这个角度上来说，对判断矩阵进行一致性检验就显得十分必要了。

一致性检验的步骤如下：

$a.$计算一致性指标$C.I.(consistency\ index)$

$C.I.=\frac{\lambda_{max}-n}{n-1}$

$b.$查找相应的平均随机一致性指标$R.I.(random\ index)$

表二给出了$1-15$阶正互反矩阵计算$1000$次得到的平均随机一致性指标

$c.$计算一致性比例$C.R.(consistency\ ratio)$

$C.R.=\frac{C.I.}{R.I.}$

当$C.R.<0.1$时，认为判断矩阵的一致性是可以接受的。当$C.R.\geq 0.1$时应该对判断矩阵进行适当修正。对于一阶、二阶矩阵总是一致的，此时$C.R.=0$




矩阵阶数
1
2
3
4
5
6
7
8




$R.I.$
0
0
0.52
0.89
1.12
1.26
1.36
1.41






矩阵阶数
9
10
11
12
13
14
15




$R.I.$
1.46
1.49
1.52
1.54
1.56
1.58
1.59


表二

4.计算各层元素对系统目标的合成权重，并进行排序。

上面我们得到的仅仅是一组元素对其上一层中某元素的权重向量。我们最终要得到的是各元素对于总目标的相对权重，特别是要得到最底层中各方案对于目标的排序权重，即所谓的“合成权重”，从而进行方案选择。

事实上，我们还需要在进行权重合成时，逐层并在最后进行总的一致性检验。但是在实际应用中，整体一致性检验常常可以忽略（这也是为什么此处不介绍总的一致性检验）。事实上在考虑决策者在给出但准则下判断矩阵时，是难以对整体进行考虑的，当整体一致性不满足要求时，进行调整也比较困难，因此目前大多数实际工作都没有对整体一致性进行严格检验。其必要性有待于进一步探讨。

三、简单举例进行应用
以该背景为例：

想要去苏州、常州、南京三个地方游玩，但受限于预算时间等只能选择一个地方游玩，而选择的因素又包括风景、居住、饮食等，我们要在综合考虑这些因素的情况下选择最佳旅行目的地。

1.分析系统中各因素之间的关系，建立系统更多解题层次结构

图1表示这一背景的层次结构模型（此处只是简单的一层准则，之后再添加还有子准则的情况）

图一


2.对同一层次的各元素关于上一层次中某一准则的重要性进行两两比较，构造两两比较判断矩阵
此处即选择旅行目的地下支配的元素的两两比较判断矩阵
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ A=\begin{bmatrix} 1 & 7 & 5 & 9\\ \frac{1}{7} & 1 & 2& 2 \\  \frac{1}{5} & \frac{1}{2} & 1 & 1 \\  \frac{1}{9} & \frac{1}{2}& 1 & 1\end{bmatrix}$

3.由判断矩阵计算被比较元素对于该准则的相对权重并进行一致性检验

（1）计算相对权重：

由$A\omega=\lambda\omega$计算得最大特征值$\lambda_{max}=4.1017$

对应特征向量$\omega=(-0.9659 \ \ -0.1972\ \ -0.1289\ \ -0.1079)$

归一化得到权重向量$\omega'=(0.69\ \ 0.14\ \ 0.09\ \ 0.08)$

（2）一致性检验

$C.I.=\frac{4.1071-4}{4-1}=0.0339$

$R.I.=0.89$

$C.R.=\frac{0.0339}{0.89}≈0.038<0.1$，因此我们认为该判断矩阵的一致性是可以接受的。

4.计算各层元素对系统目标的合成权重，并进行排序。

由于此例子只存在单一准则，并不存在合成权重，因此第三步得到的唯一权重向量即可视为合成权重。

之后博主会在空闲时更新此文介绍多准则下的合成权重计算。
四、部分步骤的matlab实现
A=[];%这是某一个判断矩阵，记维度为n
[Omega,Lambda]=eig(A);%计算方阵A的特征向量和特征值
mx=-99999.99999;
id=0;%变量mx是为了找出最大特征值，id记录当前最大特征值对应的特征向量所在的位置
for i=1:n
    if(Lambda(i,i)>mx)
        mx=lambda(i,i);
        id=i;
    end
end
O=zeros(n,1);%建立n维向量记录归一化后的权重向量
sum=0;
for i=1:n
    sum=sum+Omega(i,id);
end
for i=1:n
    O(i,1)=Omega(i,id)/sum;
end%这两个循环是为了计算归一化后的特征向量，即权重向量

买电脑，不懂找个懂得一块去。自己买不懂，走这个过程，自己不熟，很痛苦，找一个会的，会的具备这个功能，你是一个对象，会的人是一个对象，面向会的人这个对象。买电脑找个事变简单了，从执行者变成了指挥者，这就是面向对象。面向对象时找对对象很重要。软件公司为什么招人去干活？老板懂技术自己干，面向过程。招几个人，面向对象。开发就变得很简单。面试官问什么是面向对象？是一种思想。能把复杂问题简单化，能使我们的角色发生转变，从执行者变成指挥者。最后举个例子，结合实际场景，其实面试官你就是用面向对象来思考问题的，公司有招人的需求，你需要找一些专业编程功能的人，使用我专业编程功能为公司创造价值。洗衣服，做饭，找个会洗衣服做饭的对象，事情就变简单了。去饭店吃饭，叫服务员，服务员记单子，服务员招厨师，厨师做。对象不单单指人，一切皆对象，万物皆对象。有对象拿来用，没对象就造一个对象。