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
}
4. 链表
链表是一串在存储空间上非连续性、顺序的存储结构，由节点进行头尾依次连接而形成链表，每个节点又包括两个部分：数据域和下个节点的指针域
Swift里实现一个链表
- 生成节点
class ListNode {
//数据域
var val: Int
//指针域
var next:ListNode?
init(_ val: Int) {
self.val = val
self.next = nil
}
}
- 实现头插法和尾插法
- 头插法：当前节点插到第一个节点之前
- 尾插法：当前节点插入到链表最后一个节点之后
···
···taapht
