剑指offer刷题笔记
因为剑指offer的题目比较简单，所以就做成合集了，刷一题更新一题。
1 二位数组中的查找
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
这个就很简单了，从最左下方开始找起，如果现在的元素比目标大就向上走，现在的元素比目标小就往右走。
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int i=array.size()-1;
int j = 0;
while( i >= 0 && j < array[0].size() ){
int cur_ele = array[i][j];
if( cur_ele == target ) return true;
else if( cur_ele < target ) j += 1;
else i -=1;
}
return false;
}
};
2 替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
这个其实也很简单，最要是我忘记了char* char a[]，的用法，现在基本上都用string了，所以要复习一下。
原理就是找到空格的位置，然后从后向前添加。
注意'\0'问题，char*最后一位是'\0'这个是循环的终止条件。
class Solution {
public:
void replaceSpace(char *str,int length) {
//遍历一边字符串找出空格的数量
if(str==NULL||length<0)
return ;
int i=0;
int oldnumber=0;//记录以前的长度
int replacenumber=0;//记录空格的数量
while(str[i]!='\0')
{
oldnumber++;
if(str[i]==' ')
{
replacenumber++;
}
i++;
}
int newlength=oldnumber+replacenumber*2;//插入后的长度
if(newlength>length)//如果计算后的长度大于总长度就无法插入
return ;
int pOldlength=oldnumber; //注意不要减一因为隐藏个‘\0’也要算里
int pNewlength=newlength;
while(pOldlength>=0&&pNewlength>pOldlength)//放字符
{
if(str[pOldlength]==' ') //碰到空格就替换
{
str[pNewlength--]='0';
str[pNewlength--]='2';
str[pNewlength--]='%';
}
else //不是空格就把pOldlength指向的字符装入pNewlength指向的位置
{
str[pNewlength--]=str[pOldlength];
}
pOldlength--; //不管是if还是elsr都要把pOldlength前移
}
}
};
3 从头到尾打印链表
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
这个就更简单了，直接看代码吧。其实这个有很多解决方案，有时间再更新其他解。比如说用stack，递归打印等。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> res;
vector<int> res1;
while(head != NULL){
res.push_back( head -> val);
head = head -> next;
}
// 反转
for(int i=res.size() -1 ; i>=0; i--){
res1.push_back(res[i]);
}
return res1;
}
};
4 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
重建二叉树基本思想就是在前序遍历中找root，然后在中序遍历中找左右子树。
pre = {1,2,4,7,3,5,6,8}
vin = {4,7,2,1,5,3,8,6}
第一次迭代：从pre中找起，1为根节点，然后在vin中找，1左边的都是它左子树的树，1右边的都是它右子树的树。
第二次迭代：这时候vin变为{4,7,2}从pre中找起，2为根节点，然后在vin中找，只有左子树，右子树返回NULL。
第三次迭代....
/**
* 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.empty() || vin.empty() ) return NULL;
else{
// 构造函数
TreeNode* root = new TreeNode(pre[0]);
int pos_root = 0;
for(int i=0; i<vin.size(); i++){
if( vin[i] == pre[0] ) {pos_root = i; break;}
}
// 分割二叉树的两个数组
vector<int> left_pre, right_pre, left_vin, right_vin;
for(int i=0; i<pos_root; i++){
left_pre.push_back(pre[i + 1]);
left_vin.push_back(vin[i]);
}
for( int i=pos_root + 1; i<vin.size(); i++){
right_pre.push_back(pre[i]);
right_vin.push_back(vin[i]);
}
root->left = reConstructBinaryTree(left_pre, left_vin);
root->right = reConstructBinaryTree(right_pre, right_vin);
return root;
}
}
};
5 用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
stack性质是先进后出，队列性质是先进先出。原理也很简单，两次先进后出不就是先进先出了。。。
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 res = stack2.top();
stack2.pop();
return res;
}
private:
stack<int> stack1;
stack<int> stack2;
};
6 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
这道题有点似曾相识的感觉，貌似在Leetcode里做过。用暴力的方法目测会超时，然后一般这种数组题目就是用分治法或者二分法做一下的样子。
先尝试二分法，二分法最主要就是找到二分的条件。
Array = { 3,4,5,6,7,8,9,10,1,2,3}
mid = ( left + right ) / 2
（1） mid > right, min在mid+1到right之间。
（2） mid < left, min在left到mid-1之间。
还需要注意一种情况，mid == right == left，因为无法判断最小值到底在哪一部分，所以只能暴力查找了。
要单独拿出来判断。
eg {0, 1, 1, 1, 1} 的两个旋转 {1，0， 1， 1，1} {1， 1， 1， 0， 1}
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]
else {
++left;
}
}
return rotateArray[left];
}
};
7 斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
递推式是 F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2，n∈N*）
直接递推会超时，所以采用了迭代求解的方法。
class Solution {
int helper(int product, int product_pre, const int& n, int cur_n){
if( n == 0 ) return 0;
if( n == 1 ) return 1;
int temp_product = product + product_pre;
if( cur_n == 1 ) temp_product = 1;
if( cur_n == n ){
return temp_product;
}
if( cur_n == 0 ) return helper(0, 0, n, cur_n + 1);
else return helper(temp_product, product, n, cur_n + 1);
}
public:
int Fibonacci(int n) {
return helper(0, 0, n, 0);
}
};
8 跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
问题可以从每个台阶n上来看，对于n来说，它只能够由n-2这个台阶跳两步到达，或者n-1这个台阶跳1步到达。也就说n这个台阶的种类取决于n-2这个台阶和n-1这个台阶的种类。
F(n)=F(n-1)+F(n-2)
class Solution {
public:
int jumpFloor(int number) {
if( number == 1 ) return 1;
if( number == 2 ) return 2;
return jumpFloor(number - 1) + jumpFloor(number - 2);
}
};
这个和上一题不是一样一样的么，为什么这道题直接用式子递推就不会超时？测试用例需要扩充。
9 变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路和上一题一模一样的。
F(n) = F(n-1)+F(n-2)+F(n-3)+...+F(1)
F(n-1) = F(n-2)+F(n-3)+F(n-4)+..+F(1)
下面的式子带入上面就有：
F(n)=2F(n-1)
class Solution {
public:
int jumpFloorII(int number) {
int n = number;
if( n == 1 ) return 1;
return 2 * jumpFloorII( n -1 );
}
};
10 矩形覆盖
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
其实我想自己画图的，但是没有找到合适的工具。
所以这里就盗图一下：
递推规律图解.png
就是说新加了一行之后，新的一行只有横着排一行或者竖着排两行两种排列形式。也就对应着F(n-1)和F(n-2)。所以问题又回到了斐波切纳数列上了。
class Solution {
public:
int rectCover(int number) {
if(number == 0 )return 0;
if(number == 1) return 1;
if(number == 2) return 2;
return (rectCover(number - 1) + rectCover(number - 2));
}
};
11 二进制中１的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
首先判断n是不是负数，当n为负数的时候，直接用后面的while循环会导致死循环，因为负数
向左移位的话最高位补1！ 因此需要一点点特殊操作，可以将最高位的符号位1变成0，也就
是n &0x7FFFFFFF，这样就把负数转化成正数了，唯一差别就是最高位由1变成0，因为少了
一个1，所以count加1。之后再按照while循环里处理正数的方法来操作就可以啦！
class Solution {
public:
int NumberOf1(int n) {
// 处理负数
int counter = 0;
if( n < 0 ){
n &= 0x7FFFFFFF;
counter ++;
}
while( n != 0 ){
counter += n & 1;
n = n >> 1;
}
return counter;
}
};
12数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
这里我偷懒了，写了个很简单的解，最后也通过了。这个系统令人匪夷所思。这个问题应该是用递归求解的，在leetcode里遇到过。
class Solution {
public:
double Power(double base, int exponent) {
double result = 1;
if( exponent < 0 ){
base = 1 / base;
exponent = abs(exponent);
}
for( int i = 0; i< exponent; i++){
result *= base;
}
return result;
}
};
13调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
这道题思想应该和插排差不多，但是我随便写了一个简单解，然后就通过了，于是我也没深究。
class Solution {
public:
void reOrderArray(vector<int> &array) {
vector<int> rec1;
vector<int> rec2;
for( auto i : array){
if( i % 2 == 0 ) rec2.push_back(i);
else rec1.push_back(i);
}
for( int i =0; i< array.size() ;i ++){
if( i < rec1.size() ) array[i] = rec1[i];
else array[i] = rec2[i-rec1.size()];
}
}
};
14 链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个结点。
典型的双指针问题，申明两个指针p1,p2，让p2先走k步，然后p1,p2一块走，p2走到末尾时候，p1指向的位置就是我们要求的解。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if(pListHead==NULL||k==0)
return NULL;
ListNode*pTail=pListHead,*pHead=pListHead;
for(int i=1;i<k;++i)
{
if(pHead->next!=NULL)
pHead=pHead->next;
else
return NULL;
}
while(pHead->next!=NULL)
{
pHead=pHead->next;
pTail=pTail->next;
}
return pTail;
}
};
