DW数据结构与算法学习任务----Task01：数组_综合

Task01：数组（1天）

理论部分

理解数组的存储与分类
实现动态数组，该数组能够根据需要修改数组的长度

答1：数组元素在内存中顺次存放，它们的地址是连续的。元素间物理地址上的相邻，对应着逻辑次序上的相邻。

练习部分

1.利用动态数组解决数据存放问题

编写一段代码，要求输入一个整数N，用动态数组A来存放2~N之间所有5或7的倍数，输出该数组。

示例：

输入：
N = 100 输出：
5 7 10 14 15 20 21 25 28 30 35 40 42 45 49 50 55 56 60 63 65 70 75 77 80 84 85 90 91 95 98 100

思路：用Vector容器

#include <iostream>
#include <vector>using namespace std;int main()
{
    int n;vector<int> v;cin >> n;for(int i=5;i<=n;i++){
    if(i%5==0||i%7==0){
    v.push_back(i); }}vector<int>::iterator it=v.begin() ;for(;it!=v.end();it++){
    cout << *it << " ";}return 0;//时间复杂度：O(n)
}

2.托普利茨矩阵问题

如果一个矩阵的每一方向由左上到右下的对角线上具有相同元素，那么这个矩阵是托普利茨矩阵。

给定一个M x N的矩阵，当且仅当它是托普利茨矩阵时返回True。

示例：

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

解释:

在上述矩阵中, 其对角线为: "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]"。各条对角线上的所有元素均相同, 因此答案是True。

思路：二维Vector

bool isToeplitzMatrix(vector<vector<int>>& matrix) 
{
    int m = matrix.size();int n = matrix[0].size();for(int i = 0; i < m-1; ++i) {
    for(int j = 0; j < n-1; ++j) {
    if(matrix[i][j] != matrix[i+1][j+1]) {
    return false;}}}return true;//时间复杂度：O(n2)
}

3.三数之和

给定一个包含 n 个整数的数组nums，判断nums中是否存在三个元素a，b，c，使得a + b + c = 0？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：
[[-1, 0, 1],[-1, -1, 2]
]

思路：如何保证不可重复（提前排序），然后简化问题，选定一个元素，从后面找到能和这个元素匹配为0的两个元素（L,R），因为有序所以根据大小来标定L,R是否移动

class Solution {
    
public:vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(),nums.end());int target;vector<vector<int>> threesum;for(int i=0;i<nums.size();i++){
    if(i>0&&nums[i]==nums[i-1]) continue;if((target=nums[i])>0) break;int l=i+1;int r=nums.size()-1;while(l<r){
    if(target+nums[l]+nums[r]>0) r--;else if(target+nums[l]+nums[r]<0) l++;else{
    threesum.push_back({
    target,nums[l],nums[r]});l++;r--;while((nums[l]==nums[l-1])&&l<r) l++;while((nums[r]==nums[r+1])&&r>l) r--;}}}return threesum;}
};