Shawn's Blog

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
        const int prevR = nums.size(), prevC = nums[0].size();
        if (prevR * prevC < r * c) return nums;
        vector<vector<int>> ans(r, vector<int>(c));
        int idx = 0;
        for (int i = 0; i < prevR; ++i)
            for (int j = 0; j < prevC; ++j) {
                int currR = idx / c, currC = idx % c;
                ans[currR][currC] = nums[i][j];
                ++idx;
            }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), ans = 0;
        for (int i = 0; i < n; i += 2)
            ans += nums[i];
        return ans;
    }
};

Posted on Edited on In 
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 longestSubstring(string s, int k) {
        int n = s.size(), ans = 0;
        for (int cnt = 1; cnt <= 26; ++cnt) { // there could be [1..26] diff letters.
            int left = 0, right = 0, uniqueCnt = 0;
            int charCnt[26] = {0};
            while (right < n) {
                bool valid = true;
                if (charCnt[s[right++] - 'a']++ == 0)
                    ++uniqueCnt;
                while (uniqueCnt > cnt)
                    if (--charCnt[s[left++] - 'a'] == 0)
                        --uniqueCnt;
                for (int j = 0; j < 26; ++j)
                    if (charCnt[j] > 0 && charCnt[j] < k) {
                        valid = false;
                        break;
                    }
                if (valid)
                    ans = max(ans, right - left);
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestSubstring(string s, int k) {
        int n = s.size(), m[26] = {0}, left = 0, ans = 0;
        bool valid = true;
        for (char c : s)
            ++m[c - 'a'];
        for (int right = 0; right < n; ++right)
            if (m[s[right] - 'a'] < k) {
                ans = max(ans, longestSubstring(s.substr(left, right - left), k));
                valid = false;
                left = right + 1;
            }
        return valid ? n : max(ans, longestSubstring(s.substr(left, n - left), k));
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int n = A.size(), left = 0, right = 0, ans = 0;
        vector<int> P(n + 1);
        for (int i = 1; i <= n; ++i)
            P[i] = P[i - 1] + (1 - A[i - 1]);
        while (right++ < n) {
            left = lower_bound(P.begin(), P.end(), P[right] - K) - P.begin();
            ans = max(ans, right - left);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int n = A.size(), left = 0, right = 0, cnt = 0, ans = 0;
        while (right < n) {
            if (A[right++] == 0)
                ++cnt;
            while (cnt > K)
                if (A[left++] == 0)
                    --cnt;
            ans = max(ans, right - left);
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int cur = 0, cnt = 0, ans = 0;
        for (int num : nums) {
            ++cnt;
            if (num == 0) {
                cur = cnt;
                cnt = 0;
            } 
            ans = max(ans, cur + cnt);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int n = nums.size(), left = 0, right = 0, cnt = 0, ans = 0;
        while (right < n) {
            if (nums[right++] == 0)
                ++cnt;
            while (cnt > 1)
                if (nums[left++] == 0)
                    --cnt;
            ans = max(ans, right - left);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// solution for follow up (nums as streaming data).
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int n = nums.size(), left = 0, right = 0, ans = 0;
        queue<int> q;
        while (right < n) {
            if (nums[right++] == 0)
                q.push(right);
            if (q.size() > 1) {
                left = q.front(); q.pop();
            }
            ans = max(ans, right - left);
        }
        return ans;
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int cnt = 0, ans = 0;
        for (int num : nums) {
            if (num == 1) {
                ++cnt;
            } else {
                ans = max(ans, cnt);
                cnt = 0;
            }
        }
        return max(ans, cnt);
    }
};

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        const int n = nums.size();
        for (int i = 0; i < n; ++i)
            if (nums[i] <= 0)
                nums[i] = n + 1; // makes all nums as positive integer.
        for (int i = 0; i < n; ++i) {
            int num = abs(nums[i]);
            if (num <= n)
                nums[num - 1] = -abs(nums[num - 1]); // taged as negative integer.
        }
        for (int i = 0; i < n; ++i)
            if (nums[i] > 0) // have not been taged, indicating the num missed.
                return i + 1;
        return n + 1; // [1..n] all taged, the ans should be "n + 1". 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        const int n = nums.size();
        for (int i = 0; i < n; ++i)
            while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1])
                swap(nums[i], nums[nums[i] - 1]);
        for (int i = 0; i < n; ++i)
            if (nums[i] != i + 1)
                return i + 1;
        return n + 1;
    }
};

Reference: Java/C++ O(N) solution using cyclic swapping - LeetCode Discuss.

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int ans = nums.size(), i = 0;
        for (const int num : nums)
            ans ^= i++ ^ num;
        return ans;
    }
};
1
2
3
4
5
6
7
8
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int expectedSum = nums.size() * (nums.size() + 1) / 2;
        int actualSum = accumulate(nums.begin(), nums.end(), 0);
        return expectedSum - actualSum;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        // reference: https://leetcode.com/problems/couples-holding-hands/discuss/113362/JavaC%2B%2B-O(N)-solution-using-cyclic-swapping
        const int n = nums.size();
        for (int i = 0; i < n; ++i)
            for (int j = nums[i]; i != j && j != n; j = nums[i])
                swap(nums[i], nums[j]);
        for (int i = 0; i < n; ++i)
            if (nums[i] != i)
                return i;
        return n;
    }
};

Posted on Edited on In 
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
class UF {
public:
    vector<int> f;
    vector<int> size;
    int n;
    UF(int _n): n(_n), f(_n), size(_n, 1) {
        iota(f.begin(), f.end(), 0);
    }
    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }
    void _union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            if (size[x] < size[y])
                swap(x, y);
            f[y] = x;
            size[x] += size[y];
        }
    }
};
class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        const int n = row.size();
        int tot = n / 2;
        UF uf(tot);
        for (int i = 0; i < n; i += 2)
            uf._union(row[i] / 2, row[i + 1] / 2);
        unordered_map<int, int> m;
        for (int i = 0; i < tot; ++i)
            ++m[uf.find(i)];
        int ans = 0;
        // for each connected set with "sz" as size,
        // "sz - 1" would be the number of needed swaps.
        for (const auto& [_, sz] : m)
            ans += sz - 1;
        return ans;
    }
};
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
class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        const int n = row.size();
        int tot = n / 2;
        vector<vector<int>> graph(tot);
        for (int i = 0; i < n; i += 2) {
            int l = row[i] / 2;
            int r = row[i + 1] / 2;
            graph[l].emplace_back(r);
            graph[r].emplace_back(l);
        }
        vector<bool> visited(tot, false);
        int ans = 0;
        for (int i = 0; i < tot; ++i)
            if (!visited[i]) {
                queue<int> q;
                q.push(i);
                visited[i] = true;
                int cnt = 0;
                while (!q.empty()) {
                    int x = q.front(); q.pop();
                    ++cnt;
                    for (int nx : graph[x])
                        if (!visited[nx]) {
                            q.push(nx);
                            visited[nx] = true;
                        }
                }
                ans += cnt - 1;
            }
        return ans;
    }
};
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
class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        const int n = row.size();
        int tot = n / 2;
        vector<vector<int>> graph(tot);
        for (int i = 0; i < n; i += 2) {
            int l = row[i] / 2;
            int r = row[i + 1] / 2;
            graph[l].emplace_back(r);
            graph[r].emplace_back(l);
        }
        vector<bool> seen(tot, false);
        int cnt = 0, ans = 0;
        function<void(int)> dfs = [&](int x) {
            ++cnt;
            for (int nx : graph[x])
                if (!seen[nx]) {
                    seen[nx] = true;
                    dfs(nx);
                };
        };
        for (int i = 0; i < tot; ++i)
            if (!seen[i]) {
                seen[i] = true;
                dfs(i);
                ans += cnt - 1;
                cnt = 0;
            }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        int n = row.size(), ans = 0;
        vector<int> ptn(n); // self label -> partner label
        vector<int> pos(n); // label -> seat
        for (int i = 0; i < n; ++i) {
            ptn[i] = i ^ 1;
            pos[row[i]] = i;
        }
        for (int i = 0; i < n; ++i)
            for (int j = ptn[pos[ptn[row[i]]]]; i != j; j = ptn[pos[ptn[row[i]]]]) {
                swap(row[i], row[j]);
                swap(pos[row[i]], pos[row[j]]);
                ++ans;
            }
        return ans;
    }
};

Reference: Java/C++ O(N) solution using cyclic swapping - LeetCode Discuss.

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        for (int num : nums) {
            int idx = (num - 1) % n;
            nums[idx] += n;
        }
        vector<int> ans;
        for (int i = 0; i < n; ++i)
            if (nums[i] <= n)
                ans.emplace_back(i + 1);
        return ans;
    }
};
0%