leetcode刷题第十天——栈与队列Ⅱ

本次刷题顺序是按照卡尔的代码随想录中给出的顺序

1047. 删除字符串中的所有相邻重复项

char* removeDuplicates(char* s) {
    int len = strlen(s);
    char* tmp = malloc(sizeof(char) * (len + 1));
    int top = -1, idx = 0;
    while(idx < len) {
        if(top == -1) tmp[++top] = s[idx];
        else {
            if(tmp[top] == s[idx]) top--;
            else tmp[++top] = s[idx];
        }
        idx++;
    }
    tmp[++top] = '\0';
    return tmp;
}

150. 逆波兰表达式求值

bool isNumber(char* ch) {
    if(strlen(ch) > 1 || '0' <= ch[0] && ch[0] <= '9') return true;
    else return false;
}

int evalRPN(char** tokens, int tokensSize) {
    int* st = malloc(sizeof(int)* tokensSize);
    int idx = 0, top = -1;
    while(idx < tokensSize) {
        char* ch = tokens[idx];
        if(!isNumber(ch)){
            switch(ch[0]) {
                case '+': st[top - 1] += st[top]; top--; break;
                case '-': st[top - 1] -= st[top]; top--; break;
                case '*': st[top - 1] *= st[top]; top--; break;
                case '/': st[top - 1] /= st[top]; top--; break;
            }
        }else {
            st[++top] = atoi(ch);
        }
        idx++;
    }
    return st[top];
}

347. 前 K 个高频元素

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

typedef struct {
    int key;
    int value;
    UT_hash_handle hh;
}hash;

typedef struct {
    int H_key;
    int H_value;
}Heap;

Heap* obj;
int Heap_size;

bool cmp(Heap obj1, Heap obj2) {
    return obj1.H_value < obj2.H_value;
}

void swap(Heap* obj1, Heap* obj2) {
    Heap tmp = *obj1;
    *obj1 = *obj2;
    *obj2 = tmp;
}

Heap H_Top() {
    return obj[1];
}

void H_Pop() {
    obj[1] = obj[Heap_size--];
    int idx = 1, t_idx;
    while((idx << 1) <= Heap_size) {//当前结点有子结点时，继续循环
        t_idx = idx << 1;
        if(t_idx < Heap_size && cmp(obj[t_idx + 1], obj[t_idx])) t_idx++;
        if(cmp(obj[idx], obj[t_idx])) return;
        swap(&obj[t_idx], &obj[idx]);
        idx = t_idx;
    }
}

void H_Push(hash x) {
    obj[++Heap_size].H_key = x.key;
    obj[Heap_size].H_value = x.value;
    int idx = Heap_size, t_idx;
    while(idx > 1) {
        t_idx = idx >> 1;
        if(cmp(obj[t_idx], obj[idx])) return;
        swap(&obj[t_idx], &obj[idx]);
        idx = t_idx;
    }
}

int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {
    hash* ha = NULL, * tmp1, * tmp2;
    int idx = 0;
    while(idx < numsSize) {//将数据信息存入哈希表
        HASH_FIND_INT(ha, &nums[idx], tmp1);
        if(tmp1 == NULL) {
            tmp1 = malloc(sizeof(hash));
            tmp1->key = nums[idx];
            tmp1->value = 1;
            HASH_ADD_INT(ha, key, tmp1);
        }else {
            tmp1->value++;
        }
        idx++;
    }

    obj = malloc(sizeof(Heap) * (k + 1));
    Heap_size = 0;
    Heap mid;

    HASH_ITER(hh, ha, tmp1, tmp2) {
        if (Heap_size == k) {
            mid = H_Top();
            if (mid.H_value < tmp1->value) {
                H_Pop();
                H_Push(*tmp1);
            }
        } else {
            H_Push(*tmp1);
        }
    }

    // 返回结果
    *returnSize = k;
    int* ret = malloc(sizeof(int) * k);
    for (int i = 0; i < k; i++) {
        mid = H_Top();
        H_Pop();
        ret[i] = mid.H_key;
    }
    return ret;
}

栈比较适合求解括号匹配、字符去重、逆波兰表达式

今天刷题，顺带复习了哈希表和小根堆的内容。小根堆和大根堆的思维框架是完全二叉树，所以使用数组实现小根堆时，有骚操作，在调整过程中，很妙，多看几遍H_Pop和H_Push的代码，好好体会

写这个系列的博客主要是给自己一个坚持刷题的理由，今天是第十天，感觉敲代码的流畅度有所提高，虽然思维上没有质变，但是相信坚持下去一定会有更大的收获，奥里给！