Swift 算法实战之路:数组,字符串,集合,与字典

分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友 微信微信
查看查看211 回复回复2 收藏收藏 分享淘帖 转播转播 分享分享 微信
查看: 211|回复: 2
收起左侧

Swift 算法实战之路:数组,字符串,集合,与字典

[复制链接]
大秘小蜜 发表于 2016-6-21 17:03:17 | 显示全部楼层 |阅读模式
快来登录
获取最新的苹果动态资讯
收藏热门的iOS等技术干货
拷贝下载Swift Demo源代码
本帖最后由 大秘小蜜 于 2016-6-21 17:24 编辑

上次讲解了基本的语法和一些Swift的小技巧。这期我们来看几个最基本的数据结构:数组,字符串,集合和字典。当然要想了解更多Swift知识点或面试题,可以多访问全球最大的Swift开发者社区——敏捷大拇指http://www.Swifthumb.com

Swift 算法实战之路:数组,字符串,集合,与字典

Swift 算法实战之路:数组,字符串,集合,与字典 - 敏捷大拇指 - Swift 算法实战之路:数组,字符串,集合,与字典





1、数组

数组是最基本的数据结构。Swift中改变了以前Objective-C时代NSMutableArray和NSArray分开的做法,统一到了Array唯一的数据结构。下面是最基本的一些实现。

[Swift] 纯文本查看 复制代码
// 声明一个不可修改的数组
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中有现成的队列和栈,但我们完全可以用数组配合最简单的操作实现这些数据结构,下面就是用数组实现栈的示例代码。

[Swift] 纯文本查看 复制代码
// 用数组实现栈
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
  }
}





2、集合和字典

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

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

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

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

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

[Swift] 纯文本查看 复制代码
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
}


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

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

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

[Swift] 纯文本查看 复制代码
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[ i ]] else {
      dict[nums[ i ] ] = i
      continue
     }

     res.append(lastIndex)
     res.append(i)
     break
  }

  return res
}





3、字符串

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

[Swift] 纯文本查看 复制代码
// 字符串和数字之间的转换
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
}

// 将字符串按字母排序(不考虑大小写)
func sortStr(str: String) -> String {
  var chars = [Character](str.characters)
  chars.sortInPlace({$0 < $1})
  return String(chars)
}


下面是本篇的精华所在,我们来一起看一道以前的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?

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

  • 每个单词长度不一样
  • 空格需要特殊处理


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

[Swift] 纯文本查看 复制代码
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"


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

[Swift] 纯文本查看 复制代码
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)
}

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
  }
}


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




4、总结

Swift中数组、字符串、集合以及字典是最基本的数据结构,但是围绕这些数据结构的问题层出不穷。幸运的是解决方法也并不是千变万化、高深莫测,大家做好相应的积累即可。下期我们讲链表,请多加关注Swift开发者社区 敏捷大拇指 Swifthumb.com




相关内容

Swift 算法实战之路:基本语法与技巧
Swift 算法实战之路:数组,字符串,集合,与字典
Swift 算法实战之路:链表
Swift 算法实战之路:栈和队列




作者:故胤道长

都看到这里了,就把这篇资料推荐给您的好朋友吧,让他们也感受一下。

回帖是一种美德,也是对楼主发帖的尊重和支持。

*声明:敏捷大拇指是全球最大的Swift开发者社区、苹果粉丝家园、智能移动门户,所载内容仅限于传递更多最新信息,并不意味赞同其观点或证实其描述;内容仅供参考,并非绝对正确的建议。本站不对上述信息的真实性、合法性、完整性做出保证;转载请注明来源并加上本站链接,敏捷大拇指将保留所有法律权益。如有疑问或建议,邮件至marketing@swifthumb.com

*联系:微信公众平台:“swifthumb” / 腾讯微博:@swifthumb / 新浪微博:@swifthumb / 官方QQ一群:343549891(满) / 官方QQ二群:245285613 ,需要报上用户名才会被同意进群,请先注册敏捷大拇指

嗯,不错!期待更多好内容,支持一把:
支持敏捷大拇指,用支付宝支付10.24元 支持敏捷大拇指,用微信支付10.24元

评分

参与人数 1金钱 +10 贡献 +10 专家分 +10 收起 理由
Anewczs + 10 + 10 + 10 32个赞!专家给力!

查看全部评分

移动 发表于 2016-6-29 17:48:56 | 显示全部楼层
不错,基础算法必定用到!
创客 发表于 2016-7-1 03:18:02 | 显示全部楼层
不错不错,系列呢!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

做任务,领红包。
我要发帖

分享扩散

都看到这里了,就把这资料推荐给您的好朋友吧,让他们也感受一下。
您的每一位朋友访问此永久链接后,您都将获得相应的金钱积分奖励
热门推荐

合作伙伴

Swift小苹果

  • 北京治世天下科技有限公司
  • ©2014-2016 敏捷大拇指
  • 京ICP备14029482号
  • Powered by Discuz! X3.1 Licensed
  • swifthumb Wechat Code
  •   
快速回复 返回顶部 返回列表