swift算法练习笔记

626 阅读12分钟

一、冒泡排序及优化

[TOC]

protocol SortAbleSwift {
    func sort(item:[NSNumber]) -> [NSNumber]
}

五种写法的运行结果

优化核心:过滤掉已经排好序的

最后一种优化完成后,比较10个数字,只比较了19次

class SortVC: UIViewController {

    override func viewDidLoad() {
        super.viewDidLoad()

        let array: [NSNumber] = [1, 7, 3, 5, 6, 4, 2, 8, 9, 10]
        print("source = \(array)\n")
        do {
            let bubulle: BubbleSwift0 = BubbleSwift0.init()
            let result = bubulle.sort(item: array)
            print("result = \(result)\n")
        }
        do {
            let bubulle: BubbleSwift1 = BubbleSwift1.init()
            let result = bubulle.sort(item: array)
            print("result = \(result)\n")
        }
        do {
            let bubulle: BubbleSwift2 = BubbleSwift2.init()
            let result = bubulle.sort(item: array)
            print("result = \(result)\n")
        }
        do {
            let bubulle: BubbleSwift3 = BubbleSwift3.init()
            let result = bubulle.sort(item: array)
            print("result = \(result)\n")
        }
        do {
            let bubulle: BubbleSwift4 = BubbleSwift4.init()
            let result = bubulle.sort(item: array)
            print("result = \(result)\n")
        }
    }
}

一:最先想到的(效率最低)

class BubbleSwift0: SortAbleSwift {
    func sort(item: [NSNumber]) -> [NSNumber] {
        var swapCount: Int = 0                  // 交换次数
        var compareCount: Int = 0               // 比较次数
        var result = item                       // 可变数组
        let count = result.count                // 数组长度
        for _ in 0..<count {
            for j in 0..<count-1 {
                compareCount = compareCount + 1
                if result[j].intValue > result[j+1].intValue {
                    result.swapAt(j, j+1)
                    swapCount = swapCount + 1
                }
            }
        }
        print("比较次数 = \(compareCount) 交换次数 = \(swapCount)")
        return result
    }
}

二:对每趟比较次数做优化

class BubbleSwift1: SortAbleSwift {
    func sort(item: [NSNumber]) -> [NSNumber] {
        var swapCount: Int = 0                  // 交换次数
        var compareCount: Int = 0               // 比较次数
        var result = item                       // 可变数组
        let count = result.count                // 数组长度
        for i in 0..<count {
            for j in 0..<count-i-1 {
                compareCount = compareCount + 1
                if result[j].intValue > result[j+1].intValue {
                    result.swapAt(j, j+1)
                    swapCount = swapCount + 1
                }
            }
        }
        print("比较次数 = \(compareCount) 交换次数 = \(swapCount)")
        return result
    }
}

三:对(整体)已经排好序的做优化

class BubbleSwift2: SortAbleSwift {
    func sort(item: [NSNumber]) -> [NSNumber] {
        var swapCount: Int = 0                  // 交换次数
        var compareCount: Int = 0               // 比较次数
        var result = item                       // 可变数组
        let count = result.count                // 数组长度
        for i in 0..<count {
            var isOrderly: Bool = true          // 是否已经排好序
            for j in 0..<count-i-1 {
                compareCount = compareCount + 1
                if result[j].intValue > result[j+1].intValue {
                    result.swapAt(j, j+1)
                    swapCount = swapCount + 1
                    isOrderly = false
                }
            }
            if isOrderly { break }
        }
        print("比较次数 = \(compareCount) 交换次数 = \(swapCount)")
        return result
    }
}

四:对(右半部分)已经排好序的做优化

class BubbleSwift3: SortAbleSwift {
    func sort(item: [NSNumber]) -> [NSNumber] {
        var swapCount: Int = 0                  // 交换次数
        var compareCount: Int = 0               // 比较次数
        var result = item                       // 可变数组
        let count = result.count                // 数组长度
        var lastPosition: Int = count - 1       // (向右上浮最大值)最后一次的交换位置
        for _ in 0..<count {
            var isOrderly: Bool = true          // 是否已经排好序
            var lastSwap: Int = 0
            for j in 0..<lastPosition {
                compareCount = compareCount + 1
                if result[j].intValue > result[j+1].intValue {
                    result.swapAt(j, j+1)
                    swapCount = swapCount + 1
                    isOrderly = false
                    lastSwap = j
                }
            }
            if isOrderly { break }
            lastPosition = lastSwap
        }
        print("比较次数 = \(compareCount) 交换次数 = \(swapCount)")
        return result
    }
}

五:对(左半部分 + 右半部分)已经排好序的做优化

class BubbleSwift4: SortAbleSwift {
    func sort(item: [NSNumber]) -> [NSNumber] {
        var swapCount: Int = 0                      // 交换次数
        var compareCount: Int = 0                   // 比较次数
        var result = item                           // 可变数组
        let count = result.count                    // 数组长度
        var orderlyMaxPosition: Int = count - 1     // (向右上浮最大值)最后一次的交换位置
        var orderlyMinPosition: Int = 0             // (向左下沉最小值)最后一次的交换位置
        for _ in 0..<count {
            var isOrderly: Bool = true              // 是否已经排好序
            var orderlyMaxSwapPosition: Int = 0     // 有效的最大交换位置(后面的已经排好序)
            var orderlyMinSwapPosition: Int = 0     // 有效的最小交换位置(前面的已经排好序)
            // 向右寻上浮大值
            do {
                var j: Int = orderlyMinPosition
                while j < orderlyMaxPosition {
                    compareCount = compareCount + 1
                    if result[j].intValue > result[j+1].intValue {
                        result.swapAt(j, j+1)
                        swapCount = swapCount + 1
                        orderlyMaxSwapPosition = j
                        isOrderly = false
                    }
                    j=j+1
                }
            }
            if isOrderly { break }
            orderlyMaxPosition = orderlyMaxSwapPosition

            // 向左下沉最小值
            do {
                var j: Int = orderlyMaxPosition
                while j > orderlyMinPosition {
                    compareCount = compareCount + 1
                    if result[j-1].intValue > result[j].intValue {
                        result.swapAt(j-1, j)
                        swapCount = swapCount + 1
                        orderlyMinSwapPosition = j
                        isOrderly = false
                    }
                    j=j-1
                }
            }
            if isOrderly { break }
            orderlyMinPosition = orderlyMinSwapPosition
        }
        print("比较次数 = \(compareCount) 交换次数 = \(swapCount)")
        return result
    }
}

参考博客

【排序】:冒泡排序以及三种优化

二、五个常用算法中的贪心算法

swift技能点练习

五大常用算法

  • 贪心案例一:会议安排

  • 贪心案例二:零钱支付

  • 贪心案例三:过河问题

验证结果

swift技能点练习

  • Arraysort使用
  • Arrayreduce函数使用
  • tuple的使用
  • struct的使用
  • class的使用
  • Swift中的高阶函数

五大常用算法

  • 1、分治算法
  • 2、动态规划算法
  • 3、贪心算法
  • 4、回溯法
  • 5、分支界限法

贪心案例一:会议安排

问题描述:

只有一间会议室,在有限时间内(一天)安排最多的会议(不能冲突,两个会议不能同时进行)

方案一: (非最优)每次选择持续时长最短的会议,但是有可能持续时长最短的结束时间最晚

方案二: (非最优)每次选择开始时间最早的会议,但是有可能开始时间最早的持续时长对长

方案三: (最优)每次选择开始时间最早&持续时间最短的会议,也就是结束时间最早的会议,这是最优策略,可以安排更多的会议

struct Meeting {
    var number: Int = 0     // 会议编号
    var begin: Int = 0      // 会议开始时间
    var end: Int = 0        // 会议结束时间
}

class ArrangeMeeting {
    /// 随机创建count个会议
    ///
    /// - Parameter count: 会议数量
    class func createRandomMeetings(count: Int) -> [Meeting] {
        var meetings:[Meeting] = []
        for idx in 0..<count {
            var meeting: Meeting = Meeting.init()
            meeting.number = idx
            meeting.begin = Int(arc4random()%100)
            meeting.end = meeting.begin + Int(arc4random()%100)
            meetings.append(meeting)
        }
        return meetings
    }
    
    /// 从给定的会议数组中选出期望的会议数组
    ///
    /// - Parameter meetingIn: 给定的会议数组
    /// - Returns: 期望的会议数组
    class func getExpectMeetings(meetingIn: [Meeting]) -> [Meeting] {
        var meetings: [Meeting] = meetingIn
        // 存储符合条件的会议的数组
        var expectMeetings: [Meeting] = []
        // 第一步:将所有会议按照结束时间从小到大排序
        meetings.sort { (c1, c2) -> Bool in
            return c1.end < c2.end
        }
        // 第二步:添加符合条件的会议到数组中
        for var idx in 0..<meetings.count {
            if idx == 0 {
                expectMeetings.append(meetings[idx])
                continue
            }
            // 找到第一个开始时间比上一次会议结束时间晚的会议
            var goal: (duration: Int, idx: Int) = (0, 0)
            if meetings[idx].begin >= expectMeetings.last!.end {
                goal.duration = meetings[idx].end - meetings[idx].begin
                goal.idx = idx
            }
            // 获取开始时间相同 && 持续时间最短的会议
            while((idx+1 < meetings.count) && (meetings[idx].begin == meetings[idx+1].begin)) {
                idx = idx+1
                let curDuration: Int = meetings[idx].end - meetings[idx].begin
                if curDuration < goal.duration {
                    goal.duration = curDuration
                    goal.idx = idx
                }
            }
            if goal.duration > 0 {
                expectMeetings.append(meetings[goal.idx])
            }
        }
        return expectMeetings
    }
}

贪心案例二:零钱支付

问题描述:

有1元硬币、2元硬币、5元硬币、10元硬币,每一种有若干个,从中选择几种组合支付N元,找出话费硬币个数最少的支付方案

这种场景可能没有结果,比如所有硬币用完,但是还没有达到支付总额

方案一: (非最优解)只选择币值最大的,行不通,没法解决比最大值小的场景,而且还有币种个数限制

方案二: (非最优解)只选择币值最小的,行不通,最后结果不可能是最少的,而且还有币种个数限制

方案三: (最优解)优先选择币值最大的优先支付,然后依次选择次大的币值优先支付...

struct Coin {
    var value: Int = 0
    var count: Int = 0
}

class PayWithCoin {
    class func payCase1(amount: Int) -> [Coin] {
        var payCoins: [Coin] = []
        let ownedCoins: [Coin] = [Coin.init(value: 10, count: 10),
                                  Coin.init(value: 5, count: 5),
                                  Coin.init(value: 2, count: 1),
                                  Coin.init(value: 1, count: 10)]
        // 通过reduce函数计算出手中的硬币能够支付的最大额度
        let maxAmount = ownedCoins.reduce(0, { result, obj in
            result + obj.count * obj.value
        })
        if amount > maxAmount {
            // 超出最大支付额度
            return []
        }
        var amountWillPay: Int = amount
        for idx in 0..<ownedCoins.count {
            if amountWillPay >= ownedCoins[idx].value {
                // 当前币种消耗的个数
                let value = ownedCoins[idx].value
                let count = ownedCoins[idx].count
                // 使用该币种支付全部需要 needCount 个
                let needCount = amountWillPay / value
                // 如果该币种能够支付,并且有剩余,或者正好能够支付
                if needCount <= count {
                    // 剩余需要消耗的金额
                    let surplus = amountWillPay % value
                    amountWillPay = surplus
                    let coin: Coin = Coin.init(value: value, count: needCount)
                    payCoins.append(coin)
                }
                // 如果该币种不能够支付,自己可以支付的部分
                else {
                    // 剩余需要消耗的金额
                    let surplus = amountWillPay - value * count
                    amountWillPay = surplus
                    let coin: Coin = Coin.init(value: value, count: count)
                    payCoins.append(coin)
                }
                if amountWillPay <= 0 {
                    break
                }
            }
        }
        return payCoins
    }
}

贪心案例三:过河问题

问题:

n个人过河,船每次最多只能坐两个人,船载每个人过河的所需时间不同,问最快的过河时间。

最优方案:

如果n >= 4time = t[1] + t[0] + t[n-1] + t[1]

主旋律: 最快的人,次最快的人...次最慢的人,最慢的人

步调: 把最快的人和次最快的人,送完次最慢的人和最慢的人,称为一次基本循环 . . . 如果 n = 3time = t[1] + t[0] + t[2]

如果 n = 2time = t[1]

如果 n = 1time = t[0]

struct Crosser {
    var timeConsuming: Int = 0
}

class CrossRiver {
    
    /// 随机创建count个过河的人,每个人的过河时间随机
    ///
    /// - Parameter count: 过河的人的数量
    /// - Returns: 所有过河的人
    class func createRandomCrossers(count: Int) -> [Crosser] {
        var crossers: [Crosser] = []
        for _ in 0..<count {
            let crosser: Crosser = Crosser.init(timeConsuming: Int(arc4random()%10))
            crossers.append(crosser)
        }
        return crossers
    }
    
    /// 获取所有人过河所需要的最短时间
    ///
    /// - Parameter corssers: 所有过河的人
    /// - Returns: 最短的过河时间
    class func getMinimumTimeConsuming(corssers: [Crosser]) -> Int {
        var leftCrosser: [Crosser] = corssers
        // 对所有过河的人排序(规则 = 最快的人排在最前面,最慢的人排在最后面)
        leftCrosser.sort { (c1, c2) -> Bool in
            return c1.timeConsuming < c2.timeConsuming
        }
        var totalTimeConsuming: Int = 0
        while leftCrosser.count > 0 {
            if leftCrosser.count == 1 {
                totalTimeConsuming = totalTimeConsuming + leftCrosser[0].timeConsuming
                // 移除掉已经过河的人
                leftCrosser.removeFirst()
            }
            else if leftCrosser.count == 2 {
                totalTimeConsuming = totalTimeConsuming + leftCrosser[1].timeConsuming
                // 移除掉已经过河的人
                leftCrosser.removeFirst()
                leftCrosser.removeFirst()
            }
            else if leftCrosser.count == 3 {
                totalTimeConsuming = totalTimeConsuming +
                    leftCrosser[1].timeConsuming +
                    leftCrosser[0].timeConsuming +
                    leftCrosser[2].timeConsuming
                // 移除掉已经过河的人
                leftCrosser.removeFirst()
                leftCrosser.removeFirst()
                leftCrosser.removeFirst()
            }
            else {
                // 最快的和次最快的过去,最快的回来;最慢的和次最慢的过去,次最快的回来。
                totalTimeConsuming = totalTimeConsuming +
                    leftCrosser[1].timeConsuming +
                    leftCrosser[0].timeConsuming +
                    leftCrosser[leftCrosser.count-1].timeConsuming +
                    leftCrosser[1].timeConsuming
                // 移除掉已经过河的人
                leftCrosser.removeLast()
                leftCrosser.removeLast()
            }
        }
        return totalTimeConsuming
    }
}

验证结果

class GreedyAlgorithmVC: UIViewController {
    override func viewDidLoad() {
        super.viewDidLoad()
        
        // 会议安排问题
        do {
            let allMeetings: [Meeting] = ArrangeMeeting.createRandomMeetings(count: 10)
            let expectMeetings: [Meeting] = ArrangeMeeting.getExpectMeetings(meetingIn: allMeetings)
            print("expectMeetings = \(expectMeetings)")
        }
        // 零钱支付问题
        do {
            let payCoins: [Coin] = PayWithCoin.pay(amount: 101)
            print("payCoins = \(payCoins)")
        }
        // 过河问题
        do {
            // 网上四人过河的例子
            do {
                let leftCrosser: [Crosser] = [Crosser.init(timeConsuming: 5),
                                              Crosser.init(timeConsuming: 2),
                                              Crosser.init(timeConsuming: 1),
                                              Crosser.init(timeConsuming: 10)]
                let timerConsuming: Int = CrossRiver.getMinimumTimeConsuming(corssers: leftCrosser)
                print("timerConsuming = \(timerConsuming)")
            }
            // 通用的例子(随机创建n个过河的人,每个人的过河时间也随机)
            do {
                let crossers: [Crosser] = CrossRiver.createRandomCrossers(count: 10)
                let timerConsuming: Int = CrossRiver.getMinimumTimeConsuming(corssers: crossers)
                print("timerConsuming = \(timerConsuming)")
            }
        }
    }
}

三、查找指定字符串中第一个只出现一次的字符

思路:

第一步:遍历字符串,使用字典保存字符出现的个数,key为字符,value为出现的次数

第二步:再次遍历字符串,记录遍历的下标,如果字符对应的个数==1,则返回该字符和对应的下标

/// 【剑指Offer】第一个只出现一次的字符位置
///
/// - Parameter src: 传入的字符串
/// - Returns: 由字符和下标组成的元组(Int, Character),如果下标 index = -1,表示没有找到
func firstNotRepeatingChar(src: String) -> (Int, Character) {
    var mapCount: [Character:Int] = [:]
    for case let ch in src {
        mapCount[ch] = (mapCount[ch] ?? 0) + 1;
    }
    var index: Int = 0
    for case let ch in src {
        if let count = mapCount[ch] {
            if count == 1 {
                return (index, ch)
            }
        }
        index = index + 1
    }
    return (-1, Character.init("0"))
}

思路2: (ASCII码对照表)[ascii.911cha.com/]

第一步:每个字符的最大值为126,创建一个长度为126的数组,遍历字符串用字符对应的ASCII码对应的下标对应数组中的值保存字符个数

第二步:同思路一,再次遍历字符串,记录遍历的下标,如果字符对应的个数==1,则返回该字符和对应的下标

四、实现在字符串中找出连续最长的字符串

思路:

  • 从头开始遍历字符串,记录连续字符开始位置index和个数count
  • 使用元组curData记录当前的连续字符串的下标index和个数count
  • 使用元组resultData记录count最大的连续字符串的下标index和个数count
  • curData记录下一个或者字符串遍历完毕的时候,取curDataresultDatacount最大的元组保存到resultData
  • 最后resultData中保存的是目标字符串的开始位置和个数
import UIKit
class ArithmeticTest: NSObject {
    /// 找出给定字符串中连续最长的字符串(满足一定条件)
    ///
    /// - Parameters:
    ///   - str: 源字符串
    ///   - range: 条件
    /// - Returns: 目标字符串
    func findMaxCountNumberStr(str: String, range:ClosedRange<Int>) -> String {
        guard str.count > 0 else {
            return ""
        }
        var curData = (index:0, count:0)        // 记录(当前)连续字符串的开始位置index和个数count
        var resultData = (index:0, count:0)     // 记录(结果)连续字符串的开始位置index和个数count
        var curIndex: Int = 0
        while curIndex+1 < str.count {
            curData.count = 1
            curData.index = curIndex
            while curIndex+1 < str.count, range.contains(str[curIndex]?.int() ?? -1), str[curIndex]?.int() == str[curIndex+1]?.int() {
                curData.count = curData.count + 1
                curIndex = curIndex + 1
            }
            if curData.count > resultData.count {
                resultData.count = curData.count
                resultData.index = curData.index
            }
            curIndex = curIndex + 1
        }
        let resultStr: String = str[resultData.index..<(resultData.index+resultData.count)]
        return resultStr
    }
}

extension Character {
    func int() -> Int {
        var intFromCharacter:Int = 0
        for scalar in String(self).unicodeScalars {
            intFromCharacter = Int(scalar.value)
        }
        return intFromCharacter
    }
}

extension String {
    subscript (i: Int) -> Character? {
        guard i < self.count else{
            return nil
        }
        return self[self.index(self.startIndex, offsetBy: i)]
    }
    subscript (i: Int) -> String? {
        if let char: Character = self[i] {
            return String(char)
        }
        return nil
    }
    subscript (r: Range<Int>) -> String {
        let start = index(startIndex, offsetBy: r.lowerBound)
        let end = index(startIndex, offsetBy: r.upperBound)
        return String(self[start..<end])
    }
    subscript (r: ClosedRange<Int>) -> String {
        let start = index(startIndex, offsetBy: r.lowerBound)
        let end = index(startIndex, offsetBy: r.upperBound)
        return String(self[start...end])
    }
}

参考资料

[编程题]第一个只出现一次的字符

五、快速排序OC实现:

/**
 测试代码
 */
- (void)viewDidLoad {
    [super viewDidLoad];
    
    NSMutableArray* array = [NSMutableArray array];
    [array addObject:@10];
    [array addObject:@5];
    [array addObject:@12];
    [array addObject:@1];
    [array addObject:@45];
    [self quickSort:array left:0 right:array.count-1];
    NSLog(@"array = %@", array);
}

/**
 交换数组中的两个下标位置的值

 @param arr 数组
 @param x x下标
 @param y y下标
 */
- (void)swaparr:(NSMutableArray<NSNumber*>*)arr x:(NSInteger)x y:(NSInteger)y {
    NSInteger temp = arr[x].integerValue;    
    [arr replaceObjectAtIndex:x withObject:@(arr[y].integerValue)];
    [arr replaceObjectAtIndex:y withObject:@(temp)];
}

/**
 快速排序算法
 */
- (void)quickSort:(NSMutableArray<NSNumber*>*)arr left:(NSInteger)left right:(NSInteger)right {
    if (arr.count <= 0) {
        return;
    }
    
    // 递归退出条件
    if (left >= right) {
        return;
    }
    
    // 选取左值为参考对象
    NSInteger pivot = arr[left].integerValue;
    NSInteger i = left, j = right;
    while (i < j) {
        // j 向左移动,直到arr[j] <= pivot
        while (arr[j].integerValue >= pivot && i < j) {
            j--;
        }
        // i 向右移动,直到arr[i] >= pivot
        while (arr[i].integerValue <= pivot && i < j) {
            i++;
        }
        // 交换arr[i] 和 arr[j]的值
        if (i < j) {
            [self swaparr:arr x:i y:j];
        }
    }
    // 交换 pivot 和 arr[i] 的值
    [self swaparr:arr x:left y:i];
    
    // 递归pivot左侧的数组
    [self quickSort:arr left:left right:i-1];
    // 递归pivot右侧的数组
    [self quickSort:arr left:i+1 right:right];
}