【算法作业】数字流中比x小的元素个数,顺时针打印旋转矩阵元素

问题描述

1. 要求一串整数流在尽可能短的时间内求得已读取的数字流中比x 小的元素个数。注意是数据流的问题，所以要考虑新元素的加入与求解个数的影响。

2. 顺时针打印旋转矩阵元素。

解题思路

T1

1. 方法一：

在C++中，你可以使用STL中的std::set或std::multiset来实现这样的数据结构。它们底层通常是基于平衡二叉搜索树实现的，可以高效地插入、删除和查找元素。

2. 方法二：

手撕平衡二叉搜索树

1. 首先，我们定义了一个 Node 结构体，用于表示二叉搜索树的节点。每个节点包含一个整数值 data，表示节点的值，以及一个整数值 count，表示以该节点为根的子树中的节点个数。节点还有左右子节点的指针。

2. 然后，我们定义了一个 BST 类，用于表示二叉搜索树。这个类中包含了 root 成员变量，表示树的根节点。

3. BST 类中的 insert 方法用于向二叉搜索树中插入一个新节点。如果树为空，则创建一个新节点并将其作为根节点；否则，根据节点的值比较规则，将新节点插入到合适的位置。在插入过程中，我们还需要更新每个节点的 count 值，以反映树中节点的数量。

4. countLessThan 方法用于计算给定数 x 小的节点数。这个方法首先检查当前节点是否为空，如果是，则返回 0；否则，根据给定数 x 与当前节点的值的大小关系，递归地在左子树或右子树中查找符合条件的节点。在这个过程中，我们利用了二叉搜索树的性质：左子树中的所有节点都小于当前节点的值，右子树中的所有节点都大于或等于当前节点的值。因此，如果给定数 x 小于当前节点的值，则递归地在左子树中查找；否则，需要考虑当前节点以及右子树中比 x 小的节点数。

T2

没看懂这题的言外之意，于是就用纯模拟来做，如果模拟4个方向，边走边标记。如果撞墙了就停下来，后退一步转个方向。

完整代码

T1

1. 方法一：

#include <iostream>
#include <set>

using namespace std;

int countElementsLessThan(const multiset<int>& elements, int x) {
    // 使用lower_bound找到第一个大于等于x的元素的迭代器
    multiset<int>::iterator it = elements.lower_bound(x);
    // 返回x之前的元素个数
    return distance(elements.begin(), it);
}

int main() {
    multiset<int> elements; // 用于存储数字流的数据结构

    // 输入数字流，每次输入一个数字后，输出当前已读取数字流中比给定数 x 小的元素个数
    int x;
    while (cin >> x) {
        elements.insert(x);
        int count = countElementsLessThan(elements, x);
        cout << "Number of elements less than " << x << " is: " << count << endl;
    }

    return 0;
}

2. 方法二：

#include <iostream>

using namespace std;

struct Node {
    int data;
    int count; // 记录以该节点为根的子树中的节点个数
    Node* left;
    Node* right;
    
    Node(int value) : data(value), count(1), left(NULL), right(NULL) {}
};

class BST {
private:
    Node* root;

    // 插入节点
    Node* insert(Node* node, int value) {
        if (node == NULL) {
            return new Node(value);
        }

        if (value < node->data) {
            node->left = insert(node->left, value);
        } else {
            node->right = insert(node->right, value);
        }

        node->count++; // 更新节点的计数

        return node;
    }

    // 计算比给定数小的节点数

	int countLessThan(Node* node, int x) {
	    if (node == NULL) {
	        return 0;
	    }
	
	    if (x <= node->data) {
	        return countLessThan(node->left, x);
	    }
	
	    return node->count - (node->right ? node->right->count : 0) + countLessThan(node->right, x);
	}


public:
    BST() : root(NULL) {}

    // 插入值
    void insert(int value) {
        root = insert(root, value);
    }

    // 获取比给定数小的节点数
    int countLessThan(int x) {
        return countLessThan(root, x);
    }
};

int main() {
    BST bst;

    // 输入数字流，每次输入一个数字后，输出当前已读取数字流中比给定数 x 小的元素个数
    int x;
    while (cin >> x) {
        bst.insert(x);
        int count = bst.countLessThan(x);
        cout << "Number of elements less than " << x << " is: " << count << endl;
    }

    return 0;
}

T2

#include<iostream>
using namespace std;
#define COL 4
#define ROW 3 
int main(){
    int map[3][4]={{1,2,3,4},
                   {5,6,7,8},
                   {9,10,11,12}}; 
    bool vis[3][4]={0};
    int x=0,y=0,dir=0;// 0=右，1=下，2=左，3=上 
    int count = 0;
    while(count < ROW * COL){
        switch (dir){
            case 0:
                while(y < COL && vis[x][y] == 0){
                    cout<<map[x][y]<<"->";
                    vis[x][y]=1;
                    count++;
                    y++;//向右走
                }
                y--; // 回退到合法范围内
                x++; // 行数加1
                break;
            case 1:
                while(x < ROW && vis[x][y] == 0){
                    cout<<map[x][y]<<"->";
                    vis[x][y]=1;
                    count++;
                    x++;//向下走
                }
                x--; // 回退到合法范围内
                y--; // 列数减1
                break;
            case 2:
                while(y >= 0 && vis[x][y] == 0){
                    cout<<map[x][y]<<"->";
                    vis[x][y]=1;
                    count++;
                    y--;//向左走
                }
                y++; // 回退到合法范围内
                x--; // 行数减1
                break;
            case 3:
                while(x >= 0 && vis[x][y] == 0){
                    cout<<map[x][y]<<"->";
                    vis[x][y]=1;
                    count++; 
                    x--;//向上走
                }
                x++; // 回退到合法范围内
                y++; // 列数加1
                break;
        }
        dir = (dir + 1) % 4;
    }  
	cout<<"over";       
    return 0;
}