剑指offer 代码实现 C++
剑指Offer
1. 二维数组中的查找
// 每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序
// Solution: 从右上角或左下角开始查找，对比target大小可逐步排除整行/整列
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
bool flag = false;
int row = array.size();
if (row > 0) {
int col = array[0].size();
int i = 0, j = col-1;
while(i < row && j >= 0) {
if (array[i][j] == target) {
flag = true;
break;
} else if (array[i][j] > target)
j --;
else
i ++;
}
}
return flag;
}
};
2. 替换空格
// length 为字符串总容量
// Soluntion: 先统计有多少个blank，再从后向前赋值
// Attention: 1. 注意原始str空间不足的情况；2. 注意复制字符串末尾的'\0'
class Solution {
public:
void replaceSpace(char *str,int length) {
if (str == NULL && length <= 0) {
return;
}
int oriStrLen = 0;
int blankCount = 0;
for (int i = 0; str[i] != '\0'; i ++) {
if (' ' == str[i])
blankCount ++;
oriStrLen ++;
}
int newStrLen = oriStrLen + 2*blankCount;
if (newStrLen > length) {// 原始str空间不足
return;
}
int j = newStrLen;
for (int i = oriStrLen; i >= 0; i --) {
if (0 == blankCount)
break;
if (str[i] == ' ') {
str[j --] = '0';
str[j --] = '2';
str[j --] = '%';
blankCount --;
} else {
str[j --] = str[i];
}
}
}
};
3. 从尾到头打印链表
// 返回从尾部到头部的列表值序列，例如[1,2,3]
// Attention: 要求不改变输入数据
// Solution：（1）使用先入后出的栈；（2）使用递归，但在递归层太多时可能导致函数调用栈溢出
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
stack<int> vals;
ListNode* pNode = head;
while(pNode != NULL) {
vals.push(pNode->val);
pNode = pNode->next;
}
vector<int> res;
while(!vals.empty()) {
res.push_back(vals.top());
vals.pop();
}
return res;
}
};
4. 重建二叉树
// 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
// Solution:前序遍历第一个值为根节点，中序遍历左子树的值都在根节点值左侧，右子树值在右侧，然后递归构建树
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if (pre.size() == 0 || vin.size() == 0)
return NULL;
return construct(pre, 0, pre.size()-1, vin, 0, vin.size()-1);
}
TreeNode* construct(vector<int> pre, int preStart, int preEnd,
vector<int> vin, int vinStart, int vinEnd) {
// 开始位置大于结束位置，已经没有需要处理的元素
if (preStart > preEnd) {
return NULL;
}
// 找到根节点root，及中序遍历的root_index
int root = pre[preStart];
int root_vin_index = vinStart;
while (root_vin_index <= vinEnd && vin[root_vin_index] != root) {
root_vin_index ++;
}
// 如果在中序遍历中找不到root值，抛出异常
if (vin[root_vin_index] != root) {
printf("Invalid input.");
return NULL;
}
// 创建根节点并赋值
TreeNode* node = new TreeNode(root);
// 递归构建左子树，元素有left = root_vin_index - vinStart个
// 左子树前序遍历位置[preStart+1, preStart+left]
// 左子树中序遍历位置[vinStart, root_vin_index-1]
node->left = construct(pre, preStart+1, preStart+root_vin_index-vinStart,
vin, vinStart, root_vin_index-1);
// 递归构建右子树，元素有right = vinEnd - root_vin_index个
// 右子树前序遍历位置[preStart+left+1, preEnd]
// 右子树中序遍历位置[root_vin_index+1, vinEnd]
node->right = construct(pre, preStart+root_vin_index-vinStart+1, preEnd,
vin, root_vin_index+1, vinEnd);
return node;
}
};
5. 用两个栈实现队列
// Solution: 当stack2不为空时，弹出top()；当stack2为空时，将stack1中所有元素压入stack2，再弹出top().
// Tips：两个队列实现栈，相当于每次弹出队尾的元素
class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
}
if (stack2.empty()) {
printf("Queue is empty!");
return NULL;
}
int head = stack2.top();
stack2.pop();
return head;
}
private:
stack<int> stack1;
stack<int> stack2;
};
