算法部分
1.快速排序
/**
快速排序
*/
-(void)quickSort:(NSMutableArray *)arr {
NSInteger left = 0;
NSInteger right = arr.count - 1;
while (left < right) {
while (left < right && arr[left] <= arr[right]) {
[arr exchangeObjectAtIndex:left withObjectAtIndex:right];
right --;
}
while (left < right && arr[left] > arr[right]) {
[arr exchangeObjectAtIndex:left withObjectAtIndex:right];
left ++;
}
}
}
/// 快排
/// - Parameter arr: 要排序的数组
func kuaipai(arr: inout [Int],left: Int,right: Int) {
if left > right {
return
}
var i = left
var j = right
let key = arr[i]
while i < j {
while (i < j && key <= arr[j]) {
j = j - 1
}
while (i < j && key >= arr[i]) {
i = i + 1
}
if (i < j) {
let t = arr[i]
arr[i] = arr[j]
arr[j] = t
}
}
arr[left] = arr[i]
arr[i] = key
kuaipai(arr: &arr, left: left, right: i - 1)
kuaipai(arr: &arr, left: i + 1, right: right)
}
2.冒泡排序
/**
冒泡排序
*/
- (void)bubbleSort:(NSMutableArray *)arrM {
for (NSInteger i = 0; i < arrM.count; i ++) {
for (NSInteger j = 0; j < arrM.count - 1 - i; j++) {
if ([arrM[j] integerValue] < [arrM[j + 1] integerValue]) {
[arrM exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
}
}
}
}
3.希尔排序
希尔排序
*/
- (void)shellSort:(NSMutableArray *)arr{
NSInteger gap = arr.count / 2;//1
while (gap > 0) {
for (NSInteger i = gap; i < arr.count; i ++) {
NSInteger j = i;
while (j - gap >= 0 && [arr[j] integerValue] < [arr[j - gap] integerValue]) {
[arr exchangeObjectAtIndex:j withObjectAtIndex:j - gap];
j -= gap;
}
}
gap = gap / 2;
}
}
4.插入排序
/**
插入排序
*/
- (void)insertionSort:(NSMutableArray *)arr {
for (NSInteger i = 1; i < arr.count; i ++) {
NSInteger temp = [[arr objectAtIndex:i] integerValue];
NSInteger j = i;
while (j > 0 && temp < [[arr objectAtIndex:j-1] integerValue]) {
[arr replaceObjectAtIndex:j withObject:[arr objectAtIndex:j-1]];
j--;
}
[arr replaceObjectAtIndex:j withObject:[NSNumber numberWithInt:temp]];
}
NSLog(@"%@",arr);
}
5.统计出现的字符串
/**
统计出现的字符串
*/
- (void)lettersCount:(NSString *)str {
NSMutableDictionary *dic = [NSMutableDictionary dictionary];
for (NSInteger i = 0; i < str.length; i ++) {
NSString *key = [NSString stringWithFormat:@"%c",[str characterAtIndex:i]];
if (![dic.allKeys containsObject:key]) {
dic[key] = @1;
}else {
NSInteger value = [dic[key] integerValue];
value ++;
dic[key] = [NSNumber numberWithInteger:value];
}
}
NSLog(@"%@",dic);
}
6.push pop
/**
题目：我现在需要实现一个栈，这个栈除了可以进行普通的push、pop操作以外，还可以进行getMin的操作，getMin方法被调用后，会返回当前栈的最小值，你会怎么做呢？你可以假设栈里面存的都是int整数
*/
- (void)push:(NSInteger)data {
[self.dataArr addObject:@(data)];
if (self.dataArr.count > 1) {
if (data < [self.dataArr[self.dataArr.count - 2] integerValue]) {
[self.minsArr addObject:@(self.dataArr.count - 1)];
}
}else {
[self.minsArr addObject:@0];
}
}
- (void)pop {
if (self.dataArr.count > 0) {
if ([self.dataArr.lastObject integerValue] != [self.dataArr[self.minsArr.count - 1] integerValue]) {
[self.minsArr removeLastObject];
}
[self.dataArr removeLastObject];
// return [self.dataArr.lastObject integerValue];
}
////最好抛出异常 -1可能是push的
// return -19574;
}
- (NSInteger)getMin {
if (self.dataArr.count > 0) {
NSInteger index = [[self.minsArr lastObject] integerValue];
return [self.dataArr[index] integerValue];
}
//同上
return -19574;
}
