二维dp——最长回文子串求解

题目

给你一个字符串s，找到s中最长的回文子串

思路

  • 对于一个字符串，如果它的长度为1，那么必定是回文串。

  • 考虑一般情况

如果一个字符串是回文串，那么去掉两端的字符一定也是回文串，比如ababa是回文，其中bab也是回文。那么可以设二维dp数组，dp[i][j]表示字符串从第i位到第j位是否构成回文串（i<=j）

那么，我们只需要填充这个二维表格，找到这个二维表格中“相距最远”的两个1（即代表最长的回文子串）

  • 考虑如何递推填充二位dp数组

首先考虑基本情况，所有回文子串可以看作由长度为1的子串（构成长度为奇数的回文串）和长度为2的子串（构成长度为偶数的回文子串）两种基本情况扩展来。所以有

dp[i][i] = 1; (i>=0 && i<str.size())
dp[i][i+1] = (str[i]==str[i+1]) ? 1 : 0; (i+1 < str.size())

这样就填充了表格的中间和上边一大部分

j 0 1 2 3 4
i a a a a a
0 a 1 1
1 a 1 1
2 a 1 1
3 a 1 1
4 a 1

此时考虑填充剩下的部分，由于i<=j，所以只需填充上三角部分对应的矩阵即可，并且，我们考虑了基本情况即子串长度为1和长度为2的情况，只需从长度为3考虑，即j起始位置应该是i+2，同时要保证i和j不越界(0<i<=j<str.size())

  • 考虑状态转移情况

如果str[i]==str[j]，那么从i到j构成的子串是否是回文串由去掉边界两个字符决定，即dp[i][j]==dp[i+1][j-1]，体现在表格上就是dp[i][j]左下角的元素。如果我们自上而下填充这个表格，会出现一个元素左下角元素未计算的情况，因此，考虑对i从下往上遍历，保证左下角元素存在（i从str.size()-2到0遍历）遍历行的同时，j从左向右遍历，填充一行向上，直到填充整个上三角。

j 0 1 2 3 4
i a a a a a
0 a 1 1 1 1 1
1 a 1 1 1 1
2 a 1 1 1
3 a 1 1
4 a 1
  • 计算最长回文子串

得到二维dp数组后，从中找每行相距最远的两个1即为对应回文子串的边界下标。找最长回文子串的代码，复杂度O（n^2）

string res;
for(int i = 0;i<str.size();i++)
{
    for(int j = i;j<str.size();j++)
    {
        if(dp[i][j]==1 && j-i+1>res.size()) 
        {
            res = str.substr(i，j-i+1);
        }
    }
}
return res;

代码

string longestPalindrome(string s) {
    if(s.size()==1) return s;
    int len = s.size();
    vector<vector<int> >dp(len，vector<int>(len，0));
    string res;
    //初始化边界
    for(int i = 0;i<len;i++)
    {
        dp[i][i] = 1;
        if(i+1<len && s[i]==s[i+1]) dp[i][i+1] = 1;
    }

    for(int i = len-1;i>=0;i--)
        for(int j = i+2;j<len;j++)
            if(s[i]==s[j]) dp[i][j] = dp[i+1][j-1];
        
    for(int i = 0;i<len;i++)
        for(int j = i;j<len;j++) 
            if(dp[i][j]==1 && j-i+1 > res.size()) res = s.substr(i，j-i+1);
    
    return res;
}

STL常见容器用法

vector

vector意为向量，可以理解为变长数组

  1. vector定义
#include<vector>
using namespace std;
vector<typename> name;

vector中存放的类型可以是基本数据类型char, int, double, struct，也可以是STL标准容器，例如vector, set, queue。如果typename也是一个STL容器，定义的时候需要在>>之间加空格，因为在C++11之前会被认为是右移运算符。

vector<int> name;
vector<double> name;
vector<vector<int> > name;
  1. vector元素的访问

(1) 通过下标访问

(2) 通过迭代器访问

迭代器类似指针, 定义

vector<typename>:: iterator it;

通过迭代器访问vector元素

#include<stdio.h>
#include<vector>
using namespace std;

vector<int> vi;
for(int i = 1;i<=5;i++)
{
    vi.push_back(i);
}

vector<int>:: iterator it = vi.begin();
for(int i = 0;i<vi.size();i++)
{
    printf("%d", *(it+i))
}
return 0;

begin()函数用于取vi元素的首地址，end()函数用于取尾元素的下一个地址

使用迭代器遍历的第二种方法

for(vector<int>:: iterator it=vi.begin();it!=vi.end();it++)
{
    cout<<*it<<endl;
}
  1. vector常用函数

(1) push_back() 向容器末尾添加一个元素

(2) pop_back() 删除容器末尾元素

(3) size() 范围容器内元素个数

(4) clear() 清空容器内元素

(5) insert(it, x) 向vector的任意迭代器it处插入一个元素x

(6) earse()

  • earse(it) 除迭代器it位置的元素

  • earse(first, last) 删除[first, last)区间内的元素

set

set意为集合，是一个内部自动去重和有序的容器

  1. 定义
#include<set>
using namespace std;

set<typename> name;
  1. set元素的访问

set只能通过迭代器访问，除了vector和string之外的STL容器都不能用*(it+N)访问

set<int> st;
st.insert(2);
st.insert(5);
st.insert(2);
st.insert(3);
set<int>:: iterator it;

for(it=st.begin();it!=st.end();it++)
{
    cout<<*it<<endl; //2 3 5自动去重和排序
}
  1. 常用函数

(1) insert(x) 把x插入容器，自动去重和排序，时间复杂度O(logN)

(2) find(value) 返回set中值为value的迭代器

(3) earse

  • earse(it) 删除迭代器对应的值

  • earse(value) 删除set中的value

  • earse(first, last) 删除[first, last)区间内的元素

(4) size() 返回set内元素的个数

(5) clear() 清空set元素

string

在C语言中，一般使用char str[]存放字符串，但是操作不方便，容易出错，为了编程者方便地对字符串进行操作，C++在STL中封装了string类型

  1. string定义
#include<string>
using namespace std;

string str; //定义，默认是""
string str = "abcd" //定义并初始化
  1. 访问string中的内容

(1) 通过下标访问

(2) 通过迭代器访问

for(string::iterator it = str.begin();it!=str.end();it++)
{
    cout<<*it<<endl;
}
  1. 常用函数

(1) operator += 字符串拼接运算符

(2) compare operator 比较规则是字典序

(3) size()/length() 返回字符串的长度

(4) insert()

  • insert(pos, string) 在pos位置插入字符串string
string str = "abcxyz", str2 = "opq";
str.insert(3, str2); //abcopqxyz
  • insert(it, it2, it3) it为源字符串的待插入位置，it2和it3为待插入字符串的首尾迭代器，表示[it2, it3)插入到it的位置
string str = "abcxyz", str2 = "opq";
str.insert(str.begin()+3, str2.begin(), str2.end());

(5) earse()

  • earse(it) 删除单个元素

  • earse(first, last) 删除区间[first, last)内的元素

(6) clear() 清空字符串内元素

(7) substr(pos, len) 返回字符串从pos位置起，长度为len的子串

string str = "Thank you for your smile.";
cout<<str.substr(0, 5); //Thank
cout<<str.substr(14, 4); //your
cout<<str.substr(19, 5); //smile

(8) string::npos 用于作为find函数失配时的返回值

(9) find()

  • find(str2) 如果str2是当前字符串的字串，返回出现的首位置，否则返回string::npos

  • find(str2, pos) 从当前字符串的pos位开始匹配str2，返回结果同上

(10) replace

  • replace(pos, len, str2) 把当前字符串从pos位置开始len长度的字串替换为str2

  • replace(it1, it2, str2) 把当前字符串位于迭代器[it1, it2)范围的字串替换为str2

map

map意为映射，可以将任何基本类型映射到任何基本类型，比如将string映射到int，或者将STL容器映射到STL容器

  1. map的定义
#include<map>
using namespace std;

map<typename1, typename2> mp;
map<string, int> mp2; //建字符串到整形的映射
map<set<int>, string> mp3; //建立set容器到字符串的映射
  1. map内元素的访问

(1) 通过下标访问

int main()
{
    map<char, int> mp;
    mp['c'] = 20;// 建立'c' -> 20
    mp['c'] = 30;// 建立'c' -> 30 (20被覆盖)
    printf("%d", mp['c']); //30
    return 0;
}

(2) 通过迭代器访问 通过it->first访问map的key, 通过it->second访问map的value

int main()
{
    map<char, int> mp;
    mp['m'] = 20;
    mp['r'] = 30;
    mp['a'] = 40;
    for(map<char, int>::iterator it=mp.begin();it!=mp.end();it++)
    {
        printf("%c, %d", it->first, it->second);
    }
}

map的key会按从小到大顺序排列，因为其内部也是基于红黑树实现的

  1. 常用函数

(1) find(key) 返回键为key的映射的迭代器

(2) earse()

  • earse(it) 删除迭代器it对应的键值对

  • earse(key) 删除键为key对应的元素

  • earse(first, last) 删除迭代器区间[first, last)内的键值对

(3) size() 返回map内键值对的数量

(4) clear() 清空map的元素

  1. map的使用场景

  • 需要建立字符或字符串与整数映射的题目

  • 判断大整数或其他数据类型是否存在的题目，可以把map当做布尔数组使用

注：map的键和值是唯一的，如果需要一个键对应多个值，需要用multimap，另外C++11中还增加了unordered_map，用散列替代红黑树，只做映射不做排序，速度更快

queue

queue意为队列，在STL中是一个先进先出的容器

  1. queue定义
#include<queue>
using namespace std;
queue<typename> q;
  1. queue内元素的访问

队列只允许元素先进先出，即插入操作发生在队尾，删除操作发生在队头。STL中通过front()访问队头元素, back()访问队尾元素

int main()
{
    queue<int> q;
    for(int i = 1;i<=5;i++)
    {
        q.push(i);
    }
    printf("%d, %d", q.front(), q.back());
}
  1. 常用函数

(1) push(x) x入队，插入队尾

(2) front(), back() 访问队头、队尾元素

(3) pop() 队头元素出队

(4) empty() 检测queue是否空，空返回true,不空返回false

(5) size() 返回queue内元素的个数

  1. 主要用途

实现BFS时，可以通过STL提供的queue,避免自己实现队列遇到错误情况，简化代码

注：使用front()和pop()前，必须用empty()判断队列是否空，队列不空才能pop和取元素

priority_queue

priority_queue意为优先队列，本质就是一个最大堆（默认）底层用堆实现。在优先队列中，队首元素一定是当前优先队列中优先级最高的那一个。

  1. 定义
#include<queue>
using namespace std;
priority_queue<typename> name;
  1. 元素访问

通过top()访问堆顶元素，也就是优先级最高的元素

int main()
{
    priority_queue<int> q;
    q.push(3);
    q.push(4);
    q.push(1);
    printf("%d", q.top()); //4
}
  1. 常用函数

(1) push(x) x入队

(2) top() 返回堆顶元素

(3) pop() 弹出堆顶元素

(4) empty() 检测队列是否空

(5) size() 返回队列内元素的个数

  1. priority_queue优先级设置

(1) 基本数据类型优先级设置
此处基本数据类型就是int, double, char等直接可用的数据类型，优先级队列对他们的设计原则是数字大的优先级高

priority_queue<int, vector<int>, less<int> > q;//数字越大优先级越高（降序）
priority_queue<double, vector<double>, greater<double> > q2;//数字越小优先级越高（升序）

(2) 结构体类型优先级设置

定义表示水果的结构体，包含水果名称和价格两个成员

struct fruit
{
    string name;
    int price;
};

希望水果价格高的优先级高，需要重载operator < 运算符

struct fruit
{
    string name;
    int price;
    friend bool operator < (fruit f1, fruit f2) {
        return f1.price < f2.price; //内部按水果价格排序
    }
};

int main()
{
    priority_queue<fruit> q;
    struct fruit f1, f2, f3;
    f1.name = "桃子";
    f1.price = 3;
    f2.name = "梨子";
    f2.price = 4;
    f3.name = "苹果";
    f3.price = 1;
    q.push(f1);
    q.push(f2);
    q.push(f3);
    cout<<q.top().name<<q.top().price<<endl; //梨子 4
}

stack

stack意为栈，是STL中一个后进先出的容器，插入和删除都在栈顶操作

  1. 定义
#include<stack>
using namespace std;
stack<typename> s;
  1. 栈内部元素的访问

由于栈本身是一种后进先出的数据结构，在STL中只能通过top()来访问栈顶元素

int main()
{
    stack<int> st;
    for(int i = 1;i<=5;i++)
    {
        st.push(i); // push顺序 1, 2, 3, 4, 5
    }
    printf("%d", st.top()); //5
    return 0;
}
  1. 常用函数

(1) push(x) x入栈

(2) top() 取栈顶元素

(3) pop() 弹出栈顶元素

(4) empty() 判断栈是否空

(5) size() 返回栈内元素个数

  1. 用途

stack用于模拟一些递归栈，用空间换取时间，避免递归层数过多导致的超时

pair

pair可看作内部有两个元素的结构体，且两个元素的类型可指定

struct pair
{
    typename1 first;
    typename2 second;
};
  1. pair定义
#include<map>
using namespace std;
pair<typename1, typename2> name;

如果想定义pair同时初始化，只需跟上一个小括号，里面填上两个待初始化的元素

pair<string, int> p("haha", 5);

如果想在代码中临时定义pair,两种方法：

  • 类型定义写在前面，后面用小括号
pair<string, int> p("haha", 5);
  • 使用自带的make_pair方法
make_pair("haha", 5);
  1. pair中元素的访问

pair中只有两个元素：first和second，按结构体方法去访问即可

int main()
{
    pair<string, int> p;
    p.first = "haha";
    p.second = 5;
    cout<<p.first<<p.second<<endl;
    p = make_pair("xixi", 55);
    cout<<p.first<<p.second<<endl;
    p = pair<string, int>("heihei", 5);
    cout<<p.first<<p.second<<endl;
    return 0;
}
  1. 用途

  • 用来代替二元结构体及其构造函数，节省编码时间

  • 作为map的键值对插入

int main()
{
    map<string, int> mp;
    mp.insert(make_pair("heihei", 5));
    mp.insert(make_pair("haha", 10));
    for(auto iterator it = mp.begin();it!=mp.end();it++)
    {
        cout<<it->first<<" "<<it->second<<endl; //haha 10 heihei 5
    }
}

Linux高级命令使用

ln(link, 连接文件)

  • windows中的快捷方式和指向的目标是两个独立文件

  • Linux中有两种连接文件：

    • 软链接（符号链接）等同于Windows里的快捷方式
    • 硬链接 增加源文件的引用计数，删除文件时，引用计数减一，当引用计数为0，源文件才会被真正删除

  • 创建软链接

ln -s src link->src
  • 创建硬链接
ln src link->src
  • ls -l查看文件类型：
    • ‘-’ 表示普通文件
    • ‘d’ 表示文件夹
    • ‘l’ 表示符号连接文件
    • ‘p’ 表示管道文件
    • ‘s’ 表示socket文件

man 查询手册

  • 查询命令
man 1 ls
  • 查询linux api
man 2 mkdir
  • 查询C库函数
man 3 stoi

vim 高级命令

  • 快速换行(命令模式+行号)
: 1 # 快速跳转到第一行
  • 删除连续多行
3dd # 删除从当前行开始的三行
  • 行复制粘贴
3yy # 复制从当前行开始的三行
p # 粘贴到下一行

rwx与权限表示

drwxr-xr-x : 10个字符， 第一个字符表示文件类型。剩下9个分成3组， 表示文件权限。

  • 前三个表示此文件属主对文件的权限

  • 中间三个表示此文件属主所在的组对文件的权限

  • 后三个表示其他用户对文件的权限

  • ‘r’ 代表可读4

  • ‘w’ 代表可写2

  • ‘x’ 代表可执行1

  • ‘-’ 代表空权限0

find 查找文件

知道文件名，但是不知道具体路径在哪

find /etc -name "interfaces"

grep 在文件中查找

想查找字符串出现在哪些文件的哪些行

grep -nr "字符串" *

uname 查看系统信息

uname -a

mount/umount 挂载

mount -t nfs -o nolock 192.168.1.141:/root/rootfs /mnt
umount /mnt

df/du 磁盘空间相关

df -h # 显示已挂载的分区列表
du -h # 列出文件或文件夹的大小
du -h "文件名" # 以G/M表示展示文件大小

用户管理

useradd username # 添加username 用户
userdel username # 删除username 用户
passwd username # 为username设置密码

权限管理 chmod/chown/chgrp

权限的数字表示法：

  • ‘r’ 可读 4
  • ‘w’ 可写 2
  • ‘x’ 可执行 1
  • ‘-’ 无权限 0

改权限的命令

chmod 755 文件名 # 改变文件权限（主权限/组权限/其他用户权限）
chmod +x  文件名 # 给文件增加可执行权限
chmod -x  文件名

改用户和组的命令

chown # 修改文件的用户
chgrp # 修改文件的组

网络配置

ifconfig eth0 192.168.1.13 # 设置ip地址
ifconfig eth0 up # 启动网卡
ifconfig eth0 down # 关闭网卡
ifup eth0
ifdown eth0
ifconfig eth0 192.168.1.13 netmask 255.255.255.0 # 同时设置ip和子网掩码

二叉树的遍历

刷题的时候遇到关于二叉树的基础题目，发现很多基础知识都遗忘了，赶紧又看了一遍巩固一下。用博客记录一下，以后多看看。

二叉树的定义

二叉树是一种常见的数据结构，其中每个节点，除了根节点以外，都有唯一一个父节点，每个节点都至多有两个孩子节点。

二叉树常用链式存储，在C语言中用结构体定义二叉树节点：

struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    TreeLinkNode(int x) :val(x)， left(NULL)， right(NULL) {
        
    }
};

定义的最后一行代码类似C++中构造函数的初始化列表的用法。可以看到每个二叉树节点都包含一个数据域和两个指向自己类型的指针域，存储了左右孩子节点的地址。

二叉树的构造

首先声明一点，任意序列构造二叉树是无法实现的，必须有一定约束。因为二叉树有两个分支，无法确定将新节点插在那个分支上。对于二叉搜索树和平衡二叉树都是特殊约束的二叉树，即插入元素的位置是确定的。

这里使用层序插入的方法构造二叉树，所谓层序插入，即从一组序列（向量）读取元素，按元素顺序依此插入的二叉树的每一层中，理论上构造出来的是一颗完全二叉树。

难点分析

考虑层序插入的场景，是不断取元素，不断填充每一层的叶子节点的过程，因此在第n+1层插入节点时，只从第n层的一个父节点插入，这个父节点插满了，需要找第n层的其他父节点。

因此：由于要把节点插入到每一层，因此需要保存之前插入到树中节点的指针，并且一个节点的左右孩子没有插满时，都要持有对该节点的访问权限，又是顺序读取元素，顺序插入，因此考虑队列的方法保存节点指针。

算法思路

  1. 插入一个节点，就把这个节点放入队列尾部（push_back）
  2. 每次插入节点时，从队列首部取一个元素（front），该元素是树中应该插入且未插满的元素，如果左孩子空，插左边，右孩子空，插右边
  3. 插完右边之后，这个节点就插满了，从队列头部弹出（pop_front）

代码实现


/**
 * @brief 层序遍历构建二叉树
 * 
 * @param array 
 * @return TreeLinkNode* 
 */
TreeLinkNode* levelOrderConstructTree(vector<int> array)
{
    if(array.size()==0) return NULL;
    deque<TreeLinkNode *> q;
    //保存根节点
    TreeLinkNode * root = (TreeLinkNode *)malloc(sizeof(TreeLinkNode));
    root->left=NULL;
    root->right=NULL;
    root->val=array[0];
    q.push_back(root);

    for(int i = 1;i<array.size();i++)
    {
        //构建叶节点
        TreeLinkNode * node = (TreeLinkNode *)malloc(sizeof(TreeLinkNode));
        node->left=NULL;
        node->right=NULL;
        node->val=array[i];

        q.push_back(node);
        
        TreeLinkNode* father = q.front();

        if(father->left==NULL)
        {
            father->left=node;
        }
        else
        {
            father->right=node;
            q.pop_front();
        }
    }
    return root;
}

二叉树的遍历

接下来的内容才是标题相关的内容。但是二叉树要遍历前提是有一颗二叉树。总的来说，二叉树的遍历有两种方式，一种是层序遍历，按每一层的叶节点访问。另一种是先序、中序、后序，按一定顺序访问这个链式存储结构。

先序遍历

首先介绍先序遍历，先序遍历是在遍历一颗树时，先访问根节点，再遍历左子树，左子树遍历完，遍历右子树，遍历每颗子树时也按照根节点，左子树，右子树的顺序进行访问。

递归实现

从先序遍历的定义可以看出，用递归进行实现非常容易，代码


/**
 * @brief 二叉树的先序遍历
 * 
 * @param root 
 */
void preOrderTraversal(TreeNode *root)
{
    if(root==NULL) return ;
    else
    {
        cout<<root->val<<" ";
        preOrderTraversal(root->left);
        preOrderTraversal(root->right);
    }
}

访问节点用打印实现

非递归实现

递归程序本质上使用递归栈实现的，因此手动构建栈也可以实现先序遍历。考虑先序遍历的过程，遇到一个节点，直接访问，然后向左子树延伸，直到左子树到头，这时候回到上一个节点，遍历右子树，因此需要一个栈保存节点的右孩子指针。先遇到的后访问，栈顶优先弹出的是最近的未访问过的右子树。

  • 程序思路如下：
  1. 遇到一个节点，不空就访问，并且把节点右指针压栈（push）
  2. 根节点向左子树延伸，直到节点的左孩子为空
  3. 从栈中弹出顶部元素（pop）作为访问节点
  • 代码实现：
void preOrderTraversal2(TreeNode *root)
{
    if(root ==NULL) return;
    else
    {
        stack<TreeNode*> s;
        
        while(root || !s.empty())
        {
            while(root)
            {
                cout<<root->val<<" ";
                s.push(root->right);
                root = root->left;          
            }
            
            //左边到头
            if(!s.empty())
            {
                //根节点切到右子树
                root = s.top();
                s.pop()
            }
        }    
    }    
}

中序遍历

与先序遍历类似，中序访问时，先访问左子树，再访问根节点，再访问右子树。访问每棵子树时也按照左子树、根节点、右子树的顺序进行。

递归实现

直接给出代码

void InOrderTraversal(TreeNode* root)
{
    
    if(root==NULL) return ;
    else
    {
        InOrderTraversal(root->left);
        cout<<root->val<<" ";
        InOrderTraversal(root->right);
    }
}

非递归实现

  • 思路：
  1. 遇到一个节点，先不访问，因为先要访问该节点的左子树，所以先把这个节点压栈（push），等会在访问
  2. 根节点向左子树延伸，直到左边空，沿路的左子树都被压入堆栈
  3. 从堆栈弹出栈顶元素（pop）是最近遇到的节点，访问之，然后根节点切换到该节点的右指针，访问右子树
  • 代码
void InOrderTraversal(TreeNode* root)
{
    if(root==NULL) return;
    else
    {
        stack<TreeNode*> s;
        while(root || !s.empty())
        {
            while(root)
            {
                s.push(root);
                root = root->left;    
            }
            //左边到头
            if(!s.empty())
            {
                root = s.top();
                s.pop();                
                cout<<root->val<<" ";                
                root = root->right;
            }            
        }    
    }    
}

后序遍历

后序遍历子树的访问顺序为，先递归访问左子树，再递归访问右子树，最后访问根节点

递归实现

void PostOrderTraversal(TreeNode* root)
{
    if(root == NULL) return ;
    else
    {
        PostOrderTraversal(root->left);
        PostOrderTraversal(root->right);
        cout<<root->val<<" ";
    }    
}

非递归实现

二维数组中的查找

题目描述

在一个二维数组array中（每个一维数组的长度相同），每一行从左至右递增，每一列从上至下递增。完成一个函数，输入这样一个二维数组和一个整数，判断数组中是否含有该整数。

输入：
[[1， 2， 8， 9]，
[2， 4， 9， 12]，
[4， 7， 10， 13]，
[6， 8， 11， 15]]

给定target=7，返回true.

给定target=3，返回false.

数据范围：矩阵长宽满足0<n，m<500，矩阵中的值满足0<val<10^9

解法：二维数组的二分查找

思路：这道题是要在二维有序数组中查找元素，在一维有序数组中查找元素常用二分查找提高效率，因此想尝试拓展到二维。二分查找是通过不断缩小查询范围，每次查找使得搜索空间减半从而提高查找效率的。

在一维二分查找中，常采用数组首尾元素当做查找边界，但是这道题不可以这样做。比如如果（begin0，begin1）左上元素当做首节点，（end0， end1）右下当做尾节点，中间元素（mid0， mid1）和target比较大小，从而确定begin、end变量如何调整。但是在这道题中，按主对角线方向，对于任意元素，其上方和左方元素都比自身小，而其右方和下方元素都比自身大，所以比较大小后无法得到确定的调整方向。

但是如果以副对角线方向选择节点，任意一元素，其左方元素比自身小，下方元素比自身大；其上方元素比自身小，右方元素比自身大，因此选定左下或右上元素作为起点，可以通过比较target大小确定行列的收缩（扩张）范围。如果选择右上元素作为起点，如果target<node，列减小，应该向左侧移动；如果target>node，行增加，应该向下方移动。

代码

bool Find(int target， vector<vector<int>> array)
{
    bool res = false;
    int shape0 = array.size();
    if (shape0 == 0)
        return false;
    int shape1 = array[0].size();
    if( shape1 == 0)
        return false;

    int row = 0;
    int col = shape1-1;

    while(row<shape0 && col>-1)
    {
        if(target == array[row][col])
            res = true;
        if(target < array[row][col])
        {
            row--;
        }
        if(target > array[row][col])
        {
            col++;
        }
    }
    return res;
}