浙大数据结构-第一讲

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cmath>

using namespace std;
// 例2：递归暂用内存非常大（空间复杂度大）
void PrintN1(int n) {
    for(int i=1; i<n; i++) printf("%d ", i);
}
void PrintN2(int n) {
    if(!n) return;
    PrintN2(n-1);
    printf("%d ", n);
}
// 例3：多项式秦九zhao算法
// 多项式 f(x) = a[0] + a[1]x + a[2]x^2 + ... + a[n]x^n
double f(int n, double a[], double x) {
    double res = 0;
    for(int i=n; i >= 0; i--) {
        res = res * x + a[i];
    }
    return res;
}
// 时间复杂度大
double f2(int n, double a[], double x) {
    double p = a[0];
    for (int i=1; i<=n; i++) {
        p += (a[i] * pow(x, i));
    }
    return p;
}
// 测试函数
void testF() {
    cout << CLK_TCK; // 在ctime中，1000，表示一秒钟有多少个计数单元
    clock_t start, stop; // typedef long clock_t
    double duration;
    start = clock();
    double arr[4]{1.0, 2.0, 4.0, 3.0};
    cout << f(3, arr, 2.0); // 1 + 2*2 + 4*4 + 3*8 = 45
    stop = clock();
    duration = ((double)(stop - start)) / CLK_TCK;
    cout << duration << "秒\n";
    // 扩展
    long long curTime = time(NULL); // 获取1970年到现在的秒数
}
// 复杂度关心的是随着数据规模的增大，算法的数量级。
void test1() {
    // 时间复杂度O(N^3);
    int A,B,N; cin >> A >> B >> N;
    if (A > B) {
        for (int i=0; i<N; i++) {
            for (int j=N*N; j>i; j--) A += B;
        }
    } else {
        for (int i=0; i<N*2; i++) {
            for (int j=0; j<N*2; j++) A += B;
        }
    }
}
int main() {

}

• 最后讲了个连续子数组的最大和的三种写法

• 在线查找

  class Solution {
  public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int cur = 0;
        for(int n : nums) {
            cur += n;
            res = max(res, cur);
            if(cur < 0) cur = 0;
        }
        return res;
    }
  };

• 分治法

  class Solution {
  public:
    int maxSubArray(vector<int>& nums) {
        return help(nums, 0, nums.size() - 1);
    }
  
    int help (vector<int>& v, int left, int right) {
        // 递归中止条件
        if(left > right) return INT_MIN;
        if(left == right) return v[left];
  
        // 使用分治法
        int mid = (left + right) / 2;
        // 分别判断没有mid的左右子问题
        int leftRes = help(v, left, mid-1);
        int rightRes = help(v, mid+1, right);     
        // 判断包含mid的情况
        int leftSum = 0, curLeftSum=0, rightSum = 0, curRightSum = 0, leftIdx = mid-1, rightIdx = mid+1;
        while(leftIdx >= left) {
            curLeftSum += v[leftIdx--];
            leftSum = max(leftSum, curLeftSum);
        }
        while(rightIdx <= right) {
            curRightSum += v[rightIdx++];
            rightSum = max(rightSum, curRightSum);
        }
        int midRes = v[mid] + (leftSum>0?leftSum:0) + (rightSum>0?rightSum:0);
        return max(max(leftRes,rightRes),midRes);
    }
  };