剑指offer.C++.code61-67
2018-03-29 本文已影响0人
小异_Summer
61. 把二叉树打印成多行
- 从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
// Solution:广度优先遍历，使用队列
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>> res;
if (pRoot == NULL)
return res;
vector<int> one_level;
queue<TreeNode *> nodes;
nodes.push(pRoot);
int nextLevelToPrint = 0;
int toBePrinted = 1;
while (!nodes.empty()) {
TreeNode * pNode = nodes.front();
if (pNode->left != NULL) {
nodes.push(pNode->left);
nextLevelToPrint ++;
}
if (pNode->right != NULL) {
nodes.push(pNode->right);
nextLevelToPrint ++;
}
nodes.pop();
one_level.push_back(pNode->val);
toBePrinted --;
if (toBePrinted == 0) {
res.push_back(one_level);
one_level.clear();
toBePrinted = nextLevelToPrint;
nextLevelToPrint = 0;
}
}
return res;
}
};
62. 序列化二叉树【没有理解透彻】
- 请实现两个函数，分别用来序列化和反序列化二叉树
// Solution:流中读取，记录NULL
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
char* Serialize(TreeNode *root) {
if (root == NULL)
return NULL;
string str;
Serialize(root, str);
char* res = new char[str.length()+1];
int i;
for (i = 0; i < str.length(); i ++)
res[i] = str[i];
res[i] = '\0';
return res;
}
void Serialize(TreeNode *root, string& str) {
if (root == NULL) {
str += '#';
return;
}
str += to_string(root->val);
str += ',';
Serialize(root->left, str);
Serialize(root->right, str);
}
TreeNode * Deserialize(char *str) {
if (str == NULL)
return NULL;
TreeNode * root = Deserialize(&str);
return root;
}
TreeNode * Deserialize(char **str) {
if (**str == '#') {
(*str) ++;
return NULL;
}
int num = 0;
while (**str != '\0' && **str != ',') {
num = num * 10 + ((**str)-'0');
(*str) ++;
}
TreeNode * root = new TreeNode(num);
if (**str == '\0')
return root;
else
(*str) ++;
root->left = Deserialize(str);
root->right = Deserialize(str);
return root;
}
};
63. 二叉搜索树的第k个结点
- 给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。
//Solution:中序遍历，结点值递增
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
TreeNode* KthNodeCore(TreeNode* pRoot, int& k) {
TreeNode* target = NULL;
if (pRoot->left != NULL)
target = KthNodeCore(pRoot->left, k);
if (target == NULL) {
if (k == 1)
target = pRoot;
k --;
}
if (target == NULL && pRoot->right != NULL)
target = KthNodeCore(pRoot->right, k);
return target;
}
TreeNode* KthNode(TreeNode* pRoot, int k)
{
if (pRoot == NULL || k == 0)
return NULL;
return KthNodeCore(pRoot, k);
}
};
64. 流数据中的中位数
- 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
// Solution:使用最大堆、最小堆保存中位数相关的两个数
class Solution {
private:
vector<int> min;
vector<int> max;
public:
void Insert(int num)
{
int size = min.size() + max.size();
if ((size & 1) == 0) { // 第奇数个值，放入最小堆中
if (max.size() > 0 && num < max[0]) { // 数字小于最大堆中最大值，需要保证最大堆中的值都小于最小堆中的值
max.push_back(num);
push_heap(max.begin(), max.end(), less<int>());
num = max[0];
pop_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.size() > 0 && 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 size = max.size() + min.size();
if (size == 0)
return 0;
double res = 0;
if (size & 1 == 1) // 奇数个数字
res = min[0];
else // 偶数个数字
res = (min[0] + max[0]) / 2.0;
return res;
}
};
65. 滑动窗口的最大值
- 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。
// Solution:使用双向队列，保存size大小的窗口中中最大值index
class Solution {
public:
vector<int> res;
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
if (num.size() >= size && size >= 1) {
deque<int> index;
for (int i = 0; i < size; i ++) {
while (!index.empty() && num[i] >= num[index.back()])
index.pop_back();
index.push_back(i);
}
for (int i = size; i < num.size(); i ++) { //从index = size开始
res.push_back(num[index.front()]);
while (!index.empty() && num[i] >= num[index.back()])
index.pop_back();
if (!index.empty() && index.front() <= (i - size))
index.pop_front();
index.push_back(i);
}
res.push_back(num[index.front()]);
}
return res;
}
};
66. 矩阵中的路径【回溯法】
- 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
//Solution:回溯法，同时标记已走过的路
class Solution {
public:
bool hasPath(char* matrix, int rows, int cols, char* str)
{
if (matrix == NULL || rows < 1 || cols < 1 || str == NULL)
return false;
bool *visited = new bool[rows*cols];
memset(visited, 0, rows*cols);
int pathLength = 0;
for (int i = 0; i < rows; i ++) {
for (int j = 0; j < cols; j ++) {
if (hasPathCore(matrix, rows, cols, i, j, str, pathLength, visited)) {
return true;
}
}
}
delete [] visited;
return false;
}
bool hasPathCore(char* matrix, int rows, int cols, int row, int col, char* str,
int pathLength, bool * visited) {
if (str[pathLength] == '\0')
return true;
bool hasPath = false;
if (row >= 0 && row < rows && col >= 0 && col < cols &&
matrix[row * cols + col] == str[pathLength] &&
visited[row * cols + col] == false) {
pathLength ++;
visited[row * cols + col] = true;
hasPath = hasPathCore(matrix, rows, cols, row, col-1, str, pathLength, visited) ||
hasPathCore(matrix, rows, cols, row-1, col, str, pathLength, visited) ||
hasPathCore(matrix, rows, cols, row, col+1, str, pathLength, visited) ||
hasPathCore(matrix, rows, cols, row+1, col, str, pathLength, visited);
if (!hasPath) {
pathLength --;
visited[row * cols + col] = false;
}
}
return hasPath;
}
};
67. 机器人的运动范围【回溯法】
- 地上有一个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)
{
bool * visited = new bool[rows * cols];
for (int i = 0; i < rows * cols; i ++)
visited[i] = false;
int count = movingCountCore(threshold, rows, cols, 0, 0, visited);
delete [] visited;
return count;
}
int movingCountCore(int threshold, int rows, int cols, int row, int col, bool * visited) {
int count = 0;
if (check(threshold, rows, cols, row, col, visited)) {
visited[row * cols + col] = true;
count = 1 + movingCountCore(threshold, rows, cols, row, col-1, visited)
+ movingCountCore(threshold, rows, cols, row-1, col, visited)
+ movingCountCore(threshold, rows, cols, row, col+1, visited)
+ movingCountCore(threshold, rows, cols, row+1, col, visited);
}
return count;
}
bool check(int threshold, int rows, int cols, int row, int col, bool* visited){
if (row >= 0 && row < rows && col >= 0 && col < cols &&
!visited[row * cols + col] &&
getDigitSum(row) + getDigitSum(col) <= threshold)
return true;
return false;
}
int getDigitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
};
