《剑指offer》week3

发表于 | 分类于 ，

问题一：二叉搜索树的后序遍历序列

问题描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

如果是则返回true，否则返回false。

假设输入的数组的任意两个数字都互不相同。

样例

1
2
3
输入：[4, 8, 6, 12, 16, 14, 10]

输出：true

问题分析

二叉搜索数对应的就是树的中序遍历

在这里，首先通过后续遍历的结果找到根节点，也即是数组中的最后一个元素，然后在数组中从左到右找出第一个比根节点的元素大的元素，然后从这个节点开始已知遍历到当前后续遍历的倒数第二个元素，如果这其中的元素比根节点的元素小的话，那么就直接返回false，反之则递归判断根节点的左右子树。

时间复杂度

$O(n^2)$

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> seq;
    bool verifySequenceOfBST(vector<int> sequence) {
      	seq=sequence;
      	dfs(0,seq.size()-1);
    }
    bool dfs(int start,int end){
      	if(start>=end) return true;  //找到了最后，也就是最终成功的递归出口
  		int root=q[end];
      	int k=0;
      	while(q[k]<root) k++;
      	for(int i=k;i<end;i++){
  			if(q[i]<root)
              return false;   //找到了最终失败的递归出口
		}
      	return dfs(start,k-1)&&dfs(k,end-1);   //递归继续一步进行
	}

总结

  • 进行递归搜索到最终状态的边界判断（第9行）
  • 找出不满足接着进行递归搜索的情况（第15行）
  • 当前步满足条件，继续进行递归的判断

问题二：二叉树中和为某一值的路径

问题描述

输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。

从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

样例

1
2
3
4
5
6
7
8
9
10
给出二叉树如下所示，并给出num=22。
      5
     / \
    4   6
   /   / \
  12  13  6
 /  \    / \
9    1  5   1

输出：[[5,4,12,1],[5,6,6,5]]

问题分析

题目中已经给了限制条件，也就是路径是从根节点开始一直到叶节点，只需要递归进行判断，注意这里采用的是先序遍历，在具体的过程中，需要定义两个数组，一个是用来保存当前的路径，这个数组在每一次根节点->左子树->右子树之后都要清空；另一个数组是保存所有的满足条件的路径。

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
/**
 * 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:
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> findPath(TreeNode* root, int sum) {
        dfs(root,sum);
        return ans;
    }
    void dfs(TreeNode* root,int sum){
        if(!root) return;    //如果为空的话，那么就跳过该节点
        path.push_back(root->val);
        sum-=root->val;
        if(!root->left&&!root->right&&sum==0)   //如果访问到了叶子结点，并且当前sum已经为0
            ans.push_back(path);
        dfs(root->left,sum);  //遍历当前节点的左子树
        dfs(root->right,sum);  //遍历当前节点的右子树
        path.pop_back();  //当遍历完当前子树之后就清空当前的路径 
    }
};

总结

灵活运用先序遍历、中序遍历、后序遍历，有以下两个动作需要注意：

  • 在访问根节点的时候，是否已经满条件
  • 在一趟遍历完成之后是否需要有其他的动作

问题三：复杂链表的复刻

问题描述

请实现一个函数可以复制一个复杂链表。

在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者null。

问题分析

分以下三步进行：

  • 将每个节点复制一份出来，并将新复制出来的节点接在该节点的后面，这一步就完成了节点的值的复制和节点的next指针的复制
  • 对每一个原来链表中的节点的random指针进行复制，具体的做法为：p->next->random=p->random->next
  • 将新复制出来的节点单独作为一个链表

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
/**
 * Definition for singly-linked list with a random pointer.
 * struct ListNode {
 *     int val;
 *     ListNode *next, *random;
 *     ListNode(int x) : val(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *copyRandomList(ListNode *head) {
        for(auto p=head;p;){   //第一步：在当前节点后面复制一个和当前节点具有相同值的节点，使得该节点指向当前节点的下一个节点
            auto np=new ListNode(p->val);  //生成一个复制节点
            auto next=p->next;  //记录下当前节点的下一个节点
            p->next=np;
            np->next=next;
            p=next;  //将当前节点转移到下一个节点处
        }
        for(auto p=head;p;p=p->next->next){  //第二步：将当前节点的下一个节点的rand指针指向当前节点的rand指针的下一个节点,也就是完成rand指针的复制
            if(p->random){
                p->next->random=p->random->next;
            }
        }
        auto dummy=new ListNode(-1);
        auto cur=dummy;
        for(auto p=head;p;p=p->next){   //第三步：循环获得链表中复制出来的节点
            cur->next=p->next;
            cur=cur->next;
            p=p->next;  //将上for循环中的p=p->next也就是后移两个节点
        }
        return dummy->next;
    }
};

问题四：二叉搜索树与双向链表

问题描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

要求不能创建任何新的结点，只能调整树中结点指针的指向。

注意：

  • 需要返回双向链表最左侧的节点。

例如，输入下图中左边的二叉搜索树，则输出右边的排序双向链表。

问题分析

递归调用

定义一个pair记录当前根节点的最左节点和最右节点，返回时就需要返回这个pair的第一个元素

依次访问每个节点所在的子树，主要有四种情况

  • 当前节点为空
  • 当前节点的左子树和右子树都不为空
  • 当前节点的左子树为空，右子树不为空
  • 当前节点的右子树为空，左子树不为空

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
/**
 * 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:
    TreeNode* convert(TreeNode* root) {
        if(!root) return NULL;
        auto sides=dfs(root);
        return sides.first;
    }
    pair<TreeNode*,TreeNode*> dfs(TreeNode* root){   //用一个pair的形式上记录下一个子树的最左节点和最右节点
        if(!root->left&&!root->right) return {root,root};  //如果左右子树都是为空
        if(root->left&&root->right){     //如果左右子树都不是空的
            auto lside=dfs(root->left),rside=dfs(root->right);
            lside.second->right=root,root->left=lside.second;
            rside.first->left=root,root->right=rside.first;
            return {lside.first,rside.second};
        }
        if(root->left){   //如果左子树不是空的
            auto lside=dfs(root->left);
            lside.second->right=root,root->left=lside.second;
            return {lside.first,root};
        }
        if(root->right){   //如果右子树不是空的
            auto rside=dfs(root->right);
            rside.first->left=root,root->right=rside.first;
            return {root,rside.second};
        }
    }
};

问题五：序列化二叉树

问题描述

请实现两个函数，分别用来序列化和反序列化二叉树。

您需要确保二叉树可以序列化为字符串，并且可以将此字符串反序列化为原始树结构。

样例

1
2
3
4
5
6
7
8
你可以序列化如下的二叉树
    8
   / \
  12  2
     / \
    6   4

为："[8, 12, 2, null, null, 6, 4, null, null, null, null]"

注意:

  • 以上的格式是AcWing序列化二叉树的方式，你不必一定按照此格式，所以可以设计出一些新的构造方式。

问题分析

先序遍历

序列化的过程就是将二叉树节点的数值转换为字符串中的字符

反序列化就是将字符串中的字符转换为节点的数值

如果在序列化的过程中是采用先序遍历的过程，那么在反序列化的过程中也是采用先序遍历，不能两者采用的方法是不一样的。

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
44
45
46
47
48
49
50
/**
 * 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:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        dfs_s(root,res);
        return res;
    }
    void dfs_s(TreeNode* root,string& res){   //前序遍历方法：先遍历根节点，再遍历左节点然后遍历右节点
        if(!root){  //边界判断
            res+="null ";
            return;
        }
        res+=to_string(root->val)+' ';   //先遍历根节点
        dfs_s(root->left,res);   //然后遍历左子树
        dfs_s(root->right,res);  //最后遍历右子树
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int u=0;
        return dfs_d(data,u);
    }
    TreeNode* dfs_d(string data,int &u){
        if(u==data.size()) return NULL;
        int k=u;  
        while(data[k]!=' ') k++;   //定位到空格的地方
        if(data[u]=='n'){  //当前节点不是数字，而是一个'n'
            u=k+1;  //如果则将u指向下一个数字的首地址
            return NULL;
        }
        int val=0;
        for(int i=u;i<k;i++) val=val*10+data[i]-'0';   //获得当前位置的数字
        u=k+1;
        auto root=new TreeNode(val);   //先序遍历遍历根节点
        root->left=dfs_d(data,u);   //先序遍历遍历左子树
        root->right=dfs_d(data,u);   //先序遍历遍历右子树
        return root;  //返回根节点
    }
};

总结

一般优先采用先序遍历，先序遍历的一般化过程如下：

  • 先判断当前的根节点的边界条件
  • 遍历根节点
  • 遍历左子树
  • 遍历右子树
  • 返回子节点

问题六：数组排列

问题描述

输入一组数字（可能包含重复数字），输出其所有的排列方式。

样例

1
2
3
4
5
6
7
8
9
10
11
输入：[1,2,3]

输出：
      [
        [1,2,3],
        [1,3,2],
        [2,1,3],
        [2,3,1],
        [3,1,2],
        [3,2,1]
      ]

问题分析

(深度优先遍历+回溯) $O(n×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
25
26
class Solution{
public:
	vector<vector<int>> res;
	vector<bool> st;
	vector<int> path;
	vector<vector<int>> permute(vector<int>& nums) {
		for (int i = 0; i < nums.size(); i ++ ) st.push_back(false);   //将所有的数字状态置为false
  		dfs(nums,0);
  		return res;
	}
	void dfs(vector<int>& nums,int u){
		if(u==nums.size()){
  			res.push_back(path);
          	return;
		}
  		for(int i=0;i<nums.size();i++){
  			if(!st[i]){
  				path.push_back(nums[i]);
  				st[i]=true;
  				dfs(nums,u+1);
  				st[i]=false;  //递归返回时需要将第i个数值的状态置为未被使用
  				path.pop_back();   //并将第i个数字剔除掉
			}
		}
	}
};

总结

回溯法可以看成蛮力法的升级版，它从解决问题每一步的所有可能选项里系统地选择出一个可行的解决方案。回溯法非常适合由多个步骤组成的问题，并且每个步骤都有多个选项。当我们在某一步选择了其中一个选项时，就进入下一步，然后又面临新的选项。我们就这样重复选择，直至到达最终的状态。

问题七：数组中出现次数超过一半的数字

问题描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

假设数组非空，并且一定存在满足条件的数字。

思考题：

  • 假设要求只能使用$O(n)$ 的时间和额外$O(1)$的空间，该怎么做呢？

样例

1
2
3
输入：[1,2,1,1,3]

输出：1

问题分析

扫描

依次扫描所给数组中的每个整数，先用val记录第一个数组元素，往后扫描，遇到的下一个整数仍等于val，那么令count++，如果不等则count—；如果count变为0，则从下一个元素开始，重新令val为下一个元素，count为1。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int cnt=0,val=-1;   //cnt表示当前元素的计数个数，val表示当前的变量
        for(auto x:nums){
            if(!cnt) val=x,cnt=1;  //如果cnt为0，则从当前元素开始，并且令cnt为1
            else{
                if(x==val) cnt++;
                else cnt--;
            }
        }
        return val;
    }
};

问题八：最小的k个数

问题描述

输入n个整数，找出其中最小的k个数。

注意：

  • 数据保证k一定小于等于输入数组的长度;
  • 输出数组内元素请按从小到大顺序排序;

样例

1
2
3
输入：[1,2,3,4,5,6,7,8] , k=4

输出：[1,2,3,4]

问题分析

利用一个大根堆，每次将整数插入到该大根堆中，如果当前大根堆的元素个数超过k个，那么就需要排除一个元素；最后需要将最后保留的大根堆排一个序。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
    	priority_queue<int> heap;
    	for(auto x:input){
  			heap.push(x);
  			if(heap.size()>k)
  				heap.pop();
		}
		vrctor<int> res;
		for(int i=0;i<heap.size();i++){
  			res.push_back(heap.top());
  			heap.pop();
		}
		reverse(res.begin(),res.end());
		returnres;
	}
}

总结

大根堆定义：priority_queue q;

小根堆定义：priority_queue,greater>

入堆：heap.push(x)

出堆：heap.pop()

取堆顶元素：heap.top()

问题九：数据流中的中位数

问题描述

如何得到一个数据流中的中位数？

如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。

如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

样例

1
2
3
4
5
输入：1, 2, 3, 4

输出：1,1.5,2,2.5

解释：每当数据流读入一个数据，就进行一次判断并输出当前的中位数。

问题分析

维护两个堆，大根堆和小根堆一定是两个中间最相邻的两个数，重点就是怎么去维护这两个堆。大根堆里面存放的是比较小的一半数，小根堆里面存放的是比较大的一半数；大根堆在下，小根堆在上。

每次在添加数的时候我们都是先添加到大根堆里面，出现以下两种情况的话就做出相应的改变：

  • 逆序交换：如果下面的大根堆的元素的堆顶元素大于小根堆堆顶元素，则发生交换
  • 下多转移：如果大根堆的元素格式比小根堆元素的个数多与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
class Solution {
//逆序交换；下多转移；保证下面是小的一半（是一个大根堆），上面是大的一半（是一个小根堆）
public:
    priority_queue<int> max_heap;
    priority_queue<int,vector<int>,greater<int>> min_heap;
    void insert(int num){   //维护两个堆，大根堆和小根堆一定是两个中间最相邻的两个数，重点就是怎么去维护这两个堆
        max_heap.push(num);
        if(min_heap.size()&&max_heap.top()>min_heap.top()){   //如果下面的大根堆的元素的堆顶元素大于小根堆堆顶元素，则发生交换
            auto maxv=max_heap.top(),minv=min_heap.top();
            max_heap.pop(),min_heap.pop();
            max_heap.push(minv),min_heap.push(maxv);
        }
        if(max_heap.size()>min_heap.size()+1){   //如果大根堆的元素格式比小根堆元素的个数多与1个以上
            auto maxv=max_heap.top();
            max_heap.pop();
            min_heap.push(maxv);
        }
    }

    double getMedian(){
        if(max_heap.size()+min_heap.size()&1) return max_heap.top();   //如果是奇数
        else return (max_heap.top()+min_heap.top())/2.0;
    }
};

问题十：连续子数组的最大和

问题描述

输入一个 非空 整型数组，数组里的数可能为正，也可能为负。

数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。

要求时间复杂度为O(n)。

样例

1
2
3
输入：[1, -2, 3, 10, -4, 7, 2, -5]

输出：18

问题分析

动态规划（dp）

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {

//sum记录的是上一个连续数组的和
public:
    int maxSubArray(vector<int>& nums) {
        int max = -100000;
        int sum = 0;
        for (int i = 0; i < nums.size(); i++){
            if (sum < 0) {   //由于数组中可能含有负数，则可能就是说前面连续数组的和可能为0
                sum = nums[i];
            }else
                sum += nums[i];
            if(max < sum) max = sum;
        }
        return max;
    }
};

问题十一：从1到n整数中1出现的次数

问题描述

输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。

例如输入12，从1到12这些整数中包含“1”的数字有1，10，11和12，其中“1”一共出现了5次。

样例

1
2
输入： 12
输出： 5

问题分析

1
2
3
4
5
6
7
8
9
10
设数字为abcde，当前位数为c位    
    c位1的个数即为高位个数+低位个数
    高位范围为 00 ~ ab-1 ：
        有 ab*100 个(因为c在百位)
    如果高位为ab：
  		低位分为三种情况：
        	c = 0 ,有 0 个
        	c = 1 ，有 de + 1 个
        	c > 1 , 有 100 个 (因为c在百位)
    依次遍历每一位数相加，即为总共1的个数

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int numberOf1Between1AndN_Solution(int n) {
        vector<int> nums;
        while(n){
  			nums.push_back(n%10);
  			nums/=10;
		}
		int res=0;
		for(int i=0;i<nums.size();i++){
  			int left=0,right=0,t=1;
  			for(int j=num.size();j>i;j--) left+=left*10+nums[j];
  			for(int j=i-1;j>=0;j--) right+=right*10+nums[j],t*=10;
  			res+=left*t;
  			if(nums[i]==1) res+=right+1;
  			else if(nums[i]>1) res+=t;
		}
		return res;
    }
};
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多