1768. 交替合并字符串:双指针

简介: 这是 力扣上的 1768. 交替合并字符串,难度为 简单。

题目描述

这是 力扣上的 1768. 交替合并字符串,难度为 简单

image.png

题目分析

题目的要求比较明确,通过我们查看给出的示例也能很清晰的认识到题目是需要从 word1 和 word2 中挨个拼接起来,最终得到一个拼接的结果

另外,给出的 word1 和 word2 并不一定是一样长的,若其中一个字符串中的字母使用完了,那么直接将另外一个字符串剩下的内容追加到结果串中即可

思考:

对于做算法新手来说,这个题是可以很好的应用到双指针的思想,并且可以落地到实践中

简单来说,这个题可以简单的遍历数组挨个拼接即可,但此处我们可以重点介绍一下什么叫做双指针:

双指针,见名知意,就是在我们实现算法的时候使用了两个指针,从这里也可以引申到三指针等等,此处指的指针,不一定在算法中真的是去使用指针来实现,也是使用的逻辑上的指针

一般咱们使用双指针,可能会用到序列,数组,链表上,这些数据结构咱们的双指针的展现形式可能是具体数据的索引位置,也可能是节点的地址

对于实现二叉树,多叉树的题目,或者是图类型的题目,那么这个双指针体现的方式就是指向对应的节点了,这里列一下可能会用到的场景:

  • 一般那种追赶类型的题目,慢指针追赶快指针,成环类型的题目会用到
  • 对于需要用滑动窗口,需要动态控制区间的题目可以使用到
  • 当然,对于今天的字符串合并类型的题目可以用到,属于标记位置
  • 还有很多,欢迎补充...


那么对于今天的题,简单逻辑如下:

  • 定义 2 个变量i,j i, ji,j 用于分别遍历 word1和word2word1 和 word2word1word2,并记录 word1word1word1 的字符长度为n nnword2 word2word2 的为m mm
  • 使用循环控制,进入循环的条件是$$ i
  • 当能够进入循环的时候,说明此时 word1word1word1word2word2word2都没有遍历完毕,因此我们可以先追加 word1word1 word1对应的字符,再追加 word2word2 word2对应的字符
  • 若从循环中退出,那么说明 word1word1word1word2word2word2 其中一个必然是遍历完毕,我们通过 i,j,n,mi ,j ,n,m ijnm的关系即可知道
  • 最后将较长的一方的剩余字符串怼到结果上就行了

接下来,咱们就可以来实现编码了,咱们这次使用 golang 的方式来进行实现

Golang 的实现方式:

func mergeAlternately(word1, word2 string) string {
    // 定义双指针
    i,j := 0,0
    n,m := len(word1),len(word2)
    res := make([]byte, 0, n+m)
    // 遍历 word1 和 Word2 ,直到其中一个遍历完毕
    for i<n && j<m {
        res = append(res, word1[i], word2[j])
        i++
        j++
    }
    if i == n{
        res = append(res, word2[j:]...)
    }else{
        res = append(res, word1[i:]...) 
    }
    return string(res)
}

这种实现方式,咱们的时间复杂度为 O(n+m),咱们遍历了 word1 + word2,空间复杂度是 O(n+m),我们开辟了 res 结果字符串占用空间消耗

今天就到这里,若有偏差,还请斧正

欢迎点赞,关注,收藏

朋友们,你的支持和鼓励,是我坚持分享,提高质量的动力

image.png

好了,本次就到这里

技术是开放的,我们的心态,更应是开放的。拥抱变化,向阳而生,努力向前行。

我是阿兵云原生,欢迎点赞关注收藏,下次见~

相关文章
C4.
|
6月前
|
存储 程序员 C语言
C语言中如何通过指针引用字符串
C语言中如何通过指针引用字符串
C4.
64 0
|
6月前
【每日一题Day301】LC2337移动片段得到字符串 | 双指针 计分
【每日一题Day301】LC2337移动片段得到字符串 | 双指针 计分
47 0
|
6月前
【每日一题Day150】LC1616分割两个字符串得到回文串 | 双指针+贪心
【每日一题Day150】LC1616分割两个字符串得到回文串 | 双指针+贪心
37 0
|
6月前
【每日一题Day117】LC1234替换子串得到平衡字符串 | 双指针
【每日一题Day117】LC1234替换子串得到平衡字符串 | 双指针
44 0
|
6月前
|
算法 C语言
通过指针引用字符串
通过指针引用字符串
59 1
|
2月前
|
存储 人工智能 C语言
C语言程序设计核心详解 第八章 指针超详细讲解_指针变量_二维数组指针_指向字符串指针
本文详细讲解了C语言中的指针,包括指针变量的定义与引用、指向数组及字符串的指针变量等。首先介绍了指针变量的基本概念和定义格式,随后通过多个示例展示了如何使用指针变量来操作普通变量、数组和字符串。文章还深入探讨了指向函数的指针变量以及指针数组的概念,并解释了空指针的意义和使用场景。通过丰富的代码示例和图形化展示,帮助读者更好地理解和掌握C语言中的指针知识。
|
6月前
|
存储 C++
C++程序中的字符串与指针
C++程序中的字符串与指针
51 2
|
6月前
|
C语言
C语言指针与字符串
C语言指针与字符串
34 0
|
C语言
C语言之字符串的连接使用指针和调用函数两种方法
C语言之字符串的连接使用指针和调用函数两种方法
251 0
|
6月前
|
安全 C语言
指针与字符串:C语言中的深入探索
指针与字符串:C语言中的深入探索
102 0