算法记录

1,字符串反转（oc）

@interface CharReverse : NSObject
void char_reverse(char * cha);
@end

@implementation CharReverse
void char_reverse(char * cha){
    char * begin = cha;
    char * end = cha + strlen(cha) - 1;
    while (begin < end) {
        char temp = *begin;
        *(begin++) = *end;
        *(end--) = temp;
    }
}
@end

//调用
char ch[] = "hellow,world";
char_reverse(ch);
printf("%s\n",ch);

字符串反转（swift）

func reverseString(_ s: inout [Character]) {
    
    guard !s.isEmpty else {
        return
    }
    var j = s.count-1;
    var i = 0;
    var temp: Character;
    while(i < j){ //类似冒泡
        temp = s[i];
        s[i] = s[j];
        s[j] = temp;
        
        i += 1;
        j -= 1;
    }
    
}

var cha:[Character] = ["C", "a", "t", "!", "🐱"]

//调用
reverseString(&cha)

2，单链表反转（oc）

struct Node{
    int data;
    struct Node *next;
};
@interface LinkListReverse : NSObject
struct Node *reserveList(struct Node *head);//链表反转
struct Node *constructList(void);//初始化
void printList(struct Node *head);//打印
@end

@implementation LinkListReverse

struct Node *reserveList(struct Node *head){
    
    struct Node *p = head;
    struct Node *newH = NULL;
    
    while (p != NULL) {
        struct Node *temp = p->next;//获取下个指针避免丢失
        p->next = newH;//接到新的指针头
        newH = p;//反转
        p = temp;//指针后移
    }
    return newH;
}

struct Node *constructList(void){
    struct Node *head = NULL;
    struct Node *cur = NULL;
    for (int i =1; i<5; i++) {
        struct Node * node = malloc(sizeof(struct Node));
        node->data = i;
        
        if (head == NULL) {
            head = node;
        }else{
            cur->next = node;
        }
        cur = node;
    }
    return head;
}

void printList(struct Node *head){
    struct Node * temp = head;
    while (temp!=NULL) {
        printf("node is %d \n",temp->data);
        temp = temp->next;
    }
}
@end

//调用
 struct Node *list = constructList();
    printList(list);
    printf("-----\n");
    struct Node *newList = reserveList(list);
    printList(newList);

3，给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var dic = [Int:Int]()
    for(index,num)in nums.enumerated(){
        print(index,num)
        if let oldIndex = dic[target-num] {
            return [oldIndex,index]
        }else{
            dic[num] = index
        }
    }
    
    return[-1,-1]
}

4,合并2个有序数组

@interface MergeSortedList : NSObject
void mergeSortedList(int a[],int aLen,int b[],int bLen,int result[]);
@end

@implementation MergeSortedList
void mergeSortedList(int a[],int aLen,int b[],int bLen,int result[]){
    int p = 0;//遍历数组a
    int q = 0;//遍历数组b
    int i = 0;//记录当前存储位置
    while (p<aLen && q<bLen) {
        if (a[p] <= b[q]) {
            result[i] = a[p];
            p++;
        }else {
            result[i] = b[q];
            q++;
        }
        i++;
    }
    
    while (p<aLen) {//a数组有剩余，继续遍历a数组并赋值
        result[i] = a[p++];
        i++;
    }
    
    while (q<bLen) {//b数组有剩余，继续遍历b数组并赋值
        result[i] = b[q++];
        i++;
    }
    
}
@end

5,在字符串中找出第一个出现一次的字母 主要考察Hash算法 eg：字母a对应的ASCII值是97，可以记录在数组下标索引为97的位置

char -> index  //通过f(key) = key hash函数关联
存储和查找都通过该函数，有效提高查找效率

@interface HashFind : NSObject
char findFirstChar(char * cha);
@end

@implementation HashFind
char findFirstChar(char * cha){
    char result = '\0';
    //定义一个数组，用来存储各个字母出现的字数
    int array[256];
    //对数组进行初始化操作
    for (int i = 0; i<256; i++) {
        array[i] = 0;
    }
    
    char *p = cha;
    //遍历每个字符
    while (*p != '\0') {
        //在字母对应存储位置，进行出现次数加+1操作
        array[*(p++)]++;//先次数增加后指针p向后移动
    }
    
    p=cha;//重新指向头部，遍历字符串（遍历字符串是为了减少遍历次数）
    while (*p != '\0') {
        //遇到第一次出现次数为1的字符，打印结果
        if (array[*p] == 1) {
            result = *p;
            break;//结束循环
        }
        p++;//继续遍历
    }
    
    return result;
}
@end