[数据结构与算法]剑指offer —二分、堆、双指针等专题

概述

本文总结二分、双指针、位运算、堆相关的算法题，共有12道题：

1. 旋转数组的最小数字
2. 跳台阶
3. 二叉搜索树与双向链表
4. 最小的k个数
5. 数据流中的中位数
6. 滑动窗口的最大值
7. 数组中数字出现的次数I
8. 数组中数字出现的次数II
9. 和为s的连续正数序列
10. 扑克牌顺子
11. 矩阵中的路径
12. 机器人的运动范围

1. 旋转数组的最小数字

• 题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
原题链接

• 思路

  这是基础的二分题目，但是需要提前做一些处理；

  二分的本质是在一个序列中寻找一个分界点，这个分界点能够将序列分割成两部分，注意必须保证这两部分没有交集。

class Solution {
public:
    int minArray(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;
            if(nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        
        return nums[l];
    }
};

2. 跳台阶

• 题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
原题链接

• 思路

  此题比较简单，做法也很多，但一眼看上去就是数量型DP问题。

class Solution {
public:
    int numWays(int n) {

        if(n <= 1) return 1;
        vector<int> f(n + 1, 0);
        f[0] = 1, f[1] = 1;
        for(int i = 2; i <= n; i ++)
            f[i] = (f[i - 1] + f[i - 2]) % 1000000007;
        return f[n];
    }
};

3. 二叉搜索树与双向链表

• 题目描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
原题链接

• 思路

  此题用dfs做比较方便，dfs的难点在于递归函数的建立，你要明确两个点：

  • 递归函数的作用
  • 最终目的
  
  

  对于dfs问题，一定要先搞清楚上面这两个问题再建立以及构造函数，否则大概率是错误的；

  就以本题为例，递归函数的作用应该是将子树转换为一个双向链表，而最终目的当然就是得到给定树原地转换后的双向链表。好了，明确这两个问题之后就可以着手递归函数的建立了。参数很容易想到就是子树的根，返回值呢？这时候就需要联系这两个点了，也就是如何将子树的双向链表拼接成整个树的双向链表，显然需要双向链表的首尾指针，到这里返回值也被我们确定了就是pair<Node*, Node*>。

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct 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) {
        
        if(!root->left && !root->right) 
            return {root, root};
        
        if(root->left && root->right) {
            
            auto lsides = dfs(root->left), rsides = dfs(root->right);
            lsides.second->right = root, root->left = lsides.second;
            rsides.first->left = root, root->right = rsides.first;
            return {lsides.first, rsides.second};
        }
        
        if(root->left) {
            
            auto lsides = dfs(root->left);
            lsides.second->right = root, root->left = lsides.second;
            return {lsides.first, root};
        }
        
        if(root->right) {
            
            auto rsides = dfs(root->right);
            rsides.first->left = root, root->right = rsides.first;
            return {root, rsides.second};
        }
        
        return {NULL, NULL};
    }
};

这道题不加最后一句return {NULL, NULL};会报存在没有返回值的情况的错误，但我感觉不加也可以。

4. 最小的k个数

• 题目描述

描述
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
限制：
0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000
原题链接

• 思路

  此题是经典的topK问题，也是面试常考的一个题；

  即给一个无序数组，找出最小(或最大)的k个数，瞬间想到的做法应该就是给数组排个序(如快排)，这样做确实没错但是并非最优解，我们可以利用堆将其优化成O(nlogk)的时间复杂度。

  面试中对于这种比较简单的算法一般会让你口述思路，下面简单说一下：

  • 将数组中的元素依次加入堆中；
  • 当堆中元素个数超过k个时，每次都要删除堆顶元素，保证堆中元素个数始终为k个；
  • 当数组元素全部遍历一遍后，堆中的这k个元素就是最小(或最大)的k个；
  • 求最小k个用最大堆，求最大k个用最小堆。
  
  

  同时，如果面试中考到topk了大概率也会问到堆，建议把堆也复习一下。

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {

        priority_queue<int> max_heap;
        for(auto x : arr) {

            max_heap.push(x);
            if(max_heap.size() > k) max_heap.pop();
        }

        vector<int> res;
        while(max_heap.size()) {

            res.push_back(max_heap.top());
            max_heap.pop();
        }
        return res;
    }
};

扩展：关于heap的考查方式一般就两种，堆排序和堆实现，下面分别给出代码

模拟堆

维护一个集合，初始时集合为空，支持如下几种操作：
1. I x，插入一个数 x；
2. PM，输出当前集合中的最小值；
3. DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
4. D k，删除第 k 个插入的数；
5. C k x，修改第 k 个插入的数，将其变为 x；
现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。
输入格式
第一行包含整数 N。
接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。
输出格式
对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。
每个结果占一行。
数据范围
1≤N≤105
?109≤x≤109
数据保证合法。

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

const int N = 100010;
int ph[N], hp[N];//映射数组
int h[N], cnt;

void heap_swap(int a, int b){
    
    swap(h[a], h[b]);
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
}

void down(int u){
    
    //找到左右孩子中最小的点，与之交换
    int t = u;
    if(2*u <= cnt && h[2*u] < h[t]) t = 2*u;
    if(2*u + 1 <= cnt && h[2*u + 1] < h[t]) t = 2*u + 1;
    if(t != u) {
        
        heap_swap(u, t);
        down(t);
    }
}

void up(int u){
    
    while(u / 2 && h[u] < h[u / 2]){
        
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

int main(){
    
    cin.tie();
    ios::sync_with_stdio(false);
    int n, m = 0;
    
    cin >> n;
    while(n --){
        
        string op;
        int k, x;
        
        cin >> op;
        if(op == "I"){
            
            cin >> x;
            h[++ cnt] = x;
            
            //更新ph, hp
            ph[++ m] = cnt, hp[cnt] = m;//***注意：这个一定要在up操作之前，先更新ph和hp再up
            up(cnt);
        }
        else if(op == "PM") cout << h[1] << endl;
        else if(op == "DM") {
            
            heap_swap(1, cnt --);
            down(1);
        }
        else if(op == "D"){
            
            cin >> k;
            k = ph[k];
            heap_swap(k, cnt --);
            up(k);
            down(k);
        }
        else{
            
            cin >> k >> x;
            k = ph[k];
            h[k] = x;
            up(k);
            down(k);
        }
    }
    
    return 0;
}

堆排序

输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
int n, m;
int h[N], cnt;

void down(int u) {
    
    int t = u;
    if(2*u <= cnt && h[2*u] <= h[t]) t = 2*u;
    if(2*u + 1 <= cnt && h[2*u + 1] <= h[t]) t = 2*u + 1;
    if(t != u) {
        
        swap(h[t], h[u]);
        down(t);
    }
}

int main() {
    
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) {
        
        int x;
        cin >> x;
        h[i] = x;
    }
    cnt = n;
    
    for(int i = n / 2; i; i --) 
        down(i);
        
    while(m --) {
        
        cout << h[1] << " ";
        h[1] = h[cnt --];
        down(1);
    }
    
    return 0;
}

5. 数据流中的中位数

• 题目描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如：
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
原题链接

• 思路

  这道题利用了topK问题的思想，创建两个堆构成的数据结构来维护当前加入的数据，这两个堆分别为大根堆和小根堆。在元素加入该数据结构的过程中，这两个堆需要平衡各自维护的元素数量以及元素性质，也就是说需要遵循一定规则，规则就是：大根堆存较小的一半元素，小根堆存较大的另一半元素。因为这个元素的个数是奇偶不确定的，所以这个一半的限制是有讲究的 (具体看代码实现)；

  这个方法是不容易想出来的，但我们至少要搞清楚为什么采用上述的双堆结构能找到中位数？

  根据当前维护元素个数的奇偶分别讨论：（假设当前元素个数为n）

  • 当元素个数为奇数时，那么元素个数就无法等分，因此让大根堆存(n+1)/2个元素，让小根堆存剩下的 元素。来看看此时大根堆的堆顶元素max_heap_top满足什么样的性质，max_heap_top大于大根堆中的其余所有元素，同时max_heap_top也小于小根堆中的所有元素。原来如此！这个max_heap_top不就是我们要寻找的中位数嘛；
  • 当元素个数为偶数时，元素个数可以等分，正好大根堆和小根堆都拥有n/2个元素，显然大根堆堆顶max_heap.top和小根堆堆顶min_heap_top就是当前所有元素排序后位于中间位置的两个元素，中位数就是(max_heap_top + min_heap_top) / 2。
  
  下面是代码实现：

class MedianFinder {
public:

    priority_queue<int> max_heap;
    priority_queue<int, vector<int>, greater<int>> min_heap;
    /** initialize your data structure here. */
    MedianFinder():max_heap(), min_heap() {

    }
    
    void addNum(int num) {

        max_heap.push(num);

        //限制小根堆存的是较大的一半元素，大根堆存的是较小的一半元素
        while(min_heap.size() && min_heap.top() < max_heap.top()) {

            auto min = min_heap.top(), max = max_heap.top();
            max_heap.pop(), min_heap.pop();
            min_heap.push(max), max_heap.push(min);
        }

        //限制两个堆中的元素数量
        if(max_heap.size() > min_heap.size() + 1) {
            
            min_heap.push(max_heap.top());
            max_heap.pop();
        }
    }
    
    double findMedian() {

        if((max_heap.size() + min_heap.size()) & 1) return max_heap.top();
        return (max_heap.top() + min_heap.top()) / 2.0;
    }
};

在面试考查中，一般不会求数据流的中位数，更多的是求无序序列的中位数。如果是静态序列的话就不需要双堆结构来维护了，用一个堆就可以找到中位数，此时就变成了topK问题。

6. 滑动窗口的最大值

• 题目描述

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
解释: 

  滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
原题链接

• 思路

  此题考查单调队列，在窗口滑动的过程中这些数组元素存在这么一种性质：如果后进入窗口的元素大于等于前面的元素，那么前面的这些元素不可能是滑动窗口的最大值（现在以及将来），所以这些元素对结果没有意义就无需保留，我们可以用双端队列维护一个滑动窗口。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {

        vector<int> res;
        deque<int> q;
        for(int i = 0; i < nums.size(); i ++) {

            while(q.size() && q.front() <= i - k) q.pop_front();
            while(q.size() && nums[q.back()] <= nums[i]) q.pop_back();
            q.push_back(i);
            if(i >= k - 1) res.push_back(nums[q.front()]);
        }
        return res;
    }
};

7. 数组中数字出现的次数I

• 题目描述

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

限制：
2 <= nums.length <= 10000
原题链接

• 思路

  根据题目特点，序列中除了两个数之外剩下均是成对出现，因此可以用异或来解决此题。

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {

        int sum = 0;
        for(auto num : nums) 
            sum ^= num; // sum = x ^ y

        int k = 0;
        while(!(sum >> k & 1)) // 找到1
            k ++;

        int part1 = 0;
        for(auto num : nums)
            if(num >> k & 1)
                part1 ^= num; // 最后剩的一定是两个数中第k位为1的那个数

        return vector<int>{part1, part1 ^ sum};
    }
};

8. 数组中数字出现的次数II

• 题目描述

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

输入：nums = [3,4,3,3]
输出：4

示例 2：

输入：nums = [9,1,7,9,7,9,7]
输出：1

限制：
1 <= nums.length <= 10000
1 <= nums[i] < 2^31
原题链接

• 思路

  此题和上一道只出现一次的两个数字属于同一类型，这一类题目从宏观上难以入手一般通过二进制来解决；

  对于本题来说，如果从数的二进制表示考虑，可以发现对于所有数每一位出现1的总次数只存在两种情况：3的倍数+1和3的倍数。对于情况一，这多出来的1一定属于这个只出现一次的数字；对于情况二，这个只出现一次的数字该位应该为0。因此我们遍历二进制表示的所有位，自然会得到这个只出现一次的数字。

class Solution {
public:
    int singleNumber(vector<int>& nums) {

        int res = 0;
        for(int i = 31; i >= 0; i --) {

            int cnt = 0;
            for(auto num : nums) 
                if(num >> i & 1)
                    cnt ++;
            if(cnt % 3)
                res = res * 2 + 1;
            else
                res = res * 2;
        }
        return res;
    }
    
};

9. 和为s的连续正数序列

• 题目描述

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
原题链接

示例 1：

输入：target = 9
输出：[[2,3,4],[4,5]]

示例 2：

输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

限制：
1 <= target <= 10^5

• 思路

  先想一个暴力解法。如何确定一个连续正整数序列呢？确定它的左右边界就可以了，因此我们可以枚举左右边界的所有情况，但这样做的时间复杂度是O(n^2)一定会超时的；

  这时候就需要看看暴力做法中枚举左右边界的所有情况是否都是有意义的。假设左右边界为[i, j]，随着i的推进j也必须向右推进，因为只有这样才能保证区间和恒为target，因此左右边界只需要分别扫描一遍即可，时间复杂度为O(2n)。

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {

        vector<vector<int>> res;
        for(int i = 1, j = 1, s = 1; i <= target; i ++) {

            vector<int> tmp;
            while(s < target) s += ++ j;
            if(s == target && j - i + 1 > 1) {

                for(int k = i; k <= j; k ++)
                    tmp.push_back(k);
                res.push_back(tmp);
            } 
            s -= i;
        }
        return res;
    }
};

10. 扑克牌顺子

• 题目描述

从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
原题链接

示例 1:

输入: [1,2,3,4,5]
输出: True

示例 2:

输入: [0,0,1,2,5]
输出: True

限制：
数组长度为 5
数组的数取值为 [0, 13] .

• 思路

  此题的大小王很具迷惑性，其实根本不需要考虑这两个牌是否在我们的手牌里，因为这两张牌可以替代任何一个数，所以我们可以将这两个牌想象成一个可以随机设置的数字牌；

  因此，此题只需要关心手牌里数字牌的最大数字和最小数字的差值就可以了，只要差值不超过4手牌一定是一个顺子。假设差值是5，那么[5, 10]必须是5, 6, 7, 8, 9, 10才能构成一个顺子，但显然此时是6张牌了与条件矛盾。

class Solution {
public:
    bool isStraight(vector<int>& nums) {

        if(nums.empty()) return false;

        std::sort(nums.begin(), nums.end());
        int k = 0;
        while(nums[k] == 0) k ++; //去0

        for(int i = k + 1; i < nums.size(); i ++)
            if(nums[i] == nums[i - 1])
                return false;

        return nums.back() - nums[k] <= 4;
    }
};

11. 矩阵中的路径

• 题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
原题链接

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false

提示：
1 <= board.length <= 200
1 <= board[i].length <= 200
board 和 word 仅由大小写英文字母组成

• 思路

  根据题目要求，只要网格中存在任意一条这样的路径等于word即可，对于路径问题基本上离不开dfs和bfs，但到底何时使用dfs或者bfs呢？本人简单总结了一下：

  • dfs 一般用于寻找问题的全部解或者任意一个解，因为dfs的目的就是单纯地找到解决方案而已，所以也把dfs叫做暴搜；
  • bfs 找到问题解的同时所经历步数一定是最少的，因此一般利用bfs的这种性质解决最短路径问题。
  
  

  就本题而言，找到任意一条路径就可以返回，dfs显然比bfs更快些，因为dfs是一条道走到黑的，如果足够幸运只遍历一次就可以找到答案，相反就需要不断回溯寻找其他路径。

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {

        for(int i = 0; i < board.size(); i ++)
            for(int j = 0; j < board[i].size(); j ++) 
                if(dfs(board, word, 0, i, j))
                    return true;
        return false;
    }

    bool dfs(vector<vector<char>> &board, string &word, int u, int x, int y) {
        
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
        if(word[u] != board[x][y]) return false;
        if(u == word.size() - 1) return true;

        char t = board[x][y];
        board[x][y] = '*';
        for(int i = 0; i < 4; i ++) {

            int a = x + dx[i], b = y + dy[i];
            if(a >= 0 && a < board.size() && b >= 0 && b < board[a].size())
                if(dfs(board, word, u + 1, a, b))
                    return true;
        }

        board[x][y] = t;
        return false;   
    }
};

12. 机器人的运动范围

• 题目描述

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
原题链接

示例 1：

输入：m = 2, n = 3, k = 1
输出：3

示例 2：

输入：m = 3, n = 1, k = 0
输出：1

提示：
1 <= n,m <= 100
0 <= k <= 20

• 思路

  此题和矩阵中的路径都属于搜索类问题，上一题中讲到了dfs的应用场景，dfs一般用于枚举所有情况或求任意一种情况，bfs的应用场合和dfs有所不同：

  • bfs是一种地毯式搜索，bfs对每个满足条件的点都会扩展到相邻的所有点，直到遍历完所有满足条件的点为止
  
  

  bfs的一个重要特点就是扩散，但它很难确定一条具体的路径，所以它一般用于求一些关于数量的题目，而dfs是可以定位一条具体路径的，解题时可以根据两者的区别选择合适的方法。

  ps：同时bfs是有模板的，写法上有一定套路，而dfs的写法多变难度较大。

  就本题而言，无论运动范围还是求格子个数等关键词都将解题方法指向bfs。

class Solution {
public:

    int getnum(pair<int, int> t) {

        int sum = 0;
        while(t.first) {
            
            sum += t.first % 10;
            t.first /= 10;
        }
        while(t.second) {
            
            sum += t.second % 10;
            t.second /= 10;
        }
        return sum;
    }

    int movingCount(int m, int n, int k) {

        int res = 0;
        if(!m || !n) return 0;

        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
        vector<vector<bool>> st(m, vector<bool>(n, false));
        queue<pair<int, int>> q;
        
        q.push({0, 0});
        while(q.size()) {

            auto t = q.front();
            q.pop();
            if(st[t.first][t.second] || getnum(t) > k) continue;
            res ++;
            st[t.first][t.second] = true;

            for(int i = 0; i < 4; i ++) {

                int a = t.first + dx[i], b = t.second + dy[i];
                if(a >=  0 && a < m && b >= 0 && b < n) q.push({a, b}); 
            } 
        }
        return res;
    }
};