ecc算法 swift
2019-05-06 21:00:43 lin1109221208 阅读数 25

题目描述:

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

1、粗暴的方法

每次选中一个数,然后遍历整个数组,判断是否有另一个数使两者之和为target

时间复杂度:O(n^2)

 

2、利用集合可以优化时间复杂度

思路:在遍历数组的过程中,用集合每次保存当前值。假如集合中已经有一个数等于目标值减去当前当前值,则证明在之前的遍历中一定有一个数与当前值之和等于目标值

时间复杂度:O(n)

具体实现:

func twoSum(mums:[Int], _ target:Int)->Bool{
    var set = Set<Int>()
    for num in nuns{
        if set.contains(target-num){
            return true
        }
        
        set.insert(num)
    }
    return false
}

3、题目变形

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

思路:算法思路与2类似,但是为了方便得到序列号,使用字典

时间复杂度:O(n)

具体实现:

func twoSum(nums : [Int], target : Int)->[Int]{
    var dict = [Int : Int]

    for(i,num) in nums.enumerated(){
        if let lastIndex = dict[target-num]{
            return [lastIndex,i]
        }else{
            dict[num]=i
        }
    }
    fatalError("no valid output!")
}

 

2017-08-02 17:13:00 weixin_33923148 阅读数 7
2017-10-25 19:59:59 qq_40691827 阅读数 154

编写一个程序,能交换两个变量的数值
例如: 变量a值为20,变量b值为30,调用函数后,a的值变为30,b 的值变为20

答案:   -func swap(a: inout Int , b:inout Int){
            let temp = a
             a = b
            b = temp
        }
        var x = 20 , y = 30
        swap(a:&x , b:&y)
        print(x,y)

编写一个程序,求1! + 2! + 3! + 4!的和
要求:使用嵌套定义函数实现

答案: func getSum(number: Int) -> Int {
    //求某个数阶乘的结果
    func getFactorIal(num: Int) -> Int {
        var sum = 1
        for _ in 1...num {
            sum += 1
        }
        return sum
    }
    var total = 0
    for item in 1...number {
        total += getFactorIal(num: item)
    }
    return total
}
print(getSum(number: 3))

古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少?

答案:func getFinboNum(num: Int) ->Int{
            if num == 1 || num == 2 {
             return 1
            }
        return (getFinboNum(num: num - 1) + getFinboNum(num: num - 2))
}
for month in 1...10{
    print("\(month):\(getFinboNum(num: month))")
}

打印出所有的“水仙花数”,所谓“水仙花数”是指一个三位数,其各位数字立方和等于该数本身。例如:153是一个“水仙花数”,因为153=1的三次方+5的三次方+3的三次方

答案 :for number in 100...999{
    var hunder = number / 100
    var ten = number / 10 % 10
    var num = number % 10
   let sum = pow(Decimal(hunder), 3) + pow(Decimal(ten), 3) +  pow(Decimal(num), 3)
    if sum == Decimal(number){
        print(number)
    }
}   

编写一个程序,要求可以把一个字符串中的每一个字符,如果是大
写字母变小写字母,如果是小写字母变大写,如果是其他字符不变
例如: 字符串China23beiJing 经过程序转换为cHINA23BEIjING

答案:
/*
 函数,将大写字母变小写,小写字母变大写,其他不变
 */
func changeCharcter (chNum:Character) -> Character {
    //将字符转成整数

    var chStr = String(chNum)   //将字符转成字符串
    var num:UInt32 = 0  //用于接受字符整数值的变量
    for item in chStr.unicodeScalars {
        num = item.value    //循环只执行一次,获取字符的整数的值

    }
    /*
     如果是大小写字母,转换数值
     */
    //如果是大写字母
    if num >= 65 && num <= 90 {
        num += 32
    }
        //如果是小写字母
    else if num >= 97 && num <= 122 {
        num -= 32
    }
    /*
     将整数转换为字符
     */
    let newChNum = Character(UnicodeScalar(num)!)
    return newChNum

}
var str = "China23beiJing "
var i = 0   //表示偏移量(循环变量初始值)
while i < str.characters.count {    //循环条件,包含循环变量的终止值
    var str1 = str[str.index(str.startIndex, offsetBy: i)]
//    str1 = changeCharcter(chNum: str1)

    str.replaceSubrange(str.index(str.startIndex, offsetBy:
        i)...str.index(str.startIndex, offsetBy: i),
                           with: String(changeCharcter(chNum: str1)))
    i+=1;   //循环变量值变化
}
print(str)

编写一个程序,要求接收一个数字,程序会将这个数字以二进制方
式打印,例如:数字10 , 以1010的方式打印出来

答案 :
    func binaryPrintIntNumber(num : Int) {

    var remainderArr:[Int] = []  //int数组,存储余数
    var quotient:Int = num  //表示商的变量,初始值是num
    while quotient > 0 {   //商的值是0
        let remainderNum = quotient % 2 //获取余数的值
        remainderArr.insert(remainderNum, at: 0)    //插入数组
        quotient /= 2   //商变换
    }
    for item in remainderArr {
        print(item, terminator: "")
    }
    print("")
}

var a = 10
binaryPrintIntNumber(num: a)
print(a)

编写一个程序,判断101-200之间有多少个素数,并输出所有素数

答案:
    var isPreimNum = true   //判断是否是素数,是就是true不是就是false
var sum = 0
for item in 101...200 {     //遍历101到200中的任意数
    for j in 2..<item {     //判断item是不是素数
        if item % j == 0 {
            isPreimNum = false
            break
        }
    }
    if isPreimNum {     //如果是素数
        print(item)     //打印这个素数
        sum += 1
    }
    isPreimNum = true

}
print(sum)}

编写一个程序,查看1、2、3、4四个数字,能组成多少个互不相同且无重复数字的三位数?都是多少?

var sum1 = 0  //定义变量用于记录个数

for hudder in 1...4 {   //百位
    for ten in 1...4 {  //十位
        for num in 1...4 {  //个位
            if hudder != ten && hudder != num && ten != num {
                print(hudder*100 + ten*10 + num)
                sum1 += 1   //计算个数
            }
        }
    }
}

print(sum1)
2019-06-21 18:00:02 lin1109221208 阅读数 25

1、描述

给定一个包含 m x n 个元素的矩阵(m行,n列),请按照顺时针螺旋顺序,返回矩阵中的所有元素

例1:输入:[

                        [1, 2, 3],

                        [4, 5, 6],

                         [7, 8, 9]

                     ]

          输出:[1, 2, 3, 6, 9, 8, 7, 4 ,5]

例2:输入:[

                        [1, 2, 3, 4],

                        [5, 6, 7, 8],

                        [9, 10, 11, 12]

                     ]

          输出:[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

 

2、算法

解法一:模拟

思路:绘制螺旋轨迹路径,我们发现当路径超出界限或者进入之前访问过的单元格时,会顺时针旋转方向。

 步骤:

1)假设数组有R 行C 列,seen[r][c] 表示第 r 行第 c 列的单元格之前已经被访问过了。

2)当前所在位置为(r, c),前进方向是di。我们希望访问所有R xC 个单元格。

 3)当我们遍历整个矩阵,下一步候选移动位置是(cr, cc)。

4)如果这个候选位置在矩阵范围内并且没有被访问过,那么它将会变成下一步移动的位置;否则,我们将前进方向顺时针旋转之后再计算下一步的移动位置。

时间复杂度:O(n)

func spiralOrder(_ matrix: [[Int]]) -> [Int] {
        var ans : [Int] = [Int]()
        if matrix.count == 0 {
            return ans
        }
        let R = matrix.count
        let C = matrix[0].count
        var seen : [[Bool]] = [[Bool]].init(repeating: [Bool].init(repeating: false, count: C), count: R)
        
        var dr = [0, 1, 0, -1]
        var dc = [1, 0, -1, 0]
        
        var r = 0, c = 0, di = 0
        
        for i in 0..<R*C {
            ans.append(matrix[r][c])
            seen[r][c] = true
            let cr = r + dr[di]
            let cc = c+dc[di]
            if 0<=cr && cr<R && 0<=cc && cc<C && !seen[cr][cc]{
                r = cr
                c = cc
            }else{
                di = (di+1)%4
                r += dr[di]
                c += dc[di]
            }
        }
        return ans
    }

解法二:按层模拟O(n)

思路:答案是最外层所有元素按照顺时针顺序输出,其次是次外层,以此类推。

步骤:

1)我们定义矩阵的第 k 层是到最近边界距离为 k 的所有顶点。例如,下图矩阵最外层元素都是第 1 层,次外层元素都是第 2 层,然后是第 3 层的。
2) 对于每层,我们从左上方开始以顺时针的顺序遍历所有元素,假设当前层左上角坐标是(r1, c1),右下角坐标是(r2, c2)。
3)首先,遍历上方的所有元素(r1, c),按照c = c1,...,c2 的顺序。

4)然后遍历右侧的所有元素(r, c2),按照r = r1+1,...,r2 的顺序。

5)如果这一层有四条边(也就是r1 < r2 并且c1 < c2 ),我们以下图所示的方式遍历下方的元素和左侧的元素。

时间复杂度:O(n)

func spiralOrder(_ matrix: [[Int]]) -> [Int] {
         
        var ans : [Int] = [Int]()
        if matrix.count == 0 {
            return ans
        }
        var r1 = 0, r2 = matrix.count-1
        var c1 = 0, c2 = matrix[0].count-1
        
        while r1<=r2 && c1<=c2 {
            //第一行的数 top
            for c in c1...c2 {
                ans.append(matrix[r1][c])
            }
            //最右边除了第一行的所有最后一个数 right
            var r = r1+1
            while r <= r2 {
                ans.append(matrix[r][c2])
                r += 1
            }
            //下边及左边最外层数
            if r1<r2 && c1<c2 {
                //bottom
                var c = c2-1
                while c > c1 {
                    ans.append(matrix[r2][c])
                    c -= 1
                }
                //left
                var r = r2
                while r>r1{
                    ans.append(matrix[r][c1])
                    r -= 1
                }
            }
            r1 += 1
            r2 -= 1
            c1 += 1
            c2 -= 1
        }
        
        return ans
    }

解法三:从外向内遍历

思路:从外部向内部逐层遍历打印矩阵,最外面一圈打印完,里面仍然是一个矩阵

第i层矩阵的打印,需要经历4个循环

         从左到右

         从上倒下

         从右往左,如果这一层只有1行,那么第一个循环已经将该行打印了,这里就不需要打印了,即 (m-1-i )!= i

         从下往上,如果这一层只有1列,那么第2个循环已经将该列打印了,这里不需要打印,即(n-1-i) != i

func spiralOrder(_ matrix: [[Int]]) -> [Int] {
        var ans : [Int] = [Int]()
        if matrix.count == 0 {
            return ans
        }
        let m = matrix.count
        let n = matrix[0].count
        var i = 0
        
        //统计矩阵从外向内的层数,如果矩阵为空,那么它的层数至少是1层
        let count = (min(m, n)+1)/2
        //从外部向内部遍历,逐层打印数据
        while i<count {
            //从左到右
            for j in i..<n-i {
                ans.append(matrix[i][j])
            }
            //从上到下
            for j in i+1..<m-i{
                ans.append(matrix[j][(n-1)-i])
            }
            
            //从右往左,如果这一层只有1行,那么第一个循环已经将该行打印了,这里就不需要打印了,即 (m-1-i )!= i
            var j = (n-1)-(i+1)
            while j >= i && (m-1-i != i){
                ans.append(matrix[m-1-i][j])
                j -= 1
            }
            
            //从下往上,如果这一层只有1列,那么第2个循环已经将该列打印了,这里不需要打印,即(n-1-i) != i
            var k = (m-1)-(i+1)
            while k>=i+1 && (n-1-i != i){
                ans.append(matrix[k][i])
                k -= 1
            }
            
            i += 1
        }
        
        return ans
    }

 

2019-05-17 09:57:08 lin1109221208 阅读数 8

描述:判断一个整数是否是回文数,回文数是指正序(从左往右)和倒序(从右往左)读都是一样的整数

例1:输入:121

          输出:true

例2:输入:-121

          输出:false

           解释:从左往右读 为 -121,从右往左读 为 121-,所以不是一个回文数

例3:输入:10

           输出:false

           解释:从右往左读 为 01,不是一个回文数

 

解法一:利用字符串

思路:将整数转换为字符串,然后将字符串反转,并判断反转后的字符串是否与原字符串相等,相等则是回文数,反之不是

具体实现:

//判断一个整数是否是回文数(从左往右读 == 从右往左读)
func isPalindrome(_ x: Int) -> Bool {
        var original = String(x)
        var new : String! = ""
        for c in original {
            new = String(c) + new
        }

        if  new == original {
            return true
        }else {
            return false
        }
}

 

进阶:不用字符串方式解决

解法二:反转整个整数

思路:将整数全部反转,判断反转后是否与原整数一致

具体实现:

func isPalindrome(_ x: Int) -> Bool {
        
        //用反转后的整数比较
        var y = x //用y记住原始值
        var res : Int  = 0 //用于存储反转后的类型

        while y > 0 {
            res = res*10 + y%10
            y = y/10
        }
        if res == x {
            return true
        }
        return false
}

 

解法三:反转一半整数

思路:反转一半的整数,判断是否与后面位数的整数相等

如何知道反转数字的位数达到了整数的一半?

答:我们将原始数字除以 10,然后给反转后的数字乘上 10,所以,当原始数字小于反转后的数字时,就意味着我们已经处理了一半位数的数字。

具体实现:

func isPalindrome(_ x: Int) -> Bool {
        // 特殊情况:
        // 如上所述,当 x < 0 时,x 不是回文数。
        // 同样地,如果数字的最后一位是 0,为了使该数字为回文,
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if x < 0 || (x%10==0 && x != 0) {
            return false
        }
        var s = x
        var res = 0
        //我们将原始数字除以 10,然后给反转后的数字乘上 10,所以,当原始数字小于反转后的数字时,就意味着我们已经处理了一半位数的数字。
        while s > res {
            res = res*10+s%10
            s /= 10
        }

        // 当数字长度为奇数时,我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如,当输入为 12321 时,在 while 循环的末尾我们可以得到 x = 12,revertedNumber = 123,
        // 由于处于中位的数字不影响回文(它总是与自己相等),所以我们可以简单地将其去除。
        return s==res || s==res/10
    }

 

swift算法:子集

阅读数 36

没有更多推荐了,返回首页