题目描述
剑指offer面试题38：输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
题解
方法一：分治法
分治法：求一个规模为n的问题，先求左边规模大约为n/2的问题，再求右边规模大约为n/2的问题，然后合并左边和右边的解，从而求得最终解。经典例子就是归并排序，先对左半部分和右半部分数据分别进行排序，最后将左半部分和右半部分的数据进行归并，得到整个数据的排序结果。
void MergeSortCore(vector<int>&number,vector<int>©,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>©,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;
}
};
京公网安备 11010502036488号