1. 给出一个整形数组和一个目标值，判断数组中是否有两个数之和等于目标值
// Swift func twoSum(nums:[Int], target: Int) -> Bool { // 初始化集合 var set = Set<Int>() // 遍历整形数组 for num in nums { // 判断集合中是否包含目标值减去当前值的结果 if set.contains(target - num) { return true } // 不包含，将当前值存入集合，用于下次判断 set.insert(num) } //都不包含，返回false return false } // OC - (BOOL)twoSum:(NSArray *)array target:(int)target { NSMutableSet *set = [[NSMutableSet alloc] init]; for (NSNumber *number in array) { if ([set containsObject:[NSNumber numberWithInt:target - [number intValue]]]) { return true; } [set addObject:number]; } return false; }
2. 在这道题的基础上做修改:给定一个整型数组中有且仅有 两个数之和等于目标值,求这两个数在数组中的序号.
func twoSum1(nums:[Int], target: Int) -> [Int] { //初始化字典 var dict:[Int:Int] = [:] for (index, num) in nums.enumerated() { //从dict字典中取出之前保存的索引，判断索引是否存在 if let lastIndex = dict[target - num] { //返回之前存的索引和当前的索引 return [lastIndex, index]; } else { //保存当前索引，用于后续判断 dict[num] = index } } fatalError("No valid output !") } - (NSMutableArray *)twoSum:(NSArray *)array target:(int)target { NSMutableArray *idxArray = [NSMutableArray array]; NSMutableDictionary *dict = [[NSMutableDictionary alloc] init]; for (int i = 0; i < array.count; i ++) { int num = [array[i] intValue]; NSString *lastNumber = [NSString stringWithFormat:@"%d", target - num]; if ([dict.allKeys containsObject:lastNumber]) { [idxArray addObject:dict[lastNumber]]; [idxArray addObject:[NSNumber numberWithInt:i]]; } else { NSString *key = [NSString stringWithFormat:@"%d", num]; [dict setValue:[NSNumber numberWithInt:i] forKey: key]; } } return idxArray; }
3. 给出一个字符串，要求将其按照单词顺序进行反转
eg: 输入 "hello world" ，输出"world hello"
//按照单词翻转字符串 hello world -> world hello func reversalStringWithWords(inputString: String?) -> String? { guard let inputString = inputString else { return nil } let array = inputString.components(separatedBy: " ") var resultArray:[String] = [] for obj in array { resultArray.insert(obj, at: 0) } return (resultArray as NSArray).componentsJoined(by: " ") }
4. 字符串反转 hello world -> dlrow olleh
func reversalString(inputString: String?) -> String? { guard let inputString = inputString else { return nil } var outputString = "" for (_, str) in inputString.enumerated() { outputString.insert(str, at: outputString.startIndex) } return outputString }
5. 快速排序
func quickSort(_ array: [Int]) -> [Int] { guard array.count > 1 else { return array } let temp = array[array.count / 2 ] let left = array.filter{$0 < temp} let middle = array.filter{$0 == temp} let right = array.filter{$0 > temp} return quickSort(left) + middle + quickSort(right) } func quickSort1(_ array: [Int]) -> [Int] { guard array.count > 1 else { return array } let temp = array[array.count/2] var left: [Int] = [], middle: [Int] = [], right: [Int] = [] for obj in array { if obj < temp { left.append(obj) } else if obj == temp { middle.append(obj) } else { right.append(obj) } } if left.count == 0 && right.count == 0 { return quickSort1(left) + middle + quickSort1(right) } else { return quickSort1(left) + quickSort1(middle) + quickSort1(right) } }
5. // 二分法查找有序数组中是否包含数字x, [1, 2, 3, 4, 6, 8, 9] 4 -> true
func binarySearch(_ nums: [Int], target: Int) -> Bool { var left = 0, middle = 0, right = nums.count - 1 while left <= right { middle = (right - left) / 2 + left if nums[middle] == target { return true } else if nums[middle] < target { left = middle + 1 } else { right = middle - 1 } } return false }
6. 链表
链表是一串在存储空间上非连续性、顺序的存储结构，由节点进行头尾依次连接而形成链表，每个节点又包括两个部分：数据域和下个节点的指针域
Swift里实现一个链表
- 生成节点
class ListNode { //数据域 var val: Int //指针域 var next:ListNode? init(_ val: Int) { self.val = val self.next = nil } }
- 实现头插法和尾插法
- 头插法：当前节点插到第一个节点之前
- 尾插法：当前节点插入到链表最后一个节点之后
···
···taapht
