My Blog | 详情

Leetcode周赛249 —— 题解

1.leetcode_1929_Concatenation_of_Array

分析：很直白，根据给定的 n 长度数组 nums，创建一个 2n 的数组，前 n 个元素的子数组和后 n 个元素的子数组均和 nums 相等。直接 2n 次赋值即可，当 i > n 时，index = i % nums.length

Complexity:

Time: O(n)

Space: O(1)

完整代码：

// AC: Runtime: 2 ms, faster than 100.00% of Java online submissions for Concatenation of Array.
// Memory Usage: 47.7 MB, less than 100.00% of Java online submissions for Concatenation of Array.
// .
// T:O(n), S:O(1)
// 
class Solution {
    public int[] getConcatenation(int[] nums) {
        int size = nums.length;
        int[] ret = new int[2 * size];
        for (int i = 0; i < 2 * size; i++) {
            ret[i] = nums[i % size];
        }

        return ret;
    }
}

2.leetcode_1930_Unique_Length-3_Palindromic_Subsequences

源地址：Unique Length-3 Palindromic Subsequences - LeetCode

分析：给定一个由小写字母字符串 s，希望找出其中满足要求的 不同的 长度为 3 的子序列。要求是长度为 3 的子序列为回文序列。

当长度为 3 的回文子序列被选出时，区分子序列的因素只有两个：

开头的字母
中间的字母。

这样就很清晰了，理论上至多只会产生 26 * 26 = 676 个唯一子序列。

所以我们遍历 s，记录每一个字母的首次出现位置 start-index，最后一次出现位置 end-index。当拿到字母的 start-index, end-index 后，只需统计在此区间有多少个不同的字母，即是此字母开头的子序列能产生的回文序列个数。

Complexity:

Time: O(26 * n) ~ O(n)

Space: O(26 * 2) ~ O(1)

完整代码：

// AC: Runtime: 74 ms, faster than 100.00% of Java online submissions for Unique Length-3 Palindromic Subsequences.
// Memory Usage: 51.5 MB, less than 50.00% of Java online submissions for Unique Length-3 Palindromic Subsequences.
// thought: record the start-index and end-index of every char, and count the distinct char between (start-index, end-index)
// T:O(n^2), S:O(1)
// 
class Solution {
    public int countPalindromicSubsequence(String s) {
        int size = s.length(), ret = 0;
        HashMap<Character, List<Integer>> charIndex = new HashMap<>();
        for (int i = 0; i < size; i++) {
            char c = s.charAt(i);
            if (charIndex.get(c) != null) {
                if (charIndex.get(c).size() == 1) {
                    charIndex.get(c).add(i);
                } else {
                    charIndex.get(c).set(1, i);
                }
            } else {
                List<Integer> tempList = new LinkedList<>();
                tempList.add(i);
                charIndex.put(c, tempList);
            }
        }
        for (int i = 0; i < 26; i++) {
            char c = (char) (i + 'a');
            if (charIndex.get(c) != null && charIndex.get(c).size() == 2) {
                HashSet<Character> tempRecord = new HashSet<>();
                int startIndex = charIndex.get(c).get(0), endIndex = charIndex.get(c).get(1);
                if (endIndex - startIndex == 1) {
                    continue;
                }
                for (int j = startIndex + 1; j <= endIndex - 1; j++) {
                    tempRecord.add(s.charAt(j));
                    // reach max possible value, break
                    if (tempRecord.size() == 26) {
                        break;
                    }
                }
                ret += tempRecord.size();
            }
        }

        return ret;
    }
}

3.leetcode_1931_Painting_a_Grid_With_Three_Different_Colors

源地址：Painting a Grid With Three Different Colors - LeetCode

分析：给定一个 m*n 的矩形网格，现在需要用三种固定颜色对网格进行染色，要求染完之后满足 任意相邻两个网格之间颜色不同。问共有多少种不同的染色的方案？结果用 (10^9 + 7) 取模后返回 int 结果。

要解决这个问题，可以先尝试解决一个简化版本的情形：

4.leetcode_1932_Merge_BSTs_to_Create_Single_BST

源地址：Merge BSTs to Create Single BST - LeetCode

分析：