Leetcode周赛249 —— 题解
1.leetcode_1929_Concatenation_of_Array

原地址:Concatenation of Array - LeetCode

分析:很直白,根据给定的 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 的回文子序列被选出时,区分子序列的因素只有两个:

  1. 开头的字母
  2. 中间的字母。

这样就很清晰了,理论上至多只会产生 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

分析: