leetcode算法题(LeetCode基础算法题第99篇)(1)

技术提高是一个循序渐进的过程,所以我讲的leetcode算法题从最简单的level开始写的,然后到中级难度,最后到hard难度全部完。

目前我选择C语言,python和Java作为实现语言,因为这三种语言还是比较典型的。由于篇幅和精力有限,其他语言的实现有兴趣的朋友请自己尝试。

初级难度说的差不多的时候,我打算再加点其他内容,我可能会从操作系统到协议栈,从分布式聊到大数据框架,从大数据聊到人工智能,... ...。

如果有任何问题可以在文章后评论或者私信给我

我会持续分享下去,敬请您的关注。

LeetCode 387. 字符串中的第一个唯一字符 (First Unique Character in a String)

问题描述:

给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。

注: 您可以假定该字符串只包含小写字母。

示例:

leetcode算法题(LeetCode基础算法题第99篇)(2)

C语言实现:

第一直觉是遍历整个字符串,统计每个字母出现的次数,再遍历,找出字符串中第一个出现一次的字母的下标。这种算法的复杂度是O(n),要执行两次for循环。

但是我想在一次循环中解决这个问题。 我发现其实可以用我们前面用过的一种方法,我们可以从字符串的左右两边同时查找26个字母中的每一个字母在字符串最左边和最右边的位置,这样有三种情况:

  1. 查找失败,说明字符串中没这个字母;
  2. 如果两次查找字母的位置都不同,说明这个字母在字符串中出现多次;
  3. 如果两次查找字母的位置都是同一个,那么就说明这个字母在字符串中就出现一次,就是我们要找的,那么只需要看它的下标是不是最小的即可;

代码如下:

leetcode算法题(LeetCode基础算法题第99篇)(3)

我们用内置的函数strchr和strrchr来分别从左边和右边来查找每一个字母,函数返回一个指针,那么下标就是返回的指针与s的差。

leetcode算法题(LeetCode基础算法题第99篇)(4)

python语言的实现:

python的实现和C实现基本一致。

代码如下:

leetcode算法题(LeetCode基础算法题第99篇)(5)

leetcode算法题(LeetCode基础算法题第99篇)(6)

Java语言的实现:

Java实现和C语言基本一致。

代码如下:

leetcode算法题(LeetCode基础算法题第99篇)(7)

leetcode算法题(LeetCode基础算法题第99篇)(8)

,