Skip to content

Latest commit

 

History

History
181 lines (154 loc) · 4.72 KB

数组.md

File metadata and controls

181 lines (154 loc) · 4.72 KB
Raw

数组理论基础

  1. 数组是存放在连续内存空间上的相同类型数据的集合
  2. 数组下标都是从 $0$ 开始且数组内存空间的地址是连续的
  3. 正是因为数组的在内存空间的地址是连续的，所以数组添加和删除元素是不方便的
  4. 在 c++ 中 vector 的底层实现是 array，严格来讲 vector 是容器，不是数组，数组的元素是不能删的，只能覆盖，STL 中的 erase 函数实际上是将需要删除的元素覆盖掉，再 resize 整个容器的大小释放掉被删除元素的空间，减小 vector 的大小，是一个 $O(n)$ 的操作

数组中常见的面试题型

  1. 暴力枚举
  2. 双指针算法（见双指针算法总结）
  3. 螺旋矩阵问题

数组题型

leetcode.54 螺旋矩阵

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        vector<int> res;
        vector<vector<bool>> st(n, vector<bool>(m, false));
        // x 表示行，y 表示列
        // 向右移动 x 不变 y+1 
        // 向下移动 y 不变 x+1
        // 向左移动 x 不变 y-1
        // 向上移动 y 不变 x-1
        int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

        for (int i = 0, x = 0, y = 0, d = 0; i < n * m; i ++){
            // 将(0, 0)加入答案，并将当前格子状态更新
            res.push_back(matrix[x][y]);
            st[x][y] = true;
            // (a, b)表示下一个位置
            int a = x + dx[d], b = y + dy[d];
            // 如果(a, b)出界了，或者(a, b)格子走过了，则需要转向
            if (a < 0 || a >= n || b < 0 || b >= m || st[a][b]){
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;
        }
        return res;
    }
};

leetcode.54 ACM 模式

第一行表示 $n$ 行 $m$ 列的矩阵，后面 $n$ 行每行表示具体的数，按照顺时针螺旋顺序，返回矩阵中的所有元素

输入样例

3 4
1 2 3 4
5 6 7 8
9 10 11 12

输出样例

1 2 3 4 8 12 11 10 9 5 6 7

解题代码

#include <iostream>

using namespace std;

const int N = 110;

int n, m;
int a[N][N];
bool st[N][N];

int main(){
    cin >> n >> m;
    
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            cin >> a[i][j];
    
    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
    
    for (int i = 0, x = 0, y = 0, d = 0; i < m * n; i ++){
        cout << a[x][y] << ' ';
        st[x][y] = true;
        int a = x + dx[d], b = y + dy[d];
        if (a < 0 || a >= n || b < 0 || b >= m || st[a][b]){
            d = (d + 1) % 4;
            a = x + dx[d], b = y + dy[d];
        }
        x = a, y = b;
    }
    
    return 0;
}

leetcode.59 螺旋矩阵 II

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n));
        int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

        for (int i = 1, x = 0, y = 0, d = 0; i <= n * n; i ++){
            res[x][y] = i;

            int a = x + dx[d], b = y + dy[d];
            if (a < 0 || a >= n || b < 0 || b >= n || res[a][b]){
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;
        }
        return res;
    }
};

leetcode.54 ACM 模式

第一行表示正整数 $n$
后面 $n$ 行表示生成的 $1$ 到 $n^2$ 的螺旋矩阵

输入样例

3

输出样例

1 2 3 
8 9 4 
7 6 5

解题代码

#include <iostream>

using namespace std;

const int N = 110;

int n;
int res[N][N];

int main(){
    cin >> n;
    
    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
    
    for (int i = 1, x = 0, y = 0, d = 0; i <= n * n; i ++){
        res[x][y] = i;
        
        int a = x + dx[d], b = y + dy[d];
        if (a < 0 || a >= n || b < 0 || b >= n || res[a][b]){
            d = (d + 1) % 4;
            a = x + dx[d], b = y + dy[d];
        }
        x = a, y = b;
    }
    
    for (int i = 0; i < n; i ++){
        for (int j = 0; j < n; j ++){
            cout << res[i][j] << ' ';
        }
        puts("");
    }
        
    return 0;
}