LeetCode Day4

LeetCode Day4

数组

¶有序数组的平方

/* 其实昨天已经写过了 */
/* 这里就看看不同的方法吧 */

/* 暴力排序 */
/* 时间复杂度为 O(nlogn) */
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++)
            nums[i] *= nums[i];
        sort(nums.begin(), nums.end()); // 快速排序
        return nums;
    }
};

/* 双指针法，但是换个思路 */
/* 先找最大的 */
class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int k = A.size() - 1;
        vector<int> result(A.size(), 0);
        for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要i <= j，因为最后要处理两个元素
            if (A[i] * A[i] < A[j] * A[j])  {
                result[k--] = A[j] * A[j];
                j--;
            }
            else {
                result[k--] = A[i] * A[i];
                i++;
            }
        }
        return result;
    }
};

¶长度最小的子数组

/* 暴力实现 */
/* 两个 for 循环，其时间复杂度为 O(n^2) */
/* 此代码不能通过，超时了（TLE） */
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result = INT32_MAX;
        int len = nums.size();
        int newRES = 0;
        int sum;
        for (int i = 0; i < len; i++)
        {
            sum = 0;
            for (int j = i; j < len; j++)
            {
                sum += nums[j];
                if (sum >= target)
                {
                    newRES = j - i + 1;
                    result = result > newRES ? newRES : result;
                    break;
                }
            }
        }
        return result == INT32_MAX ? 0 : result;
    }
};

/* 不超时的方法：滑动窗口法 */
/* 所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果 */
/*
对暴力方法的改进：
只用一个 for 循环，且循环的索引表示滑动窗口的终止位置
看上去其实和双指针法没有什么区别
消除了暴力方法中的一些不必要的计算

须明确：
窗口内是什么？
如何移动窗口的起始位置？
如何移动窗口的结束位置？

窗口：满足其和 ≥ target 的长度最小的连续子数组
起始位置移动：如果当前窗口的值大于 target，窗口向前移动
结束位置如何移动：窗口的结束位置就是遍历数组的指针即for循环里的索引
*/

/* 来具体实现一下 */
int minSubArrayLen(int target, vector<int>& nums) {
    int len = nums.size();
    int result = INT32_MAX;
    int sum = 0;
    int startIndex = 0, endIndex = 0;
    bool flag;
    int newRES = 0;
    for (; endIndex < len; endIndex++)
    {
        sum += nums[endIndex];
        flag = false;
        while (startIndex <= endIndex)
        {
            if (sum >= target)
            {
                flag = true;
                sum -= nums[startIndex];
                startIndex++;
            }
            else break;
        }
        if (flag) {
            newRES = endIndex - startIndex + 2;
            result = result > newRES ? newRES : result;
        }
    }
    return result == INT32_MAX ? 0 : result;
}

/* 看看正规的滑动窗口代码 */
int minSubArrayLen(int target, vector<int>& nums) {
    int result = INT32_MAX;
    int sum = 0; // 滑动窗口数值之和
    int i = 0; // 滑动窗口起始位置
    int subLength = 0; // 滑动窗口的长度
    for (int j = 0; j < nums.size(); j++) {
        sum += nums[j];
        // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
        while (sum >= target) {
            subLength = (j - i + 1); // 取子序列的长度
            result = result < subLength ? result : subLength;
            sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
        }
    }
    // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
    return result == INT32_MAX ? 0 : result;
}

/*
这份代码把每个和大于 target 的子数组长度都去与 result 比较
代码精简，我的想法是用 flag 去控制一下，减少计算次数
重要的是理解其核心代码
while (sum >= target) {
    subLength = (j - i + 1); 
    result = result < subLength ? result : subLength;
    sum -= nums[i++]; 
}
*/

/* 自己写的费拉不堪的代码 */
/* 
整个过程就是模拟出题目描述的过程
然后加了一点滑动窗口（双指针） 
*/

class Solution {
public:
    struct basket{
        int type;
        int number = 0;
        bool isempty() { return number == 0; }
    };
    
    int totalFruit(vector<int>& fruits) {
        int maxfruits = INT32_MIN;
        int len = fruits.size();
        int startIndex = 0, endIndex = 0;
        int pushElem, popElem;
        int newResult;
        basket B1, B2;
        for (; endIndex < len; endIndex++)
        {
            pushElem = fruits[endIndex];
            if (B1.isempty() && B2.isempty()) { B1.type = pushElem; B1.number++; }
            else if (B1.isempty()) 
            {
                if (pushElem != B2.type) { B1.type = pushElem; B1.number++; }
                else B2.number++;
            }
            else if (B2.isempty()) 
            {
                if (pushElem != B1.type) { B2.type = pushElem; B2.number++; }
                else B1.number++;
            }
            else
            {
                if (pushElem == B1.type) B1.number++;
                else if (pushElem == B2.type) B2.number++;
                else 
                {
                    newResult = B1.number + B2.number;
                    maxfruits = maxfruits > newResult ? maxfruits : newResult;
                    while (!B1.isempty() && !B2.isempty())
                    {
                        popElem = fruits[startIndex];
                        if (popElem == B1.type) B1.number--;
                        if (popElem == B2.type) B2.number--;
                        startIndex++;
                    }
                    if (B1.isempty()) { B1.type = pushElem; B1.number++; }
                    if (B2.isempty()) { B2.type = pushElem; B2.number++; }
                }
            }
        }
        newResult = B1.number + B2.number;
        maxfruits = maxfruits > newResult ? maxfruits : newResult;
        return maxfruits;
    }
};

/*
为什么自己写的这么复杂，其实写的时候就发现了
没有想出用什么数据结构来写，所以就硬写
看了官方的题解才知道用哈希表
哈希表可以同时存储窗口内的数（代表水果类型）以及出现的次数
哈希表中出现超过两个键值对时就不满足条件了
此时开始移动窗口的起始位置，并进行删除
直至哈希表中只有两个键值对
*/

/* 官方题解 */

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int n = fruits.size();
        unordered_map<int, int> cnt;

        int left = 0, ans = 0;
        for (int right = 0; right < n; ++right) {
            ++cnt[fruits[right]];
            while (cnt.size() > 2) {
                auto it = cnt.find(fruits[left]);
                --it->second;
                if (it->second == 0) {
                    cnt.erase(it);
                }
                ++left;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};