zkkKillua's Blog
0%

发表于 分类于

1. 来回倒

使用两个栈，一个作为输入栈，一个作为输出栈。
push: 添加到输入栈中
pop: 将输入栈的元素弹出并添加到输出栈，实现逆序，弹出首元素后，再将剩余元素弹回输入栈
peek: 同pop
这种方法比较繁琐，pop和peek操作都是O(n)的。

2. 不来回倒

使用两个栈，一个作为输入栈，一个作为输出栈。
几乎同方法1，但是当元素被弹到输出栈之后，不再弹回到输入栈。
因为输出栈本身就是“队列”的前部分，当输出栈为空时，再将输入栈弹到输出栈，得到的又是队列接下来的一部分。
这样可以将pop和peek的操作降低到均摊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
43
44
45
46
47
48
49
class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {}
    
    /** Push element x to the back of queue. */
    void push(int x) {
        inStack.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        if (outStack.empty())
            move();
        int val = outStack.top();
        outStack.pop();

        return val;
    }
    
    /** Get the front element. */
    int peek() {
        if (outStack.empty())
            move();
        return outStack.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return inStack.empty() && outStack.empty();
    }
private:
    stack<int> inStack, outStack;
    void move() {
        while (!inStack.empty()) {
            outStack.push(inStack.top());
            inStack.pop();
        }
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */
阅读全文 »

发表于 分类于

参考最长递增子序列

1. dp

首先将信封从小到大排列，之后设置动态规划数组，dp[i]代表以envelopes[i]为结尾的信封序列最长的长度。
则每次dp[i]都由左侧比它小的信封中最长的长度+1得到。
时间O(n^2)，空间O(n)。 

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
class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        int n = envelopes.size();
        if (n == 0)
            return 0;
        sort(envelopes.begin(), envelopes.end());

        vector<int> lens(n, 1);
        int maxLength = 1;
        for (int i = 1; i < n; i++) {
            int maxBefore = 0;
            for (int j = i; j >= 0; j--) {
                if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1] && lens[j] > maxBefore) {
                    maxBefore = lens[j];
                    if (lens[j] == maxLength)
                        break;
                }
            }
            lens[i] += maxBefore;
            maxLength = max(maxLength, lens[i]);
        }

        return maxLength;
    }
};

2. dp+二分

阅读全文 »

发表于 更新于 分类于

1. 分区间动态规划

通过观察一段连续数字的二进制可以发现，[2^i, 2^(i+1))部分实际是在之前的二进制数字前面加一位1.

所以可以根据 2^i分成多部分，根据已有的+1得到新的。
时间 O(n)，空间 O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> res(1, 0);

        for (int k = 0; ; k++) {
            int sz = pow(2, k);
            for (int i = 0; i < sz; i++) {
                if (sz + i > num)
                    break;
                res.push_back(1 + res[i]);
            }
            if (res.size() == num + 1)
                break;
        }

        return res;
    }
};
阅读全文 »

发表于 分类于

1. 朴素

滑动窗口，记录窗口内部的最大值和最小值。
但是每次移动窗口之后，如果最大值或者最小值被移除了，则需要重新遍历窗口内部的元素获取。
时间O(n^2)，空间O(1)。

2. 堆

使用大根堆和小根堆保存当前窗口内部的数据，从而能够直接获得最大值和最小值。
不过问题在于，如果移动窗口移除的是非最大值或最小值，则堆是无法直接删除非堆顶的元素的，需要使用hash表记录，每次删除时对照hash表，延迟删除。
时间O(nlogn)，空间O(n)。 

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
class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        int n = nums.size();
        int left = 0, right = 0;
        int res = 0;
        priority_queue<int> bigHeap;
        priority_queue<int, vector<int>, greater<int>> smallHeap;
        unordered_map<int, int> bigDel, smallDel;

        while (right < n) {
            if (bigHeap.empty() || (!bigHeap.empty() && bigHeap.top() - nums[right] <= limit && nums[right] - smallHeap.top() <= limit)) {
                bigHeap.push(nums[right]);
                smallHeap.push(nums[right]);
                right++;
            } else {
                res = max(res, right - left);
                bigDel[nums[left]]++;
                smallDel[nums[left]]++;
                left++;
            }

            while (!bigHeap.empty() && bigDel[bigHeap.top()] > 0) {
                bigDel[bigHeap.top()]--;
                bigHeap.pop();
            }
            while (!smallHeap.empty() && smallDel[smallHeap.top()] > 0) {
                smallDel[smallHeap.top()]--;
                smallHeap.pop();
            }
        }
        res = max(res, right - left);

        return res;
    }
};
阅读全文 »

发表于 分类于

1. hash表

首先使用hash表记录每个数据出现的频数，就可以得知最大的频数及其对应的数据。
此时如果有该数据的第一次和最后一次出现的位置，则可以获得这段区间的长度，比较频数最大的数据的区间的最小值即可。
数据的记录可以用hash表，key是元素值，为保证数据的一致性，value是一个数组，储存频数、首位置和末位置。也可以用3个数组直接储存，因为已经给定了0~49999的范围。
时间O(n)，空间O(n)。 

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
class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, vector<int>> mp;     // key, [freq, first, last]
        int maxFreq = 0, minLen = 0;

        for (int i = 0; i < n; i++) {
            if (mp.count(nums[i]) == 0)
                // mp[nums[i]].emplace_back(1, i, i);       // 此时数组还不存在
                mp[nums[i]] = {1, i, i};
            else {
                mp[nums[i]][0]++;
                mp[nums[i]][2] = i;
            }
            if (maxFreq == mp[nums[i]][0])
                minLen = min(minLen, mp[nums[i]][2] - mp[nums[i]][1] + 1);
            else if (maxFreq < mp[nums[i]][0]) {
                maxFreq = mp[nums[i]][0];
                minLen = mp[nums[i]][2] - mp[nums[i]][1] + 1;
            }
        }

        return minLen;
    }
};

发表于 更新于 分类于

1. 贪心

贪心第一个0作为开始，将其及之后的元素进行反转。
因为如果反转的起点不是第一个0，则左侧的部分1也会被反转成0，而要反转被反转成的这部分0，又要向左延伸，因此需要贪心第一个0作为反转的起点。
时间 O(nk)，空间 O(1)，超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        int n = A.size();
        int res = 0;

        for (int i = 0; i < n; i++) {
            if (A[i] == 0) {
                if (i <= n - K) {
                    for (int j = i; j < i + K; j++)
                        A[j] ^= 1;
                    res++;
                } else {
                    res = -1;
                    break;
                }
            }
        }

        return res;
    }
};

2. 差分数组

方法1中超时是因为及时反转了数组，有 O(k)的复杂度，因此考虑延迟反转数组。
如果使用一个数组直接记录每个元素的反转次数，则时间复杂度跟方法1中是相同的，而且还额外使用 O(n)的空间复杂度。
而我们又需要区间内每个元素的反转次数，因此考虑使用差分，其是利用对区间两侧的操作代替对区间内部的操作。

阅读全文 »

发表于 分类于

1. 并查集

有1对情侣时，需要交换0次。
有2对情侣交叉坐时，需要交换1次。
有3对情侣交叉坐时，需要交换2次。
…
有k对情侣交叉坐时，需要交换k-1次。
因为有k对情侣交叉坐时，交换1次可以使且仅使1对情侣牵手，剩余k-1对情侣交叉坐，以此类推。
交换1次仅能使1对情侣牵手，因为如果可以使2对情侣牵手，剩余k-2对情侣交叉坐，则之前不是k对情侣交叉坐的。

因此考虑使用并查集，每次遍历两个位置，并获取他们所属的组别。组别是值/2，如0和1属于0组，2和3属于1组…
判断二者组别如果一致，则跳过；否则使用并查集将二者的组别合并，合并成为1个连通分支。同一个连通分支中的各个数据一定是多组同队情侣交叉分散在不同的位置上。
最终答案为每个连通分支中情侣对数 - 1的和，实际上也等于总情侣对数 - 连通分支数，而后者更容易计算。
时间O(n)，空间O(n)。 

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
class UnionFind {
public:
    UnionFind (int n) {
        // parent.reserve(n);       // reserve()只预留空间，不修改size，故修改后不能直接访问
        parent.resize(n);
        cnt = n;
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    int find (int x) {
        if (x != parent[x])
            parent[x] = find(parent[x]);
        return parent[x];
    }

    void unite(int a, int b) {
        int pa = find(a), pb = find(b);
        if (pa != pb) {
            parent[pb] = pa;
            cnt--;
        }
    }

    int getCnt() {
        return cnt;
    }
private:
    vector<int> parent;
    int cnt;    // 连通分支数
};

class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        int n = row.size();
        UnionFind uf(n);

        for (int i = 0; i < n; i += 2) {
            int group1 = row[i] / 2, group2 = row[i + 1] / 2;
            if (group1 != group2)
                uf.unite(group1, group2);
        }

        return n / 2 - uf.getCnt();
    }
};

发表于 分类于

1. 堆

由于类只需要求第k大元素，因此只保留第k大和比它大的元素作为比较即可，其他元素可以丢弃。
因此可以使用一个大小为k的小根堆，储存前k大元素。
当要插入元素时，与小根堆堆顶元素比较，如果偏小则抛弃，如果偏大则弹出堆顶，插入该元素。
时间O(nlogk)，空间O(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
class KthLargest {
public:
    KthLargest(int k, vector<int>& nums) {
        int n = nums.size();
        this->k = k;
        for (int i = 0; i < n; i++)
            add(nums[i]);
    }
    
    int add(int val) {
        if (smallHeap.size() == k && val > smallHeap.top()) {
            smallHeap.pop();
            smallHeap.push(val);
        } else if (smallHeap.size() < k)
            smallHeap.push(val);
        
        return smallHeap.top();
    }

private:
    int k;
    priority_queue<int, vector<int>, greater<int>> smallHeap;
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */

发表于 分类于

1. 滑动窗口

固定窗口的左边界，右边界向右滑动，可以找到一个最大的不可再扩展的大小为k的好子数组。此时如果也找到一个最大的不可再扩展的大小为k-1的好子数组，则二者右边界的差值即为当前左边界对应的大小为k的好子数组的个数，因为二者右侧的差值中含有第k种数据。
这种做法需要使用两个freq数组记录k-1和k窗口（简称为大、小窗口）出现的各个元素的次数，因为当左边界向右移动之后，小窗口内部的元素数据可能变为k-2个，而大窗口仍为k个。所以需要分开保存，分别扩展。

如果固定的是窗口的右边界，大小窗口只有左边界不同。实际操作中，相较于固定左边界，固定右边界更加简单，因为此时每次扩展移动的都是同一个右边界，而固定左边界时右边界扩展是要扩展两个右边界。
使用这种算法，同样地需要找到一个最大的不可再扩展的大小为k和k-1的好子数组的左边界，二者的差值即为当前固定右边界对应的好子数组的种数。
之后右边界继续向右移动1个位置，有三种情况：

  1. 大小窗口的元素种数都没有改变，仍为k和k-1
  2. 大窗口的元素种类没有改变，小窗口的元素种类变为k
  3. 大小窗口的元素种数都增加，变为k+1和k
    对于第一种情况，二者的左边界不需要改变，并计算差值增加到答案，作为新的右边界对应的好子数组的个数；对于第二种情况，小窗口需要向右移动左边界，移动到最大的不可再扩展的大小为k-1的好子数组的左边界，而大窗口的左边界不变；对于第三种情况，小窗口的左边界向右移动到最大的不可再扩展的大小为k-1的好子数组的左边界，大窗口的左边界移动到小窗口的左边界的原位置即可。

通过这个题要学会固定一个边界，滑动另一个边界求解问题的方法。
时间O(n)，空间O(n)。

阅读全文 »

发表于 分类于

1. 滑动窗口

要求是字符串的任一排列，因此不需要实际遍历各种排列，只需要统计该字符串各字符的个数即可。
窗口右边界向右滑动，直到不可再滑动。如果此时还不满足条件，则左边界向右滑动1个位置，然后继续判断右边界。当左右边界重叠时右边界还不能向右滑动，证明字符串中不存在该字符，左右边界同时向右滑动1个位置。
时间O(n)，空间O(26)。 

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 checkInclusion(string s1, string s2) {
        int len1 = s1.length(), len2 = s2.length();
        if (len1 > len2)
            return false;

        int left = 0, right = 0;
        bool res = false;
        int freq[26];
        for (int i = 0; i < 26; i++)
            freq[i] = 0;
        for (int i = 0; i < len1; i++)
            freq[s1[i] - 'a']++;

        while (right < len2) {
            if (freq[s2[right] - 'a'] > 0) {
                freq[s2[right] - 'a']--;
                right++;
                len1--;
                if (len1 == 0) {
                    res = true;
                    break;
                }
            } else {
                if (left == right) {
                    left++;
                    right++;
                } else {
                    freq[s2[left] - 'a']++;
                    left++;
                    len1++;
                }
            }
        }

        return res;
    }
};