Shawn's Blog

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        final int R = matrix.length, C = matrix[0].length;
        int[] sorted = new int[R * C];
        int idx = 0;
        for (int[] row : matrix)
            for (int num : row)
                sorted[idx++] = num;
        Arrays.sort(sorted);
        return sorted[k - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        final int R = matrix.length;
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < R; ++i)
            q.offer(new int[]{matrix[i][0], i, 0});
        for (int i = 0; i < k - 1; ++i) {
            int[] now = q.poll();
            if (now[2] != R - 1)
                q.offer(new int[]{matrix[now[1]][now[2] + 1], now[1], now[2] + 1});
        }
        return q.poll()[0];
    }
}
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 kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int left = matrix[0][0], right = matrix[n - 1][n - 1];
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (check(matrix, k, mid, n))
                right = mid;
            else
                left = mid + 1;
        }
        return left;
    }
    private boolean check(int[][] matrix, int k, int mid, int n) {
        int i = n - 1, j = 0, cnt = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= mid) {
                cnt += i + 1;
                ++j;
            } else {
                --i;
            }
        }
        return cnt >= k;
    }
}

Posted on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        int n = A.size(), flipped = 0, ans = 0;
        vector<int> isFlipped(n);
        for (int i = 0; i < n; ++i) {
            if (i >= K)
                flipped ^= isFlipped[i - K];
            if (flipped == A[i]) {
                if (i + K > n)
                    return -1;
                isFlipped[i] = 1;
                flipped ^= 1;
                ++ans;
            }
        }
        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
class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        int n = A.size(), flipped = 0, ans = 0;
        queue<int> isFlipped;
        for (int i = 0; i < n; ++i) {
            if (i >= K) {
                flipped ^= isFlipped.front();
                isFlipped.pop();
            }
            if (flipped == A[i]) {
                if (i + K > n)
                    return -1;
                isFlipped.push(1);
                flipped ^= 1;
                ++ans;
            } else {
                isFlipped.push(0);
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        // "cur" is the count of flipping times within current sliding window.
        int n = A.size(), cur = 0, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i >= K && A[i - K] > 1) {
                --cur;
                A[i - K] += 2;
            }
            if (cur % 2 == A[i]) {
                if (i + K > n)
                    return -1;
                A[i] += 2;
                ++cur;
                ++ans;
            }
        }
        return ans;
    }
};

Reference: [Java/C++/Python] One Pass and O(1) Space - LeetCode Discuss.

Posted 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 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 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 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 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 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 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 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;
    }
};
0%