题目五十一
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
思路：递归判断其左右树即可
class Solution {
public:
bool isSymmetrical(TreeNode* pRoot)
{
return isSymmetrical(pRoot,pRoot);
}
bool isSymmetrical(TreeNode* pRoot1,TreeNode* pRoot2){
if (pRoot1 == nullptr && pRoot2 == nullptr){
return true;
}
if (pRoot1 == nullptr || pRoot2 == nullptr){
return false;
}
if (pRoot1->val != pRoot2->val){
return false;
}
return isSymmetrical(pRoot1->left,pRoot2->right)&&isSymmetrical(pRoot2->left,pRoot1->right);
}
};
题目五十二
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
思路：利用两个栈来实现此功能。奇数行从左到右打印，偶数行从右到左打印，因此在打印奇数行（比如第一行）的时候，要将下一层（第二行）从右到左加入数组，同时将下一行的数字从右到左加入栈中，这样pop的时候我们就会先pop左节点，这时就可以将第三行的数据从左到右加入数组。
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int> >result;
if (pRoot == nullptr){
return result;
}
stack<TreeNode *>stackL;
stack<TreeNode *>stackR;
TreeNode *popNode;
//先将第一层加入
vector<int>temp;
temp.push_back(pRoot->val);
result.push_back(temp);
temp.clear();
//根节点在第一层奇数层，加入stackL
stackL.push(pRoot);
while(!stackL.empty()||!stackR.empty()){
while(!stackL.empty()){
popNode = stackL.top();
stackL.pop();
if (popNode->right){
temp.push_back(popNode->right->val);
stackR.push(popNode->right);
}
if (popNode->left){
temp.push_back(popNode->left->val);
stackR.push(popNode->left);
}
}
if (!temp.empty()){
result.push_back(temp);
temp.clear();
}
while(!stackR.empty()){
popNode = stackR.top();
stackR.pop();
if (popNode->left){
temp.push_back(popNode->left->val);
stackL.push(popNode->left);
}
if (popNode->right){
temp.push_back(popNode->right->val);
stackL.push(popNode->right);
}
}
if (!temp.empty()){
result.push_back(temp);
temp.clear();
}
}
return result;
}
题目四十三
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
思路：之字形打印可以借用栈，这种分行打印借助队列即可
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int> >result;
if (pRoot == nullptr){
return result;
}
queue<TreeNode *>que;
TreeNode *frontNode;
que.push(pRoot);
while(!que.empty()){
int size = que.size();
vector<int>temp;
while(size--){
frontNode = que.front();
temp.push_back(frontNode->val);
if (frontNode->left){
que.push(frontNode->left);
}
if (frontNode->right){
que.push(frontNode->right);
}
que.pop();
}
result.push_back(temp);
}
return result;
}
题目四十四
请实现两个函数，分别用来序列化和反序列化二叉树
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
class Solution {
public:
vector<int> buffer;
char* Serialize(TreeNode *root) {
buffer.clear();
df1(root);
int size = buffer.size();
int *res = new int[size];
for (int i = 0;i<size;i++){
res[i] = buffer[i];
}
return (char *)res;
}
TreeNode* Deserialize(char *str) {
int *p = (int *)str;
return df2(p);
}
void df1(TreeNode *root){
if (root == nullptr){
buffer.push_back(0xFFFFFFFF);
}else{
buffer.push_back(root->val);
df1(root->left);
df1(root->right);
}
}
TreeNode *df2(int *&p){
if (*p == 0xFFFFFFFF){
p++;
return nullptr;
}else{
TreeNode *res = new TreeNode(*p);
p++;
res->left = df2(p);
res->right = df2(p);
return res;
}
}
};
题目四十五
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
思路：考虑用最大堆最小堆来做
class Solution {
public:
void Insert(int num)
{
int len = max.size() + min.size();
//偶数，将值插入最大堆
if ((len & 1) == 0){
//如果这个数小于最大堆的最大数，则将最大堆中的最大值插入到最小堆中
if (!max.empty() && num < max[0]){
max.push_back(num);
push_heap(max.begin(),max.end(),less<int>());
num = max[0];
push_heap(max.begin(),max.end(),less<int>());
max.pop_back();//弹出末尾元素
}
min.push_back(num);
push_heap(min.begin(),min.end(),greater<int>());
}else{
//当前数据总数为奇数，插入最小堆，如果这个数大于最小堆的最小数字，则将最小数加入最大堆中
if(!min.empty() && num > min[0]){
min.push_back(num);
push_heap(min.begin(),min.end(),greater<int>());
num = min[0];
pop_heap(min.begin(),min.end(),greater<int>());
min.pop_back();
}
max.push_back(num);
push_heap(max.begin(),max.end(),less<int>());
}
}
double GetMedian()
{
int len = max.size() + min.size();
double res;
if ((len & 1) == 0){
//切记要除以2.0
res = (max[0] + min[0])/2.0;
}else{
res = min[0];
}
return res;
}
private:
//使用数组模拟最大堆最小堆，保证最小堆的最小的数大于最大堆的最大数
//这样取中位数的时候直接根据奇偶来取堆的头部即可
//最大堆存比较小的数，从大到小排列
vector<int> max;
//最小堆存比较大的数，从小到大排列
vector<int> min;
};
题目四十六
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
思路：循环遍历即可
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
vector<int> res;
if (num.empty()||size<=0||size>num.size()){
return res;
}
for (int i = 0;i<num.size()-size+1;i++){
int max = num[i];
for (int j = i;j < i + size;j++){
if (num[j] > max){
max = num[j];
}
}
res.push_back(max);
}
return res;
}
题目四十七
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如
a b c e
s f c s
a d e e
矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
思路：我们可以借助一个布尔值矩阵，与题目给出的矩阵大小相同，来判断是否途径了某个位置，如果经过了则设置为true，如果途径之后与string不符，则需要退回上一格将布尔值矩阵相应位置设置为false
class Solution {
public:
bool hasPath(char* matrix, int rows, int cols, char* str)
{
if (matrix == nullptr||rows <= 0 || cols <= 0||str == nullptr){
return false;
}
bool *visited = new bool[rows*cols];
memset(visited,0,rows*cols);
int pathlength = 0;
for (int row = 0;row<rows;row++){
for (int col = 0;col < cols;col++){
if (hasPathCore(matrix,rows,cols,str,row,col,visited,pathlength)){
return true;
}
}
}
return false;
}
bool hasPathCore(char* matrix, int rows, int cols, char* str,int row,int col,bool *visited,int &pathLength){
if (str[pathLength] == '\0'){
return true;
}
bool haspath = false;
if (row < rows&&row >= 0 && col >=0 && col < cols&&matrix[row*cols+col] == str[pathLength]&&!visited[row*cols+col]){
pathLength++;
visited[row*cols+col] = true;
haspath = hasPathCore(matrix,rows,cols,str,row-1,col,visited,pathLength)||hasPathCore(matrix,rows,cols,str,row+1,col,visited,pathLength)||hasPathCore(matrix,rows,cols,str,row,col-1,visited,pathLength)||hasPathCore(matrix,rows,cols,str,row,col+1,visited,pathLength);
if (!haspath){
pathLength--;
visited[row*cols+col] = false;
}
}
return haspath;
}
};
题目四十八
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
思路：这道题和上一题基本一样，唯独多了一个数字的处理。
class Solution {
public:
int movingCount(int threshold, int rows, int cols)
{
if (threshold < 0||rows<=0||cols<=0){
return 0;
}
bool *visited = new bool[rows*cols];
memset(visited,0,rows*cols);
int count = movingCore(threshold,rows,cols,0,0,visited);
return count;
}
int movingCore(int threshold, int rows, int cols,int col,int row,bool *visited){
int count = 0;
if (row >=0 && row<rows && col >=0 && col < cols &&getDig(row)+getDig(col) <= threshold&&!visited[row*cols+col]){
visited[row*cols+col] = true;
count = 1+movingCore(threshold,rows,cols,col,row+1,visited)+movingCore(threshold,rows,cols,col,row-1,visited)+movingCore(threshold,rows,cols,col-1,row,visited)+movingCore(threshold,rows,cols,col+1,row,visited);
}
return count;
}
int getDig(int number){
int sum = 0;
while(number){
sum+=number%10;
number/=10;
}
return sum;
}
};
题目四十九
给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
思路：求一根绳子的最大乘积，那么我们可以把问题分割，比如我们把绳子分成a，b，c三段，那么我们就要知道a，b，c它们分割可构成的最大乘积是多少，得出它们的最大乘积再求整个绳子的最大乘积。
int cutRope(int number) {
if (number < 2){
return 0;
}
if (number == 2){
return 1;
}
if (number == 3){
return 2;
}
//当绳子长度小于4的时候不分割才最大
int *products = new int[number+1];
products[0] = 0;
products[1] = 1;
products[2] = 2;
products[3] = 3;
for (int i = 4;i <= number;i++){
int max = 0;
for (int j = 1;j<=i/2;j++){
int product = products[j]*products[i-j];
if (product > max){
max = product;
}
}
products[i] = max;
}
return products[number];
}
网友评论