题目描述

英文题目

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

return its level order traversal as:

1
2
3
4
5

[
  [3],
  [9,20],
  [15,7]
]

中文题目

给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。

例如:
给定二叉树: [3,9,20,null,null,15,7],

1
2
3
4
5

  3
 / \
9  20
  /  \
 15   7

返回其层次遍历结果：

1
2
3
4
5

[
  [3],
  [9,20],
  [15,7]
]

一. 基础内容

• 1 常量和变量
  • 1.1 声明常量和变量
  • 1.2 类型标注
  • 1.3 命名常量和变量
  • 1.4 输出常量和变量
• 2 注释
• 3 分号
• 4 整数
  • 4.1 整数范围
  • 4.2 Int
  • 4.3 UInt
• 5 浮点数
• 6 类型安全和类型推断
• 7 数值型字面量
• 8 数值类型转换
  • 8.1 整数转换
  • 8.2 整数和浮点数转换
• 9 类型别名
• 10 布尔值
• 11 元组
• 12 可选项
  • 12.1 nil
  • 12.2 If 语句以及强制展开
  • 12.3 可选项绑定
  • 12.4 隐式展开可选项
• 13 错误处理
• 14 断言和先决条件
  • 14.1 使用断言进行调试
  • 14.2 强制先决条件

二. 基本运算符

• 1 专门用语
• 2 赋值运算符
• 3 算术运算符
  • 3.1 余数运算符
  • 3.2 一元减号运算符
  • 3.3 一元加号运算符
• 4 组合赋值符号
• 5 比较运算符
• 6 三元条件运算符
• 7 合并空值运算符
• 8 区间运算符
  • 8.1 闭区间运算符
  • 8.2 半开区间运算符
  • 8.3 单侧区间
• 9 逻辑运算符
  • 9.1 逻辑非运算符
  • 9.2 逻辑与运算符
  • 9.3 逻辑或运算符
  • 9.4 混合逻辑运算
  • 9.5 显式括号

三. 字符串和字符

• 1 字符串字面量
• 2 初始化一个空字符串
• 3 字符串可变性
• 4 字符串是值类型
• 5 操作字符
• 6 连接字符串和字符
• 7 字符串插值
• 8 Unicode
  • 8.1 Unicode 标量
  • 8.2 字符串字面量中的特殊字符
  • 8.3 扩展字形集群
• 9 字符统计
• 10 访问和修改字符串
  • 10.1 字符串索引
  • 10.2 插入和删除
• 11 子字符串
• 12 字符串比较
  • 12.1 字符串和字符相等性
  • 12.2 前缀和后缀相等性
• 13 字符串的 Unicode 表示法
  • 13.1 UTF-8 表示法
  • 13.2 UTF-16 表示法
  • 13.3 Unicode 标量表示法

四. 集合类型

• 1 集合的可变性
• 2 数组
  • 2.1 数组类型简写语法
  • 2.2 创建一个空数组
  • 2.3 使用默认值创建数组
  • 2.4 通过连接两个数组来创建数组
  • 2.5 使用数组字面量创建数组
  • 2.6 访问和修改数组
  • 2.7 遍历一个数组
• 3 合集[1]
  • 3.1 Set 类型的哈希值
  • 3.2 合集类型语法
  • 3.3 创建并初始化一个空合集
  • 3.4 使用数组字面量创建合集
  • 3.5 访问和修改合集
  • 3.6 遍历合集
• 4 执行合集操作
  • 4.1 基本合集操作
  • 4.2 合集成员关系和相等性
• 5 字典
  • 5.1 字典类型简写语法
  • 5.2 创建一个空字典
  • 5.3 用字典字面量创建字典
  • 5.4 访问和修改字典
  • 5.5 遍历字典

五. 控制流

• 1 For-in 循环
• 2 While 循环
  • 2.1 While
  • 2.2 Repeat-While
• 3 条件语句
  • 3.1 If
  • 3.2 Switch
    • 3.2.1 没有隐式贯穿
    • 3.2.2 区间匹配
    • 3.2.3 元组
    • 3.2.4 值绑定
    • 3.2.5 Where
    • 3.2.6 复合情况
• 4 控制转移语句
  • 4.1 Continue
  • 4.2 Break
    • 4.2.1 循环语句中的 Break
    • 4.2.2 Switch 语句里的 Break
  • 4.3 Fallthrough
  • 4.4 给语句打标签
• 5 提前退出
• 6 检查API的可用性

六. 函数

• 1 定义和调用函数
• 2 函数的形式参数和返回值
  • 2.1 无形式参数的函数
  • 2.2 多形式参数的函数
  • 2.3 无返回值的函数
  • 2.4 多返回值的函数
  • 2.5 可选元组返回类型
• 3 函数实际参数标签和形式参数名
  • 3.1 指定实际参数标签
  • 3.2 省略实际参数标签
  • 3.3 默认形式参数值
  • 3.4 可变形式参数
  • 3.5 输入输出形式参数
• 4 函数类型
  • 4.1 使用函数类型
  • 4.2 函数类型作为形式参数类型
  • 4.3 函数类型作为返回类型
• 5 内嵌函数

七. 闭包

• 1 闭包表达式
  • 1.1 Sorted 方法
  • 1.2 闭包表达式语法
  • 1.3 从语境中推断类型
  • 1.4 从单表达式闭包隐式返回
  • 1.5 简写的实际参数名
  • 1.6 运算符函数
• 2 尾随闭包
• 3 捕获值
• 4 闭包是引用类型
• 5 逃逸闭包
• 6 自动闭包

八. 枚举

• 1 枚举
• 2 枚举语法
• 3 使用 Switch 语句来匹配枚举值
• 4 遍历枚举情况（case）
• 5 关联值
• 6 原始值
  • 6.1 隐式指定的原始值
  • 6.2 从原始值初始化
• 7 递归枚举

九. 类和结构体

• 1 类与结构体的对比
  • 1.1 定义语法
  • 1.2 类与结构体实例
  • 1.3 访问属性
  • 1.4 结构体类型的成员初始化器
• 2 结构体和枚举是值类型
• 3 类是引用类型
  • 3.1 特征运算符
  • 3.2 指针
• 4 类和结构体之间的选择
• 5 字符串，数组和字典的赋值与拷贝行为
• 6 译注

Cocoa Operation不需要关心线程管理和数据同步的事情，可以把精力放在自己需要执行的操作上。相关的类有Operation和OperationQueue。其中Operation是个抽象类，使用它必须用它的子类，可以实现它或者使用它定义好的子类：BlockOperation。创建Operation子类的对象，把对象添加到OperationQueue队列里执行。

使用Operation的两种方式

直接用定义好的子类：BlockOperation。

1

Thread.detachNewThreadSelector(#selector(ViewController.downloadImage), toTarget: self, with: nil)

1
2

let myThread = Thread(target: self, selector: #selector(ViewController.downloadImage), object: nil)
myThread.start()

1
2
3
4
5

@objc func downloadImage() {
    let imageUrl = "http://hangge.com/blog/images/logo.png"
    let data = try! Data(contentsOf: URL(string: imageUrl)!)
    print(data.count)
}

线程同步方法通过锁来实现，每个线程都只用一个锁，这个锁与一个特定的线程关联。下面演示两个线程之间的同步。

1
2
3
4
5
6
7

//定义两个线程
var thread1:Thread?
var thread2:Thread?

//定义两个线程条件，用于锁住线程
let condition1 = NSCondition()
let condition2 = NSCondition()

1
2
3
4
5

thread2 = Thread(target: self, selector: #selector(ViewController.method2),
                         object: nil)
thread1 = Thread(target: self, selector: #selector(ViewController.method1),
                 object: nil)
thread1?.start()

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

//定义两方法，用于两个线程调用
@objc func method1(sender:AnyObject){
    for i in 0 ..< 10 {
        print("Thread 1 running \(i)")
        sleep(1)

        if i == 2 {
            thread2?.start() //启动线程2

            //本线程（thread1）锁定
            condition1.lock()
            condition1.wait()
            condition1.unlock()
        }
    }

    print("Thread 1 over")

    //线程2激活
    condition2.signal()
}

//方法2
@objc func method2(sender:AnyObject){
    for i in 0 ..< 10 {
        print("Thread 2 running \(i)")
        sleep(1)

        if i == 2 {
            //线程1激活
            condition1.signal()

            //本线程（thread2）锁定
            condition2.lock()
            condition2.wait()
            condition2.unlock()
        }
    }

    print("Thread 2 over")
}

基本思路是，首先要创建公用的NSCondition实例。然后：
消费者取得锁，取产品，如果没有，则wait，这时会释放锁，直到有线程唤醒它去消费产品；
生产者制造产品，首先也是要取得锁，然后生产，再发signal，这样可唤醒wait的消费者。

Tread在三种多线程技术中是最轻量级的，但需要自己管理线程的生命周期和线程同步。线程同步对数据的加锁会有一定的系统开销。

Thread的两种创建方式

（1）直接创建线程并且自动运行线程

（2）先创建一个线程对象，然后手动运行线程，在运行线程操作之前可以设置线程的优先级等线程信息。

1

Thread.detachNewThreadSelector(#selector(ViewController.downloadImage), toTarget: self, with: nil)

1
2

let myThread = Thread(target: self, selector: #selector(ViewController.downloadImage), object: nil)
myThread.start()

1
2
3
4
5

@objc func downloadImage() {
    let imageUrl = "http://hangge.com/blog/images/logo.png"
    let data = try! Data(contentsOf: URL(string: imageUrl)!)
    print(data.count)
}

线程同步方法通过锁来实现，每个线程都只用一个锁，这个锁与一个特定的线程关联。下面演示两个线程之间的同步。

1
2
3
4
5
6
7

//定义两个线程
var thread1:Thread?
var thread2:Thread?

//定义两个线程条件，用于锁住线程
let condition1 = NSCondition()
let condition2 = NSCondition()

1
2
3
4
5

thread2 = Thread(target: self, selector: #selector(ViewController.method2),
                         object: nil)
thread1 = Thread(target: self, selector: #selector(ViewController.method1),
                 object: nil)
thread1?.start()

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

//定义两方法，用于两个线程调用
@objc func method1(sender:AnyObject){
    for i in 0 ..< 10 {
        print("Thread 1 running \(i)")
        sleep(1)

        if i == 2 {
            thread2?.start() //启动线程2

            //本线程（thread1）锁定
            condition1.lock()
            condition1.wait()
            condition1.unlock()
        }
    }

    print("Thread 1 over")

    //线程2激活
    condition2.signal()
}

//方法2
@objc func method2(sender:AnyObject){
    for i in 0 ..< 10 {
        print("Thread 2 running \(i)")
        sleep(1)

        if i == 2 {
            //线程1激活
            condition1.signal()

            //本线程（thread2）锁定
            condition2.lock()
            condition2.wait()
            condition2.unlock()
        }
    }

    print("Thread 2 over")
}

基本思路是，首先要创建公用的NSCondition实例。然后：
消费者取得锁，取产品，如果没有，则wait，这时会释放锁，直到有线程唤醒它去消费产品；
生产者制造产品，首先也是要取得锁，然后生产，再发signal，这样可唤醒wait的消费者。

BFS代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

BFS(graph, start, end)

	queue = []
	queue.append([start])
	visited.add(start)

	while queue:
		node = queue.pop()
		visited.add(node)
	
		process(node)
		nodes = generate_related_node(node)
		queue.push(nodes)
		
	# other processing work
	...

DFS

递归写法

1
2
3
4
5
6
7
8

visited = set()
dfs(node, visited)
	visited.add(node)
	#process current node here
	...
	for next_node in node.children():
		if not next_node in visited:
			dfs(next_node, visited)

非递归写法（不常用）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

DFS(self, tree)
	if tree.root is None
		return []
	visited, stack = [], [tree.root]
	
	while stack:
		node = stack.pop()
		visited.add(node)
		
		process(node)
		node = generate_related_nodes(node)
		stack.push(nodes)
	
	# other processing work
	...

题目描述

英文题目

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

1
2
3
4

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

1
2
3
4
5

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

1
2
3

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

中文题目

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

1
2
3
4

输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

1
2
3
4
5

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3:

1
2
3

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

题目描述

英文题目

• Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

  You may assume that the array is non-empty and the majority element always exist in the array.

  Example 1:

  1 2	Input: [3,2,3] Output: 3

  Example 2:

  1 2	Input: [2,2,1,1,1,2,2] Output: 2

中文题目

• • 给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

    你可以假设数组是非空的，并且给定的数组总是存在众数。

    示例 1:

    1 2	输入: [3,2,3] 输出: 3

    示例 2:

    1 2	输入: [2,2,1,1,1,2,2] 输出: 2

题目描述

英文题目

• Implement pow(x, n), which calculates x raised to the power n (xn).

  Example 1:

  1 2	Input: 2.00000, 10 Output: 1024.00000

  Example 2:

  1 2	Input: 2.10000, 3 Output: 9.26100

  Example 3:

  1 2 3

  Input: 2.00000, -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25

  Note:

  • -100.0 < x < 100.0
  • n is a 32-bit signed integer, within the range [−231, 231 − 1]

中文题目

• 实现 pow(x, n) ，即计算 x 的 n 次幂函数。

  示例 1:

  1 2	输入: 2.00000, 10 输出: 1024.00000

  示例 2:

  1 2	输入: 2.10000, 3 输出: 9.26100

  示例 3:

  1 2 3

  输入: 2.00000, -2 输出: 0.25000 解释: 2-2 = 1/22 = 1/4 = 0.25

  说明:

  • -100.0 < x < 100.0
  • n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

题目描述

英文题目

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]

1
2
3
4
5
6
7

     _______6______
    /              \
 ___2__          ___8__
/      \        /      \
0      _4       7       9
      /  \
      3   5

Example 1:

1
2
3

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

1
2
3
4

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself 
             according to the LCA definition.

Note:

• All of the nodes’ values will be unique.
• p and q are different and both values will exist in the BST.

中文题目

• 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

  百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

  例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

  1 2 3 4 5 6 7

  _______6______ / \ ___2__ ___8__ / \ / \ 0 _4 7 9 / \ 3 5

  示例 1:

  1 2 3

  输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。

  示例 2:

  1 2 3

  输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

  说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉搜索树中。

题目描述

英文题目

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

1
2
3
4
5
6
7

     _______3______
    /              \
 ___5__          ___1__
/      \        /      \
6      _2       0       8
      /  \
      7   4

Example 1:

1
2
3

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of of nodes 5 and 1 is 3.

Example 2:

1
2
3
4

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself
             according to the LCA definition.

Note:

• All of the nodes’ values will be unique.
• p and q are different and both values will exist in the binary tree.

中文题目

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

1
2
3
4
5
6
7

     _______3______
    /              \
 ___5__          ___1__
/      \        /      \
6      _2       0       8
      /  \
      7   4

示例 1:

1
2
3

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

示例 2:

1
2
3

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明:

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉树中。