技术提高是一个循序渐进的过程,所以我讲的leetcode算法题从最简单的level开始写的,然后到中级难度,最后到hard难度全部完。
目前我选择C语言,python和Java作为实现语言,因为这三种语言还是比较典型的。由于篇幅和精力有限,其他语言的实现有兴趣的朋友请自己尝试。
初级难度说的差不多的时候,我打算再加点其他内容,我可能会从操作系统到协议栈,从分布式聊到大数据框架,从大数据聊到人工智能,... ...。
如果有任何问题可以在文章后评论或者私信给我。
我会持续分享下去,敬请您的关注。
LeetCode 387. 字符串中的第一个唯一字符 (First Unique Character in a String)
问题描述:给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。
注: 您可以假定该字符串只包含小写字母。
示例:C语言实现:
第一直觉是遍历整个字符串,统计每个字母出现的次数,再遍历,找出字符串中第一个出现一次的字母的下标。这种算法的复杂度是O(n),要执行两次for循环。
但是我想在一次循环中解决这个问题。 我发现其实可以用我们前面用过的一种方法,我们可以从字符串的左右两边同时查找26个字母中的每一个字母在字符串最左边和最右边的位置,这样有三种情况:
- 查找失败,说明字符串中没这个字母;
- 如果两次查找字母的位置都不同,说明这个字母在字符串中出现多次;
- 如果两次查找字母的位置都是同一个,那么就说明这个字母在字符串中就出现一次,就是我们要找的,那么只需要看它的下标是不是最小的即可;
代码如下:
我们用内置的函数strchr和strrchr来分别从左边和右边来查找每一个字母,函数返回一个指针,那么下标就是返回的指针与s的差。
python语言的实现:
python的实现和C实现基本一致。
代码如下:
Java语言的实现:
Java实现和C语言基本一致。
代码如下:
,