剑指offer 1-6
1. 二维数组中的查找
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int s1 = array.size(), s2 = array[].size();
int i = s1 - , j = ;
while (i >= && j < s2) {
if (array[i][j] == target) {
return true;
}
else if (array[i][j] > target) {
i--;
}
else {
j++;
}
}
return false;
}
};
本题还可采用其他分治策略，后续补充。
2. 替换空格
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
分析：
插入元素如果从前向后插入的话需要O(n^2)的时间复杂度，考虑先把空格个数算出，然后从后向前复制。
代码：
class Solution {
public:
void replaceSpace(char *str,int length) {
int blankSz = ;
for (int i = ; i < length; ++i) {
if (str[i] == ' ') {
blankSz ++;
}
}
int i = length - , j = length + * blankSz - ;
while (i >= ) {
if (str[i] != ' ') {
str[j] = str[i];
j--;
i--;
} else {
str[j] = '';
str[j - ] = '';
str[j - ] = '%';
i--;
j -= ;
}
}
}
};
3. 从尾到头打印链表
输入一个链表，从尾到头打印链表每个节点的值
分析：
方法1：利用一个栈，把元素以此压栈，然后弹栈倒序输出；
方法2：利用递归（本质利用了系统的栈）
代码：
//方法1
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
stack<int> st;
vector<int> result;
while (head != nullptr) {
st.push(head -> val);
head = head -> next;
}
while (!st.empty()) {
result.push_back(st.top());
st.pop();
}
return result;
}
}; //方法2
class Solution {
private:
vector<int> result;
public:
vector<int> printListFromTailToHead(ListNode* head) {
if (head != nullptr) {
printListFromTailToHead(head -> next);
result.push_back(head -> val);
}
return result;
}
};
4. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
分析:
思路就是手动做二叉树恢复的思路，在中序遍历中找到根节点的位置，然后对左右子树各自递归。注意代码的写法，helper函数的参数设计（要传起始终止位置，不要拷贝vector）和传递（搞不清楚就举例子）即可。
代码：
class Solution {
private:
TreeNode* helper(const vector<int>& pre, int prevStart, int prevEnd, const vector<int>& vin, int vinStart, int vinEnd) {
if (prevStart == prevEnd) {
return nullptr;
}
if (prevEnd - prevStart == ) {
TreeNode* result = new TreeNode(pre[prevStart]);
return result;
}
int rootVal = pre[prevStart];
TreeNode* result = new TreeNode(rootVal);
int length = ;
for (int i = vinStart; i < vinEnd; ++i) {
if (vin[i] != rootVal) {
length++;
}
else {
break;
}
}
result -> left = helper(pre, prevStart + , prevStart + length + , vin, vinStart, vinStart + length);
result -> right = helper(pre, prevStart + length + , prevEnd, vin, vinStart + length + , vinEnd);
return result;
}
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
TreeNode* result = helper(pre, , pre.size(), vin, , vin.size());
return result;
}
};
5. 用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
分析：
思路1 stack1用来push, stack2用来pop()，每次pop()完把数据倒回到stack1中，保证满足队列顺序，但效率比较低；
思路2 stack1用来push, stack2用来pop(), 每次pop()前判定stack2是否为空，如果为空则将stack1中元素均倒入stack2，然后再在stack2中pop(),不空直接pop()stack2
代码：
//方法1
class Solution
{
public:
void push(int node) {
stack1.push(node);
} int pop() {
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
int result = stack2.top();
stack2.pop();
while (!stack2.empty()) {
stack1.push(stack2.top());
stack2.pop();
}
return result; } private:
stack<int> stack1;
stack<int> stack2;
}; //方法2
class Solution
{
public:
void push(int node) {
stack1.push(node);
} int pop() {
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
}
int result = stack2.top();
stack2.pop();
return result; } private:
stack<int> stack1;
stack<int> stack2;
};
6. 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
分析：
思路1 二分搜索，用套路写就行，注意的是，其实由于更新start的条件只能在array[mid] > target时，start = mid，所以出循环后array[start]肯定不是解，可以不加那个判断；
思路2 可以用递归，注意分开两个区间的时候，有可能一个区间是非旋转的，所以递归终止条件是
if (rotateArray[] <= rotateArray[n - ]) {
return rotateArray[];
}
可以同时处理两种情况。
代码：
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
int start = , end = rotateArray.size() - ;
while (start + < end) {
int mid = start + (end - start) / ;
if (rotateArray[mid] == rotateArray[]) {
start = mid;
}
else if (rotateArray[mid] < rotateArray[]) {
end = mid;
}
else {
start = mid;
}
}
return rotateArray[end];
}
};
最新文章
- bzoj1396: 识别子串
- maven学习讲解
- linux下proc里关于磁盘性能的参数
- centos下cmake安装
- 中国海洋大学第四届朗讯杯高级组 I Cuckoo for Hashing
- MysqlHelp
- What’s New in Python 2.7 — Python 3.4.0b2 documentation
- hdu3579 Hello Kiki（数论）
- 优先队列的二叉堆Java实现
- Angular4.0入门
- c# List列表数据转换成树形结构
- onenote使用教程
- zabbix监控实战<1>
- 冲刺博客NO.9
- 通过 CLI 管理 Jenkins Server
- c# ThreadPool 判断子线程全部执行完毕的四种方法
- php-------代码加密的几种方法
- 【转】每天一个linux命令（5）：rm 命令
- 关于php上传文件过大的表单回填
- c#并行扫描端口控制台程序