剑指offer|

发表于

1 剑指offer书本
2 oj提交牛客网剑指offer
3 题解参考：https://github.com/zhedahht/CodingInterviewChinese2
http://blog.csdn.net/Together_CZ/article/details/74906427
http://blog.csdn.net/panda_AJ/article/details/69420293

1、二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
思路：从右上角判断是否与查找数字相等，如果大于这个数字证明比这一行的数字都大，可以剔除这一行，如果小于这个数字，证明比这一列的数字都小，可以剔除这一列
注意：边界问题，与行列剔除的增加减小
*/
class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
    if(array.empty())   return false;
	int i=0;
    int is=array.size();
	int j=array[0].size()-1;
	while(j>=0&&i<is)
	{
        if(target==array[i][j])   return true;
		else if(target<array[i][j])    j--;//比右上角的数字小，证明比这一列的数字小  
		else i++;//比右上角的数字大，证明比这一行的数字大 	
	}
	return false;
    }
};

2、替换空格

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
思路：两种思路：1、只能在本数组上进行展开：先计算空格的个数，再向后拓展空格2倍的空格长度。
				2、可以利用新空间，新开一个数组，一个个移动。
注意: 容错机制，字符串可能是空指针
 */
class Solution {
public:
	void replaceSpace(char *str,int length) {
	if(str==NULL||length<=0)   return ;
	int spaceCount=0;
	for(int i=0;i<length;i++)
	{
		if(str[i]==' ')    spaceCount++;//统计空格的数量 
	}
	if(spaceCount==0)   return ;
	length--;
	int newLength=2*spaceCount+length;//向后拓展空格个数*2
	
	while(newLength>=0&&length>=0)//从后向前循环查询
	{
		if(str[length]==' ')//如果是空格就填字母 
		{
			str[newLength--]='0';
			str[newLength--]='2';
			str[newLength--]='%';
		}else
		{//如果不是空格就移动char 
			str[newLength--]=str[length];	
		}
		length--;
	}
    }
};

3、从头到尾打印链表

输入一个链表，从尾到头打印链表每个节点的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
/*
思路1：使用了stl函数reverse，直接遍历一遍然后输出
 */
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
		vector<int> print;
        if(head==NULL)   return print;
		ListNode* pNode=head;
		while(pNode)
		{
			print.push_back(pNode->val);
			pNode=pNode->next;
		}
        reverse(print.begin(),print.end());
		return print;
    }
};

/*
思路2： 借用栈的先进后出自然的倒置过来。
思路3： 栈与递归相同，也可用递归来做，不过递归要考虑内存栈深度。
 */
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> reverse_list;
        stack<int> nodes;

        ListNode *p_node = head;
        while(p_node != nullptr)
        {
            nodes.push(p_node->val);
            p_node = p_node->next;
        }

        int tempVal;
        while(!nodes.empty())
        {
            tempVal = nodes.top();
            reverse_list.push_back(tempVal);
            nodes.pop();
        }
        return reverse_list;
    }
};

4、重建二叉树 **

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * 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() || pre.size()!=vin.size())
            return nullptr;

        vector<int> left_pre, right_pre, left_vin, right_vin;
        TreeNode *node = new TreeNode(pre[0]);

        int left_length = 0;
        while(pre[0]!=vin[left_length] && left_length < pre.size())
            ++ left_length;

        for(int i=0; i<left_length; i++)
        {
            left_pre.push_back(pre[i+1]);
            left_vin.push_back(vin[i]);
        }

        for(int i=left_length+1; i<pre.size(); i++)
        {
            right_pre.push_back(pre[i]);
            right_vin.push_back(vin[i]);
        }
        node->left = reConstructBinaryTree(left_pre, left_vin);
        node->right = reConstructBinaryTree(right_pre, right_vin);

        return node;
    }
};

5、两个栈实现队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
思路：先进后出->先进先出，不过要考虑的是什么时候需要进行栈传递转换。
 */
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()){
			throw new exception("queue is empty");
		}else {
			int x=stack2.top();
			stack2.pop();
			return x;
    	}
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

6、旋转数组最小的数字 **

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*
思路1：直接遍历一遍，对比到递减时就是最小值，特殊情况没旋转
 */
 */
class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.empty())    return 0;
        int i=0;
        for(i=0;i<rotateArray.size()-1;i++)
        {
            if(rotateArray[i]>rotateArray[i+1])
            	return rotateArray[i+1];
		}
        if(i==rotateArray.size()-1)    return rotateArray[0];
    }
};

/*
思路2：二分查找思想 
注意：非递增数列，还有可能相等，多种情况都要考虑到。 
 */

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
    	if(rotateArray==NULL)   throw new exception("nullptr"); 
		int lIndex=0,rIndex=rotateArray.size()-1;
		if(rIndex==-1)   return 0;
		int midIndex=lIndex;
		while(rotateArray[lIndex]>=rotateArray[rIndex])//因为就旋转一次，最左边的一定大于最右边的，否则就没有旋转 
		{
			if(rIndex-lIndex==1)	
			{
				return rotateArray[rIndex];//这时候左边的指针应该指向了第一个数组的最大值（最后一个值） 
										   //第二个指针应该指向了第二个数组的最小值（第一个值） 
			}	
			midIndex=(lIndex+rIndex)/2;
			//cout<<lIndex<<" "<<midIndex<<" "<<rIndex<<endl;
			if(rotateArray[midIndex]==rotateArray[lIndex]
				&&rotateArray[midIndex]==rotateArray[rIndex])//如果三个相等就没有办法用二分查找了 
			{
				int min=rotateArray[lIndex];
				for(int i=lIndex;i<rIndex;i++)
				{
					if(rotateArray[i]<min)
						min=rotateArray[i];
				}
				return min;
			}
			if(rotateArray[midIndex]>=rotateArray[lIndex])//中间的大于左边的
			{
				lIndex=midIndex;//左指针移动到中间				 
			}
			else if(rotateArray[midIndex]<=rotateArray[rIndex])//中间的小于右边的 
			{
				rIndex=midIndex;//右指针移动到中间 
			}
		}
		return rotateArray[lIndex];
    }
};

7、斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*
公式法，指数增长
*/
class Solution {
public:
    int Fibonacci(int n) {
    	if(n==0)   return 0;
    	if(n==1)   return 1;
		return Fibonacci(n-1)+Fibonacci(n-2);
    }
};


/*
思路：把计算出来的后面直接用上，避免重复计算
注意：起止边界
 */
class Solution {
public:
    int Fibonacci(int n) {
    	if(n<=0)  return 0;
    	if(n==1)  return 1;
    	int f1=1,f2=0,fn=1;
    	for(int i=2;i<=n;i++)
    	{
    		fn=f1+f2;
    		f2=f1;
    		f1=fn;
    	}
    	return fn;
    }
};

8、青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
 思路:同上
 */
class Solution {
public:
    int jumpFloor(int number) {
    	if(number==0)   return 1;
    	if(number==1)   return 1;
    	int sum1=1,sum2=1,sum=2;
    	for(int i=2;i<=number;i++)//去掉前两次基本跳法（搞清楚基本跳法的基数是多少）
    	{
    		sum=sum1+sum2;
    		sum2=sum1;
    		sum1=sum;
		}
		return  sum;
    }
};

9、变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
假设跳上第n个台阶有f(n)种方法，则f(1)=1,f(2)=2,f(3)=4,f(4)=8,我们隐约感觉到f(n)=2^(n-1)。但是需要证明下，采用数学归纳法同样根据我们根据上篇文章中跳台阶的思路，可以得到f(n)=f(n-1)+f(n-2)+....+f(1)+1,而f(n-1)=f(n-2)+....+f(1)+1,两个式子相减，得到f(n) = 2f(n-1),很明显可以得到f(n)=2^(n-1)。
 */
class Solution {
public:
    int jumpFloorII(int number) {
        int jump_number = 1;
        for(int i=0; i<number-1; i++)
            jump_number = jump_number * 2;
        return jump_number;
    }
};

//简单的写法，也更快
class Solution {
public:
    int jumpFloorII(int number) {
        return 1<<(--number);
    }
};

10、矩形覆盖

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
同上，有两种摆放方式，减去一个有一种，减去两个有一种。
*/
class Solution {
public:
    int rectCover(int number) {
        if(number<2)   return number;
        int sum1=2,sum2=1,sum=3;
        for(int i=2;i<number;i++)
        {
            sum=sum1+sum2;
            sum2=sum1;
            sum1=sum;
		}
        return sum;
    }
};

11、二进制中1的个数

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*
思路1：考虑到附负数，要用外部的游标
 */
class Solution {
public:
     int  NumberOf1(int n) {
     	if(n==0)  return 0;
		int count=0;        
 		int flag=1;
 		while(flag)//考虑到负数 
 		{
 			if(flag&n)
			  count++;
			flag=flag<<1; 
			cout<<flag<<endl;
		}
		return count;	
	}
};

/*
思路2：一个数与自己减去1的得数相与就可以把最后一位1变为0，依次类推就可以把所有的1变为0;
 */
class Solution {
public:
	int  NumberOf1(int n) {
		int count=0;
		while(n)
		{
			count++;
			n=(n-1)&n;
		}
		return count;
	}
};

12、数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*
要考虑完全涉及到的情况：
1）指数为正
2）指数为负
3）底数为正
4）底数为负
*/
class Solution {
public:
    double Power(double base, int exponent) {
    	double sum=0;
    	if(base==0)   return 0;
    	if(exponent==0)   return 1;
    	else if(exponent>0)//指数为正
    	{	
			for(int i=0;i<exponent;i++)
			{
				sum=sum+base;
			}
			if(base<0&&exponent%2)
				sum=sum*(-1);
    	}else{//指数为负
			for(int i=0;i<exponent*(-1);i++)
			{
				sum=sum+base;
			} 
			sum=1.00/sum;
			if(base<0&&exponent%2)
				sum=sum*(-1);
    	}
    }
};

13、调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

判断一个数是否是奇数：x&0x1==0; 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*相对位置可变的解法*/
/*维护两个指针，前指针从前向后找到第一个偶数，后指针从后向前找到第一个奇数，然后相互交换位置*/
class Solution {
public:
    void reOrderArray(vector<int> &array) {
		int lIndex=0,rIndex=array.size()-1;
		while(lIndex<rIndex)
		{
			while((array[lIndex] & 0x1)!=0)//前指针从前向后找到第一个偶数
			{
				lIndex++;
			}
			while((array[rIndex] & 0x1)==0)//后指针从后向前找到第一个奇数
			{
				rIndex--;
			} 
			if(lIndex<rIndex)
			{
				swap(array[lIndex],array[rIndex]);
			}
		}
    }
};

如果改变规则为可以被3整除的和不能被3整除的前后分组，尾数为4的和位数不为4的前后分组,使用函数指针增加代码的复用性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*相对位置不可变的解法*/
/*复杂度比较高的简单解法，维护两个指针，前面的指针找到第一个偶数，下一个指针从这个指针开始往后找到第一个奇数，
然后把找到的奇数保存下来，再把两个指针之间的数向后移一位，再把奇数保存到前面*/
class Solution {
public:
    void reOrderArray(vector<int> &array,bool (*isEvent)(int a)) {
        int length = array.size();
        if(length==0 || length==1)
            return;

        int index_even=0, index_odd;
        while(index_even<length)
        {
            while(!isEven(array[index_even]))//循环到第一个偶数 
                ++ index_even;
            index_odd = index_even+1;//左指针的后一个开始向后找到第一个奇数 
            while(isEven(array[index_odd]))
                ++ index_odd;

            if(index_odd<length)
            {
                int temp = array[index_odd];//后面的奇数 
                for(int i=index_odd; i>index_even; i--)//从后面的指针到前面的指针，交换位置 
                    array[i] = array[i-1];
                array[index_even] = temp;//把后面的奇数调整到前面来 
            }
            else
                break;
        }
    }
};

bool isEven(int number){
	return (number & 0x1) == 0;//判断这个数是不是偶数 
}

链表中倒数第 k个节点

输入一个链表，输出该链表中倒数第k个结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*定义两个快慢指针,快的先走k步,然后一起走到快指针到最后，这样慢指针指向的就是要求的*/
/*注意（测试点）：ListHead==nullptr 倒数第k个节点，不是从0开始的，
				  倒数第一个节点就是最后一个，k有可能大于链表长度，还有可能等于0*/
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* lptr=pListHead,*rptr=pListHead;
        
    	for(int i=1;i<k;i++)
    	{
            if(rptr->next)//这种情况更要考虑到，有可能k>链表长度
                rptr=rptr->next;//向后移动k个
            else return NULL;
    	}
    	while(rptr->next)//右指针向后移动至尾部
    	{
    		rptr=rptr->next;
    		lptr=lptr->next;
    	}
    	return lptr;
    }
};

反转链表

输入一个链表，反转链表后，输出链表的所有元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
		if(pHead==nullptr)   return nullptr;

		ListNode* p=pHead;
		ListNode* pre=nullptr;
		ListNode* pnext=p->next;
		ListNode* reserveHead=nullptr;

		while(p)
		{
			pnext=p->next;
			p->next=pre;
			if(pnext==nullptr)
			{
				reaerveHead=p;
			}
			pre=p;
			p=pnext;
		}

    }
};

合并两个排序的链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

方法1：（循环）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
思路：将链表2往链表1中合并，两层循环，外部循环链表2，内部循环链表1，找到第一个p2<p1的点，并把p2插曲p1的前面的一个点。
注意及测试点：链表1和2为nullptr，链表1和2的插入结束位置（边界！！！）。
 */
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
    	if(pHead1==NULL)   return pHead2;
    	if(pHead2==NULL)   return pHead1;
    	
        ListNode* p1=pHead1,* p2=pHead2; 
        while(p1->next&&p2)//处理最后一个p2，不处理最后一个p1; 
        {
        	while(p1->next&&p2&&p2->val<p1->next->val)//找到小于的第一个节点，内部移动p2 
			{
				ListNode* p1next=p1->next;
				ListNode* p2next=p2->next;
				p1->next=p2;
				p2->next=p1next;
				p2=p2next;
			}
			p1=p1->next;//外部移动p1 
		}
		
		if(p2)//把p2剩下的接上去
        {
            while(p1->next)//把p1调到结尾 
				p1=p1->next;
        	p1->next=p2;
        }
		
		return pHead1;
    }
};

方法2：（递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
思路：因为每次合并完一个节点后剩下的都是一个新的两个链表的合并开始 ，所以可以看作递归来做。
注意与测试点：深入理解这个递归的思路与过程，可以结合上面的循环来看，注意返回
 */ 

class Solution {
public:
	int head;
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
    	if(pHead1==NULL)   return pHead2;
    	if(pHead2==NULL)   return pHead1;
    	
    	ListNode* pHead=NULL; 
     	if(pHead2->val<=pHead1->val)//如果找到一个小于的节点
		{
			pHead=pHead2;
			pHead->next=Merge(pHead1,pHead2->next);//p2向后移动 (上面的内部循环)
		}else//如果小于或者等于p1 
		{
			pHead=pHead1; 
			pHead->next=Merge(pHead1->next,pHead2); //p1向后移动 (上面的外部循环)
		}
		
		return pHead;
    }
};

树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

1
2


本文标题:剑指offer|

文章作者:Hengliy

发布时间:2018年02月04日 - 15:02

最后更新:2018年02月24日 - 17:02

原始链接:http://hengliy.github.io/2018/02/04/剑指OFFER/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。