MichaelFu

题目

给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

示例

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]

示例 3：

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]

解法一

题目有两个要点：

1. 字符串数组里面的字符串长度都是一样的；
2. 要求字符串数组中的字符串都要连续连在一起的，前后顺序可以是任意排列组合；

假设，words 的长度是 n，words 中每个单词的长度是 w，所以我们每次可以从字符串 s 取 n * w 长度来判断它是否是 words 的自由排列组合。

在判断时，我们先将 words 中每个单词的数量放在一个计数器中，可以用 map 表示，例如：["aaa", "bbb"] 表示成 {"aaa": 1, "bbb": 1}；["aaa", "aaa", "ccc"] 表示成 {"aaa": 2, "ccc": 1}；然后我们将 s 中每个 n * w 长度的子串每 w 个一组放在一个 map 中计数，最后和 words 的计数器比较是否相等，如果相等就是我们想要的子串。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

use std::collections::HashMap;

impl Solution {
    pub fn find_substring(s: String, words: Vec<String>) -> Vec<i32> {
        let mut result: Vec<i32> = Vec::new();

        let n = words.len();
        if n == 0 {
            return result;
        }

        let w = words[0].len();
        if s.len() < n * w {
            return result;
        }

        let mut counter = HashMap::new();
        for i in 0..n {
            counter
                .entry(words[i].as_str())
                .and_modify(|count| *count += 1)
                .or_insert(1);
        }

        for i in 0..=(s.len() - n * w) {
            let mut tmp_counter = HashMap::new();
            for j in 0..n {
                let start = i + j * w;
                let tmp_str = &s[start..(start + w)];
                tmp_counter
                    .entry(tmp_str)
                    .and_modify(|count| *count += 1)
                    .or_insert(1);
            }
            if tmp_counter == counter {
                result.push(i as i32);
            }
        }

        result
    }
}

题目

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例

示例 1：

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2：

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3：

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 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
26
27
28
29
30
31
32

fn max(a: i32, b: i32) -> i32 {
    if a >= b {
        a
    } else {
        b
    }
}

impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let mut result = 0;
        let mut left = 0i32;
        let mut right = -1i32;
        let mut freq = [0; 127];
        let s = s.into_bytes();

        while (left as usize) < s.len() {
            let right_index = (right + 1) as usize;
            if right_index < s.len() && freq[s[right_index] as usize] == 0 {
                right += 1;
                freq[s[right_index] as usize] += 1;
            } else {
                freq[s[left as usize] as usize] -= 1;
                left += 1;
            }

            result = max(result, right - left + 1);
        }

        result
    }
}

题目

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

思路

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

impl Solution {
    pub fn add_two_numbers(
        l1: Option<Box<ListNode>>,
        l2: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        let mut head = Box::new(ListNode::new(0));
        let mut n1 = 0;
        let mut n2 = 0;
        let mut carry = 0;
        let mut current = &mut head;

        let mut l1 = l1;
        let mut l2 = l2;

        loop {
            if l1.is_none() && l2.is_none() && carry == 0 {
                break;
            }

            if l1.is_none() {
                n1 = 0;
            } else {
                n1 = l1.as_ref().unwrap().val;
                l1 = l1.unwrap().next;
            }

            if l2.is_none() {
                n2 = 0;
            } else {
                n2 = l2.as_ref().unwrap().val;
                l2 = l2.unwrap().next;
            }

            current.next = Some(Box::new(ListNode::new((n1 + n2 + carry) % 10)));
            current = current.next.as_mut().unwrap();
            carry = (n1 + n2 + carry) / 10;
        }

        head.next
    }
}

参考链接

1. Add Two Numbers

题目

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

在数组中找到 2 个数之和等于给定值的数字，结果返回 2 个数字在数组中的下标。

示例

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

输入：nums = [3,2,4], target = 6
输出：[1,2]

输入：nums = [3,3], target = 6
输出：[0,1]

思路

这道题最优的做法时间复杂度是 O(n)。顺序扫描数组，对每一个元素，在 map 中找能组合给定值的另一半数字，如果找到了，直接返回 2 个数字的下标即可。如果找不到，就把这个数字存入 map 中，等待扫到另一半数字的时候，再取出来返回结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14

use std::collections::HashMap;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut positions = HashMap::<i32, usize>::new();
        for i in 0..nums.len() { 
            if let Some(j) = positions.get(&(target - nums[i])) {
                return vec![*j as i32, i as i32];
            }
            positions.insert(nums[i], i);
        }
        vec![]
    }
}

参考链接

1. Two Sum

map 的目的是设计一种数据结构来维护一个集合的数据，并且能够对集合进行增删改查，实现 map 主要有两种数据结构：HashTable 和 搜索树。

HashTable 会用一个 hash 函数将将 key 分配到不同的 bucket 中，因此，开销主要在 hash 函数计算 key 哈希值上，大多时候，HashTable 的性能还是很高的。不过 HashTable 一般会存在碰撞，或者说冲突的问题，就是不同的 key 被映射到了同一个 bucket，对于这个问题，一般由两种应对方法，链表法和开放寻址法：

• 链表法是将一个 bucket 实现成一个链表，落在同一个 bucket 中的 key 都会插入这个链表；
• 开放寻址法是在发生冲突时，根据一定的规律，在 bucket 后面选择一个空位用来放置新的 key；

搜索树一般会采用自平衡搜索树实现，包括：AVL 树，红黑树或者 B-Tree，搜索实现中的查找效率是 O(logN)，而 HashTable 平均查找效率是 O(1)，hash 函数如果设计良好，不会出现 hash 碰撞的情况。两者不同的，搜索树可以实现按照 key 的顺序遍历，而 HashTable 的顺序是随机的。

有的语言中用两种不同的数据结构实现了 map，就像 Rust 中的 std::collections::BTreeMap 和 std::collections::HashMap。

Go 语言中采用了 HashTable 的方式来实现 map，并且使用链表法解决哈希冲突，本文基于 go1.18 darwin/arm64。

一直以来，从 JavaScript，PHP，Python到Golang，然后还有linux系统中，无处不见正则表达式的身影，可是一致困扰在POSIX和PCRE的概念中，分不清这两个是个啥，今天就来翻翻正则表达式的老底，了解了解正则表达式的前世今生。

Regular Expression的Regular一般被译为正则、正规、常规。此处的Regular即是规则的意思，Regular Expression即描述某种规则的表达式之意。

正则表达式（英语：Regular Expression，在代码中常简写为regex、regexp或RE），是计算机科学的一个概念。正则表达式使用单个字符串来描述、匹配一系列匹配某个句法规则的字符串。在很多文本编辑器里，正则表达式通常被用来检索、替换那些匹配某个模式的文本。

许多程序设计语言都支持利用正则表达式进行字符串操作。例如，在Perl中就内建了一个功能强大的正则表达式引擎。正则表达式这个概念最初是由Unix中的工具软件（例如sed和grep）普及开的。正则表达式通常缩写成regex，单数有regexp、regex，复数有regexps、regexes、regexen。

std::marker::PhantomData 是一个零大小的类型，用于标记一些类型，这些类型看起来拥有类型 T，但实际上并没有：

1
2
3

pub struct PhantomData<T>
 where
    T: ?Sized;

Rust 并不希望在定义类型时，出现目前还没使用，但未来会被使用的泛型参数，例如未使用的生命周期参数以及未使用的类型。

PhantomData 最常见的用例可能是具有未使用的生命周期参数的结构体，例如，这儿有一个结构体 Slice，它有两个 *const T 类型的指针，可能指向某个地方的数组，我们期望 Slice 类型的值在生命周期 'a 内仅仅有效，但是如果像下面这样，'a 我们又无处安放：

1
2
3
4

struct Slice<'a, T> {
    start: *const T,
    end: *const T,
}

我们可以使用 PhantomData 告诉编译器就像 Slice 结构包含引用 &'a T 一样来纠正这个问题：

1
2
3
4
5
6
7

use std::marker::PhantomData;

struct Slice<'a, T: 'a> {
    start: *const T,
    end: *const T,
    phantom: PhantomData<&'a T>,
}

这反过来要求 T 类型中的任何引用在生命周期 'a 内都是有效的，初始化 Slice 时，仅需要为 phantom 字段提供值 PhantomData 即可：

1
2
3
4
5
6
7
8

fn borrow_vec<T>(vec: &Vec<T>) -> Slice<'_, T> {
    let ptr = vec.as_ptr();
    Slice {
        start: ptr,
        end: unsafe { ptr.add(vec.len()) },
        phantom: PhantomData,
    }
}

slice 是 Go 里面最常用的数据结构之一，相比起长度固定的数组，slice 使用起来更加灵活，它可以动态扩容，可以从其他 slice 或者数组创建。不过 slice 的底层依然是一个固定长度的数组，也就是一片连续内存，当插入新的元素时，如果当前容量不够，就需要扩容，申请一片足够大的内存，并将原有的内容的复制进去。

接下来的测试使用的 Go 版本都是：go version go1.18 darwin/arm64。

创建一个 slice，我们有下面几种方法（Go 官方文档中也有详细的说明）：

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
28

package main

import "fmt"

func main() {
	// 方法一：slice 字面量
	var s1 = []int{1, 2, 3, 4}
	fmt.Println(s1, len(s1), cap(s1))

	// 方法二：使用 make 创建
	var s2 = make([]int, 10, 10)
	fmt.Println(s2, len(s2), cap(s2))

	// 方法三：从数组或者slice创建，引用数组的部分片段
	// 形式是：arr[low:high]，那么创建的 slice 长度是 high-low，容量是：cap(arr) - low
	var arr = [10]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
	var s3 = arr[2:8]
	fmt.Println(s3, len(s3), cap(s3))

	// 方法四：类似前面的方法，但是我们在创建时可以指定最大容量，形式是：arr[low:high:max]
	// 这种情况下容量是 max - low，长度是：high - low
	var s4 = s3[1:4:7]
	fmt.Println(s4, len(s4), cap(s4))

	// 当然还有其他的形式，例如我们可以从数组的指针创建
	var s5 = (&arr)[2:4]
	fmt.Println(s5, len(s5), cap(s5))
}

这将输出：

[1 2 3 4] 4 4
[0 0 0 0 0 0 0 0 0 0] 10 10
[2 3 4 5 6 7] 6 8
[3 4 5] 3 6
[2 3] 2 8

很多时候，我们需要实现一些自动优化的数据结构，在某些情况下是一种优化的数据结构和相应的算法，在其他情况下使用通用的结构和通用的算法。比如当一个 HashSet 的内容比较少的时候，可以用数组实现，但内容逐渐增多，再转换成用哈希表实现。如果我们想让使用者不用关心这些实现的细节，使用同样的接口就能享受到更好的性能，那么，就可以考虑用智能指针来统一它的行为。

我们来实现一个智能 String，Rust 下 String 在栈上占了 24 个字节，然后在堆上存放字符串实际的内容，对于一些比较短的字符串，这很浪费内存。

参考 Cow，我们可以用一个 enum 来处理：当字符串小于 N 字节时，我们直接用栈上的数组，否则使用 String。但是这个 N 不宜太大，否则当使用 String 时，会比目前的版本浪费内存。

当使用 enum 时，额外的 tag + 为了对齐而使用的 padding 会占用一些内存。因为 String 结构是 8 字节对齐的，我们的 enum 最小 8 + 24 = 32 个字节。

所以，可以设计一个数据结构，内部用1个字节表示字符串的长度，用 30 个字节表示字符串内容，再加上 1 个字节的 tag，正好也是 32 字节，可以和 String 放在一个 enum 里使用，我们暂且称这个 enum 叫 SmartString，它的结构如下图所示：

使用 std::sync::Mutex 可以多线程共享可变数据，Mutex、RwLock 和原子类型，即使声明为 non-mut，这些类型也可以修改：

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
28
29
30

use std::borrow::Cow;
use std::collections::HashMap;
use std::sync::{Arc, Mutex};
use std::thread;
use std::time::Duration;

fn main() {
    // 用 Arc 来提供并发环境下的共享所有权（使用引用计数）
    let metrics: Arc<Mutex<HashMap<Cow<'static, str>, usize>>> =
        Arc::new(Mutex::new(HashMap::new()));
    for _ in 0..32 {
        let m = metrics.clone();
        thread::spawn(move || {
            let mut g = m.lock().unwrap();

            // 此时只有拿到 MutexGuard 的线程可以访问 HashMap
            let data = &mut *g;

            // Cow 实现了很多数据结构的 From trait，
            // 所以我们可以用 "hello".into() 生成 Cow
            let value = data.entry("hello".into()).or_insert(0);
            *value += 1;

            // MutexGuard 被 Drop，锁被释放
        });
    }

    thread::sleep(Duration::from_millis(100));
    println!("metrics: {:?}", metrics.lock().unwrap());
}