[数据结构与算法]数据结构leetcode——day3

350. 两个数组的交集 II

思路：双指针+排序 有序过后 利用双指针同步比较，不同则较小的往前走继续比较，相同就写入数组，两指针同时走比较下一位
（记录下qsort中cmp函数，int cmp(const void *a, const void *b)
返回正数就是说 cmp 传入参数第一个要放在第二个后面, 负数就是传入参数第一个要放第二个前面, 如果是 0, 那就无所谓谁前谁后.
所以更具体的也可以这么写

int cmp(const void* _a, const void* _b) {
    int *a = _a, *b = (int*)_b;
    return *a == *b ? 0 : *a > *b ? 1 : -1;
}

c语言代码如下

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int cmp(const void* _a, const void* _b) {
    int *a = _a, *b = (int*)_b;
    return *a - *b;
}

int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size,
               int* returnSize) {
    //先对两个数组进行从小到大排序
    qsort(nums1, nums1Size, sizeof(int), cmp);
    qsort(nums2, nums2Size, sizeof(int), cmp);
    *returnSize = 0;
    int* intersection = (int*)malloc(sizeof(int) * fmin(nums1Size, nums2Size));
    int index1 = 0, index2 = 0;
    while (index1 < nums1Size && index2 < nums2Size) {
        //如果不同，则较小的那个往前走
        if (nums1[index1] < nums2[index2]) {
            index1++;
        } else if (nums1[index1] > nums2[index2]) {
            index2++;
        } else {
            intersection[(*returnSize)++] = nums1[index1];
            index1++;
            index2++;
        }
    }
    return intersection;
}

方法二：哈希
利用哈希表统计出现次数，然后在第二个数组中再一一对应，有相同的对应次数就减1 并写入数组 直至为0 （说明无相同的)

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if (nums1.size() > nums2.size()) {
            return intersect(nums2, nums1);
        }
        unordered_map <int, int> m;
        for (int num : nums1) {
            ++m[num];
        }
        vector<int> intersection;
        for (int num : nums2) {
            if (m.count(num)) {
                intersection.push_back(num);
                --m[num];
                if (m[num] == 0) {
                    m.erase(num);
                }
            }
        }
        return intersection;
    }
};

121. 买卖股票的最佳时机

标准动态规划题目 ，最大利润即在最低点买 记录最低价格，分别记录在第i天卖的收益，最后返回dp[n-1]

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0; // 边界条件
        int minprice = prices[0];
        vector<int> dp (n, 0);

        for (int i = 1; i < n; i++){
            minprice = min(minprice, prices[i]);
            dp[i] = max(dp[i - 1], prices[i] - minprice);
        }
        return dp[n - 1];
    }
};