《剑指offer》week1

发表于 | 分类于 ，

问题一：找出数组中重复的数

题目描述

给定一个长度为$n$的整数数组 nums，数组中所有的数字都在 $0∼n−1$的范围内。

数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

注意：如果某些数字不在 $0∼n−1$的范围内，或数组中不包含重复数字，则返回 -1；

样例

1
2
3
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

题目分析

(数组遍历) $O(n)$

首先遍历一遍数组，如果存在某个数不在0到n-1的范围内，则返回-1。

下面的算法的主要思想是把每个数放到对应的位置上，即让 nums[i] = i。

从前往后遍历数组中的所有数，假设当前遍历到的数是$nums[i]=x$，那么：

如果x != i && nums[x] == x，则说明$x$出现了多次，直接返回$x$即可；

如果nums[x] != x，那我们就把$x$交换到正确的位置上，即 swap(nums[x], nums[i])，交换完之后如果nums[i] != i，则重复进行该操作。由于每次交换都会将一个数放在正确的位置上，所以swap操作最多会进行$n$次，不会发生死循环。
循环结束后，如果没有找到任何重复的数，则返回-1。

时间复杂度分析

每次swap操作都会将一个数放在正确的位置上，一共只有$n$个数和$n$个位置，所以swap最多会进行$n$次。所以总时间复杂度是$O(n)$。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
    	int n=nums.size();
        if(nums.empty()) return -1;
        for(auto x:nums){
        	if(x>n&&x<0) return -1;
		}
    	for(int i=0;i<n;i++){
            if(i!=nums[i]&&nums[nums[i]]==nums[i])
            	return nums[i];    //也就是说当前扫描到的数和和这个数应该所在的位置的数是一个数
         	if(i!=nums[i]&&nums[i]!=nums[nums[i]])
            	swap(nums[i],nums[nums[i]]);   //这一步就是把当前扫描到的数放到应该放到的位置
		}
      return -1;
    }
};

总结

这个题目的思想就是充分利用题目给的条件，也就是数组中的数只是在$0∼n−1$之间，刚好有$n$个数，我们只要将每一数根据它的数值大小放到它应该所在的位置上（swap(nums[i],nums[nums[i]])），其实这就是相当于提前占坑，如果后面也有一个数和这个数相等，就会发现这个坑已经被别人占nums[i]!=i&&nums[i]==nums[nums[i]]，就直接返回这个数就行。

问题二：不修改数组找出重复的数字

题目描述

给定一个长度为 $n+1$的数组nums，数组中所有的数均在 $1∼n$的范围内，其中$n≥1$。

请找出数组中任意一个重复的数，但不能修改输入的数组。

样例

1
2
3
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

思考题：如果只能使用 $O(1)$的额外空间，该怎么做呢？

题目分析

(分治，抽屉原理) $O(nlogn)$

这道题目主要应用了抽屉原理和分治的思想。

抽屉原理：n+1 个苹果放在 n 个抽屉里，那么至少有一个抽屉中会放两个苹果。

用在这个题目中就是，一共有 n+1 个数，每个数的取值范围是1到n，所以至少会有一个数出现两次。

然后我们采用分治的思想，将每个数的取值的区间[1, n]划分成[1, n/2]和[n/2+1, n]两个子区间，然后分别统计两个区间中数的个数。

注意这里的区间是指 数的取值范围，而不是 数组下标。

划分之后，左右两个区间里一定至少存在一个区间，区间中数的个数大于区间长度。

这个可以用反证法来说明：如果两个区间中数的个数都小于等于区间长度，那么整个区间中数的个数就小于等于n，和有n+1个数矛盾。

因此我们可以把问题划归到左右两个子区间中的一个，而且由于区间中数的个数大于区间长度，根据抽屉原理，在这个子区间中一定存在某个数出现了两次。

依次类推，每次我们可以把区间长度缩小一半，直到区间长度为1时，我们就找到了答案。

复杂度分析

时间复杂度：每次会将区间长度缩小一半，一共会缩小$ O(logn)$次。每次统计两个子区间中的数时需要遍历整个数组，时间复杂度是 $O(n)$。所以总时间复杂度是$ O(nlogn)$。

空间复杂度：代码中没有用到额外的数组，所以额外的空间复杂度是 $O(1)$。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n=nums.size();
        for(auto x:nums){
            if(x>n||x<1)
            	return -1;
		}
        int l=1,r=n-1;
        while(l<r){
            int count=0;
            middle=end+start>>1;
            for (auto x : nums) count += x >= start && x <= middle;
            if(count>middle-start+1)
            	end=middle;
            else
            	start=middle+1;
		}
        return r;
    }
};

总结

二分查找算法模板

算法思路：假设目标值在闭区间$[l, r]$中， 每次将区间长度缩小一半，当$l = r$时，我们就找到了目标值。

当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。

C++ 代码模板：

1
2
3
4
5
6
7
8
int binarySearch(int l,int r){
    while(l<r){
      mid=l+r>>2;
      if (check(mid)) r = mid;
      else l = mid + 1;
	}
	return l;
}

问题三：二维数组中的查找

题目描述

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

样例

1
2
3
4
5
6
7
8
9
10
11
输入数组
[
  [1,2,8,9]，
  [2,4,9,12]，
  [4,7,10,13]，
  [6,8,11,15]
]

如果输入查找数值为7，则返回true，

如果输入查找数值为5，则返回false。

题目分析

(单调性扫描) $O(n+m)$

核心在于发现每个子矩阵右上角的数的性质：

  • 如下图所示，x左边的数都小于等于x，x下边的数都大于等于x。

因此我们可以从整个矩阵的右上角开始枚举，假设当前枚举的数是 $x$：

  • 如果 $x$等于target，则说明我们找到了目标值，返回true；
  • 如果 $x$小于target，则 $x$左边的数一定都小于target，我们可以直接排除当前一整行的数；
  • 如果 $x$大于target，则 $x$下边的数一定都大于target，我们可以直接排序当前一整列的数；

排除一整行就是让枚举的点的横坐标加一，排除一整列就是让纵坐标减一。

当我们排除完整个矩阵后仍没有找到目标值时，就说明目标值不存在，返回false。

时间复杂度分析

每一步会排除一行或者一列，矩阵一共有$n$行，$m$列，所以最多会进行$m+n$步。所以时间复杂度是$O(n+m)$。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool searchArray(vector<vector<int>> array, int target) {
    	if(array.empty()||array[0].empty()) return false;   //先判断函数传入的参数是否合格
      	int i=0,j=array[0].size()-1;
      	while(i<array.size()&&j>=0){
  			if(target==array[i][j]) return true;
          	if(target>array[i][j])
              	i++;
            else
              	j--;
		}
      return flase;
    }
};

总结

在遇到比较复杂的问题时，应该从一个简单的情况入手，得到一般的规律。

问题四：替换空格

题目描述

请实现一个函数，把字符串中的每个空格替换成"%20"。

你可以假定输入字符串的长度最大是1000。

注意输出字符串的长度可能大于1000。

样例

1
2
3
输入："We are happy."

输出："We%20are%20happy."

题目分析

算法1

(线性扫描) $O(n)$
这个题在C++里比较好做，我们可以从前往后枚举原字符串：

如果遇到空格，则在string类型的答案中添加 “%20”；

如果遇到其他字符，则直接将它添加在答案中；

但在C语言中，我们没有string这种好用的模板，需要自己malloc出char数组来存储答案。

此时我们就需要分成三步来做：

  • 遍历一遍原字符串，计算出答案的最终长度；
  • malloc出该长度的char数组；
  • 再遍历一遍原字符串，计算出最终的答案数组；

时间复杂度分析

原字符串只会被遍历常数次，所以总时间复杂度是$O(n)$。

算法2

(双指针扫描) $O(n)$
在部分编程语言中，我们可以动态地将原数组长度扩大，此时我们就可以使用双指针算法，来降低空间的使用：

  • 首先遍历一遍原数组，求出最终答案的长度length；
  • 将原数组resize成length大小；
  • 使用两个指针，指针i指向原字符串的末尾，指针j指向length的位置；
  • 两个指针分别从后往前遍历，如果str[i] == ‘ ‘，则指针j的位置上依次填充’0’, ‘2’, ‘%’，这样倒着看就是”%20”；如果str[i] != ‘ ‘，则指针j的位置上填充该字符即可。

由于i之前的字符串，在变换之后，长度一定不小于原字符串，所以遍历过程中一定有i <= j，这样可以保证str[j]不会覆盖还未遍历过的str[i]，从而答案是正确的。

时间复杂度分析

原字符串只会被遍历常数次，所以总时间复杂度是$ O(n)$。

C++代码

算法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string replaceSpaces(string &str) {
      	string res;
      	for(auto x:str){
  			if(x==' ')
              	res+="20%"
            else
              	res+=x;
		}
      return res;
    }
};

算法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string replaceSpaces(string &str) {
    	int count=0;
    	for(auto x:str)
    		if(x==' ')
    			count++;
    	int indexOfOriginal=str.size();
    	int indexOfNew=str.size()+count*2;
      	str.resize(indexOfNew+1);
    	while(indexOfOriginal>=0&&indexOfNew>indexOfOriginal){
  			if(str[indexOfOriginal]==' ')
  				str[indexOfNew--]="0";
  				str[indexOfNew--]="2";
  				str[indexOfNew--]="%";
  			else
  				str[indexOfNew--]=str[indexOfOriginal];
  			indexOfOriginal--;
		}
		return str;
    }
};

总结

如果面试的过程中面试官要求不能浪费多余的空间，也就是直接在原数组后面直接加内存，则用算法二；如果没有这种要求的话，就直接用算法一。

问题五：从尾到头打印链表

输入一个链表的头结点，按照 从尾到头 的顺序返回节点的值。

返回的结果用数组存储。

样例

1
2
输入：[2, 3, 5]
返回：[5, 3, 2]

题目分析

(遍历链表) $O(n)$

单链表只能从前往后遍历，不能从后往前遍历。

因此我们先从前往后遍历一遍输入的链表，将结果记录在答案数组中。
最后再将得到的数组逆序即可。

时间复杂度分析

链表和答案数组仅被遍历了常数次，所以总时间复杂度是$O(n)$。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
    	vector<int> res;
    	
    	while(head){
  			res.push_back(head->val);
  			head=head->next();
		}
		return vector<int>(res.rbegin(),res.rend());
    }
};

总结

链表的数据结构：

1
2
3
4
struct ListNode{
  	int m_nValue;
  	ListNode *m_pNext;
}

模板一：在链表的末尾添加一个节点

模板二：找到第一个含有某个数值的节点并删除这个节点

问题六：重构二叉树

题目描述

输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。

注意:

  • 二叉树中每个节点的值都互不相同；
  • 输入的前序遍历和中序遍历一定合法；

样例

1
2
3
4
5
6
7
8
9
10
11
给定：
前序遍历是：[3, 9, 20, 15, 7]
中序遍历是：[9, 3, 15, 20, 7]

返回：[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示：
    3
   / \
  9  20
    /  \
   15   7

题目分析

(递归) $O(n)$
递归建立整棵二叉树：先递归创建左右子树，然后创建根节点，并让指针指向两棵子树。

具体步骤如下：

  • 先利用前序遍历找根节点：前序遍历的第一个数，就是根节点的值；
  • 在中序遍历中找到根节点的位置$k$，则$k$左边是左子树的中序遍历，右边是右子树的中序遍历；
  • 假设左子树的中序遍历的长度是$l$，则在前序遍历中，根节点后面的个$l$数，是左子树的前序遍历，剩下的数是右子树的前序遍历；
  • 有了左右子树的前序遍历和中序遍历，我们可以先递归创建出左右子树，然后再创建根节点；

时间复杂度分析

我们在初始化时，用哈希表(unordered_map)记录每个值在中序遍历中的位置，这样我们在递归到每个节点时，在中序遍历中查找根节点位置的操作，只需要$O(1)$的时间。此时，创建每个节点需要的时间是$O(1)$，所以总时间复杂度是$O(n)$。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  	unordered_map<int,int> pos;
  	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
      	for(int i=0;i<inorder.size();i++)
          	pos[inorder[i]]=i;   //记录下每一个中序遍历的的序列下标
      	return dfs(preorder,inorder,0,preorder.size()-1,0,preorder.size()-1);
    TreeNode* dfs(vecotr<int>& pre,vector<int>& in,pl,pr,il,ir){
      	if(pl>pr) return NULL;
  		TreeNdoe* root(pre[pl]);
      	int k=pos[pre[pl]];  //左子树节点的个数为k-il
      	root->left=dfs(pre,in,pl+1,pl+k-il,il,k-1);
      	root->right=dfs(pre,in,pl+k-il+1,pr,k+1,ir);
      	return root;
	}

总结

这个题目非常经典，必须要熟练掌握啊，思想就是用递归的想法建立左子树和右子树。

问题七：二叉树的下一个节点

问题描述

给定一棵二叉树的其中一个节点，请找出中序遍历序列的下一个节点。

注意：

  • 如果给定的节点是中序遍历序列的最后一个，则返回空节点;
  • 二叉树一定不为空，且给定的节点一定不是空节点；

样例

1
2
3
4
5
6
7
8
假定二叉树是：[2, 1, 3, null, null, null, null]， 给出的是值等于2的节点。

则应返回值等于3的节点。

解释：该二叉树的结构如下，2的后继节点是3。
  2
 / \
1   3

题目分析

(模拟) $O(h)$

这道题目就是让我们求二叉树中给定节点的后继。

分情况讨论即可，如下图所示：

  • 如果当前节点有右儿子，则右子树中最左侧的节点就是当前节点的后继。比如F的后继是H；
  • 如果当前节点没有右儿子，则需要沿着father域一直向上找，找到第一个是其father左儿子的节点，该节点的father就是当前节点的后继。比如当前节点是D，则第一个满足是其father左儿子的节点是C，则C的father就是D的后继。

时间复杂度分析

不论往上找还是往下找，总共遍历的节点数都不大于树的高度。所以时间复杂度是$O(h)$，其中$h$是树的高度。

C++代码

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode *father;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* p) {
    	if(p->right){
    		p=p->right;
    		while(p->left) p=p->left;
    		return p;
		}
		else{
  			while (p->father && p == p->father->right) p = p->father;
  			return p->father;
			}
		}
	}
};

问题八：用两个栈实现队列

题目描述

请用栈实现一个队列，支持如下四种操作：

  • push(x) – 将元素x插到队尾；
  • pop() – 将队首的元素弹出，并返回该元素；
  • peek() – 返回队首元素；
  • empty() – 返回队列是否为空；

注意：

  • 你只能使用栈的标准操作：push to top，peek/pop from top, size 和 is empty；
  • 如果你选择的编程语言没有栈的标准库，你可以使用list或者deque等模拟栈的操作；
  • 输入数据保证合法，例如，在队列为空时，不会进行pop或者peek等操作；

样例

1
2
3
4
5
6
7
MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

题目分析

(栈，队列) $O(n)$

这是一道基础题，只要把功能实现对就可以，不需要考虑运行效率。

我们用两个栈来做，一个主栈，用来存储数据；一个辅助栈，用来当缓存。

  • push(x)，我们直接将x插入主栈中即可。
  • pop()，此时我们需要弹出最先进入栈的元素，也就是栈底元素。我们可以先将所有元素从主栈中弹出，压入辅助栈中。则辅助栈的栈顶元素就是我们要弹出的元素，将其弹出即可。然后再将辅助栈中的元素全部弹出，压入主栈中。
  • peek()，可以用和pop()操作类似的方式，得到最先压入栈的元素。
  • empty()，直接判断主栈是否为空即可。

时间复杂度分析

  • push()：$O(1)$；
  • pop(): 每次需要将主栈元素全部弹出，再压入，所以需要$O(n)$ 的时间；
  • peek()：类似于pop()，需要$O(n)$的时间；
  • empty()：$O(1)$；

C++代码

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
class MyQueue {
public:
    /** Initialize your data structure here. */
    stack<int> stk, cache;
    MyQueue() {

    }
  	void push(int x){
  		stk.push(x);
	}
  	void copy(stack<int> &a,stack<int> &b){
  		while(a.size()){
			b.push(a.top());
          	a.pop();
		}
    int pop(){
  		copy(stk,cache);
      	res=cache.top()
        cache.pop();
      	copy(cache,stk);
      	return res;
	}
	 /** Get the front element. */
    int peek() {
        copy(stk, cache);
        int res = cache.top();
        copy(cache, stk);
        return res;
    }
    /** Returns whether the queue is empty. */
    bool empty() {
        return stk.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * bool param_4 = obj.empty();
 */

总结

如果用两个队列实现一个栈的话，在插入元素的时候，就是将该元素压入到非空的队列中；在删除元素的时候将当前非空的队列的元素一一进行删除并压入到另一个空的队列中，队列中最后一个元素只进行删除。

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
/*
用两个队列模拟入栈操作
*/
void push(PQUEUE pS1,PQUEUE pS2,int val)
{
	if(is_empty(pS2))
		en_queue(pS1, val);
	else
		en_queue(pS2, val);
}
 
/*
用两个队列模拟出栈操作
*/
bool pop(PQUEUE pS1,PQUEUE pS2,int *pData)
{
	if(is_empty(pS1) && is_empty(pS2))
		return false;
 
	int DelData;
	if(!is_empty(pS2))
	{
		int len = length(pS2);
		while(len-- > 1)
		{
			de_queue(pS2,&DelData);
			en_queue(pS1,DelData);
		}
		//将队列的最后一个元素出队，作为出栈元素
		de_queue(pS2,pData);
		return true;
	}
	if(!is_empty(pS1))
	{
		int len = length(pS1);
		while(len-- > 1)
		{
			de_queue(pS1,&DelData);
			en_queue(pS2,DelData);
		}
		//将队列的最后一个元素出队，作为出栈元素
		de_queue(pS1,pData);
		return true;
	}
}

问题九：斐波那契数列

问题描述

输入一个整数 $n$，求斐波那契数列的第$n$项。

假定从0开始，第0项为0。($n<=39$)

样例

1
2
3
输入整数 n=5 

返回 5

题目分析(递推)

这题的数据范围很小，我们直接模拟即可。

当数据范围很大时，就需要采用其他方式了，可以参考 求解斐波那契数列的若干方法 。

用两个变量滚动式得往后计算，$a$表示第 $n−1$项，$b$表示第$n$项。

则令$c=a+b$ 表示第 $n+1$ 项，然后让 $a,b$ 顺次往后移一位。

时间复杂度分析

总共需要计算$n$ 次，所以时间复杂度是 $O(n)$ 。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int Fibonacci(int n) {
    	int a=b=1;
    	int c;
    	while(n--){
  			c=a+b;
  			b=a;
  			b=c;
		}
		return c;
	}
}

总结

矩阵运算 + 快速幂。

快速幂算法的模板可以参考这里。

可以先利用矩阵运算的性质将通项公式变成幂次形式，然后用平方倍增（快速幂）的方法求解第$n$项。

首先我们定义向量

然后我们可以找出矩阵：

则有：

所以：

由于矩阵具有结合律，所以我们可以先求出$A^{n-1} \% P$，然后再用$X1$左乘，即可求出$X_n$，向量$X_n$的第一个元素就是$a_n$。

时间复杂度分析：快速幂的时间复杂度是 $O(logn)$，所以算法5的时间复杂度也是 $O(logn)$。

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ctime>

using namespace std;
void mul(int a[][2], int b[][2], int c[][2]){
  	int temp[][2] = {{0, 0}, {0, 0}};
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
            for (int k = 0; k < 2; k ++ )
            {
                long long x = temp[i][j] + (long long)a[i][k] * b[k][j];
                temp[i][j] = x % MOD;
            }
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
            c[i][j] = temp[i][j];
 
}
int f_final(long long n)
{
    int x[2] = {1, 1};

    int a[2][2] = {{1, 1}, {1, 0}};

    int res[][2] = {{1, 0}, {0, 1}};
    int t[][2] = {{1, 1}, {1, 0}};
    long long k = n - 1;
    while (k)
    {
        if (k&1) mul(res, t, res);   //res*=t
        mul(t, t, t);    //t*=t
        k >>= 1;
    }

    int c[2] = {0, 0};
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
        {
            long long r = c[i] + (long long)x[j] * res[i][j];
            c[i] = r % MOD;
        }

    return c[0];
}


int main()
{
    long long n ;

    cin >> n;
    cout << f_final(n) << endl;

    return 0;
}

这里给出快速幂运算的代码和解释：

代码：

1
2
3
4
5
6
7
8
9
10
int pow(int a, int b) {
    int ans = 1, base = a;
    while (b != 0) {
        if (b & 1 != 0)   //当b的最后一位为奇数时
            ans *= base;
        base *= base;
        b >>= 1;
    }
    return ans;
}

解释：快速幂运算也叫反复平方法

假设要求$x^n$，如果$n = 2^k$，那么原题可以很轻松的表示为：$x^n = ((x^2)^2)^2…$。这样只要做$k$次平方运算就能解决，时间复杂度就从$O(n)$下降到$log(n)$。

由上面的分析可知，只要幂运算的幂可以写成$2^k$的形式，就可以用上面的方法降低时间复杂度。所以我们可以将任意的实数$n$改写有限个$2^k$的形式的相加。例如：

img
如图所示，$x^{22}$可以改写成$x^{16}x^4x^2$。这样我们就可以分别对$x^{16}$和$x^4$以及$x^2$使用上述方法快速计算结果，最后只要相加就可以了。

由于是二进制，很自然地想到用位运算这个强大的工具：&和>>

&运算通常用于二进制取位操作，例如一个数 & 1 的结果就是取二进制的最末位。还可以判断奇偶x&1==0为偶，x&1==1为奇。

运算比较单纯,二进制去掉最后一位，

题目十：找出旋转数组中的最小值

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

输入一个升序的数组的一个旋转，输出旋转数组的最小元素。

例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

数组可能包含重复项。

注意：数组内所含元素非负，若数组大小为0，请返回-1。

样例

1
2
3
输入：nums=[2,2,2,0,1]

输出：0

题目分析

(二分) $O(n)$

用两个指针分别指向数组中的第一个元素和最后一个元素，按照题目中的旋转的规则，第一个元素应该是大于或者等于最后一个元素（当然，这种情况有特例，当数组中允许存在重复数组的时候，有可能数组中最后一个元素和第一个元素是相等的，这个时候我们需要将最后一个相等的元素删除掉）

接着我们可以找到中间元素，如果中间元素大于第一个指针指向的元素的话，那么中间元素就是位于前面的数组中；如果中间元素小于第二个指针指向的元素的话，那么中间元素就是位于后面的数组中。这两种情况下分别移动第二个和第一个指针。

为了便于分析，我们先将数组中的数画在二维坐标系中，横坐标表示数组下标，纵坐标表示数值，如下所示：

图中水平的实线段表示相同元素。

我们发现除了最后水平的一段（黑色水平那段）之外，其余部分满足二分性质：竖直虚线左边的数满足 $nums[i]>=nums[0]$；而竖直虚线右边的数不满足这个条件。

分界点就是整个数组的最小值。

所以我们先将最后水平的一段删除即可。

另外，不要忘记处理数组完全单调的特殊情况：

当我们删除最后水平的一段之后，如果剩下的最后一个数大于等于第一个数，则说明数组完全单调。

时间复杂度分析

二分的时间复杂度是 $O(logn)$，删除最后水平一段的时间复杂度最坏是 $O(n)$，所以总时间复杂度是 $O(n)$。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size() - 1;
        if (n < 0) return -1;
        while (n > 0 && nums[n] == nums[0]) n -- ;
        if (nums[n] >= nums[0]) return nums[0];
        int l = 0, r = n;
        while (l < r) {
            int mid = l + r >> 1;       // [l, mid], [mid + 1, r]
            if (nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        return nums[r];
    }
};

总结

二分查找的使用主要是判断$low$指针和$high$指针和$middle$位置的大小，这个题目其实在第一次迭代后就是我们常规的二分查找了

问题十一：数组中的路径

题目描述

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。

路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。

如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。

注意：

  • 输入的路径不为空；
  • 所有出现的字符均为大写英文字母；

样例

1
2
3
4
5
6
7
8
9
10
matrix=
[
  ["A","B","C","E"],
  ["S","F","C","S"],
  ["A","D","E","E"]
]

str="BCCE" , return "true" 

str="ASAE" , return "false"

题目分析

(DFS) $O(n^23^k)$

在深度优先搜索中，最重要的就是考虑好搜索顺序。

我们先枚举单词的起点，然后依次枚举单词的每个字母。

过程中需要将已经使用过的字母改成一个特殊字母，以避免重复使用字符。

时间复杂度分析

单词起点一共有 $n^2$ 个，单词的每个字母一共有上下左右四个方向可以选择，但由于不能走回头路，所以除了单词首字母外，仅有三种选择。所以总时间复杂度是 $O(n^23^k)$。

C++代码

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
class Solution {
public:
    bool hasPath(vector<vector<char>>& matrix, string str) {
        for(int i=0;i<matrix.size();i++)
            for(int j=0;j<matrix[0].size();j++){
                if(dfs(matrix,str,0,i,j))
                    return true;
            }
        return false;
    }
    bool dfs(vector<vector<char>> &matrix, string &str, int u, int x, int y) {
        if (matrix[x][y] != str[u]) return false;   //如果当前的矩阵中的元素和字符串元素不相等，则直接返回false;
        if (u == str.size() - 1) return true;   //如果当前已经到了字符串最后一个元素，则可以跳出递归，直接返回true；
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        char t = matrix[x][y];
        matrix[x][y] = '*';  //标记这个元素已经访问过
        //在上下左右四个方位进行判断
        for (int i = 0; i < 4; i ++ ) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < matrix.size() && b >= 0 && b < matrix[a].size()) {
                if (dfs(matrix, str, u + 1, a, b)) return true;
            }
        }
        //在上下左右四个方位中没有元素能够进行匹配
        matrix[x][y] = t;
        return false;
    }
};

总结

这个题目就是使用回溯法，主要要判断好递归的入口！

第一周的打卡结束，收获满满，加油，徐何军！！！

分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多