zkkKillua's Blog
0%

发表于 分类于

1. 滑动窗口

题目中要求的是“子数组”，但实际上是要求连续的“子串”。
因此可以使用滑动窗口，固定左侧，右侧在满足“湍流”条件的情况下向右移动，直到不满足条件，记录此时子数组的长度。
取长度的最大值，然后重新开始窗口的滑动。
由于当前窗口内的子数组满足“湍流”条件，因此该子数组的任意子数组也满足“湍流”条件，故调整窗口左侧到右侧位置，以窗口最后一个元素作为下一个窗口新开始的元素。
时间O(n)，空间O(1)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        int n = arr.size();
        if (n <= 1)
            return n;

        int len = 0, maxLen = 0;
        int left = 0, right = 1;
        bool greater = arr[1] > arr[0];

        while (right < n) {
            if ((greater && arr[right] > arr[right - 1]) || (!greater && arr[right] < arr[right - 1])) {
                right++;
                greater = !greater;
            }
            else {
                len = right - left;
                maxLen = max(maxLen, len);
                while (right < n && arr[right] == arr[right - 1])
                    right++;
                left = right - 1;
                if (right < n)
                    greater = arr[right] > arr[left];
            }
        }
        maxLen = max(maxLen, right - left);

        return maxLen;
    }
};

发表于 分类于

1. 朴素

遍历直到出现不满足非递减的情况，此时需要进行调整，然后看调整之后是否可以继续满足非递减条件。
调整时使用贪心策略，优先修改能使调整后的当前位置的元素更小。
可能遇到的情况：1 2 3 4 1 6 7 ..., 1 2 3 8 4 5 6 ...
时间O(n)，空间O(1)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int n = nums.size();
        if (n <= 2)
            return true;

        bool changed = false, res = true;
        int preLoc = 0;
        for (int i = 0; i < n; i++) {
            if (nums[i] < nums[preLoc] && changed) {
                res = false;
                break;
            } else if (nums[i] < nums[preLoc] && !changed) {
                if (preLoc == 0) 
                    preLoc = i;
                else {
                    if (nums[i] >= nums[preLoc - 1]) 
                        preLoc = i;
                }
                changed = true;
            } else 
                preLoc = i;
        }

        return res;
    }
};

发表于 分类于

1. 动态规划

由于不能贪心抽两侧最大的牌，因此考虑dp，两侧都抽，然后对剩下的部分同样进行一次“可获得的最大点数”的求解。
为了避免重复计算，使用hash表记录求解过的每一段数组的最大点数。
另外，由于hash表的key是pair类型，因此还需要手动提供pair类型的hash函数。
时间O(k^2)，空间O(k^2)，因为要求解和记录k从0到k每种情况下，对应数组段的最大点数。超时。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
struct pairhash {
public:
    template <class T, class U>
    std::size_t operator () (const std::pair<T, U>& p) const {
        // sizt_t = typeof(sizeof(x))，是sizeof()函数返回值的类型，代表目标平台下最大可能的数组尺寸
        // size_t是unsigned，保证跨平台
        std::hash<T> Thasher;
        std::hash<U> Uhasher;
        return Thasher(p.first) ^ Uhasher(p.second);
        // 使用first和second的hash值的异或作为pair的hash值
    }
};

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int n = cardPoints.size();
        // unordered_map<pair<int, int>, int> scores;
        unordered_map<pair<int, int>, int, pairhash> scores;
        subMaxScore(cardPoints, 0, n, scores, k);

        return scores[make_pair(0, n)];
    }

private:
    int subMaxScore(vector<int>& cardPoints, int beg, int end, unordered_map<pair<int, int>, int, pairhash>& scores, int k) {
        if (k == 0)
            return 0;
        
        pair<int, int> cur = make_pair(beg, end);
        if (scores.count(cur))
            return scores[cur];

        int leftScore = cardPoints[beg], rightScore = cardPoints[end - 1];
        pair<int, int> left = make_pair(beg + 1, end), right = make_pair(beg, end - 1);
        if (scores.count(left))     // 选最左元素
            leftScore += scores[left];
        else 
            leftScore += subMaxScore(cardPoints, beg + 1, end, scores, k - 1);
        if (scores.count(right))    // 选最右元素
            rightScore += scores[right];
        else 
            rightScore += subMaxScore(cardPoints, beg, end - 1, scores, k - 1);
        
        scores[cur] = max(leftScore, rightScore);
        return scores[cur];
    }
};

2. 滑动窗口

并不一定是窗口两侧初始化为数组两侧，窗口向内收缩；也可以是固定窗口大小，移动窗口位置。
因为要从n个数中选k个，因此可以固定窗口大小为n-k个，代表剩余的数据。窗口从左向右滑动，在此过程中统计结果。
时间O(k)，空间O(1)。

阅读全文 »

发表于 分类于

1. 滑动窗口

滑动窗口从左侧开始在满足cost的情况下向右滑动，记录最大窗口大小。
当cost不足以支持窗口继续向右扩展时，左侧窗口向右收缩1次，然后右侧窗口继续向右扩展。
时间O(n)，空间O(1)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int equalSubstring(string s, string t, int maxCost) {
        int n = s.length();
        int left = 0, right = 0, maxDist = 0;

        while (right < n) {
            int cost = abs(s[right] - t[right]);
            if (cost <= maxCost) {
                maxCost -= cost;
                right++;
                maxDist = max(maxDist, right - left);
            } else if (left < right) {
                maxCost += abs(s[left] - t[left]);
                left++;
            } else if (left == right) {
                left++;
                right++;
            }
        }

        return maxDist;
    }
};

发表于 分类于

1. 暴力

每移动一下窗口，就对新窗口的内容排序，得到中位数。
时间O(nklogk)，超时。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> saveNums(nums);
        int left = 0;
        vector<double> res;

        while (left + k <= n) {
            nums = saveNums;
            sort(nums.begin() + left, nums.begin() + left + k);
            int a = nums[(2 * left + k - 1) / 2], b = nums[(2 * left + k) / 2];
            res.push_back((a - b) / 2.0 + b);   // 2.0保证转换为小数，(a-b)/2.0+b避免溢出
            left++;
        }

        return res;
    }
};

2. 堆+延迟删除

由于移动窗口之后，绝大多数的数据是不变的，因此对窗口内的所有数据重新排序是很费时的。
考虑用一个大根堆和一个小根堆储存有序数组左右两侧的部分，大根堆存较小的数据，小根堆存较大的数据，使得大小根堆的堆顶都是有序数据中间的部分。
这样如果窗口是奇数大小，则令大根堆比小根堆多1个数，大根堆的堆顶就是中位数；如果窗口大小是偶数，则取二者的平均值。
当窗口向右移动时，右侧新增的元素如果>=大根堆堆顶元素，则加入大根堆，否则加入小根堆。
窗口向右移动之后，左侧减少了一个元素。假设已经从堆中删除了这个元素，则可能会导致两个堆各自的元素个数不再满足要求，因此需要弹出数据偏多的堆的堆顶元素，加入数据偏少的堆中。
考虑删除左侧元素。因为窗口左侧的元素可能在堆的内部，而堆只能对堆顶进行操作，所以不能直接删除可能在内部的窗口左侧元素。又因为如果不考虑数据个数的话，在堆内部的这个元素对于求中位数是没有影响的，因此可以考虑延迟删除。
使用一个hash表记录每个元素要删除的次数，当要删除的元素在堆的内部时，暂时不删除，因为对于求解问题没有影响。直到在堆将要删除的元素移动到堆顶时，才可能会对中位数的求解产生影响，此时检查hash表，将其删除即可。
时间O(nlogk)。

阅读全文 »

发表于 分类于

1. 朴素

首先找到第一个字符最后一次出现的位置，得到一个子串。
然后遍历这个子串，找其中每一个字符的最后一次出现的位置，得到这个子串最终的结尾。
对右侧剩余部分做同样的处理。
时间O(n^2)，空间O(1)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> partitionLabels(string S) {
        vector<int> ans;
        int n = S.length();

        for (int i = 0; i < n;) {
            int lastIdx = lastLocation(S, i);       // 获取开始字符的最后出现位置
            for (int j = i + 1; j < lastIdx; j++)
                // 这里可以适当剪枝，已经访问过的字符之后不需要再重复访问了，因为其最后出现的位置还是不变的。
                lastIdx = max(lastIdx, lastLocation(S, j));
            ans.push_back(lastIdx - i + 1);
            i = lastIdx + 1;
        }

        return ans;
    }
private:
    int lastLocation(string S, int k) {
        int n = S.length();
        for (int i = k + 1; i < n; i++)
            if (S[k] == S[i])
                k = i;
        
        return k;
    }
};

2. 记忆化

上述方法的问题是在查找每个元素出现的最后一个位置上花费了太多的时间，导致时间复杂度是O(n^2)的。
可以使用一个bool数组记录已经访问过最后一个位置的元素，之后再遇到就不需要再次访问了，不过这样最差是O(26n)的。
更好的方法是首先遍历一次字符串，使用一个大小为26的数组记录每个字符最后出现的位置，在需要最后一个位置时直接查表。
时间O(n)，空间O(26) = O(1)。

阅读全文 »

发表于 分类于

1. 模拟

两个指针分别指向name和typed即可。
时间O(m + n)，空间O(1)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    bool isLongPressedName(string name, string typed) {
        int nameLen = name.length(), typedLen = typed.length();
        int nameIdx = 0, typedIdx = 0;
        bool res = true;

        while (res && (nameIdx < nameLen || typedIdx < typedLen)) {
            if (nameIdx == nameLen) {
                if (typedIdx == 0) 
                    res = false;
                else {
                    while (typedIdx < typedLen) {
                        if (typed[typedIdx] == typed[typedIdx - 1])
                            typedIdx++;
                        else {
                            res = false;
                            break;
                        }
                    }
                }
            } else if (typedIdx == typedLen)
                res = false;
            else {
                if (name[nameIdx] == typed[typedIdx]) {
                    nameIdx++;
                    typedIdx++;
                    if (nameIdx < nameLen && name[nameIdx] != name[nameIdx - 1]) {
                        while (typedIdx < typedLen && typed[typedIdx] == typed[typedIdx - 1])
                            typedIdx++;
                    }
                } else
                    res = false;
            }
        }

        return res;
    }
};

发表于 分类于

1. 模拟

直接在原有字符串上进行修改，当遇到#时，把其左侧的第一个非#修改为#，表示已删除。
为了更快的找到左侧第一个非#字符，而不是每次都要–遍历，可以直接逆序修改。
时间O(n)，空间O(1)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int sLen = S.length(), tLen = T.length();
        int sCount = 0, tCount = 0;
        bool ans = true;

        for (int i = sLen - 1; i >= 0; i--) {
            if (sCount > 0 && S[i] != '#') {
                S[i] = '#';
                sCount--;
            } else if (S[i] == '#')
                sCount++;
        }
        for (int i = tLen - 1; i >= 0; i--) {
            if (tCount > 0 && T[i] != '#') {
                T[i] = '#';
                tCount--;
            } else if (T[i] == '#')
                tCount++;
        }

        int sidx = 0, tidx = 0;
        while (sidx < sLen || tidx < tLen) {
            while (sidx < sLen && S[sidx] == '#')
                sidx++;
            while (tidx < tLen && T[tidx] == '#')
                tidx++;
            if ((sidx == sLen && tidx < tLen) || (sidx < sLen && tidx == tLen)) {
                ans = false;
                break;
            } else if (sidx < sLen && tidx < tLen) {
                if (S[sidx++] != T[tidx++]) {
                    ans = false;
                    break;
                }
            }
        }

        return ans;
    }
};

发表于 更新于 分类于

1. 双指针

首先找到正数和负数的分界点，然后二者根据各自指向的值的平方大小向左向右移动。
时间O(n)，空间O(1)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int n = A.size();
        vector<int> res(n);
        int neg, pos, sep, count = 0;

        for (sep = 0; sep < n; ++sep)
            if (A[sep] >= 0)
                break;
        neg = sep - 1;
        pos = sep;
        while (count < n) {
            int val;
            if (neg >= 0 && pos < n) {
                if (-A[neg] <= A[pos]) 
                    val = A[neg--];
                else
                    val = A[pos++];
            } else if (neg >= 0)
                val = A[neg--];
            else 
                val = A[pos++];
            res[count++] = val * val;
        }

        return res;
    }
};