数据结构-数组知识理论

• 数组
• • 定义
  • 基础操作
  • • 访问
    • 添加
    • 删除
  • 习题
  • • 力扣 704
    • 力扣 27
    • 力扣 977
    • 力扣 209
    • 力扣 59

数组是一组存放在内存中的，地址连续的相同类型数据的集合

数组可以直接通过下标进行访问，地址从0开始。以c++为例，可以直接nums[i]访问nums数组中的第i位。在编程语言中的下标都是从0开始的。

在数组中想要在第i位添加元素，并没有想象中这么简单

// 第一步判断数组长度是否足够：若长度不够需要扩展数组的长度
// 是否在末尾添加元素，若不是则需要将其他的元素后移

// 在删除中与添加也类似，不过并不需要考虑容量问题
// 但是需要考虑删除之后后面元素的前移问题

习题地址
这是一个简单的二分查找的题目，也是比较基础的题目，在做这个题目的时候需要考虑清楚当前位置查找的不对时下一步要怎么做，防止出现死循环的问题，这与while中的判断条件以及两侧值的变化方式有关。
下面给出代码

class Solution {
public:
    int search(vector& nums, int target) {
        int i = 0, j = nums.size() - 1;
        int find = (i + j) / 2;
        while (i <= j)
        {
            find = (i + j) / 2;
            if (nums[find] == target)
            {
                return find;
            }
            else
            {
                if (nums[find] > target)
                {
                    j = find - 1;
                }
                else
                {
                    i = find + 1;
                }
            }
        }
        return -1;
    }
};

有不懂的小伙伴也可以看代码随想录的题解哦

题目
本题就是最基本的数组的删除问题，也是数组的一个基本操作，不会的朋友仔细西靠一下哦

class Solution {
public:
    int removeElement(vector& nums, int val) {
        if (nums.size() == 0) return 0;
        int j = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if (nums[i] != val)
            {
                nums[j] = nums[i];
                j++;
            }
        }
        return j;
    }
};

方法的思路就是，通过一个for循环不断的向前遍历，在遍历的同时判断这个位置上的数是否需要删除，若不需要删除则放到现在j的位置上，然后j向前移动一位。

题目
这题需要使用双指针的方法，首先从数列中找到绝对值最小的值所在的位置，然后向两侧遍历，不断向新数组中加入较小绝对值的平方即可

class Solution {
public:
    vector sortedSquares(vector& nums) {
        int j = 0;
        for (int i = 1; i < nums.size(); i++)
        {
            if (abs(nums[i]) < abs(nums[j])) j = i;
        }
        vector newNums;
        newNums.push_back(nums[j] * nums[j]);
        int p = j - 1;
        int q = j + 1;
        while (p >= 0 || q < nums.size()) {
            if (p < 0) {
                newNums.push_back(nums[q] * nums[q]);
                q++;
            }
            else {
                if (q >= nums.size()) {
                    newNums.push_back(nums[p] * nums[p]);
                    p--;
                }
                else {
                    if (abs(nums[q] < abs(nums[p]))) {
                        newNums.push_back(nums[q] * nums[q]);
                        q++;
                    }
                    else {
                        newNums.push_back(nums[p] * nums[p]);
                        p--;
                    }
                }
            }
        }
        return newNums;
    }
};

题目
这题主要是一个区间问题，所以使用滑动窗口的方法，当窗口中的和大于目标就减去前面的一个数，小于的时候就加上后面的一个数

class Solution {
public:
    int minSubArrayLen(int target, vector& nums) {
        int all = nums[0];
        int i = 0, j = 1;
        int ans = 100010;

        while (true) {
            if (all >= target) {
                ans = min(ans, j - i);
                all -= nums[i];
                i++;
            }
            else {
                if (j == nums.size()) {
                    break;
                }
                all += nums[j];
                j++;
            }
        }
        if (ans == 100010)return 0;
        else return ans;
    }
};

题目
这是一个模拟题，模拟他的要求就可以了

class Solution {
public:
    vector> generateMatrix(int n) {
        vector> obj(n); 
        for (int i = 0; i < obj.size(); i++)
        {
            obj[i].resize(n);
        }
        int p = 0, q = 0;
        int  aa[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
        int t = 0;
        for (int i = 1; i <= n * n; i++) {
            obj[p][q] = i;
            if (p + aa[t][0] >= n || p + aa[t][0] < 0|| q + aa[t][1] >= n || q + aa[t][1] < 0 || obj[p + aa[t][0]][q + aa[t][1]] != 0) t = (t + 1) % 4;
            p = p + aa[t][0];
            q = q + aa[t][1];
        }
        return obj;
    }
};