Swift 数数并说 - LeetCode

LeetCode.jpg

题目:数数并说

描述:报数序列是指一个整数序列,按照其中的整数的顺序进行报数,得到下一个数。其前五项如下:
1.     1
2.     11
3.     21
4.     1211
5.     111221

1 被读作 "one 1" ("一个一") , 即 11。 11 被读作 "two 1s" ("两个一"), 即 21。 21 被读作 "one 2", "one 1" ("一个二" , "一个一") , 即 1211。 给定一个正整数 n ,输出报数序列的第 n 项。

注意:整数顺序将表示为一个字符串。

案例1:

输入: 1
输出: "1"

案例2:

输入: 4
输出: "1211"
方案一:使用字符串获取子串比较

外层循环正整数n,内层循环获取到的字符串,比较前一位和后一位,相同则增加count,然后再拼接字符串

代码一:
func countAndSay(_ n: Int) -> String {
    var say = "1"
    for _ in 1..<n {
        var cnt = 1
        var tempSay = ""
        for j in 0..<say.count {
            if (say.substingInRange(j..<j+1) == say.substingInRange(j+1..<j+2)) {
                cnt += 1
            } else {
                tempSay += String(cnt) + String(say.substingInRange(j..<j+1)!)
                cnt = 1
            }
        }
        say = tempSay
    }
    return say
}

extension String {
    //获取子字符串
    func substingInRange(_ r: Range<Int>) -> String? {
        if r.lowerBound < 0 || r.upperBound > self.count {
            return nil
        }
        let startIndex = self.index(self.startIndex, offsetBy:r.lowerBound)
        let endIndex   = self.index(self.startIndex, offsetBy:r.upperBound)
        return String(self[startIndex..<endIndex])
    }
}

Swift中取范围内字符子串参考:Swift4 获取String子字符串这里直接把代码拷过来了

执行用时不截图了:1276ms、、、
方案二:将字符串转成数组,使用下标比较

思想和方法一是一致的,但明显取下标方便,然后数组效率比字符串要高 代码二:

func countAndSay(_ n: Int) -> String {
    var say = "1"
    if n == 1 {
        return say
    }
    for _ in 1..<n {
        var tempSay = ""
        var cnt = 1
        var chars = Array(say)
        for j in 0..<say.count {
            //条件太长还是括起来比较好
            if (j + 1 < chars.count && chars[j] == chars[j + 1]) {
                cnt += 1
            } else {
                tempSay.append("\(cnt)")
                tempSay.append(chars[j])
                cnt = 1
            }
        }
        say = tempSay
    }
    return say
}
执行用时:32ms,比方案一提高了太多
方案三:也不算什么方案、、、看了提交记录的第一名,对上方方案二优化了一下、、

就减少了一次循环、、、

代码三:
func countAndSay2(_ n: Int) -> String {
    var say = "1"
    if n == 1 {
        return say
    }
    for _ in 1..<n {
        var tempSay = ""
        var cnt = 1
        var chars = Array(say)
        var current = chars[0]
        for j in 1..<say.count {
            if chars[j] == current {
                cnt += 1
            } else {
                tempSay.append("\(cnt)")
                tempSay.append(current)
                cnt = 1
                current = chars[j]
            }
        }
        tempSay.append("\(cnt)")
        tempSay.append(current)
        say = tempSay
    }
    return say
}

结果又快了那么一点点、、、没啥影响、、

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏黑泽君的专栏

java基础学习_基础语法(上)01_day02总结

=============================================================================

1193
来自专栏C#

DotNet常用排序算法总结

    数据结构和算法对一个程序来说是至关重要的,现在介绍一下几种算法,在项目中较为常用的算法有:冒泡排序,简单选择排序,直接插入排序,希尔排序,堆排序,...

1929
来自专栏和蔼的张星的图像处理专栏

420. 报数看懂题意

这个题主要在看懂题意,程序写起来稍有麻烦。首先把当n等于1的string写出来,这是一个种子,然后根据这个种子来来生成新的。具体的一些细节就不写了,主要是一个计...

921
来自专栏xx_Cc的学习总结专栏

iOS-正则表达式的简单使用

4437
来自专栏desperate633

LintCode 比较字符串题目分析代码

比较两个字符串A和B,确定A中是否包含B中所有的字符。字符串A和B中的字符都是 大写字母

591
来自专栏ACM算法日常

leetcode 38 | 报数(简单题)

报数序列是指一个整照其中的整数的顺序进数序列,按行报数,得到下一个数。其前五项如下:

3252
来自专栏攻城狮的动态

简谈归并排序

3836
来自专栏赵俊的Java专栏

报数

2045
来自专栏函数式编程语言及工具

Scalaz(18)- Monad: ReaderWriterState-可以是一种简单的编程语言

  说道FP,我们马上会联想到Monad。我们说过Monad的代表函数flatMap可以把两个运算F[A],F[B]连续起来,这样就可以从程序的意义上形成一种串...

2027
来自专栏Java进阶之路

Java8 Optional 的正确使用方式

1940

扫码关注云+社区

领取腾讯云代金券