写点什么

2023-06-28:你想要用小写字母组成一个目标字符串 target。 开始的时候,序列由 target.length 个 ‘?‘ 记号组成 而你有一个小写字母印章 stamp。 在每个回合,你可

  • 2023-06-28
    北京
  • 本文字数:3824 字

    阅读完需:约 13 分钟

2023-06-28:你想要用小写字母组成一个目标字符串 target。


开始的时候,序列由 target.length 个 '?' 记号组成


而你有一个小写字母印章 stamp。


在每个回合,你可以将印章放在序列上,并将序列中的每个字母替换为印章上的相应字母


你最多可以进行 10 * target.length 个回合


举个例子,如果初始序列为 "?????",而你的印章 stamp 是 "abc"


那么在第一回合,你可以得到 "abc??"、"?abc?"、"??abc"


(请注意,印章必须完全包含在序列的边界内才能盖下去。)


如果可以印出序列,那么返回一个数组,该数组由每个回合中被印下的最左边字母的索引组成


如果不能印出序列,就返回一个空数组。


例如,如果序列是 "ababc",印章是 "abc"


那么我们就可以返回与操作 "?????" -> "abc??" -> "ababc" 相对应的答案 [0, 2]


另外,如果可以印出序列,那么需要保证可以在 10 * target.length 个回合内完成


任何超过此数字的答案将不被接受。


输入:stamp = "abc", target = "ababc"。


输出:[0,2]。


答案 2023-06-28:

大体步骤如下:

1.创建变量 s 和 t,分别存储印章 stamp 和目标字符串 target 的字节数组表示。


2.创建变量 m 和 n,分别存储印章长度和目标字符串长度。


3.创建数组 inDegrees,长度为 n-m+1,初始化每个元素为 m。该数组表示每个位置需要匹配的印章字符数量。


4.创建二维数组 graph,长度为 n,每个位置是一个空的整数数组。该数组表示目标字符串每个位置对应的可能的匹配位置。


5.创建队列 queue,长度为 n-m+1,用于存储已经匹配完所有印章字符的位置。


6.创建变量 l 和 r,分别表示队列 queue 的左右指针,初始时都为 0。


7.遍历目标字符串,从 0 到 n-m,依次处理每个位置:


7.1.在当前位置 i,遍历印章的每个字符:


7.1.1.若目标字符串 t 的第 i+j 个字符与印章字符相等,表示匹配成功,更新 inDegrees 数组,将对应位置的值减 1。


7.1.1.1.如果经过减 1 操作后,该位置上印章字符匹配数量变为 0,将该位置加入队列 queue,并将右指针 r 向右移动。


7.1.2. 若目标字符串 t 的第 i+j 个字符与印章字符不相等,表示匹配失败,将该位置加入 graph[i+j]数组中,表示可以在该位置之后的某个位置尝试匹配印章。


8.创建 bool 类型的数组 visited,长度为 n,用于标记目标字符串的位置是否被访问过。


9.创建数组 path,长度为 n-m+1,用于记录完成印章替换的顺序。


10.创建变量 size,初始为 0,表示已经完成替换的印章的数量。


11.当左指针 l 小于右指针 r 时,执行以下循环:


11.1.取出队列 queue 中的当前位置 cur,并将左指针 l 右移。


11.2.将当前位置 cur 加入数组 path 中,并增加 size 的值。


11.3.遍历印章的每个字符:


11.3.1.若当前位置 cur+i 未被访问过,表示可以尝试在该位置继续匹配印章:


11.3.1.1.将该位置标记为已访问 visited[cur+i] = true。


11.3.1.2.遍历当前位置 cur+i 对应的 graph 数组中的每个位置 next:


11.3.1.2.1.更新 inDegrees 数组,将对应位置的值减 1。


11.3.1.2.1.1.如果经过减 1 操作后,该位置上印章字符匹配数量变为 0,将该位置加入队列 queue,并将右指针 r 向右移动。


12.检查完成替换的印章数量是否等于 n-m+1,如果不相等,返回空数组[]。


13.将数组 path 中的元素按照首尾对称的顺序重新排列,即交换元素 path[i]和 path[j],其中 i 从 0 遍历到 size-1,j 从 size-1 遍历到 0。


14.返回数组 path 作为结果。


该程序的总时间复杂度和总空间复杂度为:


总时间复杂度:O((n - m + 1) * m),其中 n 是 target 字符串的长度,m 是 stamp 字符串的长度。


总空间复杂度:O(n),其中 n 是 target 字符串的长度。

go 完整代码如下:

package main
import ( "fmt")
func movesToStamp(stamp string, target string) []int { s := []byte(stamp) t := []byte(target) m := len(s) n := len(t) inDegrees := make([]int, n-m+1) for i := range inDegrees { inDegrees[i] = m } graph := make([][]int, n) for i := range graph { graph[i] = []int{} } queue := make([]int, n-m+1) l, r := 0, 0 for i := 0; i <= n-m; i++ { for j := 0; j < m; j++ { if t[i+j] == s[j] { if inDegrees[i]--; inDegrees[i] == 0 { queue[r] = i r++ } } else { graph[i+j] = append(graph[i+j], i) } } } visited := make([]bool, n) path := make([]int, n-m+1) size := 0 for l < r { cur := queue[l] l++ path[size] = cur size++ for i := 0; i < m; i++ { if !visited[cur+i] { visited[cur+i] = true for _, next := range graph[cur+i] { if inDegrees[next]--; inDegrees[next] == 0 { queue[r] = next r++ } } } } } if size != n-m+1 { return []int{} } for i, j := 0, size-1; i < j; i, j = i+1, j-1 { path[i], path[j] = path[j], path[i] } return path}
func main() { stamp := "abc" target := "ababc" result := movesToStamp(stamp, target) fmt.Println(result)}
复制代码


rust 完整代码如下:

fn moves_to_stamp(stamp: String, target: String) -> Vec<i32> {    let s: Vec<char> = stamp.chars().collect();    let t: Vec<char> = target.chars().collect();    let m = s.len();    let n = t.len();    let mut in_degrees: Vec<i32> = vec![m as i32; n - m + 1];    let mut graph: Vec<Vec<i32>> = vec![Vec::new(); n];    let mut queue: Vec<i32> = vec![0; n - m + 1];    let mut l = 0;    let mut r = 0;
for i in 0..=n - m { for j in 0..m { if t[i + j] == s[j] { if in_degrees[i] > 0 { in_degrees[i] -= 1; }
if in_degrees[i] == 0 { queue[r] = i as i32; r += 1; } } else { graph[i + j].push(i as i32); } } }
let mut visited: Vec<bool> = vec![false; n]; let mut path: Vec<i32> = vec![0; n - m + 1]; let mut size = 0;
while l < r { let cur = queue[l]; l += 1; path[size] = cur; size += 1;
for i in 0..m { let cur_i = cur + i as i32; if !visited[cur_i as usize] { visited[cur_i as usize] = true; for &next in &graph[cur_i as usize] { if in_degrees[next as usize] > 0 { in_degrees[next as usize] -= 1; }
if in_degrees[next as usize] == 0 { queue[r] = next; r += 1; } } } } }
if size != n - m + 1 { return Vec::new(); }
for i in 0..size / 2 { let tmp = path[i]; path[i] = path[size - 1 - i]; path[size - 1 - i] = tmp; }
path}
fn main() { let stamp = String::from("abc"); let target = String::from("ababc"); let result = moves_to_stamp(stamp, target); println!("{:?}", result);}
复制代码


c++完整代码如下:

#include <iostream>#include <vector>#include <algorithm>
using namespace std;
vector<int> movesToStamp(string stamp, string target) { int m = stamp.length(); int n = target.length(); vector<int> inDegrees(n - m + 1, m); vector<vector<int>> graph(n, vector<int>()); vector<int> queue(n - m + 1, 0); int l = 0, r = 0;
for (int i = 0; i <= n - m; i++) { for (int j = 0; j < m; j++) { if (target[i + j] == stamp[j]) { if (--inDegrees[i] == 0) { queue[r++] = i; } } else { graph[i + j].push_back(i); } } }
vector<bool> visited(n, false); vector<int> path(n - m + 1, 0); int size = 0;
while (l < r) { int cur = queue[l++]; path[size++] = cur;
for (int i = 0; i < m; i++) { if (!visited[cur + i]) { visited[cur + i] = true;
for (int next : graph[cur + i]) { if (--inDegrees[next] == 0) { queue[r++] = next; } } } } }
if (size != n - m + 1) { return vector<int>(); }
reverse(path.begin(), path.begin() + size); return path;}
int main() { string stamp = "abc"; string target = "ababc";
vector<int> result = movesToStamp(stamp, target);
cout << "Result: "; for (int num : result) { cout << num << " "; } cout << endl;
return 0;}
复制代码



发布于: 刚刚阅读数: 4
用户头像

公众号:福大大架构师每日一题 2021-02-15 加入

公众号:福大大架构师每日一题

评论

发布
暂无评论
2023-06-28:你想要用小写字母组成一个目标字符串 target。 开始的时候,序列由 target.length 个 ‘?‘ 记号组成 而你有一个小写字母印章 stamp。 在每个回合,你可_Go_福大大架构师每日一题_InfoQ写作社区