算法小记

题目描述
剑指offer面试题38：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
题解
方法一：分治法
分治法：求一个规模为n的问题，先求左边规模大约为n/2的问题，再求右边规模大约为n/2的问题，然后合并左边和右边的解，从而求得最终解。经典例子就是归并排序，先对左半部分和右半部分数据分别进行排序，最后将左半部分和右半部分的数据进行归并，得到整个数据的排序结果。

void MergeSortCore(vector<int>&number,vector<int>&copy,int start,int end)
{
    if(start<end)
    {
        int mid=start+((end-start)>>1); //取得中间值
        MergeSort(number,copy,start,mid); //对左边数据排序
        MergeSort(number,copy,mid+1,end); //对右边数据排序
        Merge(number,copy,start,mid,end); //归并左半部分和右半部分   
    }
}

void Merge(vector<int>&number,vector<int>&copy,int start,int mid,int end)
{
    for(int i=start;i<=end;++i)
        copy[i]=number[i]; //先将元素复制到copy数组中
    int i=start,j=mid+1,k=start;
    while(i<=mid && j<=end)
    {
        if(copy[i]<copy[j])
            number[k++]=copy[i++];
        else
            number[k++]=copy[j++];
    }
    while(i<=mid)
        number[k++]=copy[i++]
    while(j<=end)
        number[k++]=copy[j++]
}

步骤：

求 pro(left, rigth) -> int
先求pro(left, (left+right)/2) -> lval
再求pro((left+right)/2 + 1, right) -> rval
merge(lval, rval) -> result
对于本题求二叉树的高度，我们可以先分别求出左子树和右子树的高度，那么二叉树的高度就是左右子树中高度较大者加1，同理对于左子树和右子树可以同样地求解。

求TreeDepth(TreeNode* pRoot)->int
先求 TreeDepth(pRoot->left) ->lval
再求TreeDepth(pRoot->right) ->rval
return max(lval, rval) + 1
代码

class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if (pRoot==nullptr) 
            return 0;
        int lval = TreeDepth(pRoot->left);
        int rval = TreeDepth(pRoot->right);
        return max(lval, rval) + 1;
    }
};

方法二 层次遍历
求最大深度，可用使用队列。因为要满足先进先出的特性。
1.初始化：一个队列queue<TreeNode>q，将根结点入队列q
2.如果队列不空进行如下操作：
3.弹出队头元素，保存为node，将node的左右非空孩子结点加入队列
4.继续第2步和第3步，直到队列为空。
*如果不需要确定当前遍历到了哪一层，模板如下**

void bfs(TreeNode *root)
{
    if(root==nullptr)
        return;    
    bool *visited = new bool[len]; //申请visited数组标示结点是否已经访问
    memset(visited,len,0);
    queue<TreeNode*>q;
    q.push(root);
    while(!q.empty())
    {
        TreeNode *node=q.frot();
        q.pop();
        for(遍历node结点所有相邻结点next)
        {
            if(next结点不为空且其还没有访问的话)
            {
                visited[next]=true;
                q.push(next);
            }
        }
    }
}

如果需要确定遍历到了哪一层，模板如下

void bfs(TreeNode *root) 
{
    if(root==nullptr)
        return;    
    int level = 0;
    bool *visited = new bool[len]; 
    memset(visited,len,0);
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int sz = pq.size(); //当前层中结点个数
        while (sz--) {
            TreeNode *node = q.front(); q.pop();
            for (遍历node所有的相邻节点next) {
                if (next结点不为空 && vis[nex] == 0) {
                    visited[next] = true;
                    q.push(next);
                }
            } // end for
        } // end inner while
        level++;
    } // end outer while
}

对于本题，直接套上第二个模板即可，代码如下

class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if (pRoot==nullptr) 
            return 0;
        queue<TreeNode*> q;
        q.push(pRoot);
        int leve1 = 0;
        while (!q.empty()) {
            int sz = q.size();
            while (sz--) {
                TreeNode *node = q.front(); q.pop();
                if (node->left!=nullptr) q.push(node->left);
                if (node->right!=nullptr) q.push(node->right);
            }
            leve1 += 1;
        }
        return level;
    }
};

题目描述
剑指offer上面试题45，输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
我们可以采用全排列+排序，贪心+排序这两种方法来解决
题解
方法一：全排列+排序（暴力方法）
假设n个整数的索引为[0...n-1]，如果我们对这n个索引进行全排列，然后再对每次全排列进行组织一下结果，选取最小的即为答案。比如[1,2,3]的全排列如下:
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] 六种
全排列的模板代码为：

void perm(int pos, vector<int> &num, vector<vector<int>> &all_result) {
    if (pos+1 == num.size()) {
        // 一次全排列的结果
        all_result.push_back(num);
        return;
    }
    for (int i = pos; i < num.size(); ++i) //依次将pos位置元素和后面的元素进行交换
    { 
        swap(num[pos], num[i]); //将第pos位置的元素依次和后面的元素交换
        perm(pos+1, num, all_result); //处理下一个位置pos+1
        swap(num[pos], num[i]); //将第pos位置的元素从后面的元素中换回来
    }
}
int main() {
    vector<int> num = {1, 2, 3};
    vector<vector<int>> all_result;
    perm(0, num, all_result);
}

然后将上述代码修改一下运用到本题上，如下：

void perm(int pos, vector<string>&str, string &ret)
{
    if (pos + 1 == str.size())
    {
        string tmp="";
        for (int j = 0; j < str.size(); ++j)
            tmp += str[j]; 
        if (tmp < ret)
            ret = tmp;
        return;
    }
    for (int i = pos; i < str.size(); ++i)
    {
        swap(str[i], str[pos]);
        perm(pos + 1, str, ret);
        swap(str[i], str[pos]);
    }
}
void PrintMinNumber2(vector<int>data)
{
    if (data.empty())
        return;
    vector<string>str;
    int len = 0;
    for (int i = 0; i < data.size(); ++i)
    {
        string tmp = to_string(data[i]);
        len += tmp.length();
        str.push_back(tmp);
    }
    string ret(len, '9');
    perm(0, str, ret);
    cout << ret << endl;
}
int main()
{
    int number[] = { 54,67,21,21 };
    vector<int>data(number, number + 4);
    int length = sizeof(number) / sizeof(number[0]);
    PrintMinNumber2(data);
    return 0;
}

方法二：贪心+自定义排序
显然第一种方法出现了太多无关的排列，我们需要一个最小的数，如果有两个字符串a，b，如果a+b<b+a，那么我们就希望a排在b的前面，因为a排在前面可以使结果更小，于是可以自定义排序规则，使得vector中字符串满足如上规则，那么最后的结果肯定是最小的。
算法步骤：
1.将vector<int>转化为vector<string>
2.自定义上述排序规则
3.整合结果即可
对于第二步的自定义排序规则，实现上可以使用仿函数，lambda表达式，函数指针等形式。
1.仿函数</string></int>

struct Com
{
    bool operator()(string a,string b)
    {
        return a+b<b+a;
    }
}；
sort(str.begin(),str.end(),Com()); //Com()为临时对象

2.lambda表达式

// 1. 匿名lambda表达式
sort(str.begin(), str.end(), [](string a, string b) {
     return a + b < b + a;
});
// 2.具名lambda表达式
auto lam = [](string a, string b) {
     return a + b < b + a;
 };
sort(str.begin(), str.end(), lam);

3.函数指针

static bool Com(string a,string b)
{
    return a+b<b+a;
}
sort(str.begin(),str.end(),Com);

最后的代码如下:

class Solution {
public:
    string PrintMinNumber(vector<int> nums) {
        vector<string> str;
        for (int val : nums) 
            str.push_back(to_string(val));
        sort(str.begin(), str.end(), [](string a, string b) {
            return a + b < b + a;
        });
        string ret = "";
        for (string s : str) 
            ret += s;
        return ret;
    }
};