Swift的集合有两种,是数组和字典,显式声明和隐式声明、增删改查、基本操作等将在本文介绍。

/**

 *数组的初始化

 */

//数组只能存同一种数据类型

var array = ["a", "b", "c"]

array[0] = "A"

//显式的声明存储字符串的数组

var array2:[String] = ["a", "b", "c"]

var array3:Array<String> = ["a", "b", "c"]

//创建空数组,存储Int类型

var array4 = [Int]()

var array5 = Array<String>()

var array6:[Int] = []

var array7:Array<Int> = []

//清空数组,清空后,后期仍然只能使用之前定义的数据类型

array2 = []

array2 = [String]()

array2 = Array<String>()

//初始化,10个值,每个值都为0

var array8 = [Int](count:10, repeatedValue:0)

//数组合并

var array9 = [1, 2, 3]

var array10 = array8+array9



/**

 *数组的基本操作

 */

var array = ["A", "B", "C", "D"]

//数组的总数

array.count

//数组是否为空

array.isEmpty

//数组结尾加入新的元素

array.append("E")

array += ["F"]

array += ["G", "H"]

//数组任意位置加入新元素

array.insert("b", atIndex: 2)

//删除任意位置的元素,返回所删除的元素的值

array.removeAtIndex(1)

//删除最后一个元素

array.removeLast()

//删除所有元素

array.removeAll(keepCapacity: false)

//修改单个元素

array[0] = "AA"

//修改一组元素,若key为2...4,包含2,3,4三个key,而value只有一个,那么2,3,4三个值将只剩一个

array[2...4] = ["AA", "BB", "CC"]

array[2..<4] = ["AA", "bb"]

//遍历数组

for index in 0..<array.count{

    println("\(index) -> \(array[index])")

}

for item in array{

    println(item)

}

for (index, item) in enumerate(array){

    println("\(index) -> \(item)")

}



/**

 * 字典

 *键值对,可以是任意类型,但是一旦声明了一个字典,那么只能有一种搭配的类型。比如下面是键是Int,值是String。那么所有的键都必须是Int,所有的值都必须是String

 */

//隐式声明字典

var dictionary = [1:"a", 2:"b", 3:"c"]

//现式声明字典

var dictionary1:Dictionary<Int, String> = [1:"a", 2:"b", 3:"c"]

var dictionary2:[Int:String] = [1:"a", 2:"b", 3:"c"]

//声明空字典、清空一个已有的字典

var dictionary3 = Dictionary<Int, String>()

var dictionary4 = [Int, String]()

//清空字典的特殊表示

dictionary4 = [:]


/**

 *字典的基本操作

 */

//字典总数

var dictionary = [1:"a", 2:"b", 3:"c"]

dictionary.count

//字典是否为空

dictionary.isEmpty

//调用,传入的key可以是任意值,程序不会报错,因为返回的是optionalkey不存在时返回nil

dictionary[1]

"第一个元素:" + dictionary[1]!

//插入新元素

dictionary[4] = "d"

//修改元素两种方式

dictionary[4] = "e"

var oldValue = dictionary.updateValue("e", forKey: 4)

//删除元素两种方式

dictionary[4] = nil

var oldValue4 = dictionary.removeValueForKey(4)

//字典的遍历

for (key, value) in dictionary{

    println("\(key) -> \(value)")

}

//遍历key

Array(dictionary.keys)

[Int](dictionary.keys)

//遍历value

Array(dictionary.values)

[String](dictionary.values)

    堆是一种特殊的完全二叉树,是树的一种常见的应用,最简单的便是解决将无序的数列从大到小排列或者从小到大排列。性能极佳。

    堆分两种,一种是最大堆,即所有的父节点都大于它的两个子节点。另一种是最小堆,即所有的父节点都小于它的两个子节点。

    如果一组数列,是无序的,要将它有序的排列,那么:

min = 9999;

for(i=0; i<n; i++){

    if(num[i] < min){

        min = num[i];

    }

}

    这是最简单也是最高效的算法。可是,如果现在要删除最小数,在数列中插入一个任意一个数,此时再求最小值呢?那么就要重复上面的操作。那么问题来了,如果这个动作要重复100亿次呢?此时,时间复杂度就要100亿×数列的长度。即O(num.count*100亿)。这是不科学的,这个时候,我们引入了堆。

    最小堆的根节点永远是最小值!此时我们删掉了最小值,也就是根节点,在根节点的位置插入一个任意值,这个时候这个树就不是堆了,我们要把根节点向下移动,找到他合适的位置,也就是他要比他父节点大,比他的根节点小。此时这个树又恢复成了堆。

    现在有如下堆:

无标题.jpg


    堆的黑色数组表示节点的编号,在圈圈里。红色数组表示这个节点的值。我们现在要从小到大排列一个数列。也就是对红色数组进行排序。

    1、1号节点是根节点,永远是最小值,这是最小堆的特性。反之最大堆的根节点是最大值。

    2、将1号节点的值改变为新插入的任意值。

    3、将新插入的值向下移动,使树恢复为最小堆。和它的左子节点还有右子节点比较,若大,则交换位置。如此反复,直到不能再交换位置了。

    使用最小堆来从小到大排列一个无序数列的全部代码如下,时间复杂度为O(NLogN):

#include <stdio.h>

//存放堆

int h[100];

//存储堆的元素个数

int n;

//交换元素

void swap(int x, int y){

    int t;

    t = h[x];

    h[x] = h[y];

    h[y] = t;

}

//向下调整

void siftdown(int i){

    int t, flag=0;

    //判断该点的做儿子是否存在

    while(i*2 <= n && flag == 0){

        //如果左儿子存在,则判断是否交换值

        if(h[i] > h[i*2])

            t = i * 2;

        else

            t = i;

        //右儿子是否存在

        if(i*2+1 <= n && h[t] > h[i*2+1]){

            t = i*2+1;

        }

        //如果需要交换则交换

        if( t!= i){

            swap(t, i);

            i = t;

        //如果不需要交换,则准备退出while

        }else{

            flag = 1;

        }

    }

}

//向上调整,本函数本次将不会用到。

void siftup(int i){

    int flag = 0;

    while(i != 1 && flag == 0){

        if(h[i] < h[i/2]){

            swap(i, i/2);

            i = i/2;

        }else{

            flag = 1;

        }

    }

}

//创建堆

void create(){

    int i;

    for(i=n/2; i>=1; i--){

        siftdown(i);

    }

}

//获取最小的元素

int getMin(){

    int t;

    //堆顶(根节点)为最小值

    t = h[1];

    //删除根节点,把堆的最后一个元素赋给根节点

    h[1] = h[n];

    n--;

    //把根节点向下移动,使堆恢复最小堆

    siftdown(1);

    return t;

}

int main(){

    int i, num;

    scanf("%d", &num);

    for(i=1; i<=num; i++){

        scanf("%d", &h[i]);

    }

    n = num;

    //创建堆

    create();

    //讲堆从小到大排列

    for(i=1; i<=num; i++){

        printf("%d ", getMin());

    }

    return 0;

}


输入:

14

99 5 36 7 22 17 46 12 2 19 25 28 1 92

//输出:

1 2 5 7 12 17 19 22 25 28 36 46 92 99


    若使用最大堆,根节点就是整个数列的最大值,那么将h[1]和h[n]交换位置,此时h[n]就是最大值,然后将h[1]向下移动已恢复新的堆。此时将堆的大小减一,重复上面的操作。时间复杂度将会从O(NLogN)降低到O(NLogK)

    完整代码如下:

#include <stdio.h>

//存放堆

int h[100];

//存储堆的元素个数

int n;

//交换元素

void swap(int x, int y){

    int t;

    t = h[x];

    h[x] = h[y];

    h[y] = t;

}

//向下调整

void siftdown(int i){

    int t, flag=0;

    //判断该点的做儿子是否存在

    while(i*2 <= n && flag == 0){

        //如果左儿子存在,则判断是否交换值

        if(h[i] < h[i*2])

            t = i * 2;

        else

            t = i;

        //右儿子是否存在

        if(i*2+1 <= n && h[t] < h[i*2+1]){

            t = i*2+1;

        }

        //如果需要交换则交换

        if( t!= i){

            swap(t, i);

            i = t;

        //如果不需要交换,则准备退出while

        }else{

            flag = 1;

        }

    }

}

//创建堆

void create(){

    int i;

    for(i=n/2; i>=1; i--){

        siftdown(i);

    }

}

//从小到大排序

int minToMaxSort(){

    while(n>1){

        swap(1, n);

        n--;

        siftdown(1);

    }

}

int main(){

    int i, num;

    scanf("%d", &num);

    for(i=1; i<=num; i++){

        scanf("%d", &h[i]);

    }

    n = num;

    //创建堆

    create();

    //排序

    minToMaxSort();

    for(i=1; i<=num; i++){

        printf("%d ", h[i]);

    }

    return 0;

}

输入:

14

99 5 36 7 22 17 46 12 2 19 25 28 1 92

//输出:

1 2 5 7 12 17 19 22 25 28 36 46 92 99

Ps:本算法参考《啊哈!算法》一书。

   什么是Bellman-Ford算法?Bellman-Ford算法是一种堪称完美的解决一个点到其他各点的最短路径的算法。Bellman-Ford算法的核心代码只有4行,可以解决负权边的问题。

    Bellman-Ford算法的核心代码只有四行,如下

for(k=1; k<=n-1; k++)

    for(i=1; i<=m; i++)

        if(dis[v[i]] > dis[u[i]] + w[i])

            dis[v[i]] = dis[u[i]] + w[i];

    Bellman-Ford算法的核心代码意思是:遍历每一个点,其中每一次遍历时,遍历所有的边,对每个边进行一次松弛操作。

    松弛什么?请点击查看。算法十一:Dijkstra算法 - 一个点到各个点的最短路径

    现在有如下图,共5个点5条边,边都是有向边,其中点1到点2的距离为负数。如下:

无标题.jpg


    为什么会进行n-1次的循环呢?因为在不包含负权回路的路径中,n个点最多有n-1条边。在负权边中,负权回路会使最短路径不断的变小,永无止境。

完整代码如下:

#include <stdio.h>

int main(){

    int dis[10], i, k, m, n, u[10], v[10], w[10];

    int maxValue = 9999;

    //源点为1

    int start = 1;

    //读入点的个数n,边的个数m

    scanf("%d %d", &n, &m);

    //读入边

    for(i=1; i<=m; i++){

        scanf("%d %d %d", &u[i], &v[i], &w[i]);

    }

    //初始化dis数组。dis数组表示源点到各个点的初始距离,初始化时都为无穷大

    for(i=0; i<=n; i++){

        dis[i] = maxValue;

    }

    //源点到源点的距离为0

    dis[start] = 0;

    //Bellman-Ford算法的核心语句

    for(k=1; k<=n-1; k++){

        for(i=1; i<=m; i++){

            if(dis[v[i]] > dis[u[i]] + w[i]){

                dis[v[i]] = dis[u[i]] + w[i];

            }

        }

    }

    for(i=1; i<=n; i++){

        printf("%d ", dis[i]);

    }

    return 0;

}

输入:

5 5

2 3 2

1 2 -3

1 5 5

4 5 2

3 4 3

//输出:

0 -3 -1 2 4

    Bellman-Ford算法的时间复杂对为O(MN)。

    我们可以更加完善上面的代码。比如我们已经知道了使用Bellman-Ford算法不能包含负权回路,那么我们需要检测图中是否包含负权回路:

sign = 0

for(i=1; i<=m; i++)

    if(dis[v[i]] > dis[u[i]] + w[i])

        flag = 1;

if(sign == 1)

    printf("此图有负权回路");

    另外,在n-1轮循环中,若n-3轮已经松弛完毕,那么n-2和n-1两次循环便毫无意义,因此增加判断,若第x轮dis数组已经不再发生变化了,则不在继续进行循环。

    新版的完整代码如下:

#include <stdio.h>

int main(){

    int dis[10], i, k, m, n, u[10], v[10], w[10], sign, check;

    int maxValue = 9999;

    //源点为1

    int start = 1;

    //读入点的个数n,边的个数m

    scanf("%d %d", &n, &m);

    //读入边

    for(i=1; i<=m; i++){

        scanf("%d %d %d", &u[i], &v[i], &w[i]);

    }

    //初始化dis数组。dis数组表示源点到各个点的初始距离,初始化时都为无穷大

    for(i=0; i<=n; i++){

        dis[i] = maxValue;

    }

    //源点到源点的距离为0

    dis[start] = 0;

    //Bellman-Ford算法的核心语句

    for(k=1; k<=n-1; k++){

        //本轮dis数组是否发生变化

        ckeck = 0;

        for(i=1; i<=m; i++){

            if(dis[v[i]] > dis[u[i]] + w[i]){

                dis[v[i]] = dis[u[i]] + w[i];

                check = 1;

            }

        }

        //本轮没有发生松弛,则不再继续进行了。

        if(ckeck == 0){

            break;

        }

    }

    sign = 0

    for(i=1; i<=m; i++)

        if(dis[v[i]] > dis[u[i]] + w[i])

            sign = 1;

    if(sign == 1){

        printf("此图有负权回路");

    }else{

        for(i=1; i<=n; i++){

            printf("%d ", dis[i]);

       }

    }

    return 0;

}



    在第每一轮循环中,其实只对上一次发生了松弛的边的相邻边判断是否需要松弛,因此,没有必要每次都进行m次循环(遍历所有的边判断是否需要松弛)。比如第一轮松弛了1->2和1->5,那么第二次仅仅判断2->3和5->4这两个边是否需要松弛,而不需要遍历所有的边。

    在这种情况下,我们引入队列,将需要松弛的点加入队列。每个点仅仅需要入队一次即可,因为入队多次是没有意义的。初始时我们将1号点(源点)加入队列。然后开始遍历队列,对队列中每个点的边进行松弛。队列为空时所得结果便是一个点到其他所有点的最短路径。这是对上述的Bellman-Ford算法一种极大的优化。当然,在最坏的情况下,和Bellman-Ford算法的时间复杂度是一样的,即O(MN)。此优化也可以解决负权边。

    完整代码如下:

#include <stdio.h>

int main(){

    int dis[10] = {0}, i, j, k, m, n, u[10], v[10], w[10];

    int book[10] = {0};

    //first数组和next数组用来建立领接表,即first记录一个边的开头,比如第2号边的开头是点a,那么first[a]=2,a开头的下一个边是第5号边,则next[5]=a,组成一个链表的形式

    int first[10], next[10];

    int queue[100] = {0}, head = 1, tail = 1;

    int maxValue = 9999;

    //源点为1

    int start = 1;

    //读入点的个数n,边的个数m

    scanf("%d %d", &n, &m);

    //初始化dis数组。dis数组表示源点到各个点的初始距离,初始化时都为无穷大

    //book用来标记那个点已经入队了,因为队列中同时出现同一个点多次是没有意义。

    //first用来标记第i条边的起点

    for(i=0; i<=n; i++){

        dis[i] = maxValue;

        book[i] = 0;

        first[i] = -1;

    }

    //源点到源点的距离为0

    dis[start] = 0;

    //读入边

    for(i=1; i<=m; i++){

        scanf("%d %d %d", &u[i], &v[i], &w[i]);

        //使用first和next两个数组建立领接表

        next[i] = first[u[i]];

        first[u[i]] = i;

    }

    //源点入队

    queue[tail] = start;

    tail++;

    //标记已经入队的点

    book[i] = start;

    while(head < tail){

        //当前需要处理的点,是队首的点,处理队首开头的所有边

        k = first[queue[head]];

        //扫描这个点开头的所有边

        while( k != -1){

            if(dis[v[k]] > dis[u[k]] + w[k]){

                dis[v[k]] = dis[u[k]] + w[k];

                if(book[v[k]] == 0){

                    queue[tail] = v[k];

                    tail++;

                    book[v[k]] = 1;

                }

            }

            k = next[k];

        }

        //这个点开头的所有边都处理完了,就出队

        book[queue[head]] = 0;

        head++;

    }

    for(i=1; i<=n; i++){

        printf("%d ", dis[i]);

    }

    getchar();getchar();

    return 0;

}

输入:

5 5

2 3 2

1 2 -3

1 5 5

4 5 2

3 4 3

//输出:

0 -3 -1 2 4

Ps:本算法参考《啊哈!算法》一书。

    初探Swift之Swift字符串、字符串处理、字符串函数。Swift字符串本质是一个对象,同其他语言一样,可以使用拼接、长度、子字符串查找、子字符串替换、子字符串删除等操作。


//字符串长度,长度为5

var str_es = "swift"

countElements(str_es)

//中文字符串长度,长度为2,一个汉子为1

var str_ch = "你好"

countElements(str_ch)


//声明一个字符

let myChar:Character = "!"


//比较,同其他语言,是按照字典的顺序。与长度无关

let a = "abcd";

let b = "abd";

a == b

a > b

a < b


//字符串的前缀和后缀

let chapterNames = [

    "第一:1111",

    "第二:1111",

    "第二:1111a",

    "第二:1111",

    "第三:1111",

    "第三:1111a",

]

//前缀为第二的个数统计

var count = 0

for name in chapterNames{

    if name.hasPrefix("第二"){

        count++

    }

}

count

//后缀为“a”的个数统计

count = 0

for name in chapterNames{

    if name.hasSuffix("a"){

        count++

    }

}

count




//字符串高级操作,需要引入Foundation

import Foundation


var str = "hello WOrld";

//首字母大写

str.capitalizedString

//大写

str.uppercaseString

//小写

str.lowercaseString


//去除两边的空格

var str2 = "  hi ! "

str2.stringByTrimmingCharactersInSet(NSCharacterSet.whitespaceCharacterSet())


//字符串按照空格分割为数组,同php的explode函数

var str3 = "hello world"

str3.componentsSeparatedByString(" ")


//数组连接为字符串,同php的implode函数

var str4 = "_"

str4.join(["1","2","3"])


//查找字符串

var str = "Welcome to play Swift! Step by Step learn Swift language from now!"

str.rangeOfString("Step")

//第二个参数是枚举,可以根据Xcode的提示看到,NSStringCompareOptions.CaseInsensitiveSearch是不区分大小写

str.rangeOfString("welcome", options: NSStringCompareOptions.CaseInsensitiveSearch)


//字符串的开头位置

str.startIndex

//字符串的结束为止

str.endIndex


//Range

let strRange = Range<String.Index>(start:str.startIndex, end:str.endIndex)

//在Range范围内查找

let startIndex = str.startIndex

let endIndex:String.Index = advance(str.startIndex, 10)

let searchRange = Range<String.Index>(start:startIndex, end:endIndex)

str.rangeOfString("Step", options: NSStringCompareOptions.CaseInsensitiveSearch, range: searchRange)

//截取开头的4个字符

var toIndex = advance(str.startIndex, 4)

str.substringToIndex(toIndex)

    初探Swift,Swift变量声明,let和var分别声明常量和变量。Swift数据类型,包括整型,浮点型,字符型,布尔型,可选型等,已经强制类型转换和if选择。

//-----------变量相关----------

//常量

let maxNum = 1000

//变量

var index = 0


var a=0.0, y=0, z=0

a = 1;

a = 1.1;

//报错

//a = "a";


//显示申明类型

var test : Int

test = 10


var red, green, blue : Int

//十进制

red = 17;

//二进制,以0b开头

red =0b10001

//八进制,以0o开头

red = 0o21

//十六进制,以0x开头

red = 0x11


//科学计数法

let b = 0.012

letc =1.2e-2


//多位整数的表示法

lete =1000000

letf =1_000_000

letg =1_000_000


//自动类型转换

let h:Float = 1

//Xcode beta2会将1.2转为1,而Xcode beta3直接报错。

//let i:Int = 1.2


//强制类型转换

let j:Double = Double(h) + b


//变量名,任何unicode都可以

let 姓名 = "小明"

println(姓名 + "你好")




//----------选择-----------

let bool1 = true

let bool2:Bool = false


//即使语句块只有一行,花括号{}也不能省略,在选择里,只有truefalse10都是不可以的。

if bool1{

    println("hello");

}else if bool2{

    println("world");

}else{

    println("swift");

}




//---------元组-----------

let tuples_1 = ("小明", "", 21, true)

//元组可以赋值给变量

let (name, sex, age, status) = tuples_1

println("姓名:"+name+",性别:"+sex);

//元祖可以用.0.1.2来访问

println("姓名:"+tuples_1.0+",性别:"+tuples_1.1);


//每个元祖都赋一个key

let tuples_2 = (date:"2015-01-05", time:"16:06", author:"lane")

println("日期:"+tuples_2.date+" "+tuples_2.time+",作者:"+tuples_2.author);

println("日期:"+tuples_2.0+" "+tuples_2.1+",作者:"+tuples_2.2);


//至提取元组的第一个值,不关心后面的值

let login = (true, "小明")

let (staic, _) = login

if staic{

    println("hi");

}else{

    println("hi hi");

}

//元组的类型显示声明

let login2:(Bool, String) = (true, "小明")



//可选型optional

var optionalVar1:Int?

optionalVar1=1


let userAge = "18"

var age = userAge.toInt()


if(age != nil){

    println("You age is " + String(age!) )

}else{

   println("Invalidate userInput")

}


//解包

if let userInput = userAge.toInt(){

    println("you age is\(userInput)");

}

let m:String? = "hello";

let n:String! = "hi";