坚持记录完成LeetCode的每日一题

[0622] 面试题 16. 18. Pattern Matching LCCI (Medium)

KeyWords: 字符串与哈希表

Question

You are given two strings, pattern and value. The pattern string consists of just the letters a and b, describing a pattern within a string. For example, the string catcatgocatgo matches the pattern aabab (where cat is a and go is b). It also matches patterns like a, ab, and b. Write a method to determine if value matches pattern. a and b cannot be the same string.

Example 1:

1 2	`Input: pattern = "abba", value = "dogcatcatdog" Output: true`

Example 2:

1 2	`Input: pattern = "abba", value = "dogcatcatfish" Output: false`

Example 3:

1 2	`Input: pattern = "aaaa", value = "dogcatcatdog" Output: false`

Example 4:

1 2	`Input: pattern = "abba", value = "dogdogdogdog" Output: true`

Explanation: "a"="dogdog",b=""，vice versa.

Note: 0 <= len(pattern) <= 1000 0 <= len(value) <= 1000 pattern only contains "a" and "b", value only contains lowercase letters.

Intuition

枚举

本题的算法实现不难，但是细节较多。题目中给出的 pattern 和 value 的长度可以为 0，因此需要充分考虑边界情况。

我们设 $\textit{pattern}$ 的长度为 $\ell_p$ ，$\textit{value}$ 的长度为 $\ell_v$ 。根据题目描述，我们需要给字母 a 和 b 分配不同的字符串值（可以为空字符串），使得将 $\textit{pattern}$ 中的字母替换成对应的字符串后，结果与 $\textit{value}$ 相同。

在分配字符串之前，我们不妨先分配 a 和 b 对应字符串的长度。如果确定了长度，那么我们只要将 $\textit{value}$ 按照 $\textit{pattrn}$ 中出现字母的顺序，划分成 $\ell_p$ 个子串，并判断其中 a 对应的子串是否相同，以及 b 对应的子串是否相同即可。具体地，假设 $\textit{pattern}$ 中出现了 $c_a$ 个 a 以及 $\ell_p - c_a$ 个 b，并且 a 和 b 对应字符串的长度分别为 $\ell_a$ 和 $\ell_b$ ，那么必须要满足：

\[ c_a * \ell_a + (\ell_p - c_a) * \ell_b = \ell_v \]

其中 $c_a$ 是已知的常量，$\ell_a$ 和 $\ell_b$ 是未知数。这是一个二元一次方程，可能无解、有唯一解或者无数解。然而我们需要的仅仅是自然数解，也就是 $\ell_a$ 和 $\ell_b$ 都大于等于 $0$ 的解，因此我们可以直接枚举 $\ell_a$ 的值，它必须是 $[0, \frac{\ell_v}{c_a}]$ 之间的自然数，否则 $\ell_b$ 就不会大于等于 0 了。在枚举 $\ell_a$ 之后，我们将其带入等式并解出 $\ell_b$。如果 $\ell_b$ 是整数，我们就枚举了一组 a 和 b 的可能长度。

在枚举了长度之后，我们就可以根据 $\textit{pattern}$ 来将 $\textit{value}$ 划分成 $\ell_p$ 个子串。具体地，我们遍历 $\textit{pattern}$，并用一个指针 $\textit{pos}$ 来帮助我们进行划分。当我们遍历到一个 $a$ 时，我们取出从 $\textit{pos}$ 开始，长度为 $\ell_a$ 的子串。如果这是我们第一次遇到字母 aa，我们就得到了 $a$ 应该对应的子串；否则，我们将取出的子串与 $a$ 应该对应的子串进行比较，如果不相同，说明模式匹配失败。

同理，当我们遍历到一个 $b$ 时，我们取出从 $\textit{pos}$ 开始，长度为 $\ell_b$ 的子串，根据是否第一次遇到字母 $b$ 来进行比较。在比较结束后，我们将 $\textit{pos}$ 向后移动，进行下一个字母的匹配。

在遍历完成之后，如果匹配没有失败，我们还需要判断一下 aa 和 bb 是否对应了不同的子串。只有它们对应的子串不同时，才是一种满足题目要求的模式匹配。

细节

上面的算法看上去不是很复杂：我们只需要用一重循环枚举 $\ell_a$，计算出 $\ell_b$，再用一重循环遍历 $\textit{pattern}$ 以及移动 $\textit{pos}$ 即可。但就像我们在「前言」部分所说的，本题有非常多的细节需要考虑。

我们回到二元一次方程：

\[ c_a * \ell_a + (\ell_p - c_a) * \ell_b = \ell_v \] 如果我们枚举 $\ell_a$，那么必须要求 $c_a \neq 0$，因为在 $c_a = 0$ 的情况下，原方程如果有解，那么一定有无数解（因为 $\ell_a$ 可以取任意值）。因此如果 $c_a = 0$，我们就必须枚举 $\ell_b$ 。这无疑增加了编码的复杂度，因为需要根据 $c_a$ 的值选择对 $\ell_a$ 或 $\ell_b$ 进行枚举，失去了统一性。并且，如果 $\ell_p - c_a$ 也为 0，那么我们连 $\ell_b$都无法枚举。

因此，我们必须梳理一下判断的逻辑：

如果 $\textit{pattern}$ 为空，那么只有在 $\textit{value}$ 也为空时，它们才能匹配；

如果 $\textit{value}$ 为空，那么如果 $\textit{pattern}$ 也为空，就和第一条的情况相同；如果 $\textit{pattern}$ 中只出现了一种字母，我们可以令该字母为空，另一没有出现的字母为任意非空串，就可以正确匹配；如果 $\textit{pattern}$ 中出现了两种字母，那么就无法正确匹配，因为这两种字母都必须为空串，而题目描述中规定它们不能表示相同的字符串；

如果 $\textit{pattern}$ 和 $\textit{value}$ 均非空，那么我们需要枚举 $\textit{pattern}$ 中出现的那个字母（如果两个字母均出现，可以枚举任意一个）对应的长度，使用上面提到的算法进行判断。

对于上面的第三条，我们可以根据「对称性」减少代码的编写的复杂度：我们还是固定枚举 $\ell_a$，但如果 $c_a < \ell_p - c_a$ ，即 $a$ 出现的次数少于 $b$ 出现的次数，那么我们就将 $\textit{pattern}$ 中所有的 $a$ 替换成 $b$，$b$ 替换成 $a$。这样做就保证了 $a$ 出现了至少一次（$c_a > 0$），枚举 $\ell_a$就不会有任何问题，同时不会影响答案的正确性。

这样一来，我们就可以优化判断的逻辑：我们首先保证 $\textit{pattern}$ 中 $a$ 出现的次数不少于 $b$ 出现的次数。如果不满足，我们就将 $a$ 和 $b$ 互相替换；如果 $\textit{value}$ 为空，那么要求 $\textit{pattern}$ 也为空（$\ell_p = 0$）或者只出现了字母 $a$（$\ell_p - c_a = 0$），这两种情况均等同于 $\ell_p - c_a = 0$。在其余情况下，都无法匹配成功；如果$ $ 为空且 $\textit{value}$ 不为空，那么无法匹配成功；如果 $\textit{pattern}$ 和 $ $ 均非空，我们就可以枚举 $\ell_a$。

正则表达式

构造正则表达式解决问题

参考链接

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/pattern-matching-lcci/solution/mo-shi-pi-pei-by-leetcode-solution/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Java Code

枚举

class Solution {
    public boolean patternMatching(String pattern, String value) {
        int count_a = 0, count_b = 0;
        for (char ch: pattern.toCharArray()) {
            if (ch == 'a') {
                ++count_a;
            } else {
                ++count_b;
            }
        }
        if (count_a < count_b) {
            int temp = count_a;
            count_a = count_b;
            count_b = temp;
            char[] array = pattern.toCharArray();
            for (int i = 0; i < array.length; i++) {
                array[i] = array[i] == 'a' ? 'b' : 'a';
            }
            pattern = new String(array);
        }
        if (value.length() == 0) {
            return count_b == 0;
        }
        if (pattern.length() == 0) {
            return false;
        }
        for (int len_a = 0; count_a * len_a <= value.length(); ++len_a) {
            int rest = value.length() - count_a * len_a;
            if ((count_b == 0 && rest == 0) || (count_b != 0 && rest % count_b == 0)) {
                int len_b = (count_b == 0 ? 0 : rest / count_b);
                int pos = 0;
                boolean correct = true;
                String value_a = "", value_b = "";
                for (char ch: pattern.toCharArray()) {
                    if (ch == 'a') {
                        String sub = value.substring(pos, pos + len_a);
                        if (value_a.length() == 0) {
                            value_a = sub;
                        } else if (!value_a.equals(sub)) {
                            correct = false;
                            break;
                        }
                        pos += len_a;
                    } else {
                        String sub = value.substring(pos, pos + len_b);
                        if (value_b.length() == 0) {
                            value_b = sub;
                        } else if (!value_b.equals(sub)) {
                            correct = false;
                            break;
                        }
                        pos += len_b;
                    }
                }
                if (correct && !value_a.equals(value_b)) {
                    return true;
                }
            }
        }
        return false;
    }
}

正则表达式

class Solution {
    public boolean patternMatching(String pattern, String value) {
     if (value.length() == 0) {
            return pattern.length() <= 1;
        }
        if (pattern.length() == 0) {
            return value.length() == 0;
        }

        Map<String, String> map = new HashMap<>();
        String start = pattern.substring(0, 1);
        if(start.equals("a")){
            map.put("a", "\\1");
            map.put("b", "\\2");
        }else {
            map.put("a", "\\2");
            map.put("b", "\\1");
        }

        StringBuilder newPatter = new StringBuilder();
        boolean boolena = true;
        boolean boolenb = true;
        for(int i = 0; i < pattern.length(); i++){
            String sub = pattern.substring(i, i+1);
            switch (sub){
                case "a":
                    if(boolena){
                        newPatter.append("(\\w*)");
                        boolena = false;
                    }else {
                        newPatter.append(map.get("a"));
                    }
                    break;
                case "b":
                    if(boolenb){
                        newPatter.append("(\\w*)");
                        boolenb = false;
                    }else {
                        newPatter.append(map.get("b"));
                    }
            }
        }
        return value.matches(newPatter.toString());
    }
}

[0623] 67. Add Binary (Easy)

67. Add Binary Leetcode 67. 二进制求和（易）

[0624] 15. 3Sum Closest (Medium)

3Sum Closest LeetCode 15. 三数之和（中）

[0625] 139. Word Break (Medium)

EveryDay Check LOST，端午节放假的原因，在外面玩了一整天，LeetCode每日一题 lost。以后无论什么日子，每天起床第一件事情，把当天的LeetCode做了。

KeyWords: 动态规划

Question

139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words.

Example 1:

1 2	`Input: s = "leetcode", wordDict = ["leet", "code"] Output: true`

Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

1 2	`Input: s = "applepenapple", wordDict = ["apple", "pen"] Output: true`

Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.

Example 3:

1 2	`Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] Output: false`

Intuition

我们定义 $\textit{dp}[i]$ 表示字符串 $s$ 前 $i$ 个字符组成的字符串 $s[0..i-1]$ 是否能被空格拆分成若干个字典中出现的单词。从前往后计算考虑转移方程，每次转移的时候我们需要枚举包含位置 $i-1$ 的最后一个单词，看它是否出现在字典中以及除去这部分的字符串是否合法即可。公式化来说，我们需要枚举 $s[0..i-1]$ 中的分割点 $j$ ，看 $s[0..j-1]$ 组成的字符串 $s_1$（默认 $j = 0$ 时 $s_1$ 为空串）和 $s[j..i-1]$ 组成的字符串 $s_2$ 是否都合法，如果两个字符串均合法，那么按照定义 $s_1$ 和 $s_2$ 拼接成的字符串也同样合法。由于计算到 $\textit{dp}[i]$ 时我们已经计算出了 $\textit{dp}[0..i-1]$ 的值，因此字符串 $s_1$ 是否合法可以直接由 $dp[j]$ 得知，剩下的我们只需要看 $s_2$ 是否合法即可，因此我们可以得出如下转移方程： \[ \textit{dp}[i]=\textit{dp}[j]\ \&\&\ \textit{check}(s[j..i-1]) \]

其中 $\textit{check}(s[j..i-1])$ 表示子串 $s[j..i-1]$ 是否出现在字典中。

对于检查一个字符串是否出现在给定的字符串列表里一般可以考虑哈希表来快速判断，同时也可以做一些简单的剪枝，枚举分割点的时候倒着枚举，如果分割点 $j$ 到 $i$ 的长度已经大于字典列表里最长的单词的长度，那么就结束枚举，但是需要注意的是下面的代码给出的是不带剪枝的写法。

对于边界条件，我们定义 $\textit{dp}[0]=true$ 表示空串且合法。

参考链接

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/word-break/solution/dan-ci-chai-fen-by-leetcode-solution/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Java Code

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

[0626] 面试题 02.01. 移除重复节点 (easy)

Key words: 字符串与哈希表、链表

Question

面试题 02.01. 移除重复节点

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例1:

1 2	`输入：[1, 2, 3, 3, 2, 1] 输出：[1, 2, 3]`

示例2:

1 2	`输入：[1, 1, 1, 1, 2] 输出：[1, 2]`

提示：

链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。

进阶：如果不得使用临时缓冲区，该怎么解决？

Intuition

缓冲区解法

基于hash map去重

复杂度分析

时间复杂度：$O(N)$
空间复杂度：$O(N)$

双层循环

给定的链表上使用两重循环，其中第一重循环从链表的头节点开始，枚举一个保留的节点，这是因为我们保留的是「最开始出现的节点」。第二重循环从枚举的保留节点开始，到链表的末尾结束，将所有与保留节点相同的节点全部移除。

复杂度分析

时间复杂度：$O(N^2)$
空间复杂度：$O(1)$

参考链接

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/remove-duplicate-node-lcci/solution/yi-chu-zhong-fu-jie-dian-by-leetcode-solution/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Java Code

缓冲区解法

class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        // 特殊用例判定
        if (head == null) {
            return head;
        }
        // 声明hashmap
        ListNode pos = head;
        Set<Integer> hashmap = new HashSet<Integer>();
        // 注意此处要在while之外将头节点添加进去
        hashmap.add(pos.val);

        // 依次遍历链表节点进行判重
        while (pos.next != null) {
            if (hashmap.add(pos.next.val)) {
                pos = pos.next;
            } else {
                pos.next = pos.next.next;
            }
        }

        // 将最后一位置为null
        pos.next = null;

        // 返回处理之后的头节点
        return head;
    }
}

双层循环解法

class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {        
        // 声明外部指针
        ListNode outter = head;
        // 依次遍历判重
        // 外层循环
        while (outter != null) {
            ListNode inner = outter;
            // 内层循环
            while (inner.next != null) {
                if (outter.val == inner.next.val) {
                    // 遇到重复的直接跳过
                    inner.next = inner.next.next;
                } else {
                    // 不是重复的元素就保留
                    inner = inner.next;
                }
            }
            // 更新外层循环指针
            outter = outter.next;
        }
        // 返回处理之后的头节点
        return head;
    }
}

[0627] 41. First Missing Positive (Hard)

41. First Missing Positive LeetCode 41. 缺失的第一个正数（难）

[0628] 209. Minimum Size Subarray Sum (Medium)

209. Minimum Size Subarray Sum

Keywords: 二分查找和搜索、数组与指针

Question

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Example:

1 2	`Input: s = 7, nums = [2,3,1,2,4,3] Output: 2`

Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Intuition

前缀和 + 二分查找

在确定每个子数组的开始下标后，找到长度最小的子数组需要 $O(n)$ 的时间。如果使用二分查找，则可以将时间优化到 $O(\log n)$。

为了使用二分查找，需要额外创建一个数组 $\text{sums}$ 用于存储数组 $\text{nums}$ 的前缀和，其中 $\text{sums}[i]$ 表示从 $\text{nums}[0]$ 到 $\text{nums}[i-1]$ 的元素和。得到前缀和之后，对于每个开始下标 $i$，可通过二分查找得到大于或等于 $i$ 的最小下标 $\textit{bound}$，使得 $\text{sums}[\textit{bound}]-\text{sums}[i-1] \ge s$，并更新子数组的最小长度（此时子数组的长度是 $\textit{bound}-(i-1)$）。

因为这道题保证了数组中每个元素都为正，所以前缀和一定是递增的，这一点保证了二分的正确性。如果题目没有说明数组中每个元素都为正，这里就不能使用二分来查找这个位置了。

复杂度分析

时间复杂度：$O(n \log n)$
空间复杂度：$O(n)$

双指针

定义两个指针 $\textit{start}$ 和 $\textit{end}$ 分别表示子数组的开始位置和结束位置，维护变量 $\textit{sum}$ 存储子数组中的元素和（即从$ []$ 到 $\text{nums}[\textit{end}]$ 的元素和）。

初始状态下，$\textit{start}$ 和 $\textit{end}$ 都指向下标 $0$，$\textit{sum}$ 的值为 $0$。

每一轮迭代，将 $\text{nums}[end]$ 加到 $\textit{sum}$，如果 $\textit{sum} \ge s$，则更新子数组的最小长度（此时子数组的长度是 $\textit{end}-\textit{start}+1$），然后将 $\text{nums}[start]$ 从 $\textit{sum}$ 中减去并将 $\textit{start}$ 右移，直到 $\textit{sum} < s$，在此过程中同样更新子数组的最小长度。在每一轮迭代的最后，将 $\textit{end}$ 右移。

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是数组的长度。指针 $\textit{start}$ 和 $\textit{end}$ 最多各移动 $n$ 次。
空间复杂度：$O(1)$

Java Code

前缀和 + 二分查找

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int[] sums = new int[n + 1]; 
        // 为了方便计算，令 size = n + 1 
        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
        // 以此类推
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            int target = s + sums[i - 1];
            int bound = Arrays.binarySearch(sums, target);
            if (bound < 0) {
                bound = -bound - 1;
            }
            if (bound <= n) {
                ans = Math.min(ans, bound - (i - 1));
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

双指针

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

LeetCode

动态规划数组与指针字符串与哈希表二分查找和搜索链表

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

Ant Design Pro 上一篇

Java语法快查下一篇

LeetCode2020 0622-0628

[0622] 面试题 16. 18. Pattern Matching LCCI (Medium)

Question

Intuition

Java Code

[0623] 67. Add Binary (Easy)

[0624] 15. 3Sum Closest (Medium)

[0625] 139. Word Break (Medium)

Question

Intuition

Java Code

[0626] 面试题 02.01. 移除重复节点 (easy)

Question

Intuition

Java Code

[0627] 41. First Missing Positive (Hard)

[0628] 209. Minimum Size Subarray Sum (Medium)

Question

Intuition

Java Code