牛客网-剑指offer算法专栏
对算法题的一些记录。
JZ1：二维数组中查找
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
/* 思路
* 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，
* 因此从左下角开始查找，当要查找数字比左下角数字大时。右移
* 要查找数字比左下角数字小时，上移
*/
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int row = array.size();
int col = array[0].size();
int m = row-1, n = 0;
while(m>=0 && n < col){
if(target == array[m][n])return true;
else if(target > array[m][n])++n;
else --m;
}
return false;
}
};
循环判断的条件不使用无符号类型
JZ2：替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
/*
问题1：替换字符串，是在原来的字符串上做替换，还是新开辟一个字符串做替换！
问题2：在当前字符串替换，怎么替换才更有效率（不考虑java里现有的replace方法）。
``从前往后替换，后面的字符要不断往后移动，要多次移动，所以效率低下
``从后往前，先计算需要多少空间，然后从后往前移动，则每个字符只为移动一次，这样效率更高一点。
*/
class Solution {
public:
void replaceSpace(char *str,int length) {
int count=0;
for(int i=0;i<length;i++){
if(str[i]==' ')
count++;
}
for(int i=length-1;i>=0;i--){
if(str[i]!=' '){
str[i+2*count]=str[i];
}
else{
count--;
str[i+2*count]='%';
str[i+2*count+1]='2';
str[i+2*count+2]='0';
}
}
}
};
JZ3从尾到头打印链表
输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
思路1：利用栈先入后出的特性完成
思路2：保存数组，数组翻转
思路3：递归
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
stack<int> temp;
while(head != NULL){
temp.push(head->val);
head = head -> next;
}
vector<int> a;
while(!temp.empty()){
a.push_back(temp.top());
temp.pop();
}
return a;
}
};
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> a;
while(head != NULL){
a.push_back(head->val);
head = head -> next;
}
reverse(a.begin(), a.end());
return a;
}
};
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> a;
if(head != NULL){
a.insert(a.begin(), head->val);
if(head -> next != NULL){
vector<int> b = printListFromTailToHead(head -> next);
if(!b.empty())a.insert(a.begin(), b.begin(), b.end());
}
}
return a;
}
};
JZ4 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：因为是树的结构，一般都是用递归来实现。
用数学归纳法的思想就是，假设最后一步，就是root的左右子树都已经重建好了，那么我只要考虑将root的左右子树安上去即可。
根据前序遍历的性质，第一个元素必然就是root，那么下面的工作就是如何确定root的左右子树的范围。
根据中序遍历的性质，root元素前面都是root的左子树，后面都是root的右子树。那么我们只要找到中序遍历中root的位置，就可以确定好左右子树的范围。
正如上面所说，只需要将确定的左右子树安到root上即可。递归要注意出口，假设最后只有一个元素了，那么就要返回。
/**
* 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) {
int vinlen = vin.size();
if(!vinlen)return nullptr;
TreeNode *root = new TreeNode(pre[0]);
if(vinlen == 1)return root;
int gen = 0;
for(int i=0; i< vinlen; i++){
if(pre[0] == vin[i]){
gen = i;
break;
}
}
vector<int> pre_l, pre_r, vin_l, vin_r;
for(int i = 0; i < gen; i++){
vin_l.push_back(vin[i]);
pre_l.push_back(pre[i+1]);
}
for(int i = gen+1; i < vinlen; i++){
vin_r.push_back(vin[i]);
pre_r.push_back(pre[i]);
}
root -> left = reConstructBinaryTree(pre_l, vin_l);
root -> right = reConstructBinaryTree(pre_r, vin_r);
return root;
}
};
JZ5用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
用两个栈实现一个队列的功能:
入队：将元素进栈A
出队：
判断栈B是否为空，如果不为空，栈B直接出栈。
如果为空，则将栈A中所有元素pop，并push进栈B，栈B出栈；
用两个队列实现一个栈的功能:
入栈：将元素进队列A
出栈：判断队列A中元素的个数是否为1，如果等于1，则出队列，
否则将队列A中的元素出队列，并放入队列B，直到队列A中的元素留下一个，然后队列A出队列，再把队列B中的元素出队列以此放入队列A中。
class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
int res = 0;
if(!stack2.empty()){
res = stack2.top();
stack2.pop();
}
else{
while(stack1.size()){
int temp = stack1.top();
stack1.pop();
stack2.push(temp);
}
res = stack2.top();
stack2.pop();
}
return res;
}
private:
stack<int> stack1;
stack<int> stack2;
};
JZ6旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
思路：
（1）我们用两个指针left,right分别指向数组的第一个元素和最后一个元素。按照题目的旋转的规则，第一个元素应该是大于最后一个元素的（没有重复的元素）。
但是如果不是旋转，第一个元素肯定小于最后一个元素。
（2）找到数组的中间元素。
中间元素大于第一个元素，则中间元素位于前面的递增子数组，此时最小元素位于中间元素的后面。我们可以让第一个指针left指向中间元素。
移动之后，第一个指针仍然位于前面的递增数组中。
中间元素小于第一个元素，则中间元素位于后面的递增子数组，此时最小元素位于中间元素的前面。我们可以让第二个指针right指向中间元素。
移动之后，第二个指针仍然位于后面的递增数组中。
这样可以缩小寻找的范围。
（3）按照以上思路，第一个指针left总是指向前面递增数组的元素，第二个指针right总是指向后面递增的数组元素。
最终第一个指针将指向前面数组的最后一个元素，第二个指针指向后面数组中的第一个元素。
也就是说他们将指向两个相邻的元素，而第二个指针指向的刚好是最小的元素，这就是循环的结束条件。
//C++ 二分法
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if (rotateArray.empty()) return 0;
int left = 0, right = rotateArray.size() - 1;
while (left < right) {
//确认子数组是否是类似1,1,2,4,5,..,7的非递减数组
if (rotateArray[left] < rotateArray[right]) return rotateArray[left];
int mid = left + (right - left) / 2;
//如果左半数组为有序数组
if (rotateArray[left] < rotateArray[mid])
left = mid + 1;
//如果右半数组为有序数组
else if (rotateArray[mid] < rotateArray[right])
right = mid;
//否则，rotateArray[left] >= rotateArray[mid] >= rotateArray[right]
/*
例如： 5 4 3 2 1
应该为rotateArray[left] >= rotateArray[mid] >= rotateArray[right]
所以要++left，而不能是--right。
不然按照你的 rotateArray[left] == rotateArray[mid] == rotateArray[right] 话，--right也可行。
*/
else {
++left;
}
}
return rotateArray[left];
}
};
JZ7斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
n<=39
思路：
1. 常规算法
2. 动态规划
3. 矩阵快速幂
class Solution {
public:
int Fibonacci(int n) {
if(n == 0){
return 0;
}
if(n == 1){
return 1;
}
int a = 0,b = 1;
int m = 0;
for(int i = 2;i <= n;i++){
m = a + b;
a = b;
b = m;
}
return m;
}
};
// c++动态规划版
class Solution {
public:
int Fibonacci(int n) {
int f = 0, g = 1;
while(n-->0) {
g += f; //最后g是算到第n+1个
f = g - f; //通过g，算出第n个，算了第n+1个数，然后倒推
}
return f;
}
};
JZ48 不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
思路：位运算
1. 两个数异或：相当于每一位相加，而不考虑进位；
2. 两个数相与，并左移一位：相当于求得进位；
3. 将上述两步的结果相加
class Solution {
public:
int Add(int num1, int num2)
{
while(num2){
int temp = num1 ^ num2;
num2 = (num1 & num2) << 1;
num1 = temp;
}
return num1;
}
};
JZ
JZ
JZ
JZ
JZ
JZ
JZ
v
JZ
JZ
JZ
v
v