LeetCode 1253 - Reconstruct a 2-Row Binary Matrix

https://leetcode.com/problems/reconstruct-a-2-row-binary-matrix/

Given the following details of a matrix with n columns and 2 rows :

• The matrix is a binary matrix, which means each element in the matrix can be 0 or 1.
• The sum of elements of the 0-th(upper) row is given as upper.
• The sum of elements of the 1-st(lower) row is given as lower.
• The sum of elements in the i-th column(0-indexed) is colsum[i], where colsum is given as an integer array with length n.

Your task is to reconstruct the matrix with upper, lower and colsum.

Return it as a 2-D integer array.

If there are more than one valid solution, any of them will be accepted.

If no valid solution exists, return an empty 2-D array.

Example 1:

Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]
Explanation: [[1,0,1],[0,1,0]], and [[0,1,1],[1,0,0]] are also correct answers.

Example 2:

Input: upper = 2, lower = 3, colsum = [2,2,1,1]
Output: []

Example 3:

Input: upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]
Output: [[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]

https://leetcode.com/problems/reconstruct-a-2-row-binary-matrix/discuss/425793/C%2B%2BJava-5-lines

If the column sum is 2 or 0, the choice is obvius.

If it's 1, we set the upper bit if upper is larger than lower, and lower bit otherwise.

public List<List<Integer>> reconstructMatrix(int u, int l, int[] cs) {
    boolean[][] res = new boolean[2][cs.length];
    for (int i = 0; i < cs.length; ++i) {
        res[0][i] = cs[i] == 2 || (cs[i] == 1 && l < u);
        res[1][i] = cs[i] == 2 || (cs[i] == 1 && !res[0][i]);
        u -= res[0][i] ? 1 : 0;
        l -= res[1][i] ? 1 : 0;
    }
    return l == 0 && u == 0 ? new ArrayList(Arrays.asList(res[0], res[1])) : new ArrayList();    
}

https://www.cnblogs.com/onePunchCoder/p/11831345.html

public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colums) {
        int sum = 0;
        int numof2 = 0;
        for (int colum : colums) {
            sum += colum;
            if (colum == 2) {
                numof2++;
            }
        }
        List<List<Integer>> result = new ArrayList<>();
        if (sum != upper + lower || numof2 > Math.min(upper, lower)) {
            return result;
        }
        List<Integer> upperList = new ArrayList<>();
        List<Integer> lowerList = new ArrayList<>();
        result.add(upperList);
        result.add(lowerList);
        for (int colum : colums) {
            if (colum == 0) {
                upperList.add(0);
                lowerList.add(0);
            } else if (colum == 2) {
                upperList.add(1);
                upper--;
                lowerList.add(1);
                lower--;
            } else {
                if (upper > lower) {
                    upperList.add(1);
                    lowerList.add(0);
                    upper--;
                } else {
                    upperList.add(0);
                    lowerList.add(1);
                    lower--;
                }
            }
        }
        return result;
    }

https://www.codetd.com/en/article/7811117

2, a brief translation:

Construction of a plurality of data rows two columns, and the first row of upper, and the second row of Lower, and to colsum [i] of the i-th column. If such an array does not exist returns NULL

3, code analysis:

• If the upper + lower does not mean colsum and then return empty.
• If the number 2 is greater than colsum in upper or lower, return null
• From left to right, a premise is inserted vertically keep balance. (When colums [i] == 1, if lower> = upper plug, the plug remaining cases)

public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colums) {
        int sum = 0;
        int numof2 = 0;
        for (int colum : colums) {
            sum += colum;
            if (colum == 2) {
                numof2++;
            }
        }
        List<List<Integer>> result = new ArrayList<>();
        if (sum != upper + lower || numof2 > Math.min(upper, lower)) {
            return result;
        }
        List<Integer> upperList = new ArrayList<>();
        List<Integer> lowerList = new ArrayList<>();
        result.add(upperList);
        result.add(lowerList);
        for (int colum : colums) {
            if (colum == 0) {
                upperList.add(0);
                lowerList.add(0);
            } else if (colum == 2) {
                upperList.add(1);
                upper--;
                lowerList.add(1);
                lower--;
            } else {
                if (upper > lower) {
                    upperList.add(1);
                    lowerList.add(0);
                    upper--;
                } else {
                    upperList.add(0);
                    lowerList.add(1);
                    lower--;
                }
            }
        }
        return result;
    }

https://leetcode.com/problems/reconstruct-a-2-row-binary-matrix/discuss/425170/Detailed-Explanation-using-Greedy-Approach

• First, intialize both the rows as 0. Now, fill the indices where the vertical column sum is 2 (as they don't have a choice). So, now we only need to make choices for the columns with sum 1. Find out the current sum of the first row. Compare it with the required amount. If the difference becomes negative, it means that there is no solution. Else, greedily fill the required 1s in the top row and the remaining 1s in the bottom row. Finally, check if the sum of the bottom row equals lower

https://leetcode.com/problems/reconstruct-a-2-row-binary-matrix/discuss/425110/O(n)-time-Java-Solution-Easy-to-understand-with-Comments-and-Explaination

We count the number of columns for which we need 1 in both rows(colsum[i] == 2), similarly we count the number of columns for which we need column-sum as 1 and column-sum as 0.

For the columns where we need the column-sum as 2, we definitely know that we need 1 in both the rows, similarly if the column-sum is 0 we know we need to place 0s in both the rows.

For the case where we need column-sum as 1, we need to see if we can have a 1 in row1 or do we have to have a 1 in row2.
For those cases I have done a precomputation and followed a somewhat greedy approach.
The number of columns where we need a 1 in row1 and 0 in row2 is say count1 (as mentioned in code).
We start assigning values to the two rows now by iterating over each value in the colsum array. If we encounter a colsum[i] == 2 or colsum[i] == 0, we assign 1s to both the rows and 0s to both the rows respectively.
For the cases where colsum[i] == 1, we check value of count1 variable which will tell us if we can assign a 1 to row1 or not. If value of count1 > 0, we can assign 1 to row1 and 0 to row2 and we simultaneously decrement count1. Else if count1 == 0, we assign a 0 to row1 and 1 to row2.

    public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {
        
        int n = colsum.length;
        int sum0 = 0; // no. of columns with colsum 0
        int sum1 = 0; // no. of columns with colsum 1
        int sum2 = 0; // no. of columns with colsum 2
        
        for(int i = 0; i < n; i++){
            if(colsum[i] == 0) sum0 ++;
            else if(colsum[i] == 1) sum1 ++;
            else sum2 ++;
        }
        
        int count1 = upper - sum2; // no. of columns with 1 in 1st row and 0 in 2nd row
        int count2 = lower - sum2; // no. of columns with 0 in 1st row and 1 in 2nd row
        
        // check if arrangement is possible or not
        if(count1 < 0 || count2 < 0 || count1 + count2 != sum1) return new ArrayList<>();
        
        List<List<Integer>> ans = new ArrayList<>();
        for(int i = 0; i < 2; i++) ans.add(new ArrayList<>());
        
        for(int i = 0; i < n; i++){
            if(colsum[i] == 2){
                ans.get(0).add(1);
                ans.get(1).add(1);
            }
            else if(colsum[i] == 0){
                ans.get(0).add(0);
                ans.get(1).add(0);
            }
            else{
                if(count1 > 0){
                    count1 --;
                    ans.get(0).add(1);
                    ans.get(1).add(0);
                }
                else{
                    ans.get(0).add(0);
                    ans.get(1).add(1);
                }
            }
        }
        
        return ans;
    }

https://www.acwing.com/solution/LeetCode/content/6123/

(贪心) $O(n)$

1. colsum 为 0 或者 2 的列的值可以直接确定，根据情况，更新 upper 和 lower，此时 upper 和 lower 记录当前行还需要多少个 1。如果这时候 upper 或 lower 小于 0，则直接返回空数组。
2. 接下来处理 colsum 为 1 的列，如果 upper 大于 0，则这一列第一行填 0，第二行填 1，然后 upper 减 1。反之亦然。最后处理结束后，如果 upper 或 lower 仍大于 0，则返回空数组。

时间复杂度

• 每个位置仅遍历两次，故时间复杂度为 $O(n)$。

空间复杂度

• 答案需要额外 $O(n)$ 的空间。

    vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {
        int n = colsum.size();
        vector<vector<int>> res(2, vector<int>(n));

        for (int i = 0; i < n; i++)
            if (colsum[i] == 0) {
                res[0][i] = res[1][i] = 0;
            } else if (colsum[i] == 2) {
                res[0][i] = res[1][i] = 1;
                upper--; lower--;
                if (upper < 0 || lower < 0)
                    return {};
            } 

        for (int i = 0; i < n; i++)
            if (colsum[i] == 1) {
                if (upper > 0) {
                    res[0][i] = 1; res[1][i] = 0;
                    upper--;
                } else if (lower > 0) {
                    res[0][i] = 0; res[1][i] = 1;
                    lower--;
                } else {
                    return {};
                }
            }

        if (upper > 0 || lower > 0)
            return {};

        return res;
    }

LeetCode 1229 - Meeting Scheduler

https://www.acwing.com/solution/LeetCode/content/5442/

你是一名行政助理，手里有两位客户的空闲时间表：slots1 和 slots2，以及会议的预计持续时间 duration，请你为他们安排合适的会议时间。

「会议时间」是两位客户都有空参加，并且持续时间能够满足预计时间 duration 的 最早的时间间隔。

如果没有满足要求的会议时间，就请返回一个 空数组。

「空闲时间」的格式是 [start, end]，由开始时间 start 和结束时间 end 组成，表示从 start 开始，到 end 结束。

题目保证数据有效：同一个人的空闲时间不会出现交叠的情况，也就是说，对于同一个人的两个空闲时间 [start1, end1] 和 [start2, end2]，要么 start1 > end2，要么 start2 > end1。

样例

输入：
slots1 = [[10,50],[60,120],[140,210]],
slots2 = [[0,15],[60,70]],
duration = 8

输出：[60,68]

输入：
slots1 = [[10,50],[60,120],[140,210]],
slots2 = [[0,15],[60,70]],
duration = 12

输出：[]

限制

• 1 <= slots1.length, slots2.length <= 10^4
• slots1[i].length, slots2[i].length == 2
• slots1[i][0] < slots1[i][1]
• slots2[i][0] < slots2[i][1]
• 0 <= slots1[i][j], slots2[i][j] <= 10^9
• 1 <= duration <= 10^6

(贪心，双指针) $O(n\log n)$

1. 首先将两个人的时间表从小到大排序。
2. 我们用 i 表示第一个人当前的时间段，j 表示第二个人。
3. 对于一个重合的时间段，[s1, e1] 和 [s2, e2]，如果 s2 <= s1 <= e2，则说明 i 开始的较晚，我们判断 min(e1, e2) - s1 是否满足 duration，若满足，则可以返回答案。若不满足，则根据 e1 和 e2 的大小关系推进 i 或 j。
4. 如果 j 开始的较晚同理。

时间复杂度

• 排序后，每个时间段最多扫描一次，故时间复杂度为 $O(n\log n)$。

空间复杂度

• 只需要常数的额外空间。

    vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
        int n = slots1.size(), m = slots2.size();
        auto cmp = [&](const vector<int>& x, const vector<int> &y) {
            return x[0] < y[0];
        };

        sort(slots1.begin(), slots1.end(), cmp);
        sort(slots2.begin(), slots2.end(), cmp);

        vector<int> ans;
        int i = 0, j = 0;

        while (i < n && j < m) {
            while (i < n && slots1[i][1] < slots2[j][0]) i++;
            if (i == n) break;

            while (j < m && slots2[j][1] < slots1[i][0]) j++;
            if (j == m) break;

            int s1 = slots1[i][0], e1 = slots1[i][1], s2 = slots2[j][0], e2 = slots2[j][1];

            if (s2 <= s1 && s1 <= e2) {
                if (min(e1, e2) - s1 >= duration) {
                    ans.push_back(s1);
                    ans.push_back(s1 + duration);
                    break;
                } else {
                    if (e1 < e2) i++;
                    else j++;
                }
            } else if (s1 <= s2 && s2 <= e1) {
                if (min(e1, e2) - s2 >= duration) {
                    ans.push_back(s2);
                    ans.push_back(s2 + duration);
                    break;
                } else {
                    if (e1 < e2) i++;
                    else j++;
                }
            }
        }

        return ans;
    }

https://www.cnblogs.com/seyjs/p/11713518.html
首先对slots1和slots2分别按start排好序。接下来分别从slots1和slots2中取第一个元素，判断两个元素是否满足会议，如果不满足，则从end较小的元素对应的slots中取后一个元素。以此类推，直到找出符合条件的slot为止。

    def minAvailableDuration(self, slots1, slots2, duration):
        """
        :type slots1: List[List[int]]
        :type slots2: List[List[int]]
        :type duration: int
        :rtype: List[int]
        """
        def cmpf(v1,v2):
            return v1[0] - v2[0]
        slots1.sort(cmp=cmpf)
        slots2.sort(cmp=cmpf)
        inx1 = inx2 = 0
        while inx1 < len(slots1) and inx2 < len(slots2):
            item1 = slots1[inx1]
            item2 = slots2[inx2]
            if item1[0] > item2[1]:
                inx2 += 1
            elif item1[1] < item2[0]:
                inx1 += 1
            else:
                ms = max(item1[0],item2[0])
                me = min(item1[1],item2[1])
                if me - ms >= duration:
                    return [ms,ms+duration]
                if item1[1] < item2[1]:
                    inx1 += 1
                else:
                    inx2 += 1
        return []

X. Video
https://www.bilibili.com/video/av71845446/

LeetCode 1147 - Longest Chunked Palindrome Decomposition

https://leetcode.com/problems/longest-chunked-palindrome-decomposition/

Return the largest possible k such that there exists a_1, a_2, ..., a_k such that:

• Each a_i is a non-empty string;
• Their concatenation a_1 + a_2 + ... + a_k is equal to text;
• For all 1 <= i <= k,  a_i = a_{k+1 - i}.

Example 1:

Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7
Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".

Example 2:

Input: text = "merchant"
Output: 1
Explanation: We can split the string on "(merchant)".

Example 3:

Input: text = "antaprezatepzapreanta"
Output: 11
Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)".

Example 4:

Input: text = "aaa"
Output: 3
Explanation: We can split the string on "(a)(a)(a)".

Constraints:

• text consists only of lowercase English characters.
• 1 <= text.length <= 1000

https://www.codetd.com/en/article/6958381

Problem-solving ideas: This title is not too difficult, my approach is a greedy algorithm + dual pointers. First introducing two variables head and tail, respectively, equal to text [0] and text [-1]. If the head is equal to tail, which represents both the part may be composed of two palindromic segment, then make head equal text [1], tail equal text [-2]; if the two are not equal, so that head = head + text [0] , tail = text [-2] + tail, head until it equals the tail. Principle is equal to the tail head encounters each case, which represents a part of two palindromic segment, head and tail of the reset value.

code show as below:

class Solution(object):
    def longestDecomposition(self, text):
        """
        :type text: str
        :rtype: int
        """
        res = 0
        head_inx = 0
        tail_inx = len(text) - 1
        head = ''
        tail = ''
        while head_inx <= tail_inx and head_inx < len(text) and tail_inx >= 0:
            if head == '' and tail == '':
                head = text[head_inx]
                tail = text[tail_inx]
                head_inx += 1
                tail_inx -= 1
            elif head == tail:
                res += 2
                head = text[head_inx]
                tail = text[tail_inx]
                head_inx += 1
                tail_inx -= 1
            else:
                #head_inx += 1
                #tail_inx -= 1
                head = head + text[head_inx]
                tail = text[tail_inx] + tail
                head_inx += 1
                tail_inx -= 1
        res += 2 if  head == tail and head_inx - len(head) != tail_inx + len(tail) else 1
        return res if res != 0 else 1

https://zxi.mytechroad.com/blog/greedy/leetcode-1147-longest-chunked-palindrome-decomposition/
Solution: Greedy
Break the string when the shortest palindrome is found.
prefer to use string_view

Time complexity: O(n^2)
Space complexity: O(n)

  int longestDecomposition(string_view text) {    

    const int n = text.length();

    if (n == 0) return 0;

    for (int l = 1; l <= n / 2; ++l) {

      if (text.substr(0, l) == text.substr(n - l))

        return 2 + longestDecomposition(text.substr(l, n - 2 * l));

    }

    return 1;

  }

https://www.acwing.com/solution/LeetCode/content/3433/

(贪心) $O(n^2)$

1. 可以证明，如果能找到最短的字符串的前缀和后缀，则我们就将其拆分出来。这样迭代下去，一定是答案最大的。
2. 也就是说，不存在一个因为拆分出了长度更小的段，而导致整体答案变小的情况。
3. 所以我们可以通过枚举首尾的情况，来拆分字符串。
4. 对于当前字符串，从小到大枚举长度 len 表示期望的相同的段的长度，直到当前字符串长度的一半，然后枚举判断前缀和后缀子串是否相同。
5. 如果找到了一个相同的前后缀，则答案加 2，更新字符串重新迭代；否则答案加 1，退出迭代。

时间复杂度

• 最坏情况下，整个字符串不可拆分，此时需要 $O(n^2)$ 的时间去枚举验证。
• 故时间复杂度为 $O(n^2)$。

空间复杂度

• 没有用任何额外的数组，故空间复杂度为 $O(1)$。

    bool check(int l, int r, int len, const string& text) {
        for (int i = l, j = r - len + 1; j <= r; i++, j++)
            if (text[i] != text[j])
                return false;

        return true;
    }

    int longestDecomposition(string text) {
        int n = text.length();
        int l = 0, r = n - 1;
        int ans = 0;
        while (l <= r) {
            int length = r - l + 1;
            bool flag = false;
            for (int len = 1; len <= length / 2; len++)
                if (check(l, r, len, text)) {
                    l += len;
                    r -= len;
                    flag = true;
                    break;
                }

            if (!flag) {
                ans++;
                break;
            }
            else
                ans += 2;
        }
        return ans;
    }

https://xindubawukong.github.io/2019/08/15/Leetcode-1147-Longest-Chunked-Palindrome-Decomposition/

)的做法，枚举中间一块的长度，然后从中间向两边贪心，判断字符串相等使用hash。后来发现，直接从两边往中间贪心就行了。。连hash都不用，直接暴力判断。

    int longestDecomposition(string text) {
        int n = text.length();
        int ans = 0;
        int l = 0, r = 0;
        while (r * 2 + 1 < n) {
            if (text.substr(l, r - l + 1) == text.substr(n - r - 1, r - l + 1)) {
                ans += 2;
                l = r + 1;
                r = l;
                continue;
            }
            r++;
        }
        if (n % 2 == 0 && l == n / 2) return ans;
        return ans + 1;
    }

X. https://algorithm-notes-allinone.blogspot.com/2019/08/leetcode-1147-longest-chunked.html
The first response to this question is that we need to run a recursion with dp or memo, to gradually converge to the base case. See the code below,

class Solution {
public:
    int longestDecomposition(string text) {
        int res = 1, len = text.size();
        vector<vector<int>> memo(len, vector<int>(len, -1));
        dsf(text, 0, len-1, memo);
        return memo[0][len-1];
    }
 
private:
    int dsf(string &ts, int x, int y, vector<vector<int>> &memo) {
        if(x<0 || y>=ts.size() || x>y) return 0;
        if(memo[x][y] != -1) return memo[x][y];
        int t = 1;
        for(int i=x; i<=(y-x+1)/2; ++i) {
            if(ts.substr(x, i) == ts.substr(y-i+1, i)) {
                t = max(t, 2 + dsf(ts, x+i, y-i, memo));
            }
        }
        memo[x][y] = t;
        return memo[x][y];
    }