Movatterモバイル変換


[0]ホーム

URL:


小n快乐成长🍉

发表于||阅读次数

Interviews

软件工程技术面试个人指南。

Maintainer -Kevin Naughton Jr.

其他语言版本

目录

在线练习

在线面试编程

数据结构

Linked List

  • 链表即是由节点(Node)组成的线性集合,每个节点可以利用指针指向其他节点。它是一种包含了多个节点的、能够用于表示序列的数据结构。
  • 单向链表: 链表中的节点仅指向下一个节点,并且最后一个节点指向空。
  • 双向链表: 其中每个节点具有两个指针 p、n,使得 p 指向先前节点并且 n 指向下一个节点;最后一个节点的 n 指针指向 null。
  • 循环链表:每个节点指向下一个节点并且最后一个节点指向第一个节点的链表。
  • 时间复杂度:
    • 索引:O(n)
    • 搜索:O(n)
    • 插入:O(1)
    • 移除:O(1)

Stack

  • 栈是元素的集合,其包含了两个基本操作:push 操作可以用于将元素压入栈,pop 操作可以将栈顶元素移除。
  • 遵循后入先出(LIFO)原则。
  • 时间复杂度:
    • 索引:O(n)
    • 搜索:O(n)
    • 插入:O(1)
    • 移除:O(1)

Queue

  • 队列是元素的集合,其包含了两个基本操作:enqueue 操作可以用于将元素插入到队列中,而 dequeue 操作则是将元素从队列中移除。
  • 遵循先入先出原则 (FIFO)。
  • 时间复杂度:
    • 索引:O(n)
    • 搜索:O(n)
    • 插入:O(1)
    • 移除:O(1)

Tree

  • 树是无向、连通的无环图。

Binary Tree

  • 二叉树即是每个节点最多包含左子节点与右子节点这两个节点的树形数据结构。
  • 满二叉树: 树中的每个节点仅包含 0 或 2 个节点。
  • 完美二叉树(Perfect Binary Tree): 二叉树中的每个叶节点都拥有两个子节点,并且具有相同的高度。
  • 完全二叉树: 除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。

Binary Search Tree

  • 二叉搜索树(BST)是一种特殊的二叉树,其任何节点中的值都会大于或者等于其左子树中存储的值并且小于或者等于其右子树中存储的值。
  • 时间复杂度:
    • 索引:O(log(n))
    • 搜索:O(log(n))
    • 插入:O(log(n))
    • 删除:O(log(n))

Binary Search Tree

Trie

  • 字典树,又称基数树或者前缀树,能够用于存储键为字符串的动态集合或者关联数组的搜索树。树中的节点并没有直接存储关联键值,而是该节点在树中的挂载位置决定了其关联键值。某个节点的所有子节点都拥有相同的前缀,整棵树的根节点则是空字符串。

Alt text

Fenwick Tree

  • 树状数组又称 Binary Indexed Tree,其表现形式为树,不过本质上是以数组实现。数组中的下标代表着树中的顶点,每个顶点的父节点或者子节点的下标能够通过位运算获得。数组中的每个元素包含了预计算的区间值之和,在整棵树更新的过程中同样会更新这些预计算的值。
  • 时间复杂度:
    • 区间求值:O(log(n))
    • 更新:O(log(n))

Alt text

Segment Tree

  • 线段树是用于存放间隔或者线段的树形数据结构,它允许快速的查找某一个节点在若干条线段中出现的次数.
  • 时间复杂度:
    • 区间查询:O(log(n))
    • 更新:O(log(n))

Alt text

Heap

  • 堆是一种特殊的基于树的满足某些特性的数据结构,整个堆中的所有父子节点的键值都会满足相同的排序条件。堆更准确地可以分为最大堆与最小堆,在最大堆中,父节点的键值永远大于或者等于子节点的值,并且整个堆中的最大值存储于根节点;而最小堆中,父节点的键值永远小于或者等于其子节点的键值,并且整个堆中的最小值存储于根节点。
  • 时间复杂度:
    • 访问最大值 / 最小值:O(1)
    • 插入:O(log(n))
    • 移除最大值 / 最小值:O(log(n))

Max Heap

Hashing

  • 哈希能够将任意长度的数据映射到固定长度的数据。哈希函数返回的即是哈希值,如果两个不同的键得到相同的哈希值,即将这种现象称为碰撞。
  • Hash Map: Hash Map 是一种能够建立起键与值之间关系的数据结构,Hash Map 能够使用哈希函数将键转化为桶或者槽中的下标,从而优化对于目标值的搜索速度。
  • 碰撞解决
    • 链地址法(Separate Chaining): 链地址法中,每个桶是相互独立的,包含了一系列索引的列表。搜索操作的时间复杂度即是搜索桶的时间(固定时间)与遍历列表的时间之和。
    • 开地址法(Open Addressing): 在开地址法中,当插入新值时,会判断该值对应的哈希桶是否存在,如果存在则根据某种算法依次选择下一个可能的位置,直到找到一个尚未被占用的地址。所谓开地址法也是指某个元素的位置并不永远由其哈希值决定。

Alt text

Graph

  • 图是一种数据元素间为多对多关系的数据结构,加上一组基本操作构成的抽象数据类型。
    • 无向图(Undirected Graph): 无向图具有对称的邻接矩阵,因此如果存在某条从节点 u 到节点 v 的边,反之从 v 到 u 的边也存在。
    • 有向图(Directed Graph): 有向图的邻接矩阵是非对称的,即如果存在从 u 到 v 的边并不意味着一定存在从 v 到 u 的边。

Graph

算法

排序

快速排序

  • 稳定: 否
  • 时间复杂度:
    • 最优时间:O(nlog(n))
    • 最坏时间:O(n^2)
    • 平均时间:O(nlog(n))

Alt text

归并排序

  • 归并排序是典型的分治算法,它不断地将某个数组分为两个部分,分别对左子数组与右子数组进行排序,然后将两个数组合并为新的有序数组。
  • 稳定: 是
  • 时间复杂度:
    • 最优时间:O(nlog(n))
    • 最坏时间:O(nlog(n))
    • 平均时间:O(nlog(n))

Alt text

桶排序

  • 桶排序将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。
  • 时间复杂度:
    • 最优时间:Ω(n + k)
    • 最坏时间:O(n^2)
    • 平均时间:Θ(n + k)

Alt text

基数排序

  • 基数排序类似于桶排序,将数组分割到有限数目的桶中;不过其在分割之后并没有让每个桶单独地进行排序,而是直接进行了合并操作。
  • 时间复杂度:
    • 最优时间:Ω(nk)
    • 最坏时间:O(nk)
    • 平均时间:Θ(nk)

图算法

深度优先搜索

  • 深度优先算法是一种优先遍历子节点而不是回溯的算法。
  • 时间复杂度:O(|V| + |E|)

Alt text

广度优先搜索

  • 广度优先搜索是优先遍历邻居节点而不是子节点的图遍历算法。
  • 时间复杂度:O(|V| + |E|)

Alt text

拓扑排序

  • 拓扑排序是对于有向图节点的线性排序,如果存在某条从 u 到 v 的边,则认为 u 的下标先于 v。
  • 时间复杂度:O(|V| + |E|)

Dijkstra 算法

  • Dijkstra 算法 用于计算有向图中单源最短路径问题。
  • 时间复杂度:O(|V|^2)

Alt text

Bellman-Ford 算法

  • Bellman-Ford 算法是在带权图中计算从单一源点出发到其他节点的最短路径的算法。
  • 尽管算法复杂度大于 Dijkstra 算法,但是它适用于包含了负值边的图。
  • 时间复杂度:
    • 最优时间:O(|E|)
    • 最坏时间:O(|V||E|)

Alt text

Floyd-Warshall 算法

  • Floyd-Warshall 算法 能够用于在无环带权图中寻找任意节点的最短路径。
  • 时间复杂度:
    • 最优时间:O(|V|^3)
    • 最坏时间:O(|V|^3)
    • 平均时间:O(|V|^3)

Prim 算法

  • Prim 算法是用于在带权无向图中计算最小生成树的贪婪算法。换言之,Prim 算法能够在图中抽取出连接所有节点的边的最小代价子集。
  • 时间复杂度:O(|V|^2)

Alt text

Kruskal 算法

  • Kruskal 算法同样是计算图的最小生成树的算法,与 Prim 的区别在于并不需要图是连通的。
  • 时间复杂度:O(|E|log|V|)

Alt text

位运算

  • 位运算即是在位级别进行操作的技术,合适的位运算能够帮助我们得到更快地运算速度与更小的内存使用。
  • 测试第 k 位:s & (1 << k)
  • 设置第 k 位:s |= (1 << k)
  • 第 k 位置零:s &= ~(1 << k)
  • 切换第 k 位值:s ^= ~(1 << k)
  • 乘以 2:s << n
  • 除以 2:s >> n
  • 交集:s & t
  • 并集:s | t
  • 减法:s & ~t
  • 交换x = x ^ y ^ (y = x)
  • 取出最小非 0 位(Extract lowest set bit):s & (-s)
  • 取出最小 0 位(Extract lowest unset bit):~s & (s + 1)
  • 交换值:
    1
    2
    3
    x ^= y;
    y ^= x;
    x ^= y;

算法复杂度分析

大 O 表示

  • 大 O 表示 用于表示某个算法的上限,往往用于描述最坏的情况。

Alt text

小 O 表示

  • 小 O 表示用于描述某个算法的渐进上界,不过二者要更为紧密。

大 Ω 表示

  • 大 Ω 表示用于描述某个算法的渐进下界。

Alt text

小 ω 表示

  • Little Omega Notation用于描述某个特定算法的下界,不过不一定很靠近。

Theta Θ 表示

  • Theta Notation用于描述某个确定算法的确界。

Alt text

视频教程

面试书籍

  • Competitive Programming 3 - Steven Halim & Felix Halim
  • Cracking The Coding Interview - Gayle Laakmann McDowell
  • Cracking The PM Interview - Gayle Laakmann McDowell & Jackie Bavaro

计算机科学与技术资讯

文件结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
.
├── Array
│   ├── bestTimeToBuyAndSellStock.java
│   ├── findTheCelebrity.java
│   ├── gameOfLife.java
│   ├── increasingTripletSubsequence.java
│   ├── insertInterval.java
│   ├── longestConsecutiveSequence.java
│   ├── maximumProductSubarray.java
│   ├── maximumSubarray.java
│   ├── mergeIntervals.java
│   ├── missingRanges.java
│   ├── productOfArrayExceptSelf.java
│   ├── rotateImage.java
│   ├── searchInRotatedSortedArray.java
│   ├── spiralMatrixII.java
│   ├── subsetsII.java
│   ├── subsets.java
│   ├── summaryRanges.java
│   ├── wiggleSort.java
│   └── wordSearch.java
├── Backtracking
│   ├── androidUnlockPatterns.java
│   ├── generalizedAbbreviation.java
│   └── letterCombinationsOfAPhoneNumber.java
├── BinarySearch
│   ├── closestBinarySearchTreeValue.java
│   ├── firstBadVersion.java
│   ├── guessNumberHigherOrLower.java
│   ├── pow(x,n).java
│   └── sqrt(x).java
├── BitManipulation
│   ├── binaryWatch.java
│   ├── countingBits.java
│   ├── hammingDistance.java
│   ├── maximumProductOfWordLengths.java
│   ├── numberOf1Bits.java
│   ├── sumOfTwoIntegers.java
│   └── utf-8Validation.java
├── BreadthFirstSearch
│   ├── binaryTreeLevelOrderTraversal.java
│   ├── cloneGraph.java
│   ├── pacificAtlanticWaterFlow.java
│   ├── removeInvalidParentheses.java
│   ├── shortestDistanceFromAllBuildings.java
│   ├── symmetricTree.java
│   └── wallsAndGates.java
├── DepthFirstSearch
│   ├── balancedBinaryTree.java
│   ├── battleshipsInABoard.java
│   ├── convertSortedArrayToBinarySearchTree.java
│   ├── maximumDepthOfABinaryTree.java
│   ├── numberOfIslands.java
│   ├── populatingNextRightPointersInEachNode.java
│   └── sameTree.java
├── Design
│   └── zigzagIterator.java
├── DivideAndConquer
│   ├── expressionAddOperators.java
│   └── kthLargestElementInAnArray.java
├── DynamicProgramming
│   ├── bombEnemy.java
│   ├── climbingStairs.java
│   ├── combinationSumIV.java
│   ├── countingBits.java
│   ├── editDistance.java
│   ├── houseRobber.java
│   ├── paintFence.java
│   ├── paintHouseII.java
│   ├── regularExpressionMatching.java
│   ├── sentenceScreenFitting.java
│   ├── uniqueBinarySearchTrees.java
│   └── wordBreak.java
├── HashTable
│   ├── binaryTreeVerticalOrderTraversal.java
│   ├── findTheDifference.java
│   ├── groupAnagrams.java
│   ├── groupShiftedStrings.java
│   ├── islandPerimeter.java
│   ├── loggerRateLimiter.java
│   ├── maximumSizeSubarraySumEqualsK.java
│   ├── minimumWindowSubstring.java
│   ├── sparseMatrixMultiplication.java
│   ├── strobogrammaticNumber.java
│   ├── twoSum.java
│   └── uniqueWordAbbreviation.java
├── LinkedList
│   ├── addTwoNumbers.java
│   ├── deleteNodeInALinkedList.java
│   ├── mergeKSortedLists.java
│   ├── palindromeLinkedList.java
│   ├── plusOneLinkedList.java
│   ├── README.md
│   └── reverseLinkedList.java
├── Queue
│   └── movingAverageFromDataStream.java
├── README.md
├── Sort
│   ├── meetingRoomsII.java
│   └── meetingRooms.java
├── Stack
│   ├── binarySearchTreeIterator.java
│   ├── decodeString.java
│   ├── flattenNestedListIterator.java
│   └── trappingRainWater.java
├── String
│   ├── addBinary.java
│   ├── countAndSay.java
│   ├── decodeWays.java
│   ├── editDistance.java
│   ├── integerToEnglishWords.java
│   ├── longestPalindrome.java
│   ├── longestSubstringWithAtMostKDistinctCharacters.java
│   ├── minimumWindowSubstring.java
│   ├── multiplyString.java
│   ├── oneEditDistance.java
│   ├── palindromePermutation.java
│   ├── README.md
│   ├── reverseVowelsOfAString.java
│   ├── romanToInteger.java
│   ├── validPalindrome.java
│   └── validParentheses.java
├── Tree
│   ├── binaryTreeMaximumPathSum.java
│   ├── binaryTreePaths.java
│   ├── inorderSuccessorInBST.java
│   ├── invertBinaryTree.java
│   ├── lowestCommonAncestorOfABinaryTree.java
│   ├── sumOfLeftLeaves.java
│   └── validateBinarySearchTree.java
├── Trie
│   ├── addAndSearchWordDataStructureDesign.java
│   ├── implementTrie.java
│   └── wordSquares.java
└── TwoPointers
├── 3Sum.java
├── 3SumSmaller.java
├── mergeSortedArray.java
├── minimumSizeSubarraySum.java
├── moveZeros.java
├── removeDuplicatesFromSortedArray.java
├── reverseString.java
└── sortColors.java
18 directories, 124 files

发表于|分类于||阅读次数

类型转换可以判断实例的类型,也可以将该实例在其所在的类层次中视为其父类或子类的实例

Swift 中类型转换的实现为isas 操作符。这两个操作符使用了一种简单传神的方式来检查一个值的类型或将某个值转换为另一种类型。

为类型转换定义类层次

你可以在类及其子类层次中使用类型转换来判断特定类实例的类型并且在同一类层次中将该实例类型转换为另一个类。下面的三段代码定义了一个类层次以及一个包含了这些类实例的数组,作为类型转换的例子。

第一个代码片段定义了一个叫做MediaItem 的新基类。这个类为出现在数字媒体库中的所有成员提供了基本的功能。它声明了一个String 类型的name 和一个叫做initname 初始化器。(这里假设所有的媒体项目,包括所有电影和音乐,都有一个名字。)

1
2
3
4
5
6
classMediaItem{
var name:String
init(name:String) {
self.name = name
}
}

下一个片段定义了两个MediaItem 的子类。第一个子类,Movie ,封装了额外的电影的信息。他在MediaItem 的基础上添加了名为director 的属性及其初始化器。第二个子类,Song ,增加了名为artist 的属性及其初始化器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classMovie:MediaItem{
var director:String
init(name:String, director:String) {
self.director = director
super.init(name: name)
}
}
classSong:MediaItem{
var artist:String
init(name:String, artist:String) {
self.artist = artist
super.init(name: name)
}
}

最后一个代码段创建了名为library 的常量数组,它包含了两个Movie 实例和三个Song 实例。library 数组的类型是在初始化时根据常量字面量推断出来的。Swift的类型检查器能够推断MovieSong有一个共同的父类MediaItem因此library 的类型推断为[MediaItem]

1
2
3
4
5
6
7
8
let library = [
Movie(name:"Casablanca", director:"Michael Curtiz"),
Song(name:"Blue Suede Shoes", artist:"Elvis Presley"),
Movie(name:"Citizen Kane", director:"Orson Welles"),
Song(name:"The One And Only", artist:"Chesney Hawkes"),
Song(name:"Never Gonna Give You Up", artist:"Rick Astley")
]
// "library" 的类型被推断为[MediaItem]

事实上library 储存的项目在后台依旧是MovieSong 实例。总之,如果你遍历这个数组的内容,你取出的项目将会是MediaItem 类型而非MovieSong 类型。为了使用他们原生的类型,你需要检查他们的类型或将他们向下转换为不同的类型,如下所述。

类型检查(is)

使用类型检查操作符 (is )来检查一个实例是否属于一个特定的子类。如果实例是该子类类型,类型检查操作符返回true ,否则返回false

下面的例子定义了两个变量,movieCountsongCount ,用来计算数组libraryMovieSong 实例的个数:

1
2
3
4
5
6
7
8
9
10
11
12
13
var movieCount =0
var songCount =0
for itemin library {
if itemisMovie {
movieCount +=1
}elseif itemisSong {
songCount +=1
}
}
print("Media library contains\(movieCount) movies and\(songCount) songs")
// Prints "Media library contains 2 movies and 3 songs"

这个例子遍历了library 数组中的每个元素。每一轮中,for-in 的循环都将item 常量设置为数组中的下一个MediaItem

如果当前MediaItemMovie 类型的实例,item is Movie 返回true ,反之返回false 。同样的,item is Song 检查了该对象是否为Song 类型的实例。在for-in 循环的最后,movieCountsongCount 的值就是数组中对应类型实例的数量。

向下类型转换(as)

某个类类型的常量或变量可能实际上在后台引用自一个子类的实例。当你遇到这种情况时你可以尝试使用类型转换操作符( as? 或 as! )将它向下*类型转换至其子类类型*。

由于向下类型转换能失败,类型转换操作符就有了两个不同形式。条件形式as?返回了一个你将要向下类型转换的值的可选项强制形式as!则将向下类型转换和强制展开结合为一个步骤

如果你不确定你向下转换类型是否能够成功,请使用条件形式的类型转换操作符 (as? )。使用条件形式的类型转换操作符总是返回一个可选项,如果向下转换失败,可选值为nil 。这允许你检查向下类型转换是否成功。

当你确信向下转换类型会成功时,使用强制形式的类型转换操作符(as!)。当你向下转换至一个错误的类型时,强制形式的类型转换操作符会触发一个运行错误

下面的例子遍历了library 中的每个MediaItem ,并打印出相应的描述信息。要这样做的话,每个项目均需要被当做MovieSong 来访问,而不仅仅是MediaItem 。为了在描述信息中访问MovieSongdirectorartist 属性,这样做是必要的。

在这个例子中,数组中每一个项目的类型可能是Movie 也可能是Song 。你不知道遍历时项目的确切类型是什么,所以这时使用条件形式的类型转换符( as? )来检查遍历中每次向下类型转换:

1
2
3
4
5
6
7
8
9
10
11
12
13
for itemin library {
iflet movie = itemas?Movie {
print("Movie: '\(movie.name)', dir.\(movie.director)")
}elseiflet song = itemas?Song {
print("Song: '\(song.name)', by\(song.artist)")
}
}
// Movie: 'Casablanca', dir. Michael Curtiz
// Song: 'Blue Suede Shoes', by Elvis Presley
// Movie: 'Citizen Kane', dir. Orson Welles
// Song: 'The One And Only', by Chesney Hawkes
// Song: 'Never Gonna Give You Up', by Rick Astley

例子开头尝试将当前item 当做Movie 向下类型转换。由于item 是一个MediaItem 的实例,它有可能是Movie 类型;同样的,也有可能是Song 或者仅仅是MediaItem 基类。介于这种不确定性,类型转换符as? 在向下类型转换到子类时返回了一个可选项。item as? Movie 的结果是Movie? 类型,也就是“可选Movie 类型”。

当数组中的Song 实例使用向下转换至Movie 类型时会失败。为了处理这种情况,上面的例子使用了可选绑定来检查可选Movie 类型是否包含了一个值(或者说检查向下类型转换是否成功)。这个可选绑定写作“if let movie = item as? Movie ”,它可以被读作:

尝试以Movie 类型访问item 。如果成功,设置一个新的临时常量movie 储存返回的可选Movie 类型 。

如果向下类型转换成功,movie 的属性将用于输出Movie 实例的描述信息,包括director 的名字。同理,无论是否在数组中找到Song ,均可以检查Song 实例然后输出合适的描述(包括artist 的名字)。

Any 和 AnyObject 的类型转换

Swift 为不确定的类型提供了两种特殊的类型别名:

  • AnyObject 可以表示任何类类型的实例。
  • Any 可以表示任何类型,包括函数类型。

只有当你确切需要使用它们的功能和行为时再使用AnyAnyObject 。在写代码时使用更加明确的类型表达总要好一些。

这里有一个使用Any 类型来对不同类型进行操作的例子,包含了函数类型以及非类类型。这个例子定义了一个名为things 的数组,它用于储存Any 类型的值:

1
2
3
4
5
6
7
8
9
var things = [Any]()
things.append(0)
things.append(0.0)
things.append(43)
things.append(3.14159)
things.append("hello")
things.append((3.0,5.0))
things.append(Movie(name:"Ghostbusters", director:"Ivan Reitman"))
things.append({ (name:String) ->Stringin"Hello,\(name)"})

这个things 数组包含了两个Int 值、两个Double 值、一个String 值、一个(Double, Double) 的元组、Movie 实例“Ghostbusters”、以及一个接收String 值并返回String 值的闭包表达式。

你可以在switch 结构的case 中使用isas 操作符找出已知AnyAnyObject 类型的常量或变量的具体类型。下面的例子使用switch 语句遍历了things 数组并查询每一项的类型。其中几个switchcase 将确定的值和确定类型的常量绑定在一起,使其值可以被输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
for thingin things {
switch thing {
case0asInt:
print("zero as an Int")
case0asDouble:
print("zero as a Double")
caselet someIntasInt:
print("an integer value of\(someInt)")
caselet someDoubleasDoublewhere someDouble >0:
print("a positive double value of\(someDouble)")
caseisDouble:
print("some other double value that I don't want to print")
caselet someStringasString:
print("a string value of \"\(someString)\"")
caselet (x, y)as (Double,Double):
print("an (x, y) point at\(x),\(y)")
caselet movieasMovie:
print("a movie called\(movie.name), dir.\(movie.director)")
caselet stringConverteras (String) ->String:
print(stringConverter("Michael"))
default:
print("something else")
}
}
// zero as an Int
// zero as a Double
// an integer value of 42
// a positive double value of 3.14159
// a string value of "hello"
// an (x, y) point at 3.0, 5.0
// a movie called Ghostbusters, dir. Ivan Reitman
// Hello, Michael

注意
Any类型表示了任意类型的值,包括可选类型如果你给显式声明的Any类型使用可选项,Swift 就会发出警告。如果你真心需要在Any值中使用可选项,如下所示,你可以使用as运算符来显式地转换可选项为Any

1
2
3
let optionalNumber:Int? =3
things.append(optionalNumber)// Warning
things.append(optionalNumberasAny)// No warning

摘自:swift 官网
所有代码在Xcode9 Swift4 环境编译没问题,代码戳这里 https://github.com/keshiim/LearnSwift4

发表于|分类于||阅读次数

Remove Duplicates from Sorted Array

题目描述

Given a sorted array, remove the dupicatesin-place such that each element appear onlyonce and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input arrayin-place with O(1) extra memory.

Example

1
2
3
4
Given nums = [1,1,2],
Your function shouldreturn length =2, with the first two elements of nums being1and2 respectively.
It doesn't matter what you leave beyond thenew length.

解法1

这道题要我们从有序数组中去除重复项,并返回去重后的数组长度。那么这道题的解题思路是,我们使用快慢指针来记录遍历的坐标,最开始时两个指针都指向第一个数字,如果两个指针指的数字相同,则快指针向前走一步,如果不同,则两个指针都向前走一步,这样当快指针走完整个数组后,慢指针当前的坐标加1 就是数组中不同数字的个数,代码如下:

Cpp

1
2
3
4
5
6
7
8
9
10
11
12
classSolution {
public:
intremoveDuplicates(vector<int>& nums){
if (nums.empty())return0;
int n = nums.size(), pre =0, cur =0;
while (cur < n) {
if (nums[pre] == nums[cur]) ++cur;
else nums[++pre] = nums[cur++];
}
return pre +1;
}
};

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
classSolution{
funcremoveDuplicates(_ nums:inout [Int]) ->Int {
if nums.isEmpty {return0 }
var pre =0, cur =0
let n = nums.count
while cur < n {
if nums[pre] == nums[cur] { cur +=1 }
else {
pre +=1
nums[pre] = nums[cur]
cur +=1
}
}
return pre +1
}
}

解法2

我们也可以用for循环来写,这里的j就是上面解法中的prei就是cur,所以本质上都是一样的,参见代码如下:

Cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
classSolution {
public:
intremoveDuplicates(vector<int>& nums){
if (nums.empty())return0;
int n = nums.size(), j =0;
for (int i =0; i < n; i++) {
if (nums[j] != nums[i]) {
nums[++j] = nums[i];
}
}
return pre +1;
}
};

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
classSolution{
funcremoveDuplicates(_ nums:inout [Int]) ->Int {
if nums.isEmpty {return0 }
var j =0
let n = nums.count
for iin0..<n {
if nums[j] != nums[i] {
j +=1
nums[j] = nums[i]
}
}
return pre +1
}
}

发表于|分类于||阅读次数

错误处理是相应和接收来自你程序中错误条件的过程。Swift 给运行时可恢复错误的抛出、捕获、传递和操纵提供了一类支持。
有些函数和方法不能保证总能完全执行或者产生有用的输出。可选项用来表示不存在值,但是当函数错误,能够了解到什么导致了错误将会变得很有用处,这样你的代码就能根据错误来响应了。

举例来说,假设一个阅读和处理来自硬盘上文件数据的任务。这种情况下有很多种导致任务失败的方法,目录中文件不存在,文件没有读权限,或者文件没有以兼容格式编码。从这些错误中区分不同的状况将能够让程序解决和从这些错误中恢复,并且把不能解决的错误通知给用户。

表示和抛出错误

在 Swift 中,错误表示为遵循Error协议类型的值。这个空的协议明确了一个类型可以用于错误处理。

Swift 枚举是典型的为一组相关错误条件建模的完美配适类型,关联值还允许错误错误通讯携带额外的信息。比如说,这是你可能会想到的游戏里自动售货机会遇到的错误条件:

1
2
3
4
5
enumVendingMachineError:Error{
case invalidSelection
case insufficientFunds(coinsNeeded:Int)
case outOfStock
}

抛出一个错误允许你明确某些意外的事情发生了并且正常的执行流不能继续下去。你可以使用throw 语句来抛出一个错误。比如说,下面的代码通过抛出一个错误来明确自动售货机需要五个额外的金币:

1
throwVendingMachineError.insufficientFunds(coinsNeeded:5)

处理错误

当一个错误被抛出,周围的某些代码必须为处理错误响应——比如说,为了纠正错误,尝试替代方案,或者把错误通知用户。

在 Swift 中有四种方式来处理错误。你可以将来自函数的错误传递给调用函数的代码中,使用do-catch 语句来处理错误,把错误作为可选项的值,或者错误不会发生的断言。每一种方法都在下边的章节中有详细叙述。

当函数抛出一个错误,它就改变了你程序的流,所以能够快速定位错误就显得格外重要。要定位你代码中的这些位置,使用try 关键字——或者try?try! 变体——放在调用函数、方法或者会抛出错误的初始化器代码之前。这些关键字在下面的章节中有详细的描述。

使用抛出函数传递错误

为了明确一个函数或者方法可以抛出错误,你要在它的声明当中的形式参数后边写上throws关键字。使用throws标记的函数叫做抛出函数。如果它明确了一个返回类型,那么throws关键字要在返回箭头 (->)之前。

1
2
3
funccanThrowErrors()throws ->String
funccannotThrowErrors() ->String

抛出函数可以把它内部抛出的错误传递到它被调用的生效范围之内。

注意:只有抛出函数可以传递错误。任何在非抛出函数中抛出的错误都必须在该函数内部处理。

在抛出函数体内的任何地方,你都可以用throw语句来抛出错误。

在下边的栗子中,VendingMachine类拥有一个如果请求的物品不存在、卖光了或者比押金贵了就会抛出对应的VendingMachineError错误的vend(itemNamed:)方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
structItem{
var price:Int
varcount:Int
}
classVendingMachine{
var inventory = ["Candy Bar":Item(price:12,count:7),
"Chips":Item(price:10,count:4),
"Pretzels":Item(price:7,count:11)
]
var coinsDeposited =0
funcvend(itemNamed name: String)throws {
guardlet item = inventory[name]else {
throwVendingMachineError.invalidSelection
}
guard item.count >0else {
throwVendingMachineError.outOfStock
}
guard item.price <= coinsDepositedelse {
throwVendingMachineError.insufficientFunds(coinsNeeded: item.price - coinsDeposited)
}
coinsDeposited -= item.price
var newItem = item
newItem.count -=1
inventory[name] = newItem
print("Dispensing\(name)")
}
}

vend(itemNamed:)方法的实现使用了guard语句来提前退出并抛出错误,如果购买零食的条件不符合的话。因为throw语句立即传送程序控制,所以只有所有条件都达到,物品才会售出。

由于vend(itemNamed:)方法传递它抛出的任何错误,所以你调用它的代码要么直接处理错误——使用do-catch语句,try?或者try!——要么继续传递它们。比如说,下边栗子中的buyFavoriteSnack(person:vendingMachine:)同样是一个抛出函数,任何vend(itemNamed:)方法抛出的函数都会向上传递给调用buyFavoriteSnack(person:vendingMachine:)函数的地方。

1
2
3
4
5
6
7
8
9
10
let favoriteSnacks = [
"Alice":"Chips",
"Bob":"Licorice",
"Eve":"Pretzels",
]
funcbuyFavoriteSnack(person: String, vendingMachine: VendingMachine)throws {
let snackName = favoriteSnacks[person] ??"Candy Bar"
try vendingMachine.vend(itemNamed: snackName)
}
// Dispensing Chips

在这个栗子中,buyFavoriteSnack(person:vendingMachine:)函数查找给定人的最爱零食并且尝试通过调用vend(itemNamed:)方法来购买它们。由于vend(itemNamed:)方法会抛出错误,调用的时候要在前边用try关键字

使用 Do-Catch 处理错误

使用do-catch语句来通过运行一段代码处理错误。如果do分句中抛出了一个错误,它就会与catch分句匹配,以确定其中之一可以处理错误。

这是do-catch语句的通常使用姿势:

1
2
3
4
5
6
7
8
do {
try expression
statements
}catch pattern1 {
statements
}catch pattern2where condition {
statements
}

catch后写一个模式来明确分句可以处理哪个错误。如果一个catch分句没有模式,这个分句就可以匹配所有错误并且绑定这个错误到本地常量error

catch分句没有处理do分句可能抛出的所有错误。如果没有catch分句能处理这个错误,那错误就会传递到周围的生效范围当中。总之,错误总得在周围某个范围内被处理。举例来说,接下来的代码处理了VendingMachineError枚举里的所有三个错误,但其他所有错误得通过范围内其他代码处理:

1
2
3
4
5
6
7
8
9
10
11
12
13
var vendingMachine =VendingMachine()
vendingMachine.coinsDeposited =8
do {
try buyFavoriteSnack("Alice", vendingMachine: vendingMachine)
// Enjoy delicious snack
}catchVendingMachineError.invalidSelection {
print("Invalid Selection.")
}catchVendingMachineError.outOfStock {
print("Out of Stock.")
}catchVendingMachineError.insufficientFunds(let coinsNeeded) {
print("Insufficient funds. Please insert an additional\(coinsNeeded) coins.")
}
// prints "Insufficient funds. Please insert an additional 2 coins."

在上面的栗子当中,函数buyFavoriteSnack(person:vendingMachine:)try表达式中被调用,因为它会抛出错误。如果抛出错误,执行会立即切换到catch分句,它决定是否传递来继续。如果没有错误抛出,do语句中剩下的语句将会被执行。

转换错误为可选项

使用try?通过将错误转换为可选项来处理一个错误。如果一个错误在try?表达式中抛出,则表达式的值为nil。比如说下面的代码xy拥有同样的值和行为:

1
2
3
4
5
6
7
8
9
10
11
12
funcsomeThrowingFunction()throws ->Int {
// ...
}
let x =try? someThrowingFunction()
let y:Int?
do {
y =try someThrowingFunction()
}catch {
y =nil
}

如果someThrowingFunction()抛出一个错误,xy的值就是nil。另一方面,xy的值是函数返回的值。注意xy是可选的无论someThrowingFunction()返回什么类型,这里函数返回了一个整数,所以xy是可选整数。

当你想要在同一句里处理所有错误时,使用try?能让你的错误处理代码更加简洁。比如,下边的代码使用了一些方法来获取数据,或者在所有方式都失败后返回nil

1
2
3
4
5
funcfetchData() ->Data? {
iflet data =try? fetchDataFromDisk() {return data }
iflet data =try? fetchDataFromServer() {return data }
returnnil
}

取消错误传递

事实上有时你已经知道一个抛出错误或者方法不会在运行时抛出错误。在这种情况下,你可以在表达式前写try!取消错误传递并且把调用放进不会有错误抛出的运行时断言当中。如果错误真的抛出了,你会得到一个运行时错误。

比如说,下面的代码使用了loadImage(_:)函数,它在给定路径下加载图像资源,如果图像不能被加载则抛出一个错误。在这种情况下,由于图像跟着应用走,运行时不会有错误抛出,所以取消错误传递是合适的。

1
let photo =try! loadImage("./Resources/John Appleseed.jpg")

指定清理操作

使用defer语句来在代码离开当前代码块前执行语句合集。这个语句允许你在以任何方式离开当前代码块前执行必须要的清理工作——无论是因为抛出了错误还是因为return或者break这样的语句。比如,你可以使用defer语句来保证文件描述符都关闭并且手动指定的内存到被释放。

defer语句延迟执行直到当前范围退出。这个语句由defer关键字和需要稍后执行的语句组成。被延迟执行的语句可能不会包含任何会切换控制出语句的代码,比如breakreturn语句,或者通过抛出一个错误。延迟的操作与其指定的顺序相反执行——就是说,第一个defer语句中的代码会在第二个中代码执行完毕后执行,以此类推。

1
2
3
4
5
6
7
8
9
10
11
12
funcprocessFile(filename: String)throws {
if exists(filename) {
let file =open(filename)
defer {
close(file)
}
whilelet line =try? file.readline() {
// Work with the file.
}
// close(file) is called here, at the end of the scope.
}
}

摘自:Swift 官网
所有代码在Xcode9 Swift4 环境编译没问题,代码戳这里 https://github.com/keshiim/LearnSwift4

发表于|分类于||阅读次数

可选链是一个调用和查询可选属性、方法和下标的过程,它可能为nil如果可选项包含值,属性、方法或者下标的调用成功;如果可选项是nil ,属性、方法或者下标的调用会返回nil 。多个查询可以链接在一起,如果链中任何一个节点是nil ,那么整个链就会得体地失败。

注意
Swift 中的可选链与 Objective-C 中的 nil 信息类似,但是它却工作在任意类型上,而且它能检测成功还是失败。

可选链代替强制展开

你可以通过在你希望如果可选项为非nil 就调用属性、方法或者脚本的可选值后边使用问号(?来明确可选链。这和在可选值后放叹号(! )来强制展开它的值非常类似。主要的区别在于可选链会在可选项为nil得体地失败,而强制展开则在可选项为nil 时触发运行时错误。

为了显示出可选链可以在nil 值上调用,可选链调用的结果一定是一个可选值,就算你查询的属性、方法或者下标返回的是非可选值。你可以使用这个可选项返回值来检查可选链调用是成功(返回的可选项包含值),还是由于链中出现了nil 而导致没有成功(返回的可选值是nil )。

另外,可选链调用的结果与期望的返回值类型相同,只是包装成了可选项。通常返回Int 的属性通过可选链后会返回一个Int?

接下来的一些代码片段演示了可选链与强制展开的不同并允许你检查是否成功。首先,定义两个类,PersonResidence

1
2
3
4
5
6
7
classPerson{
var residence:Residence?
}
classResidence{
var numberOfRooms =1
}

Residence 实例有一个Int 属性叫做numberOfRooms ,它带有默认值 1 .Person 实例有一个Residence? 类型的可选residence 属性。
如果你创建一个新的Person 实例,得益于可选项的特性,它的residence 属性会默认初始化为nil 。下面的代码中,john 拥有值为nilresidence 属性:

1
let john =Person()

如果你尝试访问这个人的residence 里的numberOfRooms 属性,通过在residence 后放一个叹号来强制展开它的值,你会触发一个运行时错误,因为residence 根本没有值可以展开:

1
2
let roomCount = john.residence!.numberOfRooms
// this triggers a runtime error

上边的代码会在john.residence 有一个非nil 值时成功并且给roomCount 赋值一个包含合适房间号的Int 值。总之,这段代码一定会在residencenil 时触发运行时错误,如同上边展示的那样。
可选链提供另一种访问numberOfRooms 的方法。要使用可选链,使用问号而不是叹号:

1
2
3
4
5
6
iflet roomCount = john.residence?.numberOfRooms {
print("John's residence has\(roomCount) room(s).")
}else {
print("Unable to retrieve the number of rooms.")
}
// Prints "Unable to retrieve the number of rooms."

事实上通过可选链查询就意味着对numberOfRooms 的调用一定会返回Int? 而不是Int

你可以赋值一个Residence 实例给john.residence ,这样它就不会再有nil 值:

1
john.residence =Residence()

john.residence 现在包含了实际的Residence 实例,而不是nil 。如果你尝试用与之前相同的可选链访问numberOfRooms ,它就会返回一个Int? 包含默认numberOfRooms 值 1 :

1
2
3
4
5
6
iflet roomCount = john.residence?.numberOfRooms {
print("John's residence has\(roomCount) room(s).")
}else {
print("Unable to retrieve the number of rooms.")
}
// Prints "John's residence has 1 room(s)."

为可选链定义模型类

你可以使用可选链来调用属性、方法和下标不止一个层级。这允许你在相关类型的复杂模型中深入到子属性,并检查是否可以在这些子属性里访问属性、方法和下标。

下边的代码段定义了四个模型类用于随后的栗子,包括多层可选链的栗子。这些栗子通过添加RoomAddress 类扩展了上边的PersonResidence 模型,以及相关的属性、方法和下标。

Person 类与之前的定义方式相同,Residence 类比以前要复杂一些。这次,Residence 类定义了一个叫做rooms 的变量属性,它使用一个空的[Room] 类型空数组初始化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classResidence{
var rooms = [Room]()
var numberOfRooms:Int {
return rooms.count
}
subscript(i:Int) ->Room {
get {
return rooms[i]
}
set {
rooms[i] = newValue
}
}
funcprintNumberOfRooms() {
print("The number of rooms is\(numberOfRooms)")
}
var address:Address?
}

由于这个版本的Residence 储存了Room 实例的数组,它的numberOfRooms 属性使用计算属性来实现,而不是储存属性。计算属性numberOfRooms 只是返回rooms数组的count 属性值。
作为给它的rooms 数组赋值的快捷方式,这个版本的Residence 提供了一个可读写的下标来访问rooms 数组的索引位置。

这个版本的Residence 同样提供了一个叫做printNumberOfRooms 的方法,它打印住所中的房间号。最终,Residence 定义了一个可选属性叫做address ,它是一个Address? 类型,这个属性的Address 类类型在下面定义。

rooms 数组使用的Room 类型仅有一个属性叫做name ,还有一个初始化器来给这个属性设置合适的房间名:

1
2
3
4
classRoom{
let name:String
init(name:String) {self.name = name }
}

这个模型的最后一个类型叫做Address 。这个类型有三个String? 类型可选属性。前两个属性,buildingNamebuildingNumber ,是定义地址中特定建筑部分的代替方式。第三个属性,street ,是给地址里街道命名的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
classAddress{
var buildingName:String?
var buildingNumber:String?
var street:String?
funcbuildingIdentifier() ->String? {
if buildingName !=nil {
return buildingName
}elseif buildingNumber !=nil && street !=nil {
return"\(buildingNumber)\(street)"
}else {
returnnil
}
}
}

Address 类同样提供了一个方法叫做buildingIdentifier() ,它有一个String? 类型的返回值。这个方法检查地址的属性并返回buildingName 如果它有值的话,或者把buildingNumberstreet 串联起来,如果它们都有值的话,或者就是nil

通过可选链访问属性

如同可选链代替强制展开中展示的那样,你可以使用可选链来访问可选值里的属性,并且检查这个属性的访问是否成功。
使用上边定义的类来创建一个新得Person 实例,并且尝试如之前一样访问它的numberOfRooms 属性:

1
2
3
4
5
6
7
8
let john =Person()
iflet roomCount = john.residence?.numberOfRooms {
print("John's residence has\(roomCount) room(s).")
}else {
print("Unable to retrieve the number of rooms.")
}
// Prints "Unable to retrieve the number of rooms."

由于john.residencenil ,这个可选链调用与之前一样失败了。
你同样可以尝试通过可选链来给属性赋值:

1
2
3
4
let someAddress =Address()
someAddress.buildingNumber ="29"
someAddress.street ="Acacia Road"
john.residence?.address = someAddress

在这个栗子中,给john.residenceaddress 属性赋值会失败,因为john.residence 目前是nil
这个赋值是可选链的一部分,也就是说= 运算符右手侧的代码都不会被评判。在先前的栗子中,不容易看出someAddress 没有被评判,因为赋值一个常量不会有任何副作用。下边的栗子做同样的赋值,但它使用一个函数来创建地址。函数会在返回值之前打印“函数被调用了”,这可以让你看到= 运算符右手侧是否被评判。

1
2
3
4
5
6
7
8
9
10
funccreateAddress() ->Address {
print("Function was called.")
let someAddress =Address()
someAddress.buildingNumber ="29"
someAddress.street ="Acacia Road"
return someAddress
}
john.residence?.address = createAddress()

你可以看到createAddress() 函数没有被调用,因为没有任何东西打印出来。

通过可选链调用方法

你可以使用可选链来调用可选项里的方法,并且检查调用是否成功。你甚至可以在没有定义返回值的方法上这么做

Residence 类中的printNumberOfRooms() 方法打印了当前numberOfRooms 的值。方法看起来长这样:

1
2
3
funcprintNumberOfRooms() {
print("The number of rooms is\(numberOfRooms)")
}

这个方法没有指定返回类型。总之,如没有返回值的函数中描述的那样,函数和方法没有返回类型就隐式地指明为 Void 类型。意思是说它们返回一个()的值或者是一个空的元组。

如果你用可选链在可选项里调用这个方法,方法的返回类型将会是Void? ,而不是Void ,因为当你通过可选链调用的时候返回值一定会是一个可选类型。这允许你使用if 语句来检查是否能调用printNumberOfRooms() 方法,就算是方法自身没有定义返回值也可以。通过对比调用printNumberOfRooms 返回的值是否为nil 来确定方法的调用是否成功:

1
2
3
4
5
6
if john.residence?.printNumberOfRooms() !=nil {
print("It was possible to print the number of rooms.")
}else {
print("It was not possible to print the number of rooms.")
}
// Prints "It was not possible to print the number of rooms."

如果你尝试通过可选链来设置属性也是一样的。上边通过可选链访问属性中的例子尝试设置address 值给john.residence ,就算是residence 属性是nil 也行。任何通过可选链设置属性的尝试都会返回一个 (Void?) 类型值,它允许你与nil 比较来检查属性是否设置成功

1
2
3
4
5
6
if (john.residence?.address = someAddress) !=nil {
print("It was possible to set the address.")
}else {
print("It was not possible to set the address.")
}
// Prints "It was not possible to set the address."

通过可选链访问下标

你可以使用可选链来给可选项下标取回或设置值,并且检查下标的调用是否成功。

注意:
当你通过可选链访问一个可选项的下标时,你需要把问号放在下标括号的前边,而不是后边。可选链的问号一定是紧跟在可选项表达式的后边的。

下边的栗子尝试使用下标取回Residence 类里john.residence 属性的数组rooms 里第一个房间的名字。由于john.residence 目前是nil ,下标的调用失败了:

1
2
3
4
5
6
iflet firstRoomName = john.residence?[0].name {
print("The first room name is\(firstRoomName).")
}else {
print("Unable to retrieve the first room name.")
}
// Prints "Unable to retrieve the first room name."

可选链问号在下标的调用中紧跟john.residence在下标的方括号之前,因为john.residence 在可选链被访问时是可选值。
同样的,你可以尝试通过在可选链里用下标来设置一个新值:

1
john.residence?[0] =Room(name:"Bathroom")

这个下标设置的尝试同样失败了,因为residence 目前还是nil

如果你创建并且赋值一个实际的Residence 实例给john.residence ,在rooms 数组里添加一个或者多个Room 实例,你就可以通过可选链使用Residence 下标来访问rooms 数组里的实际元素了:

1
2
3
4
5
6
7
8
9
10
11
let johnsHouse =Residence()
johnsHouse.rooms.append(Room(name:"Living Room"))
johnsHouse.rooms.append(Room(name:"Kitchen"))
john.residence = johnsHouse
iflet firstRoomName = john.residence?[0].name {
print("The first room name is\(firstRoomName).")
}else {
print("Unable to retrieve the first room name.")
}
// Prints "The first room name is Living Room."

访问可选类型的下标

如果下标返回一个可选类型的值——比如说 Swift 的Dictionary 类型的键下标——放一个问号在下标的方括号后边来链接它的可选返回值:

1
2
3
4
5
ar testScores = ["Dave": [86,82,84],"Bev": [79,94,81]]
testScores["Dave"]?[0] =91
testScores["Bev"]?[0] +=1
testScores["Brian"]?[0] =72
// the "Dave" array is now [91, 82, 84] and the "Bev" array is now [80, 94, 81]

上面的栗子中定义了一个叫做testScores 的字典,它包含两个键值对把String 类型的键映射到一个整型值的数组。这个栗子用可选链把 “Dave” 数组中第一个元素设为 91 ;把 “Bev” 数组的第一个元素增加 1 ;然后尝试设置 “Brian” 数组中的第一个元素。前两个调用是成功了,因为testScores 字典包含了 “Dave” 和 “Bev” 这两个键。第三个调用失败了,因为字典testScores 并没有包含 “Brian” 键。

链的多层连接

你可以通过连接多个可选链来在模型中深入访问属性、方法以及下标。总之,多层可选链不会给返回的值添加多层的可选性。

  • 如果你访问的值不是可选项,它会因为可选链而变成可选项;
  • 如果你访问的值已经是可选的,它不会因为可选链而变得更加可选。

因此:

  • 如果你尝试通过可选链取回一个Int 值,就一定会返回Int? ,不论通过了多少层的可选链;
  • 类似地,如果你尝试通过可选链访问Int? 值,Int? 一定就是返回的类型,无论通过了多少层的可选链。

用可选返回值链接方法

先前的例子说明了如何通过可选链来获取可选类型属性的值。你还可以通过可选链来调用返回可选类型的方法,并且如果需要的话可以继续对方法的返回值进行链接。

在下面的栗子通过可选链来调用AddressbuildingIdentifier() 方法。这个方法返回String? 类型值。正如上面所说,通过可选链调用的方法的最终返回的类型还是String?

1
2
3
4
iflet buildingIdentifier = john.residence?.address?.buildingIdentifier() {
print("John's building identifier is\(buildingIdentifier).")
}
// Prints "John's building identifier is The Larches."

摘自:Swift 官网
所有代码在Xcode9 Swift4 环境编译没问题,代码戳这里 https://github.com/keshiim/LearnSwift4

发表于|分类于||阅读次数

Number of Longest Increasing Subsequence

题目描述

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example

1
2
3
4
5
6
7
Input: [1,3,5,4,7]
Output:2
Explanation: The two longest increasing subsequence are [1,3,4,7]and [1,3,5,7].
Input: [2,2,2,2,2]
Output:5
Explanation: The length of longest continuous increasing subsequence is1,and there are5 subsequences' length is1, so output5.

Note

Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

分析

动态规划求解,建立两个数组lencnt

  • len[k]: 表示以nums[k] 为末尾的最长子序列长度。
  • cnt[k]: 表示以nums[k] 为末尾的最长子序列个数。

对于每一个nums[i],只需要遍历其前面的所有数字nums[j] (0 <= j < i),找到比它小且长度最长的nums[k],就可得出以nums[i] 为末尾的子序列的最大长度 len[i] =len[k] + 1

同时,以nums[i] 为末尾的最长子序列个数应该等于nums[j] (0 <= j < i)中,比它小且长度最长的所有nums[k] 的最长子序列个数之和。

用两条公式来阐述上面一段难以理解的话

  • len[i] = max(len[i], len[k] + 1), for all 0 <= k < i and nums[k] < nums[i] and len[j] + 1 > len[i]
  • cnt[i] = sum(cnt[k]), for all 0 <= k < i and len[i] = len[k] + 1

举个栗子:
nums = {1, 3, 5, 4, 7}

初始状态,len = {1, 1, 1, 1, 1}cnt = {1, 1, 1, 1, 1}

开始遍历

  • 数字 3,比它小的只有 1 =>len[1] = len[0] + 1 = 2,cnt[1] = cnt[0] = 1
  • 数字 5,比它小且长度最长的为 3 =>len[2] = len[1] + 1 = 3,cnt[2] = cnt[1] = 1
  • 数字 4, 比它小且长度最长的为 3 =>len[3] = len[1] + 1 = 3,cnt[3] = cnt[1] = 1
  • 数字 7,比它小且长度最长的为 5 和 4 =>len[4] = len[2] + 1 = 4,cnt[4] = cnt[2] + cnt[3] = 2

最终状态,len = {1, 2, 3, 3, 4}cnt = {1, 1, 1, 1, 2}

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
classSolution {
public:
intfindNumberOfLIS(vector<int>& nums){
int maxLen =1, res =0, n = nums.size();
vector<int> len(n,1);
vector<int> cnt(n,1);
for (int i =1; i < n; i++) {
for (int j =0; j < i; j++) {
if (nums[j] < nums[i]) {
if (len[j] +1 > len[i]) {
len[i] = len[j] +1;
cnt[i] = cnt[j];
}elseif (len[j] +1 == len[i]) {
cnt[i] += cnt[j];
}
}
}
maxLen = max(maxLen, len[i]);
}
for (int i =0; i < n; i++) {
if (maxLen == len[i]) res += cnt[i];
}
return res;
}
};

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
classSolution{
funcfindNumberOfLIS(_ nums: [Int]) ->Int {
if nums.isEmpty {
return0
}
var maxLen =1, res =0
let n = nums.count
var len = [Int](repeating:1,count: n)
var cnt = [Int](repeating:1,count: n)
for iin1..<n {
for jin0..<i {
if nums[j] < nums[i] {
if len[j] +1 > len[i] {
len[i] = len[j] +1
cnt[i] = cnt[j]
}elseif len[j] +1 == len[i] {
cnt[i] += cnt[j]
}
}
}
maxLen =max(maxLen, len[i])
}
for iin0..<n {
if maxLen == len[i] { res += cnt[i] }
}
return res
}
}

类似题目

Longest continuous increasing

发表于|分类于||阅读次数

Longest Continuous Increasing

题目描述

Given an unsorted array of integers, find the length of longestcontinuous increasing subsequence(subarray).

Example

1
2
3
4
5
6
7
8
Input: [1,3,5,4,7]
Output:3
Explanation: The longest continuous increasing subsequence is [1,3,5], its length is3.
Even though [1,3,5,7] is also an increasing subsequence, it'snot a continuous one where5and7 are separated by4.
Input: [2,2,2,2,2]
Output:1
Explanation: The longest continuous increasing subsequence is [2], its length is1.

Note

Length of the array will not exceed 10,000

解法1

这道题让我们求一个数组的最长连续递增序列,由于有了连续这个条件,我们可以使用一个计数器,如果遇到大的数字,计数器自增1;如果是一个小的数字,则计数器重置为1。我们用一个变量cur来表示前一个数字,初始化为整型最大值,当前遍历到的数字num就和cur比较就行了,每次用cnt来更新结果res,参见代码如下:

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
classSolution {
public:
intfindLengthOfLCIS(vector<int>& nums){
int res =0, cnt =0, pre = INT_MAX;
for (int num : nums) {
if (num > pre) ++cnt;
else cnt =1;
res = max(res, cnt);
pre = num;
}
return res;
}
};

Swift

1
2
3
4
5
6
7
8
9
10
11
12
classSolution{
funcfindLengthOfLCIS(_ nums: [Int]) ->Int {
var res =0, cnt =0, pre =Int.max
for numin nums {
if pre < num { cnt +=1 }
else { cnt =1 }
res =max(res, cnt)
pre = num
}
return res
}
}

解法2

下面这种方法的思路和上面的解法一样,每次都和前面一个数字来比较,注意处理无法取到钱一个数字的情况,参见代码如下:

1
2
3
4
5
6
7
8
9
10
11
classSolution {
public:
intfindLengthOfLCIS(vector<int> &nums){
int res =0, cnt =0, n = nums.size();
for (int i =0; i < n; i++) {
if (i ==0 || nums[i -1] < nums[i]) res = max(res, ++cnt);
else cnt =1
}
return res;
}
}

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
classSolution{
funcfindLengthOfLCIS(_ nums: [Int]) ->Int {
var res =0, cnt =0, n = nums.count
for iin0..<n {
if i ==0 || nums[i -1] < nums[i] {
cnt +=1
res =max(res, cnt)
}else {
cnt =1
}
}
return res
}
}

类似题目

Number of Longest Increasing Subsequence

发表于|分类于||阅读次数

Swift 使用自动引用计数(ARC)机制来追踪和管理你的 App 的内存。在大多数情况下,这意味着 Swift 的内存管理机制会一直起作用,你不需要自己考虑内存管理。当这些实例不在需要时,ARC会自动释放类实例所占用的内存。

总之,在少数情况下,为了能帮助你管理内存,ARC需要更多关于你代码之间的关系信息。这里将描述了这些情况并向你展示如何启用ARC来管理你 App 的内存。在 Swift 中使用 ARC 与 _Transitioning to ARC Release Notes_ 中描述的在 Objective-C 中使用 ARC 十分相似。

引用计数只应用于类的实例。结构体和枚举是值类型,不是引用类型,没有通过引用存储和传递

ARC的工作机制

每次你创建一个类的实例,ARC 会分配一大块内存来存储这个实例的信息。这些内存中保留有实例的类型信息,以及该实例所有存储属性值的信息。

此外,当实例不需要时,ARC 会释放该实例所占用的内存,释放的内存用于其他用途。这确保类实例当它不在需要时,不会一直占用内存。

然而,如果 ARC 释放了正在使用的实例内存,那么它将不会访问实例的属性,或者调用实例的方法。确实,如果你试图访问该实例,你的app很可能会崩溃

为了确保使用中的实例不会消失,ARC 会跟踪和计算当前实例被多少属性,常量和变量所引用。只要存在对该类实例的引用,ARC 将不会释放该实例。

为了使这些成为可能,无论你将实例分配给属性,常量或变量,它们都会创建该实例的强引用。之所以称之为“强”引用,是因为它会将实例保持住,只要强引用还在,实例是不允许被销毁的。

ARC

下面的例子展示了自动引用计数的工作机制。这个例子由一个简单的Person 类开始,定义了一个名为name 的存储常量属性:

1
2
3
4
5
6
7
8
9
10
classPerson{
let name:String
init(name:String) {
self.name = name
print("\(name) is being initialized")
}
deinit {
print("\(name) is being deinitialized")
}
}

Person 类有一个初始化器,它设置了实例的name 属性并且输出一条信息表明初始化器生效。Person 类也有一个反初始化器,会在类的实例被销毁的时候打印一条信息。

下面的代码片段定义了三个Peroson? 类型的变量,用来按照代码中的顺序,为新的Person 实例设置多个引用。由于可选类型的变量会被自动初始化为一个nil,目前还不会引用到Person 类的实例。

1
2
3
var reference1:Person?
var reference2:Person?
var reference3:Person?

你可以创建一个新的Person 实例并且将它赋值给三个变量中的一个:

1
2
reference1 =Person(name:"John Appleseed")
// prints "John Appleseed is being initialized"

注意,当调用person 类的出初始化器的时候,会输出 “John Appleseed is being initialized” 信息。这就说明初始化执行了。

因为Person 实例已经赋值给了reference1 变量,现在就有了一个从reference1 到该实例的强引用。因为至少有一个强引用,ARC可以确保Person 一直保持在内存中不被销毁。

如果你将同一个Person 实例分配给了两个变量,则该实例又会多出两个强引用:

1
2
reference2 = reference1
reference3 = reference1

如果你通过给其中两个变量赋值nil 的方式断开两个强引用(包括最先的那个强引用),只留下一个强引用,Person 实例不会被销毁:

1
2
reference1 =nil
reference2 =nil

在你清楚地表明不再使用这个Person 实例时,直到第三个也就是最后一个强引用被断开时 ARC 会销毁它。

1
2
reference3 =nil
// prints "John Appleseed is being deinitialized"

类实例之间的循环强引用

在上面的例子中,ARC 能够追踪你所创建的Person 实例的引用数量,并且会在Person 实例不在使用时销毁。

总之,写出某个类永远不会变成零强引用的代码是可能的。如果两个类实例彼此持有对方的强引用,因而每个实例都让对方一直存在,就会发生这种情况。这就是所谓的循环强引用

解决循环强引用问题,可以通过定义类之间的关系为弱引用(weak )无主引用(unowned )来代替强引用。这个过程在解决类实例之间的循环强引用中有描述。总之,在你学习如何解决循环强引用问题前,了解一下它是如何产生的也是很有意义的事情。

下面的例子展示了一个如何意外地创建循环强引用的例子。这个例子定义了两个类,分别是PersonApartment ,用来建模公寓和它其中的居民:

1
2
3
4
5
6
7
8
9
10
11
12
13
classPerson{
let name:String
init(name:String) {self.name = name }
var apartment:Apartment?
deinit {print("\(name) is being deinitialized") }
}
classApartment{
let unit:String
init(unit:String) {self.unit = unit }
var tenant:Person?
deinit {print("Apartment\(unit) is being deinitialized") }
}

每一个Person 实例有一个类型为String ,名字为name 的属性,并有一个可选的初始化为nilapartment 属性。apartment 属性是可选项,因为一个人并不总是拥有公寓。

类似的,每个Apartment 实例都有一个叫unit ,类型为String 的属性,并有一个可选的初始化为niltenant 属性。tenant 属性是可选的,因为一栋公寓并不总是有居民。

这两个类都定义了反初始化器,用以在类实例被反初始化时输出信息。这让你能够知晓PersonApartment 的实例是否像预期的那样被释放。

接下来的代码片段定义了两个可选项变量johnunit4A ,它们分别被赋值为下面的ApartmentPerson 的实例。这两个变量都被初始化为nil ,这正是可选项的优点:

1
2
var john:Person?
var unit4A:Apartment?

在两个实例的强引用创建和分配之后,下图表现了强引用的关系。John 变量对Person 实例有一个强引用,unit4A 变量对Apartment 实例有一个强引用:
referenceCycle01_2x
现在你就可以把这两个实例关联在一起,这样人就有公寓了,而且公寓有房间号。注意,感叹号(! )是用来展开和访问可选变量johnunit4A 里的实例的,所以这些实例的属性可以设置:

1
2
john!.apartment = unit4A
unit4A!.tenant = john

在将两个实例联系在一起之后,强引用的关系如图所示:
referenceCycle02_2x

不幸的是,这两个实例关联后会产生一个循环强引用。Person 实例现在有了一个指向Apartment 实例的强引用,而Apartment 实例也有了一个指向Person 实例的强引用。因此,当你断开johnunit4A 变量所持有的强引用时,引用计数并不会降零,实例也不会被ARC 释放:

1
2
john =nil
unit4A =nil

注意,当你把这两个变量设为nil 时,没有任何一个反初始化器被调用。循环强引用会一直阻止PersonApartment 类实例的释放,这就在你的应用程序中造成了内存泄漏。
在你将johnunit4A 赋值为nil 后,强引用关系如下图:
referenceCycle03_2x
PersonApartment 实例之间的强引用关系保留了下来并且不会被断开。

解决实例之间的循环强引用

Swift 提供了两种办法用来解决你在使用类的属性时所遇到的循环强引用问题:弱引用(weak reference )和无主引用(unowned reference )

弱引用和无主引用允许循环引用中的一个实例引用另外一个实例而不保持强引用。这样实例能够互相引用而不产生循环强引用。

对于生命周期中会变为nil 的实例使用弱引用。相反,对于初始化赋值后再也不会被赋值为 nil 的实例,使用无主引用。在实例的生命周期中,当引用可能“没有值”的时候,就使用弱引用来避免循环引用。如同在无主引用中描述的那样,如果引用始终有值,则可以使用无主引用来代替。上面的Apartment 例子中,在它的声明周期中,有时是”没有居民”的,因此适合使用弱引用来解决循环强引用。

弱引用

弱引用不会对其引用的实例保持强引用,因而不会阻止 ARC 释放被引用的实例。这个特性阻止了引用变为循环强引用。声明属性或者变量时,在前面加上weak 关键字表明这是一个弱引用。

由于弱引用不会强保持对实例的引用,所以说实例被释放了弱引用仍旧引用着这个实例也是有可能的。因此,ARC 会在被引用的实例被释放时自动地设置弱引用为nil 。由于弱引用需要允许它们的值为nil ,它们一定得是可选类型

你可以检查弱引用的值是否存在,就像其他可选项的值一样,并且你将永远不会遇到“野指针”。

在 ARC 给弱引用设置nil 时不会调用属性观察者

下面的例子跟上面PersonApartment 的例子一致,但是有一个重要的区别。这次,Apartmenttenant 属性被声明为弱引用:

1
2
3
4
5
6
7
8
9
10
11
12
13
classPerson{
let name:String
init(name:String) {self.name = name }
var apartment:Apartment?
deinit {print("\(name) is being deinitialized") }
}
classApartment{
let unit:String
init(unit:String) {self.unit = unit }
weakvar tenant:Person?
deinit {print("Apartment\(unit) is being deinitialized") }
}

两个变量(johnunit4A )之间的强引用和关联创建得与上次相同:

1
2
3
4
5
6
7
8
var john:Person?
var unit4A:Apartment?
john =Person(name:"John Appleseed")
unit4A =Apartment(unit:"4A")
john!.apartment = unit4A
unit4A!.tenant = john

现在,两个关联在一起的实例的引用关系如下图所示:
weakReference01_2x
Person 实例依然保持对Apartment 实例的强引用,但是Apartment 实例现在对Person 实例是弱引用。这意味着当你断开john 变量所保持的强引用时,再也没有指向Person 实例的强引用了,由于再也没有指向Person 实例的强引用,该实例会被释放:

1
2
john =nil
// prints "John Appleseed is being deinitialized"

**由于再也没有强引用到Person 它被释放掉了并且tenant 属性被设置为nil
weakReference02_2x
现在只剩下来自unit4A 变量对Apartment 实例的强引用。如果你打断这个强引用,那么Apartment 实例就再也没有强引用了:

1
2
unit4A =nil
// prints "Apartment 4A is being deinitialized"

由于再也没有指向Apartment 实例的强引用,该实例也会被释放:
weakReference03_2x

在使用垃圾回收机制的系统中,由于没有强引用的对象会在内存有压力时触发垃圾回收而被释放,弱指针有时用来实现简单的缓存机制。总之,对于 ARC 来说,一旦最后的强引用被移除,值就会被释放,这样的话弱引用就不再适合这类用法了

无主引用

和弱引用类似,无主引用 不会牢牢保持住引用的实例。但是不像弱引用,总之,无主引用假定是永远有值的。因此,无主引用总是被定义为非可选类型。你可以在声明属性或者变量时,在前面加上关键字unowned 表示这是一个无主引用。

由于无主引用是非可选类型,你不需要在使用它的时候将它展开。无主引用总是可以直接访问。不过 ARC 无法在实例被释放后将无主引用设为nil ,因为非可选类型的变量不允许被赋值为nil

注意:
如果你试图在实例的被释放后访问无主引用,那么你将触发运行时错误。只有在你确保引用会一直引用实例的时候才使用无主引用。

还要注意的是,如果你试图访问引用的实例已经被释放了的无主引用,Swift 会确保程序直接崩溃。你不会因此而遭遇无法预期的行为。所以你应当避免这样的事情发生。

下面的例子定义了两个类,CustomerCreditCard ,模拟了银行客户和客户的信用卡。这两个类中,每一个都将另外一个类的实例作为自身的属性。这种关系可能会造成循环强引用。

CustomerCreditCard 之间的关系与前面弱引用例子中ApartmentPerson 的关系略微不同。在这个数据模型中,一个客户可能有或者没有信用卡,但是一张信用卡总是关联着一个客户。为了表示这种关系,Customer 类有一个可选类型的card 属性,但是CreditCard 类有一个非可选类型的customer 属性。

另外,新的CreditCard 实例只有通过传送number 值和一个customer 实例到CreditCard 的初始化器才能创建。这就确保了CreditCard 实例在创建时总是有与之关联的customer 实例。

由于信用卡总是关联着一个客户,因此将customer 属性定义为无主引用,以避免循环强引用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
classCustomer{
let name:String
var card:CreditCard?
init(name:String) {
self.name = name
}
deinit {
print("\(name) is being deinitialized")
}
}
classCreditCard{
let number:UInt64
unownedlet customer:Customer
init(number:UInt64, customer:Customer) {
self.number = number
self.customer = customer
}
deinit {
print("Card #\(number) is being deinitialized")
}
}

下面的代码片段定义了一个叫john 的可选Customer 变量,用来保存某个特定客户的引用。由于是可选项,所以变量被初始化为nil

1
var john:Customer?

现在你可以创建一个Customer 实例,用它初始化和分配一个新的CreditCard 实例作为customercard 属性:

1
2
john =Customer(name:"John Appleseed")
john!.card =CreditCard(number:1234_5678_9012_3456, customer: john!)

如下图,是你关联了两个实例后的图示关系:
unownedReference01_2x
现在Customer 实例对CreditCard 实例有一个强引用,并且CreditCard 实例对Customer 实例有一个无主引用。

由于Customer 的无主引用,当你断开john 变量持有的强引用时,那么就再也没有指向Customer 实例的强引用了。
unownedReference02_2x
因为不再有Customer 的强引用,该实例被释放了。其后,再也没有指向CreditCard 实例的强引用,该实例也随之被释放了:

1
2
3
john =nil
// prints "John Appleseed is being deinitialized"
// prints "Card #1234567890123456 is being deinitialized"

上边的例子展示了如何使用安全无主引用。Swift 还为你需要关闭运行时安全检查的情况提供了不安全无主引用——举例来说,性能优化的时候。对于所有的不安全操作,你要自己负责检查代码安全性。

使用unowned(unsafe) 来明确使用了一个不安全无主引用。如果你在实例的引用被释放后访问这个不安全无主引用,你的程序就会尝试访问这个实例曾今存在过的内存地址,这就是不安全操作。

无主引用和隐式展开的可选属性

上面弱引用和无主引用例子涵盖了两种常用的需要打破循环强引用的场景。

PersonApartment 的例子展示了两个属性的值都允许为nil ,并会潜在的产生循环强引用。这种场景最适合用弱引用来解决

CustomerCreditCard 的例子展示了一个属性的值允许为nil ,而另一个属性的值不允许为nil ,这也可能导致循环强引用。这种场景最好使用无主引用来解决

总之, 还有第三种场景,在这种场景中,两个属性都必须有值,并且初始化完成后永远不会为nil 。在这种场景中,需要一个类使用无主属性,而另外一个类使用隐式展开的可选属性
一旦初始化完成,这两个属性能被直接访问(不需要可选展开),同时避免了循环引用。这一节将为你展示如何建立这种关系。

下面的例子定义了两个类,CountryCity ,每个类将另外一个类的实例保存为属性。在这个数据模型中,每个国家必须有首都,每个城市必须属于一个国家。为了实现这种关系,Country 类拥有一个capitalCity 属性,而City 类有一个country 属性:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
classCountry{
let name:String
var capiitalCity:City!
init(name:String, capitalName:String) {
self.name = name
self.capiitalCity =City(name: capitalName, country:self)
}
}
classCity{
let name:String
unownedlet country:Country
init(name:String, country:Country) {
self.name = name
self.country = country
}
}

为了建立两个类的依赖关系,City 的初始化器接收一个Country 实例,并且将实例保存到country 属性。

Country 的初始化器调用了City 的初始化器。总之,如同在两段式初始化中描述的那样,只有Country 的实例完全初始化完后,Country 的初始化器才能把self 传给City 的初始化器。

为了满足这种需求,通过在类型结尾处加上感叹号(City! )的方式,以声明CountrycapitalCity 属性为一个隐式展开的可选属性。如同在隐式展开可选项中描述的那样,这意味着像其他可选项一样,capitalCity 属性有一个默认值nil ,但是不需要展开它的值就能访问它。

由于capitalCity 默认值为nil ,一旦Country 的实例在初始化器中给name 属性赋值后,整个初始化过程就完成了。这意味着一旦name 属性被赋值后,Country 的初始化器就能引用并传递隐式的selfCountry 的初始化器在赋值capitalCity 时,就能将self 作为参数传递给City 的初始化器。

以上的意义在于你可以通过一条语句同时创建CountryCity 的实例,而不产生循环强引用,并且capitalCity 的属性能被直接访问,而不需要通过感叹号来展开它的可选值:

1
2
3
var country =Country(name:"China", capitalName:"Beijing")
print("\(country.name)`s capital city is called\(country.capiitalCity.name)")
// prints "China`s capital city is called Beijing"

在上面的例子中,使用隐式展开的可选属性的意义在于满足了两段式类初始化器的需求。capitalCity 属性在初始化完成后,就能像非可选项一样使用和存取同时还避免了循环强引用。

闭包的循环强引用

上面我们看到了循环强引用是如何在两个实例属性互相保持对方的强引用时产生的,还知道了如何用弱引用和无主引用来打破这些循环强引用。

循环强引用还会出现在你把一个闭包分配给类实例属性的时候,并且这个闭包中又捕获了这个实例。捕获可能发生于这个闭包函数体中访问了实例的某个属性,比如self.someProperty ,或者这个闭包调用了一个实例的方法,例如self.someMethod() 。这两种情况都导致了闭包 “捕获”了self ,从而产生了循环强引用。

循环强引用的产生,是因为闭包和类相似,都是引用类型。当你把闭包赋值给了一个属性,你实际上是把一个引用赋值给了这个闭包。实质上,这跟之前上面的问题是一样的——两个强引用让彼此一直有效。总之,和两个类实例不同,这次一个是类实例和一个闭包互相引用。

Swift 提供了一种优雅的方法来解决这个问题,称之为闭包捕获列表( closuer capture list )。不过,在学习如何用闭包捕获列表打破循环强引用之前,我们还是先来了解一下这个循环强引用是如何产生的,这对我们很有帮助。

下面的例子为你展示了当一个闭包引用了self 后是如何产生一个循环强引用的。例子中定义了一个叫HTMLElement 的类,用一种简单的模型表示HTML 中的一个单独的元素:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
classHTMLElement{
let name:String
let text:String?
lazyvar asHTML: () ->String = {
iflet text =self.text {
return"<\(self.name)>\(text)</\(self.name)>"
}else {
return"<\(self.name)>"
}
}
init(name:String, text:String? =nil) {
self.name = name
self.text = text
}
deinit {
print("\(name) is being deinitiallized")
}
}

HTMLElement 类定义了一个name 属性来表示这个元素的名称,例如表示标题元素的 “h1” 、代表段落元素的 “p” 、或者代表换行元素的 “br” 。HTMLElement 还定义了一个可选的属性text ,它可以用来设置和展现 HTML 元素的文本。

除了上面的两个属性,HTMLElement 还定义了一个lazy 属性asHTML 。这个属性引用了一个将nametext 组合成 HTML 字符串片段的闭包。该属性是Void -> String 类型,或者可以理解为“一个没有参数,但返回String 的函数”。

默认情况下,闭包赋值给了asHTML 属性,这个闭包返回一个代表 HTML 标签的字符串。如果text 值存在,该标签就包含可选值text ;如果text 不存在,该标签就不包含文本。对于段落元素,根据text 是 “some text” 还是nil ,闭包会返回"<p>some text</p>" 或者 "<p />"

可以像实例方法那样去命名、使用asHTML 属性。总之,由于asHTML 是闭包而不是实例方法,如果你想改变特定元素的 HTML 处理的话,可以用自定义的闭包来取代默认值。

1
2
3
4
5
6
7
let heading =HTMLElement(name:"h1")
let defaultText ="some default text"
heading.asHTML = {
return"<\(heading.name)>\(heading.text ?? defaultText)</\(heading.name)>"
}
print(heading.asHTML())
// prints "<h1>some default text</h1>"

注意:
声明为 lazy 属性,因为只有当元素确实需要处理为 HTML 输出的字符串时,才需要使用 asHTML 。实际上 asHTML 是延迟加载属性意味着你在默认的闭包中可以使用 self ,因为只有当初始化完成以及 self 确实存在后,才能访问延迟加载属性。

HTMLElement 类只提供一个初始化器,通过nametext (如果有的话)参数来初始化一个元素。该类也定义了一个初始化器,当HTMLElement 实例被释放时打印一条消息。

下面的代码展示了如何用HTMLElement 类创建实例并打印消息。

1
2
3
var paragraph:HTMLElement? =HTMLElement(name:"p", text:"hello, world")
print(paragraph!.asHTML())
// prints"hello, world"

上面的paragraph 变量定义为可选HTMLElement ,因此我们接下来可以赋值nil 给它来演示循环强引用。

不幸的是,上面写的HTMLElement 类产生了类实例和asHTML 默认值的闭包之间的循环强引用。循环强引用如下图所示:
closureReferenceCycle01_2x
实例的asHTML 属性持有闭包的强引用。但是,闭包在其闭包体内使用了self (引用了self.nameself.text ),因此闭包捕获了self ,这意味着闭包又反过来持有了HTMLElement 实例的强引用。这样两个对象就产生了循环强引用。

尽管闭包多次引用了self ,它只捕获HTMLElement 实例的一个强引用。

如果设置paragraph 变量为nil ,打破它持有的HTMLElement 实例的强引用,HTMLElement 实例和它的闭包都不会被释放,也是因为循环强引用:

1
paragraph =nil

注意HTMLElement 的反初始化器中的消息并没有被打印,证明了HTMLElement 实例并没有被销毁。

解决闭包的循环强引用

你可以通过定义捕获列表作为闭包的定义来解决在闭包和类实例之间的循环强引用。捕获列表定义了当在闭包体里捕获一个或多个引用类型的规则。正如在两个类实例之间的循环强引用,声明每个捕获的引用为弱引用或无主引用而不是强引用。应当根据代码关系来决定使用弱引用还是无主引用。

注意:Swift 要求你在闭包中引用self成员时使用 self.someProperty 或者 self.someMethod (而不只是 someProperty 或 someMethod )。这有助于提醒你可能会一不小心就捕获了 self 。

定义捕获列表

捕获列表中的每一项都由weakunowned 关键字与类实例的引用(如self )或初始化过的变量(如delegate = self.delegate! )成对组成。这些项写在方括号中用逗号分开

把捕获列表放在形式参数和返回类型前边,如果它们存在的话:

1
2
3
4
lazyvar someClosure: (Int,String) ->String = {
[unownedself,weak delegate =self.delegate!]in
//closure body goes here
}

如果闭包没有指明形式参数列表或者返回类型,是因为它们会通过上下文推断,那么就把捕获列表放在关键字in 前边,闭包最开始的地方:

1
2
3
4
lazyvar someClosure: () ->String = {
[unownedself,weak delegate =self.delegate!]in
// closure body goes here
}

弱引用和无主引用

在闭包和捕获的实例总是互相引用并且总是同时释放时,将闭包内的捕获定义为无主引用。

相反,在被捕获的引用可能会变为nil 时,定义一个弱引用的捕获弱引用总是可选项 ,当实例的引用释放时会自动变为nil 。这使我们可以在闭包体内检查它们是否存在。

如果被捕获的引用永远不会变为nil ,应该用无主引用而不是弱引用。

前面的HTMLElement 例子中,无主引用是正确的解决循环强引用的方法。这样编写HTMLElement 类来避免循环强引用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
classHTMLElement{
let name:String
let text:String?
lazyvar asHTML: () ->String = {
[unownedself]in
iflet text =self.text {
return"<\(self.name)>\(text)</\(self.name)>"
}else {
return"<\(self.name)>"
}
}
init(name:String, text:String? =nil) {
self.name = name
self.text = text
}
deinit {
print("\(name) is being deinitiallized")
}
}

上面的HTMLElement 实现和之前的实现一致,除了在asHTML 闭包中多了一个捕获列表。这里,捕获列表是[unowned self] ,表示“用无主引用而不是强引用来捕获self

和之前一样,我们可以创建并打印HTMLElement 实例:

1
2
3
var paragraph:HTMLElement? =HTMLElement(name:"p", text:"hello, world")
print(paragraph!.asHTML())
// prints "<p>hello, world</p>"

使用捕获列表后引用关系如下图所示:
closureReferenceCycle02_2x
这次,闭包以无主引用的形式捕获self ,并不会持有HTMLElement 实例的强引用。如果将paragraph 赋值为nilHTMLElement 实例将会被释放,并能看到它的反初始化器打印出的消息。

1
2
paragraph =nil
// prints "p is being deinitialized"

摘自:Swift 官网
所有代码在Xcode9 Swift4 环境编译没问题,代码戳这里 https://github.com/keshiim/LearnSwift4

发表于|分类于||阅读次数

类实例被释放的时候,反初始化器就会立即被调用。你可以是用deinit 关键字来写反初始化器,就如同写初始化器要用init 关键字一样。反初始化器只在类类型中有效

反初始化器原理

当实例不再被需要的时候 Swift会自动将其释放掉,以节省资源。如同自动引用计数中描述的那样,Swift 通过自动引用计数(ARC)来处理实例的内存管理。基本上,当你的实例被释放时,你不需要手动清除它们。总之,当你在操作自己的资源时,你可能还是需要在释放实例时执行一些额外的清理工作。比如说,如果你创建了一个自定义类来打开某文件写点数据进去,你就得在实例释放之前关闭这个文件。

每个类当中只能有一个反初始化器。反初始化器不接收任何形式参数,并且不需要写圆括号:

1
2
3
deinit {
// perform the deinitialization
}

反初始化器会在实例被释放之前自动被调用。你不能自行调用反初始化器。父类的反初始化器可以被子类继承,并且子类的反初始化器实现结束之后父类的反初始化器会被调用。父类的反初始化器总会被调用,就算子类没有反初始化器。

由于实例在反初始化器被调用之前都不会被释放,反初始化器可以访问实例中的所有属性并且可以基于这些属性修改自身行为(比如说查找需要被关闭的那个文件的文件名)。

应用反初始化器

这里有一个应用反初始化器的栗子。这里栗子给一个简单的游戏定义了两个新的类型,BankPlayerBank类用来管理虚拟货币,它在流通过程中永远都不能拥有超过10000金币。游戏当中只能有一个Bank,所以Bank以具有类型属性和方法的类来实现当前状态的储存和管理:

1
2
3
4
5
6
7
8
9
10
11
classBank{
staticvar coinsInBank =10_000
staticfuncdistribute(coins numberOfCoinsRequested: Int) ->Int {
let numberOfCoinsToVend =min(numberOfCoinsRequested, coinsInBank)
coinsInBank -= numberOfCoinsToVend
return numberOfCoinsToVend
}
staticfuncreceive(coins: Int) {
coinsInBank += coins
}
}

Bank会一直用CoinsInBank属性来追踪当前金币数量。它同样也提供了两个方法——distribute(coins:)receive(coins:)——来处理金币的收集和分发

distribute(coins:)在分发金币之前检查银行当中是否有足够的金币。如果金币不足,Bank返回一个比需要的数小一些的数值(并且零如果银行里没有金币的话)。distribute(coins:)声明了一个numberOfCoinsToVend的变量形式参数,所以数值可以在方法体内修改而不需要再声明一个新的变量。它返回一个整数值来明确提供的金币的实际数量。
receive(coins:)方法只是添加了接受的金币数量到银行的金币储存里去。

Player类描述了游戏中的一个玩家。每个玩家都有确定数量的金币储存在它们的钱包中。这个以玩家的coinsInPurse属性表示:

1
2
3
4
5
6
7
8
9
10
11
12
classPlayer{
var coinsInPurse:Int
init(coins:Int) {
coinsInPurse =Bank.distribute(coins: coins)
}
funcwin(coins: Int) {
coinsInPurse +=Bank.distribute(coins: coins)
}
deinit {
Bank.receive(coins: coinsInPurse)
}
}

每一个Player实例都会用银行指定的金币数量来作为一开始的限定来初始化,尽管Player实例可能会在没有足够多金币的时候收到更少的数量。

Player类定义了一个win(coins:)方法,它从银行取回确定数量的金币并且把它们添加到玩家的钱包当中。Player类同样实现了一个反初始化器,它会在Player实例释放之前被调用。这时,反初始化器会把玩家多有的金币返回到银行当中:

1
2
3
4
5
var playerOne:Player? =Player(coins:100)
print("A new player has joined the game with\(playerOne!.coinsInPurse) coins")
// Prints "A new player has joined the game with 100 coins"
print("There are now\(Bank.coinsInBank) coins left in the bank")
// Prints "There are now 9900 coins left in the bank"

新的Player实例创建出来了,同时如果可以的话会获取100个金币。这个Player实例储存了一个可选的Player变量叫做playerOne。这里使用了一个可选变量,是因为玩家可以在任何时候离开游戏。可选项允许你追踪当前游戏中是否有玩家。

因为playerOne是可选项,当它的coinsInPurse属相被访问来打印默认金币时,必须使用叹号 (!)才能完全符合,并且无论win(coins:)方法是否被调用:

1
2
3
4
5
playerOne!.win(coins:2_000)
print("PlayerOne won 2000 coins & now has\(playerOne!.coinsInPurse) coins")
// Prints "PlayerOne won 2000 coins & now has 2100 coins"
print("The bank now only has\(Bank.coinsInBank) coins left")
// Prints "The bank now only has 7900 coins left"

这时,玩家拥有了2000个金币。玩家的钱包当中保存了2100个金币,并且银行只剩下7900个金币。

1
2
3
4
5
6
playerOne =nil
print("PlayerOne has left the game")
// prints "PlayerOne has left the game"
print("The bank now has\(Bank.coinsInBank) coins")
// prints "The bank now has 10000 coins"

现在玩家离开了游戏。这通过设置playerOne变量为nil来明确,意味着“无Player实例。”当这个时候,playerOne变量到Player实例的引用被破坏掉了。没有其他的属性或者变量仍在引用Player实例,所以它将会被释放掉以节约内存。在释放掉的瞬间,它的反初始化器会自动被调用,然后它的金币被送回给了银行。

摘自:swift 官网
所有代码在Xcode9 Swift4 环境编译没问题,代码戳这里 https://github.com/keshiim/LearnSwift4

发表于|分类于||阅读次数

Degree of an Array

题目描述

Given a non-empty array of non-negative integersnums, thedegree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray ofnums, that has the same degree asnums.

Example

1
2
3
4
5
6
7
8
9
10
Input: [1,2,2,3,1]
Output:2
Explanation:
The inputarray has a degree of2 because both elements1and2 appear twice.
Of the subarrays that have the same degree:
[1,2,2,3,1], [1,2,2,3], [2,2,3,1], [1,2,2], [2,2,3], [2,2]
The shortest length is2. Soreturn2.
------------------------
Input: [1,2,2,3,1,4,2]
Output:6

Note

  • nums.length will be between 1 and 50,000.
  • nums[i] will be an integer between 0 and 49,999.

分析

这道题给我一个数组,定义数组的度为某个或某些数字出现最多的次数,现让我们找到最短的子数组使其与原数组拥有相同的度。

那么我们需要统计每个数字出现的次数,用哈希表map<数字, 次数> m来建立起数字和出现次数的映射。由于我们要求包含最大度的最小长度子数组,那么最好的情况就是子数组首位数字就是统计度的数字,即出现最多的数字。那么我们肯定要知道该数字第一次出现的位置和最后一次出现的位置,由于我们开始的时候并不知道那个数字出现次数最多,所以我们统计所有数字的首位出现位置,那么我用再用一个哈希表map<数字, pair<首, 尾>> pos来建立每个数字与其首位出现位置的关系。我们用变量degree来表示数组的度。

解法1

现在我们遍历原数组,累加当前数字出现的次数,当某个数字是第一次出现,那么我们用当前位置来更新改数字出现的首位置,否则更新尾位置。没遍历一个数,我们就更新一个degree。当前遍历完成后,我们已经有了数组的度,还有每个数字首位出现的位置,下面就来找出出现次数等于degree的数字,然后计算其首位位置差加上1,由于出现次数为degree的数字不一定只有一个,我们遍历所有的,找出其中最小的即可。代码如下

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
classSulotion {
public:
intfindShortestSubArray(vector<int> &nums){
int n = nums.size(), res = INT_MAX, degree =0;
unordered_map<int,int> m;
unrodered_map<int, pair<int,int>> pos;
for (int i =0; i < n; i++) {
if (++m[nums[i]] ==1) {
pos[nums[i]] = {i, i};
}else {
pos[nums[i]].second = i;
}
degree = max(degree, m[nums[i]]);
}
for (auto a : m) {
if (degree == a.second) {
res = min(res, pos[a.first].second - pos[a.first].first +1);
}
}
return res;
}
};

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
classSolution{
funcfindShortestSubArray(_ nums: [Int]) ->Int {
let n = nums.count
var degree =0, res =Int.max
var m = [Int:Int]();
var pos = [Int: [Int]]()
for iin0..<n {
let num = nums[i]
letcount = (m[num] ??0) +1//次数累加
m[num] =count
ifcount ==1 {
//说明第一次记录
pos[num] = [i, i]
}else {
let position = pos[num]
pos[num] = [(position?.first)!, i];
}
degree =max(degree,count)
}
for (num,count)in m {
ifcount == degree {
res =min(res, (pos[num]?.last)! - (pos[num]?.first)! +1)
}
}
return res
}
}

解法2

下面这种方法只用了一次遍历,思路上跟上面的解法类似,还是要建立数字出现次数的哈希表,还有就是建立每个数字和其第一次出现位置之间的映射,那么我们当前遍历的位置其实可以看作是尾位置,还是可以计算子数组的长度的。我们遍历数组,累加当前数字出现的次数,如果某个数字是第一次出现,建立该数字和当前位置的映射,如果当前数字的出现次数等于degree时,当前位置为尾位置,首位置在startIdx中取的,二者做差加1来更新结果res;如果当前数字的出现次数大于degree,说明之前的结果代表的数字不是出现最多的,直接将结果res更新为当前数字的首尾差加1的长度,然后degree也更新为当前数字出现的次数。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
classSolution {
public:
intfindShortestSubArray(vector<int,int> &nums){
int n = nums.size(), res = INT_MAX, degree =0
unordered_map<int,int> m, startIdx;
for (int i =0; i < n; i++) {
++m[nums[i]];
if (!startIdx.cout(nums[i])) {
startIdx[i] = i;
}
if (m[nums[i]] == degree) {
res = min(res, i - startIdx[nums[i]] +1);
}elseif (m[nums[i] > degree) {
res = i - startIdx[nums[i]] +1;
degree = m[nums[i]];
}
}
return res;
}
}

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
classSolution{
funcfindShortestSubArray(_ nums: [Int]) ->Int {
let n = nums.count
var res =Int.max, degree =0
var m = [Int:Int](), startIdx = [Int:Int]()
for iin0..<n {
m[nums[i]] = (m[nums[i]] ??0) +1//先设置出现次数
if startIdx[nums[i]] ==nil {
startIdx[nums[i]] = i//设置初始位置
}
if m[nums[i]] == degree {
res =min(res, i - startIdx[nums[i]]! +1)
}elseif m[nums[i]]! > degree {
res = i - startIdx[nums[i]]! +1
degree = m[nums[i]]!
}
}
return res
}
}

[8]ページ先頭

©2009-2025 Movatter.jp