高频面试算法：leetCode算法（swift实现一）

1、算法一：给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
a、例如：[2,5,3,7,4],k=2;结果为：[7,4,1,5,3]

///inout在swift中表示传地址进入
func rotate( arr:inout [Int],k:Int){
  for _ in 0..<k{
      let lastV = arr[arr.count-1]
      for index in 0..<arr.count-1{
          let last = arr.count-1-index
          arr[last] = arr[last-1]
      }
      arr[0] = lastV
  }
  print("rotate:\(arr)")
}

2、算法二：
==给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
==请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
==注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。
==为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。[2,6,8,9,14,67,0,0,0,0], num2: [12,23,34,45]

///思路：直接num2合并到num2，并进行相应判断移动
 func merge(num1:[Int],m:Int,num2:[Int],n:Int){
     var result = num1
     var i = n-1
     var j = m-1
     var offset = n+m-1
     while(i >= 0){
         let r2 = num2[i]
         let r1 = num1[j]
         if r2 > r1{
             result[offset] = r2
             i -= 1
         }else{
             result[offset] = r1
             j -= 1
         }
         offset -= 1
     }
     print("merge: origin:\(num1)  result:\(result)")
 }

3、算法三：设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
==规律分析：n=1，f(1)=1；n=2，f(2)=2；n=3，f(3)=3；n=4，f(4)=5；n=5，f(5)=8；...；n=n，f(n-2)+f(n-1)
==使用递归的方式实现

func climStairs(n:Int) -> Int{
   if n <= 2{
       return n
   }
   return climStairs(n: n-1) + climStairs(n: n-2)
}

4、算法四：数字加一：给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。

func plusOne(array:[Int]){
      var arr = array
      let count = arr.count
      let one = 1
      for i in 0..<count{
          let index = count - i - 1
          let value = arr[index]
          if value < 9{
              arr[index] = arr[index] + one
              break
          }else{
              arr[index] = 0
              if index <= 0{
                  arr.insert(1, at: 0)
              }
          }
      }
      print("plus one:\(arr)")
  }

5、算法五：树的中序遍历

 /// MARK:初始化二叉树
  func setupTree(){
      let node1 = Node().value(1)
      let node2 = Node().value(2)
      let node3 = Node().value(3)
      let node4 = Node().value(4)
      let node5 = Node().value(5)
      let node6 = Node().value(6)
      node1?.left(node2)
      node1?.right(node3)
      node2?.left(node4)
      node2?.right(node5)
      node3?.right(node6)
      intermediateSequence(node: node1)
  }
  /// MARK:中序遍历
  func intermediateSequence(node:Node?){
      if node == nil{return}
      intermediateSequence(node: node?.tleft)
      print("--\(node!.tvalue)--")
      intermediateSequence(node: node?.tright)
  }
  class Node : NSObject{
      var tleft : Node? = nil
      var tright : Node? = nil
      var tvalue : Int = 0
      
      @discardableResult
      func left(_ left:Node?) -> Node?{
          self.tleft = left
          return self
      }
      
      @discardableResult
      func right(_ right:Node?) -> Node?{
          self.tright = right
          return self
      }
      
      @discardableResult
      func value(_ value:Int) -> Node?{
          self.tvalue = value
          return self
      }
  }

转载请标明出处