请选择 进入手机版 | 继续访问电脑版
楼主: z74646
1297 0

[其他] Swift 数组、字符串、集合与字典详解 [推广有奖]

  • 0关注
  • 1粉丝

本科生

75%

还不是VIP/贵宾

-

威望
0
论坛币
300 个
通用积分
0
学术水平
0 点
热心指数
1 点
信用等级
0 点
经验
890 点
帖子
55
精华
0
在线时间
12 小时
注册时间
2014-2-26
最后登录
2016-7-2

z74646 发表于 2016-6-14 23:42:39 |显示全部楼层 |坛友微信交流群

+2 论坛币
k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群
赵安豆老师微信:zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

感谢您参与论坛问题回答

经管之家送您两个论坛币!

+2 论坛币

今天我们来看几个最基本的数据结构:数组,字符串,集合和字典。

数组

数组是最基本的数据结构。Swift编程语言(http://www.maiziedu.com/course/16/)中改变了以前Objective-C时代NSMutableArray和NSArray分开的做法,统一到了Array唯一的数据结构。下面是最基本的一些实现。

[size=9.0000pt]1

[size=9.0000pt]2

[size=9.0000pt]3

[size=9.0000pt]4

[size=9.0000pt]5

[size=9.0000pt]6

[size=9.0000pt]7

[size=9.0000pt]8

[size=9.0000pt]9

10

11

// 声明一个不可修改的数组

let nums = [1, 2, 3]

let nums = [Int](count: 5, repeatedValue: 0)

// 声明一个可以修改的数组

var nums = [3, 1, 2]

// 增加一个元素

nums.append(4)

// 对原数组进行升序排序

nums.sortInPlace({$0 < $1})

// 将原数组除了最后一个以外的所有元素赋值给另一个数组

let anotherNums = Array(nums[0 ..< nums.count - 1])

不要小看这些简单的操作:数组可以依靠它们实现更多的数据结构。Swift虽然不像Java中有现成的队列和栈,但我们完全可以用数组配合最简单的操作实现这些数据结构,下面就是用数组实现栈的示例代码。

[size=9.0000pt]1

[size=9.0000pt]2

[size=9.0000pt]3

[size=9.0000pt]4

[size=9.0000pt]5

[size=9.0000pt]6

[size=9.0000pt]7

[size=9.0000pt]8

[size=9.0000pt]9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

// 用数组实现栈

class Stack {

  var stack: [AnyObject]

  init() {

    stack = [AnyObject]()

  }

  func push(object: AnyObject) {

    stack.append(object)

  }

  func pop() -> AnyObject? {

    if (!isEmpty()) {

      return stack.removeLast()

    } else {

      return nil

    }

  }

  func isEmpty() -> Bool {

    return stack.isEmpty

  }

  func peek() -> AnyObject? {

    return stack.last

  }

[size=9.0000pt]}

集合和字典

这两个数据结构经常使用的原因在于,查找数据的时间复杂度为O(1)。这两个在实战中经常与数组配合使用,请看下面这道题:

给一个整型数组和一个目标值,判断数组中是否有两个数字之和等于目标值

这道题是传说中经典的2Sum,我们已经有一个数组记为nums,也有一个目标值记为target,最后要返回一个Bool值。

最粗暴的方法就是每次选中一个数,然后遍历整个数组,判断是否有另一个数使两者之和为target。这种做法时间复杂度为O(n^2)。

采用集合可以优化时间复杂度。在遍历数组的过程中,用集合每次保存当前值。假如集合中已经有了目标值减去当前值,则证明在之前的遍历中一定有一个数与当前值之和等于目标值。这种做法时间复杂度为O(n),代码如下。

[size=9.0000pt]1

[size=9.0000pt]2

[size=9.0000pt]3

[size=9.0000pt]4

[size=9.0000pt]5

[size=9.0000pt]6

[size=9.0000pt]7

[size=9.0000pt]8

[size=9.0000pt]9

10

func twoSum(nums: [Int], _ target: Int) -> Bool {

  var set = Set<int>()

  for num in nums {

    if set.contains(target - num) {

      return true

    }

    set.insert(num)

  }

  return false

}</int>

如果把题目稍微修改下,变为

给定一个整型数组中有且仅有两个数字之和等于目标值,求两个数字在数组中的序号

思路与上题基本类似,但是为了方便拿到序列号,我们采用字典,时间复杂度依然是O(n)。代码如下。

[size=9.0000pt]1

[size=9.0000pt]2

[size=9.0000pt]3

[size=9.0000pt]4

[size=9.0000pt]5

[size=9.0000pt]6

[size=9.0000pt]7

[size=9.0000pt]8

[size=9.0000pt]9

10

11

12

13

14

func twoSum(nums: [Int], _ target: Int) -> [Int] {

  var res = [Int]()

  var dict = [Int: Int]()

  for i in 0 ..< nums.count {

    guard let lastIndex = dict[target - nums] else {

      dict[nums] = i

      continue

     }

     res.append(lastIndex)

     res.append(i)

     break

  }

  return res

[size=9.0000pt]}

[size=9.0000pt]

[size=9.0000pt]

字符串

字符串在算法实战中极其常见。首先还是列举一下字符串的通常用法。

[size=9.0000pt]1

[size=9.0000pt]2

[size=9.0000pt]3

[size=9.0000pt]4

[size=9.0000pt]5

[size=9.0000pt]6

[size=9.0000pt]7

[size=9.0000pt]8

[size=9.0000pt]9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

// 字符串和数字之间的转换

let str = "3"

let num = Int(str)

let number = 3

let string = String(num)

// 字符串长度

let len = str.characters.count

// 访问字符串中的单个字符,时间复杂度为O(n)

let char = str[str.startIndex.advancedBy(n)]

// 修改字符串

str.removeAtIndex(n)

str.append("c")

str += "hello world"

// 检测字符串是否是由数字构成

func isStrNum(str: String) -> Bool {

  return Int(str) != nil

[size=9.0000pt]}

// 将字符串按字母排序(不考虑大小写)

func sortStr(str: String) -> String {

  var chars = [Character](str.characters)

  chars.sortInPlace({$0 < $1})

  return String(chars)

[size=9.0000pt]}

下面是本篇的精华所在,我们来一起看一道以前的Google面试题。

Given an input string, reverse the string word by word.

A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

For example,

Given s = "the sky is blue",

return "blue is sky the".

Could you do it in-place without allocating extra space?

这道题目一看好简单,不就是翻转字符串的翻版吗?这种方法有以下两个问题

  每个单词长度不一样

  空格需要特殊处理

这样一来代码写起来会很繁琐而且容易出错。不如我们先实现一个字符串翻转的方法。

[size=9.0000pt]1

[size=9.0000pt]2

[size=9.0000pt]3

[size=9.0000pt]4

[size=9.0000pt]5

private func _swap(inout chars:[Character], _ p: Int, _ q: Int) {

  let temp = chars[p]

  chars[p] = chars[q]

  chars[q] = temp

}

有了这个方法,我们就可以实行下面两种字符串翻转:

整个字符串翻转,"the sky is blue" -> "eulb si yks eht"

每个单词作为一个字符串单独翻转,"eulb si yks eht" -> "blue is sky the"

整体思路有了,我们就可以解决这道问题了

[size=9.0000pt]1

[size=9.0000pt]2

[size=9.0000pt]3

[size=9.0000pt]4

[size=9.0000pt]5

[size=9.0000pt]6

[size=9.0000pt]7

[size=9.0000pt]8

[size=9.0000pt]9

10

11

12

13

14

15

16

17

18

19

20

21

func reverseWords(s: String) -> String {

  var chars = [Character](s.characters)

  _reverse(&chars, 0, chars.count - 1)

  var start = 0

  for i in 0 ..< chars.count {

    if i == chars.count - 1 || chars[i + 1] == " " {

      _reverse(&chars, start, i)

      start = i + 2

    }

  }

  return String(chars)

[size=9.0000pt]}

private func _reverse(inout chars: [Character], _ start: Int, _ end: Int) {

  var start = start

  var end = end

  while start < end {

    _swap(&chars, start, end)

    start += 1

    end -= 1

  }

[size=9.0000pt]}

时间复杂度还是O(n),整体思路和代码简单很多。

总结

Swift中数组、字符串、集合以及字典是最基本的数据结构,但是围绕这些数据结构的问题层出不穷。幸运的是解决方法也并不是千变万化、高深莫测,大家做好相应的积累即可。下期我们讲链表、栈、队列这三种数据结构。

二维码

扫码加我 拉你入群

请注明:姓名-公司-职位

以便审核进群资格,未注明则拒绝

关键词:SWIFT 字符串 Hello World Characters Character 编程语言 字符串 count

您需要登录后才可以回帖 登录 | 我要注册

本版微信群
加好友,备注cda
拉您进交流群

京ICP备16021002-2号 京B2-20170662号 京公网安备 11010802022788号 论坛法律顾问:王进律师 知识产权保护声明   免责及隐私声明

GMT+8, 2024-3-29 22:45