二分查找，复杂度 logn
var list = [1,2,3,5,7,8]
var item = 2
var low = 0
var high = list.count - 1
while low<=high {
let mid = (low + high)/2
let guess = list[mid]
if item > guess{
low = mid+1
}else if item == guess{
print("找到了:",mid)
break
}else{
high = mid-1
}
}
选择排序
var list = [1,4,21,5,7,8]
for i in 0...list.count-1{
var j = i+1
var minValue = list[i]
var minIndex = i
//寻找无序部分最小值
while j<list.count {
if list[j]<minValue{
minValue = list[j]
minIndex = j
}
j += 1
}
//交换最小值和当前位置
list.swapAt(minIndex, i)
}
print(list)
数组递归求和
var list = [1,2,3,5]
func sum(list:[Int],len:Int)->Int{
if len == 1{
return list[0]
}else{
return list[len-1] + sum(list: list, len: len-1)
}
}
快速排序
nlogn
func quickSort(array:[Int])->[Int] {
if array.count < 2 {
return array;
} else {
let midValue = array[0];
let lessArr:[Int] = array.filter { $0 < midValue };
let moreArr:[Int] = array.filter { $0 > midValue };
return quickSort(array: lessArr) + [midValue] + quickSort(array: moreArr);
}
}
quickSort(array: list);
广度优先BFS
var graph:[String: [String]] = Dictionary()
graph["me"] = ["bob","alice","claiee"]
graph["bob"] = ["peggy","me"]
graph["alice"] = ["hallen","rick"]
graph["claiee"] = ["rick"]
var searchQueue = [String]()
searchQueue = graph["me"]!
var route = [String]()
var searched = [String]()
while searchQueue.count != 0 {
let person = searchQueue.first!
//print(searchQueue)
searchQueue.removeFirst()
route.append(person)
//检查是否被标记
if !searched.contains(person){
if person == "ricck" {
print("find him")
print(route)
break
}else{
//如果检查过了，就将此人进行标记不再检查
searched.append(person)
if (graph[person] != nil){
searchQueue += graph[person]!
}
}
}
if searchQueue.count == 0{
print("cound't find him")
}
}
树的相关操作
class TreeNode{
var left:TreeNode?
var right:TreeNode?
var value:Int = 0
init(value:Int) {
self.value = value
}
}
//leetcode
//Given a binary tree, find its minimum depth.
//The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
func run(root:TreeNode?)->Int{
if(root == nil){
return 0
}
let left = run(root: root?.left)
let right = run(root: root?.right)
if left == 0 || right == 0{
return left+right+1
}
return min(left, right)+1
}
//求树的深度
func maxDepth(root:TreeNode?)->Int{
guard let root = root else{
return 0
}
return max(maxDepth(root: root.left), maxDepth(root: root.right))
}
//前序遍历
func preOrder(root:TreeNode?)->[Int]{
var res = [Int]()
var stack = [TreeNode]()
var node = root
while !stack.isEmpty || node != nil {
if node != nil{
res.append(node!.value)
stack.append(node!)
node = node!.left
}else{
node = stack.removeLast().right
}
}
return res
}
leetCode 150. 逆波兰表达式求值
根据逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: ((2 + 1) * 3) = 9
示例 2：
输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: (4 + (13 / 5)) = 6
var tockens = ["2", "1", "+", "3", "*"]
func evalRPN(tocken:[String])->Int{
var stack = [Int]()
for i in tocken{
if let num = Int(i){
stack.append(num)
}else{
let b = stack.removeLast()
let a = stack.removeLast()
stack.append(get(a: a, b: b, op: i))
}
}
return stack.removeLast()
}
func get(a:Int,b:Int,op:String)->Int{
switch op {
case "+":
return a+b
case "-":
return a-b
case "*":
return a*b
case "/":
return a/b
default:
return 0
}
}
evalRPN(tocken: tockens)
//剑指OFFER
/*
在一个二维数组中（每个一维数组的长度相同），
每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
*/
func findMetrix(target:Int,array:[[Int]])->Bool{
let row = array.count - 1
let col = array[0].count - 1
//从左下角开始找,大的话往上移动，小的话往右移动
var i = row
var j = 0
while j<=col && i >= 0 {
if target > array[i][j]{
j += 1
}else if target < array[i][j]{
i -= 1
}else{
return true
}
}
return false
}
阶乘计算
func sum(n:Int)->Int{
if n == 1{
return 1
}else{
return n*sum(n: n-1)
}
}
sum(n: 4)//4
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
func findRotateMinNumber(array:[Int])->Int{
if (array.isEmpty){
return 0
}
for i in 0..<array.count-1{
if (array[i]>array[i+1]){
return array[i+1]
}
}
return array[0]
}
findRotateMinNumber(array: [4,5,6,1,2,3])
跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）
func jumpFloor(num:Int)->Int{
if num == 1{
return 1
}else if num == 2{
return 2
}else{
return jumpFloor(num: num-1)+jumpFloor(num: num - 2)
}
}
//变态青蛙跳台阶,可以跳任意阶数
func jumpFloor2(num:Int)->Int{
if num == 1{
return 1
}else{
return 2*jumpFloor(num: num-1)
}
}
幂函数实现：
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
func power(ex:Int,base:Double)->Double{
var result:Double = 1.0
for _ in 0...abs(ex){
result *= base;
}
//正负数
if ex >= 0 {
return result
}else{
return 1/result
}
}
power(ex: 10, base: 2.0)
数组奇数前偶数后
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
func reOrderArray(array:[Int])->[Int]{
var even = [Int]()
var odd = [Int]()
for i in array{
if i%2 == 0{
odd.append(i)
}else{
even.append(i)
}
}
return odd+even
}
var AR = [1,3,4,12,4,5,7]
reOrderArray(array: AR)//[4, 12, 4, 1, 3, 5, 7]
链表
//链表
class ListNode{
var val:Int = 0
var next:ListNode?
init(val:Int) {
self.val = val
}
}
//翻转链表
func reverseList(pHead:ListNode?)->ListNode?{
var pHead = pHead
if pHead == nil || pHead?.next == nil{
return pHead
}
var last:ListNode?
while (pHead != nil) {
let tem = pHead?.next
pHead?.next = last
last = pHead
pHead = tem
}
return last
}
//字符串的全排列
func permutations( ss:inout [String],start:Int){
if start == ss.count-1{
print(ss)
}else{
for i in start..<ss.count{
ss.swapAt(start, i)
permutations(ss: &ss, start: start+1)
ss.swapAt(i, start)
}
}
}
var test = ["a","b","c"]
permutations(ss: &test, start: 0)
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
//数组旋转输出
func printMetrix(matrix:inout [[Int]]){
var result = [Int]()
print(matrix)
while matrix.count>0 {
result += matrix.removeFirst()
if matrix.count<=0{
break
}
turn(matrix: &matrix)
print(result)
}
//print(result)
}
func turn( matrix:inout [[Int]]){
var nemat = [[Int]]()
for i in 0..<matrix[0].count{
var nemat2 = [Int]()
for j in 0..<matrix.count{
nemat2.append(matrix[j][i])
}
// nemat2.reverse()
nemat.append(nemat2)
}
nemat.reverse()
matrix = nemat
}
网友评论