ARTS打卡：第十五周

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

ARTS打卡：第十五周

每周完成一个ARTS：

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

Algorithm

387. First Unique Character in a String(Easy)

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Examples:

s = “leetcode”
return 0.

s = “loveleetcode”,
return 2.

Note: You may assume the string contain only lowercase letters.

题意

给一串字符串，在字符串中找到第一个不重复的字符并返回该字符的下标，若果不存在，则返回 -1。

注意：你可以假设该字符串只包含小写字母。

解题思路(1)

这道题解法其实很简单，可以用暴力破解来做，双重遍历就能找出答案，不过我们作为新时代的好青年，一定是要有追求的😏，我们可以借助散列表，将时间复杂度从 O(n²) 降至 O(n)。
我就不多解释，直接上代码了😝。

代码实现(1)

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
26
27
class Solution {
    public int firstUniqChar(String s) {
        // 边界条件
        if (s == null) {
            return -1;
        }
        // 创建一个哈希 map
        Map<Character, Integer> map = new HashMap<>(16);
        int n = s.length();
        // 首先遍历字符串中每个字符
        for (int i = 0; i < n; i++) {
            Character key = s.charAt(i);
            // 将字符作为 key，在字符串中出现的次数作为 value；判断 map 中有无包含当前字符，有则 value + 1，无则，将当前字符作为 key，value 设为 1
            map.put(key, map.getOrDefault(key, 0) + 1);
        }

        // 第二次遍历字符串，找出 map 中 value == 1 的字符，并返回当前下标
        for (int i = 0; i < n; i++) {
            Character key = s.charAt(i);
            if (map.get(key) == 1) {
                return i;
            }
        }
        // 无符合要求的字符，返回 -1
        return -1;
    }
}

运行结果和复杂度分析(1)

结果：Runtime: 38 ms, faster than 38.79% of Java online submissions for First Unique Character in a String.
Memory Usage: 38.1 MB, less than 98.75% of Java online submissions for First Unique Character in a String.

时间复杂度：在最坏的情况下，即不存在无重复的字符，时间复杂度是O(2n)，最好的情况下是 O(n)，所以时间复杂度位是 O(n)。
空间复杂度：O(n)。

解题思路(2)

解法来源于别人提交记录，题目中有说明，我们可以假设输入的字符串是一串小写字母串，那么就可以从这个角度出发，借助 Java API 来实现，详细思路看代码注释。

代码实现(2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int firstUniqChar(String s) {
    // 边界条件
    if (s == null) {
        return -1;
    }
    // 字符串长度
    int index = s.length();
    // 字符串是小写字母组成的字符串，所以字符范围在 a ~ z
    for (char i = 'a'; i <= 'z'; i++) {
        // String.indexOf（返回第一次出现指定字符的字符串中的索引，没有出现则返回 -1），所以 s.indexOf(i) != -1
        // String.lastIndexOf(返回指定字符的最后一次出现的字符串中的索引)，所以 s.indexOf(i) == s.lastIndexOf(i) 时，该字符没有重复
        // s.indexOf(i) < index 是要求出第一个没有重复字符
        if (s.indexOf(i) != -1 && s.indexOf(i) == s.lastIndexOf(i) && s.indexOf(i) < index) {
            index = s.indexOf(i);
        }
    }
    // 当index != s.length() 证明存在没有重复的字符
    if (index != s.length()) {
        return index;
    }
    return -1;
}

运行结果和复杂度分析(2)

Runtime: 1 ms, faster than 100.00% of Java online submissions for First Unique Character in a String.
Memory Usage: 36.6 MB, less than 99.82% of Java online submissions for First Unique Character in a String.

时间复杂度：O(1)
空间复杂度：O(1)

Review

本周阅读：《The Joel Test: 12 Steps to Better Code》
这一篇很老的文章，发行于2000年，不过作者在文章中写到的内容，现在来看还是挺有价值的，值的小伙伴们阅读。

Tip

本周分享从极客时间的《SQL必知必会》专栏中学习到的技巧：

  • mysql> select @@profiling;：查看profiling是否开启，开启能让MySQL收集在执行SQL时所使用的资源情况
    • profiling = 1 表示开启
    • profiling = 0 表示关闭
      image
  • show profilings：查看当前会话产生的所有profiling
  • show profiling：获取上一次查询的执行时间
    image

Share

本周分享：