算法举例

 

一些算法举例

排序算法

首先看一张图:

sort_algorithm

这里就不多解释了,下面抽几个排序简单讲下。

成功

信息

Warning Text.

Error Text.

success info warning error

冒泡排序

  • 算法步骤

比较相邻的元素。如果第一个比第二个大,就交换他们两个。 对每一对相邻元素作同样的工作,从开始第一队到结尾的最后一对。这步做完后,最后的元素会是最大的数。 针对所有的元素重复以上的步骤,除了最后一个。 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

  • 动图演示

bubbleSort

  • 代码实现:
    func bubbleSort(arr: inout [Int]) {
        for i in 0..<arr.count-1 {
            for j in 0..<arr.count-1-i {
                if arr[j] > arr[j+1] {
                    arr.swapAt(j, j+1)
                }
            }
        }
    }

i的循环是计数用,j的循环是当次将最大的数放到最后。

插入排序

  • 算法步骤

将第一待排序的第一个元素看过一个有序序列,把第二个元素到最后一个元素当成未排序序列。 从头到位以此扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面)

  • 动图演示

由于很好理解就不放动图演示了。

  • 代码实现
    func insertSort(arr: inout [Int]) {
        for i in 1..<arr.endIndex {
            let temp = arr[i]
            for j in (0..<i).reversed() {
                if arr[j] > temp {
                    arr.swapAt(j, j+1)
                }
            }
        }
    }

快速排序

平均状况下,排序n个项目要O(nlogn)次比较。在最坏的状况下则需要O(n^2)次比较,但这种状况并不多见。事实上,快排通常明显比其他O(nlogn)算法更快一个,因为它的内部循环可以在大部分的架构上很有效率地被实现出来。 快排使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。 快速排序本质上市冒泡排序基础上的递归分治法。它是处理大数据排序最快的算法之一了。 《算法艺术与信息学竞赛》上说:

快速排序最坏的情况是O(n^2),比如顺序数列额快排。但它的平摊期望时间是O(nlogn),且O(nlogn)记号中隐含的常数因子很小,比复杂度稳定等于O(nlogn)的归并排序要小很多。所以,对绝大多数树顺序性较弱的随机数列而言,快速排序总是优于归并排序。

  • 算法步骤
  1. 从数列中挑出一个元素,称为“基准”(pivot);
  2. 重新排序数列,所有元素比基准值晓得摆放在基准面前,所有比基准大的摆在基准后面(相同的可以放到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  3. 递归的(recursive)把小于基准值的元素的子数列和大于基准值元素的子数列排序。
  • 动图演示

quickSort

  • 代码实现
    //寻找pivot的函数
    func partition(arr: inout [Int], left: Int, right: Int) -> Int {
        let pivot = left
        var index = pivot+1
        for i in index...right {
            if arr[i] < arr[pivot] {
                arr.swapAt(i, index)
                index+=1
                //i和index都更新,以pivot为分隔,两边都冒泡,后面再将假设的pivot替换为真正的pivot,然后继续递归
            }
        }
        //此处相当于pivot需要更新
        arr.swapAt(pivot, index-1)
        return index-1
    }
    
    func quickSort(arr: inout [Int], left: Int, right: Int) {
        if arr.count <= 1 {
            //nothing, live it alone
        }
        
        let left = left
        let right = right
        if left < right {
            let partitionIndex = partition(arr: &arr, left: left, right: right)
            quickSort(arr: &arr, left: left, right: partitionIndex-1)
            quickSort(arr: &arr, left: partitionIndex+1, right: right)
        }
    }

字符串

复原IP地址

给定一个只包含数字的字符串,复原它并返回所有可能的IP地址格式。

有效的IP地址正好由四个整数(0到255之间组成),整数之间用’.’分隔。

  • 示例
输入: "25525511135"
输出:["255.255.11.135", "255.255.111.35"]
  • 思路

回溯法

1、一开始,字符串的长度小于 4 或者大于 12 ,一定不能拼凑出合法的 ip 地址(这一点可以一般化到中间结点的判断中,以产生剪枝行为);

2、每一个结点可以选择截取的方法只有 3 种:截 1 位、截 2 位、截 3 位,因此每一个结点可以生长出的分支最多只有 3 条分支;

根据截取出来的字符串判断是否是合理的 ip 段,这里写法比较多,可以先截取,再转换成 int ,再判断。我采用的做法是先转成 int,是合法的 ip 段数值以后,再截取。

3、由于 ip 段最多就 4 个段,因此这棵三叉树最多 4 层,这个条件作为递归终止条件之一;

  • 解法
func restoreIpAddresses(_ s: String) -> [String] {
  //回溯法
  var res:[String]=[]
  var tmp:[String]=[]
  let chs:[Character]=[Character](s)
  backTrace(&res,&tmp,chs,0,0)
  return res
}

func backTrace(_ res:inout [String],_ tmp:inout [String],_ chs:[Character],_ ind:Int,_ has:Int){
  if ind == chs.count && has == 4{
    var str:String=""
    for i in tmp{
      str += i+"."
    }
    str.removeLast()
    res.append(str)
    return
  }
  if (has == 4 && ind < chs.count) || (ind == chs.count && has < 4){return}
  for i in ind...ind+2{
    if i >= chs.count{break}    //确保i是一个有效的下标
    if i > ind && chs[ind] == "0"{break}
    let str:String=String(chs[ind...i])
    if str.count == 3 && str > "255"{continue}  //长度为1和2的数都可以,为3的话需要筛选
    tmp.append(str)
    backTrace(&res,&tmp,chs,i+1,has+1)
    tmp.removeLast()
  }
}
  • 结果

let ress = solution.restoreIpAddresses(“25525511135”)

print(ress)

[“255.255.11.135”, “255.255.111.35”]

字符串相乘

  • 示例
输入:num1="123",num2="456"
输出:"56088"
num1,num2均不以0开头,除非是数字0本身
  • 思路

第i位和第j位相乘,结果会在第i+j上面,如果有进位,则i+j-1上也有,结果是倒序的

  • 解法

代码实现:

func multiply(_ num1: String, _ num2: String) -> String {
        if Int(num1) == 0 || Int(num2) == 0 {return "0"}
        var result = ""
        var resultArray: [Int] = [Int].init(repeatElement(0, count: num1.count+num2.count))
        //这两个for执行完,结果数组里面是未处理过进位的结果
        for i in (0..<num1.count) {
            for j in 0..<num2.count {
                let c1 = Int(String(num1[i]))!
                let c2 = Int(String(num2[j]))!
                
                let res = c1*c2
                resultArray[i+j] += res
            }
        }
        
        //处理进位
        var carrys = 0
        for i in (0..<resultArray.count).reversed() {
            if resultArray[i] == 0 {
                continue
            }
            
            let tmp = resultArray[i]+carrys
            
            carrys = tmp/10
            resultArray[i] = tmp%10
        }
        
        //最后一位如果是0,则需要舍弃
        let end = resultArray.last!==0 ? resultArray.count-1 : resultArray.count
        for i in 0..<end {
            result += String(resultArray[i])
        }
        
        return result
    }
  • 测试
print(solution.multiply("123", "3128"))
  • 结果

384744

字符串s1和s2,判断s2中是否包含s1的排列

  • 示例
输入:"abo"和"eidboammnj"
输出:true
如果是"abb"则false,字符串都是小写,长度1-10000
  • 思路

采用窗口滑动法,从开始的空窗口从左向右滑动

  • 解法

代码实现:

//保证了字符串都是小写字母,97是小写的a,65是大写的A
    func checkInclusion(_ s1: String, _ s2: String) -> Bool {
        if s1.isEmpty || s2.isEmpty {return false}
        guard s1.count <= s2.count else {
            return false
        }

        func allZero(_ counts: [Int]) -> Bool {
            for i in 0 ..< 26 {
                if counts[i] != 0 {
                    return false
                }
            }
            return true
        }

        let chars1 = Array(s1.unicodeScalars)
        let chars2 = Array(s2.unicodeScalars)
        let len1 = chars1.count
        let len2 = chars2.count
        var counts = [Int](repeatElement(0, count: 26))

        //可以简单理解有两个同时滑动的窗口,都向右滑,上面一个窗口后面会为空
        for i in 0 ..< len1 {
            //s1从右边滑进的+1,从右边滑出的-1
            counts[Int(chars1[i].value - 97)] += 1
            //s2从右边滑进的-1,从右边滑出的-1
            counts[Int(chars2[i].value - 97)] -= 1
        }

        if allZero(counts) {return true}
        
        //因为都是s2,所以只看滑进还是滑出
        for i in len1 ..< len2 {
            //从右边滑进,-1
            counts[Int(chars2[i].value - 97)] -= 1
            //从右边滑出,+1
            counts[Int(chars2[i - len1].value - 97)] += 1
            
            if allZero(counts) {return true}
        }

        //窗口的大小是短串的长度,必须要这样,否则肯定是false
        return false
    }

有一个字符串和一组子字符串,请返回覆盖率最高,单词最多的子字符串列表

示例:

字符串: abcdefg
子字符串: ((ab,0, 1), (cd, 2, 3),(efg,4, 6), (abc,0,2),(abcd, 0, 3), (cdef, 2, 5))
期望: {ab, cd, efg}
  • 分析

最长不重复子串

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例:

 输入:"adbdeacdmmm"
 输出:5
 解释:因为无重复的最长子串是"bdeac"或者"eacdm"
  • 分析

首先本体如果使用两层for循环当然可以轻松搞定,但是时间复杂度也是O(n^2),显然不是很满意,所以需要想个法子将复杂度调整到O(n)。 因为是子串,不是子序列,所以肯定是一串连续的字符区域。头设定为start,尾设定为end。那么在仅仅遍历一遍的情况下,start是会不断往后涨的,end就是当前遍历的位置。 1. 如果当前遍历的字符在start后面没有出现过,则接着遍历,start往后移 2. 如果当前遍历的字符已经出现了(这里可以使用hash表记录,key是character,value是index),则说明肯定有字符重复,需要将start移到这个重复字符处,也就是遍历的字符上一次出现的位置的下一个位置(index) 3. 在这个过程中,时刻更新最大长度

  • 解法

代码实现:

//code1
extension String {
    subscript(_ i: Int)->Character {
        get {return self[index(startIndex, offsetBy: i)]}
    }
}

code1是为了给string添加subscript操作,真正功能代码是:

    //code2
    func lengthOfLongestSubstring(_ s: String) -> (Int, String?) {
        if s.isEmpty {
            return (0, nil)
        }
        var maxLength = 0
        var start = maxLength
        
        var retString: String? = " "
        
        var hashTable: Dictionary<Character, Int> = [Character:Int]()
                
        for i in 0..<s.count {
            if hashTable.keys.contains(s[i]) && hashTable[s[i]]! >= start {
                start = hashTable[s[i]]!+1
            }
            
            hashTable[s[i]] = i
            
            maxLength = max(maxLength, i+1-start)
        }
        
        return (maxLength, retString!)
    }

当然code2实际上只是输出长度并没有输出子字符串,我们尝试着输出长度和子字符串,其实就是在code2的基础上稍微改一下:

    //code3
    func lengthOfLongestSubstring(_ s: String) -> (Int, String?) {
        if s.isEmpty {
            return (0, nil)
        }
        
        var maxLength = 0
        var start = maxLength
        
        var retString: String? = " "
        let strArray = Array(s)
        
        var hashTable: Dictionary<Character, Int> = [Character:Int]()
                
        for i in 0..<s.count {
            if hashTable.keys.contains(s[i]) && hashTable[s[i]]! >= start {
                start = hashTable[s[i]]!+1
            }
            
            hashTable[s[i]] = i
            
            //此处就是获取子串,由于会一直遍历到最后,所以如果有多个相等长度的子串,会停留在最后一个子串,返回
            if i+1-start >= maxLength {
                let subArr = strArray[start..<i+1]
                let subStr: String = subArr.map{String.init($0)}.joined()
                retString = subStr
            }
            
            maxLength = max(maxLength, i+1-start)
        }

        return (maxLength, retString!)
    }

示例代码如下:

var solution = Solution()
var turple1 = solution.lengthOfLongestSubstring("adbdeacdmmm")

print(turple1)

以“adbdeacdmmm”为例,则长度为5,子串为:”bdeac”或者”eacdm”,但是由于“eacdm”在后面,所以输出的是“eacdm” 可以看到:

lengthOfLongestSubstring

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串”” 示例:

输入:["flower","flow","flight"]
输出:"fl"

说明 所有的输入只包含小写字母a-z

  • 解法一

暴力循环法,从题目可知:最长公共前缀的长度一定是字符串数组中长度最短的哪个字符串

  1. 首先找出长度最短的字符串str,比如str=”abcf”。
  2. 以此对’abcf’,’abc’,’ab’,’a’进行筛选,判断哪个是所有的其他字符串的前缀。
  • 解法二

看下图:

longestCommonPrefix

对str[0]按照字符遍历,与其他字符串以此比较对应位置上的字符,并记录查找位置,如果找到不相等或者对应字符串的长度到了限制,就找到了。

代码如下:

    func longestCommonPrefix(_ strs: [String]) -> String {
        if strs.count <= 0 {
            return ""
        }
        
        if strs.count == 1 {
            return strs[0]
        }
        
        let str = strs[0]
        for i in 0..<str.count {
            let c: Character = str[i]
            for j in 1..<strs.count {
                if i == strs[j].count || c != strs[j][i] {
                    let rightIndex = strs[0].index(strs[0].startIndex, offsetBy: i)
                    return String(strs[0][strs[0].startIndex..<rightIndex])
                }
            }
        }
        
        return strs[0]
    }

测试:

let strs2: [String] = ["abcdfj", "abc", "abcmnihiuh", "abcmunh"]
let str2: String = solution.longestCommonPrefix(strs2)
print(str2)

结果:

abc

数组

寻找中间数

给出一个无序数组,求出一个数,使得其左边的数都小于它,右边的数都大于等于它。要求时间复杂度为n

  • 示例
输入:[4,3,2,7,9,10,11,10]
输出:7,9
  • 思路

两次遍历,第一次遍历,记录下每个位置和它之后的那个元素的最小值(当然这个最小值会一直更新,所以这一次遍历完,就是整个数组的最小值),需要一个n的数组,存放的是这个位置和它后面一个位置的较小值,当然如果已经遇到了,最小值,因为会和最小值进行判断,所以后续这个新的数组里存放的都是这个最小值了。

第二次遍历是正常的从左向右遍历,寻找左边大且比右边小的数,也会记住一个最大值。

  • 解法
func findTheMidNumber(_ data: [Int]) -> [Int] {
  var res = [Int]()

  if data.count == 0 {return res}
  if data.count <= 2 {return res}

  var rightMin = [Int](repeating: 0, count: data.count)
  var r_min = data[data.count-1]

  //从右往左,寻找每个位置及其之后的最小数
  for i in (0..<data.count).reversed() {
    if data[i] < r_min {
      r_min = data[i]
    }
    rightMin[i] = r_min
  }

  //从左往右,寻找左边大且比右边小的数
  var l_max = data[0]
  for i in 0..<data.count-1 {
    if data[i] > l_max {
      l_max = data[i]
      if data[i] < rightMin[i+1] {
        res.append(data[i])
      }
    }
  }
  print(res)
  return res
}
  • 测试

_ = findTheMidNumber([4,3,2,7,9,10,11,10])

[7, 9]

三数之和

一个包含n个整数的数组nums,判断nums中是否存在三个元素a,b,c,使得a+b+c=0?请找出所有满足条件且不重复的三元组

注意:不可以包含重复的三元组

  • 示例
输入:nums=[-1,0,1,2,-1,-4]
输出:[[-1,0,1], [-1,-1,2]]
  • 思路

除非三个数全是0,否则肯定会有正数和负数,所以假定选择一个数,然后再去找另外两个数,这样只要找到两个数且和为第一个选择的数的相反数。

  1. 从小到大排序
  2. 循环
  3. 如果最小的数大于0,直接结束(因为必须要有负数)

sort_algorithm

相当于两数之和问题:a+b=target,因为是排好序的,选定了i,那么j+k需要是i的相反数,如果j+k<target,则j++,否则k–,j和k是右边数组的首末两端

  • 解法
func threeSum(_ nums: [Int])->[[Int]]? {
  var tempNums = nums

  if nums.count <= 0 {return nil}
  //排序
  insertSort(arr: &tempNums)
  if tempNums[0] > 0 {return nil}

  var res = [[Int]]()

  for i in 0..<tempNums.count {
    let target = -tempNums[i]

    var j = i+1
    var k = tempNums.count-1

    while k-j > 0 {
      let numj = tempNums[j]
      let numk = tempNums[k]

      if numj+numk < target {
        j += 1
      } else if numj+numk > target {
        k -= 1
      } else {
        //找到,返回i,j,k
        res.append([tempNums[i],numj,numk])
        break
      }
    }
  }

  return res
}
  • 测试
let res = solution.threeSum([-1,0,1,2,-1,-4])
  • 结果

[[-1, -1, 2], [-1, 0, 1]]

岛屿最大面积

给定一个包含了一些 01 的非空二维数组 grid

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为 0 。)

  • 示例
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ,因为岛屿只能包含水平或垂直的四个方向的 1

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

  • 解法
func dfs(_ i: Int,_ j: Int,_ m: Int,_ n:Int,_ grid: inout [[Int]],_ tempArea: inout Int) -> Int {
  if i<0 || i>=m || j<0 || j>=n || grid[i][j] == 0 {
    return tempArea
  }
  grid[i][j] = 0
  tempArea += 1
  tempArea = dfs(i+1, j, m, n, &grid, &tempArea)
  tempArea = dfs(i-1, j, m, n, &grid, &tempArea)
  tempArea = dfs(i, j+1, m, n, &grid, &tempArea)
  tempArea = dfs(i, j-1, m, n, &grid, &tempArea)
  return tempArea
}

func maxAreaOfIsland(_ grid: [[Int]]) -> Int {
  var tempGrid = grid
  var area = 0
  let m = tempGrid.count
  var n = 0
  var islandMax = 0
  for i in 0..<m {
    n = tempGrid[i].count
    for j in 0..<n {
      area = 0
      area = dfs(i, j, m, n, &tempGrid, &area)
      islandMax = max(islandMax, area)
    }
  }
  return islandMax
}

最长连续递增序列

给定一个未经排序的整数数组,找到最长且连续的递增序列,并返回该序列的长度。

  • 示例
输入:[1,3,5,4,7]
输出:3
解释:最长递增序列是[1,3,5], 长度为3

输入:[2,2,2,2]
输出:1
解释:最长连续递增序列是[2], 长度为1

:数组长度不超过10000

  • 思路
    • count 为当前元素峰值,ans为最大峰值
    • 初始化 count=1
    • 从0位置开始遍历,遍历是根据前后元素状态判断是否递增,递增则count++,递减count=1
    • 如果count>ans,则更新ans
    • 直到循环结束
  • 解法
func findLengthOfLCIS(_ nums: [Int])->Int {
  if nums.count <= 1 {return nums.count}
  var ans = 1
  var count = 1

  for i in 0..<nums.count-1 {
    if nums[i+1] > nums[i] {
      count += 1
    } else {
      count = 1
    }

    ans = count>ans ? count : ans
  }

  return ans
}
  • 结果

print(solution.findLengthOfLCIS([1,3,5,4,7]))

3

数组中的第K大的元素

在未排序的数组中找到第k大的元素。

  • 示例
输入: [3,2,1,5,6,4], k=2
输出:5

输入: [3,2,3,1,2,4,5,5,6], k=4
输出:4

假设k总是有效的,且1<=k<=数组长度

  • 思路

改进快速排序算法,求得第k大的元素,不需要将快速排序完全进行完,只需要进行一遍的递归,如果q刚好是第k大,则打完收工。

  • 解法
//寻找pivot的函数
func partition(arr: inout [Int], left: Int, right: Int) -> Int {
  let pivot = left
  var index = pivot+1
  for i in index...right {
    if arr[i] < arr[pivot] {
      arr.swapAt(i, index)
      index+=1
      //i和index都更新,以pivot为分隔,两边都冒泡,后面再将假设的pivot替换为真正的pivot,然后继续递归
    }
  }
  //此处相当于pivot需要更新
  arr.swapAt(pivot, index-1)
  return index-1
}

func findKthLargest(_ nums: inout [Int], _ k: Int) -> Int {
  return quickSelect(&nums, 0, nums.count-1, nums.count-k)
}

func quickSelect(_ a: inout [Int], _ l: Int, _ r: Int, _ index: Int) -> Int {
  let q = partition(arr: &a, left: l, right: r)
  if q == index {
    return a[q]
  } else {
    return q<index ? quickSelect(&a, q+1, r, index) : quickSelect(&a, l, q-1, index)
  }
}
  • 结果

var nums = [3,2,3,1,2,4,5,5,6]

let r10 = solution.findKthLargest(&nums, 4)

4

最长连续增序列

给定一个未排序的整数数组,找出最长连续增序列的长度。

要求算法复杂度O(n)

  • 示例
输入:[100,4,200,1,3,2]
输出:4
解释:最长连续序列是[1,2,3,4]。长度为4
  • 思路

使用hashmap来保存数组中已经遍历过的元素,key对应元素的值,value表示该元素所在的连续子数组的长度。如果hash中存在此元素,则遍历下一个元素。如果不存在,则看hashmap中是否存在在此元素的前一个元素,比如如果遍历到5时,看看hash中是否存在4,如果存在则取该连续子数组的子一个元素,将它value值+1,并将该元素放到hashmap中,value值与第一个元素值相同,都表示该连续子数组的长度。如果hashmap中存在的该元素遍历到5时,hashmap中是否存在6,将次元素加入到最后一个连续的子数组中,并且和2中一样,找到子数组的第一个和最后一个元素,将它们的value值更新为子数组的长度。

swift解法简单,先排好序,然后判断i-1的值+1是否等于i的值,是的话,则继续向后,否则,当前和记录的最大值比较,currentstreak=1初始化

  • 解法
func longestConsecutive(_ nums: [Int]) -> Int {
  guard nums.count > 0 else { return 0 }
  let nums = nums.sorted(){$0 < $1}
  
  var longestStreak = 1
  var currentStreak = 1
  for i in 1..<nums.count {
    if nums[i] != nums[i - 1] {
      if nums[i - 1] + 1 == nums[i] {
        currentStreak += 1
      } else {
        longestStreak = max(longestStreak, currentStreak)
        currentStreak = 1
      }
    }
  }
  return max(longestStreak, currentStreak)
}

按频率对整数数组进行排序

应该按频率对数组排序,如果相同的频率则对整数排序

  • 示例
输入:1 1 1 1 1 2 1 2 3 3 3 3 3
输出:1 1 1 1 1 1 3 3 3 3 3 2 2
  • 思路

用hashmap存放数字出现的次数,然后对hashmap的value进行排序

代码实现:

func sortFrequencyArray(source: [Int]) -> [Int] {
  if source.count <= 1 {
    return source
  }

  //key是数字,value是出现的频率
  var hashTable: Dictionary<Int, Int> = [Int:Int]()
  for i in 0..<source.count {
    let key: Int = source[i]

    if hashTable.keys.contains(key) {
      //更新数值
      var value = hashTable[key]
      value! += 1
      hashTable[key] = value
    } else {
      hashTable[key] = 1
    }
  }

  let values = hashTable.sorted{
    if $0.1 == $1.1 {
      //如果value(频率)相等,则按照key倒序
      return $0.0 > $1.0
    }

    //如果value(频率)不等,则按照value倒序
    return $0.1 > $1.1
  }

  var result: [Int] = [Int]()

  for i in 0..<values.count {
    for _ in 0..<values[i].1 {
      result.append(values[i].0)
    }
  }

  return result
}
  • 测试
let array6 = [8,8,8,8,8,8,8,8,8,8,8,8,8,7,7,1,1,6,6,1,1,1,2,1,2,4,4,3,3,5,5]
let array7 = solution.sortFrequencyArray(source: array6)
print(array7)
  • 结果

[8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 1, 1, 1, 1, 1, 1, 7, 7, 6, 6, 5, 5, 4, 4, 3, 3, 2, 2]

链表

合并两个排过序的链表,并将其作为新链表

示例:

输入:1->2->4,1->3->4
输出:1->1->2->3->4->4

思路: 很简单,就是链表遍历,然后变换next就可以了

代码实现:

链表构造

class Node<T> {
    var value: T
    var next: Node<T>?
    init(_ val: T) {
        self.value = val
        self.next = nil
    }
}

class IntLinkList {
    var head: Node<Int>?
    var tail: Node<Int>?
    
    init() {
        tail = nil
        head = tail
    }
    
    var isEmpty: Bool {
        get {
            return head == nil
        }
    }
    
    func append(value: Int) {
        let node = Node(value)
        if tail == nil {
            tail = node
            head = tail
        } else {
            tail!.next = node
            tail = tail!.next
        }
    }
    
    func appendToHead(value: Int) {
        let node = Node(value)
        if head == nil {
            head = node
            tail = head
        } else {
            node.next = head?.next
            head = node
        }
    }
    
    func insertAt(index: Int, value: Int) {
        if index == 0 {
            self.appendToHead(value: value)
        }
        
        var tmp = head
        
        var i: Int = 0
        
        while i != index && tmp == nil {
            tmp = tmp?.next
            i+=1
        }
        
        if i == index {
            let node = Node(value)
            node.next = tmp?.next
            tmp?.next = node
        } else {
            //说明index太大,还没到,链表就走完了
            self.append(value: value)
        }
    }
}

功能

//left和right是已经排好序的链表
    func bindTwoLink(firstList left: IntLinkList, second right: IntLinkList) -> IntLinkList {
        guard !left.isEmpty else {return right}
        
        guard !left.isEmpty else {return right}
        
        let list = IntLinkList()
        
        var currentLeft = left.head
        var currentRight = right.head
        
        if let leftNode = currentLeft , let rightNode = currentRight {
            if leftNode.value < rightNode.value {
                list.head = leftNode
                currentLeft = leftNode.next
            } else {
                list.head = rightNode
                currentRight = rightNode.next
            }
            list.tail = list.head
        }
        
        while let leftNode = currentLeft, let rightNode = currentRight {
            if leftNode.value < rightNode.value {
                list.tail?.next = leftNode
                currentLeft = leftNode.next
            } else {
                list.tail?.next = rightNode
                currentRight = rightNode.next
            }
            list.tail = list.tail?.next
        }
        
        //此处还有最后两个尾端没有遍历到
        if let leftNode = currentLeft {list.tail?.next = leftNode}
        if let rightNode = currentRight {list.tail?.next = rightNode}
        
        return list
    }

测试:

let list1 = IntLinkList()
list1.append(value: 1)
list1.append(value: 2)
list1.append(value: 4)
list1.append(value: 5)
list1.append(value: 22)

let list2 = IntLinkList()
list2.append(value: 1)
list2.append(value: 3)
list2.append(value: 4)
list2.append(value: 5)
list2.append(value: 6)
list2.append(value: 7)
list2.append(value: 8)

let list = solution.bindTwoLink(firstList: list1, second: list2)

var head = list.head

while head?.next != nil  {
    print(head!.value as Any, terminator: " ")
    head = head!.next
}

print(head!.value)

结果:

1 1 2 3 4 4 5 5 6 7 8 22

反转链表

  • 示例
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
  • 思路

将节点的next指向pre即可

  • 解法
func reverseList(_ head: Node<Int>?) -> Node<Int>? {
  var cur = head
  var last: Node<Int>?
  var next: Node<Int>?

  while (cur != nil) {
    next = cur?.next
    cur?.next = last
    last = cur
    cur = next
  }

  return last
}
  • 结果

let list3 = IntLinkList()

list3.append(value: 10)

list3.append(value: 12)

list3.append(value: 4)

list3.append(value: 5)

list3.append(value: 2)

var prev = solution.reverseList(list3.head)

while prev?.next != nil {

print(prev!.value as Any, terminator: ” “)

prev = prev!.next

}

print(prev!.value)

2 5 4 12 10

树是最常用且非常有用的数据结构之一,通过下图可以很容易理解树的概念。

leetcode_tree

上图展示的是一个拥有5个层级数的树结构。树根root是第0层,从树最外层开始每深入一层,其层级树相应的减1。 树能帮你解决很多问题,包括:

  • 表示对象的层级关系
  • 使查询快速高效
  • 能提供有序的数据链
  • 文本的前缀匹配搜索

swift构造树

class TreeNode<T> {
    var value: T
    var children: [TreeNode] = []
    weak var parent: TreeNode?
    
    init(value: T) {
        self.value = value
    }
    
    func add(child: TreeNode) {
        children.append(child)
        child.parent = self
    }
}

但是这种是没办法被print打印出来的。需要:

extension TreeNode: CustomStringConvertible {
    var description: String {
        var text = "\(value)"
        if !children.isEmpty {
            text += "{"+children.map{$0.description}.joined(separator: ", ")+"}"
        }
        return text
    }
}

搜索:

extension TreeNode where T: Equatable {
    func search(value: T) -> TreeNode? {
        if value == self.value {
            return self
        }
        
        for child in children {
            if let found = child.search(value: value) {
                return found
            }
        }
        
        return nil
    }
}

为数组建立二进制搜索树,并搜索范围内的节点

示例:

输入:int型数组[7, 20,9,10,25,16,2,40]
范围:[9,35]
输出:9,10,20, 25, 16

思路:

构建BST:

class BinarySearchTree<T: Comparable> {
    private(set) public var value: T
    private(set) public var parent: BinarySearchTree?
    private(set) public var left: BinarySearchTree?
    private(set) public var right: BinarySearchTree?
    
    init(value: T) {
        self.value = value
    }
    
    var isRoot: Bool {
        return parent == nil
    }
    
    var isLeaf: Bool {
        return left == nil && right == nil
    }
    
    var isLeftChild: Bool {
        return parent?.left === self
    }
    
    var isRightChild: Bool {
        return parent?.right === self
    }
    
    var hasLeftChild: Bool {
        return left != nil
    }
    
    var hasRightChild: Bool {
        return right != nil
    }
    
    var hasBothChildren: Bool {
        return hasLeftChild && hasRightChild
    }
    
    var count: Int {
        return (left?.count ?? 0)+1+(right?.count ?? 0)
    }
  
    func insert(value: T) {
        if value < self.value {
            if let left = left {
                left.insert(value: value)
            } else {
                left = BinarySearchTree(value: value)
                left?.parent = self
            }
        } else {
            if let right = right {
                right.insert(value: value)
            } else {
                right = BinarySearchTree(value: value)
                right?.parent = self
            }
        }
    }
}

功能函数:

//获取[9,35]
    func findTree(tree: BinarySearchTree<Int>) {
        if tree.value <= 9 {
            //在右边找
            if tree.value == 9 {
                print(tree.value, terminator: " ")
            }
            
            if tree.hasRightChild {
                findTree(tree: tree.right!)
            }
        } else if tree.value >= 35 {
            //在左边找
            if tree.value == 35 {
                print(tree.value, terminator: " ")
            }
            
            if tree.hasLeftChild {
                findTree(tree: tree.left!)
            }
        } else if tree.value > 9 && tree.value < 35 {
            print(tree.value, terminator: " ")
            if tree.hasLeftChild {
                findTree(tree: tree.left!)
            }
            if tree.hasRightChild {
                findTree(tree: tree.right!)
            }
        }
    }

测试:

let tree = BinarySearchTree<Int>(value: 7)
tree.insert(value: 20)
tree.insert(value: 9)
tree.insert(value: 10)
tree.insert(value: 25)
tree.insert(value: 16)
tree.insert(value: 2)
tree.insert(value: 40)
print(tree)

(2) <- 7 -> ((9 -> (10 -> (16))) <- 20 -> (25 -> (40)))

20 9 10 16 25

杂项

产生不重复的随机数

  • 思路

设想一下,有n个苹果,有不同的编号,从1-n,每次拿一个出来。来产生不同的随机数

  • 实现
func randomNumberWithoutDuplication(_ number: Int) -> [Int] {
  var resultArr = Array(repeating: 0, count: number)
  var startArr = Array(1...number)

  for i in 0..<startArr.count {
    let currentCount = UInt32(startArr.count-i)
    let index = Int(arc4random_uniform(currentCount))
    resultArr[i] = startArr[index]
    startArr[index] = startArr[Int(currentCount) - 1]
  }

  return resultArr
}
  • 测试

let aaa = solution.randomNumberWithoutDuplication(10)

[1, 5, 8, 9, 4, 3, 10, 2, 6, 7]

求解n!的结果中有多少个0

  • 思路

    首先我们知道10=25,所以有多少个0取决于有多少个25。而n!中包含5的因子的个数,可以用下面的表达式来计算

    k= n/5+n/5^2+n/5^3+…

    同样的n!包含2的因子的个数可以用下面的表达式来计算

    m= n/2+n/2^2+n/2^3+…

    很显然m>k。所以末尾0的个数是min(m,k)也就是k了。

  • 实现

    func trailing_zero_num(number: Int) -> Int {
      var num = 0
      var n = number
      while Bool(truncating: n as NSNumber) {
        num += n/5
        n = n/5
      }
      return num
    }
    

多线程交替打印A,B分别10次

  • 实现
func outABWithGCD() {
  let queue1 = DispatchQueue(label: "com.queue1.a", qos: .utility)
  let queue2 = DispatchQueue(label: "com.queue2.b", qos: .utility)

  var change: Bool = true

  queue1.async {
    var count1 = 0
    while true {
      if change {
        print("queue1:A")
        change = false
        count1+=1
      }

      if count1 == 10 {
        break
      }
    }
  }

  queue2.async {
    var count2 = 0
    while true {
      if !change {
        print("queue2:B")
        change = true
        count2+=1
      }

      if count2 == 10 {
        break
      }
    }
  }
}
  • 示例
solution.outABWithGCD()
  • 结果

queue1:A

queue2:B

queue1:A

queue2:B

queue1:A

queue2:B

queue1:A

queue2:B

queue1:A

queue2:B

queue1:A

queue2:B

queue1:A

queue2:B

queue1:A

queue2:B

queue1:A

queue2:B

queue1:A

queue2:B

动态或贪心

买卖股票的最佳时机

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

如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。

注意: 你不能再买入股票前卖出股票。

  • 示例
输入:[7,1,5,3,6,4]
输出: 5
解释: 在第2天(股票价格=1)的时候买入,在第5天(=6),最大利润=6-1=5.注意利润不可能是7-1

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

需要找到最小的谷之后的最大的峰。 我们可以维持两个变量——minprice 和 maxprofit,它们分别对应迄今为止所得到的最小的谷值和最大的利润(卖出价格与最低价格之间的最大差值)。

  • 解法
func maxProfit(_ prices: [Int]) -> Int {
  var minPrice = Int.max
  var maxProfit = 0
  for i in 0..<prices.count {
    if prices[i] < minPrice {
      minPrice = prices[i]
    } else if prices[i] - minPrice > maxProfit {
      maxProfit = prices[i]-minPrice
    }
  }

  return maxProfit
}
  • 结果

print(solution.maxProfit([7,1,5,3,6,4]))

5

买卖股票的最佳时机II

  • 示例
输入:[7,1,5,3,6,4]
输出:7
解释:在第2天(=1)买入,第三天(=5)卖出,利润4,然后在第4天(=3)买入,第5天(=6)卖出,利润3
总利润3+4=7
  • 思路

在斜坡上爬升并持续增加从交易中获得的利润

leetcode_maxprofit

  • 解法
func maxProfitII(_ prices: [Int]) -> Int {
  if prices.count < 2 {
    return 0
  }

  var maxProfit = 0
  for i in 1..<prices.count {
    if prices[i] > prices[i-1] {
      maxProfit += prices[i]-prices[i-1]
    }
  }
  return maxProfit
}
  • 结果

print(solution.maxProfitII([7,1,5,3,6,4]))

7

滑动窗口最大值

给定一个Int窗口,实时的输出窗口最大的元素

  • 示例
输入:k=3,nums=[1,3,-1,-3,5,3,6]
输出:[3,3,5,5,6]
  • 思路

窗口为3个位置,只要有一个最大值进来,比他早的元素永远没有出头之日,所以可以直接忽略掉。

  • 解法
func findMaxInWindow(_ count: Int, _ nums: [Int]) -> [Int] {
  var res = [Int]()

  if nums.count < 0 {
    return []
  }

  var maxNum = Int.min

  if nums.count < count {
    for i in 0..<nums.count {
      if nums[i] > maxNum {
        maxNum = nums[i]
      }
    }

    res.append(maxNum)

    return res
  }

  for i in 0..<count {
    if nums[i] > maxNum {
      maxNum = nums[i]
    }
  }

  res.append(maxNum)

  for j in (nums.count-count-1)..<nums.count {
    if nums[j] > maxNum {
      maxNum = nums[j]
    }

    res.append(maxNum)
  }

  return res
}
  • 结果

let r15 = solution.findMaxInWindow(3, [1,3,-1,-3,5,3,6])

print(r15)

[3, 3, 5, 5, 6]

生成小括号字符串

给定固定长度,比如n,生成所有合法的小括号组成形式

  • 示例
输入: n=3
输出: ["((()))", "(()())", "(())()", "()(())", "()()()"]
  • 思路

采用递归,但是要注意,左右括号肯定都是为n个,并且左括号可以随意加(不超过n),但是右括号必须要在左括号大于右括号的时候才可以输入,然后递归即可

  • 解法
func generateParenthesis(_ count: Int) -> [String] {
  var res: [String] = [String]()
  _gen(0, 0, count, "", &res)
  return res
}

func _gen(_ left: Int, _ right: Int, _ count: Int, _ result: String, _ res: inout [String]) {
  //递归出口
  if left == count && right == count {
    res.append(result)
  }

  if left < count {
    _gen(left+1, right, count, result+"(", &res)
  }

  if left > right && right < count {
    _gen(left, right+1, count, result+")", &res)
  }
}
  • 结果

let r16 = solution.generateParenthesis(3)

print(r16)

[”((()))”, “(()())”, “(())()”, “()(())”, “()()()”]