Swift 字符串中的第一个唯一字符 - LeetCode

LeetCode.jpg

题目:字符串中的第一个唯一字符

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

案例:

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.
一、可以参照Swift 存在重复 - LeetCode中的哈希表解决方案,记录字符串出现的索引位置

1、将字符串转为数组 2、循环字符串数组,将字符作为键,索引作为值存入字典 3、存入字典时先判断是否已经存在,已存在则将值置位-1 4、循环字典,拿到所有的值 5、将值排序(因为都是整数),最小值即为所求的索引

class Solution {
    func firstUniqChar(_ s: String) -> Int {
        var charArr = [String]()
        for character in s { //将字符串转为数组
            charArr.append(String(character))
        }
        var dic = [String: Int]()
        for i in 0..<charArr.count {
            if let _ = dic[charArr[i]] { //当字典内已经存在该字符,此时直接将其置为-1
                dic[charArr[i]] = -1
            } else {
                dic[charArr[i]] = i //记录字符出现的索引位置
            }
        }
        var newArray = [Int]()
        //循环字典,拿到所有的值
        for (_, value) in dic {
            if value != -1 { //将所有补位-1的索引添加到新的数组中
                newArray.append(value)
            }
        }
        // 如果数组不为空,则取最小值,即第一次出现的索引,所以排序后取第一个值
        if newArray.count > 0 {
            return newArray.sorted().first!
        }
        return -1
    }
}

但是分析一下算法。。。循环很多,需要创建的辅助变量也很多,同时还要排序,但是个人以为最重要的原因可能是Character转换String耗时较多(ps:求大神解答),并且运行效率确实不高,在LeetCode中只战胜了20%的方案(执行用时1016ms)、、、、

二、使用Unicode标量参,考官方网String and Characters
我们可以使用String类型的unicodeScalars属性遍历一个Unicode标量编码的字符串。这个属性是 UnicodeScalarsView类型,UnicodeScalarsView是一个UnicodeScalar类型的集合。每一个Unicode标 量都是一个任意21位Unicode码位,没有高位代理,也没有低位代理。
每一个UnicodeScalar使用value属性,返回标量的21位值,每一位都是32位无符号整形(UInt32)的值:

参考官方例子:

let dogString = "Dog‼?"
for scalar in dogString.unicodeScalars {
    print("\(scalar.value) ", terminator: "")
}
print("")
// Prints "68 111 103 8252 128054 "

for scalar in dogString.unicodeScalars {
    print("\(scalar) ")
}
// D
// o
// g
// ‼
// ?

我们知道我们小写字母的ASCII码值A是从97开始的,所以: 1、先创建一个包含26个0作为值的数组 2、循环string的unicodeScalars获取其value 3、将value - 97 代表字符,记录该字符出现的次数 4、再次循环string,获取第一个出现次数为1的字符 代码如下:

 func firstUniqChar(_ s: String) -> Int {
        //创建一个含有26个为0的值的数组
        var array = Array<Int>(repeating: 0, count: 26)
        for character in s.unicodeScalars {
            let index = Int(character.value - 97)
            //记录字符出现的次数
            array[index] = array[index] + 1
        }
        //再次循环string,使用enumerated()获取到字符串的索引
        for (index, character) in s.unicodeScalars.enumerated() {
            let count = array[Int(character.value - 97)]
            if count == 1 {
                return index
            }
        }
        return -1
    }
可以看到运行结果如下:

执行用时:172ms

运行结果.png

用Swift开始学习算法中,在LeetCode中开始做初级算法这一章节,将做的题目在此做个笔记,希望有更好方法同学们cue我哦。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏互联网杂技

javascript大法好,不用记

数组的操作 ---- Array.prototype.toString ( ) 把数组转变为字符串,返回字符串,arr.toString(); ---- Arr...

37670
来自专栏Clive的技术分享

PHP常用array函数

函数名 函数作用 array_chunk 数组分割 array_column 获取数组的某一列 array_combine 两个数组分别...

39060
来自专栏PPV课数据科学社区

一文读懂如何用 Python 实现6种排序算法

原文链接:https://my.oschina.net/liuyuantao/blog/749329 总结了一下常见集中排序的算法 ? 归并排序 归并排序也称合...

38570
来自专栏浪淘沙

java初级笔记----API

一、类Object java.lang.Object 是类层次结构的根类,每个类都使用object作为超类。所有对象(包括数组)都实现这个类...

15740
来自专栏CDA数据分析师

一文读懂如何用 Python 实现6种排序算法

总结了一下常见集中排序的算法 ? 归并排序 归并排序也称合并排序,是分治法的典型应用。分治思想是将每个问题分解成个个小问题,将每个小问题解决,然后合并。 具体的...

227100
来自专栏待你如初见

Day11

for(元素的数据类型 变量名 : 数组名或者Collection集合对象名) {

11660
来自专栏编程坑太多

java-逆波兰算法

14330
来自专栏深度学习之tensorflow实战篇

hive字符串函数

hive字符串函数 1. 字符串长度函数:length 语法: length(string A) 返回值: int 说明:返回字符串A的长度 举例:hive> ...

94370
来自专栏咸鱼不闲

String的基本用法

24520
来自专栏学海无涯

8.数组

8320

扫码关注云+社区

领取腾讯云代金券