ARTS打卡：第十六周

发表于 | 分类于 | 本文总阅读量 次

ARTS打卡：第十六周

每周完成一个ARTS：

  1. Algorithm：每周至少做一个 leetcode 的算法题
  2. Review：阅读并点评至少一篇英文技术文章
  3. Tip：学习至少一个技术技巧
  4. Share：分享一篇有观点和思考的技术文章

Algorithm

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

Input: s = “anagram”, t = “nagaram”
Output: true

Example 2:

Input: s = “rat”, t = “car”
Output: false

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

题意

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

说明：
你可以假设字符串只包含小写字母。

解题思路（1）

  1. 首先要清楚什么是字母异位词；两个单词如果包含相同的字母，次序不同，则称为字母易位词(anagram)
  2. 由题意可得，我们可以假设字符串只包含小写字母
  3. 由已知的1、2，我们可以快速的得出一个解法：将字符串分别分割为两个字符数组，然后分别进行字符排序，最后两个字符数组进行一一比对，就可以判断出是不是字母异位词了，当然，我们要加上限制条件，当字符串为空或两个字符串长度不等时，字符串 t 肯定不是字符串 s 的字母异位词。

代码实现（1）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean isAnagram(String s, String t) {
        // 边界条件 1. 当字符串为空或两个字符串长度不等时 false
        if (s == null || t == null || s.length() != t.length()) {
            return false;
        }
        // 2. 分别将字符串分解为字符数组
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        // 3. 对字符数组进行排序后，进行一一比对即可
        Arrays.sort(sChars);
        Arrays.sort(tChars);
        for (int i = 0; i < sChars.length; i++) {
            if (sChars[i] != tChars[i]) {
                return false;
            }
        }
        return true;
    }
}

运行结果和复杂度分析（1）

运行结果：
Runtime: 6 ms, faster than 43.67% of Java online submissions for Valid Anagram.
Memory Usage: 37.5 MB, less than 72.58% of Java online submissions for Valid Anagram.

复杂度分析：
时间复杂度：假设 Arrays.sort 的时间复杂度为 O(nlogn)，最后排序的时间复杂度为 O(n)，那么最终的时间复杂度为 O(nlogn)。
空间复杂度：取决于字符串的长度，这里假设为 O(n)

解题思路（2）

借鉴散列表的思想，换一个解题角度出发：

  1. 根据题意我们可以得出，给予的字符串的字符范围是 a - z，即26个字母
  2. 那么我们就可以用一个整形数组来进行存储字母，通过下标标识‘字母’，值表示字母出现的次数
  3. 数组下标如是何标识字母呢？我们可以结合 ASCII 码表来得出, 使用（当前字母 - a）的值为下标
  4. 这样我们就可以通过数组下标和值，推断出字符串 t 是不是字符串 s 的字母异位词
  5. 如果还没想出具体怎么做，嘻嘻😀，结合代码实现来理解，你会一瞬间恍然大悟的😜。

代码实现（2）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean isAnagram(String s, String t) {
        // 边界条件 1. 两字符串长度不一致，则返回 false
        if (s.length() != t.length()) {
            return false;
        }
        // 定义一个整数数组，模拟散列表
        int[] table = new int[26];
        // 遍历字符串字符
        for (int i = 0; i < s.length(); i++) {
            // 一个字符串的字符对应的值进行 + 1 操作
            // 另一个字符串的字符对应的值进行 - 1 操作
            table[s.charAt(i) - 'a']++;
            table[t.charAt(i) - 'a']--;
        }
        for (int i = 0; i < table.length; i++) {
            // 如果两个字符串是由相同数量且相等的字符组成，那么字符对应数组内的值，应该为0，因为两个字符串遍历字符时，分别做的是+1和-1的操作
            if (table[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

运行结果和复杂度分析（2）

运行结果：
Runtime: 4 ms, faster than 78.57% of Java online submissions for Valid Anagram.
Memory Usage: 36.2 MB, less than 99.41% of Java online submissions for Valid Anagram.

复杂度分析：
时间复杂度：只有两个遍历，即时间复杂度为 O(n)
空间复杂度：只额外使用了 数组 table[26]，所以空间复杂度为 O(1)

解题思路（3）

我们作为新生代的三好青年，当然要想想有没有比解法二更快的解法啦🤣~
我们可以从解法（2）出发，在此基础上进行优化，比如char 和 int 之间存在隐式转换，那么我们可以直接将字符作为 int[] 的下标，去掉 String.charAt() - ‘a’ 的消耗。

代码实现（3）

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
class Solution {
    public boolean isAnagram(String s, String t) {
        // 边界条件 1. 两字符串长度不一致，则返回 false
        if (s == null || t == null || s.length() != t.length()) {
            return false;
        }
        // ASCII 码表加上拓展集共256个字符，所以我们定义一个长度为256的整数数组来模拟散列表
        int[] table = new int[256];
        for (char c : s.toCharArray()) {
            // 一个字符串的字符对应的值进行 + 1 操作
            table[c]++;
        }
        for (char c : t.toCharArray()) {
            // 另一个字符串的字符对应的值进行 - 1 操作
            table[c]--;
        }
        for (int val : table) {
            // 如果两个字符串是由相同数量且相等的字符组成，那么字符对应数组内的值，应该为0，因为两个字符串遍历字符时，分别做的是+1和-1的操作
            if (val != 0) {
                return false;
            }
        }
        return true;
    }
}

运行结果和复杂度分析（3）

运行结果：
Runtime: 2 ms, faster than 99.82% of Java online submissions for Valid Anagram.
Memory Usage: 36.4 MB, less than 99.35% of Java online submissions for Valid Anagram.

复杂度分析：
时间复杂度：只有两个遍历，即时间复杂度为 O(n)
空间复杂度：只额外使用了整形数组 table[256]，所以空间复杂度为 O(1)

Review

本周阅读的是：What is Test-Driven Development (TDD)?

作者在文中介绍了什么是TDD（测试驱动开发）？并详细阐述了为什么TDD（测试驱动开发）在企业应用程序中是很重要的，以及对测试用例的覆盖率，进行了讨论，作者认为测试用例的覆盖率无需时刻做到100%，100%的代码覆盖率，不应该成为追求的目标，应该视业务场景而定，比如复杂的业务，可能需要做到90%，简单新功能，可能做到50%就可以了。

Tip

本周分享 Intellij IDEA 的两个快捷键：

  1. Ctrl+F12：可以快速定位到当前类的任何方法和变量。
    Ctrl+F12
  2. Alt+F7：Find Usages，从名字上就可以看出来了，可以快速的定位到类或方法或变量的任何被引用的地方。
    Find Usages

Share

本周分享：Spring Boot vs. Spring MVC vs. Spring: How Do They Compare?
译文可以看这篇：Spring、Spring MVC、Spring Boot三者的关系还傻傻分不清楚？