乐趣区

关于golang:golangleetcode初级最长公共前缀删除链表中的节点

第一题 最长公共前缀

题目信息

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 “”。

 

示例 1:

输出:strs = [“flower”,”flow”,”flight”]
输入:”fl”
示例 2:

输出:strs = [“dog”,”racecar”,”car”]
输入:””
解释:输出不存在公共前缀。
 

提醒:

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

解题思路

按程序对字符串切片进行一次遍历,对每个字符串的首个字符进行查找
若字符都雷同,则将该字符退出返回的字符串变量,并查找下一字符
若字符不同,则间接返回

代码

func getch(str string,n int)rune{
    for i, r := range str {
        if i==n{return r}
    }
    return 0
}
func longestCommonPrefix(strs []string) string {
    var res string
    var n int
    var c rune
    for {c=getch(strs[0],n)
        for _, str := range strs {if getch(str,n)==0{return res}
            if getch(str,n)!=c{return res}
        }
        res=res+string(c)
        n++
    }
}

复杂度剖析


工夫复杂度:O(len(res)*len(strs))返回的字符串长度每加一,就要多做一边循环;每做一遍循环,就要遍历一次字符串切片的所有字符串;
空间复杂度:O(1)常数级空间

官网解析

https://leetcode-cn.com/probl…
因为本题难度较低,官网四种答案的执行工夫和内存耗费并没有多少显著的差异,在此不做深刻探讨

第二题 删除链表中的节点

题目信息

请编写一个函数,用于 删除单链表中某个特定节点。在设计函数时须要留神,你无法访问链表的头节点 head,只能间接拜访 要被删除的节点。

题目数据保障须要删除的节点 不是开端节点。



解题思路

题目的要求为
传入的参数即为指向待删除的节点,且因为是单链表,无奈向前拜访
题目保障了删除的节点不是开端节点,提醒了咱们该节点必然领有 next 节点

代码


func deleteNode(node *ListNode) {
    node.Val = node.Next.Val
    node.Next = node.Next.Next
}

复杂度剖析

工夫复杂度:O(1)。

空间复杂度:O(1)。

退出移动版